Embedding Chordal Rings and Pyramids into Mesh-Connected Computers with Multiple Buses

Noritaka SHIGEI  Hiromi MIYAJIMA  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E83-D   No.2   pp.142-150
Publication Date: 2000/02/25
Online ISSN: 
DOI: 
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Theory/Models of Computation
Keyword: 
mesh-connected computer,  global bus,  embedding,  chordal ring,  pyramid,  

Full Text: PDF>>
Buy this Article




Summary: 
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.