Routing in mesh-hypercube network

مقدم أطروحة جامعية

Mahadin, Bassam Muhammad

مشرف أطروحة جامعية

Umari, Mahmud

الجامعة

الأكاديمية العربية للعلوم المالية و المصرفية

الكلية

كلية نظم و تكنولوجيا المعلومات

القسم الأكاديمي

قسم نظم المعلومات الحاسوبية

دولة الجامعة

الأردن

الدرجة العلمية

دكتوراه

تاريخ الدرجة العلمية

2005

الملخص الإنجليزي

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.

التخصصات الرئيسية

تكنولوجيا المعلومات وعلم الحاسوب

الموضوعات

• الخوارزميات

عدد الصفحات

213

قائمة المحتويات

• APA
• MLA
• AMA

لغة النص

الإنجليزية

نوع البيانات

رسائل جامعية

رقم السجل

BIM-316192