A Parallel Hardware Architecture for Accelerating α-β Game Tree Search

Yi-Fan KE; Tai-Ming PARNG

A Parallel Hardware Architecture for Accelerating α-β Game Tree Search

Yi-Fan KE, Tai-Ming PARNG

Full Text Views

0

Cite this

Summary :

Overheads caused by frequently communicating α-β values among numerous parallel search processes not only degrade greatly the performance of existing parallel α-β search algorithm but also make it impractical to implement these algorithms in parallel hardware. To solve this problem, the proposed architecture reduces the overheads by using specially designed multi-value arbiters to compare and global broadcasting buses to communicate α-β values. In addition, the architecture employs a set of α-β search control units (α-β SCU's) with distributed α-β registers to accelerate the search by searching all subtrees in parallel. Simulation results show that the proposed parallel architecture with 1444 (38 38) (α-β SCU's) searching in parallel can achieve 179 folds of speed-up. To verify the parallel architecture, we implemented a VLSI chip with 3 α-β SCU's. The chip can achieve a search speed of 13,381,345 node-visits per second, which is more than three orders of improvement over that of existing parallel algorithms.

Publication: IEICE TRANSACTIONS on Information Vol.E79-D No.9 pp.1232-1240

Publication Date: 1996/09/25

Publicized

Online ISSN

DOI

Type of Manuscript: PAPER

Category: Computer Hardware and Design

Cite this

Copy

Yi-Fan KE, Tai-Ming PARNG, "A Parallel Hardware Architecture for Accelerating α-β Game Tree Search" in IEICE TRANSACTIONS on Information, vol. E79-D, no. 9, pp. 1232-1240, September 1996, doi: .
Abstract: Overheads caused by frequently communicating α-β values among numerous parallel search processes not only degrade greatly the performance of existing parallel α-β search algorithm but also make it impractical to implement these algorithms in parallel hardware. To solve this problem, the proposed architecture reduces the overheads by using specially designed multi-value arbiters to compare and global broadcasting buses to communicate α-β values. In addition, the architecture employs a set of α-β search control units (α-β SCU's) with distributed α-β registers to accelerate the search by searching all subtrees in parallel. Simulation results show that the proposed parallel architecture with 1444 (38 38) (α-β SCU's) searching in parallel can achieve 179 folds of speed-up. To verify the parallel architecture, we implemented a VLSI chip with 3 α-β SCU's. The chip can achieve a search speed of 13,381,345 node-visits per second, which is more than three orders of improvement over that of existing parallel algorithms.
URL: https://global.ieice.org/en_transactions/information/10.1587/e79-d_9_1232/_p

Copy

@ARTICLE{e79-d_9_1232,
author={Yi-Fan KE, Tai-Ming PARNG, },
journal={IEICE TRANSACTIONS on Information},
title={A Parallel Hardware Architecture for Accelerating α-β Game Tree Search},
year={1996},
volume={E79-D},
number={9},
pages={1232-1240},
abstract={Overheads caused by frequently communicating α-β values among numerous parallel search processes not only degrade greatly the performance of existing parallel α-β search algorithm but also make it impractical to implement these algorithms in parallel hardware. To solve this problem, the proposed architecture reduces the overheads by using specially designed multi-value arbiters to compare and global broadcasting buses to communicate α-β values. In addition, the architecture employs a set of α-β search control units (α-β SCU's) with distributed α-β registers to accelerate the search by searching all subtrees in parallel. Simulation results show that the proposed parallel architecture with 1444 (38 38) (α-β SCU's) searching in parallel can achieve 179 folds of speed-up. To verify the parallel architecture, we implemented a VLSI chip with 3 α-β SCU's. The chip can achieve a search speed of 13,381,345 node-visits per second, which is more than three orders of improvement over that of existing parallel algorithms.},
keywords={},
doi={},
ISSN={},
month={September},}

Copy

TY - JOUR
TI - A Parallel Hardware Architecture for Accelerating α-β Game Tree Search
T2 - IEICE TRANSACTIONS on Information
SP - 1232
EP - 1240
AU - Yi-Fan KE
AU - Tai-Ming PARNG
PY - 1996
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E79-D
IS - 9
JA - IEICE TRANSACTIONS on Information
Y1 - September 1996
AB - Overheads caused by frequently communicating α-β values among numerous parallel search processes not only degrade greatly the performance of existing parallel α-β search algorithm but also make it impractical to implement these algorithms in parallel hardware. To solve this problem, the proposed architecture reduces the overheads by using specially designed multi-value arbiters to compare and global broadcasting buses to communicate α-β values. In addition, the architecture employs a set of α-β search control units (α-β SCU's) with distributed α-β registers to accelerate the search by searching all subtrees in parallel. Simulation results show that the proposed parallel architecture with 1444 (38 38) (α-β SCU's) searching in parallel can achieve 179 folds of speed-up. To verify the parallel architecture, we implemented a VLSI chip with 3 α-β SCU's. The chip can achieve a search speed of 13,381,345 node-visits per second, which is more than three orders of improvement over that of existing parallel algorithms.
ER -