Abstract

In direct interconnection networks, the collective communication operation one to all, which is usually refe1Ted to as broadcasting, can be generalized to allow one source node to send a message to a rectangular region of nodes, rather than to all nodes. Most of the proposed routing algorithms for direct mesh and torus networks use a broadcast tree of unicast messages. While the Minimum Spanning Tree tree-based region broadcasting is not deadlock free, unless the network is partitioned into many virtual sub-networks, where the number of virtual channels grows exponentially with the dimension of the network, the Minimum Spanning Tree Safe algorithm is deadlock­free even with one virtual channel. The Minimum Spanning Tree Safe algorithm perfo1ms very well if the source nodes of broadcast messages are part of their broadcast regions; otherwise, broadcast messages may need to be ejected as soon as they reach the first node in their region and then re-injected in order to avoid deadlock. This thesis proposes two versions of the Minimum Spanning Tree region-broadcasting algorithm that are based on the idea of starting always at a comer of a region. The first algorithm uses always a fixed comer, while the second one uses the nearest comer. The two proposed algorithms are deadlock free even when source node is located outside the broadcast region without the need for intermediate ejection and re-injection that is required by the Minimum Spanning Tree Safe. Both algorithms use virtual cut through for buffering blocked packets and can be safely mixed with dimension order unicast routing algorithms. The performance of two dimensional and four dimensional mesh networks was evaluated using the two proposed tree-based broadcast algorithms and compared to other existing algorithms which are: the Recursive Doubling, the Column Path, and the Minimum Spanning Tree Safe. The results obtained are encouragmg.

Department

Computer Science & Engineering Department

Degree Name

MS in Computer Science

Date of Award

2-1-2003

Online Submission Date

1-1-2002

First Advisor

Muhammed Mudawwar

Committee Member 1

Muhammed Mudawwar

Committee Member 2

M.N. Mikhail

Committee Member 3

Amr El Kadi

Document Type

Thesis

Extent

98 leaves :

Library of Congress Subject Heading 1

Computer networks.

Rights

The author retains all rights with regard to copyright. The author certifies that written permission from the owner(s) of third-party copyrighted matter included in the thesis, dissertation, paper, or record of study has been obtained. The author further certifies that IRB approval has been obtained for this thesis, or that IRB approval is not necessary for this thesis. Insofar as this thesis, dissertation, paper, or record of study is an educational record as defined in the Family Educational Rights and Privacy Act (FERPA) (20 USC 1232g), the author has granted consent to disclosure of it to anyone who requests a copy.

Call Number

Thesis 2002/82

Location

mmbk

Download

Included in

Engineering Commons

Share

COinS