実行時データ依存解析によるループ階層構造に着目した並列性抽出

• Item type: SIG Technical Reports(1)
• 公開日: 2009-07-28
• タイトル: 実行時データ依存解析によるループ階層構造に着目した並列性抽出
• タイトル / 言語: en
• タイトル: Extracting parallelism in nested loop structures using run-time data dependency analysis
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 最適化
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 北陸先端科学技術大学院大学情報科学センター
• 著者所属: 慶應義塾大学
• 著者所属(英): en
• 著者所属(英): Center for Information Science, Japan Advanced Institute of Science and Technology
• 著者所属(英): en
• 著者所属(英): Keio University
• 著者名: 佐藤, 幸紀; 中村, 維男
• 著者名(英): Yukinori, Sato; Tadao, Nakamura
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 大規模・複雑化するアプリケーションを高度に並列化することを目的として、既存の逐次コードをマルチコアプロセッサ上でトランザクションメモリあるいはスレッドレベル投機実行を用いて逐次的な実行結果を保証しつつ並列に動作させるというランタイム自動並列化が注目を集めている。このランタイム自動並列化を実現するためには発見的で解空間の広い並列化対象から的確に並列化候補を選択する必要がある。本論文では、実行時プロファイリング技術を用いてバイナリコード実行時にループ領域毎のデータ依存関係を調べ、並列性を抽出する手法を提案する。提案する手法は、ループ階層構造を利用し参照した全てのメモリアドレスについて依存関係を把握するために必要な情報を効率的に記録する。評価環境を構築し評価を行った結果、ループ領域に着目したデータ依存解析はデータ依存関係を効率的に把握する上で有効であること、さらに、潜在的な DOALL ループを検出できることを確認した。加えて、評価対象を構築する上で利用するコンパイラや命令セットの構成を変化させて評価を行った結果、抽出される潜在的な DOALL ループは利用するコンパイラや命令セットと密接に関係があることがわかった。
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Run-time parallelization based on transactional memory or thread-level speculation is one of techniques to realize highly parallelized processing while guaranteeing the same results as sequential execution. To realize effective run-time parallelization, we have to seek appropriate code regions for parallelization in a program. In this paper, we propose a method of data dependence analysis, which focuses on using loop regions in binary code and captures dynamic behavior of control flows and memory references effectively using dynamic binary instrumentation technique. We implement our data dependence analysis scheme and evaluated it. The results show that our scheme using loop region information can dramatically reduce the number of detected data dependencies compared with the conventional address based scheme. The results also show that potential DOALL loops can be extracted using our scheme and whether they can extract or not is strongly related to the ISA of the CPU and compiler we use.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN10096105
• 書誌情報: 研究報告計算機アーキテクチャ（ARC）; 巻 2009-ARC-184, 号 8, p. 1-8, 発行日 2009-07-28
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会