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

Title:	Efficient hypercube communications
Author:	Bhatt, Shreyas R.
View Online:	njit-etd1992-055 ([x], [64] pages ~ 1.6 MB pdf)
Department:	Department of Electrical and Computer Engineering
Degree:	Master of Science
Program:	Electrical Engineering
Document Type:	Thesis
Advisory Committee:	Ziavras, Sotirios (Committee chair) Carpinelli, John D. (Committee member) Hou, Edwin (Committee member)
Date:	1992-01
Keywords:	Hypercube networks (Computer networks)
Availability:	Unrestricted
Abstract:	Hypercube algorithms may be developed for a variety of communication-intensive tasks such as sending a message from one node to another, broadcasting a message from one node to all others, broadcasting a message from each node to all others, all-to-all personalized communication, one-to-all personalized communication, and exchanging messages between nodes via fixed permutations. All these communication patterns are special cases of many-to-many personalized communication. The problem of many-to-many personalized communication is investigated here. Two routing algorithms for many-to-many personalized communication are presented here. The algorithms proposed yield very high performance with respect to the number of time steps and packet transmissions. The first algorithm yields high performance through attempts to equibalance the number of messages at intermediate nodes. This technique tries to avoid creating a bottleneck at any node and thus reduces the total communication time. The second algorithm yields high performance through one-step time-lookahead equibalancing. It chooses from the candidate intermediate nodes the one which will probably have the minimum number of messages in the next cycle.