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). (Published)
|
PDF
An enhanced simulated annealing routing algorithm for semi-diagonal torus network.pdf Available under License Creative Commons Attribution. Download (269kB) | Preview |
Abstract
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.
| Item Type: | Article |
|---|---|
| Uncontrolled Keywords: | Multiprocessor; semi-diagonal torus (SD-Torus) network |
| Subjects: | Q Science > Q Science (General) |
| Faculty/Division: | Faculty of Industrial Sciences And Technology |
| Depositing User: | Mrs. Neng Sury Sulaiman |
| Date Deposited: | 24 Nov 2017 02:06 |
| Last Modified: | 16 May 2018 04:05 |
| URI: | http://umpir.ump.edu.my/id/eprint/19140 |
| Download Statistic: | View Download Statistics |
Actions (login required)
 |
View Item |