ALGORITHM TRANSFORMATION FOR CUBE-TYPE NETWORKS

This paper presents a method for mechanically transforming a parallel algorithm on an original network so that the algorithm can work on a t arget network. It is assumed that the networks are of cube-type such a s the shuffle-exchange network, omega network, and hypercube. Were tho se networks isomorphic to each other, the algorithm transformation is an easy task. The proposed transformation method is based on a novel g raph embedding scheme <phi:delta, kappa, pi, psi>. In addition to the dilating operation delta of the usual embedding scheme <phi:delta>, th e novel scheme uses three primitive graph-transformation operations; i c (= delta(-1)) for contracting a path into a node, pi for pipelining a graph, and psi (= n(-1)) for folding a pipelined graph. By applying the primitive operations, the cube-type networks can be transformed so as to be isomorphic to each other. Relationships between the networks are represented by the composition of applied operations. With the is omorphic mapping phi, an algorithm in a node of the original network c an be simulated in the corresponding node(s) of the target network. Th us the algorithm transformation is reduced to routine work.