CHAPTER 5. MATRIX COMPUTATIONS ON MULTI-GPU SYSTEMS

The dispatch stage

Once the DAG is constructed, the execution of the dispatch stage commences. While the analysis stage in the case of multi-GPU systems remains basically unmodified from that of SuperMatrix, the dispatch stage is deeply changed to support the particularities of the novel architecture.

Once the dispatch stage begins, the runtime system does not refer anymore to the codes provided by the programmer. Instead, all the necessary information regarding tasks to be performed, data needed by each tasks, and data dependencies between them is stored in the pending tasks queue (and thus, the associated DAG) built during the analysis stage.

From a high level perspective, once the DAG has been constructed and the dispatch stage is invoked, one thread is spawned per accelerator in the system (or less, depending on the user’s execution configuration). Each thread is bound to a specific accelerator, and is responsible for the management of that accelerator throughout the rest of the computation. Each thread monitors the queue of pending tasks, and as soon as a task becomes ready (that is, its data dependencies have been satisfied) and the corresponding accelerator is idle, task is executed in it. Upon completion, dependency information in the queue is properly updated.

There are important di erences between a run-time system designed for a multi-core architecture and a run-time focused on multi-GPU architectures that are reported next.

5.3.Programming model and runtime. Performance considerations

In this section, we review the main design decisions and performance concerns and improvements made during the design and implementation of the run-time system for multi-GPU architectures. A few concepts have been directly inherited from the existing SuperMatrix out-of-order execution run-time for multi-core architectures. In essence, the analysis stage for multi-GPU systems does not di er to that used for multi-core architectures. In this section, we focus on the di erences between both implementations and avoid details that have been already successfully applied and published for multi-core architectures [45, 46, 116].

5.3.1.Programming model

Figure 5.5 shows a sample code with the modifications necessary to transform a sequential code using the FLASH API to a code which can also run using the proposed runtime on a multi-GPU system. The code on the left side of the figure is analogous to the algorithm-by-blocks using the FLASH API shown in Figure 5.2. The code on the right part of the figure corresponds to a possible driver that initializes data structures and invokes the parallel Cholesky implementation.

Taking as a reference a driver that invokes a sequential version of the algorithm, the main di erences with respect to a parallel version of the program are mainly two:

1.Identification of a parallel region: routines FLASH Queue begin and FLASH Queue end encapsulate a parallel region. The underlying runtime system is in charge of task identification and data dependency management inside this region.

2.GPU activation: routines FLASH enable GPU and FLASH disable GPU indicate the runtime that available GPUs must be used to execute each task inside a parallel region. Without these invocations, the runtime system would execute the tasks on the multi-core processors.

A rapid review of the codes in the figure reveals that di erences between both codes are minimal, and are directly related to the structure of the underlying runtime system. In addition to the

132

5.3. PROGRAMMING MODEL AND RUNTIME. PERFORMANCE CONSIDERATIONS

runtime initialization and finalization procedures, there are two di erent parts in the code associated with the main stages of the runtime execution:

1.Analysis stage: This stage naturally corresponds to the FLAME-based part of the code in the figure. Each call to a routine starting with “FLASH *” creates a new task and adds it to the DAG. As the directionality of the operands in linear algebra routines is known a priori, all the necessary information to track dependencies between tasks is known, and the whole DAG can be constructed at runtime. In fact, the calls to routines “FLASH *” are just wrappers to functions that do not execute the real code, but just perform the DAG construction and handle dependency tracking (often referred as a symbolic execution of the code).

2.Dispatch stage: Once the first part of the execution is done, the DAG is completely built and data dependency information has been obtained. At this point, the actual parallel execution can proceed. The end of a parallel region activates the dispatch stage of the run-time system and thus the parallel execution can commence. All necessary information is now stored in the DAG, including task type, dependency tracking, and data flow information.

The code also illustrates how the user is isolated from the fact that the code is executed on a multi-GPU platform, as calls to the appropriate NVIDIA CUBLAS routines are embedded inside the task codes, and no data transfers are explicit in the codes as they are carried out by the the run-time system. This was one of the main goals in the design of the programming model, and here we demonstrate that the FLAME programming model is flexible enough to easily accommodate new architectures preserving the existing algorithms.

5.3.2.Temporal planification

In this section we o er an overview of the general mechanism that is used to schedule and dispatch tasks to the corresponding execution units in the multi-GPU architecture. Some of the ideas and techniques exposed have already been successfully implemented in the SuperMatrix runtime. Whenever possible, we only focus on the details that are necessary to adapt this runtime to the novel architecture.

Once the DAG has been built and all data dependency information is annotated, the dispatch stage commences with and invocation to the FLASH Exec list of tasks. Initially one thread is spawned per hardware accelerator. In our implementation, OpenMP is in charge of the creation, synchronization, and management of threads. From this point, each thread is responsible of the execution and data management of a given hardware accelerator.

Algorithm 2 presents the basic procedure that dictates the actions performed by each thread during the dispatch stage in order to schedule and execute tasks. In essence, the algorithm describes the general operations executed by the implemented runtime. We consider the DAG as a collection of tasks to be executed during the parallel execution stage. The tasks in this pool or queue of pending tasks are consumed by the threads following a consumer-producer scheme. When a thread becomes ready, it selects a ready task, that is, a task with all its data dependencies satisfied, and instructs the corresponding hardware accelerator to execute the task.

Note how in the algorithm, a ready state (from the data dependencies point of view) is not a su cient condition to consider that a task is ready for the execution on a given accelerator. In addition, the procedure is ready adds information about the identifier of the thread, which is necessary when data a nity policies are applied, as will be explained in the following sections. As a brief overview, we closely bind the accelerator in which a task can be executed to the specific data block that the task will update. In summary, each thread can dequeue a task from the pending

133

CHAPTER 5. MATRIX COMPUTATIONS ON MULTI-GPU SYSTEMS

Figure 5.5: Code implementation of the Cholesky factorization using the FLASH API and our multi-GPU runtime system.

134

5.3. PROGRAMMING MODEL AND RUNTIME. PERFORMANCE CONSIDERATIONS

queue when it is ready and, in case data a nity policies are applied, only if the corresponding accelerator is responsible for the execution of that task.

Algorithm 2 General runtime algorithm. This procedure is executed by all threads in order to schedule and dispatch tasks to the corresponding GPUs.

for all task in pending queue do if is ready( task, th id ) then

add to ready list( task, th id ) end if

end for

while ready tasks( th id ) do dequeue from ready()

check for pending transfers() load operands( task, th id ) dispatch task()

manage modified operands( task, th id ) for all dependent task do

update dependencies( dependent task ) if is ready( dependent task, th id ) then

add to ready list( dependent task, th id ) end if

end for end while

flush cache( )

Once a thread dequeues a task from the pending queue, it adds it to a proprietary queue of ready tasks, that only contains tasks that are ready for execution on its accelerator. Thus, the design features an independent ready queue for each accelerator present in the system. Ready tasks are dequeued and scheduled for execution by the thread that owns the corresponding queue. Prior to the execution, data blocks bound to the task must be available in the corresponding GPU. At the end, the state of the GPU memory must be updated accordingly to the memory management policies that will be explained in the following section.

Once the task is executed, the corresponding thread is in charge of updating the data dependencies of tasks that were waiting for execution in the queue of pending tasks. Once this information is updated, the algorithm continues with the identification and execution of the new ready tasks.

Up to this point, the following aspects di erentiate the run-time system tailored for multi-GPU architectures from that included in SuperMatrix for multi-core processors:

There is a close binding between threads and execution units.

The list of ready tasks is splitted, creating an independent queue bound to each execution unit.

It is possible to include data a nity policies to exploit data locality and reduce data transfers between memory spaces.

Data transfers are explicitly managed by the runtime, and not by the programmer.

135