Embedding chordal rings and pyramids into mesh-connected computers with multiple buses

This paper describes embeddings of chordal rings and pyramids into mesh-con nected 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 l ocal communication, provided by local links, and the other is global commun ication, provided by buses. By efficiently combining the two types of commu nication, optimal or efficient embeddings are achieved. For a large set of chordal rings, optimal embeddings, whose expansion, load, dilation and cong estion are 1, are given. For pyramids, an efficient embedding based on a tw o phase strategy is presented. The embedding balances dilation and congesti on.