Embedding hex-cells into tree-hypercube networks

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

Qatawnih, Awwad Ibrahim

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

Meligi, Ali

أعضاء اللجنة

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

الجامعة

جامعة الشرق الأوسط

الكلية

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

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

قسم علم الحاسوب

دولة الجامعة

الأردن

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

ماجستير

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

2008

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

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).

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

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

عدد الصفحات

68

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

• APA
• MLA
• AMA

لغة النص

الإنجليزية

نوع البيانات

رسائل جامعية

رقم السجل

BIM-698782