Custom computing machines for the set covering problem

Author

Plessl, Christian ; Platzner, Marco

Author_Institution

Comput. Eng. & Networks Lab., Swiss Fed. Inst. of Technol., Switzerland

fYear

2002

fDate

2002

Firstpage

163

Lastpage

172

Abstract

We present instance-specific custom computing machines for the set covering problem. Four accelerator architectures are developed that implement branch & bound in 3-valued logic and many of the deduction techniques found in software solvers. We use set covering benchmarks from two-level logic minimization and Steiner triple systems to derive and discuss experimental results. The resulting raw speedups are in the order of four magnitudes on average. Finally, we propose a hybrid solver architecture that combines the raw speed of instance-specific reconfigurable hardware with flexible bounding schemes implemented in software.

Keywords

add-on boards; reconfigurable architectures; set theory; ternary logic; 3-valued logic; accelerator architectures; branch & bound; custom computing machines; deduction techniques; flexible bounding schemes; hybrid solver architecture; instance-specific; logic minimization; raw speedups; reconfigurable hardware; set covering; Computer networks; Cost function; Delay; Hardware; Laboratories; Logic; Minimization; Parallel processing; Prototypes; Runtime;

fLanguage

English

Publisher

ieee

Conference_Titel

Field-Programmable Custom Computing Machines, 2002. Proceedings. 10th Annual IEEE Symposium on

Print_ISBN

0-7695-1801-X

Type

conf

DOI

10.1109/FPGA.2002.1106671

Filename

1106671