Polymorphic Processor Arrays

A Polymorphic Processor Array (PPA) is a two-dimensional mesh- connected array of processors, in which each processor is equipped with a switch able to interconnect its four NEWS ports. PPA is an abstract architecture based upon the experience acquired in the design and in the implementation of a VLSI chip, namely the Polymorphic Torus (PT) chip, and, as a consequence, it only includes capabilities that have been proved to be supported by cost-effective hardware structures. The main claims of PPA are that 1) it models a realistic class of parallel computers, 2) it supports the definition of high level programming models, 3) it supports virtual parallelism and 4) it supports low complexity algorithms in a number of application fields. In this paper we present both the PPA computation model and the PPA programming model; we show that the PPA computation model is realistic by relating it to the design of the PT chip and show that the PPA programming model is scalable by demonstrating that any algorithm having 0(p) complexity on a virtual PPA of size (square root m) X (square root m), has 0(kp) complexity on a PPA of size (square root n) X (square root n), with m=kn and k integer. We finally show some application algorithms in the area of numerical analysis and graph processing.

ICSI Technical Report TR-91-033

Technical Report