Return to d'Auriol's Publication Page
Brian J. d'Auriol and Virendrakumar C. Bhavsar, ``Generic Program Structures Induced by Partitions of a Systolic Computation Graph'', Technical Report 97/04, Department of Computer Science, The University of Manitoba, Winnipeg, Manitoba, Canada, R3T 2N2, March 1997.
We propose a technique which essentially constructs a set of concurrent program archetype definitions, each representing a valid parallel implementation of a sequentially specified program. Our approach is based on partitioning a systolic computation graph and the subsequent mappings of the computations involved to processors in a multicomputer environment. We show that the partitioning and mapping process induces a specific processor topology dependent on the partitioning strategy used. The processing requirements based on the topology imply a specific program structure. The details of resulting program structures are illustrated. The formalism contained in this paper is useful for the construction of automated tools to support the generation of parallel program codes.
Full Paper (pdf: 232KB)