Instance-Specific Accelerators for Minimum Covering

C. Plessl, M. Platzner, Journal of Supercomputing 26 (2003) 109–129.

Download
No fulltext has been uploaded.
Journal Article
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.
Publishing Year
Journal Title
Journal of Supercomputing
Volume
26
Issue
2
Page
109-129
ISSN
LibreCat-ID

Cite this

Plessl C, Platzner M. Instance-Specific Accelerators for Minimum Covering. Journal of Supercomputing. 2003;26(2):109-129. doi:10.1023/a:1024443416592
Plessl, C., & Platzner, M. (2003). Instance-Specific Accelerators for Minimum Covering. Journal of Supercomputing, 26(2), 109–129. https://doi.org/10.1023/a:1024443416592
@article{Plessl_Platzner_2003, title={Instance-Specific Accelerators for Minimum Covering}, volume={26}, DOI={10.1023/a:1024443416592}, number={2}, journal={Journal of Supercomputing}, publisher={Kluwer Academic Publishers}, author={Plessl, Christian and Platzner, Marco}, year={2003}, pages={109–129} }
Plessl, Christian, and Marco Platzner. “Instance-Specific Accelerators for Minimum Covering.” Journal of Supercomputing 26, no. 2 (2003): 109–29. https://doi.org/10.1023/a:1024443416592.
C. Plessl and M. Platzner, “Instance-Specific Accelerators for Minimum Covering,” Journal of Supercomputing, vol. 26, no. 2, pp. 109–129, 2003.
Plessl, Christian, and Marco Platzner. “Instance-Specific Accelerators for Minimum Covering.” Journal of Supercomputing, vol. 26, no. 2, Kluwer Academic Publishers, 2003, pp. 109–29, doi:10.1023/a:1024443416592.

Export

Marked Publications

Open Data LibreCat

Search this title in

Google Scholar