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", Proc. of the IASTED International Conference on Parallel and Distributed Computing and Systems, PDCS'98, Las Vegas, Nevada, USA, 28-31 Oct., 1998, Y. Pan, S. Akl and K. Li (Eds.), pp. 396-401, Oct. 1998.
We propose a technique which essentially constructs a set of program structures, 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 processes induce a specific processor topology dependent on the partitioning strategy used. The processing requirements based on the topology imply a specific program structure. Details of such resulting program structures are discussed. 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: 176KB)