Routing problem in rectangular mesh network using shortest path based Greedy method
A supercomputer can have thousands of processor-memory pairs which often referred as processing pins. Each of these pins is connected to each other through networks and passes message using a standard message passing mechanism such as Message Passing Interface. In this research, we consider the rout...
| Main Authors: | , , , |
|---|---|
| Format: | Conference or Workshop Item |
| Language: | English |
| Published: |
IOP Publishing
2019
|
| Subjects: | |
| Online Access: | http://umpir.ump.edu.my/id/eprint/28577/1/Routing%20problem%20in%20rectangular%20mesh%20network%20using%20shortest.pdf |
| _version_ | 1796994103815176192 |
|---|---|
| author | Noraziah, Adzhar Shaharuddin, Salleh Yuhani, Yusof Muhammad Azrin, Ahmad |
| author_facet | Noraziah, Adzhar Shaharuddin, Salleh Yuhani, Yusof Muhammad Azrin, Ahmad |
| author_sort | Noraziah, Adzhar |
| collection | UMP |
| description | A supercomputer can have thousands of processor-memory pairs which often referred as processing pins. Each of these pins is connected to each other through networks and passes message using a standard message passing mechanism such as Message Passing Interface. In this research, we consider the routing problem in rectangular mesh network. Each terminal pin in the network needs to be connected with its destination pin for it to function properly. Thus, maximizing the number of connection for each pair of pins and keeping the total energy throughout the network minimum becomes our main objective. In order to achieve this objective, each net need to be routed as shortest as possible. Therefore, developing a shortest path based routing algorithm is in need. In this research, Dijkstra's algorithm is used to establish the shortest connection for each net. While this method guarantees to provide the shortest connection for each single net (if exists), however each routed net will become the obstacles and block later connections. This will add complexities to route later nets and make its routing longer than optimal or sometimes impossible to complete. Therefore, the routing sequence need to be rip-up and all nets need to be re-routed. This paper presents a complete routing algorithm which can further refine the solution by using Dijkstra's based greedy method. The outcomes from this research is expected to benefit engineers from electric & electronic industry. |
| first_indexed | 2024-03-06T12:43:07Z |
| format | Conference or Workshop Item |
| id | UMPir28577 |
| institution | Universiti Malaysia Pahang |
| language | English |
| last_indexed | 2024-03-06T12:43:07Z |
| publishDate | 2019 |
| publisher | IOP Publishing |
| record_format | dspace |
| spelling | UMPir285772021-02-08T07:53:18Z http://umpir.ump.edu.my/id/eprint/28577/ Routing problem in rectangular mesh network using shortest path based Greedy method Noraziah, Adzhar Shaharuddin, Salleh Yuhani, Yusof Muhammad Azrin, Ahmad QA Mathematics QA75 Electronic computers. Computer science TK Electrical engineering. Electronics Nuclear engineering A supercomputer can have thousands of processor-memory pairs which often referred as processing pins. Each of these pins is connected to each other through networks and passes message using a standard message passing mechanism such as Message Passing Interface. In this research, we consider the routing problem in rectangular mesh network. Each terminal pin in the network needs to be connected with its destination pin for it to function properly. Thus, maximizing the number of connection for each pair of pins and keeping the total energy throughout the network minimum becomes our main objective. In order to achieve this objective, each net need to be routed as shortest as possible. Therefore, developing a shortest path based routing algorithm is in need. In this research, Dijkstra's algorithm is used to establish the shortest connection for each net. While this method guarantees to provide the shortest connection for each single net (if exists), however each routed net will become the obstacles and block later connections. This will add complexities to route later nets and make its routing longer than optimal or sometimes impossible to complete. Therefore, the routing sequence need to be rip-up and all nets need to be re-routed. This paper presents a complete routing algorithm which can further refine the solution by using Dijkstra's based greedy method. The outcomes from this research is expected to benefit engineers from electric & electronic industry. IOP Publishing 2019-11-08 Conference or Workshop Item PeerReviewed pdf en cc_by http://umpir.ump.edu.my/id/eprint/28577/1/Routing%20problem%20in%20rectangular%20mesh%20network%20using%20shortest.pdf Noraziah, Adzhar and Shaharuddin, Salleh and Yuhani, Yusof and Muhammad Azrin, Ahmad (2019) Routing problem in rectangular mesh network using shortest path based Greedy method. In: Journal of Physics: Conference Series, 12th Seminar on Science and Technology 2018 , 2-3 October 2018 , Kota Kinabalu, Sabah, Malaysia. pp. 1-8., 1358 (012079). ISSN 1742-6588 (print); 1742-6596 (online) https://doi.org/10.1088/1742-6596/1358/1/012079 |
| spellingShingle | QA Mathematics QA75 Electronic computers. Computer science TK Electrical engineering. Electronics Nuclear engineering Noraziah, Adzhar Shaharuddin, Salleh Yuhani, Yusof Muhammad Azrin, Ahmad Routing problem in rectangular mesh network using shortest path based Greedy method |
| title | Routing problem in rectangular mesh network using shortest path based Greedy method |
| title_full | Routing problem in rectangular mesh network using shortest path based Greedy method |
| title_fullStr | Routing problem in rectangular mesh network using shortest path based Greedy method |
| title_full_unstemmed | Routing problem in rectangular mesh network using shortest path based Greedy method |
| title_short | Routing problem in rectangular mesh network using shortest path based Greedy method |
| title_sort | routing problem in rectangular mesh network using shortest path based greedy method |
| topic | QA Mathematics QA75 Electronic computers. Computer science TK Electrical engineering. Electronics Nuclear engineering |
| url | http://umpir.ump.edu.my/id/eprint/28577/1/Routing%20problem%20in%20rectangular%20mesh%20network%20using%20shortest.pdf |
| work_keys_str_mv | AT noraziahadzhar routingprobleminrectangularmeshnetworkusingshortestpathbasedgreedymethod AT shaharuddinsalleh routingprobleminrectangularmeshnetworkusingshortestpathbasedgreedymethod AT yuhaniyusof routingprobleminrectangularmeshnetworkusingshortestpathbasedgreedymethod AT muhammadazrinahmad routingprobleminrectangularmeshnetworkusingshortestpathbasedgreedymethod |