[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

The mapping of linear recurrence equations on regular arrays

  • Published:
Journal of VLSI signal processing systems for signal, image and video technology Aims and scope Submit manuscript

Abstract

The parallelization of many algorithms can be obtained using space-time transformations which are applied on nested do-loops or on recurrence equations. In this paper, we analyze systems of linear recurrence equations, a generalization of uniform recurrence equations. The first part of the paper describes a method for finding automatically whether such a system can be scheduled by an affine timing function, independent of the size parameter of the algorithm. In the second part, we describe a powerful method that makes it possible to transform linear recurrences into uniform recurrence equations. Both parts rely on results on integral convex polyhedra. Our results are illustrated on the Gauss elimination algorithm and on the Gauss-Jordan diagonalization algorithm.

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
£29.99 /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 (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. R. M. Karp, R. E. Miller, and S. Winograd. The organization of computations for uniform recurrence equations.JACM, 14(3): 563–590, July 1967.

    Article  MathSciNet  MATH  Google Scholar 

  2. L. Lamport. The parallel execution of Do-Loops.Comm. ACM, Vol. 17, N. 2, pp. 83–93, Feb. 1974.

    Article  MathSciNet  MATH  Google Scholar 

  3. P.R. Cappello and K. Steiglitz. Digital signal processing applications of systolic algorithms. InVLSI Systems and Computation, H.T. Kung, B. Sproull, and G. Steel editors, Computer Science Press (1981), 245–254.

  4. M.C. Chen, Synthesizing systolic designs.1985 International Symposium on VLSI Technology, Systems and Applications, Taipei, Taiwan, R.O.C., 8–10 May 1985.

  5. J.M. Delosme and I.C.F. Ipsen. Efficient systolic arrays for the solution of Toeplitz systems: An illustration of a methodology for the construction of systolic architectures for VLSI. In W. Moore, A. McCabe, and R. Urquhart, editors,International Workshop on Systolic Arrays, pages 37–46, Adam Hilger, University of Oxford, UK, July 2–4 1986.

    Google Scholar 

  6. S.Y. Kung. VLSI array processors.IEEE ASSP Magazine, 2(3):4–22, July 1985.

    Article  Google Scholar 

  7. G.H. Li and B.W. Wah. The design of optimal systolic arrays,IEEE Trans. Computers 34, 1 (1985), 66–77.

    MATH  Google Scholar 

  8. W.L. Miranker and A. Winkler. Space-time representations of systolic computational structures.Computing, 32:93–114, 1984.

    Article  MathSciNet  MATH  Google Scholar 

  9. D.I. Moldovan. On the analysis and synthesis of VLSI algorithms,IEEE Trans. On Computer C-31 (11), November 1982, pages 1121–1126.

    Article  Google Scholar 

  10. P. Quinton.The Systematic Design of Systolic Arrays. Technical Report 193, Publication Interne IRISA, April 1983.

  11. S.K. Rao,Regular iterative algorithms and their implementations on processor arrays, PhD Thesis, Information Systems Lab., Stanford Univerity, October 1985.

  12. P. Quinton, Automatic synthesis of systolic arrays from uniform recurrent equationsProc. IEEE 11th Int. Sym. on Computer Architecture, Ann Arbor, MI, 1984, 208–214.

  13. H.T. Kung. Let’s design algorithms for VLSI systems.Proc. of the Caltech conference on VLSI, January 1979.

  14. D.I. Moldovan and J.A.B. Fortes. Partitioning and mapping algorithms into fixed size systolic arrays.IEEE Transaction on Computers, C-35(1):1–12, January 1986.

    Article  Google Scholar 

  15. V. Van Dongen and P. Quinton. The mapping of linear recurrence equations on regular arrays, Manuscript M 264, Philips Research Lab. Brussels, October 1988.

    Google Scholar 

  16. Y. Yaacoby and R. Cappello. Scheduling a system of affine recurrence equations onto a systolic array.International Conference on Systolic Arrays, San Diego, pages 373–381, May 1988.

  17. P. Gachet and B. Joinnault. Conception d’alorithmes et d’architectures systoliques. Thèse de l’Université de Rennes I, Sept 1987.

  18. Y. Saouter and P. Quinton. Computability of recurrence equations, IRISA Research Report, to appear, 1989.

  19. S.V. Rajopadhye and R.M. Fujimoto. Systolic array synthesis by static analysis of program dependencies. In J.W. de Bakker, A.J. Nijman, and PC. Treleaven, editors,Parallel Architectures and Languages Europe, pages 295–310, Springer-Verlag, June 1987.

  20. J.A.B. Fortes and D.I. Moldovan. Data broadcasting in linearly scheduled array processors.Proc. 11th Annual Symp. on Computer Architecutre, pages 224–231, 1984.

  21. Y. Wong and J.M. Delosme. Broadcast removal in systolic algorithms.International Conference on Systolic Arrays, San Diego, pages 403–412, May 1988.

  22. R.H. Kuhn. Optimization and interconnection complexity for: Parallel processors, single-stage networks, and decision trees. Technical Report UIUCDCS-R 80-1009, Univeristy of Illinois at Urbana-Champaign, February 1980.

  23. P. Gachet, B. Joinnault, and P. Quinton. Synthesizing systolic arrays using DIASTOL. In W. Moore, A. McCabe, and R. Urquhart, editors,International Workshop on Systolic Arrays, pages 25–36, Adam Hilger, University of Oxford, UK, July 2–4 1986.

    Google Scholar 

  24. V. Van Dongen and P. Quinton. Uniformization of linear recurrence equations: a step toward the automatic synthesis of systolic arrays.International Conference on Systolic Arrays, San Diego, pages 473–482, May 1988.

  25. B.W. Wah, M. Aboelaze, and W. Shang. Systematic designs of buffers in macropipelines of systolic arrays.Journal of Parallel and Distributed Computing 5, pp. 1–25, 1988.

    Article  Google Scholar 

  26. Y. Robert and D. Trystram. Systolic solution of the algebraic path problem. In W. Moore, A. McCabe, and R. Urquhart, editors,International Workshop of Systolic Arrays, pages 171–180, Adam Hilger, University of Oxford, UK, July 2–4, 1986.

    Google Scholar 

  27. P.S. Lewis and S.Y. Kung. Dependence graph based design of systolic arrays for the algebraic path problem.20th Asilomar Conf., Nov. 10–12, 1986.

  28. C. Mongenet and G.R. Perrin, Synthesis of systolic arrays for inductive problems. In J.W. de Bakker, A.J. Nijmann, and P.C. Treleaven, editors,Parallel Architectures and Languages Europe, pages 260–277, Springer-Verlag, June 1987.

  29. P. Clauss. Contribution à la synthèse de rèseaux systoliques.Rapport de DEA, Université de Besançon 1987.

  30. C. Guerra and R. Melhem, Synthesizing non-uniform systolic designs.Proc. of the 1986 International Conference on Parallel Processing, pages 765–772, August 1986.

  31. M.C. Chen. Synthesizing VLSI architectures: Dynamic programming solver.Proc. of the 1986 International Conference on Parallel Processing, pages 776–784, August 1986.

  32. P. Gachet, P. Quinton, C. Mauras and Y. Saouter. Alpha du Centaur: A prototype environment for the design of parallel regular algorithms. IRISA Research Report number 439, November 1988.

  33. V. Van Dongen. Presage, a tool for the design of low-cost systolic arrays.ISCAS 88, pages 2765–2768, 1988.

    Google Scholar 

  34. A. Schrijver.Theory of linear and integer programming. Wiley-Interscience series in Discrete Mathematics, John Wiley and Sons, 1986.

  35. J. Dieudonné.Algèbre linéaire et géométrie élémentaire, Hermann, Paris, 1964.

    MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. IRISA, Campus de Beaulieu, 35042, Rennes-Cedex, France

    Patrice Quinton

  2. PRLB, Av. van Becelaere, No. 2, Box 8, 1170, Brussels, Belgium

    Vincent van Dongen

Authors
  1. Patrice Quinton
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Vincent van Dongen
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

This work was partially funded by the French Coordinated Research ProgramC 3 and by a Grant from the SOREP company

Rights and permissions

Reprints and permissions

About this article

Cite this article

Quinton, P., van Dongen, V. The mapping of linear recurrence equations on regular arrays. J VLSI Sign Process Syst Sign Image Video Technol 1, 95–113 (1989). https://doi.org/10.1007/BF02477176

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

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

Keywords

Search

Navigation