Title: The reconfigurable ring of processors: fine-grain tree-structured computations
Abstract: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 w...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 N 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.Read More
Publication Year: 1997
Publication Date: 1997-01-01
Language: en
Type: article
Indexed In: ['crossref']
Access and Citation
Cited By Count: 4
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot