A cost-effective load balanced adaptive routing scheme for mesh-connected networks

Author

Liu, Xicheng ; Zhang, Sijing ; Li, Timothy J.

Author_Institution

Centre for Commun. Syst. Res., Cambridge Univ., UK

fYear

2000

fDate

2000

Firstpage

532

Lastpage

538

Abstract

A highly cost-effective adaptive routing algorithm for n-D meshes is designed. It employs only two virtual channels. The planar routing and the 2D VBMAR are used as constructs for it. Routing freedom is greatly enhanced to improve performance. As a result, the algorithm features load balance and high adaptivity. Deadlock freedom of the algorithm is proved. Extensive simulations show that it not only outperforms an algorithm with equal virtual channels, but also excels the fully routing algorithm with much more virtual channels

Keywords

adaptive systems; concurrency control; multiprocessor interconnection networks; network routing; processor scheduling; resource allocation; 2D VBMAR; cost-effective adaptive routing algorithm; cost-effective load balanced adaptive routing scheme; deadlock freedom; fully routing algorithm; load balance; mesh-connected networks; n-D meshes; planar routing; routing freedom; virtual channels; virtual network load balanced minimal adaptive routing algorithm; Algorithm design and analysis; Computational modeling; Computer architecture; Concurrent computing; Load modeling; Multiprocessor interconnection networks; Parallel processing; Power system modeling; Routing; System recovery;

fLanguage

English

Publisher

ieee

Conference_Titel

Modeling, Analysis and Simulation of Computer and Telecommunication Systems, 2000. Proceedings. 8th International Symposium on

Conference_Location

San Francisco, CA

ISSN

1526-7539

Print_ISBN

0-7695-0728-X

Type

conf

DOI

10.1109/MASCOT.2000.876581

Filename

876581