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...
| Main Author: | |
|---|---|
| Format: | Thesis |
| Language: | English |
| Published: |
2005
|
| Subjects: | |
| Online Access: | http://psasir.upm.edu.my/id/eprint/5850/1/FSKTM_2005_4%20IR.pdf |
| _version_ | 1796967044328980480 |
|---|---|
| author | Abduh Kaid, Monir Abdullah |
| author_facet | Abduh Kaid, Monir Abdullah |
| author_sort | Abduh Kaid, Monir Abdullah |
| collection | UPM |
| 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. |
| first_indexed | 2024-03-06T07:08:07Z |
| format | Thesis |
| id | upm.eprints-5850 |
| institution | Universiti Putra Malaysia |
| language | English |
| last_indexed | 2024-03-06T07:08:07Z |
| publishDate | 2005 |
| record_format | dspace |
| spelling | upm.eprints-58502022-01-06T03:00:54Z http://psasir.upm.edu.my/id/eprint/5850/ Efficient Sequential and Parallel Routing Algorithms in Optical Multistage Interconnection Network 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. 2005-06 Thesis NonPeerReviewed text en http://psasir.upm.edu.my/id/eprint/5850/1/FSKTM_2005_4%20IR.pdf Abduh Kaid, Monir Abdullah (2005) Efficient Sequential and Parallel Routing Algorithms in Optical Multistage Interconnection Network. Masters thesis, Universiti Putra Malaysia. 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 |
| title | 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_short | Efficient Sequential and Parallel Routing Algorithms in Optical Multistage Interconnection Network |
| title_sort | efficient sequential and parallel routing algorithms in optical multistage interconnection network |
| topic | Sequential processing (Computer science) Parallel processing (Electronic computers) Database searching |
| url | http://psasir.upm.edu.my/id/eprint/5850/1/FSKTM_2005_4%20IR.pdf |
| work_keys_str_mv | AT abduhkaidmonirabdullah efficientsequentialandparallelroutingalgorithmsinopticalmultistageinterconnectionnetwork |