Date: May 27th, 2014
Place: room 102, Faculty of Science Bldg. 7, Hongo Campus, The University of Tokyo
Title: Scalable Parallel Numerical CSP Solver
Speaker: Daisuke Ishii, Tokyo Tech
We present a parallel solver for numerical constraint satisfaction
problems (NCSPs) that can scale on a number of cores. NCSP solvers
compute pavings, which are sets of interval vectors that cover
continua of solutions, based on the branch and prune algorithm.
Although the NCSP solving process apparently exhibits a parallelism, a
parallelized solver has not been made available to date because of the
difficulty in partitioning the search space equally.
Our proposed method extends the Realpaver solver using the X10
language to split the search space and distribute the portion to the
cores. Then, an autonomous worker solver runs on each processor and
simultaneously communicates the search space with other solving tasks
in a sender-initiated manner.
In the experiments, we attained up to 119-fold speedup using 256 cores
of a parallel computer.
Title: Large Scale Parallel Monte Carlo Tree Search and Application to Go
Speaker: Kazuki Yoshizoe, JST / Todai
Monte Carlo Tree Search (MCTS), which combines Monte Carlo simulations with
tree search, is an innovative search algorithm that effectively
prunes unpromising portions of the search space by using the
statistical results of random sampling.
MCTS has not only achieved the greatest success in playing the game of Go but
also shown the promise to a broad range of applications.
We present parallel MCTS algorithms and experimental results in
synthesized game trees and the game of Go.
Our approach is based on an effective job scheduling scheme
based on a hash function and novel depth-first
reformulation that greatly reduces communication contention.
Our new algorithm successfully achieves a 3,200 fold speedup using 4,800 CPU
cores for virtual game trees and 1,350 fold speedup using
2,400 CPU cores for the game of Go, in the best cases.
We also present the difficulty in using large scale parallel computer
for real time decision making such as playing in a Go tournament.