Grain Size Controlled Parallel MCTS Clause Samples

Grain Size Controlled Parallel MCTS. ‌ This section discusses the Grain Size Controlled Parallel MCTS (GSCPM) algorithm. The pseudo-code for GSCPM is shown in Algorithm 4.1. In the MCTS loop (see Al- gorithm 2.1 and Algorithm 2.2), the computation associated with each iteration is independent. Therefore, these are candidates to guide a task decomposition by map- ping a chunk of iterations onto a task for parallel execution on separate processors. This type of task is called Iteration-Level Task (ILT) and this type of parallelism is called Iteration-Level Parallelism (ILP) [CWvdH08a, SP14, MPvdHV15a]. Definition 4.4 (Iteration-level Parallelism) Iteration-level parallelism is a type of par- allelism that enables task-level parallelization to assign a chunk of MCTS iterations as a separate task for execution on separate processors. The MCTS loop can be implemented with two different loop constructs (i.e., while and for). If we cannot predict how many iterations will take place (e.g., the search continues until a goal value has been found), then this is a while loop. In contrast, if the number of iterations is known in advance, then this can be implemented in the form of a for loop. The GSCPM algorithm is designed for the modern threading libraries. For many threading libraries, it is necessary for parallelizing loops to know the total number of iterations in advance. Therefore, the outer loop in GSCPM is a counting for loop (see Line 5 in Algorithm 4.1) which iterates as many times as the number of available tasks (nTasks). Then, the search budget (nPlayouts) can be divided into chunks of iterations to be executed by an inner serial loop (see Line 7 in Algorithm 4.1 and details of the UCTSEARCH function in Algorithm 2.2). A chunk is a sequential collection of one or more iterations. The maximum size of a chunk is called grain size. Therefore, the grain size is the number of playouts divided by the number of tasks (nPlayouts/nTasks) and it could be as small as one iteration or as large as the total number of iterations. Controlling the number of tasks (nTasks) allows to control the grain size in GSCPM. The design of GSCPM is based on fork-join parallelism. The outer loop forks instances of the inner loop as tasks (see Line 7) and the runtime scheduler allocates the tasks to threads for execution. With this technique, we can create more tasks than threads. This is called fine-grained task-level parallelism.