Efficient wiring of reconfigurable parallel processors
David S. Greenberg · 1993
Chips (or chip sets) which include one or more CPUS, some local memory, and rudimentary communications and routing hardware are becoming common (eg.transputers, SRCS HNet, thenodes ofmost MIMD machines).These chips provide the possibihty of tailoring the topology of a machine to a particular problem.Rather than asking thestandardquestion of how to best coerce one's algorithm to fit an existing topology, one can ask what would be the best topology for the algorithm.This paper defines the efficiency of a topology for an algorithm and gives upper and lower bounds on the best efficiency achievable (as a function of the number of different communication patterns used by the algorithm).This approach is then applied to algorithms which use stencil patterned communications.The result is the definition of topologies which are significantly more efficient than the naive topology.