Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 659.68078
Autor: Erdös, Paul; Koren, I.; Moran, S.; Silberman, G.M.; Zaks, S.
Title: Minimum-diameter cyclic arrangements in mapping data-flow graphs onto VLSI arrays. (In English)
Source: Math. Syst. Theory 21, No.2, 85-98 (1988).
Review: The problem of routing data from processors in a given (source) sequence to another (target) sequence is investigated. This problem represents a partial task arising in the study of complexity of mapping data-flow graphs (representing the computational algorithms) onto square and hexagonal arrays of processors. Under certain conditions this problem of routing data is equivalent to the one of finding a minimum-diameter cyclic arrangement. The analysis of worst case complexity of the later problem is made and upper and lower bounds on the number of intermediate rows of processors (between the source and target rows) are derived.
Reviewer: J.Hromkovic
Classif.: * 68Q80 Cellular and array automata
68R99 Discrete mathematics in relation to computer science
68Q25 Analysis of algorithms and problem complexity
Keywords: data routing; two-dimensional systolic arrays; linear programs; VLSI
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag