Abstract
In this paper, we use a variant of the geometric method to derive efficient modular linear systolic algorithms for the transitive closure and shortest path problems. Furthermore, we show that partially-pipelined modular linear systolic algorithms with an output operation, for matrix multiplication, can be as efficient as fully-pipelined ones, and in some cases needs less cells.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
A. V. Aho, J. Hopchoft and J. D. Ullman: The design and analysis of computer algorithms Addison-Wesley (1974).
A. Benaini and M. Tchuente: Matrix product on linear systolic arrays, in Parallel and Distributed Algorithms, M. Cosnard and al. eds, North Holland, (1989).
A. L. Fischer and H. T. Kung: Synchronizing large VLSI processor arrays. Proc. Tenth Annual IEEE/ACM Symposium on Computer Architecture, June 1983, PP. 54–58
L. J. Guibas, H. T. Kung and C. D. Thompson: Direct VLSI implementation of combinatorial algorithms; Proc. Conference on very large Scale Integration: Architecture, Design, Fabrication; California Institute of Technology (January 1979) pp. 509–525.
H. T. Kung: Why systolic architecture. IEEE Computer, 15(1) January, 1980, PP. 37–46
F. T. Leighton and C.E. Leiserson: Wafer-Scale integration of systolic arrays. Proc. Twenty-third Symp. Foundations of Computer Science, November 1982, PP. 297–311.
C. H. Huang and C. Langauer: An incremental mechanical development of systolic solutions to the algebraic path problem. Acta Informatica 27, (1989), 97–124.
S. Y. Kung, P. S. Lewis and S. C. Lo: On optimal mapping algorithms to systolic arrays with application to the transitive closure problem, in Proc. 1986 IEEE Int. Symp. Circuits Syst., PP. 1316–1322.
S. Y. Kung and S. C. Lo: A spiral systolic architecture algorithm for transitive closure problems, Proc. IEEE Int. Conf. Comput. Design, 1985.
S. Y. Kung, S. C. Lo and P. S. Lewis: Optimal systolic design for transitive closure and the shortest path problems; IEEE Trans. Comput. C-36, No. 5, 1987, PP. 603–614.
P. Lee and Z. Kedem: Synthesizing linear array algorithms from nested for loop algorithms. IEEE Trans. Comput., C-37 (1988), 1578–1598.
P. S. Lewis and S. Y. Kung: Dependence graph based design of systolic arrays for the algebraic path problem. Proc. 12 th ann. Asilomar Conf. Signals Syst., Com-put., 1986.
F. C. Lin and Wu: Systolic arrays for transitive closure algorithms in Proc. Int. Symp.VLSI Syst. Designs, Taipei May 1985.
J. F. Myoupo: A linear systolic array for transitive closure problems, Proc. Int. Conf. Parallel Process. (ICPP), 1990. Vol. I, PP. 617–618.
J. F. Myoupo: A way of deriving linear systolic arrays from a mathematical algorithm description: Case of the Warshall-Floyd Algorithm.Proc. Int. Conf. Parallel Process. (ICPP), 1991. Vol. I, PP. 575–579.
J. F. Myoupo and A.C. Fabret: Designing Modular Linear Systolic Arrays Using Dependence Graph Regular Partitions. Rapport Interne, L.R.I., Université Paris-Sud, 1992.
V. K. Prasanna Kumar and Y. C. Tsai: Designing linear systolic arrays. J. parallel distrib. Comput. 7 (1989), 441–463.
S. K. Prasanna Kumar and Y. C. Tsai: On mapping algorithms to linear and fault-tolerant systolic srrays, IEEE Trans. Comput., vol. 38, No. 3 PP. 470–478, 1989.
I. V. Ramakrishnan, P. J. Varman: Dynamic programming and transitive closure on linear pipelines; Proc. Int. Conf. on Parallel Processing, (ICPP) 1984.
I. V. Ramakrishnan and P. J. Varman: An Optimal Family of Matrix multiplication algorithms on linear arrays; ICPP (1985), IEEE press, pp.376–383.
I. V. Ramakrishnan and P. J. Varman: Synthesis of an optimal family of matrix multiplication algorithms on linear arrays; IEEE Trans. Computers, C-35(11), 1986.
Y. Robert and D. Trystram: An orthogonal systolic array for the algebraic path problem.Computing, 39,PP. 187–199, 1987.
G. Rote: A systolic array algorithm for the algebraic path problem; Computing; Vol. 34 PP. 192–219, 1985.
U. Schwiegelshohn and L. Thiele: Linear systolic arrays for matrix computation. J. parallel distrib. Comput. 7 (1989), 28–39.
T. Risset: Linear systolic arrays for matrix multiplication: Comparison of existing synthesis methods and new results; Tech. Repport, No. 91–12 LIP, Ecole Normale Supérieure de Lyon, 1991.
J. D. Ullman Computational aspects of VLSI, Computer Science Press (1984).
J. L. A. Van de Snepscheut: A derivation of a distributed implementation of Warshall's algorithm. Science of Computer Programming 7 (1986), 55–60.
S. W. Warman, Jr.: A modification of Warshall's algorithm for the transitive closure of binary relations; CACM. Vol. 18 No. 4 PP. 218–220, 1975.
S. Warshall: A theorem on boolean matrices; JACM, Vol. 9 No. 1 PP. 11–12, 1972.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1992 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Myoupo, JF., Fabret, AC. (1992). Designing modular linear systolic arrays using dependence graph regular partitions. In: Bougé, L., Cosnard, M., Robert, Y., Trystram, D. (eds) Parallel Processing: CONPAR 92—VAPP V. VAPP CONPAR 1992 1992. Lecture Notes in Computer Science, vol 634. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-55895-0_421
Download citation
DOI: https://doi.org/10.1007/3-540-55895-0_421
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-55895-8
Online ISBN: 978-3-540-47306-0
eBook Packages: Springer Book Archive