The STARTECH Massively-Parallel Chess Program 1

The STARTECH massively-parallel chess program, running on a 512-processor Connection Machine CM-5 supercomputer, tied for third place at the 1993 ACM International Computer Chess Championship. Testing the program informally, its rating was over 2400 USCF points. STARTECH employs the Jamboree search algorithm, a natural extension of Pearl’s Scout search algorithm, to find parallelism in game-tree searches. STARTECH’S work-stealing scheduler distributes the work specified by the search algorithm across the processors of the CM-5. The program uses one global transposition table shared among the processors.

Two perfonnance measures help in understanding the program’s performance: the work performed, W, and the critical-path length, C. The Jamboree search algorithm seems to perform some 2 to 3 times more work than the best serial version. The critical-path length, under tournament conditions, is less than 0.1 percent of the work, yielding an average parallelism of over 1000. The STARTECH scheduler achieves actual performance of approximately T ≈ 1.02 W/p + 1.5 C on P processors. The critical-path length and work performed can thus be used to tune performance.