|
Authors: | Christian Plessl, Marco Platzner |
Group: | Computer Engineering |
Type: | Article |
Title: | Instance-Specific Accelerators for Minimum Covering |
Year: | 2003 |
Month: | September |
Pub-Key: | plessl03_jsuper |
Journal: | The Journal of Supercomputing |
Volume: | 26 |
Number: | 2 |
Pages: | 109-129 |
Keywords: | REC |
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. |
Resources: | [BibTeX] |