Embedding quadtree structures into X-Mesh

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

Jabir, Muna

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

Bellaachia, Abd al-Ghani

الجامعة

جامعة الأخوين

الكلية

كلية الهندسة و العلوم

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

علوم الحاسب

دولة الجامعة

المغرب

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

ماجستير

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

1997

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

Given an X-mcsh M and a quadtree T, we study the problem of embedding T in M to minimize the expansion, the congestion and the communication cost.

We will present a new embedding algorithm called K~embedding for quadtrees into X-mesh.

This new strategy improves the expansion cost of an existing algorithm, the 4-Basic-Unit embedding, by 33% while keeping the communication cost the same.

It also gives a constant link congestion value for every level of the quadtree which is a very uselul result if we consider the wormhole routing as a communication protocol.

Motivated by the fact that square meshes are the most used, we present a new algorithm for quadtrees into square X-mesh called S-embedding which turns out to be very efficient in temis of conununication.

It improves the communication cost of the K-embedding by 17 % while increasing the expansion cost by 4%, which is not a significant waste of space if we compare it to the gam in terms of communication.

A merge-sort application using quadtrees onto Maspar machines is implemented in order to compare the pcaformancc of the three algorithms namely, the 4-Basic-Unlt embedding, die K.-embedding, and the S-embedding.

The simulation results showed that the S-embedding has better performance than the two other algorithms.

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

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

الموضوعات

• الخوارزميات
• الاتصالات السلكية و اللاسلكية
• معالجة البيانات
• شبكات الحاسوب
• الاتصالات الرقمية
• شبكات المعلومات

عدد الصفحات

39

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

• APA
• MLA
• AMA

لغة النص

الإنجليزية

نوع البيانات

رسائل جامعية

رقم السجل

BIM-645940