G. Veselovsky (Thailand)
Parallel computing, interconnection network, torus,permutation
Permutations belong to communications patterns demanded frequently in massively-parallel computers especially of the SIMD type. A permutation is said “admissible” to a given interconnection network if it does not cause blockings in that network under a chosen routing algorithm. Determining the admissibility of a given permutation to various static connecting topologies is a fundamental problem. Based on congruence notion from number theory, this paper presents a simple method which solves admissibility problem for regular permutations to uniaxial 2D and 3D tori under deterministic dimension-order routing commonly used in practice. Here “uniaxial” means that in every routing step all data items participating in a permutation can move along the same axis only. It is assumed that all nodes of a system work in a synchronous fashion what is also characteristic to SIMDs. The efficiency of the method is illustrated by the examples with checking admissibility of some frequently used in parallel programming permutations which belong either to Omega or BPC (bit permute-complement) classes.
Important Links:
Go Back
