自動並列化

自動並列化


自動並列化は、既存のプログラミング言語を対称に行うものと、
並列化しやすいように再設計されたカーネル言語に関して行うものの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

このWIKIを編集するにはパスワード入力が必要です

認証パスワード