明示的なタスク配置指定が可能な遅延タスク生成に基づく動的負荷分散方法

情報処理学会 Web Site 被引用文献1件 参考文献8件

書誌事項

タイトル別名
  • Enabling Explicit Task Placement on Lazy Task Creation
  • メイジテキ ナ タスク ハイチ シテイ ガ カノウ ナ チエン タスク セイセイ ニ モトヅク ドウテキ フカ ブンサン ホウホウ

この論文をさがす

説明

本論文では 遅延タスク生成(Lazy Task Creation 以下LTC)による動的負荷分散を行う言語上に 明示的に計算位置を指定できる機構を導入する. LTCは共有メモリ並列計算機上の 効率的なタスクスケジューラとして知られており 主な利点は空間使用量が小さいこと および オーバヘッドが少ないことである. しかし メモリアクセスコストが一様でない場合 しばしば データの配置によってタスクの配置を決める必要が生ずる. このような環境では 任意の遊休状態のプロセッサが任意のスレッドを実行する単純なLTC方式では不十分である. この論文では 明示的なタスク位置指定プリミティブを LTCに基くスケジューラに導入する際の問題点を述べ LTCの利点を失わずに それを実装する方法を示す. 我々の実装では プロセッサがタスク位置を指定したタスク生成を行ったときに 生成されたタスクだけでなく そのプロセッサ内のタスクスタック中の全てのタスクを 指定されたプロセッサに移動する. 指定されたプロセッサは移動したタスクを直ちに実行し そのプロセッサ内のタスクスタック中のタスクを 全て元のプロセッサに返す. このスタック交換がどのようにLTCの利点を保ったまま 明示的なタスク配置の合理的なセマンティクスを実現しているかを示す. 我々は 明示的なタスク位置指定プリミティブを 並列オブジェクト指向言語Schematicに実装し 分散共有メモリ計算機Origin 2000にて性能評価を行った. その結果(1)そのプリミティブを加えたことによるオーバヘッドは2-10%に抑えられ (2)2次キャッシュに入りきらない程巨大なデータをアクセスするプログラムにおいて 15-18%の速度向上がみられた.

This paper introduces an explicit task placement primitive to dynamic load balancing method based on Lazy Task Creation (LTC). LTC is known as an efficient task scheduler on shared-memory parallel computer, whose main advantages are its space efficiency and small overhead. When memory access cost is not uniform, however, we often need to place tasks according to data locations. On such environments, the simple LTC in which any idle processor steals any task will not work very well. In this paper, we discuss issues in introducing an explicit task placement primitive into LTC-based scheduler and show how to implement it without losing the benefits of LTC. In our implementation, when a processor encounters a task creation with an explicit placement, the processor not only migrates the thread just created, but also migrates all the tasks in its task stack to the target processor. The target processor immediately continues the migrated task and, in return, gives all the tasks in its task stack to the source processor. We show how does this "stack swapping" operation preserves all the benefits of LTC, while implementing a reasonable semantics of the explicit task placement primitive. We implemented the primitive in concurrent object-oriented language Schematic and evaluated it on Origin 2000, a distributed shared-memory computer. Experimental results indicate that (1) the primitive adds a small (2-10%) overhead to programs that do not use it, and (2) it improves programs that accesses large data that do not fit in the second-level cache by 15-18%.

収録刊行物

被引用文献 (1)*注記

もっと見る

参考文献 (8)*注記

もっと見る

キーワード

詳細情報 詳細情報について

問題の指摘

ページトップへ