深いパイプラインを持つプロセッサでは、条件分岐命令の実行コストが非常に大きくなります。これは条件分岐の実行によって、せっかくプリフェッチした命令をすべて破棄しなければならないからです。パイプライン・アーキテクチャの場合、パイプライン中の命令を破棄して再度実行を開始するには、パイプラインの深さ分だけのストール・サイクルが発生します。
そこで、このような問題を避けるためにアーキテクチャ上の工夫がされます。それらは条件分岐の方向の予測、分岐によるストールの抑制、分岐に替わる手段の提供などです。しかし高速な信号処理プログラムを実装したければ、ソフトウェアによる工夫も有効です。
DSPを活用するには条件分岐を減らすプログラム上の工夫が有効ですが、その前にプロセッサの設計者はこの問題をどう考えているか少し見てみましょう。
遅延分岐は初期のRISCで大々的に取り上げられた方法です。この方法は分岐命令に続く数命令を分岐のいかんにかかわらず必ず実行する方法で、分岐によるストールの数を減らします。実行される命令は「遅延スロットにある」といいます。
遅延分岐を使うと人間にとっては非常にわかりにくいコードになりがちですが、コンパイラにとってはそれほどの困難無しに使用できます。比較的多くのプロセッサで実装されています。
遅延分岐は分岐命令に続くパイプラインの長さ分までの命令を無条件実行することにより、原理的には分岐によるペナルティを抑制できます。しかし、バイナリ互換性やスケジューリングの現実性を天秤にかけて、実際には2命令程度の遅延スロットを持つのが現実的な解のようです。
Blackfinは遅延分岐を実装していません。ADSP-2191は実装しています。
分岐命令によるペナルティを不可避なものと考えても、そのペナルティの発生を減らすことが出来ればプログラムの実行速度を上げることができます。たとえば分岐をするかしないか事前に知ることが出来れば、プリフェッチの方向を変えることでストールの発生頻度を減らすことが出来ます。
分岐予測と呼ばれる技術は、過去の分岐パターンや履歴を元にある条件命令が次の実行で分岐するかどうかを予測します。原理そのものは簡単ですが、ハードウェア規模は決して小さくありません。分岐パターンか、あるいは分岐履歴のいずれであっても何らかのテーブルが必要になります。
Blackfinは分岐予測を行いません。
分岐予測が成功しても、プリフェッチした結果を実行できるとは限りません。なぜなら命令の実行によってレジスタの内容が変わると、それを取り消せないからです。これはパイプラインが一本しかない汎用プロセッサでは問題になりませんが、Out-Of-Order実行を行うスーパースケーラープロセッサでは大問題になります。なぜなら、このアーキテクチャは時間がかかる命令はおいて実行可能な命令からどんどん実行していくからです。分岐命令が実行可能になるまでぐずぐずしていられません。
投機的実行は、このような場合もえいや！と実行してしまう方式です。そのかわり、分岐条件が確定して分岐方向が決まると、場合によっては実行結果を取り消す必要があります。そのため、スーパースケーラー・アーキテクチャのレジスタ・リネーミングとあわせてレジスタ変更の取り消しができるように工夫されているのが普通です。
Blackfinはスーパースケーラーではありませんが、ロード命令を実行ユニットより前に行いますので、投機的ロードを可能にしています。
DSPは1MACを1命令で行うことが至上命令であったため、ほとんどのDSPがハードウェア・ループを実装しています。これはループをプリフェッチ・ユニットで実行することで、フェッチミスや条件判定のオーバーヘッドをなくす仕組みです。ループは実行前に繰り返し回数がわかっていなければなりませんが、小規模なハードウェアで極めて高速な実行が可能になります。
汎用プロセッサはこれに類する機構は使いません。代わりに条件分岐命令をスーパースケーラーでOut-Of-Order実行することで他の命令に隠してしまうという措置がとられます。この方式はプリフェッチ・ユニットに対するトリッキーな仕掛けが不要になりますが、ハードウェア規模は大きくなります。
Blackfinにはハードウェア・ループがあります。
DSPはx86系ほど力技には頼らず、どちらかと言うと命令セットの設計レベルでストールを抑止しようとします。たとえばハードウェア・ループなど最たるものでしょう。これはループ制御に一定の制限を課すことで小さなハードウェアで大きな効果を得ている非常に優れた機能です。
一方で、条件分岐のペナルティそのものの抑止は、やや捨て置かれた感があります。そこでこのペナルティを食らわないようにソフトウェアの工夫が必要になります。
長い論理式の評価は工夫をすることで条件分岐を減らすことが出来ます。たとえば論理式
( low <= x ) && ( x <= high )
はxが区間[low, high]に収まっているかどうか確認して、収まっていれば真を返します。この式を実装するとき、Blackfinの分岐命令を使うと
// 条件分岐版
cc = r0 <= r1; // r0 : low, r1 : x
if !cc jump done; // &&の左の結果が偽なら、式の結果も偽
cc = r1 <= r2; // r1 : x, r2 : high
done: // &&の左が真ならば、式の結果は&&の右の値と同じ
といった感じになります。これは一目みただけでわかりますが、条件分岐があるためにストールが発生します。そこで、以下のように論理演算だけで事を済ませるように書き換えれば、ストール無しで論理式の評価が出来ます。
// 論理演算版
cc = r0 <= r1; // r0 : low, r1 : x
v = cc; // cc をいったん退避
cc = r1 <= r2; // r1 : x, r2 : high
cc &= v; // 二つの論理値の論理積
この場合は常に一定時間で演算が終了しますし、平均的には最初の条件分岐を使うものより早く終了します。したがって、Blackfinを使う場合には論理演算を活用したほうがよいと言うことになります。
しかし、これについてはあらかじめ変数の値が求まっている時のことだという点に注意してください。論理式の中には
( low <= x ) && is_prime( x )
のように関数呼び出しを含むことがあります。このような場合は論理演算版よりも条件分岐版のほうがずっと高速になります。なぜなら&&の左側が偽のとき、&&の右側の関数は呼び出されず、そのぶん時間の節約になるからです。このように論理式の部分評価で全体の値がわかる場合、残りの評価を省略する方式を短絡評価と呼びます。この方法は実行時間の短縮につながり居ますが、&&の右側でグローバル変数の書き換えが発生する場合には、その変数が書き換えられるかどうかは左の値次第となり、コードの見通しが悪くなります。
短絡評価には速度向上と可読性の悪化という損得があるため、コンパイラの生成コードが短絡評価を行ってよいかどうかが言語仕様によって定められています。
C言語で動作しているプログラムをアセンブリプログラムに落とす場合には、この点に注意する必要があります。
分岐の方向に偏りがあるならば、プログラマがヒントとして出すことが出来ます。条件分岐命令の後ろに(bp)があるとき、Blackfinコアはプリフェッチを分岐先アドレスから開始します。これについてアセンブラではプログラマが明示的に指定できます。
C/C++言語の場合、VisualDSP++ 4.0では組み込み関数expected_true()およびexpected_false()を使ってプログラマが明示的に指定できるほか、PGO( Profiler Guided Optimization )を使用してコンパイラに最適方向を決めさせることも出来ます。
関数の中ほどに折れまがりがあるようなばあい、引数の値を使って場合わけをするのが正攻法です。しかし、中には関数の組み合わせで実現できるようなものもあります。たとえばクリッピング関数を考えて見ましょう。
f(x) = x <= b : b a <= x : a a < x < b : x
この関数を実装する場合、入力の場合わけのほかにも
// 16-Nビットの範囲にクリップする場合
r1.L = r0.L << N (s);
r2.L = r1.L >>> N;
// 任意の範囲にクリップする場合
r1.L = r0.L + r4.L (s); // 上側クリップ
r2.L = r1.L - r5.L (s); // 下側クリップ
r3.L = r2.L + r6.L; // 結果を整える
といった方法が考えられます。これらは可読性が悪いものの短い時間で終わります。しかもいずれもSIMD化が可能なうえに、ソフトウェア・パイプラインも適用できます。
可読性を犠牲にして速度を上げるというのは、工業的にはかなり古臭い話で、保守性などを考えると割が合いません。しかし、信号処理の場合苦労してでも処理サイクル数を削るに値する場合が多いため、こういった工夫が活躍する余地があります。
無論、趣味のプログラマにとっては胸がわくわくする話でもあります。
DSPのパワーを可能な限り搾り出したいのなら、分岐はしないに越したことはありません。分岐命令の実行回数と分岐頻度を考えながら、時には分岐しない工夫が考えられないか、あれこれ思いをめぐらせることになります。