THE RECONFIGURABLE RING OF PROCESSORS - FINE-GRAIN TREE-STRUCTURED COMPUTATIONS

We study fine-grain computation on the Reconfigurable Ring of Processo rs (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 li nes, to establish an arbitrary PE-to-PE connection. We present a ''coo perative'' message-passing protocol that will, in the presence of suit able 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 i n such an architecture. Our main results prove that: 1) an N-PE RRP ca n execute a sweep up or down an N-leaf complete binary tree in time pr oportional 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.