Topological transformations as a tool in the design of systolic networks. (English) Zbl 0584.68068
A systolic network, or more generally a computational network (CN), is a formal model of an arbitrary system of parallel processors. It is described by an ordered (generally infinite) digraph with several mappings assigned to its nodes and edges. Some of them express a computational process performed the others can be interpreted as synchronization functions.
One of the main notions studied in the paper is the concept of equivalence of two CN’s which is defined on the basis of an isomorphism of their space-time diagrams (unrollings). The main tool, a topological transformation of one CN into an equivalent one is used for proving several theorems including systolic conversion theorem. Another important notion describing situations when two CN’s performs essentially identical computations is the concept of simulation of one CN on another one. This, as well as the whole article, is illustrated by a number of examples enabling to understand the rather complicated formalism.
One of the main notions studied in the paper is the concept of equivalence of two CN’s which is defined on the basis of an isomorphism of their space-time diagrams (unrollings). The main tool, a topological transformation of one CN into an equivalent one is used for proving several theorems including systolic conversion theorem. Another important notion describing situations when two CN’s performs essentially identical computations is the concept of simulation of one CN on another one. This, as well as the whole article, is illustrated by a number of examples enabling to understand the rather complicated formalism.
Reviewer: Radim Jiroušek (Praha)
MSC:
| 68Q05 | Models of computation (Turing machines, etc.) (MSC2010) |
| 05C10 | Planar graphs; geometric and topological aspects of graph theory |
| 94C15 | Applications of graph theory to circuits and networks |
| 68Q80 | Cellular automata (computational aspects) |
Keywords:
parallel processing; computational network; equivalence; isomorphism; space-time diagrams; unrollings; simulationReferences:
| [1] | Bucher, W.; Culik, K., On real time and linear time cellular automata, RAIRO Inform. Théor., 18, 307-325 (1984) · Zbl 0547.68050 |
| [2] | Cappello, P. R.; Steiglitz, K., Unifying VLSI design with geometric transformations, (Proc. IEEE 1983 Internat. Conf. on Parallel Processing (1983)), 448-457 |
| [3] | Choffrut, C.; Culik, K., Folding of the plane and the design of systolic arrays, Inform. Process. Letters, 17, 149-153 (1983) · Zbl 0531.68009 |
| [4] | Choffrut, C.; Culik, K., On real-time cellular automata and trellis automata, Acta Inform., 21, 393-407 (1984) · Zbl 0534.68039 |
| [5] | Cole Stephen, N., Real-time computation by \(n\)-dimensional iterative arrays of finite-state machine, IEEE Trans. Comput., C-18, 349-365 (1969) · Zbl 0172.20804 |
| [6] | Culik, K.; Gruska, J.; Salomaa, A., Systolic trellis automata; Part II, Internat. J. Comput. Math., 16, 3-22 (1984) · Zbl 0571.68042 |
| [7] | Culik, K.; Pachl, J., Folding and unrolling systolic arrays, (ACM SIGACT-SIGOPS Symp. on Principles of Distributed Computing. ACM SIGACT-SIGOPS Symp. on Principles of Distributed Computing, Ottawa (1982)), 254-261 |
| [8] | Culik, K.; Jürgensen, H., Programmable finite automata for VLSI, Internat. J. Comput. Math., 14, 259-275 (1983) · Zbl 0528.68035 |
| [9] | Culik, K.; Salomaa, A.; Wood, D., Systolic tree acceptors, RAIRO Inform. Theoret., 18, 53-69 (1984) · Zbl 0571.68043 |
| [10] | Culik, K.; Yu, S., Iterative tree automata, Theoret. Comput. Sci., 32, 227-247 (1984) · Zbl 0544.68055 |
| [11] | Dyer, C. R., One-way bounded cellular automata, Inform. and Control, 44, 261-281 (1980) · Zbl 0442.68082 |
| [12] | Fischer, P. C., Generation of primes by a one-dimensional real-time iterative array, J. ACM, 12, 388-394 (1965) · Zbl 0173.19105 |
| [13] | O.H. Ibarra, S.M. Kim and S. Moran, Sequential machine characterizations of trellis and cellular automata and applications, Unpublished manuscript.; O.H. Ibarra, S.M. Kim and S. Moran, Sequential machine characterizations of trellis and cellular automata and applications, Unpublished manuscript. · Zbl 0574.68044 |
| [14] | O.H. Ibarra and S.M. Kim, A characterization of systolic binary tree automata and applications, Unpublished manuscript.; O.H. Ibarra and S.M. Kim, A characterization of systolic binary tree automata and applications, Unpublished manuscript. · Zbl 0521.68048 |
| [15] | Knuth, D. E., (The Art of Computer Programming, Vol. 3 (1973), Addison-Wesley: Addison-Wesley Reading, MA) · Zbl 0302.68010 |
| [16] | Kosaraju, S. R., Speed of recognition of context-free languages by array automata, SIAM J. Comput., 4, 331-340 (1975) · Zbl 0311.68052 |
| [17] | Kung, H. T., Why systolic architectures?, Comput. Magazine, 37-46 (January 1982) |
| [18] | Kung, H. T.; Lin, W. T., An algebra for VLSI algorithm, (Proc. Conf. on Elliptic Problems (1983)) · Zbl 0592.94024 |
| [19] | Kung, H. T.; Leiserson, C. E., Systolic arrays (for VLSI), (Proc. Sparse Matrix Conf. (1987)) · Zbl 0404.68037 |
| [20] | Leighton, F. T., Complexity Issues in VLSI (1983), MIT Press: MIT Press Cambridge, MA |
| [21] | Leiserson, C. E., Area-Efficient VLSI Computations (1982), MIT Press: MIT Press Cambridge, MA |
| [22] | Leiserson, C. E.; Saxe, J. B., Optimizing synchronous systems, (Proc. 22nd Ann. FOCA Symp. (1981)), 23-36 |
| [23] | Ostlund, N. S.; Whiteside, R. A., A machine architecture for molecular dynamics: The systolic loop, (Conf. on Macromolecular Structure and Specificity: Computer Assisted Modeling (1983), New York Academy of Sciences) |
| [24] | Mead, C. A.; Conway, L., Introduction to VLSI (1980), Addison-Wesley: Addison-Wesley Reading, MA |
| [25] | Seiferas, J. I., Iterative array with direct central control, Acta Inform., 8, 177-192 (1977) · Zbl 0337.94035 |
| [26] | Smith, A. R., Real-time language recognition by one-dimensional cellular automata, J. ACM, 6, 233-253 (1972) · Zbl 0268.68044 |
| [27] | Stone, H. S., Parallel processing with perfect shuffle, IEEE Trans. Comput., C-20, 153-161 (1971) · Zbl 0214.42703 |
| [28] | Ullman, J. D., Computational Aspects of VLSI (1984), Computer Science Press: Computer Science Press Rockville, MD · Zbl 0539.68021 |
| [29] | Umeo, H.; Morita, K.; Sugato, K., Deterministic one-way simulation of two-way real-time cellular automata, Inform. Process. Letters, 14, 158-161 (1982) · Zbl 0488.68041 |
| [30] | Weiser, U.; Davis, A., A wavefront notation tool for VLSI array design, (Kung, H. T.; Sproull, R. F.; Steele, G. L., VLSI Systems and Computing (1981), Carnegie-Mellon University, Computer Science Press), 226-234 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
