バックトラックに基づく負荷分散のT2K並列環境における評価

• Item type: SIG Technical Reports(1)
• 公開日: 2009-07-28
• タイトル: バックトラックに基づく負荷分散のT2K並列環境における評価
• タイトル / 言語: en
• タイトル: Evaluation of Backtracking-based Load Balancing on T2K Open Supercomputer
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 分散メモリ環境
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 京都大学学術情報メディアセンター
• 著者所属: 京都大学情報学研究科
• 著者所属: 京都大学情報学研究科
• 著者所属: 京都大学情報学研究科
• 著者所属(英): en
• 著者所属(英): Academic Center for Computing and Media Studies, Kyoto University
• 著者所属(英): en
• 著者所属(英): Graduate School of Informatics, Kyoto University
• 著者所属(英): en
• 著者所属(英): Graduate School of Informatics, Kyoto University
• 著者所属(英): en
• 著者所属(英): Graduate School of Informatics, Kyoto University
• 著者名: 平石, 拓; 八杉, 昌宏; 馬谷, 誠二; 湯淺, 太一
• 著者名(英): Tasuku, Hiraishi; Masahiro, Yasugi; Seiji, Umatani; Taiichi, Yuasa
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: マルチコアプロセッサ等を含む並列計算環境が一般的になるに伴い，並列計算向け高生産性言語はより重要になっている．Cilk 言語は共有メモリ環境におけるそのような言語の一つであり，不規則アプリケーションを含む多くのアプリケーションにおいて良好な負荷分散を実現する．すなわち，多数の論理スレッドを生成して最古優先のワークスティールを採用することで全ワーカを有効活用する．我々は，論理スレッドフリーなフレームワーク Tascell を提案している．Tascell は Cilk に対して生産性を損なうことなくより高い性能を実現し，クラスタを含む多様な並列計算環境にも対応する．Tascell ワーカは本物のタスクを生成 （spawn） するが，それは他のアイドルなワーカから要求されたときであり，一時的バックトラックによる最古のタスク生成可能状態の復元に基づく．本手法により，論理スレッド生成・管理コストを削減でき，作業空間に対する参照局所性の向上させることができる．さらに Tascell では，作業空間の遅延コピーを伴う，すっきりとした効率良いバックトラック探索アルゴリズムが実現できる．本論文では，各ノード計 16 コアを備えるクラスタである T2K オープンスーパーコンピュータにおける本手法の評価結果を報告する．評価において NUMA 環境におけるスケーラビリティの低下等の問題は見られたが，多くのアプリケーションにおいては，多コア環境においても充分な速度向上が得られることが確認できた．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: High-productivity languages for parallel computing become more important as parallel environments including multicores become more common. Cilk is such a language. It provides good load balancing for many applications including irregular ones; that is, it keeps all workers busy by creating plenty of “logical” threads and adopting the oldest-first work stealing strategy. This paper proposes a “logical thread”-free framework called Tascell, which achieves a higher performance than Cilk and supports a wider range of parallel environments including clusters without loss of productivity. A Tascell worker spawns a “real” task only when requested by another idle worker. The worker performs the spawning by temporarily “backtracking” and restoring its oldest task-spawnable state. Our approach eliminates the cost of spawning/managing logical threads, improves locality of reference for workspaces. Furthermore, Tascell enables elegant and highly-efficient backtrack search algorithms with delayed workspace copying. This paper reports performance evaluations of parallel computation on the T2K open supercomputer, a cluster that consists of computation nodes with four quad-core processors. Though there are some problems exposed such as limited scalability in NUMA environments, we can ensure that we can get sufficient scalability even in environments with computation nodes with large numbers of cores in many applications.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN10463942
• 書誌情報: 研究報告ハイパフォーマンスコンピューティング（HPC）; 巻 2009-HPC-121, 号 7, p. 1-11, 発行日 2009-07-28
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会