Optimum embeddings of end-around meshes into pyramid networks

A. Dingle, H. Barada

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

5 Scopus citations

Abstract

To increase the utility of task-oriented or specialized parallel networks, especially those already constructed, we can simulate one parallel network on another. Of primary interest then is the lower bound on the cost of such a simulation. We show that end-around meshes can be mapped to pyramids with dilation two, and minimal expansion. Furthermore, we show that if all computations are synchronized using a global clock (i.e. using both networks as synchronous machines), we can achieve an effective edge congestion of one. In this manner, we remove the need for scheduling or queueing of messages since each communication link hosts at most one message path per cycle. Hence, we obtain essentially a contention-free simulation of one parallel interconnection network by another. We also prove that this embedding is optimum, i.e. end-around meshes are not subgraphs of pyramids.

Original languageBritish English
Title of host publicationProceedings - 5th International Parallel Processing Symposium, IPPS 1991
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages445-451
Number of pages7
ISBN (Electronic)0818691670, 9780818691676
DOIs
StatePublished - 1991
Event5th International Parallel Processing Symposium, IPPS 1991 - Anaheim, United States
Duration: 30 Apr 19912 May 1991

Publication series

NameProceedings - 5th International Parallel Processing Symposium, IPPS 1991

Conference

Conference5th International Parallel Processing Symposium, IPPS 1991
Country/TerritoryUnited States
CityAnaheim
Period30/04/912/05/91

Fingerprint

Dive into the research topics of 'Optimum embeddings of end-around meshes into pyramid networks'. Together they form a unique fingerprint.

Cite this