リコンフィギャラブル・コンピューティングによる問題解法

概要

FPGAのように内部論理が再構成可能なハードウェアと論理合成技術を組み合わせ、ある特定の問題を解く際に、その問題ごとに専用回路を構成するというリコンフィギャラブル・コンピューティングの手法が可能となっている。我々は、充足可能性問題及び線形ブロック符号の復号器を例として取り上げ、本手法の有効性を検討している。

手法の特徴

本手法は、問題のクラスに対してではなくインスタンスごとにハードウェアを構成することを特徴としている。まず、個々の問題を解析し、その解法に適したハードウェア・アーキテクチャをSFLによる動作記述として生成する。その記述からPARTHENONにより論理回路を合成し、さらにFPGAにマッピングするためのデータへと変換する。その結果をダウンロードしたFPGAは与えられた問題を解くための専用マシンとなる。アーキテクチャを生成する段階でハードウェアの特性を活かしたアルゴリズムを組み込むことにより、更なる高速化が可能となる。

充足可能性問題 (SAT: Satisfiability Problem)

充足可能性問題とは2値変数からなる和積形論理式が真となる変数の値の割り当てが存在するかどうかを調べる問題であり、NP完全であることが証明されている。前年度までは、全ての変数に値を割り当てた上で枝刈りのアルゴリズムにより高速化を図っていた。今期は、必要に応じて変数に値を割り当てるアルゴリズム(図 1)を新たに考案して取り入れることにより、さらに効率的な探索ができることを確認した[1]。

図 1: SATにおける解の探索

線形ブロック符号の軟判定最尤復号器

通信の誤り訂正などに用いられる線形ブロック符号の性能評価を行う場合、長時間を要する軟判定最尤復号の計算機シミュレーションが必要となる。この処理の高速化を目指し、評価対象となる各符号に対応した復号回路をFPGAで実現する手法について検討した。ここでの復号の操作は、各符号に対応したトレリスダイアグラム上の最短経路問題に帰着できる。そこで、ダイアグラム上の複数の状態について並列に最短経路探索を行うことが可能な回路(図 2)を評価対象の符号ごとに自動合成する手法を考案し、性能評価を高速化できる見通しを得た[2]。

図 2: 符号対応の最尤復号回路のイメージ

今後の予定

取り扱う問題の一般化を行うと同時に、動的再構成可能なハードウェア・アーキテクチャとその設計自動化技術の確立に向けた研究に取り組んでいく。

参考文献

[1]: Suyama, T., Yokoo, M. and Sawada, H.: Solving Satisfiability Problems Using Logic Synthesis and Reconfigurable Hardware, Proc. of the 31st Annual Hawaii International Conference on System Sciences (HICSS-31), Vol. VII, pp. 179-186 (1998).
[2]: Nagano, H., Suyama, T. and Nagoya, A.: Soft Decision Maximum Likelihood Decoders for Binary Linear Block Codes Implemented on FPGAs, Proc. of International Symposium on Field Programmable Gate Arrays (FPGA '98), p. 261 (1998).

Contact: Takayuki Suyama; Email: suyama@cslab.kecl.ntt.co.jp (Satisfiability Problems)
Hidehisa Nagano; Email: nagano@cslab.kecl.ntt.co.jp (Soft Decision MLD)

Last modified: Wed Oct 14 14:56:34 1998