Distributed Continuation Stealing isMore Scalable than You Might Think
IEEE Cluster ’22
Shumpei Shiina, Kenjiro Taura
The University of Tokyo

2022.09.06

Dynamic Load Balancing on Distributed Memory• Dynamic load balancing is particularly important for irregular algorithms– e.g., sorting, sparse matrix arithmetic, tree-based algorithms, AMR, ...

• Hardware is becoming massively parallel → Manual load balancing is getting harder– intra-/inter-node, many-core, deep cache hierarchy, NUMA, ...

• Work stealing is a popular algorithm for automatic load balancing by the runtime– Only when a processor becomes idle, it attempts to steal work from another processor

Fig. Fluid simulation (SPH)
Fig. Unbalanced Tree

1 / 24

Task Parallelism (Fork-Join Parallelism)• Spawn (fork) a concurrent thread and join its completion– threads can be created recursively → well suited todivide-and-conquer algorithms
thread th = spawn([=]{ A(); });B(); // A() and B() are executed concurrently
th.join(); // ensures completion of A()• General parallel execution model for many algorithms– e.g., matrix arithmetic, FFT, sorting, dynamic programming, gametree search, space-partitioning tree, N-body, ...
– Adopted by many runtimes: Cilk, Intel TBB, Java fork/join,
OpenMP, ...

• A bunch of threads ( # of cores) can be createdFig. Task dependency graph– The underlying runtime performs dynamic load balancing

2 / 24

Work Stealing [Blumofe and Leiserson, JACM ’99]
• Widely used scheduling strategy for task-parallel programs• Each processor has its own thread queue• A processor pushes stealable threads to its thread queue• A processor pops a thread from its local queue when the current thread is completed• When the local queue is empty, it steals a thread from a randomly selected processor
Steal

Thread Queue

Thread…
Processor 1

Processor 2

Processor 3

Processor 𝑛

3 / 24

What is Continuation Stealing?
Thread T𝑝 :...

T𝑝

4 / 24

What is Continuation Stealing?
Thread T𝑝 :...
thread T𝑐 = spawn([=]{ B𝑐 ; });

T𝑝
Spawn

B𝑐

T𝑐
4 / 24

What is Continuation Stealing?
Thread T𝑝 :...
thread T𝑐 = spawn([=]{ B𝑐 ; });
B𝑝 ;

B𝑝

T𝑝
Spawn

B𝑐

T𝑐
4 / 24

What is Continuation Stealing?
Thread T𝑝 :...
thread T𝑐 = spawn([=]{ B𝑐 ; });B𝑝 ;T𝑐 .join();

B𝑝

T𝑝
Spawn

B𝑐

Join

T𝑐
4 / 24

What is Continuation Stealing?
Thread T𝑝 :...
thread T𝑐 = spawn([=]{ B𝑐 ; });B𝑝 ;T𝑐 .join();Processor 1: parent first

B𝑝

T𝑝
Spawn

B𝑐

Join

T𝑐
4 / 24

What is Continuation Stealing?
Thread T𝑝 :...
thread T𝑐 = spawn([=]{ B𝑐 ; });B𝑝 ;T𝑐 .join();Processor 1: parent first

B𝑝

T𝑝
Spawn
Processor 2: steal

B𝑐

Join

T𝑐
4 / 24

What is Continuation Stealing?
Thread T𝑝 :...
thread T𝑐 = spawn([=]{ B𝑐 ; });B𝑝 ;T𝑐 .join();
The newly created child is stolen→ Child stealing
Processor 1: parent first

B𝑝

T𝑝
Spawn
Processor 2: steal

B𝑐

Join

T𝑐
4 / 24

What is Continuation Stealing?
Thread T𝑝 :...
thread T𝑐 = spawn([=]{ B𝑐 ; });B𝑝 ;T𝑐 .join();

B𝑝

T𝑝
Spawn
Processor 1: child first

B𝑐

Join

T𝑐
4 / 24

What is Continuation Stealing?
Thread T𝑝 :...
thread T𝑐 = spawn([=]{ B𝑐 ; });B𝑝 ;T𝑐 .join();Processor 2: steal

B𝑝

T𝑝
Spawn
Processor 1: child first

B𝑐

Join

T𝑐
4 / 24

What is Continuation Stealing?
Thread T𝑝 :...
thread T𝑐 = spawn([=]{ B𝑐 ; });B𝑝 ;T𝑐 .join();
The parent’s continuation is stolen→ Continuation stealing
Processor 2: steal

B𝑝

T𝑝
Spawn
Processor 1: child first

B𝑐

Join

T𝑐
4 / 24

Why We Consider Continuation Stealing is Better• Many shared-memory runtimes (e.g., Cilk) use continuation stealing because of its
efficiency• Good characteristic: Continuation stealing preserves the serial execution order– i.e., the execution order of programs with spawn/join keywords removed– Ordinary function call: execute the called function → its continuation– Continuation stealing: execute the spawned thread → its continuation• Because of this execution order, continuation stealing is unlikely to be blocked at join
– Later, I’ll explain why

5 / 24

Continuation Stealing on Distributed Memory• However, most distributed work-stealing runtimes use child stealing

6 / 24

Continuation Stealing on Distributed Memory• However, most distributed work-stealing runtimes use child stealing• This is presumably because people might think...

6 / 24

Continuation Stealing on Distributed Memory• However, most distributed work-stealing runtimes use child stealing• This is presumably because people might think...
1. It is difficult to implement continuation stealing as a library with unmodified C/C++
compilers

6 / 24

Continuation Stealing on Distributed Memory• However, most distributed work-stealing runtimes use child stealing• This is presumably because people might think...
1. It is difficult to implement continuation stealing as a library with unmodified C/C++
compilers
2. Continuation stealing is less efficient than child stealing because a whole call stack needs
to be copied across nodes

6 / 24

Continuation Stealing on Distributed Memory• However, most distributed work-stealing runtimes use child stealing• This is presumably because people might think...
1. It is difficult to implement continuation stealing as a library with unmodified C/C++
compilers
2. Continuation stealing is less efficient than child stealing because a whole call stack needs
to be copied across nodes• The first concern was addressed by [Akiyama and Taura, HPDC ’15]
– Efficient RDMA-based continuation stealing by copying call stacks across nodes

6 / 24

Continuation Stealing on Distributed Memory• However, most distributed work-stealing runtimes use child stealing• This is presumably because people might think...
1. It is difficult to implement continuation stealing as a library with unmodified C/C++
compilers
2. Continuation stealing is less efficient than child stealing because a whole call stack needs
to be copied across nodes• The first concern was addressed by [Akiyama and Taura, HPDC ’15]
– Efficient RDMA-based continuation stealing by copying call stacks across nodes• The second concern has not previously been addressed– No performance comparison against child stealing or any other existing runtimes

6 / 24

Continuation Stealing on Distributed Memory• However, most distributed work-stealing runtimes use child stealing• This is presumably because people might think...
1. It is difficult to implement continuation stealing as a library with unmodified C/C++
compilers
2. Continuation stealing is less efficient than child stealing because a whole call stack needs
to be copied across nodes• The first concern was addressed by [Akiyama and Taura, HPDC ’15]
– Efficient RDMA-based continuation stealing by copying call stacks across nodes• The second concern has not previously been addressed– No performance comparison against child stealing or any other existing runtimes• This paper suggests that the second assumption is not true
6 / 24

Contributions
Technical Contribution:• Efficient join implementations over RDMA, which were not covered by previous work
– in order to reveal the full potential of continuation stealing

Experimental Results:• Despite a small increase in steal latency, continuation stealing often outperforms
child stealing overall• Even compared with existing runtimes, continuation stealing is reasonably fast(showing great scalability to more than 100k cores)• As well as steal policies, different join policies largely affect performance
particularly for programs with a complicated dependency patternContinuation stealing is beneficial even on distributed memory!
7 / 24

Outline
Background
Joining Threads over RDMA
Evaluation
Performance Analysis of Various Scheduling Policies (Synthetic Benchmark)
Scalability Study with State-of-the-Art Systems (UTS Benchmark)Thread Migration Capability and Futures (LCS Benchmark)Conclusion and Future Work

Outline
Background
Joining Threads over RDMA
Evaluation
Performance Analysis of Various Scheduling Policies (Synthetic Benchmark)
Scalability Study with State-of-the-Art Systems (UTS Benchmark)Thread Migration Capability and Futures (LCS Benchmark)Conclusion and Future Work

Child Stealing vs. Continuation Stealing on distributed memory

Easy to implement?
Representation of astealable task
Preserves serial
execution order?
Likely to efficiently
resolve join?

Child Stealing

Continuation Stealing

Yes

Not so easy

Function pointer + arguments

Call stack

No

Yes

No

Yes
8 / 24

Child Stealing vs. Continuation Stealing on distributed memory

Continuation stealing requires thread migration (without compiler support), which is
nontrivial to implement (but possible [Akiyama and Taura, HPDC ’15])

Easy to implement?
Representation of astealable task
Preserves serial
execution order?
Likely to efficiently
resolve join?

Child Stealing

Continuation Stealing

Yes

Not so easy

Function pointer + arguments

Call stack

No

Yes

No

Yes
8 / 24

Child Stealing vs. Continuation Stealing on distributed memory

Continuation stealing needs to copy the call stack, which is typically larger than a function pointer and its arguments → Larger steal cost?

Easy to implement?
Representation of astealable task
Preserves serial
execution order?
Likely to efficiently
resolve join?

Child Stealing

Continuation Stealing

Yes

Not so easy

Function pointer + arguments

Call stack

No

Yes

No

Yes
8 / 24

Child Stealing vs. Continuation Stealing on distributed memory

Continuation stealing preserves the serial execution order (the order without
spawn/join primitives) → good theoretical bounds are known

Easy to implement?
Representation of astealable task
Preserves serial
execution order?
Likely to efficiently
resolve join?

Child Stealing

Continuation Stealing

Yes

Not so easy

Function pointer + arguments

Call stack

No

Yes

No

Yes
8 / 24

Child Stealing vs. Continuation Stealing on distributed memory

Continuation stealing is considered more efficient for resolving join → Next slide

Easy to implement?
Representation of astealable task
Preserves serial
execution order?
Likely to efficiently
resolve join?

Child Stealing

Continuation Stealing

Yes

Not so easy

Function pointer + arguments

Call stack

No

Yes

No

Yes
8 / 24

Child Stealing → Joins are Likely to be Blocked

B𝑝

T𝑝
Spawn

B𝑐

Join

T𝑐

9 / 24

Child Stealing → Joins are Likely to be Blocked

Processor 1: parent first

B𝑝

T𝑝
Spawn

B𝑐

Join

T𝑐

9 / 24

Child Stealing → Joins are Likely to be Blocked

Processor 1: parent first

B𝑝

T𝑝
Spawn
Processor 2: steal

B𝑐

Join

T𝑐
Execution of the child B𝑐 is delayedcompared to the parent B 𝑝
9 / 24

Child Stealing → Joins are Likely to be Blocked

Processor 1: parent first

B𝑝

T𝑝
Spawn
Processor 2: steal

B𝑐

Join

T𝑐
Execution of the child B𝑐 is delayedcompared to the parent B 𝑝

The parent is likely to reach the join earlier→ The parent is likely to be blocked at join

9 / 24

Child Stealing → Joins are Likely to be Blocked
The parent can be resumed when the child is completed,but processor 1 may be busy when the join is resolved→ execution of the continuation of the join can be delayed
Processor 1: parent first

B𝑝

T𝑝
Spawn
Processor 2: steal

B𝑐

Join

T𝑐
Execution of the child B𝑐 is delayedcompared to the parent B 𝑝

The parent is likely to reach the join earlier→ The parent is likely to be blocked at join

9 / 24

Continuation Stealing → Joins are Unlikely to be Blocked

B𝑝

T𝑝
Spawn

B𝑐

Join

T𝑐

10 / 24

Continuation Stealing → Joins are Unlikely to be Blocked

B𝑝

T𝑝
Spawn
Processor 1: child first

B𝑐

Join

T𝑐

10 / 24

Continuation Stealing → Joins are Unlikely to be Blocked
Execution of the parent B 𝑝 is delayedcompared to the child B𝑐

Processor 2: steal

B𝑝

T𝑝
Spawn
Processor 1: child first

B𝑐

Join

T𝑐

10 / 24

Continuation Stealing → Joins are Unlikely to be Blocked
Execution of the parent B 𝑝 is delayedcompared to the child B𝑐

Processor 2: steal

B𝑝

T𝑝
Spawn
Processor 1: child first

B𝑐

Join

T𝑐
The child is likely to be completed earlier
10 / 24

Continuation Stealing → Joins are Unlikely to be Blocked
Execution of the parent B 𝑝 is delayedcompared to the child B𝑐

Processor 2: steal

The join is likely to be already resolved

B𝑝

T𝑝
Spawn
Processor 1: child first

B𝑐

Join

T𝑐
The child is likely to be completed earlier
10 / 24

Previous Work – Uni-Address Threads [Akiyama and Taura, HPDC ’15]

• Efficient RDMA-based continuation stealing without compiler modification• Basic idea: copy thread stacks to the same virtual address before threads are executed• Good scalability to 4096 cores was reported• No comparison with child stealing or existing distributed task-parallel runtimes

We still don’t know whether distributed continuation stealing is worth implementing

11 / 24

Outline
Background
Joining Threads over RDMA
Evaluation
Performance Analysis of Various Scheduling Policies (Synthetic Benchmark)
Scalability Study with State-of-the-Art Systems (UTS Benchmark)Thread Migration Capability and Futures (LCS Benchmark)Conclusion and Future Work

Performance Improvements for Join

• To evaluate the full potential of continuation stealing, we need to carefully design join
implementations, which were not well considered in previous work
• We introduced two improvements for join
1. How to efficiently resume the continuation of the join when blocked
2. How to efficiently free memory needed for join remotely (see the paper)• In this talk, we will explain the first improvement

12 / 24

Joining Strategy – Overview• In general, there are two strategies to resolve a join in fork-join programs
1. Stalling join: across a join, the executing processor is the same (e.g., Intel TBB)
2. Greedy join: the processor who runs the parent or the child, whichever reaches a join point
later, executes the continuation of the join (e.g., Cilk)• Theoretically, greedy join is considered better than stalling join
• In practice, greedy join is more difficult to implement because it involves thread
migration• The previous work [Akiyama and Taura, HPDC ’15] uses stalling join strategy• We implemented greedy join strategy by using RDMA atomic operations

13 / 24

Stalling Join (Previous Implementation)
The parent reaches the join before its child
Processor 2: steal B 𝑝

T𝑝
Spawn
Processor 1: child first

B𝑐

Join

T𝑐

14 / 24

Stalling Join (Previous Implementation)
The parent reaches the join before its child
Processor 2: steal B 𝑝

T𝑝
Spawn
Processor 1: child first

B𝑐

Join

T𝑐
Even if the child is completed, the continuation of the join must be
resumed by processor 2, who suspended the parent thread
14 / 24

Stalling Join (Previous Implementation)
The parent reaches the join before its child
Processor 2: steal B 𝑝

T𝑝
Spawn
Processor 1: child first

B𝑐

Join

T𝑐
Even if the child is completed, the continuation of the join must be
resumed by processor 2, who suspended the parent thread
14 / 24

Stalling Join (Previous Implementation)
However,
processor
maybebeforebusy when
the join is resolved
The parent
reaches 2thejoin
its child→ execution of the continuation of the join can be delayed
Processor 2: steal B 𝑝

T𝑝
Spawn
Processor 1: child first

B𝑐

Join

T𝑐
Even if the child is completed, the continuation of the join must be
resumed by processor 2, who suspended the parent thread
14 / 24Greedy Join (Our Improvement)

Processor 2: steal B 𝑝

T𝑝
Spawn
Processor 1: child first

B𝑐

Join

T𝑐

15 / 24Greedy Join (Our Improvement)

Processor 2: steal B 𝑝

T𝑝
Spawn
Processor 1: child first

B𝑐

Join

T𝑐
If the child thread is completed later, the continuation of the join isimmediately resumed by Processor 1
15 / 24Greedy Join (Our Improvement)

Processor 2: steal B 𝑝

T𝑝
Spawn
Processor 1: child first

B𝑐

Join

T𝑐
If the child thread is completed later, the continuation of the join isimmediately resumed by Processor 1
15 / 24Greedy Join (Our Improvement)
The parent thread needs to be migrated from
Processor 2 to Processor 1 at join
Processor 2: steal B 𝑝

T𝑝
Spawn
Processor 1: child first

B𝑐

Join

T𝑐
If the child thread is completed later, the continuation of the join isimmediately resumed by Processor 1
15 / 24Greedy Join (Our Improvement)
The parent thread needs to be migrated from
Processor 2 to Processor 1 at join
Processor 2: steal B 𝑝

T𝑝
Spawn

B𝑐

Join

Processor 1: child firstWe devised an efficient RDMA-based implementation of greedy join
T𝑐 utilizing RDMA atomic operations
in a lock-free manner by
If the child thread is completed later, the continuation of the join isimmediately resumed by Processor 1
15 / 24

Outline
Background
Joining Threads over RDMA
Evaluation
Performance Analysis of Various Scheduling Policies (Synthetic Benchmark)
Scalability Study with State-of-the-Art Systems (UTS Benchmark)Thread Migration Capability and Futures (LCS Benchmark)Conclusion and Future WorkEvaluation – Overview
Research questions:
1. How does continuation stealing perform compared with child stealing?
2. Is it practical to use continuation stealing in distributed task-parallel runtimes?
3. How important is thread migration (like greedy join) on distributed memory?

16 / 24

Evaluation – Overview
Research questions:
1. How does continuation stealing perform compared with child stealing?
2. Is it practical to use continuation stealing in distributed task-parallel runtimes?
3. How important is thread migration (like greedy join) on distributed memory?
Summary of our findings:
1. Despite a small increase in steal latency (only less than 20%), continuation stealing
often outperforms child stealing by efficiently resolving joins
2. Even compared with existing bag-of-tasks runtimes (without joins), our system isreasonably fast (96.4% parallel efficiency on 110,592 cores in UTS benchmark)3. Lack of thread migration capability (at either fork or join) leads to bad
performance when we intensively use threads as futures (in LCS benchmark)16 / 24

Experimental Settings• We implemented various strategies over MPI-3 RMA in a C++ library developed in theprevious work (MassiveThreads/DM [Akiyama and Taura, HPDC ’15])• Two variants of continuation stealing (stalling and greedy join)• Two variants of child stealing (RtC and Full), which mimic prevalent implementations– Only the one with better performance (Full) is shown in this presentation
Experimental environment:• ITO-A: ITO supercomputer (subsystem A) at Kyushu University (up to 256 nodes)– Intel Xeon Gold 6154 (36 CPU cores/node), InfiniBand EDR 4x (100 Gbps), Open MPI v5.0.x• Wisteria-O: Wisteria/BDEC-01 Odyssey at the University of Tokyo (up to 2304 nodes)– Fujitsu A64FX (48 CPU cores/node), Tofu Interconnect-D, Fujitsu MPI

17 / 24

Outline
Background
Joining Threads over RDMA
Evaluation
Performance Analysis of Various Scheduling Policies (Synthetic Benchmark)
Scalability Study with State-of-the-Art Systems (UTS Benchmark)Thread Migration Capability and Futures (LCS Benchmark)Conclusion and Future Work

Synthetic Benchmark• Recursive parallel-for benchmark (RecPFor)• Two-way divide-and-conquer + parallel for
loop at each recursion• Common pattern for many
divide-and-conquer algorithms– e.g., quicksort, tree construction (kdtree,
decision tree)• Each leaf task spins for 10 𝜇𝑠 (𝑀 = 10𝜇𝑠)

RecPFor(int n) {if (n == 1) {compute(M); // run for duration of M
} else {for (int k = 0; k < 5; k++) {parallel_for (int i = 0; i < n; i++)compute(M); // run for duration of M}
thread th = spawn([=] { RecPFor(n/2); });RecPFor(n/2);
th.join();}}18 / 24

Synthetic Benchmark – Performance Analysis• We profiled the execution of the RecPFor benchmark (𝑁 = 222 )• ITO-A: 576 cores (16 nodes), Wisteria-O: 1728 cores (36 nodes)

Wi
ste

ria
-

O

ITO

-A

SystemSteal Strategy

Time

# of
Outstanding
Joins# of Steals(Successful)

Avg. Steal
Latency(Successful)

Avg. Stolen
Task Size

Cont. Steal (greedy)Cont. Steal (stalling)Child Steal

8.30 s8.33 s9.31 s

56876
72546
32084174749918070976038858

31.6 𝜇s
30.4 𝜇s29.3 𝜇s1845 bytes
1790 bytes
55 bytesCont. Steal (greedy)Cont. Steal (stalling)Child Steal

5.94 s
5.97 s7.69 s2291542790358602558

17900183086034
15704498

20.4 𝜇s20.6 𝜇s19.9 𝜇s

1139 bytes
1156 bytes
55 bytes

19 / 24

Synthetic Benchmark – Performance Analysis
Continuation stealing outperforms child stealing(We will see a larger performance difference between stalling and greedy join in LCS)

Wi
ste

ria
-

O

ITO

-A

SystemSteal Strategy

Time

# of
Outstanding
Joins# of Steals(Successful)

Avg. Steal
Latency(Successful)

Avg. Stolen
Task Size

Cont. Steal (greedy)Cont. Steal (stalling)Child Steal

8.30 s8.33 s9.31 s

56876
72546
32084174749918070976038858

31.6 𝜇s
30.4 𝜇s29.3 𝜇s1845 bytes
1790 bytes
55 bytesCont. Steal (greedy)Cont. Steal (stalling)Child Steal

5.94 s
5.97 s7.69 s2291542790358602558

17900183086034
15704498

20.4 𝜇s20.6 𝜇s19.9 𝜇s

1139 bytes
1156 bytes
55 bytes

19 / 24

Synthetic Benchmark – Performance Analysis
Child stealing incurs a much larger number of outstanding joins→ less parallelism available
An outstanding join is a join thatis blocked due to a steal event

Wi
ste

ria
-

O

ITO

-A

SystemSteal Strategy

Time

# of
Outstanding
Joins# of Steals(Successful)

Avg. Steal
Latency(Successful)

Avg. Stolen
Task Size

Cont. Steal (greedy)Cont. Steal (stalling)Child Steal

8.30 s8.33 s9.31 s

56876
72546
32084174749918070976038858

31.6 𝜇s
30.4 𝜇s29.3 𝜇s1845 bytes
1790 bytes
55 bytesCont. Steal (greedy)Cont. Steal (stalling)Child Steal

5.94 s
5.97 s7.69 s2291542790358602558

17900183086034
15704498

20.4 𝜇s20.6 𝜇s19.9 𝜇s

1139 bytes
1156 bytes
55 bytes

19 / 24

Synthetic Benchmark – Performance Analysis
Many idle workers

40k

300

30k
An outstanding join
is a join that20k
is blocked due to a10ksteal event

200
100
0

SystemSteal Strategy0

1

2
Time

3

# of
4
5
Outstanding
Time (s)Joins6# of Steals
78.30 s8.33 s9.31 s

56876
72546
32084174749918070976038858

Cont. Steal200(greedy)

5.94 s
5.97 s7.69 s2291542790358602558

17900183086034
15704498

300

Cont. Steal100(stalling)Child Steal 0
0

1

2

3

4

5

8

(Successful)Cont. Steal (greedy)
500Cont. Steal (stalling)
400
Child Steal# of Busy Workers

ria
-

O

ITO

-A

Cont. Steal (greedy):Wi
ste# of Outstanding Joins

400

6

7

Avg. 0Steal
9
Latency(Successful)

Avg. Stolen
Task Size

Many outstanding joins
31.6 𝜇s1845 bytes→ less
50k parallelism
30.4 𝜇s
40k29.3 𝜇s

1790 bytes
55 bytes

20k 𝜇s20.4
10k 𝜇s
20.6
0 𝜇s
19.9

1139 bytes
1156 bytes
55 bytes

30k

8

9

# of Outstanding Joins# of Busy Workers

Child
stealing
Child
Steal: incurs a much larger number of outstanding joins
500 parallelism available
50k→ lessTime (s)19 / 24

Synthetic Benchmark – Performance Analysis• less parallelism → larger number of steals• Greedy join is the most efficient, as it can immediately resolve outstanding joins

Wi
ste

ria
-

O

ITO

-A

SystemSteal Strategy

Time

# of
Outstanding
Joins# of Steals(Successful)

Avg. Steal
Latency(Successful)

Avg. Stolen
Task Size

Cont. Steal (greedy)Cont. Steal (stalling)Child Steal

8.30 s8.33 s9.31 s

56876
72546
32084174749918070976038858

31.6 𝜇s
30.4 𝜇s29.3 𝜇s1845 bytes
1790 bytes
55 bytesCont. Steal (greedy)Cont. Steal (stalling)Child Steal

5.94 s
5.97 s7.69 s2291542790358602558

17900183086034
15704498

20.4 𝜇s20.6 𝜇s19.9 𝜇s

1139 bytes
1156 bytes
55 bytes

19 / 24

Synthetic Benchmark – Performance Analysis• Cont. steal needs to copy the call stack → larger stolen task size
• Nevertheless, the steal latency is only less than 20% longer than child stealing

Wi
ste

ria
-

O

ITO

-A

SystemSteal Strategy

Time

# of
Outstanding
Joins# of Steals(Successful)

Avg. Steal
Latency(Successful)

Avg. Stolen
Task Size

Cont. Steal (greedy)Cont. Steal (stalling)Child Steal

8.30 s8.33 s9.31 s

56876
72546
32084174749918070976038858

31.6 𝜇s
30.4 𝜇s29.3 𝜇s1845 bytes
1790 bytes
55 bytesCont. Steal (greedy)Cont. Steal (stalling)Child Steal

5.94 s
5.97 s7.69 s2291542790358602558

17900183086034
15704498

20.4 𝜇s20.6 𝜇s19.9 𝜇s

1139 bytes
1156 bytes
55 bytes

19 / 24

Synthetic Benchmark – Performance Analysis• Cont. steal needs to copy the call stack → larger stolen task size
• Nevertheless, the steal latency is only less than 20% longer than child stealing

System# ofAvg. Steal# of Steals
Avg. Stolen
Outstanding
Latency(Successful)
Task Size
Despite a small increase in steal latency,
continuation
stealing
has
an
Joins
(Successful)
Steal Strategy

Time

Wi
ste

ria
-

O

ITO

-A

overall performance benefit
Cont. Steal (greedy)Cont. Steal (stalling)Child Steal

8.30 s8.33 s9.31 s

56876
72546
32084174749918070976038858

31.6 𝜇s
30.4 𝜇s29.3 𝜇s1845 bytes
1790 bytes
55 bytesCont. Steal (greedy)Cont. Steal (stalling)Child Steal

5.94 s
5.97 s7.69 s2291542790358602558

17900183086034
15704498

20.4 𝜇s20.6 𝜇s19.9 𝜇s

1139 bytes
1156 bytes
55 bytes

19 / 24

Outline
Background
Joining Threads over RDMA
Evaluation
Performance Analysis of Various Scheduling Policies (Synthetic Benchmark)
Scalability Study with State-of-the-Art Systems (UTS Benchmark)Thread Migration Capability and Futures (LCS Benchmark)Conclusion and Future Work

Unbalanced Tree Search (UTS) Benchmark• A widely used benchmark to measure the load balancing capability of runtime systems• X-axis: the number of processes, up to 110,592 cores (2304 nodes)• Y-axis: throughput of the benchmark (higher is better)Throughput (nodes/s)• Our system could achieve 96.4% parallel efficiency on 110,592 cores
Ours (T1WL)
Ours (T1XXL)
Ours (T1L)

100G

Settings:• UTS counts the number of all nodes in an unbalanced tree in parallel

10G• Throughput: the number of counted nodes per second
1G• Ideal throughput (the straight line) is calculated by serial performance• Tree sizes: T1L < T1XXL < T1WL

100M

• Cont. steal (greedy join)
100

1K

10K

100K

# of processes

Fig. Result on Wisteria-O

20 / 24Comparison with Existing Bag-of-Tasks Runtimes in UTS• Also compared our runtime with existing systems on ITO-A (with InfiniBand)• Competitors: three state-of-the-art work-stealing systems based on bag-of-tasks– Child stealing, no join primitive → global termination detection is needed• Our system and SAWS [Cartier+, ICPP ’21] → RDMA-based, good scalability• Charm++ and X10/GLB → no RDMA, worse scalability

1G

10G

1G

100M

100M
100

1K

10K

# of processes

Fig. Our Runtime System

1G
100M
Charm++ (T1WL)
Charm++ (T1XXL)
Charm++ (T1L)

10M
1M

100

1K

# of processes

Fig. SAWS

10K

X10 (T1WL)
X10 (T1XXL)
X10 (T1L)

100G

10G

Throughput (nodes/s)

Throughput (nodes/s)

Throughput (nodes/s)

10G

100G

SAWS (T1WL)SAWS (T1XXL)
SAWS (T1L)

100G

Throughput (nodes/s)

Ours (T1WL)
Ours (T1XXL)
Ours (T1L)

100G

100

1K

10G

1G

100M
10K

100

1K

# of processes# of processes

Fig. Charm++

Fig. X10/GLB

10K

21 / 24Comparison with Existing Bag-of-Tasks Runtimes in UTS• Also compared our runtime with existing systems on ITO-A (with InfiniBand)
Summarizing,
our state-of-the-art
system• Competitors:
threework-stealing systems based on bag-of-tasks• Has more general synchronization (join) and thread migration capability– Child stealing, no join primitive → global termination detection is needed
Performs
well asor even better than bag-of-tasks counterparts• Our•system
andas
SAWS
[Cartier+, ICPP ’21] → RDMA-based, good scalability• Charm++ and X10/GLB → no RDMA, worse scalability

1G

10G

1G

100M

100M
100

1K

10K

# of processes

Fig. Our Runtime System

1G
100M
Charm++ (T1WL)
Charm++ (T1XXL)
Charm++ (T1L)

10M
1M

100

1K

# of processes

Fig. SAWS

10K

X10 (T1WL)
X10 (T1XXL)
X10 (T1L)

100G

10G

Throughput (nodes/s)

Throughput (nodes/s)

Throughput (nodes/s)

10G

100G

SAWS (T1WL)SAWS (T1XXL)
SAWS (T1L)

100G

Throughput (nodes/s)

Ours (T1WL)
Ours (T1XXL)
Ours (T1L)

100G

100

1K

10G

1G

100M
10K

100

1K

# of processes# of processes

Fig. Charm++

Fig. X10/GLB

10K

21 / 24

Outline
Background
Joining Threads over RDMA
Evaluation
Performance Analysis of Various Scheduling Policies (Synthetic Benchmark)
Scalability Study with State-of-the-Art Systems (UTS Benchmark)Thread Migration Capability and Futures (LCS Benchmark)Conclusion and Future Work

Preliminaries: Fork-Join and Futures• Our thread implementation is not only for fork-join but also for futures• Fork-join: a thread must be joined by its parent (parallelism is nested)• Future: a thread (called future) can be joined at any point (not strictly nested)• Our longest common subsequence (LCS) benchmark intensively uses futures– It combines recursive space decomposition and futures to represent true task dependencies– Lack of thread migration capability easily falls into bad load balancing in this benchmark

22 / 24

Results of the LCS Benchmark• We compared three scheduling policies with different thread migration capabilities• Child stealing: No thread migration• Cont. Steal (stalling): Migration at steal• Cont. Steal (greedy): Migration at steal + Migration at join
• Lack of either migration capability led to much worse performance (due to badload balancing)
Settings:

Tab. Execution times with 576 cores (16 nodes).

• Run on 16 nodes of ITO-A

SizeCont. Steal (greedy)Cont. Steal (stalling)Child Stealing

218

0.569 s45.9 s3.44 s433 s93.1 s2.11 ×104 s

222• Find an LCS length of 𝑁
1-byte characters (randomly
generated)• Serial cutoff size: 29

23 / 24

Outline
Background
Joining Threads over RDMA
Evaluation
Performance Analysis of Various Scheduling Policies (Synthetic Benchmark)
Scalability Study with State-of-the-Art Systems (UTS Benchmark)Thread Migration Capability and Futures (LCS Benchmark)Conclusion and Future WorkSummary
Conclusion:

Our artifact is available at:https://github.com/s417-lama/cluster22-contsteal-artifact• We introduced an efficient RDMA-based greedy join implementation• Despite a small increase in steal latency, continuation stealing has an overall
performance benefit in nested fork-join programs• Thread migration (both continuation stealing and greedy join) is particularly importantfor programs with a complicated dependency pattern
Future Work:• Integrate with PGAS to handle global data
– Current system only allows function arguments and return values for data exchange• Apply memory hierarchy-aware scheduling to improve data locality– e.g., Almost Deterministic Work Stealing (ADWS) [Shiina and Taura, SC ’19 and TPDS ’22]

24 / 24