The semester has begun with great business here at U. Iowa, and it is only with the extra time to work that comes, ironically, from Labor Day that I have time to post a little about what is happening in our group. Probably our biggest news is that the U.S. National Science Foundation has funded our large (just under $2 million) Computing Research Infrastructure (CRI) grant for StarExec. The goal of this project is to design and implement a cluster-backed web service called StarExec, which will serve as shared infrastructure for the many different communities in Computer Science developing logic solvers. Such programs are designed to be used as backends by applications in other domains, notably Artificial Intelligence (for example, planning problems), Hardware and Software Verification, Static Program Analysis, Formal Ontology, Combinatorial Design, and more. The idea is that one translates problems from the application domain — a verification problem, say — into a logical formula where validity of that formula (or dually, satisfiability), corresponds to solvability of the original problem. Logic solvers have improved tremendously in the past 10-15 years, and can handle enormous problems. SAT solvers (for pure propositional logic), for example, can handle formulas with hundreds of thousands of variables and millions of clauses. The nominal search space for such problems dwarfs the number of atoms in the observable universe. Of course, it is clever heuristics that have been demonstrated to work well in practice that makes searching and pruning this space possible.
With so much interest in logic solvers as backends for such domains, there has been a lot of growth in logic solving as a field, and in the availability of high-performance solvers for different particular kinds of logics. Different communities have sprung up (over the past couple decades) around one or the other logic. This is because different logical features give rise to significantly different engineering and theoretical issues. There have been signs of reconvergence of these different branches of automated reasoning. StarExec aims to help fuel such reconvergence, in the first place by providing a common service for creating and running jobs, where a selection of solvers is executed on a selection of benchmark formulas. StarExec will support uploading of both solvers and formulas. The former feature is useful for solver implementors, who want to compare their solvers to existing ones; the latter is useful for application developers, who want to compare solvers on their particular class of formulas. This feature is inspired both by community demand and also by System On TPTP, a web service implemented by Geoff Sutcliffe at U. Miami for first-order automated theorem provers. Indeed, the PIs for this StarExec grant are Geoff, Cesare Tinelli (my colleague here at U. Iowa), and myself.
The reason the system is called StarExec is that it will be a cross-community execution service. Different logic-solving communities will be able to use the service for services like hosting their libraries of benchmark formulas, running annual competitions or evaluations, maintaining real-time leaderboards (to define the state of the art for solvers in their community), and providing information about their benchmark formats and related standards. An advisory board consisting of community leaders from the different solver communities, as well as prominent application developers using solvers as backends, will help us ensure we provide the services that all our constituents want.
We are currently working with JJ Urich and Hugh Brown of our Computer Support Group (serving Computer Science, Math, and Statistics), both on ordering equipment, and helping interface with our campus IT Services for physical hosting of the cluster. As we have funds to buy at least 150 nodes, physical requirements like space, power, and cooling, are significant.
We plan to be running solver competitions on StarExec — at least on a trial basis — in Summer 2012. This is an ambitious goal, but we have great talent on the ground at the moment to develop the service. Tyler Jensen and CJ Palmer are two of the top recent undergraduates (currently Master’s students) of our program, and have already got demoable features up and running (thanks to a planning grant for StarExec we had last year). Unfortunately for us, but not surprisingly, they have exciting job opportunities in the works for after they graduate this December, so we will be recruiting understudies this semester, who we hope will carry the torch when they have moved on.