TY - JOUR
T1 - A Performance Analysis of Transposition-Table-Driven Work Scheduling in Distributed Search
AU - Romein, J.W.
AU - Bal, H.E.
AU - Schaeffer, J.
AU - Plaat, A.
N1 - tds:tpds
PY - 2002
Y1 - 2002
N2 - This paper discusses a new work-scheduling algorithm for parallel search of single-agent state spaces, called Transposition-Table-Driven Work Scheduling, that places the transposition table at the heart of the parallel work scheduling. The scheme results in less synchronization overhead, less processor idle time, and less redundant search effort. Measurements on a 128-processor parallel machine show that the scheme achieves close-to-linear speedups; for large problems the speedups are even superlinear due to better memory usage. On the same machine, the algorithm is 1.6 to 12.9 times faster than traditional work-stealing-based schemes.
AB - This paper discusses a new work-scheduling algorithm for parallel search of single-agent state spaces, called Transposition-Table-Driven Work Scheduling, that places the transposition table at the heart of the parallel work scheduling. The scheme results in less synchronization overhead, less processor idle time, and less redundant search effort. Measurements on a 128-processor parallel machine show that the scheme achieves close-to-linear speedups; for large problems the speedups are even superlinear due to better memory usage. On the same machine, the algorithm is 1.6 to 12.9 times faster than traditional work-stealing-based schemes.
U2 - 10.1109/TPDS.2002.1003855
DO - 10.1109/TPDS.2002.1003855
M3 - Article
SN - 1045-9219
VL - 13
SP - 447
EP - 459
JO - IEEE Transactions on Parallel and Distributed Systems
JF - IEEE Transactions on Parallel and Distributed Systems
IS - 5
ER -
