DDSの最適化

前回作ったDDSルーチンは余弦と正弦のデータ1組を作るために16サイクルかかります。このルーチンはまだストレートなコードですので、これを最適化してスピードアップを図ることにします。最適化にはソフトウェア・パイプラインを使います。これはDSP用の最適化としては王道です。詳しくは2191空挺団のなぜ最適化できるかを参照してください。

さて、ソフトウェア・パイプライン化を施すためのコードを見てみましょう。下のコードは前回のDDSで作ったプログラムのうち、ループの内側だけを取り出してコメントを削除したものです。そして命令の性質によって色分けをしています。

ソフトウェア・パイプライン化とはループ・ボディの重ね合わせによって実効ループ・ボディー長を短縮しようとするものです。重ね合わせは並列実行命令によりますから、どのような命令とどのような命令をパッキングして並列実行させるかは非常に重要な問題になります。

Blackfinの場合、並列化できるのは命令長32ビットのDSP演算命令と命令長16ビットのDAG命令です。そこで下では並列化可能な32ビット長演算命令を青、同じく16ビット長DAG命令を赤にしています。nopはどのような命令とでも並列化できます。

r2 = extract(r0, r6.L)(z);       // (a)
r3 = extract(r0, r7.L)(z);
r2 = r2 << 2;
r3 = r3 << 2;
i2 = r2;                         // (b)
i3 = r3;
r0 = r0 + r1(ns);
nop;
nop;
i2 += m0;                        // (c)
i3 += m1;
r4 = [i2] || r5 = [i3];
a1  =r4.L*r5.L,       a0  =r4.H*r5.L;
r6.H=(a1-=r4.H*r5.H), r6.L=(a0+=r4.L*r5.H);
w[i0++] = r6.H;
w[i1++] = r6.L || r6 = [p4]; 

このように色分けして睨んでみると、(a)の部分と(c)の部分を重ねることができそうです。そこで、なるべくうまくいきそうな位置に配置したのが下の表です。

こうして重ねてみると(a)(c)の部分はうまく重なりますが、(b)の部分がうまくありません。実のところ、このレジスタ間代入命令は逆立ちしても並列化できない種類の命令です。そこで涙をのんでこの部分は直列化します。具体的には双方にnopを挿入して位置を調整します。

調整した結果が以下の表になります。命令の重ね合わせに破綻はなく、nopを除去して左右の命令を結合させれば重ね合わせた部分をループ・ボディーとする新しいループを作ることができます。この段階で最適化の正当性を確認しておかなければなりません。簡単なチェック法としては以下の表に現れた新しいのループ・ボディーを国語教科書の容量で上から下に、右から左に読みます（記号α→β→γ→δの順）。その結果が最適化前のストレート・コードと同じならばまずは大丈夫です。なお、このチェックでは追加したnopを無視してもかまいません。

こうして作った最適化ループを以下に示します。なお、ループ回数は1回減ってn-1回になっています。

r2 = extract(r0, r6.L)(z);
r3 = extract(r0, r7.L)(z);
r2 = r2 << 2;
r3 = r3 << 2;
loop DDS lc0=p5;
i2 = r2;
i3 = r3;
r0 = r0 + r1(ns);

loop_begin DDS;
    r2 = extract(r0, r6.L)(z);      
    r3 = extract(r0, r7.L)(z)       || i2 += m0;
    r2 = r2 << 2                    || i3 += m1;
    r3 = r3 << 2                    || r4 = [i2]    || r5 = [i3];
    a1  =r4.L*r5.L, a0  =r4.H*r5.L; 
    r6.H=(a1-=r4.H*r5.H), r6.L=(a0+=r4.L*r5.H);     
    i2 = r2;
    i3 = r3;
    r0 = r0 + r1(ns)                || w[i0++] = r6.H;
    w[i1++] = r6.L                  || r6 = [p4];   
loop_end DDS;        

i2 += m0;
i3 += m1;
r4 = [i2] || r5 = [i3];
a1  =r4.L*r5.L, a0  =r4.H*r5.L;
r6.H=(a1-=r4.H*r5.H), r6.L=(a0+=r4.L*r5.H);
w[i0++] = r6.H;
w[i1++] = r6.L || r6 = [p4];

ループボディーのサイズは10行10サイクルです。最適化前が16行16サイクルでしたから実行時間は2/3になり、処理速度は50%向上しました。

下ごしらえと文書化が大事

上の例はコードを睨んでいれば最適化のヒントが浮かぶような書き方をしています。もちろんそんなことは無く、最適化前のコード自身、最適化に最適な形に前処理しています。その秘訣はひとえに並列化可能な命令になるよう気をつけることです。今回の例でいえば一番苦労したところはループボディーの先頭の位相分解部です。ここを並列化可能にするためにextract命令を使いたかったのですがレジスタが.Lレジスタが一つだけ足りませんでした。ループ・ボトムで毎回R6をロードしているのはこれを克服するためです。

また、機会があればいずれ説明しますが最適化前のループ内部の変数の有効範囲は、最適化後のループ・ボディー長を超えてはいけません。これは言葉でいえば面倒ですがごくあたりまえの制限です。

さらに最適化が終わるとプログラムは可読性が著しく低下しますので、最適化前のコードとともに説明文書を保管しておかなければ自分でも理解できなくなってしまいます。

ソフトウェア・パイプラインは劇的な効果があるのでこういった苦労も報われる点が救いといえば救いです。