Reconfiguration of the Backtrace Algorithm Implemented in HW to Speed up a Vector Generation Process

Recently, a method for converting combinational circuits into a corresponding backward-determining structure was proposed in order to implement the backtrace algorithm into hardware. A new proposed method, presented in this paper, extends the backward-determining structure by conflict-driven dynamic reconfiguration. Two variants of such reconfiguration are discussed and the experimental data has been obtained for the ISCAS´85 benchmarks. For these benchmarks, the area overhead and operational complexities of converted circuits and their reconfigurable variants are shown. A conclusion of the experiments is that the asymptotical complexity of the area overhead is polynomial for converted circuits without as well as with reconfiguration. In comparison with the backtrace algorithm without reconfiguration, the average growth of an area overhead is about 112 % but the average speed up is about 12 %