SIMD型計算機向けループ自動並列化手法

• Item type: SIG Technical Reports(1)
• 公開日: 2010-07-27
• タイトル: SIMD型計算機向けループ自動並列化手法
• タイトル / 言語: en
• タイトル: Auto Loop Parallelization for SIMD Architecture
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 並列言語処理系
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 東京大学
• 著者所属: IBM東京基礎研究所
• 著者所属: 東京大学
• 著者所属: 東京大学
• 著者所属(英): en
• 著者所属(英): The University of Tokyo
• 著者所属(英): en
• 著者所属(英): IBM Research - Tokyo
• 著者所属(英): en
• 著者所属(英): The University of Tokyo
• 著者所属(英): en
• 著者所属(英): The University of Tokyo
• 著者名: 中村, 晃一; 林崎, 弘成; 稲葉, 真理; 平木, 敬
• 著者名(英): Koichi, Nakamura; Hiroshige, Hayashizaki; Mary, Inaba; Kei, Hiraki
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: GPGPU などの SIMD 型並列計算機が，その費用対性能の高さから注目を集めている．この様な計算機の性能を引き出す為にはデータの配置・メモリ階層間の転送を最適化する事，加えて転送のオーバヘッドを演算・転送のパイプライン化により隠蔽する事が重要となる．しかし，ソフトウェア制御のスクラッチパッドメモリを含むメモリ階層の特性を把握し手作業で最適化する事は困難であり，これらを最適化し自動的に並列化を行う並列化コンパイラの必要性が高まっている．データ配置・転送最適化では Copy-candidate Selection 法が最も成功している手法であるが，既存研究では演算・転送のパイプライン並列性を考慮に入れていない為に，ハザードが発生し後のパイプライン化を阻害してしまうという問題がある．本稿で我々はプログラムの静的解析に基づき，データ配置・転送の最適化と演算・転送のパイプライン化を同時に行う手法: Modulo Scheduling for Copy-candidate Selection(MSCS) を提案する．これはデータ転送最適化手法とソフトウェアパイプライニング手法を混合整数計画法を用いて融合させることにより実現され，またその為に我々は Selective Data Dependence Graph(SDDG) というデータ構造を開発した．さらに東京大学に於いて開発された SIMD 型超並列計算機 GRAPE-DR を対象として我々が設計・開発を行った自動並列化コンパイラ NGC について，その実装と評価結果について述べる．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Today, SIMD parallel computers such as GPGPU are getting attentions because of its high cost-effectiveness. For extracting their potential performance, data mapping optimization and data transfer optimization are important. Pipelining of transfer operations and computations to conceal overheads of communications is also important for more advanced speedup. The problem is that it is difficult to optimize them by hand for complicated hierarchical memory structure which contains software-controlled scratch pad memories. Therefore, automatic parallelizing compilers which optimize data mapping and transfer for SIMD parallel computers are anticipated. Copy-candidate Selection methods have been most successful approach to optimize data mapping and transfer. However, since these approaches do not consider influences of pipeline execution, there is a possibility of occurrence of pipeline hazards. In this paper, we propose Modulo Scheduling for Copy-candidate Selection (MSCS) for obtaining optimal data mapping and transfer procedure under pipelined execution. To achieve the optimization, we combined Software pipelining method into Data transfer optimization method using mixed integer programming. We also propose Selective Data Dependence Graph (SDDG) which is a key structure for the formalization of MSCS. In this research, we developed auto parallelizing compiler NGC for GRAPE-DR, a massively parallel computer developed in The University of Tokyo. We will describe its implementation and evaluation results.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN10463942
• 書誌情報: 研究報告ハイパフォーマンスコンピューティング（HPC）; 巻 2010-HPC-126, 号 10, p. 1-8, 発行日 2010-07-27
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会