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 | English
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