Maximum pipelining linear recurrence on static data flow computers | International Journal of Parallel Programming Skip to main content
Springer Nature Link
Log in

Maximum pipelining linear recurrence on static data flow computers

  • Published:
International Journal of Parallel Programming Aims and scope Submit manuscript

Abstract

This paper investigates the principles of mapping linear recurrences on static data flow computers. For a linear recurrence with a single variable, the key is to properly introduce a feedback loop in the machine level data flow graphs. We show that, in order to achieve maximum pipelining, thecritical dependence delay of the recurrence must be matched with the necessarycomputational delay of the graph. Two possible mapping techniques are discussed, which are (1) changing the dependence delay by introducing an additional companion pipeline; (2) changing the computational delay by inserting FIFOs. The mapping of the Valfor-iter construct, the major language feature for expressing recurrences in Val, is outlined.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. R. W. Hockney and C. R. Jesshope,Parallel Computers, Adam Hilger Ltd, Bristol, (1981).

    Google Scholar 

  2. D. J. Kuck, A Survey of Parallel Machine Organization and Programming,Computing Surveys, Vol 9, No. 1, (March 1977).

  3. D. D. Gajski, An Algorithm for Solving Linear Recurrence System on Parallel and Pipelined Machines,IEEE Trans. on Computers, Vol. C-30, No. 3, (March 1982).

  4. P. M. Kogge, A Parallel Algorithm for Efficient Solution of a General Class of Recurrence Equations.IEEE Trans. Comput., Vol. C-22, No. 8, (August 1973).

  5. P. M. Kogge, Maximum Rate Pipelined Solutions to Recurrence Problems, inProc. 1st Computer Architecture Symp. pp. 71–76 (December 1973).

  6. P. M. Kogge, Parallel Solutions of Recurrence ProblemsIBM J. Res. Develop., Vol. 18, No. 2 (March 1974).

  7. D. J. Kuck,The Structure of Computers and Computation, Vol. 1, John Wiley & Sons Inc., (1978).

  8. D. Heller, Some Aspects of the Cyclic Reduction Algorithm for Block Tridiagonal Linear Systems,SIAM J. on Numerical Analysis, Vol. 13, ICASE Report (1976).

  9. T. Jordan,A New Parallel Algorithm for Diagonally Dominant Triangular Matrices, Los Alamos Scientific Lab, Los Alamos, NM. (1974).

    Google Scholar 

  10. H. Stone, Parallel Tridiagonal Equation Solvers,ACM Trans. on Math. Software, Vol. 1, (1975).

  11. Arvind and R. A. Iannucci, A Critique of Multiprocessing von Neumann StyleProc. of the Tenth Int. Symp. on Computer Architecture”, (June 1983).

  12. J. B. Dennis and D. P. Misunas. A Preliminary Architecture for a Basic Data-Flow Processor.The Second Annual Symp. on Computer Architecture Conf. Proc. pp. 126–132 (January 1975).

  13. J. B. Dennis, Y-P. L. Willie, and W. B. Ackerman, The MIT Data Flow Engineering Model,Proc. of the IFIP Ninth World Computer Congress, Paris, France, (September 1983).

  14. K. W. Todd, An Interpreter for Instruction Cells. Computation Structure Group Memo 208, Laboratory for Computer Science, MIT, Cambridge, MA, (August 1982).

    Google Scholar 

  15. J. B. Dennis, G. R. Gao and K. Todd, Modeling the Weather with a A Data Flow Supercomputer,IEEE Trans. on Computer,C-33, No. 7, (July 1984).

  16. J. B. Dennis and G. R. Gao, Maximum Pipelining of Array Operations on Static Data Flow Machine,Proc. of the Int. Conf. on Parallel Processing, (August 1983).

  17. W. B. Ackerman, Data Flow Languages, AFIPS Proceedings, Vol. 48: Proceedings of the National Computer Conference, AFIPS, (1979).

  18. W. B. Ackerman and J. B. Dennis, Val—A Value-Oriented Algorithmic Language Preliminary Reference Manual. Technical Report 218, Laboratory for Computer Science, MIT, Cambridge, MA, (June 1979).

    Google Scholar 

  19. J. R. McGraw, The Val Language: Description and Analysis,ACM Transaction on Programming Languages and Systems, Vol. 4, No. 1, (January 1982).

  20. G. R. Gao, An Implementation Scheme for Array Operations in Static Data Flow Computer MS Thesis, Laboratory for Computer Science, MIT, Cambridge, MA, (June 1982).

    Google Scholar 

  21. G. R. Gao, A Pipelined Code Mapping Scheme for Static Data Flow Computer, Ph.D dissertation, Lab for Computer Science, (September 1986).

  22. P. M. Kogge,The Architecture of Pipelined Computers, McGraw-Hill Company, New York, (1981).

    Google Scholar 

  23. L. M. Ni and K. Hwang, Vector Reduction Methods for Arithmetic Pipelines,Proc. of the Sixth Int. Symp. on Computer Arithmetic, (June 1983).

  24. L. M. Ni and K. Hwang, Pipelined Evaluation of First-Order Recurrence Systems,Proc. of the Int. Conf. on Parallel Processing, (August 1983).

  25. H. T. Kung, Why Systolic Architecture?,IEEE Computers, Vol 15., No. 1, (January 1982).

  26. M. C. Chen, A Methodology for Hierarchical Simulation of VLSI Systems, Technical Report 325, Yale Univ. (August 1984).

  27. M. C. Chen, The Generation of a Class of Multipliers: A synthesis Approach to the Design of Highly Parallel Algorithms in VLSI,Proc. of the ICCD, (October 1985).

  28. G. J. Li and B. W. Wah, The Design of Optimal Systolic Arrays,IEEE Trans. on Computers, Vol. C-34, No. 1, (January 1985).

  29. D. I. Moldovan, Advis: A software Package for the Design for Algorithms for VLSI Systolic Arrays,Proc. of ICCD, (1984).

  30. P. Quinton, Automatic Synthesis of Systolic Arrays from Uniform Recurrence Equations,Proc. of the 11th Annual Symp. on Computer Architecture, (1984).

  31. G. R. Gao, Homogeneous Approach of Mapping Data Flow Programs,Proc. of Intl Conf. of Parallel Processing, (August 1984).

  32. G. R. Gao, A Pipelined Code Mapping Scheme for Solving Tridiagonal Linear System Equations,Proc. of IFIP Highly Parallel Computer Conf., Nice, France, (March 1986).

  33. G. R. Gao, A Maximally Pipelined Tridiagonal Linear Equation Solver (revised),Intl. J. of Parallel and Distributed Computing, (August 1986).

  34. G. R. Gao, A Stability Classification Method and Its Application to Pipelined Solution of Linear Recurrences,J. of Parallel Computing, North Holland, (to appear).

  35. J. B. Dennis, High Speed Data Flow Computer Architecture for the Solution of Navier-Stokes Equations Computation Structure Group Memo 225, Laboratory for Computer Science, MIT, Cambridge, MA, (1982).

    Google Scholar 

  36. J. B. Dennis, Data Flow for Supercomputers,Proc. of Compcon., (March 1984).

Download references

Author information

Author notes

  1. Guang R. Gao

    Present address: Philips Laboratories, Briarcliff Manor, New York

Authors and Affiliations

    Authors
    1. Guang R. Gao
      View author publications

      You can also search for this author in PubMed Google Scholar

    Additional information

    This research was done at Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA 02139.

    Rights and permissions

    Reprints and permissions

    About this article

    Cite this article

    Gao, G.R. Maximum pipelining linear recurrence on static data flow computers. Int J Parallel Prog 15, 127–149 (1986). https://doi.org/10.1007/BF01414442

    Download citation

    • Received:

    • Revised:

    • Issue Date:

    • DOI: https://doi.org/10.1007/BF01414442

    Key Words

    Search

    Navigation