Virtual Parallelism Support in Reconfigurable Processor Arrays

TitleVirtual Parallelism Support in Reconfigurable Processor Arrays
Publication TypeTechnical Report
Year of Publication1991
AuthorsMaresca, M., & Li H.
Other Numbers671

Reconfigurable Processor Arrays (RPAs) are a special class of mesh connected computers in which each node is equipped with a switching system able to internally interconnect its NEWS ports and to establish paths between non-neighborhood nodes. The best known proposals in the area of RPAs are the Mesh with Reconfigurable Bus [Miller, et al., 1988], the Processor Arrays with Reconfigurable Bus Systems [Wang and Chen, 1990], the Gated Connection Network [Shu and Nash] and Polymorphic Processor Array [Li and Maresca, 1989]. In this paper we show that only one of these architectures, namely the Polymorphic Processor Array, supports virtual parallelism. The support of virtual parallelism is important because it allows the complexity measurements of the parallel algorithms to be scaled to real implementations, where the size of the processor array can be smaller than the problem size. We demonstrate that: 1) the RPAs that allow the establishment of an arbitrary shape two-dimensional bus do not support virtual parallelism and 2) the Polymorphic Processor Array, with its connection power to one-dimensional buses, supports virtual parallelism.

Bibliographic Notes

ICSI Technical Report TR-91-041

Abbreviated Authors

M. Maresca and Hungwen Li

ICSI Publication Type

Technical Report