自動並列化
自動並列化
自動並列化は、既存のプログラミング言語を対称に行うものと、
並列化しやすいように再設計されたカーネル言語に関して行うものの2種類がある。
既存のプログラミング言語の場合、主にFortranやC/C++が対称。
(1) 命令レベル並列化
(2) ベクトル化
(3) ループレベル並列化
(4) 粗粒度並列化
最近だとJavaやHaskell(GHC)も行っている。
JavaはFork/Joinフレームワークの提供や、StreamAPIを使用するとマルチスレッディングでコアを使い切ってくれる。
HaskellはLLVMをバックエンドに使用して、自動的にベクトル化したコードを出力する。
GHC向けにintelがコミットしているらしい。その辺はshelarcyさんが詳しい。
カーネル言語に関しては、低レイヤー向けと、高レイヤー向けがある。
(1) CUDAは高レイヤー向けでGPGPUのみ。
(2) OpenCLなどのCL系は低レイヤー向けで、GPGPUやCPUのヘテロ。
(3) ISPCは低レイヤー向けでCPUのみ。
実装
ベクトル化の実装
llvm-3.1に新規追加された、自動ベクトル化(BB内)
Autovectorization with LLVM
Polly - Polyhedral optimization in LLVM
Whole-Function Vectorization
LLVM3.3には現在3種類の自動ベクトル化が入っている。
BBVectorize
LoopVectorize
SLPVectorize(Superword Level Parallel)
ベクトル化ガイド
SPMD最適化
LLVMのopt相当を改造し、BB単位でgather/scatterでSPMD化する。らしい。
BB単位で動作するLLVMのPassが複数実装されている。
llvmでのループ並列化への取り組み
粗粒度並列化の実装
coinsでの並列化処理の説明
以下ドキュメントを読んだ勝手な予測。。
HIRを並列性抽出しやすい中間表現に変換し、
その中間表現を解析して、並列性を抽出した後、
並列プログラムに変換してあげる。
中間表現は、マクロタスクによって構成されたマクロタスクグラフで表現する。
マクロタスクは、親子関係をもち、階層化されている。
マクロタスクの主な粒度は、基本ブロック、ループ、サブルーチンからなる。
よってマクロタスクグラフは、DAG形式であり、マクロタスク単位で並列化する。
マクロタスクの親子は、サブルーチンのみ。
ループを内包したマクロタスクは、、どうすんだろ。OpenMPでループ並列化の対象として別フェーズで解析?
再帰関数は、みなかったことにする?
マクロタスクを構成した後、マクロタスクのメモリエリアを解析し、以下の4つに分類する。
use
exposed use
modify
definitely defined
解析結果を参照し、マクロタスクを自動で並列化するのか?
並列化したマクロタスクはswitchのcaseで並列に処理する。
出力結果は、coinsの書籍にちらっと掲載されていたように思う。
- 最終更新:2013-10-21 22:42:45