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

• Item type: Trans(1)
• 公開日: 1999-02-15
• タイトル: 明示的なタスク配置指定が可能な遅延タスク生成に基づく動的負荷分散方法
• タイトル / 言語: en
• タイトル: Enabling Explicit Task Placement on Lazy Task Creation
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 通常論文
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: 東京大学大学院理学系研究科情報科学専攻
• 著者所属: 東京大学大学院理学系研究科情報科学専攻
• 著者所属: 東京大学大学院理学系研究科情報科学専攻
• 著者所属: 東京大学大学院理学系研究科情報科学専攻
• 著者所属(英): en
• 著者所属(英): Department of Information Science, Graduate School of Science, University of Tokyo
• 著者所属(英): en
• 著者所属(英): Department of Information Science, Graduate School of Science, University of Tokyo
• 著者所属(英): en
• 著者所属(英): Department of Information Science, Graduate School of Science, University of Tokyo
• 著者所属(英): en
• 著者所属(英): Department of Information Science, Graduate School of Science, University of Tokyo
• 著者名: 外山, 純生; 大山恵弘; 田浦, 健次朗; 米澤, 明憲
• 著者名(英): Sumio, Toyama; Yoshihiro, Oyama; Kenji, Taura; Akinori, Yonezawa
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 本論文では 遅延タスク生成(Lazy Task Creation 以下LTC)による動的負荷分散を行う言語上に 明示的に計算位置を指定できる機構を導入する. LTCは共有メモリ並列計算機上の 効率的なタスクスケジューラとして知られており 主な利点は空間使用量が小さいこと および オーバヘッドが少ないことである. しかし メモリアクセスコストが一様でない場合 しばしば データの配置によってタスクの配置を決める必要が生ずる. このような環境では 任意の遊休状態のプロセッサが任意のスレッドを実行する単純なLTC方式では不十分である. この論文では 明示的なタスク位置指定プリミティブを LTCに基くスケジューラに導入する際の問題点を述べ LTCの利点を失わずに それを実装する方法を示す. 我々の実装では プロセッサがタスク位置を指定したタスク生成を行ったときに 生成されたタスクだけでなく そのプロセッサ内のタスクスタック中の全てのタスクを 指定されたプロセッサに移動する. 指定されたプロセッサは移動したタスクを直ちに実行し そのプロセッサ内のタスクスタック中のタスクを 全て元のプロセッサに返す. このスタック交換がどのようにLTCの利点を保ったまま 明示的なタスク配置の合理的なセマンティクスを実現しているかを示す. 我々は 明示的なタスク位置指定プリミティブを 並列オブジェクト指向言語Schematicに実装し 分散共有メモリ計算機Origin 2000にて性能評価を行った. その結果(1)そのプリミティブを加えたことによるオーバヘッドは2-10%に抑えられ (2)2次キャッシュに入りきらない程巨大なデータをアクセスするプログラムにおいて 15-18%の速度向上がみられた.
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: 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%.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11464814
• 書誌情報: 情報処理学会論文誌プログラミング（PRO）; 巻 40, 号 SIG01(PRO2), p. 1-12, 発行日 1999-02-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7802
• 出版者 / 言語: ja
• 出版者: 情報処理学会