Embedding quadtree structures into X-Mesh

Dissertant

Jabir, Muna

Thesis advisor

Bellaachia, Abd al-Ghani

University

Al Akhawayn University

Faculty

School of Science and Engineering

Department

Computer Science

University Country

Morocco

Degree

Master

Degree Date

1997

English Abstract

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.

Main Subjects

Information Technology and Computer Science

Topics

• Algorithms
• Telecommunications
• Data processing
• Computer networks
• Digital communications
• Information networks

No. of Pages

39

Table of Contents

• APA
• MLA
• AMA

Language

English

Data Type

Arab Theses

Record ID

BIM-645940