Solving Problems using Reconfigurable Computing

Abstract

Reconfigurable computing that employs logic circuits specialized for each problem is feasible by combining logic synthesis technologies and reconfigurable hardware such as FPGAs. We have conducted satisfiability problems and maximum likelihood decoding (MLD) circuits to investigate the effectiveness of this approach.

Advantages of the Approach

The advantage of this approach is that hardware architecture is organized not for a class but for each instance of the problem. First, the given instance of the problem is analyzed, and a behavioral description specific to each instance is generated. Then, PARTHENON and FPGA Mapper generate mapping data that makes FPGAs specialized machine for solving the given instance. Another advantage is that when the architecture is generated, algorithms suitable for hardware are integrated in order to rapidly solve the problem.

Satisfiability Problems

A satisfiability problem can be specified as the question of whether there exists a variable assignment that makes a given logical expression true and proved to be NP-complete. Last year, our method assigned values to all variables, when the branch and bound algorithm was introduced. However, this year, we have developed a new algorithm such that variable values are partially assigned (Fig. 1), and we have confirmed the effectiveness of this approach [1].

Fig. 1: Search method for SAT solutions

Soft Decision MLD Circuits for Linear Block Codes

For the evaluation of linear block codes, time consuming computer simulations of soft decision MLD for them have been performed. In order to reduce the evaluation time, we have presented an automatic implementation method of code specific MLD circuits on FPGAs which accelerate simulations by utilizing the parallel computability of MLD [2]. MLD for a linear block code is resolved into the shortest path problem in its trellis diagram. The MLD circuit on FPGAs includes circuits which concurrently find the shortest paths to states in the diagram (Fig. 2).

Fig. 2: Shortest path search by code specific MLD circuit

Future Work

We plan to extend our research to the development of dynamically reconfigurable hardware architecture and the establishment of design methodologies for various applications.

References

[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:52:21 1998