An Enhanced Simulated Annealing Routing Algorithm for Semi-Diagonal Torus Network

Multiprocessor is another great technology that helps in advancing human civilization due to high demands for solving complex problems. A multiprocessing system can have a lot of replicated processor-memory pairs (henceforth regard as net) or also called as processing nodes. Each of these nodes is c...

Full description

Bibliographic Details
Main Authors:	Noraziah, Adzhar, Shaharuddin, Salleh
Format:	Article
Language:	English
Published:	IOP Publishing 2017
Subjects:	Q Science (General)
Online Access:	http://umpir.ump.edu.my/id/eprint/19140/ http://umpir.ump.edu.my/id/eprint/19140/ http://umpir.ump.edu.my/id/eprint/19140/ http://umpir.ump.edu.my/id/eprint/19140/1/An%20enhanced%20simulated%20annealing%20routing%20algorithm%20for%20semi-diagonal%20torus%20network.pdf

id	ump-19140
recordtype	eprints
spelling	ump-191402018-05-16T04:05:32Z http://umpir.ump.edu.my/id/eprint/19140/ An Enhanced Simulated Annealing Routing Algorithm for Semi-Diagonal Torus Network Noraziah, Adzhar Shaharuddin, Salleh Q Science (General) Multiprocessor is another great technology that helps in advancing human civilization due to high demands for solving complex problems. A multiprocessing system can have a lot of replicated processor-memory pairs (henceforth regard as net) or also called as processing nodes. Each of these nodes is connected to each other through interconnection networks and passes message using a standard message passing mechanism. In this paper, we present a routing algorithm based on enhanced simulated annealing technique to provide the connection between nodes in a semi-diagonal torus (SD-Torus) network. This network is both symmetric and regular; thus, make it very beneficial in the implementation process. The main objective is to maximize the number of established connection between nodes in this SD-Torus network. In order to achieve this objective, each node must be connected in its shortest way as possible. We start our algorithm by designing shortest path algorithm based on Dijkstra's method. While this algorithm guarantees to find the shortest path for each single net, if it exists, each routed net will form obstacle for later paths. This increases the complexity to route later nets and makes routing longer than optimal, or sometimes impossible to complete. The solution is further refined by re-routing all nets in different orders using simulated annealing method. Through simulation program, our proposed algorithm succeeded in performing complete routing up to 81 nodes with 40 nets in 9×9 SD-Torus network size. IOP Publishing 2017 Article PeerReviewed application/pdf en cc_by http://umpir.ump.edu.my/id/eprint/19140/1/An%20enhanced%20simulated%20annealing%20routing%20algorithm%20for%20semi-diagonal%20torus%20network.pdf Noraziah, Adzhar and Shaharuddin, Salleh (2017) An Enhanced Simulated Annealing Routing Algorithm for Semi-Diagonal Torus Network. Journal of Physics: Conference series, 890. pp. 1-6. ISSN 1742-6588 (print); 1742-6596 (online) https://doi.org/10.1088/1742-6596/890/1/012082 doi: 10.1088/1742-6596/890/1/012082
repository_type	Digital Repository
institution_category	Local University
institution	Universiti Malaysia Pahang
building	UMP Institutional Repository
collection	Online Access
language	English
topic	Q Science (General)
spellingShingle	Q Science (General) Noraziah, Adzhar Shaharuddin, Salleh An Enhanced Simulated Annealing Routing Algorithm for Semi-Diagonal Torus Network
description	Multiprocessor is another great technology that helps in advancing human civilization due to high demands for solving complex problems. A multiprocessing system can have a lot of replicated processor-memory pairs (henceforth regard as net) or also called as processing nodes. Each of these nodes is connected to each other through interconnection networks and passes message using a standard message passing mechanism. In this paper, we present a routing algorithm based on enhanced simulated annealing technique to provide the connection between nodes in a semi-diagonal torus (SD-Torus) network. This network is both symmetric and regular; thus, make it very beneficial in the implementation process. The main objective is to maximize the number of established connection between nodes in this SD-Torus network. In order to achieve this objective, each node must be connected in its shortest way as possible. We start our algorithm by designing shortest path algorithm based on Dijkstra's method. While this algorithm guarantees to find the shortest path for each single net, if it exists, each routed net will form obstacle for later paths. This increases the complexity to route later nets and makes routing longer than optimal, or sometimes impossible to complete. The solution is further refined by re-routing all nets in different orders using simulated annealing method. Through simulation program, our proposed algorithm succeeded in performing complete routing up to 81 nodes with 40 nets in 9×9 SD-Torus network size.
format	Article
author	Noraziah, Adzhar Shaharuddin, Salleh
author_facet	Noraziah, Adzhar Shaharuddin, Salleh
author_sort	Noraziah, Adzhar
title	An Enhanced Simulated Annealing Routing Algorithm for Semi-Diagonal Torus Network
title_short	An Enhanced Simulated Annealing Routing Algorithm for Semi-Diagonal Torus Network
title_full	An Enhanced Simulated Annealing Routing Algorithm for Semi-Diagonal Torus Network
title_fullStr	An Enhanced Simulated Annealing Routing Algorithm for Semi-Diagonal Torus Network
title_full_unstemmed	An Enhanced Simulated Annealing Routing Algorithm for Semi-Diagonal Torus Network
title_sort	enhanced simulated annealing routing algorithm for semi-diagonal torus network
publisher	IOP Publishing
publishDate	2017
url	http://umpir.ump.edu.my/id/eprint/19140/ http://umpir.ump.edu.my/id/eprint/19140/ http://umpir.ump.edu.my/id/eprint/19140/ http://umpir.ump.edu.my/id/eprint/19140/1/An%20enhanced%20simulated%20annealing%20routing%20algorithm%20for%20semi-diagonal%20torus%20network.pdf
first_indexed	2023-09-18T22:27:25Z
last_indexed	2023-09-18T22:27:25Z
_version_	1777416060009447424

An Enhanced Simulated Annealing Routing Algorithm for Semi-Diagonal Torus Network

Similar Items