ヒストグラムカウンタ回路構成

図3.6はFPGAによるヒストグラムカウンタシステムの構成を示す．

図 3.6: FPGAによるヒストグラムカウンタシステムの構成．

ヒストグラムカウンタは図に示すように，データベースプロセッサ（DBP:Database Processor），

メモリ，FIC（Frequent Item Counter）IPコア (Intellectual Property Core)が配置され，一連の 動作を制御し，アイテムセットを格納し，結果を計数し，実行するFICタスクを実行する機能が 実装されている．FICコアモジュールに加えてFIC IPには，DMA（Direct Memory Access）と

データ転送速度を最大化し，DBPとそれぞれ通信するコントローラも含まれている．オフチップ メモリは完了したアイテムセットを格納し，オンチップメモリはデータバッファとして使用され，

オンチップメモリに最終的な計数結果を記憶する．転送速度とリソースのコストを最適化するた めと，キットの帯域幅の制限により，Avalon Busのインタフェースはすべて256ビットのデータ 幅に設定されている．従って，ビット/アイテムの構成に依存して，DMAは各動作クロックによっ て異なる数のアイテムを転送する事が出来る．

例えば，256ビット固定入力で，DMAはビット/アイテム構成がそれぞれ8ビット/アイテムお よび10ビット/アイテムである場合，FICコアモジュールにクロックごとに256/8＝32および

256/10＝25個の入力アイテムを提供する事が出来る．提案したFPGAシステムの動作は，メモ

リ内のアイテムセットの情報，すなわちアドレスおよびデータ長によって，DBPからFIC IPへ のコマンドから始まる．その後，IPコントローラを使用して，DBPはDMAを開始してデータ転 送プロセスを開始する．FICコアモジュールは，DMAの動作に基づくクラス分け結果をカウント アップし続ける．データ転送プロセスが完了すると， FICコアモジュールの計数結果がDBPに 返され，システム動作が完了する．

図3.7は同時に入力されるアイテムをカウントするためのFIC回路の詳細を示す．

図 3.7: FIC回路の詳細．

提案された設計は，完全にアイテム毎のアイテムの数を同時にカウント（FIC結果出力）する事 を目的としているため，カウンタアレイは図のように構成されている．図において，カウンタア レイはアイテム毎にResult-1からResult-2^N までの2^N カウンタを有し，N はビット/アイテムの 数である．システムはアイテムセット全体をスキャンしている間，すべてのアイテムタイプの結果

をカウントアップし続ける．従って，完了したFIC結果には単一のデータパスで回答する事が出 来る．前述のように，ビット/アイテムの数に応じて，1つの動作クロックでFICコアモジュール に転送出来る入力アイテムの数が異なる．従って，図に示すようにビット/アイテムの数に対応し て2進デコーダの数も変化する．例えば，6ビット/アイテムおよび7ビット/アイテムの設計オプ ションを備えた実装では，42（256/6）および36（256/7）バイナリデコーダが必要である．バイ ナリデコーダアレイの考えは，すべての入力アイテムに対して並列処理を達成する事であり，シ ステムの動作速度を最適化する．

アイテムを特定するバイナリデコーダのアレイは，図に示すようなバイナリ値のI_x,yマトリッ クスを生成する．x値は1から（256/N）まで，y値は1から2^N までである．各バイナリデコー ダは，対応する入力アイテムのバイナリ値である行列の列を生成する．バイナリ値の2^N ビットに は，値「1」を有するビットが1つだけあり，他の（2^N-1）ビットはゼロである．従って，I_x,y行 列の行に対して合計関数を実行する事によって，2^N の計数結果を計算する事が出来る．図に示す ように，集計タスクはアイテム毎の∑

モジュールによって行われる．アイテム毎にアイテム数の 合計の後，現在の計数結果は計数レジスタアレイに記憶された前の計数結果と加算される．操作 の終わりに，カウントレジスタ配列は最終カウント結果をDBPに返す．バイナリデコーダの設計 は，RAMで一般的に使用される一般的なアドレスデコーダの設計と同じである．

図3.8はバイナリデコーダによるアイテムクラス分類マトリックスの例を示す．

図 3.8: クラス分類マトリックスの例．

図に示すように，8ビットの入力A値に基づいて256ビットのI値が生成され，真理値表に示さ れるようにI値には1つのアサートされたビットしか存在しない．8対256バイナリデコーダの設 計は，3段階の組み合わせ論理を有する．

第1段階は，反転ビットを有する2つの入力ビット毎に構成されている．例えば，A₀，A¯₀，A₁， およびA¯1は， (A0 AND A1), (A0 AND A¯1), ( ¯A0 AND A1)，および( ¯A0 AND A¯1)の組み合わせ の値を作成する．

第2段階と第3段階は，それぞれ4つの異なる値と16の異なる値のグループをまとめて構成す る．アイテム毎の∑モジュールの設計には，ビット/アイテムシナリオのために多数の異なるバー ジョンのデザインがある．例えば，N値が8の場合，32×256I_x,y行列が作成され，256の∑

-32to6 モジュールが必要になる．次に，各∑

-32to6モジュールを32×256 I_x,y行列の行に適用して，32 個の個々の値のすべてを6ビット結果に合計する．6ビットのsum-resultは0〜31の値を保持する．

図3.9はヒストグラム加算器の構成を示す．

図 3.9: ヒストグラム加算器の構成．

他のビット/アイテム設計オプションについては，∑モジュールの異なるアーキテクチャが適 用されるが，それらはすべて図に示されているのと同じ設計思想である．∑

モジュールの設計は，

面積と処理時間の両方の性能を最適化する事を目指している．図に示すように，提案されたアー キテクチャは，全加算器（FA）とハーフ加算器（HA）のみを利用しており，クラス分類マトリッ クスで分類されたアイテム毎のアイテム数を全並列にカウントする．