Efficient Sequential and Parallel Routing Algorithms in Optical Multistage Interconnection Network

Abduh Kaid, Monir Abdullah (2005) Efficient Sequential and Parallel Routing Algorithms in Optical Multistage Interconnection Network. Masters thesis, Universiti Putra Malaysia.

[img] PDF
1109Kb

Abstract

As optical technology advances, there is a considerable interest in using this technology to implement interconnection networks and switches. Optical multistage interconnection network is popular in switching and communication applications. It has been used in telecommunication and parallel computing systems for many years. A major problem known as crosstalk is introduced by optical multistage interconnection network, which is caused by coupling two signals within a switching element. It is important to focus on an efficient solution to ,avoid crosstalk, which is routing traffic through an N x N optical network to avoid coupling two signals within each switching element.Under the constraint of avoiding crosstalk, we are interested in realising a permutation that will use the minimum number of passes to send all messages. This routing problem is an NPhard problem. Many algorithms are designed by many researchers to perform this routing such as window method, sequential algorithm, degree-descending algorithm, simulated annealing algorithm, genetic algorithm and ant colony algorithm.This thesis explores two approaches, sequential and parallel approaches. The first approach is to develop an efficient sequential algorithm for the window method. Reduction of the execution time of the algorithm in sequential platform, led to a massive improvement of the algorithm speed. Also an improved simulated annealing is proposed to solve the routing problem. The efficient combination of simulated annealing algorithm with the best heuristic algorithms gave much better result in a very minimal time. Parallelisation is another approach in our research. Three parallel strategies of the window method are developed in this research. The parallel window method with low communication overhead decreased 86% of the time compared to sequential window method. The parallel simulated annealing algorithm is also developed and it reduces 64% of the time compared to sequential simulated annealing.

Item Type:Thesis (Masters)
Subject:Sequential processing (Computer science)
Subject:Parallel processing (Electronic computers)
Subject:Database searching
Chairman Supervisor:Associate Professor Mohamed Othman, PhD
Call Number:FSKTM 2005 4
Faculty or Institute:Faculty of Computer Science and Information Technology
ID Code:5850
Deposited By: Nur Izyan Mohd Zaki
Deposited On:05 May 2010 08:42
Last Modified:27 May 2013 07:25

Repository Staff Only: item control page

Document Download Statistics

This item has been downloaded for since 05 May 2010 08:42.

View statistics for "Efficient Sequential and Parallel Routing Algorithms in Optical Multistage Interconnection Network "


Universiti Putra Malaysia Institutional Repository

Universiti Putra Malaysia Institutional Repository is an on-line digital archive that serves as a central collection and storage of scientific information and research at the Universiti Putra Malaysia.

Currently, the collections deposited in the IR consists of Master and PhD theses, Master and PhD Project Report, Journal Articles, Journal Bulletins, Conference Papers, UPM News, Newspaper Cuttings, Patents and Inaugural Lectures.

As the policy of the university does not permit users to view thesis in full text, access is only given to the first 24 pages only.