A systematic Characterization of Application Sensitivity to Network Performance

58
which is described below.
Table 3.3 describes how well our simple overhead model predicts application performance
when compared to measured runtimes. For two applications which communicate frequently, Sample,
and EM3D(write), our model accurately predicts actual application slowdown . For a number of
other applications, most notably Radix, P-Ray and Mur
4
, the sensitivity to overhead was actually
stronger than our model’s prediction; the model consistently under-predicts the run time, which is
consistent with the assumptions made by the model.
Another way to describe the “serialization effect” is that our model implicitly assumes all
work in the program is perfectly parallelizable; i.e., there are no serial phases in the program. This
assumption leads to under-predicted run times. If a processor,
576
, serializes the program in a phase
8
messages long, when we increase
9
by
@A9
, then the serial phase will add to the overall run time
by
8
@A9
. However, the simple model does not capture the serialization effect when
57BDC
E
5F6
.
A more important result of the of the serialization effect is that it reduces speedup as a
function of overhead, i.e. speedup gets worse the greater the overhead. Thus, parallel efficiency
will decrease as overhead increases for any applications which have a serial portion. Notice how for
Radix, parallel decreases as a function of overhead when scaled from 16 to 32 nodes.
Radix sort demonstrates a dramatic example of the serialization effect. The sensitivity to
overhead for Radix on 32 processors is over double that of 16 processors. When overhead rises to
100
G
s, the slowdown differential between 16 and 32 processors is a factor of three. The global his-
togram phase contains a serialization proportional to the radix and number of processors [39]. In the
unmodified case, the phase accounts for 20% of the overall execution time on 32 processors. When
the overhead is set to 100
G
s, this phase accounts for 60% of the overall execution time. However,
on 16 processors with 100
G
s of overhead, the histogram phase takes only 16% of the total time.
In the case of P-ray, recall from Figure 3.1 that the application shows a strong communica-
tion imbalance. Three processors are “hot spots”, likely containing popular objects. We conjecture
that the nodes doing the most work are not the ones sending the most messages. By increasing the
overhead, all other processors which attempt access to hotspots in the octree are likely slowed down
by a linear factor not predicted by our model
The other five applications, however, actually demonstrate a stronger sensitivity to over-
head than predicted by the model. The only application which demonstrates a non-linear dependence
to overhead was Barnes. Further experimentation with the program revealed that as overhead was
increased, lock contention caused the program to go into livelock. In fact, we were unable to add
more than 10
G
s of overhead and still have the application complete in a reasonable amount of time.

---

59
0
2
4
6
8
10
12
14
16
18
0
20
40
60
80
100
120
Slowdown
H
gap
Radix
EM3D(w)
Sample
EM3D(r)
Barnes
P-ray
Murphi
Connect
NOWsort
Radb
Figure 3.3: Sensitivity to gap
This figure plots slowdown as a function of gap in microseconds. The gap is scaled by a factor of 20.
While no hardware has a gap of over 20
I
s, we can observe from the figure that many applications
have linear responses to gap for then entire observed range.
3.3.2
gap
We next measure application sensitivity to gap. Figure 3.3 plots application slowdown as
a function of added gap in microseconds. The programs demonstrate widely varying reactions to
gap, ranging from being unaffected by 100
I
s of gap to slowing down by a factor of 16. The qualita-
tive difference between application sensitivity to gap and sensitivity to overhead can be explained by
the fact that sensitivity to gap is incurred by the program only on the portion of the messages where
the application attempts to send at a rate greater than the gap. The rest of the messages are not sent
quickly enough to be affected by the gap. Thus, infrequently communicating applications can po-
tentially ignore gap entirely, while overhead is incurred independent of message frequency. The four
applications with the highest communication frequency, Radix, EM3D(write) and read, and Sample,
suffer the largest slowdowns from added gap. The other applications are much more tolerant to gap,
slowing down by no more than a factor of 4 even in the presence of 100
I
s of added gap.
Given the linear dependence to gap demonstrated by the applications in Figure 3.3, we
believe that for our applications, the burst model more accurately predicts application behavior. Ta-
ble 3.4 depicts how well the burst model predicts actual program slowdown. As anticipated, the

---

60
g
P
s
Radix
EM3D(write)
EM3D(read)
Sample
Barnes
measure
predict
measure
predict
measure
predict
measure
predict
measure
predict
5.8
7.8
7.8
38
38
114
114
13.2
13.2
43.2
43.2
8
10.2
11
46.1
49.9
119
134.8
14.8
16.5
44.1
45.4
10
13
14.2
56.5
61.8
129.7
155.6
17.5
19.7
50.2
47.5
15
19.2
20.5
78.5
85.6
164.7
197.2
24.2
26.2
55.3
51.8
30
38.1
39.7
150.3
157.1
289.3
321.9
42.9
45.6
61.6
64.6
55
69.9
71.7
273.1
276.2
523
529.8
75.1
78
99.1
85.9
80
101.9
103.7
394
395.4
756.9
737.7
107.5
110.4
157.3
107.2
105
133.8
135.7
515.6
514.5
993.1
945.6
139.7
142.7
207.9
128.5
g
P
s
P-Ray
Mur
Q
Connect
NOW-sort
Radb
measure
predict
measure
predict
measure
predict
measure
predict
measure
predict
5.8
17.9
17.9
35.3
35.3
1.17
1.17
56.9
56.9
3.73
3.73
8
18.1
18.6
37.4
35.8
1.19
1.18
57.9
57.0
3.77
3.74
10
17.8
19.3
36.1
36.2
1.21
1.19
57.6
57.2
3.78
3.75
15
17.9
20.7
36.2
37.0
1.24
1.23
60.9
57.6
3.80
3.78
30
19.1
24.9
38.4
39.5
1.34
1.32
57.3
58.6
3.86
3.85
55
23.2
31.8
37.5
43.8
1.51
1.50
57.2
60.4
3.96
3.98
80
29.0
38.8
39.3
48.0
1.68
1.69
56.9
62.1
4.08
4.10
105
35.5
45.8
39.9
52.2
1.85
1.88
57.4
63.9
4.25
4.23
Table 3.4: Predicted vs. measured run times varying gap
This table demonstrates how well the burst model for sensitivity to gap predicts observed slowdown.
For each application, the column labeled
RST!UVXWYS
is the measured runtime, while the column la-
beled
`$W%Sa!b0c2d
is the runtime predicted by our model.
model over predicts sensitivity to gap since not all messages are sent in bursts. The model works
best for heavily communicating applications, as a larger percentage of their messages are slowed by
gap.
The two models considered demonstrate a range of possible application behavior. Appli-
cations communicating at very regular intervals would follow the uniform model, while applications
communicating in discreet phases would track the burst model.
3.3.3
Latency
Traditionally, most attempts at improving network performance have focused on improv-
ing the network latency. Further, perceived dependencies on network latencies have led program-
mers to design their applications to hide network latency. Figure 3.4 plots application slowdown as
a function of latency added to each message. Perhaps surprisingly, most of applications are fairly
insensitive to added latency. The applications demonstrate a qualitatively different ordering of sen-
sitivity to latency than to overhead and gap. Further, for all but one of the applications the sensitivity
does not appear to be strongly correlated with the read frequency or barrier interval, the operations
most likely to demonstrate the strongest sensitivity to latency.

---