Algorithm Transformation for Cube-Type Networks (Special Issue on Architectures, Algorithms and Networks for Massively Parallel Computing)

概要

論文の詳細を見る
This paper presents a method for mechanically transforming a parallel algorithm on an original network so that the algorithm can work on a target network. It is assumed that the networks are of cube-type such as the shuffle-exchange network, omega network, and hypercube. Were those networks isomorphic to each other, the algorithm transformation is an easy task. The proposed transformation method is based on a novel graph-embedding scheme ltφ:δ, K, π, ψgt. In addition to the dilating operation δ of the usual embedding scheme ltφ:δgt, the novel scheme uses three primitive graph-transformation operations; K (=δ^(-1)) for contracting a path into a node, π for pipelining a graph, and ψ(=π^(-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 isomorphic mapping φ, an algorithm in a node of the original network can be simulated in the corresponding node(s) of the target network. Thus the algorithm transformation is reduced to routine work.
社団法人電子情報通信学会の論文
1996-08-25