The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
Kami mereka bentuk algoritma penghalaan lalai baharu untuk Networks-on-Chip (NoCs) berasaskan mesh dua dimensi yang dipanggil LEF (Long Edge First) yang menawarkan daya pemprosesan tinggi dengan kerumitan reka bentuk yang rendah. Idea asas LEF berasal daripada kebijaksanaan konvensional dalam memilih algoritma penghalaan pesanan dimensi (DOR) yang sesuai untuk superkomputer dengan jala asimetri atau torus saling bersambung: penghalaan dimensi terpanjang terlebih dahulu memberikan prestasi yang lebih baik daripada strategi lain. Dalam LEF, kami menggabungkan XY DOR dan YX DOR. Apabila menghalakan paket, algoritma DOR yang dipilih bergantung pada kedudukan relatif antara nod sumber dan nod destinasi. Keputusan memilih algoritma DOR yang sesuai tidak ditetapkan pada bentuk rangkaian tetapi sebaliknya dibuat berdasarkan setiap paket. Kami juga mencadangkan kaedah mengelakkan kebuntuan yang cekap untuk LEF di mana penggunaan saluran maya adalah lebih fleksibel daripada kaedah konvensional. Kami menilai LEF berbanding O1TURN, satu lagi algoritma penghalaan lalai yang berkesan, dan algoritma penghalaan penyesuaian minimum berdasarkan model giliran ganjil genap. Keputusan penilaian menunjukkan bahawa LEF amat berkesan apabila komunikasi berada dalam jaringan asimetri. Dalam NoC 16×8, LEF malah mengatasi prestasi algoritma penghalaan penyesuaian dalam beberapa kes dan menyampaikan dari sekitar 4% sehingga sekitar 64.5% daya pemprosesan lebih tinggi daripada O1TURN. Keputusan kami juga menunjukkan bahawa kaedah pengelakan kebuntuan yang dicadangkan membantu meningkatkan prestasi LEF dengan ketara dan boleh digunakan untuk meningkatkan prestasi O1TURN. Kami juga memeriksa LEF dalam NoC berskala besar dengan beribu-ribu nod. Keputusan kami menunjukkan bahawa, apabila saiz NoC meningkat, prestasi algoritma penghalaan menjadi lebih kuat dipengaruhi oleh dasar peruntukan sumber dalam rangkaian dan kesannya adalah berbeza untuk setiap algoritma. Ini terbukti dengan keputusan NoC skala pertengahan dengan sekitar 100 nod tidak boleh digunakan secara langsung pada NoC berskala besar.
Thiem Van CHU
Tokyo Institute of Technology
Kenji KISE
Tokyo Institute of Technology
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Salinan
Thiem Van CHU, Kenji KISE, "LEF: An Effective Routing Algorithm for Two-Dimensional Meshes" in IEICE TRANSACTIONS on Information,
vol. E102-D, no. 10, pp. 1925-1941, October 2019, doi: 10.1587/transinf.2019EDP7019.
Abstract: We design a new oblivious routing algorithm for two-dimensional mesh-based Networks-on-Chip (NoCs) called LEF (Long Edge First) which offers high throughput with low design complexity. LEF's basic idea comes from conventional wisdom in choosing the appropriate dimension-order routing (DOR) algorithm for supercomputers with asymmetric mesh or torus interconnects: routing longest dimensions first provides better performance than other strategies. In LEF, we combine the XY DOR and the YX DOR. When routing a packet, which DOR algorithm is chosen depends on the relative position between the source node and the destination node. Decisions of selecting the appropriate DOR algorithm are not fixed to the network shape but instead made on a per-packet basis. We also propose an efficient deadlock avoidance method for LEF in which the use of virtual channels is more flexible than in the conventional method. We evaluate LEF against O1TURN, another effective oblivious routing algorithm, and a minimal adaptive routing algorithm based on the odd-even turn model. The evaluation results show that LEF is particularly effective when the communication is within an asymmetric mesh. In a 16×8 NoC, LEF even outperforms the adaptive routing algorithm in some cases and delivers from around 4% up to around 64.5% higher throughput than O1TURN. Our results also show that the proposed deadlock avoidance method helps to improve LEF's performance significantly and can be used to improve O1TURN's performance. We also examine LEF in large-scale NoCs with thousands of nodes. Our results show that, as the NoC size increases, the performance of the routing algorithms becomes more strongly influenced by the resource allocation policy in the network and the effect is different for each algorithm. This is evident in that results of middle-scale NoCs with around 100 nodes cannot be applied directly to large-scale NoCs.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2019EDP7019/_p
Salinan
@ARTICLE{e102-d_10_1925,
author={Thiem Van CHU, Kenji KISE, },
journal={IEICE TRANSACTIONS on Information},
title={LEF: An Effective Routing Algorithm for Two-Dimensional Meshes},
year={2019},
volume={E102-D},
number={10},
pages={1925-1941},
abstract={We design a new oblivious routing algorithm for two-dimensional mesh-based Networks-on-Chip (NoCs) called LEF (Long Edge First) which offers high throughput with low design complexity. LEF's basic idea comes from conventional wisdom in choosing the appropriate dimension-order routing (DOR) algorithm for supercomputers with asymmetric mesh or torus interconnects: routing longest dimensions first provides better performance than other strategies. In LEF, we combine the XY DOR and the YX DOR. When routing a packet, which DOR algorithm is chosen depends on the relative position between the source node and the destination node. Decisions of selecting the appropriate DOR algorithm are not fixed to the network shape but instead made on a per-packet basis. We also propose an efficient deadlock avoidance method for LEF in which the use of virtual channels is more flexible than in the conventional method. We evaluate LEF against O1TURN, another effective oblivious routing algorithm, and a minimal adaptive routing algorithm based on the odd-even turn model. The evaluation results show that LEF is particularly effective when the communication is within an asymmetric mesh. In a 16×8 NoC, LEF even outperforms the adaptive routing algorithm in some cases and delivers from around 4% up to around 64.5% higher throughput than O1TURN. Our results also show that the proposed deadlock avoidance method helps to improve LEF's performance significantly and can be used to improve O1TURN's performance. We also examine LEF in large-scale NoCs with thousands of nodes. Our results show that, as the NoC size increases, the performance of the routing algorithms becomes more strongly influenced by the resource allocation policy in the network and the effect is different for each algorithm. This is evident in that results of middle-scale NoCs with around 100 nodes cannot be applied directly to large-scale NoCs.},
keywords={},
doi={10.1587/transinf.2019EDP7019},
ISSN={1745-1361},
month={October},}
Salinan
TY - JOUR
TI - LEF: An Effective Routing Algorithm for Two-Dimensional Meshes
T2 - IEICE TRANSACTIONS on Information
SP - 1925
EP - 1941
AU - Thiem Van CHU
AU - Kenji KISE
PY - 2019
DO - 10.1587/transinf.2019EDP7019
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E102-D
IS - 10
JA - IEICE TRANSACTIONS on Information
Y1 - October 2019
AB - We design a new oblivious routing algorithm for two-dimensional mesh-based Networks-on-Chip (NoCs) called LEF (Long Edge First) which offers high throughput with low design complexity. LEF's basic idea comes from conventional wisdom in choosing the appropriate dimension-order routing (DOR) algorithm for supercomputers with asymmetric mesh or torus interconnects: routing longest dimensions first provides better performance than other strategies. In LEF, we combine the XY DOR and the YX DOR. When routing a packet, which DOR algorithm is chosen depends on the relative position between the source node and the destination node. Decisions of selecting the appropriate DOR algorithm are not fixed to the network shape but instead made on a per-packet basis. We also propose an efficient deadlock avoidance method for LEF in which the use of virtual channels is more flexible than in the conventional method. We evaluate LEF against O1TURN, another effective oblivious routing algorithm, and a minimal adaptive routing algorithm based on the odd-even turn model. The evaluation results show that LEF is particularly effective when the communication is within an asymmetric mesh. In a 16×8 NoC, LEF even outperforms the adaptive routing algorithm in some cases and delivers from around 4% up to around 64.5% higher throughput than O1TURN. Our results also show that the proposed deadlock avoidance method helps to improve LEF's performance significantly and can be used to improve O1TURN's performance. We also examine LEF in large-scale NoCs with thousands of nodes. Our results show that, as the NoC size increases, the performance of the routing algorithms becomes more strongly influenced by the resource allocation policy in the network and the effect is different for each algorithm. This is evident in that results of middle-scale NoCs with around 100 nodes cannot be applied directly to large-scale NoCs.
ER -