A systematic Characterization of Application Sensitivity to Network Performance

55
reads is EM3D(read). Due to the low barrier frequency of most programs, we ignore the
¨
cost of
barrier synchronization in our model.
We thus cannot expect a simple linear model for latency to provide much accuracy given
the structure of most of the programs. The LogGP model certainly allows for more accurate mod-
els [39], however.
3.2.4
Gap
We model bulk transfers at costing a penalty of
©
per 4 KB fragment plus a cost of

per
byte. However, few of the benchmarks use long messages. Thus, for this set of benchmarks, our
predictions about the effects of

may not be widely applicable. The NAS Parallel Benchmarks,
described in the next chapter, use long messages exclusively and so it is there where we will explore
sensitivity to

.
3.3
Sensitivity Results
Given our methodology and application characterization, we now quantify the effect of
varying LogGP parameters on our application suite. To this end, we independently vary each of the
parameters in turn to observe application slowdown. For each parameter, we attempt to explain any
observed slowdowns based on application characteristics described in the last section. Using this
intuition, we develop models to predict application slowdown.
Recall that any observed run time is a random variable, and thus any two run times, even
very controlled conditions, will yield different results. In order to better account for these discrepan-
cies, we take the minimum value of three sample run times. We take the minimum because it is most
representative of the program execution behavior without outside interference. It was found that the
majority of the discrepancy in run-time was due to effects of the GLUnix global control layer used to
start and stop jobs [45]. These effects are not of interest to the results of this thesis. The data in this
section shows that once the variance do to GLUnix is removed (by taking the minimum run-time),
the Split-C/AM programs are very well behaved; programs do not yield widely varying results from
run to run.

---

56
0
5
10
15
20
25
0
20
40
60
80
100
120
140
Slowdown

Overhead
EM3D(w)
Sample
Radix
EM3D(r)
Barnes
P-ray
Murphi
Connect
NOWsort
Radb
0
10
20
30
40
50
60
0
20
40
60
80
100
120
140
Slowdown

Overhead
Radix
EM3D(w)
EM3D(r)
Sample
Barnes
P-ray
Murphi
Connect
NOWsort
Radb
(a)
(b)
Figure 3.2: Sensitivity to Overhead for 16 and 32 Nodes
This figure plots application slowdown as a function of overhead in microseconds. Slowdown is rel-
ative to application performance with our system’s baseline LogGP parameters. Overhead is scaled
by a factor of 30, from high-performance SAN protocols to high-overhead TCP/IP stacks. Measure-
ments for the graph on the left were taken on 16 nodes, while measurements for the graph on the
right were taken on 32 nodes with a fixed input size.
3.3.1
Overhead
Figure 3.2(b) plots application slowdown as a function of added overhead measured in mi-
croseconds for our applications run on 32 nodes. The extreme left portion of the x-axis represents
runs on our cluster. As overhead is increased, the system becomes similar to a switched LAN im-
plementation. Currently, 100

s of overhead with latency and gap values similar to our network is
approximately characteristic of TCP/IP protocol stacks [60, 61, 103]. At this extreme, applications
slow down from 2x to over 50x. Clearly, efforts to reduce cluster communication overhead have
been successful. Further, all but one of our applications demonstrate a linear dependence to over-
head, suggesting that further reduction in overhead will continue to yield improved performance.
Qualitatively, the four applications with the highest communication frequency, Radix, Sample, and
both EM3D read and write, display the highest sensitivity to overhead. Barnes is the only application
which demonstrates a non-linear dependence to overhead. Instrumentation of Barnes on 16 nodes
revealed that as overhead is increased, lock contention causes the program to go into livelock. With
zero added overhead, the average number of failed lock attempts per processor is 2000 per timestep.

---

57
o

s
Radix
EM3D(write)
EM3D(read)
Sample
Barnes
measure
predict
measure
predict
measure
predict
measure
predict
measure
predict
2.9
7.8
7.8
38
38
114
114
13.2
13.2
43.2
43.2
3.9
10.5
10.3
48.1
47.5
138.7
130.7
16.1
15.8
50.1
44.9
4.9
13.2
12.9
58.1
57.0
161.6
147.3
18.7
18.4
56.3
51.8
6.9
18.7
18.0
77.4
76.1
208.8
180.5
23.8
23.6
76.1
60.3
7.9
21.5
20.5
87.4
85.6
232.9
197.2
26.5
26.2
N/A
N/A
13
36.3
33.3
138.5
133.3
354.4
280.3
39.3
39.1
N/A
N/A
23
68.9
58.9
236.2
228.6
600.1
446.7
65.2
65.0
N/A
N/A
53
198.2
135.7
535.9
514.5
1332.5
945.6
142.7
142.7
N/A
N/A
103
443.2
263.6
1027.8
991.0
2551.7
1777.2
272.1
272.2
N/A
N/A
o

s
P-Ray
Mur

Connect
NOW-sort
Radb
measure
predict
measure
predict
measure
predict
measure
predict
measure
predict
2.9
17.9
17.9
35.3
35.3
1.17
1.17
56.9
56.9
3.73
3.73
3.9
19.0
18.5
37.1
35.7
1.19
1.18
56.7
57.0
3.77
3.74
4.9
19.6
19.0
37.7
36.0
1.20
1.19
61.2
57.1
3.77
3.75
6.9
22.0
20.1
41.8
36.7
1.23
1.20
57.9
57.4
3.82
3.77
7.9
20.8
20.7
41.9
37.0
1.24
1.21
58.3
57.6
3.83
3.78
13
28.2
23.5
46.2
38.7
1.31
1.25
58.1
58.3
3.93
3.83
23
39.0
29.1
51.2
42.1
1.44
1.34
58.3
59.7
4.10
3.93
53
69.7
45.8
72.6
52.2
1.85
1.61
61.7
63.9
4.81
4.23
103
114.0
73.6
107.8
69.1
2.52
2.08
71.1
70.8
6.19
4.73
Table 3.3: Predicted vs. Measured Run Times Varying Overhead
This table demonstrates how well our model for sensitivity to overhead predicts observed slowdown
for the 32 node runs. For each application, the column labeled
! "$#%
is the measured runtime,
while the column labeled
&$#%'!(0)21
is the runtime predicted by our model. For frequently communicat-
ing applications such as Radix, EM3D(write), and Sample, the model accurately predicts measured
runtimes.
At 13
3
s of overhead, the number of failed lock attempts per processor per timestep skyrockets to
over 1 million. This implementation of Barnes does not complete for overhead values greater than
13
3
s on 16 nodes and 7
3
s on 32 nodes.
To determine the effect of scaling the number of processors on sensitivity to overhead,
we executed our applications on 16 nodes with fixed inputs. Figure 3.2(a) plots the resulting slow-
down as a function of overhead for runs on 16 nodes. With the exception of Radix, the applications
demonstrate almost identical sensitivity to overhead on 16 processors as they did on 32 processors,
slowing down by between a factor of between 2 and 25. Recall that Radix contains a phase to con-
struct a global histogram. The number of messages used to construct the histogram is a function of
the radix and the number of processors, not the number of keys. For a constant number of keys, the
relative number of messages per processor increases as processors are added. Radix thus becomes
more sensitive to overhead as the number of processors is increased for a fixed input size. In addition,
the difference in sensitivities between 16 and 32 nodes is exacerbated by a serial phase in program,

---