Skip to main content
SpringerLink
Log in

Control generation in the design of processor arrays

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

Abstract

The problem of mapping algorithms onto regular arrays has received great attention in the past. Results are available on the mapping of regular algorithms onto systolic or wavefront arrays. On the other hand, many algorithms that can be implemented on parallel architectures are not completely regular but are composed of a set of regular subalgorithms. Recently, a class of configurable processor arrays has been proposed that allows the efficient implementation of piecewise regular algorithms. In contrary to pure systolic of wavefront arrays they are distinguished by a dynamic configuration structure. The known trajectories, however, cannot be applied to the design of configurable processor arrays because the functions of the procesing elements and the interconnection structure are time- and space-dependent. In this paper, a systematic procedure is introduced that allows the efficient design of configurable processor arrays including the specification of the processing elements and the generation of control signals. Control signals are propagated through the processor array. The proposed design trajectory can be used for the design of regular arrays or configurable arrays.

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

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. H. Kung, “Let's design algorithms for VLSI system,” inProc. Caltech Conf. on VLSI, 1979, pp. 65–90.

  2. S.Y. Kung,VLSI Processor Arrays. Englewood Cliffs, NJ: Prentice Hall, 1987.

    Google Scholar 

  3. H. Kung and C. Leiserson, “Systolic arrays for VLSI,” inSIAM Sparse Matrix Proceedings, Philadelphia, 1978, pp. 245–282.

  4. U. Schwiegelshohn and L. Thiele, “One- and two-dimensional arrays for least squares problems,” inIEEE Conf. on Acoust. Speech Signal Processing, Dallas, 1987, pp. 791–794.

  5. U. Schweigelshohn and L. Thiele, “A systolic array for cyclicby-rows Jacobi algorithms,”J. on Parallel and Distributed Computing, vol. 4, 1987, pp. 334–340.

    Article  Google Scholar 

  6. U. Schwiegelshohn and L. Thiele, “Linear processor arrays for matrix computations,”J. on Parallel and Distributed Computing, vol. 7, 1989, pp. 28–39.

    Article  Google Scholar 

  7. L. Thiele, “Computational arrays for Jacobi algorithms,” inSVD and Signal Processing, North Holland Pub., 1988, pp. 369–383.

  8. L. Guibas, H. Kung, and C. Thompson, “Direct VLSI implementation of combinatorial algorithms,” inProc. Conf. on VLSI: Architecture, Design and Fabrication, 1979, pp. 509–525.

  9. M. Huber, “A systolic processor chip dedicated to the shortest path problem,” inProceedings of COMPEURO 87, Hamburg, 1987, pp. 500–501.

  10. U. Schwiegelshohn and L. Thiele, “A systolic array for the assignment problem,”IEEE Trans. Computers, 1988, pp. 1422–1425.

  11. S.K. Rao and T. Kailath, “Systematic design of special purpose processor arrays,”Proceedings of the IEEE, 1987.

  12. P. Quinton, “Automatic synthesis of systolic arrays from uniform recurrent equations,” inThe IEEE/ACM 11th Annual Int'l Symp. on Computer Architecture, Ann Arbor, MI, 1984, pp. 208–214.

  13. S.K. Rao, Regular iterative algorithms and their implementations on processor arrays. PhD thesis, Stanford University, 1985.

  14. W.L. Miranker and A. Winkler, “Space-time representation of computational structures,”Computing, 1984, pp. 93–114.

  15. D.I. Moldovan, “On the design of algorthms for VLSI systolic arrays,”Proceedings of the IEEE, 1983, pp. 113–120.

  16. J. Annevelink and P. Dewilde, “HIFI: A functional design system for VLSI processing arrays,” inProc. Int'l Conf. on Systolic Arrays, San Diego, 1988, pp. 433–452.

  17. L. Thiele, “On the hierarchical design of VLSI processor arrays,” inIEEE Symp. on Circuits and Systems, Helsinki, 1988, pp. 2517–2520.

  18. A. Benani and Y. Robert, “Spacetime-minimal systolic arrays for Gaussian elimination and the Algebraic Path Problem,” Report from the Ecole Normale Superieure de Lyon, vol. 9, 1990.

  19. J. Hwang and S. Kunk, “Parallel Algorithms/Architectures for Neural Networks,”Journal of VLSI Signal Processing, vol. 1, 1989, pp. 221–251.

    Article  MATH  Google Scholar 

  20. M. Chen and K. Yao, “On realization and implementation of Kalman filtering systolic arrays,” inProceedings of John Hopkins Workshop, 1987.

  21. D.I. Moldovan and R.A.B. Fortes, “Partitioning and mapping of algorithms into fixed size systolic arrays,”IEEE Trans. Computers, Vol. C-35, 1986, pp. 1–12.

    Article  Google Scholar 

  22. H. Nelis, E.F. Deprettere, and J. Bu, “Automatic design and partitioning of algorithms for VLSI systolic/wavefront arrays,” inProc. SPIE Conference, San Diego, 1987.

  23. Y.Wong and J.M. Delosme, “Broadcase removal in systolic algorithms,” inProc. of Int'l Conf. on Systolic Arrays, San Diego, 1988, pp. 403–412.

  24. V. Roychowdhury, L. Thiele, S.K. Rao, and T. Kailath, “On the localization of algorithms for VLSI processor arrays,” inVLSI Signal Processing III, New York: IEEE Press, 1989, pp. 459–470.

    Google Scholar 

  25. J. Bu, L. Thiele, and E. Deprettere, “Systolic array implementation of nested loop programs,” inApplication Specific Array Processors, Princeton, NJ: IEEE Computer Society Press, 1990, pp. 31–43.

    Chapter  Google Scholar 

  26. L. Thiele, “On the design of piecewise regular processor arrays,” inProc. IEEE Symp. on Circuits and Systems, Portland, 1989, pp. 2239–2242.

  27. D. Smitley and I. Lee, “Synthesizing Minimum Total Expansion Topologies for Reconfigurable Interconnection Networks,”Journal of Parallel an Distributed Computing, vol. 7, 1989, pp. 178–199.

    Article  Google Scholar 

  28. I. Schierson and S. Ilgen, “A Reconfigurable Fully Parallel Associative Processor,”Journal of Parallel and Distributed Computing, vol. 6, 1989, pp. 69–89.

    Article  Google Scholar 

  29. C.H. Chu, “A Model for an Intelligent Operating System for Executing Image Understanding Tasks on a Reconfigurable Architecture,”Journal of Parallel and Distributed Computing, vol. 6, 89, pp. 598–622.

  30. M. Chean and J. Fortes, “A Taxonomy of Reconfiguration Techniques for Fault-Tolerant Processor Arrays,”Computer, vol. 23, 1990, pp. 55–69.

    Article  Google Scholar 

  31. P. Frison, D. Lavenier, H. Leverge, and P. Quinton, “MICS-MACS: A VLSI Programmable Systolic Architecture,” inProc. Int. Conf. Systolic Arrays, 1989, pp. 146–155.

  32. O. Menzilcioglu, H.T. Kung, and S.W. Song, “A Highly Configurable Architecture for Systolic Arrays of Powerful Processors,” inProc. Int. Conf. Systolic Arrays, 1989, pp. 165–165.

  33. L. Snyder, “Introduction to the Configurable, Highly Parallel Computer,”Computer, 1982, pp. 47–56.

  34. M. Kunde, H.W. Lang, M. Schimmler, and H. Schroeder, “The Instruction Systolic Array and its relation to other models of Parallel Computers,” inProceedings Parallel Computing, North-Holland Amsterdam, 1985.

    Google Scholar 

  35. S. Rajopadhye and R. Fujimoto, “Systolic array synthesis by static analysis of program dependencies,” inProc. of Parallel Architectures and Languages Europe J. Bakker, A. Nijman, and P. Treleaven, eds.), Springer Verlag, 1987, pp. 295–310.

  36. K. Chandy and J. Misra,Parallel Program Design, Reading, MA: Addison-Wesley, 1988.

    MATH  Google Scholar 

  37. S.K. Rao and T. Kailath, “Regular iterative algorithms and their implementations on processor arrays,”Proceedings of the IEEE, vol. 6, 1988, pp. 259–282.

    Article  Google Scholar 

  38. M. Huber, J. Teich, and L. Thiele, “Design of configurable processor arrays (invited paper),“ inProc. IEEE Int. Symp. Circuits and Systems, New Orleans, 1990, pp. 970–973.

  39. G. Nemhauser and L. Wolsey, Interger and combinatorial optimization, New York: John Wiley, 1988.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Institute of Microelectronics, University of Saarland, D-6600, Saarbrücken, West Germany

    Jürgen Teich & Lothar Thiele

Authors
  1. Jürgen Teich
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Lothar Thiele
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Teich, J., Thiele, L. Control generation in the design of processor arrays. J VLSI Sign Process Syst Sign Image Video Technol 3, 77–92 (1991). https://doi.org/10.1007/BF00927836

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

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

Keywords

Search

Navigation