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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Program Social Network Analysis libquantum 10

Program Social Network Analysis libquantum 10

Program Social Network Analysis Histogram libquantum 10

Program Social Network Analysis Histogram libquantum 10 CDF

Program Social Network Analysis Histogram CDF libquantum CCDF 10

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Are Heavy Tails Phase Dependent? 18

Are Heavy Tails Phase Dependent? Time 18

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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