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
Pada masa kini, peningkatan pesat permintaan terhadap pengiraan berprestasi tinggi menyebabkan aktiviti penyelidikan yang bersemangat mengenai sistem selari secara besar-besaran. Rangkaian interkoneksi dalam sistem selari secara besar-besaran menghubungkan sejumlah besar elemen pemprosesan supaya mereka boleh bekerjasama untuk memproses tugas dengan berkomunikasi antara lain. Dengan mengenai elemen pemprosesan dan pautan antara sepasang elemen pemprosesan sebagai nod dan tepi, masing-masing, banyak masalah berkenaan dengan komunikasi dan/atau penghalaan dalam rangkaian interkoneksi boleh dikurangkan kepada masalah dalam teori graf. Untuk rangkaian interkoneksi sistem selari besar-besaran, banyak topologi telah dicadangkan setakat ini. Hypercube adalah topologi yang sangat popular dan ia mempunyai banyak varian. Bicube ialah topologi sedemikian dan ia boleh menyambung bilangan nod yang sama dengan darjah yang sama dengan hypercube manakala diameternya hampir separuh daripada hypercube. Di samping itu, bicube mengekalkan sifat nod-simetri. Oleh itu, kami menumpukan pada bicube dan mencadangkan algoritma yang memberikan laluan minimum atau terpendek antara pasangan nod yang sewenang-wenangnya. Kami memberikan bukti ketepatan algoritma dan menunjukkan pelaksanaannya.
Masaaki OKADA
Tokyo University of Agriculture and Technology
Keiichi KANEKO
Tokyo University of Agriculture and 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
Masaaki OKADA, Keiichi KANEKO, "Minimal Paths in a Bicube" in IEICE TRANSACTIONS on Information,
vol. E105-D, no. 8, pp. 1383-1392, August 2022, doi: 10.1587/transinf.2021EDP7235.
Abstract: Nowadays, a rapid increase of demand on high-performance computation causes the enthusiastic research activities regarding massively parallel systems. An interconnection network in a massively parallel system interconnects a huge number of processing elements so that they can cooperate to process tasks by communicating among others. By regarding a processing element and a link between a pair of processing elements as a node and an edge, respectively, many problems with respect to communication and/or routing in an interconnection network are reducible to the problems in the graph theory. For interconnection networks of the massively parallel systems, many topologies have been proposed so far. The hypercube is a very popular topology and it has many variants. The bicube is a such topology and it can interconnect the same number of nodes with the same degree as the hypercube while its diameter is almost half of that of the hypercube. In addition, the bicube keeps the node-symmetric property. Hence, we focus on the bicube and propose an algorithm that gives a minimal or shortest path between an arbitrary pair of nodes. We give a proof of correctness of the algorithm and demonstrate its execution.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2021EDP7235/_p
Salinan
@ARTICLE{e105-d_8_1383,
author={Masaaki OKADA, Keiichi KANEKO, },
journal={IEICE TRANSACTIONS on Information},
title={Minimal Paths in a Bicube},
year={2022},
volume={E105-D},
number={8},
pages={1383-1392},
abstract={Nowadays, a rapid increase of demand on high-performance computation causes the enthusiastic research activities regarding massively parallel systems. An interconnection network in a massively parallel system interconnects a huge number of processing elements so that they can cooperate to process tasks by communicating among others. By regarding a processing element and a link between a pair of processing elements as a node and an edge, respectively, many problems with respect to communication and/or routing in an interconnection network are reducible to the problems in the graph theory. For interconnection networks of the massively parallel systems, many topologies have been proposed so far. The hypercube is a very popular topology and it has many variants. The bicube is a such topology and it can interconnect the same number of nodes with the same degree as the hypercube while its diameter is almost half of that of the hypercube. In addition, the bicube keeps the node-symmetric property. Hence, we focus on the bicube and propose an algorithm that gives a minimal or shortest path between an arbitrary pair of nodes. We give a proof of correctness of the algorithm and demonstrate its execution.},
keywords={},
doi={10.1587/transinf.2021EDP7235},
ISSN={1745-1361},
month={August},}
Salinan
TY - JOUR
TI - Minimal Paths in a Bicube
T2 - IEICE TRANSACTIONS on Information
SP - 1383
EP - 1392
AU - Masaaki OKADA
AU - Keiichi KANEKO
PY - 2022
DO - 10.1587/transinf.2021EDP7235
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E105-D
IS - 8
JA - IEICE TRANSACTIONS on Information
Y1 - August 2022
AB - Nowadays, a rapid increase of demand on high-performance computation causes the enthusiastic research activities regarding massively parallel systems. An interconnection network in a massively parallel system interconnects a huge number of processing elements so that they can cooperate to process tasks by communicating among others. By regarding a processing element and a link between a pair of processing elements as a node and an edge, respectively, many problems with respect to communication and/or routing in an interconnection network are reducible to the problems in the graph theory. For interconnection networks of the massively parallel systems, many topologies have been proposed so far. The hypercube is a very popular topology and it has many variants. The bicube is a such topology and it can interconnect the same number of nodes with the same degree as the hypercube while its diameter is almost half of that of the hypercube. In addition, the bicube keeps the node-symmetric property. Hence, we focus on the bicube and propose an algorithm that gives a minimal or shortest path between an arbitrary pair of nodes. We give a proof of correctness of the algorithm and demonstrate its execution.
ER -