2001 | OriginalPaper | Buchkapitel
One Flip per Clock Cycle
verfasst von : Martin Henz, Edgar Tan, Roland Yap
Erschienen in: Principles and Practice of Constraint Programming — CP 2001
Verlag: Springer Berlin Heidelberg
Enthalten in: Professional Book Archive
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Stochastic Local Search (SLS) methods have proven to be successful for solving propositional satisfiability problems (SAT). In this paper, we show a hardware implementation of the greedy local search procedure GSAT. With the use of field programmable gate arrays (FPGAs), our implementation achieves one flip per clock cycle by exploiting maximal parallelism and at the same time avoiding excessive hardware cost. Experimental evaluation of our prototype design shows a speedup of two orders of magnitude over optimized software implementations and at least one order of magnitude over existing hardware schemes. As far as we are aware, this is the fastest known implementation of GSAT. We also introduce a high level algorithmic notation which is convenient for describing the implementation of such algorithms in hardware, as well as an appropriate performance measure for SLS implementations in hardware.