Faculty of Science - Cairo University

Name : Asaad Ahmed Gad El-Rab Ahmed

Date of Birth : 29/11/1977

Registration Date: 18/2/2004

Awarding Date :   17/2/2008

Supervisores :

   1- Prof. Ahmed Badr-Al-Din Khalil, Faculty of Science, Cairo University.

            2- Prof. Salwa M. M. Nassar, Electronics Research Institute.

            3- Dr.   Mohammed A. Abd El-baky, Faculty of Science, Fayoum University.

Examiners :

   1- Prof. Minrou Ito, Graduate school of Information Science, Nara Institute of Science and Technology. 8916-5 Takayama-Cho, Ikoma,Nara, 630-0192, Japan.

   2- Porf. Ahmed Ali Ahmed Radwan, Faculty of Science, Minia University, Egypt.

   3- Ahmed Badr-Al-Din khalil, Faculty of Science, Cairo University, Egypt.

Title of Thesis:

" performance Analysis of Multicomputer Systems"

Key words:

      Multicomputer systems, Irregular Networks, Routing, Deadlock, Live-Lock, Latency Time, Traffic Time.

Summary:

Many advanced research problems such as artificial intelligence, expert systems, weather forecasting, space sciences and others need a greater computing power. Multicomputer systems, which emphasize parallel processing, are the most favorable architectures to increase the computing power. These systems involve connecting multiple computers, often called nodes, interconnected by a message-passing network together into a single system. Each node has a processor with a local memory, a set of input / output devices, and a router. All local memories are private and are accessible only by local processors. The router manages message transmission across the nodes; messages can carry information between nodes, and also synchronize node activities.

Recently, irregular networks have been considered as cost-effective alternatives to massively parallel systems. In irregular networks, the irregularity is a common characteristic that allows an easy design of scalable and flexible systems with incremental expansion capability. The interconnection networks depend on several factors including topology, switching technique and routing. Switching techniques are used to transmit messages among processors. Routing schemes are used to determine the path selected by a packet in order to reach its destination. Designing deadlock-free routing algorithms is a major problem for irregular networks. Deadlock in the interconnection network occurs when set of messages is blocked forever.

This thesis proposes two new routing algorithms that efficiently support both unicast and multicast communication in irregular networks topologies. The first algorithm, Depth Prefix Routing (DPR), is a unicast routing (one-to- one), while the second algorithm, Horizontal Path Ancestor Multicast (HPAM), is a multicast routing (one-to- many).

Mathematical definitions are introduced to define the message forwarding of the proposed algorithms.

The proposed algorithms are deadlock-and livelock-free. The performance of the proposed algorithms is evaluated through comparing them with previous algorithms. The results demonstrated that the proposed algorithms outperform better in terms of the latency and traffic times.

Designed and Directed by A.H.A