A systematic Characterization of Application Sensitivity to Network Performance

3
Professor David E. Culler
Dissertation Committee Chair

---

to Mimi L. Phan.

---

---

Acknowledgements
I must first thank my uncle, Dr. James Martin. Without his singular insight on the nature
of graduate studies I would not have finished this thesis.
I must also thank my advisor, Dr. David E. Culler, for innumerable interesting conversa-
tions over the years. However, I am especially grateful for the guidance I received during those first
critical years in graduate school. Your early sheparding on the HPAM system got me off to a great
start.
My parents, Dr. Richard and Elma Martin, deserve much credit. Thanks for all the support
you have provided, especially for all those computers. More importantly, thanks for sitting through
my endless small demos. I must also thank my father for the “Professor X” book, which still gives
me a good laugh.
To my long time fiance and now wife, Mimi Phan, I must thank for giving me the love,
support and perspective to keep going during the long and difficult years.
I am greatly indebted to all the co-authors on various works, and what a list it has become.
I’m honored to even have my name on the same pages as you: Amin Vahdat, Marc Fiuczynski, Lok
Tin Liu, Remzi Arpaci-Dusseau, Frederick C.B. Wong, Chad Yoshikawa, Andrea Arpaci-Dusseau,
Klaus Schauser, Randy Wang and Arvind Krishnamurthy.
I would also like to express thanks to my office-mates in 445 Evans, 467 and 466 Soda:
Steve Luna, Cedric Krumbein, Brent Chun, Tony Chan, Vikram Makhija and Matt Welsh. You were
a great group to work with and provided quite a bit of respite from the daily grind of graduate studies.
To the other members of the NOW project, thank you for six years simulating conversa-
tions. Predictions aside, most of us made it, and that’s success enough. Thanks to Steve R., Doug,
Kristin, Jeanna, Drew, Mike, Satoshi, Nisha, Kim, Eric, Alan, and Steve L. for making such a big
project bearable.
Finally, I would like to thank my other two committee members, Dave Patterson and Hal
Varian, for giving excellent advice during my quals talk as well as for reading this work.

---

iii
Contents
Table of Contents
iii
List of Figures
vi
List of Tables
ix
1
Introduction
1
1.1
Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
1.1.1
Experiment Paradigm Axis . . . . . . . . . . . . . . . . . . . . . . . . . .
4
1.1.2
Evaluation Methods Axis . . . . . . . . . . . . . . . . . . . . . . . . . . .
6
1.1.3
Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
10
1.2
Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
11
1.2.1
Performance Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . .
11
1.2.2
Application Behavior . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
12
1.2.3
Network Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
13
1.2.4
Modeling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
14
1.3
Thesis Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
14
2
Methodology
17
2.1
Experiment Design Philosophy . . . . . . . . . . . . . . . . . . . . . . . . . . . .
18
2.2
LogGP Network Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
18
2.3
Apparatuses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
20
2.3.1
Basic Split-C/AM Apparatus . . . . . . . . . . . . . . . . . . . . . . . . .
21
2.3.2
MPI Apparatus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
26
2.3.3
TCP/IP Apparatus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
29
2.4
Factor Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
35
2.5
Other Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
37
2.5.1
Bulk Synchronous Parallel . . . . . . . . . . . . . . . . . . . . . . . . . .
38
2.5.2
Queue Shared Memory . . . . . . . . . . . . . . . . . . . . . . . . . . . .
38
2.5.3
LoPC and LoGPC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
39
2.5.4
Queuing Theory
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
39
2.6
Related Methodologies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
40
2.6.1
Holt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
40
2.6.2
Chang . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
41

---

iv
2.6.3
Ahn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
42
2.6.4
Hall . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
43
2.6.5
Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
44
3
Split-C/AM Program Sensitivity
46
3.1
Characterization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
46
3.1.1
Split-C Benchmark Suite . . . . . . . . . . . . . . . . . . . . . . . . . . .
49
3.1.2
Characteristics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
52
3.2
Analytic Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
53
3.2.1
Overhead . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
53
3.2.2
gap . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
54
3.2.3
Latency . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
54
3.2.4
Gap . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
55
3.3
Sensitivity Results
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
55
3.3.1
Overhead . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
56
3.3.2
gap . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
59
3.3.3
Latency . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
60
3.3.4
Bulk Gap . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
62
3.4
Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
63
3.4.1
Performance Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . .
63
3.4.2
Application Behavior . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
63
3.4.3
Network Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
64
3.4.4
Modeling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
64
4
NAS Parallel Benchmark Sensitivity
65
4.1
Characterization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
66
4.2
Sensitivity Results
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
68
4.2.1
Overhead . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
69
4.2.2
gap . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
70
4.2.3
Latency . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
70
4.2.4
Bulk Gap . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
71
4.3
NPB Sensitivity Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
72
4.3.1
Performance Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . .
72
4.3.2
Application Behavior . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
73
4.3.3
Network Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
74
4.3.4
Modeling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
75
5
NFS Sensitivity
76
5.1
Experimental Setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
77
5.2
SPECsfs Characteristics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
78
5.3
SPECsfs Analytic Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
81
5.3.1
Model Construction
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
81
5.3.2
Model Accuracy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
83
5.3.3
Expected Sensitivity . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
85
5.4
Previous Work on NFS Performance . . . . . . . . . . . . . . . . . . . . . . . . .
86

---