適応スパニングツリーを用いた広域メッセージパッシングシステム用の集合通信

• Item type: Trans(1)
• 公開日: 2005-08-15
• タイトル: 適応スパニングツリーを用いた広域メッセージパッシングシステム用の集合通信
• タイトル / 言語: en
• タイトル: Collective Operations for Wide-area Message Passing Systems Using Adaptive Spanning Trees
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: ネットワーク
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: 東京大学大学院情報理工学系研究科電子情報学専攻
• 著者所属: 東京大学大学院情報理工学系研究科電子情報学専攻
• 著者所属: 東京大学大学院新領域創成科学研究科基盤情報学専攻
• 著者所属(英): en
• 著者所属(英): Department of Information and Communication Engineering Graduate School of Information Science and Engineering the University of Tokyo
• 著者所属(英): en
• 著者所属(英): Department of Information and Communication Engineering Graduate School of Information Science and Engineering the University of Tokyo
• 著者所属(英): en
• 著者所属(英): Department of Frontier Informatics Graduate School of Frontier Sciences the University of Tokyo
• 著者名: 斎藤, 秀雄; 田浦, 健次朗; 近山, 隆
• 著者名(英): Hideo, Saito; Kenjiro, Taura; Takashi, Chikayama
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 本稿では，広域メッセージパッシングシステム用に，動的に生成したスパニングツリーを用いて集合通信を行う手法を提案する．提案手法では，効率良くブロードキャスト・リダクションを行うために，実行時に測定した遅延・バンド幅を基にスパニングツリーを構築する．プロセッサは，自律的に遅延とバンド幅を測定することによって，短いメッセージ用の遅延を考慮したツリーと長いメッセージ用のバンド幅を考慮したツリーを構築する．これらのスパニングツリーは，実行中にプロセッサが参加・脱退してもトポロジの変化に適応し，効率良く集合通信を行い続けることを可能にする．3 つから4 つのクラスタに分散された128 から201 の実プロセッサにおいて，我々のブロードキャストの遅延は静的にトポロジを考慮した実装の2 倍以内に収まり，バンド幅は静的にトポロジを考慮した実装の82 パーセント出た．また，実行中に一部のプロセッサが参加または脱退した場合，我々のブロードキャストは，スパニングツリーが修復されるまで8 秒程度性能が落ちたが，この間も正常に完了した．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: We propose a method for wide-area message passing systems to perform collective operations using dynamically created spanning trees. In our proposal, broadcasts and reductions are performed efficiently using topology-aware spanning trees constructed at run-time; processors autonomously measure latency and bandwidth to create latency-aware trees for short messages and bandwidth-aware trees for long messages. Our spanning trees adapt to topology changes due to the joining or leaving of processors; when processors join or leave a computation, processors repair the spanning trees so that the effective execution of collective operations can continue. With 128 to 201 processors distributed over 3 to 4 clusters, the latency of our broadcast was within a factor 2 of a static topology-aware implementation, and our broadcast achieved 82 percent of the bandwidth of a static topology-aware implementation. Moreover, when some processors joined or left a computation, our broadcast temporarily performed poorly for about 8 seconds while the spanning trees adapted to the new topology, but completed successfully even during this time.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11833852
• 書誌情報: 情報処理学会論文誌コンピューティングシステム（ACS）; 巻 46, 号 SIG12(ACS11), p. 373-383, 発行日 2005-08-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7829
• 出版者 / 言語: ja
• 出版者: 情報処理学会