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

• 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/1/An%20enhanced%20simulated%20annealing%20routing%20algorithm%20for%20semi-diagonal%20torus%20network.pdf; http://umpir.ump.edu.my/id/eprint/19140/; https://doi.org/10.1088/1742-6596/890/1/012082
• Institution: Universiti Malaysia Pahang

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.