EMBEDDING MESHES AND TORUS NETWORKS ONTO DEGREE-4 CHORDAL RINGS

Degree-four chordal rings demonstrate many attractive properties, such as node symmetry, constant degree, O(root N) diameter and the ability to interconnect an arbitrary number of nodes. The authors study the a bilities of degree-four chordal rings to execute parallel programs usi ng graph-embedding techniques. Since many algorithms have been designe d for meshes and TORUS networks, the issue of embedding meshes and TOR US networks onto degree-four chordal rings is addressed. Mapping funct ions, simple and snake-like, of embedding meshes and TORUS networks on to the degree-four chordal rings is discussed in detail. It is shown t hat the ILLIAC network is a special class of the degree-four chordal r ing. Topological properties are investigated, such as diameter and ave rage distance of ILLIAC networks and optimal degree-four chordal rings , another special class of degree-four chordal rings. Comparisons of I LLIAC networks and optimal chordal rings in these embedding issues are given.