Note: [1] This research was supported in part by the Advanced Research Projects Agency, U.S. Department of Defense, under grants N00014-94-1-0985, N00014-92-J-1310, and N00014-91-J-1698.
Note: [*] Laboratory for Computer Science, Massachusetts Institute of Technology, NE43-247, 545 Technology Square, Cambridge, MA 02139. E-mail: [email protected].
Abstract: 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.
DOI: 10.3233/ICG-1995-18102
Journal: ICGA Journal, vol. 18, no. 1, pp. 3-19, 1995
