プログラム実行に潜むべき乗則について

1.2K Views

March 23, 23

スライド概要

2023/3/13「TIER IV Computing System Workshop 2023」
発表者:佐々木 広先生 (東京工業大学 准教授)

profile-image

TIER IV(ティアフォー)は、「自動運転の民主化」をビジョンとし、Autowareを活用したソフトウェアプラットフォームと統合開発環境を提供しています。 #Autoware #opensource #AutonomousDriving #deeptech

シェア

埋め込む »CMSなどでJSが使えない場合

関連スライド

各ページのテキスト
1.

プログラム実行に潜む べき乗則について 佐々木広(東京工業大学、Tier IV) @TIER IV Computing System Workshop 2023 (16:40~17:20)

2.

自己紹介 名前:佐々木広(ささきひろし) email: sasaki@ict.e.titech.ac.jp web: https://hiroshi-sasaki.github.io 所属:東京工業大学 工学院 情報通信系 興味:計算機アーキテクチャ、コンピュータセキュリティ 今日:IISWC 2017 で発表した論文の話をします IISWC: IEEE International Symposium on Workload Characterization 2

3.

Why Do Programs Have Heavy Tails? Hiroshi Sasaki* Fang-Hsiang Su* Teruo Tanimoto† Simha Sethumadhavan* *Columbia University †Kyushu University

4.

A New Program Characterization Approach Program characterization is central to furthering computer architecture 90-10 rule (locality of reference) etc We view programs as social networks Leads to a discovery of phenomenon that is: Pervasive and Unique 4

5.

Programs Have Heavy Tails When programs are viewed as social networks Small number of instructions send outputs to a tremendous number of instructions What this means: Small number of instructions are responsible for large effects Intervention on these instructions will be disproportionately effective 5

6.

Establishing Pervasiveness and Uniqueness Heavy tails phenomenon is: 1. pervasive - widely present in programs Sensitivity study 2. fundamental - stems from how programmers structure programs Generative model 3. unique - offers new lens to view programs Comparison with previous work 6

7.

Rest of the Talk 1. Background on program social networks 2. Pervasiveness, fundamentality and uniqueness of heavy tails Sensitivity study Generative model Comparison with previous work 3. One potential application 4. Conclusions 7

8.

Rest of the Talk 1. Background on program social networks 2. Pervasiveness, fundamentality and uniqueness of heavy tails Sensitivity study Generative model Comparison with previous work 3. One potential application 4. Conclusions 7

9.

Social Network Network (or graph) structure that depicts personal relations Node is an individual Edge is a relation Connected nodes can be considered friends A directed edge can represent relations like influencer and influencee Influencers have large outdegree (number of outgoing edges) Social network analysis Density, centrality, indegree and outdegree 8

10.

Program Social Network Node is a static instruction Directed edge is either a dynamic control flow or data flow 0 sw 1 addi 2 lw 3 addi 4 Loop: lw 5 add 6 addi 7 bne 8 sw Array, 0xC001CAFE R1, R0, $0 R2, $10 R4, R0, $0 R3, R1[Array] R4, R4, R3 R1, R1, $1 R1, R2, Loop [Sum], R4 9

11.

Program Social Network Node is a static instruction Directed edge is either a dynamic control flow or data flow 0 0 sw 1 addi 2 lw 3 addi 4 Loop: lw 5 add 6 addi 7 bne 8 sw Array, 0xC001CAFE R1, R0, $0 R2, $10 R4, R0, $0 R3, R1[Array] R4, R4, R3 R1, R1, $1 R1, R2, Loop [Sum], R4 1 2 3 4 5 6 7 8 9

12.

Program Social Network Node is a static instruction Directed edge is either a dynamic control flow or data flow 0 0 sw 1 addi 2 lw 3 addi 4 Loop: lw 5 add 6 addi 7 bne 8 sw Array, 0xC001CAFE R1, R0, $0 R2, $10 R4, R0, $0 R3, R1[Array] R4, R4, R3 R1, R1, $1 R1, R2, Loop [Sum], R4 1 2 3 4 5 6 7 8 9

13.

Program Social Network Node is a static instruction Directed edge is either a dynamic control flow or data flow 0 0 sw 1 addi 2 lw 3 addi 4 Loop: lw 5 add 6 addi 7 bne 8 sw Array, 0xC001CAFE R1, R0, $0 R2, $10 R4, R0, $0 R3, R1[Array] R4, R4, R3 R1, R1, $1 R1, R2, Loop [Sum], R4 1 2 3 4 5 6 7 8 9

14.

Program Social Network Node is a static instruction Directed edge is either a dynamic control flow or data flow 0 0 sw 1 addi 2 lw 3 addi 4 Loop: lw 5 add 6 addi 7 bne 8 sw Array, 0xC001CAFE R1, R0, $0 R2, $10 R4, R0, $0 R3, R1[Array] R4, R4, R3 R1, R1, $1 R1, R2, Loop [Sum], R4 1 2 3 4 5 6 7 8 9

15.

Program Social Network Node is a static instruction Directed edge is either a dynamic control flow or data flow 0 0 sw 1 addi 2 lw 3 addi 4 Loop: lw 5 add 6 addi 7 bne 8 sw Array, 0xC001CAFE R1, R0, $0 R2, $10 R4, R0, $0 R3, R1[Array] R4, R4, R3 R1, R1, $1 R1, R2, Loop [Sum], R4 1 2 3 4 5 6 7 8 9

16.

Program Social Network Node is a static instruction Directed edge is either a dynamic control flow or data flow 0 0 sw 1 addi 2 lw 3 addi 4 Loop: lw 5 add 6 addi 7 bne 8 sw Array, 0xC001CAFE R1, R0, $0 R2, $10 R4, R0, $0 R3, R1[Array] R4, R4, R3 R1, R1, $1 R1, R2, Loop [Sum], R4 1 2 3 4 5 6 7 8 9

17.

Program Social Network Node is a static instruction Directed edge is either a dynamic control flow or data flow 0 0 sw 1 addi 2 lw 3 addi 4 Loop: lw 5 add 6 addi 7 bne 8 sw Array, 0xC001CAFE 1 R1, R0, $0 2 R2, $10 R4, R0, $0 3 R3, R1[Array] Program Social Network R4, R4, R3 Control flow + Register data flow R1, R1, $1 R1, R2, Loop [Sum], R4 4 5 6 7 8 9

18.

Program Social Network Node is a static instruction Directed edge is either a dynamic control flow or data flow 0 0 sw 1 addi 2 lw 3 addi 4 Loop: lw 5 add 6 addi 7 bne 8 sw Array, 0xC001CAFE R1, R0, $0 R2, $10 R4, R0, $0 R3, R1[Array] R4, R4, R3 R1, R1, $1 R1, R2, Loop [Sum], R4 1 2 3 4 5 6 7 8 9

19.

Program Social Network Node is a static instruction Directed edge is either a dynamic control flow or data flow 0 0 sw 1 addi 2 lw 3 addi 4 Loop: lw 5 add 6 addi 7 bne 8 sw Array, 0xC001CAFE R1, R0, $0 R2, $10 R4, R0, $0 R3, R1[Array] R4, R4, R3 R1, R1, $1 R1, R2, Loop [Sum], R4 1 2 3 4 5 6 7 8 9

20.

Program Social Network Node is a static instruction Directed edge is either a dynamic control flow or data flow 0 0 sw 1 addi 2 lw 3 addi 4 Loop: lw 5 add 6 addi 7 bne 8 sw Array, 0xC001CAFE 1 R1, R0, $0 2 R2, $10 R4, R0, $0 3 R3, R1[Array] Program Social Network R4, R4, R3 Control flow + Memory data flow R1, R1, $1 R1, R2, Loop [Sum], R4 4 5 6 7 8 9

21.

Program Social Network Analysis libquantum 10

22.

Program Social Network Analysis libquantum 10

23.

Program Social Network Analysis Histogram libquantum 10

24.

Program Social Network Analysis Histogram libquantum 10 CDF

25.

Program Social Network Analysis Histogram CDF libquantum CCDF 10

26.

Program Social Network Analysis Histogram CDF libquantum Log CCDF Log 10 CCDF

27.

Program Social Network Analysis Histogram CDF libquantum Log CCDF Log 10 CCDF

28.

Program Social Network Analysis Histogram CDF libquantum Log Power Law (also Heavy Tails) CCDF Log 10 CCDF

29.

Sample Results from SPEC CPU2006 x86-64 ISA level program social networks All have heavy tails; more than half follow power laws 11

30.

Rest of the Talk 1. Background on program social networks 2. Pervasiveness, fundamentality and uniqueness of heavy tails Sensitivity study Generative model Comparison with previous work 3. One potential application 4. Conclusions 12

31.

Rest of the Talk 1. Background on program social networks 2. Pervasiveness, fundamentality and uniqueness of heavy tails Sensitivity study Generative model Comparison with previous work 3. One potential application 4. Conclusions 12

32.

Evaluation Network types: control flow + memory or register data flow Workloads: 10 SPEC INT, 11 SPEC FP, 8 CortexSuite, 7 DaCapo, SQLite,V8 Inputs: gobmk (4), perlbench (7), CortexSuite (3),V8 (8) Compilation: GCC and LLVM with -O0, -O1, -O2, -O3 ISA: x86-64 ISA, LLVM IR and JVM instruction set Time varying behavior 13

33.

Are Heavy Tails Due to Workloads? Workloads: CortexSuite, SPEC CPU2006,V8 and SQLite Network types: control + memory or register data flow 14

34.

Are Heavy Tails Due to Workloads? Workloads: CortexSuite, SPEC CPU2006,V8 and SQLite Network types: control + memory or register data flow 14

35.

Are Heavy Tails Due to Workloads? Workloads: CortexSuite, SPEC CPU2006,V8 and SQLite Network types: control + memory or register data flow NO: heavy tails are workload independent 14

36.

Are Heavy Tails due to Inputs? Inputs: various input sizes and input sets 15

37.

Are Heavy Tails due to Inputs? Inputs: various input sizes and input sets 15

38.

Are Heavy Tails due to Inputs? Inputs: various input sizes and input sets NO: heavy tails are input independent 15

39.

Are Heavy Tails Due to Compilation? Compiler: GCC or LLVM Optimization level: -O0, -O1, -O2 or -O3 16

40.

Are Heavy Tails Due to Compilation? Compiler: GCC or LLVM Optimization level: -O0, -O1, -O2 or -O3 16

41.

Are Heavy Tails Due to Compilation? Compiler: GCC or LLVM Optimization level: -O0, -O1, -O2 or -O3 NO: heavy tails are compilation independent 16

42.

Are Heavy Tails Due to the ISA? ISA: LLVM IR and JVM instruction set SPEC CPU2006 and CortexSuite at the LLVM IR level (infinite registers) DaCapo at the JVM instruction set level (stack) 17

43.

Are Heavy Tails Due to the ISA? ISA: LLVM IR and JVM instruction set SPEC CPU2006 and CortexSuite at the LLVM IR level (infinite registers) DaCapo at the JVM instruction set level (stack) 17

44.

Are Heavy Tails Due to the ISA? ISA: LLVM IR and JVM instruction set SPEC CPU2006 and CortexSuite at the LLVM IR level (infinite registers) DaCapo at the JVM instruction set level (stack) NO: heavy tails are ISA independent 17

45.

Are Heavy Tails Phase Dependent? 18

46.

Are Heavy Tails Phase Dependent? Time 18

47.

Are Heavy Tails Phase Dependent? Time xalancbmk Memory Register calculix Memory Register 18

48.

Are Heavy Tails Phase Dependent? Time xalancbmk Memory Register calculix NO: heavy tails are phase independent Memory Register 18

49.

Evaluation Network types: control flow + memory or register data flow Workloads: 10 SPEC INT, 11 SPEC FP, 8 CortexSuite, 7 DaCapo, SQLite,V8 Inputs: gobmk (4), perlbench (7), CoretexSuite (3),V8 (8) Compilation: GCC and LLVM with -O0, -O1, -O2, -O3 ISA: x86-64 ISA, LLVM IR and JVM instruction set Time varying behavior 19

50.

Evaluation Network types: control flow + memory or register data flow Workloads: 10 SPEC INT, 11 SPEC FP, 8 CortexSuite, 7 DaCapo, SQLite,V8 Heavy tails phenomenon is Compilation: GCC and LLVM with -O0, -O1, -O2, -O3 pervasive Inputs: gobmk (4), perlbench (7), CoretexSuite (3),V8 (8) ISA: x86-64 ISA, LLVM IR and JVM instruction set Time varying behavior 19

51.

Rest of the Talk 1. Background on program social networks 2. Pervasiveness, fundamentality and uniqueness of heavy tails Sensitivity study Generative model Comparison with previous work 3. One potential application 4. Conclusions 20

52.

Rest of the Talk 1. Background on program social networks 2. Pervasiveness, fundamentality and uniqueness of heavy tails Sensitivity study Generative model Comparison with previous work 3. One potential application 4. Conclusions 20

53.

Source Code Example from mcf The highest oudegree instructions in mcf 21

54.
[beta]
Source Code Example from mcf
The highest oudegree instructions in mcf
1 long read_min(network_t *net) {
2
...
3
net->n_trips = t;
4
net->m_org
= h;
5
net->n
= (t+t+1);
6
net->m
= (t+t+t+h);
7
...
8
net->nodes
= (node_t *)calloc(net->n + 1, sizeof(node_t));
9
net->dummy_arcs = (arc_t *)calloc(net->n, sizeof(arc_t));
10
net->arcs
= (arc_t *)calloc(net->max_m, sizeof(arc_t));
11
...
12
net->stop_nodes = net->nodes + net->n + 1;
13
net->stop_arcs = net->arcs + net->m;
14
net->stop_dummy = net->dummy_arcs + net->n;
15
...
16 }

Initializing the struct net

21

55.
[beta]
Source Code Example from mcf
The highest oudegree instructions in mcf
1 long read_min(network_t *net) {
2
...
3
net->n_trips = t;
4
net->m_org
= h;
5
net->n
= (t+t+1);
6
net->m
= (t+t+t+h);
7
...
8
net->nodes
= (node_t *)calloc(net->n + 1, sizeof(node_t));
9
net->dummy_arcs = (arc_t *)calloc(net->n, sizeof(arc_t));
10
net->arcs
= (arc_t *)calloc(net->max_m, sizeof(arc_t));
11
...
12
net->stop_nodes = net->nodes + net->n + 1;
13
net->stop_arcs = net->arcs + net->m;
14
net->stop_dummy = net->dummy_arcs + net->n;
15
...
16 }

Initializing the struct net

net is the central data structure of mcf
21

56.

Are Heavy Tails Function Dependent? Analyze program social networks of functions 22

57.

Are Heavy Tails Function Dependent? Analyze program social networks of functions 22

58.

Are Heavy Tails Function Dependent? Analyze program social networks of functions (Partially)YES: though majority are heavy tails (min: 72% max:100% average: ≈85%) 22

59.

Compositions Have Heavy Tails If the functions have heavy tails, will programs which have typical compositions of these functions have heavy tails? A generative model to explain why programs have heavy tails A model of programs (structured programming) 23

60.

Compositions Have Heavy Tails If the functions have heavy tails, will programs which have typical compositions of these functions have heavy tails? Chain length Heavy Tails [%] Power laws [%] A generative model to explain why programs have heavy tails 2 98 programming) 81 A model of programs (structured 5 99 79 10 99 79 50 100 62 23

61.

Compositions Have Heavy Tails If the functions have heavy tails, will programs which have typical compositions of these functions have heavy tails? Chain length Heavy Tails [%] Power laws [%] A generative model to explain why programs have heavy tails 2 98 programming) 81 A model of programs (structured 5 99 79 10 99 79 50 100 62 23

62.

Compositions Have Heavy Tails If the functions have heavy tails, will programs which have typical compositions of these functions have heavy tails? Chain length Heavy Tails [%] Power laws [%] A generative model to explain why programs have heavy tails 2 98 programming) 81 A model of programs (structured 5 99 79 10 99 79 50 100 62 23

63.

Rest of the Talk 1. Background on program social networks 2. Pervasiveness, fundamentality and uniqueness of heavy tails Sensitivity study Generative model Comparison with previous work 3. One potential application 4. Conclusions 24

64.

Rest of the Talk 1. Background on program social networks 2. Pervasiveness, fundamentality and uniqueness of heavy tails Sensitivity study Generative model Comparison with previous work 3. One potential application 4. Conclusions 24

65.

Heavy Tails Phenomenon is Unique Will heavy tails phenomenon lead to new advances? Our approach: Perform workload characterization using program social networks Compare the results with prior work Clustering analysis on SPEC CPU2006 benchmarks Outdegree probability distribution based clustering (Micro)architecture metric based clustering [Phansalkar, ISCA’07] 25

66.

Heavy Tails Phenomenon is Unique Will heavy tails phenomenon lead to new advances? Our approach: Results are different, suggesting that program Perform workload characterization using program social networks social networks are offering a new lens to view Compare the results with prior work programs that lead to new advances Clustering analysis on SPEC CPU2006 benchmarks Outdegree probability distribution based clustering (Micro)architecture metric based clustering [Phansalkar, ISCA’07] 25

67.

Rest of the Talk 1. Background on program social networks 2. Pervasiveness, fundamentality and uniqueness of heavy tails Sensitivity study Generative model Comparison with previous work 3. One potential application 4. Conclusions Conclusion 26

68.

Rest of the Talk 1. Background on program social networks 2. Pervasiveness, fundamentality and uniqueness of heavy tails Sensitivity study Generative model Comparison with previous work 3. One potential application 4. Conclusions Conclusion 26

69.

One Potential Application Enhancing reliability Assumption: high outdegree instructions are more vulnerable (susceptible to soft errors) than others Intuition: Error has a higher chance to corrupt program state Tend to have longer lifetime (exposed to radiation) Idea: selectively protect their outputs to enhance reliability with low cost 27

70.

Conclusions Program social network: a new way to look at programs Heavy tails phenomenon in programs Small number of instructions are responsible for large effects Intervention on these instructions will be disproportionately effective Pervasive, fundamental and unique Leads us to new types of computer architecture Potential applications: Enhancing reliability by protecting high outdegree instructions, and more… 28