Embedding meshes and TORUS networks onto degree-four chordal rings

J. F. Fang, Ju-Yuan 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

Fingerprint

Mesh
Ring
Graph Embedding
Average Distance
Snakes
Parallel Programs
Interconnect
Vertex of a graph
Topological Properties
Symmetry
Arbitrary
Demonstrate
Class

All Science Journal Classification (ASJC) codes

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

Cite this

@article{9898d35c7a7a4ed482100e0525b64710,
title = "Embedding meshes and TORUS networks onto degree-four chordal rings",
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.",
author = "Fang, {J. F.} and Ju-Yuan Hsiao and Tang, {C. Y.}",
year = "1998",
month = "1",
day = "1",
doi = "10.1049/ip-cdt:19981903",
language = "English",
volume = "145",
pages = "73--80",
journal = "IEE Proceedings: Computers and Digital Techniques",
issn = "1350-2387",
publisher = "Institute of Electrical Engineers",
number = "2",

}

Embedding meshes and TORUS networks onto degree-four chordal rings. / Fang, J. F.; Hsiao, Ju-Yuan; Tang, C. Y.

In: IEE Proceedings: Computers and Digital Techniques, Vol. 145, No. 2, 01.01.1998, p. 73-80.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Embedding meshes and TORUS networks onto degree-four chordal rings

AU - Fang, J. F.

AU - Hsiao, Ju-Yuan

AU - Tang, C. Y.

PY - 1998/1/1

Y1 - 1998/1/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0032023630&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0032023630&partnerID=8YFLogxK

U2 - 10.1049/ip-cdt:19981903

DO - 10.1049/ip-cdt:19981903

M3 - Article

AN - SCOPUS:0032023630

VL - 145

SP - 73

EP - 80

JO - IEE Proceedings: Computers and Digital Techniques

JF - IEE Proceedings: Computers and Digital Techniques

SN - 1350-2387

IS - 2

ER -