loading...
Custom Computing Machines for the Set Covering Problem
Napa, California September 22-September 24
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/FPGA.2002.110667110th Annual IEEE Symposium on Field-P ...
 This Article 
 
PDF
HTML
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
Christian Plessl, Swiss Federal Institute of Technology
Marco Platzner, Swiss Federal Institute of Technology
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.
Citation:
Christian Plessl, Marco Platzner, "Custom Computing Machines for the Set Covering Problem," fccm, pp.163, 10th Annual IEEE Symposium on Field-Programmable Custom Computing Machines (FCCM'02), 2002
Usage of this product signifies your acceptance of the Terms of Use.