Massimo Maresca and Hungwen Li*
DIST-University of Genoa
*HaL Computer Systems
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 nonneighbor nodes. The best known proposals, in the area of RPAs, are the Mesh with Reconfigurable Bus , the Processor Arrays with Reconfigurable Bus Systems , the Gated Connection Network  and the Polymorphic Processor Array . In this paper we show that only one of these architectures, namely the Polymorphic Processor Array, supports virtual parallelism. (Virtual parallelism is referred to as a situation in which the number of parallel activities in which a task can be partitioned is larger than the number of available processors, and some of the activities are executed in sequence with linear performance degradation.) The support of virtual parallelism is important because it allows the complexity measurements of the parallel algorithms 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 to establish an arbitrary shape two-dimensional bus do not support virtual parallelism, and that 2) the Polymorphic Processor Array, with its connection power limited to one-dimensional buses, supports virtual parallelism.
Keywords: computer architecture, parallel processing, reconfigurability, virtual parallelism, scolability
Received December 12, 1992; revised April 15, 1993.
Communicated by Chuan-lin Wu.