Go to  Advanced Search

αβService : an asynchronous parallel tree search service for ChessGrid

Show full item record

Files in this item

Files Size Format Description   View
ubc_2005-0600.pdf 3.093Mb Adobe Portable Document Format   View/Open
 
Title: αβService : an asynchronous parallel tree search service for ChessGrid
Author: Pramanik, Sukanta
Degree Master of Science - MSc
Program Computer Science
Copyright Date: 2005
Abstract: The performance of game playing programs depends heavily on the strength of the search algorithm used. As such, several research activities have been conducted to speed up game tree search algorithms by using parallel machines. Most of these algorithms are targeted towards shared memory models or tightly coupled systems. In recent years, the rapid progress of Grid computing has led to finding a Grid solution to difficult computational problems. To ensure interoperability among diverse computational resources in the Grid, Service Oriented Architecture is used to achieve loose coupling among interacting software agents, known as services. Finding an efficient tree search algorithm in this new paradigm is a challenging problem. This thesis proposes a new service oriented algorithm, called αβService, which targets loosely coupled systems. It creates a tree of services to search the game tree concurrently. The necessity of synchronization points is eliminated with a notification mechanism, enabling the concurrently running services to continue their asynchronous search without waiting for others to finish. The αβService is implemented as a Grid service in Globus using Globus Toolkit 3. The service is deployed to create a ChessGrid testbed and experiments are conducted with a branching factor controlled test suite which demonstrates an average speedup of 2.61 with six machines.
URI: http://hdl.handle.net/2429/16669
Series/Report no. UBC Retrospective Theses Digitization Project [http://www.library.ubc.ca/archives/retro_theses/]

This item appears in the following Collection(s)

Show full item record

All items in cIRcle are protected by copyright, with all rights reserved.

UBC Library
1961 East Mall
Vancouver, B.C.
Canada V6T 1Z1
Tel: 604-822-6375
Fax: 604-822-3893