A LOCKLESS TRANSPOSITION-TABLE IMPLEMENTATION FOR PARALLEL SEARCH

Article type: Research Article

Authors: Hyatt, Robert M.^{a; 1} | Mann, Timothy^{b; 2}

Affiliations: [a] Birmingham Al, USA | [b] Palo Alto CA, USA

Note: [1] Computer and Information Sciences, University of Alabama at Birmingham, 115A Campbell Hall, UAB Station Birmingham, Al 35294-1170. Email: hyatt@cis.uab.edu.

Note: [2] Compaq Systems Research Center. VMware, Inc., 3145 Porter Drive, Palo Alto, CA 94304, USA. Email: tim@tim-mann.org.

Abstract: Parallel search programs use traditional alpha-beta tree searching, which includes the concept of transposition/refutation tables. Storing these entries in parallel can result in corrupt data that causes significant problems to the search. To prevent this, the common solution uses an atomic lock/unlock to implement a critical section that avoids the problem, but this incurs a significant performance penalty on many architectures. The paper describes a new approach that completely eliminates the need for any synchronization through locks, while still avoiding the problem of retrieving and using corrupted data.

DOI: 10.3233/ICG-2002-25104

Journal: ICGA Journal, vol. 25, no. 1, pp. 36-39, 2002