The reconfigurable ring of processors: Fine-grain tree-structured computations
We study fine-grain computation on the Reconfigurable Ring of Processors (RRP), a parallel architecture whose processing elements (PEs) are interconnected via a multiline reconfigurable bus, each of whose lines has one-packet width and can be configured, independently of other lines, to establish an arbitrary PE-to-PE connection. We present a ''cooperative'' message-passing protocol that will, in the presence of suitable implementation technology, endow an RRP with message latency that is logarithmic in the number of PEs a message passes over in transit. Our study focuses on the computational consequences of such latency in such an architecture. Our main results prove that: 1) an N-PE RRP can execute a sweep up or down an N-leaf complete binary tree in time proportional to log iv log log N; 2) a broad range of N-PE architectures, including N-PE RRPs, require time proportional to log N log log N to perform such a sweep.
rings of processors communication protocols dynamically reconfigurable parallel architectures fine-grain parallel computing tree-sweep algorithms