@article{2420,
abstract = { This paper presents the acceleration of minimum-cost covering problems by instance-specific hardware. First, we formulate the minimum-cost covering problem and discuss a branch \& bound algorithm to solve it. Then we describe instance-specific hardware architectures that implement branch \& bound in 3-valued logic and use reduction techniques similar to those found in software solvers. We further present prototypical accelerator implementations and a corresponding design tool flow. Our experiments reveal significant raw speedups up to five orders of magnitude for a set of smaller unate covering problems. Provided that hardware compilation times can be reduced, we conclude that instance-specific acceleration of hard minimum-cost covering problems will lead to substantial overall speedups. },
author = {Plessl, Christian and Platzner, Marco},
issn = {0920-8542},
journal = {Journal of Supercomputing},
keyword = {reconfigurable computing, instance-specific acceleration, minimum covering},
number = {2},
pages = {109--129},
publisher = {Kluwer Academic Publishers},
title = {{Instance-Specific Accelerators for Minimum Covering}},
doi = {10.1023/a:1024443416592},
volume = {26},
year = {2003},
}