PLuTo : An automatic parallelizer and locality optimizer for multicores

by syoyo

PLuTo – An automatic parallelizer and locality optimizer for multicores
http://www.cse.ohio-state.edu/~bondhugu/pluto/

複雑なループ処理でも、自動で処理をタイリング変換(メモリアクセスの局所化)したり、
自動で openmp ディレクティブを挿入して並列化してくれるというスグレモノツール.
すげー.

ツールはソース to ソースの変換を行うので、変換後のプログラムも普通の C コードのまま
扱うことができます.

たとえば、こんなコードが
(example/seidel/seidel.c より)


    /* pluto start (T,N) */
    for (t=0; t<=T-1; t++)  {
        for (i=1; i<=N-2; i++)  {
            for (j=1; j<=N-2; j++)  {
                a[i][j] = (a[i-1][j-1] + a[i-1][j] + a[i-1][j+1]
                        + a[i][j-1] + a[i][j] + a[i][j+1]
                        + a[i+1][j-1] + a[i+1][j] + a[i+1][j+1])/9.0;
            }
        }
    }
    /* pluto end */

pluto でタイリング変換すると


#define ceild(n,d)  ceil(((double)(n))/((double)(d)))
#define floord(n,d) floor(((double)(n))/((double)(d)))
#define max(x,y)    ((x) > (y)? (x) : (y))
#define min(x,y)    ((x) = 100);
    assert(N >= 100);
    int c1, c2, c3, c4, c5, c6;
    register int lbv, ubv;

#ifdef PERFCTR
    PERF_INIT;
#endif

    /* Generated from PLuTo-produced CLooG file by CLooG v0.14.1 64 bits in 0.03s. */
    for (c1=0;c1<=floord(T-1,10);c1++) {
        for (c2=max(ceild(10*c1-13,15),0);c2<=min(floord(T+N-3,15),floord(10*c1+N+7,15));c2++) {
            for (c3=max(max(max(max(ceild(10*c1+15*c2-13,15),ceild(15*c2-13,15)),0),ceild(20*c1-12,15)),ceild(30*c2-N-11,15));c3<=min(min(min(min(floord(2*T+2*N-6,15),floord(15*c2+T+N+11,15)),floord(20*c1+2*N+14,15)),floord(30*c2+N+25,15)),floord(10*c1+15*c2+N+21,15));c3++) {
                for (c4=max(max(max(max(ceild(15*c3-2*N+4,2),15*c2-N+2),0),-15*c2+15*c3-N-12),10*c1);c4<=min(min(min(min(10*c1+9,T-1),-15*c2+15*c3+13),15*c2+13),floord(15*c3+12,2));c4++) {
                    for (c5=max(max(15*c2,c4+1),15*c3-c4-N+2);c5<=min(min(c4+N-2,15*c3-c4+13),15*c2+14);c5++) {
                        for (c6=max(15*c3,c4+c5+1);c6<=min(15*c3+14,c4+c5+N-2);c6++) {
                            S1(c1,-c1+c2,-c1-c2+c3,c4,-c4+c5,-c4-c5+c6) ;
                        }
                    }
                }
            }
        }
    }
    /* End of CLooG code */

こんな感じになります.
なんだか出力されるコードはぐちゃぐちゃに見えますが、
メモリアクセスがタイリング(block 分割)されているので、
キャッシュヒット率が上がることが期待されます.
(ただ、アドレス算出のコストは上がるので、
ある程度大きなループでないと思ったほど効果が出ないかもしれません)

もう簡単なループ処理とかは、ツールで自動で最適化してくれる時代ですね.

pluto が想定しているプログラムは、行列計算などの配列処理が主になっているので、
レンダリングではどれくらい使い物になるかは分かりませんが、
テクスチャ処理のブロック化や一様グリッドのアクセスのブロック化などに使えそうでしょうか.

pluto のバックグラウンドで実行されている cloog や polylib で使われている、
Polyhedra(多胞体?)理論も参考になるので、いつか説明できればと思います.

Advertisements