--- _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' ...