Routing in mesh-hypercube network

Dissertant

Mahadin, Bassam Muhammad

Thesis advisor

Umari, Mahmud

University

Arab Academy for Financial and Banking Sciences

Faculty

The Faculty of Information Systems and Technology

Department

Computer information systems

University Country

Jordan

Degree

Ph.D.

Degree Date

2005

English Abstract

Mesh Hypercube (MH) network of arbitrary size, has been introduced as a new interconnection network for parallel systems.

The basic structure for this network is a combination of both mesh and hypercube networks.

It combines the attractive features of both the hypercube and the mesh, while at the same time overcoming their disadvantages.

The routing capabilities of the MH network were studied, and the length and number of parallel shortest paths in MH were computed.

Point-to-point routing in a multicomputer system is the process of sending a message from a source node (processor) to a destination node (processor).

Since point-to-point routing is the fundamental form of data communication in multicomputer systems, optimal point-to-point routing strategies for the MH network were developed, and a point-to-point distributed routing algorithm is given.

The algorithm uses only minimal length path to deliver a message from its source to its destination Wormhole routing has become the switching technique of choice in modern distributed memory multiprocessors.

There are two factors account the popularity of wormhole routing in such systems.

First, the messages latency is largely insensitive to the distance between the source and the destination.

Second, wormhole routing requires only enough storage to buffer a few flits, rather than the entire packet.

Two wormhole routing algorithms for unicast and multicast communication were introduced.

These algorithms are based on labeling the nodes in the network to prevent deadlock and livelock problems.

Messages are allowed to travel in ascending and descending order of labels only to prevent any cyclic dependencies between nodes.

A wormhole routing algorithm for broadcast communication in MH was also introduced.

The algorithm is based on dividing the network into mesh and hypercube sub networks.

The hypercube at each level is also divided into sub cubes of dimension two where each of which consists of four nodes.

The algorithm takes advantage of the distance insensitivity of wormhole routing and the presence of multiple ports between processors and their routers.

The algorithm takes in consideration two issues: deadlock-free and termination condition.

A simulation program for each individual algorithm was developed to show their performance.

The simulation shows the behavior of each algorithm under different loads and dimensions of the network.

The simulation is also used to compare the behavior of the routing algorithms on both the MH and hypercube networks.

Main Subjects

Information Technology and Computer Science

Topics

• Algorithms

No. of Pages

213

Table of Contents

• APA
• MLA
• AMA

Language

English

Data Type

Arab Theses

Record ID

BIM-316192