Treffer: Generic Program Structures Induced by Partitions of a Systolic Computation Graph

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.