Mapping semigroup array operations onto computer system with toroidalstructure

A distributed computer system (CS) is a set of processor-memory couples to be called processorelements (processors) and to be connected by a network where each line connects two processors.The network of interprocessor connections is described by a graph. In modern distributedsupercomputer systems a three-dimensional torus is usually used as the interconnection graph.A semigroup operation is a binary associative one. The examples of this operation are: asummation, a product, a conjunction, a disjunction, an exclusive OR, and also a computation ofmaximum or minimum. This paper describes a parallel algorithm for implementation of these operationson data arrays distributed among processors with a matrix ("mesh") network where everyprocessor must have the operation result. The algorithm is reduced to a sequence of cyclic shiftsin a linear processor network with making operation on each shift. The shifts are implemented forevery mesh dimension. The algorithm is easily adapted to a toroidal processor network.In the paper an algorithm for mapping semigroup array operations onto distributed CS withtoroidal structure is proposed. The algorithm is based on usage of a "butterfly" scheme and mappingthis scheme onto hypercubic CS structure with subsequent XOR-mapping of the hypercubeonto torus. It is shown that the XOR hypercube-onto- torus mapping does not produce congestionsin message passing. The algorithm implementation time is evaluated. It is shown that:1. Besides the hypercube edge dilations on torus, the proposed algorithm has the time of thesemigroup operation implementation on torus less than the cyclical-data-shift algorithm has.2. When the number of the CS processors (and the number of the data array elements) increases,the time gain of the proposed algorithm increases also.

Keywords

Authors

References