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

IPSJ Web Site

Bibliographic Information

Other Title
  • テキオウ スパニングツリー オ モチイタ コウイキ メッセージパッシング システムヨウ ノ シュウゴウ ツウシン
  • Collective Operations for Wide-area Message Passing Systems Using Adaptive Spanning Trees

Search this article

Abstract

本稿では，広域メッセージパッシングシステム用に，動的に生成したスパニングツリーを用いて集合通信を行う手法を提案する．提案手法では，効率良くブロードキャスト・リダクションを行うために，実行時に測定した遅延・バンド幅を基にスパニングツリーを構築する．プロセッサは，自律的に遅延とバンド幅を測定することによって，短いメッセージ用の遅延を考慮したツリーと長いメッセージ用のバンド幅を考慮したツリーを構築する．これらのスパニングツリーは，実行中にプロセッサが参加・脱退してもトポロジの変化に適応し，効率良く集合通信を行い続けることを可能にする．3 つから4 つのクラスタに分散された128 から201 の実プロセッサにおいて，我々のブロードキャストの遅延は静的にトポロジを考慮した実装の2 倍以内に収まり，バンド幅は静的にトポロジを考慮した実装の82 パーセント出た．また，実行中に一部のプロセッサが参加または脱退した場合，我々のブロードキャストは，スパニングツリーが修復されるまで8 秒程度性能が落ちたが，この間も正常に完了した．

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.

Journal

Related Projects

See more

Keywords

Details 詳細情報について

Report a problem

Back to top