---
_id: '2420'
abstract:
- lang: eng
text: ' 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:
- first_name: Christian
full_name: Plessl, Christian
id: '16153'
last_name: Plessl
orcid: 0000-0001-5728-9982
- first_name: Marco
full_name: Platzner, Marco
id: '398'
last_name: Platzner
citation:
ama: Plessl C, Platzner M. Instance-Specific Accelerators for Minimum Covering.
Journal of Supercomputing. 2003;26(2):109-129. doi:10.1023/a:1024443416592
apa: 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
bibtex: '@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} }'
chicago: '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.'
ieee: C. Plessl and M. Platzner, “Instance-Specific Accelerators for Minimum Covering,”
Journal of Supercomputing, vol. 26, no. 2, pp. 109–129, 2003.
mla: 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.
short: C. Plessl, M. Platzner, Journal of Supercomputing 26 (2003) 109–129.
date_created: 2018-04-17T15:10:00Z
date_updated: 2022-01-06T06:56:10Z
department:
- _id: '518'
- _id: '78'
doi: 10.1023/a:1024443416592
extern: '1'
intvolume: ' 26'
issue: '2'
keyword:
- reconfigurable computing
- instance-specific acceleration
- minimum covering
language:
- iso: eng
page: 109-129
publication: Journal of Supercomputing
publication_identifier:
issn:
- 0920-8542
publisher: Kluwer Academic Publishers
status: public
title: Instance-Specific Accelerators for Minimum Covering
type: journal_article
user_id: '398'
volume: 26
year: '2003'
...
---
_id: '2428'
abstract:
- lang: eng
text: ' In this paper we present instance-specific accelerators for minimum-cost
covering problems. We first define the covering problem and discuss a branch&bound
algorithm to solve it. Then we describe an instance-specific hardware architecture
that implements branch&bound in 3-valued logic and uses reduction techniques usually
found in software solvers. Results for small unate covering problems reveal significant
raw speedups. '
author:
- first_name: Christian
full_name: Plessl, Christian
id: '16153'
last_name: Plessl
orcid: 0000-0001-5728-9982
- first_name: Marco
full_name: Platzner, Marco
id: '398'
last_name: Platzner
citation:
ama: 'Plessl C, Platzner M. Instance-Specific Accelerators for Minimum Covering.
In: Proc. Int. Conf. on Engineering of Reconfigurable Systems and Algorithms
(ERSA). CSREA Press; 2001:85-91.'
apa: Plessl, C., & Platzner, M. (2001). Instance-Specific Accelerators for Minimum
Covering. In Proc. Int. Conf. on Engineering of Reconfigurable Systems and
Algorithms (ERSA) (pp. 85–91). CSREA Press.
bibtex: '@inproceedings{Plessl_Platzner_2001, title={Instance-Specific Accelerators
for Minimum Covering}, booktitle={Proc. Int. Conf. on Engineering of Reconfigurable
Systems and Algorithms (ERSA)}, publisher={CSREA Press}, author={Plessl, Christian
and Platzner, Marco}, year={2001}, pages={85–91} }'
chicago: Plessl, Christian, and Marco Platzner. “Instance-Specific Accelerators
for Minimum Covering.” In Proc. Int. Conf. on Engineering of Reconfigurable
Systems and Algorithms (ERSA), 85–91. CSREA Press, 2001.
ieee: C. Plessl and M. Platzner, “Instance-Specific Accelerators for Minimum Covering,”
in Proc. Int. Conf. on Engineering of Reconfigurable Systems and Algorithms
(ERSA), 2001, pp. 85–91.
mla: Plessl, Christian, and Marco Platzner. “Instance-Specific Accelerators for
Minimum Covering.” Proc. Int. Conf. on Engineering of Reconfigurable Systems
and Algorithms (ERSA), CSREA Press, 2001, pp. 85–91.
short: 'C. Plessl, M. Platzner, in: Proc. Int. Conf. on Engineering of Reconfigurable
Systems and Algorithms (ERSA), CSREA Press, 2001, pp. 85–91.'
date_created: 2018-04-17T15:39:17Z
date_updated: 2022-01-06T06:56:17Z
department:
- _id: '518'
- _id: '78'
keyword:
- minimum covering
- accelerator
- funding-sundance
page: 85-91
publication: Proc. Int. Conf. on Engineering of Reconfigurable Systems and Algorithms
(ERSA)
publisher: CSREA Press
status: public
title: Instance-Specific Accelerators for Minimum Covering
type: conference
user_id: '24135'
year: '2001'
...