Embedding hex-cells into tree-hypercube networks

Dissertant

Qatawnih, Awwad Ibrahim

Thesis advisor

Meligi, Ali

Comitee Members

Shilbayah, Nidal
al-Sadi, Jihad
Abu al-Rubb, Imad

University

Middle East University

Faculty

Faculty of Information Technology

Department

Computer Science Department

University Country

Jordan

Degree

Master

Degree Date

2008

English Abstract

Graph embedding or graph mapping is an important aspect for interconnection networks used for communication between processors in parallel systems.

Some parallel algorithms use communication structures which can be represented by hexcells.

In order to run these algorithms on a tree-hypercube multiprocessor system, without changing the current topology and the running application, their communication graphs need to be embedded into tree- hypercube.

In this thesis, we have designed an algorithm for embedding hex-cells of n nodes into tree-hypercube TH(2,d) where d >= 2.

The embedding has dilation one, congestion one, and expansion 1.1.

In the algorithm an embedding of irregular shape of hex-cells into tree-hypercube TH(2,d) where d >= 2 is performed.

We have also designed an algorithm for embedding hex-cells HC(i), where i= 1,2 into tree-hypercube TH (2, d), where d = 2i.

As a result the embedding of Hex-cells into Tree-Hypercube in algorithm 4.1 has dilation one, congestion one, and expansion 1.1, and an embedding of irregular shape of hex-cells into tree-hypercube TH(2,d) where d >= 2 is performed.

In algorithm 4.2 the embedding has dilation 1, congestion 1 and expansion 1.1 when mapping HC(1); and dilation 1, congestion 1 expansion 1.3 when mapping HC(2).

Main Subjects

Information Technology and Computer Science

No. of Pages

68

Table of Contents

• APA
• MLA
• AMA

Language

English

Data Type

Arab Theses

Record ID

BIM-698782