A Performance Analysis of Transposition-Table-Driven Work Scheduling in Distributed Search

J.W. Romein, H.E. Bal, J. Schaeffer, A. Plaat

Research output: Contribution to JournalArticleAcademicpeer-review

Abstract

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.
Original languageEnglish
Pages (from-to)447-459
JournalIEEE Transactions on Parallel and Distributed Systems
Volume13
Issue number5
DOIs
Publication statusPublished - 2002

Fingerprint

Scheduling
Scheduling algorithms
Synchronization
Data storage equipment

Bibliographical note

tds:tpds

Cite this

@article{957cb39a6d644ee2ad2a4558c8dbae67,
title = "A Performance Analysis of Transposition-Table-Driven Work Scheduling in Distributed Search",
abstract = "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.",
author = "J.W. Romein and H.E. Bal and J. Schaeffer and A. Plaat",
note = "tds:tpds",
year = "2002",
doi = "10.1109/TPDS.2002.1003855",
language = "English",
volume = "13",
pages = "447--459",
journal = "IEEE Transactions on Parallel and Distributed Systems",
issn = "1045-9219",
publisher = "IEEE Computer Society",
number = "5",

}

A Performance Analysis of Transposition-Table-Driven Work Scheduling in Distributed Search. / Romein, J.W.; Bal, H.E.; Schaeffer, J.; Plaat, A.

In: IEEE Transactions on Parallel and Distributed Systems, Vol. 13, No. 5, 2002, p. 447-459.

Research output: Contribution to JournalArticleAcademicpeer-review

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

VL - 13

SP - 447

EP - 459

JO - IEEE Transactions on Parallel and Distributed Systems

JF - IEEE Transactions on Parallel and Distributed Systems

SN - 1045-9219

IS - 5

ER -