命令レベル並列アーキテクチャのための大域的コードスケジューリング技法

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

書誌事項

タイトル別名
  • メイレイ レベル ヘイレツ アーキテクチャ ノ タメ ノ タイイキテキ コード
  • A Global Code Scheduling Technique for Instruction Level Parallel Architectures
  • 言語処理系

この論文をさがす

抄録

VLIW等の命令レベル並列アーキテクチャにおいて並列処理を効率的に行うためには コードスケジューリングにより プログラムの並列性を引き出すことが重要である.高い並列性を得るためには 大域的なスケジューリング範囲を持つことが必要であり この代表的な方法に トレーススケジューリング パーコレーションスケジューリングがある.しかしながら 前者は分岐に偏りがないプログラムに適用できないという問題点があり 後者にはコード移動の有効性を保証できない等の問題点がある.そこで 本論文では 拡張されたPDG (GPDG:Guarded PDG)を用いた新しい大域的なコードスケジューリング法を提案する.本手法は ソースプログラムをGPDGを用いた中間表現の形で表し これを逐次変形することによって最適化を行う.GPDGは分岐を含んだ大域的なコードを表現する能力を持っており これを用いることで大域的なスケジューリング範囲を持つことが可能になる.また GPDGの変形の際に グラフから得られる情報を用いることによって 分岐に偏りがないプログラムを効率良く並列化することができ コード移動の有効性も保証できる.スタンフォードベンチマークを用いた試験を行った結果 パーコレーションスケジューリングによる最適化コードの実行結果に比べて 最大で1.43倍の速度向上が得られることが分かった.

To achieve a good performance on instruction level parallel architectures such as VLIW, it is important to extract parallelly executable instructions from a program by code scheduling. To obtain highly parallel code, code schedulers must have the global scope of scheduling. Percolation Scheduling and Trace Scheduling are typical global code schedulers. However, the former cannot highly parallelize programs in which directions of branches are not biased, and the latter cannot assure the effectiveness of code transformations. We propose a new global code scheduling technique using extended PDG (GPGD: Guarded PDG). In this technique, source code is intermediately represented in GPDG, and it is successively transformed for optimizing. GPDG has ability to express a global code including branches. Therefore our technique can have global scheduling scope. When transformations are applied, by using information derived from GPDG, our technique can effectively parallelize programs in which directions of branches are not biased and can assure the effectiveness of code transformations. As a result, tests with Stanford Benchmark show that the code produced by our method was executed l.43 times faster at most than code optimized by Percolation Scheduling.

収録刊行物

被引用文献 (15)*注記

もっと見る

参考文献 (16)*注記

もっと見る

キーワード

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

問題の指摘

ページトップへ