Polymorphic Processor Arrays

TitlePolymorphic Processor Arrays
Publication TypeTechnical Report
Year of Publication1991
AuthorsMaresca, M.
Other Numbers663

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.

Bibliographic Notes

ICSI Technical Report TR-91-033

Abbreviated Authors

M. Maresca

ICSI Publication Type

Technical Report