Uniform wiring structure embeddable in euclidean space
Hirotomo Aso · Electronics and Communications in Japan (Part III Fundamental Electronic Science) · 1993
Abstract In a systolic array, uniform wiring is required for simplification of processor elements, synchronous and parallel data transmission through communications links, etc. As a method for designing a systolic array for a loop program given as a problem specification, there exists a method which is based on extracting wiring information from dependence relations among elemental computations in the loop program. In this paper, the uniformity of wiring structure is logically defined and a sufficient condition is given under with a given uniform wiring structure is embedded in a Euclidean space. In addition, its implementation method is given in the form of an embedding map. Examples satisfying this condition and a counterexample related to this condition are given. Furthermore, it is shown that there are cases that are embeddable in a Euclidean space even if they do not satisfy the given sufficient condition, which implies a natural expansion of the definition of embedding.