ソフトウェアパイプラインを考えてみる

2017/06/06 一部内容を訂正しました。

Out Of Orderのプロセッサが一般的になってしまってからあまり使わなくなった、ソフトウェアパイプラインを考えてみようと思います。
In-Orderプロセッサの最適化経験がある方はご存知のことなので、最後のほうまで飛ばしてください。

ベースとなる処理

まず、アフィン変換のような処理を見てみます。

各画素においてだいたい上から順に依存関係があるので、多少のことはコンパイラががんばってくれますが各演算のレイテンシが長いと、効率が悪く性能が出ません。

演算レイテンシを見える化した処理フロー

各演算のレイテンシを見える化すると下図のようになります。In-Orderプロセッサの場合、＜の箇所でパイプラインが遊んでしまいます。

一方Out Of Orderプロセッサの場合、次の画素やその次の画素の処理を先に実行するため、下図のようにレイテンシで空いてしまった隙間に依存しない命令が入り、効率が上がります。下図では、画素の違いを色分けしています。

In-Orderプロセッサでは、こういった賢いことはやってくれないので、上図のような最適化を自分で書かないといけません。ここで使うテクニックがソフトウェアパイプラインです。

ソフトウェアパイプライン化してみる

実際にソフトウェアパイプライン化したものが下図になります。

※下図では太字がループ外変数で、実際にはループ前にプロローグ処理が必要です。

この時のループボディだけを見てみましょう。

1. ある画素に対する座標計算
2.  一つ前の画素に対するアドレス計算と重み計算
3. 二つ前の画素に対する参照画素の読み出しとフィルタ処理

が実行されます。

図式化する都合で太字で示したループ外変数が複数の色を持っていますが、ループ内では不変なので、実体は1つです。
色分けしていなかったら3つの処理がどの行で実行されているのか全然わからないですね。

3つの処理を別々に書けたら、見やすくていいのに。。

そんな言語ありましたね。

アフィン変換のハードウェア記述

同様の処理をVerilogで記述すると下図になります。

(2017/06/05 追記)メモリアクセスは上記モジュール外でAXIなどのバスを使うことを想定しています。

参照画素の読み出しはキャッシュがないと性能がでないとか細かいところはさておき、ハードウェア記述言語だと、簡単に見やすく書けますね。

さて、改めてソフトウェアパイプラインとハードウェア記述を比べてみましょう。

• ループ内の命令の多くはループ内変数への代入で、Verilogのassign文に対応
• ループ外変数への代入は、レジスタへの代入に対応
• 1回のループはソフトウェアでは複数命令の複数サイクルですが、これはハードウェアの1サイクルに対応

記述は違いますが、意外と近いところもあるんじゃないでしょうか。

最後に

ここまで、ソフトウェア最適化の観点から話を進めてきましたが、ソフトウェア最適化を忘れて、ソフトウェアパイプラインの段数を増やしていき、積和演算も分割していき、どんどん細かくしていきましょう。そうすると、ハードウェアの1サイクル分の処理が少なくなり、レイテンシ5サイクルの積和演算命令のハードウェア実装というのも想像できるのではないでしょうか。

追記と修正

• ソフトウェアパイプライン化の図で、wx,wyがループ外変数として太字表示していたのにもかかわらずループ内で定義していた点を修正しました。
• Verilogコード内のTypo（w_offset13 -> w_offset3）を修正しました。
• Verilogコードのメモリアクセス方法について追記しました。

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください。