loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
Seventh Annual IEEE Symposium on Field-Programmable Custom Computing Machines
Reducing Compilation Time of Zhong's FPGA-Based SAT Solver
Napa California
April 21-April 23
ISBN: 0-7695-0375-6
ASCII Text
x 
 
Pak K. Chan, M.J. Boyd, S. Goren, K. Klenk, V. Kodavati, R. Kundu, M. Margolese, J. Sun, K. Suzuki, E. Thorne, X. Wang, J. Xu, M. Zhu, "Reducing Compilation Time of Zhong's FPGA-Based SAT Solver," Field-Programmable Custom Computing Machines, Annual IEEE Symposium on, pp. 308, Seventh Annual IEEE Symposium on Field-Programmable Custom Computing Machines, 1999.
 
 
BibTex
x
 
@article{ 10.1109/FPGA.1999.803709,
author = {Pak K. Chan and M.J. Boyd and S. Goren and K. Klenk and V. Kodavati and R. Kundu and M. Margolese and J. Sun and K. Suzuki and E. Thorne and X. Wang and J. Xu and M. Zhu},
title = {Reducing Compilation Time of Zhong's FPGA-Based SAT Solver},
journal ={Field-Programmable Custom Computing Machines, Annual IEEE Symposium on},
volume = {0},
year = {1999},
issn = {1082-3409},
pages = {308},
doi = {http://doi.ieeecomputersociety.org/10.1109/FPGA.1999.803709},
publisher = {IEEE Computer Society},
address = {Los Alamitos, CA, USA},
}
 
 
RefWorks Procite/RefMan/Endnote
x 
 
TY - CONF
JO - Field-Programmable Custom Computing Machines, Annual IEEE Symposium on
TI - Reducing Compilation Time of Zhong's FPGA-Based SAT Solver
SN - 1082-3409
SP
EP
A1 - Pak K. Chan,
A1 - M.J. Boyd,
A1 - S. Goren,
A1 - K. Klenk,
A1 - V. Kodavati,
A1 - R. Kundu,
A1 - M. Margolese,
A1 - J. Sun,
A1 - K. Suzuki,
A1 - E. Thorne,
A1 - X. Wang,
A1 - J. Xu,
A1 - M. Zhu,
PY - 1999
VL - 0
JA - Field-Programmable Custom Computing Machines, Annual IEEE Symposium on
ER -
 
Pak K. Chan, University of California at Santa Cruz
M.J. Boyd, University of California at Santa Cruz
S. Goren, University of California at Santa Cruz
K. Klenk, University of California at Santa Cruz
V. Kodavati, University of California at Santa Cruz
R. Kundu, University of California at Santa Cruz
M. Margolese, University of California at Santa Cruz
J. Sun, University of California at Santa Cruz
K. Suzuki, University of California at Santa Cruz
E. Thorne, University of California at Santa Cruz
X. Wang, University of California at Santa Cruz
J. Xu, University of California at Santa Cruz
M. Zhu, University of California at Santa Cruz
We present schemes to reduce the compilation time of configurable hardware that solves Boolean Satisfiability. The SAT solver presented by Zhong et al in FCCM98 has a large compilation time overhead mainly due to placement and routing of many FPGAs. We attack the problem on 3 fronts. First, we partitioning the SAT solver into instance-specific and instance non-specific components. Secondly, we transform SAT instances to canonical forms; and finally we present a board-level multiple-chip architecture to solve large SAT instances. All these efforts amount to a reduction in placement and routing time to configure the configurable hardware. We are able to reduce the compilation time to mere routing time of the implication circuits for each instance of the SAT problem, given the best scenario.
Citation:
Pak K. Chan, M.J. Boyd, S. Goren, K. Klenk, V. Kodavati, R. Kundu, M. Margolese, J. Sun, K. Suzuki, E. Thorne, X. Wang, J. Xu, M. Zhu, "Reducing Compilation Time of Zhong's FPGA-Based SAT Solver," fccm, pp.308, Seventh Annual IEEE Symposium on Field-Programmable Custom Computing Machines, 1999
Usage of this product signifies your acceptance of the Terms of Use.