Big-I/O anecdote: checkers program

"The success of the world championship calibre Chinook checkers program is largely due to its endgame databases [SCT+92]. The current databases represent over 150 billion positions, requiring 30 Gigabytes of storage when uncompressed. Using application-specific techniques, the databases are compressed into 5.22 Gigabytes of disk storage. Commonly accessed portions of the database are pre-loaded into memory and have a greater than 99% hit rate with a 500 megabyte cache. Cache misses result in random-access I/O. Even with this large cache, the sequential version of the program is I/O bound. A parallel searching version of Chinook further increases the I/O rate [Lu93]. (Computing the database is even more I/O intensive than running a match.)" -- Orran Krieger , from [Kri94].

[Kri94]: Orran Krieger. HFS: A flexible file system for shared-memory multiprocessors. PhD thesis, University of Toronto, October 1994.
[Lu93]: P. Lu. Parallel search of narrow game trees. Master's thesis, Department of Computing Science, University of Alberta, Edmonton, 1993. paullu@sys.toronto.edu
[SCT+92]: J. Schaeffer, J. Culberson, N. Treloar, B. Knight, P. Lu, and D. Szafron. A world championship caliber checkers program. Artificial Intelligence, 53(2-3):273--289, 1992.

Contributed by Orran Krieger (okrieg@eecg.toronto.edu) October 1994.