CHAP.10 OPTIMIZING C FOR FPGA PEFORMANCE 滝本研究室 M1 井上聡前回からの流れ  トリプルDESアルゴリズムの提示８・９章でSWシミュレーションをFPGA上で検証  HDLと比較してそれほど良いわけではない   C言語のコードでは最適な結果が得られない HWコンパイルにおける対象は、従来のプロセッサと異なる  C言語は設計上，プロセッサ基準の構造で最適化   比較的単純なC言語プログラミングの手法を利用することで多様なアルゴリズムにおいて劇的な加速が見込める６・７章では，プログラミングの手法をC言語で書かれたプロセスの性能向上のために適用し，HWにコンパイルできることを学んだ  この章では，それらを直接HWに適用していく  10.1 性能に対するアルゴリズムの再考  9章では，従来のC言語の実装を基盤として，トリプル DES暗号化アルゴリズムを行った例を示した目的：組込みプロセッサにコンパイルされたC言語のコードを使用して，FPGAのHW実装のプロトタイプ作成方法を示す  結果：暗号化ブロック生成は1ブロック当たり191サイクル  クロック周波数に関しては，SW実装と比べて速い  現代のプロセッサで可能なクロック数を考えると満足とはいえない   性能向上のために，アルゴリズム自体を見直すどのようにして最初にインパルスCのプロセスが実装されたか  単純化するため，単体のDESに着目する  10.1  準備 64bit のブロックを２つの32bit の値に分割  初期のデータを各データに処理する  Block[0]~block[3] (32bit) Block[0]~block[7] (64bit) Block[4]~block[7] (32bit) 10.1  計算部分をマクロFで定義する拡大転置：32bit から48bitに拡大転置  鍵スケジュールと排他的論理和をとる  Spbox処理：48bit の配列を，再度32bit に圧縮  16個の鍵スケジュールに適用（暗・復号化の主な処理）  プロセス終了最後にいくつかの最終的な順列処理を行う  出力配列に格納  10.1  配列の２分割   1bit の処理は1クロック必要なHWロジックに変換可能ブロック配列のデータを読込: 8サイクル必要    1サイクルに１つの値しかメモリから読み込めないためメモリへのアクセス回数をへらすことが最適化の鍵マクロ F 基本的にはビット演算により処理が行われているが，配列へのアクセスが残っている  メモリアクセス： 8回（F-Sp）*16回（F を参照） = 128回   データの格納  読み込みと同様、８サイクル必要 10.1 まとめ  最適化されていない元の性能 Vertex II(生成されたHW)で 3000スライス  MicroBlaze(SW)に比べて、10.6倍高速化   続く節ではさらなる最適化を行って、クロックサイクルとスライス数(=論理回路のサイズ)について効率化を行う 10.2 改善１：ループ導入によりサイズを縮小  マクロ Fを用いた、核となる16ステップの繰り返し SW: ループを使うより少し高速化  HW: 16回複製を行うことになり、大型化   ループを利用 for(i=0; i<16;i++({ F(left, right, Ks[i]; i++; F(right, left, Ks[i]); } 10.2  ループを利用したものを論理合成   およそ1500スライス評価ループにより余分な遅延も発生するが、9.4倍高速化  少しの性能低下で、HWの面積が半分になった   まとめループと、ループを除去したものを比較して評価することにより、遅延とスライス数のバランスを取ることができる  10.5節では異なる点からこのような性能比較を行う  10.3 改善２：配列の分割  HW実装による最も重要な利点   複数のメモリに同時にアクセスできるメモリへのアクセス SW バストランザクションにつき１つのメモリのみアクセス可能  HW 任意の構成で設計可能複数メモリに独立して接続することができる  例：配列B,C の値を取得して配列Aに格納 10.3  今回例にとっているDESの場合 Spbox, Ks の配列が存在  それぞれ別々のメモリに割り当てられるが、同一メモリに複数アクセスすることにより多くのサイクルが必要   これらは分割可能 Spbox：多次元配列であり、行の添字は定数  Ks : 多次元配列であり、列の添字は定数   メモリアクセスの改善 Spbox: Spbox[0~7]の８つ  Ks: Ks[i][0,1],Ks[i+1][0,1]の４つ  同時アクセスにより各１回に短縮（計２回） 10.3 まとめ  わずかな変更により各配列のアクセス回数減少全体のサイクル数が減少  生成されるHWサイズが縮小  SW実装に比べて 19.5倍の高速化（←10.2の２倍）   SpboxやKsの次元が減ったことによりアドレス計算が除去され、HWサイズがさらに縮小 10.4に続く 10.3（修正前）  今回例にとっているDESの場合 Spbox, Ks の配列が存在  それぞれ別々のメモリに割り当てられるが、同一メモリに複数アクセスすることにより多くのサイクルが必要   これらは分割可能 Spbox：多次元配列であり、行の添字は定数  Ks : 多次元配列であり、列の添字は定数   アクセス回数の比較 Spbox: 8回 → ２回  Ks : 4回 → ２回 