Reconfigurable accelerators can improve process time on combinatorial probl
ems with fine-grained parallelism. Such problems contain a huge number of l
ogical operations (NOT, AND, and OR) that can evaluate simultaneously, a ch
aracteristic that varies considerably from problem to problem. Because of t
his variability, such combinatorial problems are approached using instance-
specific reconfiguration-hardware tailored to a specific algorithm and a sp
ecific set of input data.
Boolean satisfiability (SAT for short) is a common combinatorial problem th
at exhibits fine-grained parallelism. SAT varies considerably based on the
situation. Its solution is thus an ideal candidate for improvements based o
n instance-specific reconfiguration. In fact, simulations of an instance-sp
ecific accelerator show potential speed-ups by a factor of up to 140,000 in
execution time over the solution py a soft ware solver. The authors detail
the results of their prototype that leads to an order of magnitude speedup
in the execution of difficult satisfiability problems..