Software model checking problems generally contain two differ ent types of non-determinism: 1) non-deterministically chosen values; 2) the choice of interleaving among threads. Most modern software model check ers can handle only one source of non-determinism efficiently, but not both. This paper describes a SAT-based model checker for asynchronous Boolean programs that handles both sources effectively. We address the first type of non-determinism with a form of symbolic execution and fix-point detection. We address the second source of non-determinism using a symbolic and dy namic partial-order reduction, which is implemented inside the SAT-solver’s case-splitting algorithm. The preliminary experimental results show that the new algorithm outperforms the existing software model checkers on large benchmarks.