Efficient Sequential and Parallel Routing Algorithms in Optical Multistage Interconnection Network

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

Full description

Saved in:

Bibliographic Details
Main Author:	Abduh Kaid, Monir Abdullah
Format:	Thesis
Language:	English
Published:	2005
Subjects:	Sequential processing (Computer science) Parallel processing (Electronic computers) Database searching
Online Access:	http://psasir.upm.edu.my/id/eprint/5850/1/FSKTM_2005_4%20IR.pdf
Tags:	Add Tag No Tags, Be the first to tag this record!

id	my-upm-ir.5850
record_format	uketd_dc
spelling	my-upm-ir.58502022-01-06T03:00:54Z Efficient Sequential and Parallel Routing Algorithms in Optical Multistage Interconnection Network 2005-06 Abduh Kaid, Monir Abdullah 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. Sequential processing (Computer science) Parallel processing (Electronic computers) Database searching 2005-06 Thesis http://psasir.upm.edu.my/id/eprint/5850/ http://psasir.upm.edu.my/id/eprint/5850/1/FSKTM_2005_4%20IR.pdf text en public masters Universiti Putra Malaysia Sequential processing (Computer science) Parallel processing (Electronic computers) Database searching Computer Science and Information Technology Othman, Mohamed
institution	Universiti Putra Malaysia
collection	PSAS Institutional Repository
language	English
advisor	Othman, Mohamed
topic	Sequential processing (Computer science) Parallel processing (Electronic computers) Database searching
spellingShingle	Sequential processing (Computer science) Parallel processing (Electronic computers) Database searching Abduh Kaid, Monir Abdullah Efficient Sequential and Parallel Routing Algorithms in Optical Multistage Interconnection Network
description	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.
format	Thesis
qualification_level	Master's degree
author	Abduh Kaid, Monir Abdullah
author_facet	Abduh Kaid, Monir Abdullah
author_sort	Abduh Kaid, Monir Abdullah
title	Efficient Sequential and Parallel Routing Algorithms in Optical Multistage Interconnection Network
title_short	Efficient Sequential and Parallel Routing Algorithms in Optical Multistage Interconnection Network
title_full	Efficient Sequential and Parallel Routing Algorithms in Optical Multistage Interconnection Network
title_fullStr	Efficient Sequential and Parallel Routing Algorithms in Optical Multistage Interconnection Network
title_full_unstemmed	Efficient Sequential and Parallel Routing Algorithms in Optical Multistage Interconnection Network
title_sort	efficient sequential and parallel routing algorithms in optical multistage interconnection network
granting_institution	Universiti Putra Malaysia
granting_department	Computer Science and Information Technology
publishDate	2005
url	http://psasir.upm.edu.my/id/eprint/5850/1/FSKTM_2005_4%20IR.pdf
_version_	1747810494258872320

Efficient Sequential and Parallel Routing Algorithms in Optical Multistage Interconnection Network

Similar Items