webmaster: Sven Koenig

International Symposium on Combinatorial Search (SoCS)


Title: The Performance of Swarm Search Methods.

Speaker: Gerard J. Holzmann

Abstract: In the last few years the type of compute engine that we all rely on to solve standard search problems has changed in a fundamental way. This change will have important consequences for the way in which we design and evaluate search algorithms. First, although memory sizes continue to grow in line with Moore's early predictions, CPU clock-speeds are frozen to the level they reached in roughly 2002. This brings a growing gap in capability. Soon we will have machines with very large memory sizes (think Terrabytes), but with what will feel like excruciatingly slow processors. Second, the switch to multi-core means that we will not just have one slow processor on our terra-size machines, but many. The natural evolution then is to move away from sequential search methods and towards swarm search method. In this talk, I will give some of the background, present the algorithms we have implemented for perfoming swarm searches with the SPIN model checker, and discuss performance.