階層的逐次計算のTascell言語による並列化/
HOPE言語による耐障害性
八杉 昌宏 (九州工業大学)(平石 拓(京都大学)らとの共同研究)

Nov. 2019

Masahiro YASUGI1

M. Yasugi’s Backgrounds
Developed programming language systems◦ ABCL/EM4 [ICS 1992, PACT 1994]◦ Implementing ABCL (concurrent OO language) for a data-driven parallel computer◦ OPA [PACT 1998, PDSIA 1999, ISHPC 2003]◦ Multiple threads over passive, adaptive objects◦ Synchronization and exception handing using dynamic scope◦ Lazy Task Creation with lazy frame conversion◦ Tascell [PPoPP 2009, P2S2 2016]◦ “logical thread”-free efficient work-stealing framework◦ Backtracking-based load balancing with on-demand concurrency◦ Only when requested, each worker spawns a real task by temporarily backtracking and restoring its oldest
task-spawnable state.
◦ Using mechanisms for legitimate execution stack access◦ HOPE [ICPP 2019 @Kyoto, Japan]  Tascell の後はこの話

Nov. 2019

Masahiro YASUGI

2

ここでTascellの話
Nov. 2019

Masahiro YASUGI

3

タスク並列言語Tascellの設計・実装・応用
平石 拓（学術情報メディアセンター スーパーコンピューティング研究分野）

（狭義の・ここで扱う）タスク並列言語• 多くの場合，既存の逐次言語（C，C++，Javaなど）の拡張• 並列に実行可能な処理をタスクとして生成– 通常は計算資源（コア）数より非常に大きな数のタスクを同時に生成
 タスク生成のコスト・オーバーヘッドの削減が処理系実装上重要• タスクの同期ポイントを指定• どのタスクをどのコアが実行するかは，言語処理系が自動的に，かつ動的に決定する
OpenMP Task, Cilk (Plus), Intel TBB*, X10, Chapel, MultiLisp,
Massive Threads*, Tascell– *は言語ではなくライブラリCilk• おそらく最も有名なタスク並列言語– Frigo, M., Leiserson, C. E. and Randall, K. H.: The Implementation of theCilk-5 Multithreaded Language, Proceedings of the ACM SIGPLAN 1998

• もともとMITで開発（Cilk, MIT Cilk）→ ベンチャー企業立ち上げ (Cilk++）→ Intelが買収し，現在はIntel C++ Compilerの一部（Cilk Plus）• Cilk Plusの仕様自体はオープン，現在はGCCでも利用可能• Lazy Task Creation (LTC)という実装手法により，タスク生成にかかるコストを（例えばOSのスレッド生成と比べて）大幅に削減

Cilkのプログラム例• Fibonacci using a doubly recursive algorithm– タスク並列言語のベンチマークプログラムの定番※このプログラム自体に実用的な意味はない（明らかに効率が悪い）
cilk int fib(int n)spawn内とspawn以下の計算が{並列実行可能if (n <= 2)return (1);else {
int x, y;x = spawn fib(n - 1);
y = spawn fib(n - 2);
sync;
同一スコープ内の全てのspawnの終了
return (x + y);を待ち合わせる}}
Fibの図： http://www.introprogramming.info/english-intro-csharp-book/read-online/chapter-10-recursion/

例：Pentomino• Pentomino Puzzle全解探索– Pentomino: a block consists of five attached squares– Fill a 6×10 rectangular board with the 12 different pentominos• 並列バックトラック探索で解きたい– データ並列処理として記述することが困難で，タスク並列言語が得意な例• 考え方の大部分は，実用的な探索アルゴリズムにも適用可能

Cilkプログラムの動作と問題点• Usually spawn a logical thread andexecute it immediately• Full task creation (from a stealablecontinuation) is delayed

spawn alogical thread

wn athreadstealable continuation

stealable continuation

stealable continuation
問題点 （削減されたとはいえ）タスク生成・維持コストは無視できない
プログラムの意味上，spawn先とspawn元は並行に実行されうるため，探索ステップごとにワークスペース（ここではボード）の複製を作る必要がある

タスク並列言語Tascell [PPoPP ’09]
• Backtracking-based load balancing approach• 並列性の発生そのものを，必要時まで遅らせる
parallelizable

sequential computation

fork

Anotherworker

Tascellプログラムの動作

computesequentially

Tascellプログラムの動作
make a copy of the board
spawn a task

backtrack temporarily
removing pieces
send the task

Tascellプログラムの動作
make a copy of the board
spawn a task

return from backtracking
setting the removed pieces

send the task

「並列化のコストを下げる」のではなく，「必要時までそもそも並列化しない」
 無駄なタスク生成のコストがかからない ワークスペース（ボード）の複製を真に必要になるまで遅延させることができる
resume the worker’s own task

Tascell言語• Cの拡張並列言語• 並列for構文• 一時的バックトラック– ワーカはタスク要求がない限り（spawnせず）逐次実行– 他のワーカからタスク要求を受けると• 最古の並列forまで一時的にバックトラックし，• タスクを生成した後• 一時的バックトラックから復帰して自らの計算を再開する– 「一時的バックトラック」「一時的バックトラックからの復帰」時の処理を記述するための，dynamic_wind構文を備える（c.f., Scheme）

Pentomino全解探索 in Tascell
worker int search (k, j0, j1, j2, task pentomino *tsk){
for (int p : j1, j2) {/* 並列for：ピースの種類 */for (d=0 ; d<4 ; d++) { /* 逐次for：ピースの方向 */dynamic_wind {ピース p を方向 d で置く} {if (解が見つかった？) s++;elses += search(…); // recursive call} {ピース p を取り除く}}} handles pentomino (int i1, int i2) { /* i1--i2 is a subrange of j1--j2 *//* executed to initialize :in fields of a spawned task */{ copy_piece_info (this.a, tsk->a); copy_board (this.b, tsk->b); this.k=k; this.i0=j0; this.i1=i1; this.i2=i2; }/* executed to get the result by referring :out fields */s+=this.s;}return s; }task_exec pentomino { return search(…); }Background
High productivity, scalability, load balancing, and fault tolerance
to develop high performance and robust applications including
irregular ones
for massively and extremely parallel computing systems.
Work-stealing frameworks (Lazy Task Creation, Cilk, Tascell, …)◦ provide good load balancing for many parallel applications, including irregularones written in a divide-and-conquer style◦ However, work-stealing frameworks enhanced by fault-tolerant features (suchas checkpointing) do not always work wellNov. 2019

Masahiro YASUGI4Contributions
We propose a new ``hierarchical work omission''-based parallel execution
model called HOPE.
◦ HOPE programmers’ task is to specify◦ which regions in imperative code can be executed in sequential but arbitrary order and◦ how their partial results can be accessed.

◦ Every worker has the entire work of the sequential program with its own planned
execution order (SPMO; single program multiple order).
◦ Workers (and runtime systems) automatically exchange partial results to omithierarchical subcomputations.

We discuss how to implement this new idea as an efficient, scalable andfault-tolerant dynamic load balancing programming/execution framework◦ Fault tolerance without a single point of failure by assuming fail-stops◦ the language, compiler, and runtime system.

Nov. 2019

Masahiro YASUGI

5

“HOPE” is NOT what you think
A HOPE worker does
◦ NOT have only an assigned (fixed) part of the entire work
◦ NOT wait for slow workers◦ NOT have a fixed communication pattern◦ NOT spawn a task/thread◦ NOT steal a task/thread◦ NOT wait for a result◦ NOT broadcast a result◦ NOT recover/restart (a stopped part)◦ NOT save/restore/rollback an execution stateNov. 2019

Masahiro YASUGI

6

Basic Idea (1/3)
A worker performs a divide-and-conquer computation sequentially.
worker A

Nov. 2019

Masahiro YASUGI

7

Basic Idea (2/3; full redundancyfor fault tolerance)
Every worker performs the same program with its own planned
execution order (SPMO; single program multiple order).
worker B
worker A

Nov. 2019

Masahiro YASUGI

8Basic Idea (3/3; parallel speedups)
Exchange partial results for hierarchical omission
worker B

worker A

Nov. 2019

Masahiro YASUGI

9Our Approach
The HOPE Language: Directives:◦ Arbitrary execution order (≠ spawning concurrent tasks/threads)◦ How to access to partial results

Pre-shared plans:◦ Every worker has its own planned execution order of a hierarchical computation

Variable-length addresses to identify hierarchical subcomputations
Compiler (translator)◦ into C with nested functions (L-closures [Yasugi+, CC 2006])◦ We solve dilemmas: 3 execution modes and dynamic execution mode switching

Runtime: Message Mediation Systems (MMSs) (distributed and federated)◦ as a local storage and an automatic exchanger of messages of partial results
Nov. 2019

Masahiro YASUGI

10Outline
Motivating Example
The HOPE language
Our Approach
Implementation◦ Message Mediation Systems◦ Pre-shared Plans◦ The Compiler

Evaluation
Discussion
Nov. 2019

Masahiro YASUGI

11

Motivating Example
A doubly-recursive computation for Fibonacci(typically employed as an irregular example; NOT a fast algorithm)
int fibi (int n) {if (n <= 2) return 1;
int r0, r1;
r0 = fib 2i (n - 1);
r1 = fib2i+1(n - 2);
return r0 + r1;}

Nov. 2019suffix i only forpresentation

for identifying
subcomputations

r0=fib2(50)fib1(51)
r1=fib3(49)r0=fib4(49)r1=fib7(47)r0=fib8(48)r1=fib15(45)Masahiro YASUGI

12

Hierarchical subcomputations in fib1(51)and their depths
depth 0s1: fib1(51)1

s2: r0=fib2(50)23s4: r0=fib4(49)s8: fib8s9: fib9s5: r1=fib5(48)s10: …

s11: …

s6: r0=fib6(48)s12: …

s13: …

s7: r1=fib7(47)s14: …

s15: …

...

...

...

...

…

49 s249: r0=fib249 (2)Nov. 2019s3: r1=fib3(49)s249+1: r1=fib249+1 (1)Masahiro YASUGI13

An existing work-stealing framework:
Tascell [Hiraishi,Yasugi+, PPoPP 2009](On demand) concurrency (between thief and victim)
task tfib { in: int n; out: int r };worker int fib (int n) {if (n <= 2) return 1;
int r0, r1;
do_two// Tascell’s constructr0 = fib(n - 1);
r1 = fib(n - 2); // skip if a task tfib is spawned
handles tfib {{ this.n = n - 2; } // for spawning a task tfib
{ r1 = this.r; }// merge the result of tfib}
return r0 + r1;}

Nov. 2019

Masahiro YASUGI

steal and spawn

14

1
2

3

Worker Worker
W0
W1Even(W0)withisThe root
4
5
6
7
save/restarta singlepoint of
8 9 A B C failure
D E F
A large portion ofdivide-and-conquer
3computation may
6
7
be lost5
A B

Worker Worker
W2
W3Workstealing

C D E F
Nov. 2019

7E F

Masahiro YASUGI

15

The HOPE Language
Nov. 2019

Masahiro YASUGI

16

w/o concurrency :Subcomputations may (re)use a single workspace

The HOPE Language
Directives
int fib (int n) {if (n <= 2) return 1;
int r0, r1;#pragma hope do_two // arbitrary order#pragma hope omissible result(r0)r0 = fib(n - 1); // may exchange partial result r0 for omission#pragma hope omissible result(r1)r1 = fib(n - 2); // may exchange partial result r1 for omission
return r0 + r1;}
◦ Results are not always on the left-hand side.
Nov. 2019

Masahiro YASUGI17

Our Approach
Nov. 2019

Masahiro YASUGI

19

Worker Worker
W0W1

1243567678 9 A B C D E F
Nov. 20195678 9 A B C D E FWorker Worker
W2W3

35

3No single point of failure24248 9 A B C D E F
1

1

fully
redundant
execution
Masahiro YASUGI12435678 9 A B C D E F
20Worker Worker
W0W11243567678 9 A B C D E F
Nov. 20195678 9 A B C D E FWorker Worker
W2
W3

353No single point of failure24248 9 A B C D E F
11fullyredundant
execution
Masahiro YASUGI

12435678 9 A B C D E F
21

Worker Worker
W0
W1

1243567678 9 A B C D E F
Nov. 20195678 9 A B C D E FWorker Worker
W2
W3

353No single point of failure24248 9 A B C D E F
11fullyredundant
execution
Masahiro YASUGI12435678 9 A B C D E F
22

Worker Worker
W0
W1(000)(011)

12435670
20-first or 1-first 4
at each depth

8 9 A B C D E F

10-first
3151

61-first
78 9 A B C D E F

0-first0
SPMO (single program multiple order)

12456

1

Worker Worker
W2
W3(101)(110)

3

1-first

712
43
56

1
7

Each worker’s
0
8 9 A B C D E F planned order 8 9 A B C D E F
1Nov. 2019

Masahiro YASUGI

23

Worker Worker
W0W1

123Exchanging
4567partialresults
8 9 A B C D E F
123Nov. 201956247Masahiro YASUGI

35678 9 A B C D E F
1Worker Worker
W2W3Hierarchicalomission
8 9 A B C D E F
412435678 9 A B C D E F
24

Another example of hierarchical omission
When ignoring depth 3 and more
Worker W0(000)4Worker W1(011)5Worker W2(101)6Worker W3(110)7Nov. 2019

5476674570654Masahiro YASUGI04211105631
70 10 1 0 1 0 1
8 9 A B C D E F

25

Implementation
Nov. 2019

Masahiro YASUGI27

The HOPE Compiler
Translation of a HOPE program into a C program with MMS API calls
Naive translation would involve the following issues to be addressed:
Dilemma 1 (collaboration cost):
 Hierarchical omission of subcomputations
 Overheads of writing/checking partial results
 Costs of maintaining the “current” VL address

Dilemma 2 (multiple-order cost):

 SPMO reduces overlapping of subcomputations
 Costs of order selection
 Branch-predictor unfriendly

Nov. 2019

Masahiro YASUGI

00421110563170 10 1 0 1 0 1
8 9 A B C D E F32

Dynamic execution mode switchingwith Nested functions
The “check” mode
The “non-check” mode

When no longer“alone”

The “work-first” mode

Dynamic execution mode switching (DEMS)
10 times◦ Changes a past choice of modes◦ Legitimate execution stack access [Yasugi+, CC 2006]
to handle VL addresses and partial results
Nov. 2019

Masahiro YASUGI

35

Evaluation
Nov. 2019

Masahiro YASUGI36

Environment/Benchmark

No cut-offs(No thresholds)

The K computer (per node)

Benchmarks◦ SPARC64 VIIIfx 2GHz 8-core◦ Tofu Interconnect◦ FujitsuMPI （OpenMPI based）◦ Fujitsu C/C++ Compiler 1.2.0◦ Fib(n)Fibonacci◦ Nq(n)n-queen problem◦ Pen(n)Pentomino problem◦ AreaSum(n) AreaSum◦ MatMul(n) Matrix Multiplication◦ with -O2 optimizers◦ Nested function

Fault injection◦ LW-SC [Hiraishi+ 2006]

Employing◦ 1, 2, 4, 8, 16,…, 256, 512, 1024 nodes◦ 7 workers/nodeNov. 2019◦ FT(n) one out of n workers◦ simulated by discarding incoming/outgoing system messages

Compare HOPE and Tascell

Masahiro YASUGI37

Ideal speedup(to serial C)

Tascell
HOPE
FT(64)
FT(4)serial C

1000 sTascell
HOPE
FT(4)FT(64)

1 second

HOPE

Nov. 2019

FT(4)Masahiro YASUGIFT(64)

Tascell38

Other Evaluations

HOPE

Tascell

Cilk Plus

w/DEMSw/o
DEMS>75x faster execution>2.8x faster execution
Nov. 2019

Masahiro YASUGI

39

Summary: What is “HOPE”?
Every HOPE worker (with its runtime system)◦ has the entire work of a divide-and-conquer program to compute the resultindependently◦ performs the entire hierarchical computation sequentially◦ uses its own fixed/planned execution order of the hierarchical computation◦ MAY omit a hierarchical subcomputation if the result is locally available(handles the result of a subcomputation as an eliminator of thesubcomputation)◦ MAY exchange the result of a subcomputation with only relevant workers◦ CAN guess the current participants of a subcomputation based on local
availability of partial results and the entire pre-shared plans
Nov. 2019

Masahiro YASUGI43