Intel FPGAのアダーツリー

2つずつ足していけば良いというわけではない. <a name='more'></a> 『6. 推奨される HDL コーディング構文』[[1](#hdlcode)]にデバイスごとに加算器のつなぎ方を変えるべきということが書いてある. > <h6>アダー・ツリー</h6> >ターゲットにしたアルテラ・デバイスのアーキテクチャに合わせてア > ダー・ツリーを適切に構築すると、性能と集積度が大幅に改善される場 > 合があります。大きなアダー・ツリーを使用するアプリケーションの例 > として、有限インパルス応答（FIR）フィルタがあります。パイプライ > ン化されたバイナリまたはターナリ・アダー・ツリーを適切に使用する > と、結果の品質を大幅に改善できます。 > <h6>ロジック・エレメントに 4 入力 LUT を使用したアーキテクチャ</h6> > Stratix シリーズ、Cyclone シリーズ、APEX シリーズ、および FLEX シ > リーズのデバイスなどのアーキテクチャは、LE の標準組み合わせ構造と > して 4 入力 LUT を使用しています。 > デザインがパイプライン化可能な場合、4 入力ルックアップ・テーブル > を使用するデバイスにおいて 3 つの数値（A、B、C）を最も高速で加算 > する方法は、A+B を計算し、出力をラッチし、ラッチされた出力を C > に加算することです。A + B の加算には 1 レベルのロジック（1 つの LE > で 1 ビットが加算される）が必要なので、最大クロック速度で実行され > ます。これは必要なだけ拡張できます。 > <h6>アダプティブ・ロジック・エレメントに 6 入力 LUT を使用した > アーキテクチャ</h6> > > Stratix II アーキテクチャは基本ロジック構造に 6 入力 LUT を使用する > ため、Stratix II デバイスは上記の 4 入力 LUT を用いた例とは異なるコー > ディング・スタイルのほうが有利です。特に Stratix II デバイスの ALM > は、3 ビットを同時に加算できます。したがって、上記の例のツリーは > 深度が 2 レベルで、4 つの add-by-two の代わりに、2 つの add-by-three > で実現できることになります。 だそうな. つまりいつも二項加算でつなげれば良いというわけではないらしい. おそらくデバイスアーキテクチャを見ればわかるだろう. 私にはわからない. ということでCyclone VとMAX 10で一度に加算する数を変えて試してみた. 実装したのは64個の移動平均. 2項加算と3項, 4項, 6項の場合で実装した. 当然3項と6項の加算は64個であまりが出るので, 一部項の数が異なる. 下に2項の場合のみのソースコードを載せる. アダーツリーの実験用なので普通はこんなふうに移動平均しない. 直接形のFIRフィルタの加算はこんな感じになるだろう. 詳しくは以下のリポジトリを参照. ソースコードと実装結果を載せた. [https://github.com/toms74209200/ADDR_TREE](https://github.com/toms74209200/ADDR_TREE) ## 実装結果 下に実装した結果を抜粋して表にまとめた. Cyclone V(5CSEBA6U19C6)とMAX 10(10M08SAE144C8GES)で違うスピードグレードにしてしまったため, デバイス同士では比較できない. ### Cyclone V | | Logic utilization | Total registers | CLK | | ---- | ----------------- | --------------- | ------ | | 2 | 739 | 2146 | 306.28 | | 3 | 435 | 1623 | 309.02 | | 4 | 545 | 1623 | 309.02 | | 6 | 511 | 1292 | 201.01 | ### MAX 10 | | Logic utilization | Total registers | CLK | | ---- | ----------------- | --------------- | ------ | | 2 | 2,156 | 2146 | 269.69 | | 3 | 1,841 | 1623 | 177.87 | | 4 | 1,653 | 1408 | 178.22 | | 6 | 1,663 | 1292 | 127.52 | まず言えるのはCyclone Vでは3項の加算, MAX 10では4項の加算が最も優れているということだ. 何も考えずに2項にした場合, 動作周波数は問題ないがレジスタと（ここでは陽に表れていないが）レイテンシが増える. 対していっぺんに加算した6項では段数が減るため, レジスタとレイテンシは減るが動作周波数が大幅に下る. ## 参考 [1]<a name="hdlcode"></a> [6. 推奨される HDL コーディング構文 https://www.intel.co.jp/content/dam/altera-www/global/ja_JP/pdfs/literature/hb/qts/qts_qii51007_j.pdf](https://www.intel.co.jp/content/dam/altera-www/global/ja_JP/pdfs/literature/hb/qts/qts_qii51007_j.pdf)