Almost Deterministic Work Stealing
SC’19
Shumpei Shiina, Kenjiro Taura
The University of Tokyo

11/20/2019

Overview• Work Stealing is a popular scheduling algorithm for Task Parallelism• However, data locality of Work Stealing is not good
→ We propose Almost Deterministic Work Stealing (ADWS) to solve this problem
Visualization of task mapping• Simulation of 2D dambreaking• Colors of cells represent ranks of workers (blue: 0 → red: 63)

Fig. Random Work Stealing

Fig. ADWS (no steal)Fig. ADWS

1 / 32

Outline
Introduction
Motivating Example: Calculation of Particle Interactions
Task Parallelism and Work Stealing
Data Locality in Work Stealing
Proposed Method: Almost Deterministic Work Stealing (ADWS)
Deterministic Task Allocation
Hierarchical Localized Work Stealing
Evaluation
Related Work
Conclusion

Outline
Introduction
Motivating Example: Calculation of Particle Interactions
Task Parallelism and Work Stealing
Data Locality in Work Stealing
Proposed Method: Almost Deterministic Work Stealing (ADWS)
Deterministic Task Allocation
Hierarchical Localized Work Stealing
Evaluation
Related Work
Conclusion

Outline
Introduction
Motivating Example: Calculation of Particle Interactions
Task Parallelism and Work Stealing
Data Locality in Work Stealing
Proposed Method: Almost Deterministic Work Stealing (ADWS)
Deterministic Task Allocation
Hierarchical Localized Work Stealing
Evaluation
Related WorkConclusion

Motivating Example: Calculation of Particle Interactions

2D dambreaking simulation• Smoothed Particle Hydrodynamics (SPH)
which calculates short-range forces• Particles are managed in a quadtree(an octree in 3D)• The quadtree is usually unbalanced→2 / 32

Parallelization while Traversing the Tree
Sequential CodeTask Parallel Codeparticle_interaction(node) {if (node is leaf) {/* Calculate particle interactions* in leaf node */} else {for (child in node.children) {particle_interaction(child);}}}particle_interaction(node) {if (node is leaf) {/* Calculate particle interactions* in leaf node */} else {task_group tg;
for (child in node.children) {/* Spawn a child node as a task (fork) */tg.run([=]{ particle_interaction(child); });}/* Wait for completion of tasks (join) */tg.wait();}}3 / 32

Outline
Introduction
Motivating Example: Calculation of Particle InteractionsTask Parallelism and Work Stealing
Data Locality in Work Stealing
Proposed Method: Almost Deterministic Work Stealing (ADWS)
Deterministic Task Allocation
Hierarchical Localized Work Stealing
Evaluation
Related WorkConclusion

Task Parallelism• Parallel execution model by specifying
dependencies between tasks• Directed Acyclic Graph (DAG)

task_group tg;
tg.run([]{ ... });tg.run([]{ ... });tg.run([]{ ... });tg.run([]{ ... });tg.wait();Fig. TBB-like Task Group Notation• Fork-join pattern is frequently used• This paper focuses on nested fork-join programs

Fig. Directed Acyclic Graph (DAG)

4 / 32

Work Stealing1• Frequently used strategy to schedule task parallel programs• Each worker has its own task queue, and pushes/pops tasks to/from the queue• If tasks are exhausted in its local queue, it tries to steal tasks from other workers• Usually victims are chosen randomly• We call it random work stealing
Task Queue

StealTask

worker 0

worker 1

worker 2worker 3

1 R. D. Blumofe and C. E. Leiserson, “Scheduling multithreaded computations by work stealing,” J. ACM, vol. 46, no. 5, pp. 720–748, 1999.

5 / 32

OutlineIntroduction
Motivating Example: Calculation of Particle Interactions
Task Parallelism and Work Stealing
Data Locality in Work Stealing
Proposed Method: Almost Deterministic Work Stealing (ADWS)
Deterministic Task Allocation
Hierarchical Localized Work Stealing
Evaluation
Related WorkConclusion

1. Data Locality in DAGs
• Close nodes in DAGs tend to touch close data
• We want to schedule close nodes in close cores• Much more important in hierarchical memory architectures• What if worker {0, 1}, {2, 3} are in the same NUMA nodes?
0020323323320101032110001321100013102130221302

memorymemoryFig. Good Data Locality

Fig. Bad Data Locality

6 / 32

2. Data Locality in Iterative Programs• Iterative programs have similar DAGs across iterations• e.g, programs that iterate an array over and over• Data locality exists “vertically” in DAGs
• If scheduling is deterministic, data locality is good

7 / 32

Bad Data Locality in Random Work Stealing
Data locality is usually damaged by its randomness
1. Data Locality in DAGs
• Steal strategy is unaware of memory hierarchy

2. Data Locality in Iterative Programs• Scheduling is not deterministic across iterations

8 / 32

Good Data Locality in ADWS
Almost Deterministic Work Stealing (ADWS) improves both data locality
1. Data Locality in DAGs
• Improved by task mapping that matches task hierarchy with memory hierarchy

2. Data Locality in Iterative Programs• Improved by almost deterministic scheduling across iterations• ADWS also does dynamic load balancing

9 / 32

Outline
Introduction
Motivating Example: Calculation of Particle Interactions
Task Parallelism and Work Stealing
Data Locality in Work Stealing
Proposed Method: Almost Deterministic Work Stealing (ADWS)
Deterministic Task Allocation
Hierarchical Localized Work Stealing
Evaluation
Related WorkConclusion

ADWS Consists of Two Parts

1. Deterministic Task Allocation• Initial deterministic task mapping• Static partitioning for nested fork-join programs

2. Hierarchical Localized Work Stealing• Dynamic load balancing• Performs work stealing in a hierarchical manner

10 / 32

Task Hierarchy and Memory Hierarchy
0526756667754566603423335544122233311222501111200

100• Close workers touch close nodes in DAGs

00Fig. Desired Scheduling of a DAG
7654321• Task mapping respects memory hierarchy• Without a priori knowledge, it seems impossible• What kind of information is needed?

0Fig. Example of Memory Hierarchy

11 / 32

Hints from Programmers
Programmers must specify the amount of work for each task explicitly• It does not have to be absolute values; relative values are OK(ratio of w_1, ..., w_4 to w_all)• Rough estimates are acceptable thanks to dynamic load balancing at runtime• It is usually hardware-independent and application-specific• e.g. the number of particles (next slide)task_group tg(w_all);tg.run([]{ ... }, w_1);
tg.run([]{ ... }, w_2);
tg.run([]{ ... }, w_3);
tg.run([]{ ... }, w_4);
tg.wait();where w_1 + w_2 + w_3 + w_4 == w_all
12 / 32

Specifying Hints is Not So Hard
We can just use the number of particles in particle interactions
Particle Interactions in ADWS
particle_interaction(node) {if (node is leaf) {/* Calculate particle interactions in leaf node */} else {task_group tg(node.n_particles);for (child in node.children) {tg.run([=]{ particle_interaction(child); }, child.n_particles);}tg.wait();}}• The number of particles is a rough estimate
13 / 32Outline
Introduction
Motivating Example: Calculation of Particle Interactions
Task Parallelism and Work Stealing
Data Locality in Work Stealing
Proposed Method: Almost Deterministic Work Stealing (ADWS)
Deterministic Task Allocation
Hierarchical Localized Work Stealing
Evaluation
Related Work
Conclusion

Overview of Deterministic Task Allocation (1/4)

8.00• Circles: tasks• Triangles: worker ranges• Bottom rectangles: workers• Initially, there is only one task
• We want to distribute it to all workers
7654321014 / 32

Overview of Deterministic Task Allocation (2/4)• Left task: the spawned task
8.0

• Right task: the continuation0

8.0 - 3.6
= 4.4

3.6

• A new task is spawned

40• Split the worker range into two parts
based on the amount of work
specified by programmers• A task is executed by a worker whose
rank is the smallest in its worker
range

76

54

3

2

10

15 / 32

Overview of Deterministic Task Allocation (3/4)

8.00

8.0 - 3.6
= 4.4

3.6
40
3.6 - 3.0
= 0.6

3.0

• Continue to split worker ranges5

4.4 - 3.8
= 0.6

3.8

400

recursively and in parallel

7654

32

1016 / 32

Overview of Deterministic Task Allocation (4/4)

8.00

8.0 - 3.6
= 4.4

3.64

• Task distribution proceeds while
workers are executing actual tasks

0
3.6 - 3.0
= 0.6

3.0
56

7

40

3.0 - 1.8
= 1.2

1.8

50
3.8 - 1.8
= 2.0

1.8

56

4.4 - 3.8
= 0.6

3.8

24

302

1017 / 32

Algorithm of Deterministic Task Allocation (1/3)

local migration
queue queuei• Workers search for left boundary of theirikwork region• If worker range is split at worker k• Worker i pushes a task to worker k
lk

j

i

worker i

18 / 32

Algorithm of Deterministic Task Allocation (2/3)

local migration
queue queuei• If worker range is split at worker i itselfik• Worker i pushes the continuation to local

t1i

queue
• Worker i executes the spawned task (left)

lk

ji

t1i

worker i

19 / 32

Algorithm of Deterministic Task Allocation (3/3)

local migration
queue queue

iik• Tasks from other workers are pushed tot1
imigration queue

t1iijt2

it2lkjiworker i

20 / 32

Characteristics of Deterministic Task Allocation• Tasks are executed from left to right

local migration
queue queuei• The same order as serial execution• Work-first scheduling policy

ikt1• Workers do not push tasks to a
migration queue simultaneouslyit1iijt2i• No lock contention while searching• Please read the paper for more details

t2lkjiworker i

21 / 32

OutlineIntroduction
Motivating Example: Calculation of Particle Interactions
Task Parallelism and Work Stealing
Data Locality in Work Stealing
Proposed Method: Almost Deterministic Work Stealing (ADWS)
Deterministic Task Allocation
Hierarchical Localized Work Stealing
Evaluation
Related Work
Conclusion

Hierarchical Localized Work Stealing (1/4)

040• It depends on Deterministic Task
Allocation

5• Limit the range of steals to inside its

6405

200

“group”
7654321022 / 32

Hierarchical Localized Work Stealing (2/4)

045• Move to its parent group when the current

0400task group completes

7654321023 / 32

Hierarchical Localized Work Stealing (3/4)

040• It follows partitioning of deterministic task
allocation from bottom up

7

654

32

1024 / 32

Hierarchical Localized Work Stealing (4/4)

0• It becomes equivalent to random work
stealing at last
• Ideally, few tasks are ready at this time

7654

32

1025 / 32

Outline
Introduction
Motivating Example: Calculation of Particle Interactions
Task Parallelism and Work Stealing
Data Locality in Work StealingProposed Method: Almost Deterministic Work Stealing (ADWS)
Deterministic Task Allocation
Hierarchical Localized Work StealingEvaluation
Related WorkConclusion

Experiment Environment

Implement ADWS on MassiveThreads2 , a lightweight threading library• Skylake 6130 @ 2.1 GHz• 4 sockets• 4 NUMA nodes• 16 x 4 = 64 cores

2 J. Nakashima and K. Taura, “MassiveThreads: A thread library for high productivity languages,” in Concurrent Objects and Beyond: Papers dedicatedto Akinori Yonezawa on the Occasion of His 65th Birthday. Springer Berlin Heidelberg, 2014, pp. 222–238.

26 / 32

Performance Evaluation of Particle Interactions
We modified FDPS3 to use nested fork-join parallelism• Original implementation of FDPS uses GNU OpenMP parallel for (dynamic)

ADWS
Original FDPS implementation(OpenMP dynamic)• # of particles: 138968• 2D dam breaking
Higher is better

3 M. Iwasawa, A. Tanikawa, N. Hosono, et al., “Implementation and performance of FDPS: A framework for developing parallel particle simulation codes,”Publications of the Astronomical Society of Japan, vol. 68, no. 4, 2016.

27 / 32

Performance Evaluation of Heat2DHighly memory-bound and iterative application (5-point stencil)• It divides a 2D region into four parts recursivelyADWS, OpenMP static• optimized (SIMD)• 4096x4096 matrices• cutoff = 64x64

Higher is better• single precision

Existing Methods
for Task Parallelism• Constrained WS: 44 J. Lifflander, S. Krishnamoorthy, and L. V. Kale, “Optimizing data locality for fork/join programs using constrained work stealing,” in SC ’14: Proceedingsof the International Conference for High Performance Computing, Networking, Storage and Analysis, 2014, pp. 857–868

28 / 32

Performance Evaluation of Matrix Multiplication
Not iterative application using a simple divide-and-conquer algorithm
C11C21!
C12A11=C22A21A12A22!

B11B21!
B12A11 B11 + A12 B21=
B22
A21 B11 + A22 B21

A11 B12 + A12 B22
A21 B12 + A22 B22!

ADWS

• optimized (SIMD)
Random WS• 4096x4096 matrices• cutoff = 128x128• single precision
Higher is better• Hierarchical WS: 55 S.-J. Min, C. Iancu, and K. Yelick, “Hierarchical work stealing on manycore clusters,” in Fifth Conference on Partitioned Global Address Space Programming
Models (PGAS11), vol. 625, 201129 / 32

Outline
Introduction
Motivating Example: Calculation of Particle Interactions
Task Parallelism and Work Stealing
Data Locality in Work Stealing
Proposed Method: Almost Deterministic Work Stealing (ADWS)
Deterministic Task Allocation
Hierarchical Localized Work Stealing
Evaluation
Related WorkConclusion

Comparison to Related Work
• Optimize scheduling by using metrics of previous iterations678• ADWS is not specific to iterative programs• Optimize scheduling by using users’ hardware-specific hints910• ADWS requires users’ hints, but they are not hardware-specific• Optimize a steal strategy based on memory hierarchy without hints11• It does not optimize data locality of iterative programs
6 U. A. Acar, G. E. Blelloch, and R. D. Blumofe, “The data locality of work stealing,” in Proceedings of the Twelfth Annual ACM Symposium on Parallel
Algorithms and Architectures, ACM, 2000, pp. 1–12.

7 J. Lifflander, S. Krishnamoorthy, and L. V. Kale, “Optimizing data locality for fork/join programs using constrained work stealing,” in SC ’14: Proceedingsof the International Conference for High Performance Computing, Networking, Storage and Analysis, 2014, pp. 857–868.

8 Q. Chen, M. Guo, and H. Guan, “LAWS: Locality-aware work-stealing for multi-socket multi-core architectures,” in Proceedings of the 28th ACM International Conference on Supercomputing, ACM, 2014, pp. 3–12.

9 Y. Guo, J. Zhao, V. Cave, et al., “SLAW: A scalable locality-aware adaptive work-stealing scheduler,” in 2010 IEEE International Symposium on Parallel
Distributed Processing (IPDPS), 2010, pp. 1–12.

10 J. Deters, J. Wu, Y. Xu, et al., “A NUMA-aware provably-efficient task-parallel platform based on the work-first principle,” in 2018 IEEE International
Symposium on Workload Characterization (IISWC), 2018, pp. 59–70.

11 S.-J. Min, C. Iancu, and K. Yelick, “Hierarchical work stealing on manycore clusters,” in Fifth Conference on Partitioned Global Address Space Programming
Models (PGAS11), vol. 625, 2011.

30 / 32

Outline
Introduction
Motivating Example: Calculation of Particle Interactions
Task Parallelism and Work Stealing
Data Locality in Work Stealing
Proposed Method: Almost Deterministic Work Stealing (ADWS)
Deterministic Task AllocationHierarchical Localized Work Stealing
Evaluation
Related WorkConclusion

Conclusion
We have presented Almost Deterministic Work Stealing (ADWS), which:• focuses on nested fork-join parallelism• improves data locality in work stealing• memory hierarchy-aware deterministic scheduling

ADWS requires users’ hints, but• it is hardware-independent and application-specific• it keeps portability of code

ADWS can speedup task parallel programs while keeping productivity

31 / 32

Future Work• Automatic work estimation for iterative programs• Programmers do not have to specify hints• More benchmarks• Combine with cache-aware scheduling like CATS1212 Q. Chen, M. Guo, and Z. Huang, “CATS: Cache aware task-stealing based on online profiling in multi-socket multi-core architectures,” in Proceedings ofthe 26th ACM International Conference on Supercomputing, ACM, 2012, pp. 163–172.

32 / 32