When: Tuesday, November 03, 1:30 p.m.

Where: 4101 Gates & Hillman Centers

Austin McDonald,
Machine Learning Department

Data Analysis Project Presentation

Abstract:
We present an extension of WalkSAT, a stochastic local search algorithm for solving SAT problems. Our extension learns new clauses by resolving existing clauses based on the current state of a WalkSAT run. We show that clause learning leads to significant speedup in WalkSAT runs, both in terms of fewer steps and faster runtime. We also demonstrate that our WalkSAT implementation is both easily parallelizable and demonstrates great speedup from parallelization, by leveraging learned clauses across the entire set of parallel runs. WalkSAT, due to its simple algorithm, is particularly well-suited to implementation on graphics processing units (GPUs), which are often capable of many more operations per second than a CPU for applications with little control flow. Our parallelization scheme also scales easily to thousands of threads, which is required to optimally utilize GPUs. We describe extending our algorithm to work in a GPU environment.

<< Back