最適化の効果

最適化をするときには効果を測定することを絶対に惜しんではいけません。特にパイプライン化したプロセッサの挙動は複雑であり、よかれと思って行った作業が却って速度を落とすことがあります。ADSP-2191の場合はディープ・パイプライン、VLIW、SIMDなどの要素がないために、他のDSPよりは挙動が単純です。それでもパイプライン・アーキテクチャーは時として予想のつかないふるまいをします。ですから、測定を惜しんではいけません。

測定

以下に今回作ったコードの計算部分を再掲します。(a)、(b)、(c)はそれぞれ最適化なし、デュアルロード使用、命令＋デュアルロード使用のコードであり、下に行くほど最適化を強力に施してあります。これらのコードの実行時間を調べてみましょう。

// (a) 最適化なし

fir:
    mr=0;                       // SUM=0
    dm(i0+=m0)=mx0;             // ▽
    cntr=TAPS;                  // TAPS-1回繰り返し
    do fir_loop until ce;
        mx0=dm(i0+=m0);         // ディレイラインのロード(古い物から新しい物へ)
        my0=dm(i6+=m5);         // 伝達関数のロード(後ろから前へ)
fir_loop:
        mr=mr+mx0*my0(ss);      // 積和
    mr=mr(rnd);                 // △
    rts;        // 49-52

// (b) デュアルロードによる最適化

fir:
    mr=0;                       // SUM=0
    dm(i0+=m0)=mx0;             // ▽
    cntr=TAPS;                  // TAPS-1回繰り返し
    do fir_loop until ce;
        mx0=dm(i0+=m0), my0=pm(i6+=m5);   // 伝達関数とサンプルのロード
fir_loop:
        mr=mr+mx0*my0(ss);      // 積和
    mr=mr(rnd);                 // △
    rts;        // 52-55, 42-44

// (c) 命令+デュアルロードによる最適化

fir:
    mr=0;                       // SUM=0
    dm(i0+=m0)=mx0;             // ▽
    mx0=dm(i0+=m0),my0=pm(i6+=m5);                        // プリロード

    cntr=TAPS-1;
    do fir_loop until ce;
fir_loop:
        mr=mr+mx0*my0(ss), mx0=dm(i0+=m0),my0=pm(i6+=m5); // 積和
    mr=mr+mx0*my0(rnd);         // △
    rts;                        // 測定のため、遅延分岐は使用しない。     

計測は実行サイクルを計るで紹介したEMU CYCLE COUNTERを使います。測定区間はプログラムコメントに▽と△を書いた区間です。区間の開始も終わりもしるしをつけた行を含むサイクル数を測定します。

評価

以下にその測定結果を表で表します。表中「プログラム」は上で示した(a), (b), (c)です。(b)は2種類の計測結果がありますが、これはインパルス応答hを配置するメモリーセクションによる速度差を測定するためです。DAGで説明しているようにADSP-2191はDMバスとPMのバスを使ったデュアル・ロードを行う場合、二つのロードが異なるメモリー・ブロックをアクセスするように調整しなければきちんとした性能を出せません。これを測定するために(b-2)ではdelayとhを別のメモリー・ブロックになるように配置しています。配置の方法は最適化で説明した方法と同じです。

「9tap」の欄が測定結果です。この数値はタップ数を9としてビルドしたプログラムのものであり、実測値から14を引いた真のサイクル数です。これだけではよくわかりませんのでタップ数10の時のものも測定し、そこからNタップフィルタのときのサイクル数を求めたものを「Ntap」の欄に書き込んでいます。

まず最初に(a)の結果を見ましょう。このプログラムはループの中に3命令ありますのでNタップのときのサイクル数が3Nで推移するのは納得できます。しかしオーバーヘッドの+8はやや大きすぎるように見えます。数えてみるとDO命令を含めたループ外命令は全部で4つあります。従って4サイクルがどこかで余計に消費されています。

さらに(b-1)を見てみると、デュアル・ロード命令を使っているにもかかわらず、9タップのときのサイクル数がシングル・ロードの時より増えていることがわかります。確かにデュアル・ロードといっても(b-1)はdelayとhを同じメモリーブロックに置いたため、アクセスが直列化されておりロード命令の実行に2サイクルかかってしまいます。が、それでもサイクルが増えるというのは納得がいきません。

実はADSP-2191のDO命令には短いループのときにオーバーヘッドが増大する性質があります。具体的に言うとループ本体の長さがパイプラインのステージ数より短い場合、ADSP-2191はパイプラインをフラッシュしてしまいます。私が理解する限り、5ステージ目にある命令デコーダはdo命令がショートループだと判断した時点で先行するステージをフラッシュするためにこのような挙動になるようです。いずれにせよパイプラインの挙動は難解です。特にDSPの場合、重要な命令の性能を落とさないようにパイプライン構造にいろいろ手を入れるために単純な動きはしません。

さて、次に進みましょう。(b-1)と(b-2)を見比べると1タップあたりのサイクル数が3から2に減少しています。これはdelayとhの配置ブロックを分けたためにアクセスのオーバーヘッドが解消したのが理由です。しかし、ここでも(b-2)でNとは独立なオーバーヘッドが11から10に減少するという不思議な動きがあります。単純に考えれば(b-2)は最初の一回だけデュアルロードと命令フェッチの衝突が発生するため、オーバーヘッドは増えるはずです。しかし、なぜか減っています。これは推察に過ぎませんが、おそらくDOループを終了するときにストールが発生しているのでしょう。シーケンサーはループボディーの近辺に到達すると、ループカウンターをデクリメントして終了条件をチェックし、プリフェッチ・アドレスを変更します。しかし、ループが短くなると、この作業を行う余裕がなくなります。多分、これが原因でストールしているのでしょう。

最後に、一番最適化した(c)を見てみます。このプログラムは目論見どおりNタップをNサイクル+αで処理します。しかしながら、オーバーヘッドはこれまでのどのプログラムよりも大きくなっています。ループの最適化の過程で前後にはみ出すコードが出てくるためある程度仕方のないことですが、それを除外してもループ外のオーバーヘッドは(c-2)より1サイクル増えています。

アルゴリズムの計算量を問題の大きさNの多項式で論じるとき、純粋なアルゴリズム論では多項式の中のもっとも大きな次数の項を論じます。例えば、3N²+2N+5という多項式では問題にされるのはN²の項だけです。これはNが大きくなったとき、次数の小さな項は無視できるからです。この理屈は我々のFIRフィルターの場合にも当てはまります。Nが大きくなればサイクル数が3N+xのコードは2N+yのコードよりも確実に遅くなります。

しかしながら、現実のプログラムの中にはタップ数の小さなフィルターも現れます。その場合も全体の性能に影響を及ぼさないような部位ならば問題ありません。しかし、性能の観点から無視できないのであれば、2、3のコードを書いてみてその性能をきちんと評価すべきです。アナログ・デバイセズはそのDSP製品の計算時間が決定論的であることを強調しますが、計算時間が決定論的であることと、計算時間が直感的にわかることは別の話です。時間的に厳しいプログラムであれば速度評価は避けて通れないのです。

まとめ

以上でFIRフィルターに関する説明を終わります。FIRフィルターは単純なアルゴリズムであり、単純なコードに落とすことができます。しかし、その裏にはDSPの真髄ともいえる技術の数々が横たわっています。これほど短いコードの中にかくもいろいろと詰まっているあたりが、DSPの面白さだと感じます。

次は⇒C++プログラムに組み込む