Embedding meshes and TORUS networks onto degree-four chordal rings

J. F. Fang, J. Y. Hsiao, C. Y. Tang

Research output: Contribution to journalArticle

7 Citations (Scopus)

Abstract

Degree-four chordal rings demonstrate many attractive properties, such as node symmetry, constant degree, O(√N) diameter and the ability to interconnect an arbitrary number of nodes. The authors study the abilities of degree-four chordal rings to execute parallel programs using graph-embedding techniques. Since many algorithms have been designed for meshes and TORUS networks, the issue of embedding meshes and TORUS networks onto degree-four chordal rings is addressed. Mapping functions, simple and snake-like, of embedding meshes and TORUS networks onto the degree-four chordal rings is discussed in detail. It is shown that the ILLIAC network is a special class of the degree-four chordal ring. Topological properties are investigated, such as diameter and average distance of ILLIAC networks and optimal degree-four chordal rings, another special class of degree-four chordal rings. Comparisons of ILLIAC networks and optimal chordal rings in these embedding issues are given.

Original languageEnglish
Pages (from-to)73-80
Number of pages8
JournalIEE Proceedings: Computers and Digital Techniques
Volume145
Issue number2
DOIs
Publication statusPublished - 1998 Jan 1

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Hardware and Architecture
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'Embedding meshes and TORUS networks onto degree-four chordal rings'. Together they form a unique fingerprint.

Cite this