Mesh-Connected Processor Arrays for the Transitive Closure Problem

摘要

The main purpose in this paper is to lay a theoretical foundation for the design of mesh connected processor arrays for the transitive closure program. Using a simple path algebraic formulation of the problem and observing its similarity to certain well known smoothing problems that occur during digital signal processing, we show how to draw upon existing techniques from the signal processing literature to derive regular iterative algorithms for determining the transitive closure of the graph. The regular iterative algorithms that are derived using this considerations, are then analyzed and synthesized on mesh-connected processor arrays. Among the vast number of mesh connected processor arrays that can be designed using this unified approach, the systolic arrays reported in the literature for this problem are shown to be special cases. Keywords: Mesh connected processor arrays; Transitive closure problems; Systolic architectures; Matrix multiplication; Array; and Iteration algorithm.