For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Embedding Chordal Rings and Pyramids into Mesh-Connected Computers with Multiple Buses
Noritaka SHIGEI Hiromi MIYAJIMA
IEICE TRANSACTIONS on Information and Systems
Publication Date: 2000/02/25
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Theory/Models of Computation
mesh-connected computer, global bus, embedding, chordal ring, pyramid,
Full Text: PDF>>
This paper describes embeddings of chordal rings and pyramids into mesh-connected computers with multiple buses which have a bus on each row and each column, called MCCMBs. MCCMBs have two types of communication. The one is local communication, provided by local links, and the other is global communication, provided by buses. By efficiently combining the two types of communication, optimal or efficient embeddings are achieved. For a large set of chordal rings, optimal embeddings, whose expansion, load, dilation and congestion are 1, are given. For pyramids, an efficient embedding based on a two phase strategy is presented. The embedding balances dilation and congestion.