The New Jersey Institute of Technology's
Electronic Theses & Dissertations Project

Title:	Deterministic and adaptive routing algorithms for mesh-connected computers
Author:	Cai, Yikui
View Online:	njit-etd1994-068 (xi, 65 pages ~ 2.2 MB pdf)
Department:	Department of Electrical and Computer Engineering
Degree:	Master of Science
Program:	Electrical Engineering
Document Type:	Thesis
Advisory Committee:	Palis, Michael Abueg (Committee chair) Nassimi, David (Committee member) Ziavras, Sotirios (Committee member)
Date:	1994-05
Keywords:	Computer architecture.
Availability:	Unrestricted
Abstract:	The two-dimensional mesh topology has been widely used in many multicomputer systems, such as the AMETEK Series 2010, Illiac IV, MPP, DAP, MasPar MP-1 and Intel Paragon. Its major advantages are its excellent scalability and simplicity. New generation multicomputer uses a switching technique called wormhole routing. The essential idea of wormhole routing is to advance a packet directly from incoming to outgoing channel without sorting it, as soon as enough information has been received in the packet header to select the outgoing channel. It has advantages of low latency and low error rate. The problems addressed by this thesis are to evaluate existing routing algorithms for the 2D mesh based on the wormhole model and to design a new routing algorithm that performs better from existing algorithms. In this thesis, the performance of both deterministic and adaptive algorithms, as functions of network size, router buffer size, packet length, is evaluated by computer simulation under different traffic model. Also, a new algorithm, called the west-north-first algorithm, is proposed and tested. It contains both characteristics of deterministic and adaptive algorithm, and hence has a better overall performance under various network traffic models. The results of this study can be applied to the design of parallel processing network system.