Maxime Gonthier -Samuel

Thibault -Loris Marchal -

Memory-Aware Scheduling Memory-Aware Scheduling Of Tasks Sharing Data On Multiple GPUs Of Tasks Sharing Data On Multiple GPUs

Figure 2: Example with a memory of size 2 data. The graph of input data dependencies is shown on the left. The figure on the right corresponds to the partition and schedule produced by the scheduler ▸ Deque Model

Schedules tasks where their completion times are expected to be minimal. Uses a ready strategy to favor tasks whose data has already been loaded into memory.

▸ EAGER EAGER

Process tasks in the order in which it receives them our baseline ⇒ our ba ▸ Tesla V100 GPUs with a 12000 MB/s PCI bandwidth Tesla V100 GPUs with a 12000 MB/s PCI bandwidth ▸ GPU memory limited to 500 MB to better distinguish the performance even on small datasets GPU memory limited to 500 MB to better distinguish the performance even on small datasets ▸ 10 runs per experiment (deviation < 2%) 10 runs per experiment (deviation < 2%)

▸ Pathological matrix size due to LRU's eviction policy when the memory is a constraint (after the red Pathological matrix size due to LRU's eviction policy when the memory is a constraint (after the red dotted line) for EAGER, hMETIS and DARTS dotted line) for EAGER, hMETIS and DARTS

▸ DMDAR suffers from a conflict between prefetches and evictions DMDAR suffers from a conflict between prefetches and evictions ▸ DARTS+LUF stays close to the asymptotic goal ! DARTS+LUF stays close to the asymptotic goal !

▸ hMETIS suffers from a large scheduling hMETIS suffers from a large scheduling cost cost

▸ DARTS can be used with a reduced DARTS can be used with a reduced complexity (DARTS+OPTI) by stopping complexity (DARTS+OPTI) by stopping the search for the optimal data earlier.

the search for the optimal data earlier.

▸ Even without memory limitation, DARTS Even without memory limitation, DARTS outperforms DMDAR outperforms DMDAR To get peak performance we need to minimize the number of access to the main memory ▸ Motivations : Motivations :

• High-performance computing applications, like weather and climate forecasting, have an increasing demand in computer power • GPUs have a large computation power but have a limited memory. This, coupled with the share of a single PCI express bus by multilple GPUs induce a large amount of data transfers which reduces performance Limiting data movement is crucial to extract the most out of GPUs ⇒ our ba • Limits data transfers thanks to the finding of an optimal data and an adapted eviction policy

• Overlaps communication and computations by distributing transfers over time

• Can be used with a reduced complexity • Can deal with priorities

▸ Areas for improvement: Areas for improvement:

• Manage multiple MPI nodes

• Use other out-of-core applications (DARTS is not specific to GPUs!) ▸ Task flow Task flow

• (1). DARTS fills Planned Tasks (1). DARTS fills Planned Tasks • (2). Some tasks are popped by Task (2). Some tasks are popped by Task Buffer and start to be prefetched Buffer and start to be prefetched • (3). If the GPU is idling, a task is (3). If the GPU is idling, a task is popped from Task Buffer popped from Task Buffer • (4). After an eviction, tasks in Planned (4). After an eviction, tasks in Planned Tasks can be removed Tasks can be removed

▸ Strategy Strategy

• (1).Find the optimal data D such (1).Find the optimal data D such that the number of tasks depending that the number of tasks depending on D and on other data in memory on D and on other data in memory is maximum is maximum

• (2). Fill plannedTasks with these (2). Fill plannedTasks with these tasks tasks

▸ Our eviction policy : Least Used in the Future (LUF) Our eviction policy : Least Used in the Future (LUF)

• If possible, evict data not useful for any task in If possible, evict data not useful for any task in taskBuffer and used by a minimal number of tasks in taskBuffer and used by a minimal number of tasks in plannedTasks plannedTasks

• Otherwise, evict data whose next usage is the furthest in Otherwise, evict data whose next usage is the furthest in the future in the future in plannedTasks plannedTasks

Figure 4 :Figure 6 :Figure 5 :

 465 Figure 4: GFlop/s (left) and data transfers (right) on a tiled (1 x n) Matrix Multiplication in outer product order with 2 Tesla V100 GPUs

▸

  ⇒ our ba We provide a new algorithm (DARTS) and a new eviction policy (LUF) focused on data locality ▸ Results : Results : DARTS+LUF achieves good performance because it : :

Objective 1 :

 1 Minimize the number of tasks on each GPU Objective 2: Minimize the amount of data loads on each GPU ▸ Using (hyper-)graph partitioning: hMETIS Using (hyper-)graph partitioning: hMETIS • Hypergraph Represents a data being shared by multiple tasks ⇒ our ba • hMETIS produces subsets of task that maximize the amount of edges (data shares) inside each subset • We add dynamic reordering and task stealing to improve performance Intuition : Consider data locality before task allocation You can learn You can learn more about my more about my work on my work on my website website

Motivation: Extract peak performance from GPUs Motivation: Extract peak performance from GPUs Experimental evaluations on independent taskset Experimental evaluations on independent taskset

Summary and conclusion Summary and conclusion

A novel strategy: Data-Aware Reactive Task Scheduling (DARTS) A novel strategy: Data-Aware Reactive Task Scheduling (DARTS)

Algorithms from the state of the art Algorithms from the state of the art

Framework and objectives Framework and objectives

Experimental evaluations with dependencies Experimental evaluations with dependencies

▸ When choosing the optimal data with dependencies, DARTS takes into account the transfer time, priority When choosing the optimal data with dependencies, DARTS takes into account the transfer time, priority and length of task associated with each data. and length of task associated with each data.

▸ DARTS achieves better performances once the memory is a constraint (on the right of the green dotted DARTS achieves better performances once the memory is a constraint (on the right of the green dotted line) and behaves as DMDAR when the memory is not limited (on the left). It also greatly reduces data line) and behaves as DMDAR when the memory is not limited (on the left). It also greatly reduces data transfers. DARTS outperforms the scheduler from PaRSEC, a state-of-the-art runtime. transfers. DARTS outperforms the scheduler from PaRSEC, a state-of-the-art runtime.

Figure 1

Figure 3