2026-05-20T17:26:58Z https://ipsj.ixsq.nii.ac.jp/oai

oai:ipsj.ixsq.nii.ac.jp:00069737 2025-01-21T23:48:01Z 934:1119:6067:6121

2次元Meshネットワーク・Torusネットワーク上での最適全対全通信アルゴリズム Optimal All-to-All Communication Algorithm on 2-dimensional Mesh Network and Torus Network 高上, 治之 矢崎, 俊志 安島, 雄一郎 清水, 俊幸 石畑, 宏明 Haruyuki, Takaue Syunji, Yazaki Yuichiro, Ajima Toshiyuki, Shimizu Hiroaki, Ishihata ネットワーク 本論文では，各ノードは同時に複数のメッセージを送受信可能なモデルを前提とした，2 次元 Mesh ネットワーク・Torus ネットワーク上での全対全通信アルゴリズムを提案する．提案するアルゴリズムでは，各ノードは，複数のメッセージを同時に送信する方式をとっており，Mesh ネットワークでは，同時に 2 つのメッセージを送信することにより，Torus ネットワークでは，同時に 4 つのメッセージを送信することによりネットワークのバイセクションバンド幅を最大限に引き出すようにスケジューリングしている．本方式での通信時間は，2 次元 Mesh ネットワーク・Torus ネットワーク上での理論的下限を達成していることを示す． In this paper, we present an optimal all-to-all communication algorithm for a 2D mesh/torus network. The proposed algorithm ensures full utilization of the network link bisection bandwidth without the need for split-phase operation, which are used in previously proposed algorithm, provided each node can transfer several messages concurrently. We show the proposed alogrithms acheives the theoretical lower bound time of all-to-all communicaiton in both a 2D mesh with two concurrent message transfers and a 2D torus with four concurrent message transfers. journal article 情報処理学会 2010-06-21 application/pdf 情報処理学会論文誌コンピューティングシステム（ACS） 2 3 88 98 1882-7829 AA11833852 https://ipsj.ixsq.nii.ac.jp/record/69737/files/IPSJ-TACS0302012.pdf jpn