LogGPS: A Parallel Computational Modelfor Synchronization Analysis
Fumihiko Ino, Noriyuki Fujimoto and Kenichi Hagihara
Graduate School of Engineering Science
Osaka University
Toyonaka, Osaka 560-8531, Japan{ino, fujimoto, hagihara}@ics.es.osaka-u.ac.jp

ABSTRACT
We present a new parallel computational model, named LogGPS, which captures synchronization.
The LogGPS model is an extension of the LogGP model,
which abstracts communication on parallel platforms. Although the LogGP model captures long messages with one
bandwidth parameter (G), it does not capture synchronization that is needed before sending a long message by highlevel communication libraries. Our model has one additionalparameter, S, deﬁned as the threshold for message length,
above which synchronous messages are sent.
We also present some experimental results using bothmodels. The results include (1) a veriﬁcation of the LogGPS
model, (2) an example of synchronization analysis using an
MPI program and (3) a comparison of the models. The results indicate that the LogGPS model is more accurate thanthe LogGP model, and analyzing synchronization costs isimportant when improving parallel program performance.

1.

INTRODUCTION

When developing parallel programs, the programs are expected to get much better performance on many parallel
platforms. To develop such programs, parallel computational models are useful for developers. The models abstract
the performance of the platforms so that, by changing theparameters of the model, developers can know the predictedperformance of programs on every platform.
Both the LogP model [5] and the LogGP model [2] aresuch realistic models. In [2, 5, 6] the models have shown
good accuracy for low-level communication libraries such as
Active Messages [19] and Elan library [8]. The LogP model
abstracts the communication performance of a platform byfour parameters: L, o, g and P (see §3). The LogGP model
has one additional parameter (G) compared with the LogP
model and captures special support (that many platforms
have) for long messages, which provides much higher communication bandwidth for long messages compared to short

Permission to make digital or hard copies of all or part of this work forpersonal or classroom use is granted without fee provided that copies are
not made or distributed for profit or commercial advantage and that copies
bear this notice and the full citation on the first page. To copy otherwise, torepublish, to post on servers or to redistribute to lists, requires prior specificpermission and/or a fee.
PPOPP’01, June 18-20, 2001, Snowbird, Utah, USA.
Copyright 2001 ACM 1-58113-346-4/01/0006 ...$5.00.

messages. That is, the LogGP model uses two bandwidth:
1/G for long messages and 1/g for short messages.
Thus, the LogGP model reﬂects the advantage of the special support, however, it does not reﬂect the disadvantage,i.e., the need of synchronization when sending a long message. This lack might make the model inaccurate, especially for programs written using high-level communication
libraries such as MPI [13] and MPL [9]. For example, many
MPI implementations [4, 7, 10, 15] switch communication
protocols according on message length, and the protocols
can be classiﬁed into two groups: synchronous and asynchronous. This protocol switch is out of consideration under the LogGP model, which reﬂects only the advantage ofthe support. Therefore, for accuracy, models for parallel
programs such as MPI programs should reﬂect not only theadvantage but also the disadvantage of the support.
In previous works [1, 12, 14, 17], the LogGP model has
been used to analyze the performance of MPI programs.
In [1, 14] they indicated that synchronization occurs before
sending a long message. They assumed that the sender processor synchronizes to the receiver processor at the shortest
time and included the synchronization cost into the overhead, o, deﬁned as a constant value for every message length.
However, since the sender does not always synchronize at
the shortest time, their method has insuﬃcient accuracy for
programs that vary its synchronization costs at long range.
The same discussion can be held for [12], which misses considering synchronization.
In [17] they built a synchronization model for a wavefront
application that uses MPI routines. They showed its synchronization cost as a formula, which consists of the communication latency and the processor ID, and added the synchronization cost to the communication cost derived by the
LogGP model. Their method has good accuracy but cannot
apply to programs that are diﬃcult to derive the equation
without run. In addition, the derived model is dependent on
the target application, so that we have to repeatedly builda synchronization model for every application.
Through the previous works, we think that synchronization costs must be accurately analyzed for the whole analysis of MPI programs and synchronization models must be
independent of the target programs. To analyze the synchronization costs in accurate, the LogGP model (and also
the LogP model) is insuﬃcient because it misses considering
the protocol switch.
Furthermore, both the methods for deriving the parameters of the models and the deﬁnitions of MPI routine costs

= single packet

Table 1: MPICH communication protocols
ProtocolPacketSynchronization
Short
singlenoEager
multiplenoRendezvous multiple
yescommunication cost
MPI_Send cost
MPI_Send
Ps

t
data

Pr

t
MPI_Recv
receiver synchronization cost
MPI_Recv cost

are diﬀerent among the works, and it is not clear which
method provides better accuracy.
Now, our goals are as follows.

(a) Eager protocol
idle state
MPI_SendPs(G1) Develop a realistic model for synchronization analysis.

t
REQ

ACK

data

Pr

t
MPI_Recv(G2) Develop a method for deriving the parameters of themodel and apply the model to high-level communication routines.

sender synchronization cost(b) Rendezvous protocol with blocking send
MPI_Isend

To achieve goal (G1), we extended the LogGP modelby adding one parameter, S, or the threshold for message
length, above which synchronous protocols are employed.
Furthermore, to make the model more accurate, we represented the communication overhead as a linear function of
message length. Then we named the new model LogGPS.
To achieve goal (G2), we applied the LogGPS model to some
MPI routines [13] and compared with the LogGP model by
analyzing an MPI program.
Finally, we believe that the LogGPS model is useful toanalyze the synchronization costs of parallel programs, especially when improving the performance of the programs.
The rest of the paper is organized as follows. §2 describes
the communication protocols used in MPI implementations[4, 7, 10, 15]. §3 presents the LogGPS model and the deﬁnitions of MPI routine costs. §4 presents the experimental
results. Finally, §5 concludes the paper.

idle state
MPI_Wait

Ps

t
REQ

ACK

data

Pr

t
MPI_Recv(c) Rendezvous protocol with nonblocking send

Figure 1: Behavior of MPICH communication protocols

MPI COMMUNICATION PROTOCOLS

Table 2: Relationship between message length andcommunication protocols of MPI implementations
Message length (bytes)
Implementation
Short
Eager
Rndv.
MPICH P4
∼1023
∼127999 128000∼–
1029∼
MPICH Cenju-4 ∼1028
MPICH-SCore∼8191∗ ∼16383∗∗ 16384∗∗ ∼∼65536–65537∼LAM C2C
IBM PE∼4095–
4096∗∗ ∼∗: on Myrinet ∗∗: changeable by runtime option

In this section, we describe the communication protocols
used in MPICH [7], the base of many MPI implementations.
Some other implementations are also shown in Table 2.
MPICH consists of two layers, machine-dependent andmachine-independent, separated by Abstract Device Interface (ADI). The default ADI (P4) uses three protocols: Short,
Eager and Rendezvous (Rndv.), as shown in Table 1. In thefollowing, let Ps and Pr be the sender processor and thereceiver processor, respectively.
In the Short and Eager protocol, Ps should not wait for
Pr to call the matching receive routine because Pr copies
messages to own buﬀer (Fig. 1(a)). In contrast, in the
Rndv. protocol, Ps has to send a request (REQ) prior
to the original message and wait for an acknowledgement(ACK) from Pr (Fig. 1(b)). Therefore, the use of blocking
send routine (MPI Send) makes Ps idle inside the send routine during the wait. On the other hand, nonblocking sendroutine (MPI Isend) allows Ps to return immediately after
sending the REQ. However, if the ACK has not been arrived when Ps calls the matching wait routine (MPI Wait),
Ps becomes idle inside the wait routine (Fig. 1(c)). Thus,
the Rndv. protocol needs synchronization, but messages aretransmitted in bulk after the synchronization, so that practical communication bandwidth grows up. Furthermore, some
platforms have special support for long messages to raise thebandwidth more. For example, the NEC Cenju-4 [11] andMyrinet [3] provide remote DMA transfer.

Table 2 shows the relationship between message lengthand the communication protocols of MPI implementations[4, 7, 10, 15]. Each employs asynchronous protocols (Shortand Eager) for short messages and synchronous (Rndv.) forlong. That is, MPI implementations switch the protocol toprovide better bandwidth for any given message length.
To change the threshold length between the asynchronousand synchronous protocols, we must modify the source codeof MPI implementation and re-compile it. But some implementations such as MPICH-SCore [15] and IBM PE [10] canchange the threshold statically by runtime option. As far as
we know, the threshold is unchangeable during a run.
In the following we use the term sender synchronization
cost, deﬁned as the length of the wait time at Ps, time after the arrival of a REQ until the call of the receive routine(Fig. 1(b)). We also use the term receiver synchronization
cost, the length of the wait time at Pr, time after the call ofa receive routine until the arrival of the message (Fig. 1(a)).
Synchronization costs are deﬁned as the sum of sender synchronization costs and receiver synchronization costs. Besides, we use the term communication cost, deﬁned as thelength of time after the call of a send routine at Ps until
the call of the receive routine at Pr, and the term MPI routine cost, deﬁned as the length of time after the call of theroutine until the return of the routine (Fig. 1(a)).

2.

ts1: send1 (k=2, Short)o’+2Os2Gsts2: send2 (k=4, Eager)o’+4Osg

2Gs

ts3: send3 (k=5, Rendezvous)

2Gl= 1byte message
2Gso’+5Os
g

Ps

o’

3Gl

o’

t

o’ o’

Pr

L

L
o’+2Or

T1

T2

tr1: recv1

T3

o’+4Or
T1

tr2: recv2

T2’

T3

L
tr3-ts3
T4t

L

Lo’+5Ortr3: recv3

T5

T1’

T 2’

T3’

Figure 2: An example of message sends under the LogGPS model (s = 2, S = 4)

Condition
k≤s
s<k≤S
k>S

3.

Table 3: Communication costs under the LogGPS model
Communication cost
T1 ,T2 ,...,T5
T 1 + T2 + T3
(1) T1 = o + kOs
T2 = kGs + L
T1 + T2 + T3
(2) T2 = sGs + (k − s)Gl + L
T3 = o + kOr
T4 + T5 + T1 + T2 + T3 (3) T4 = max{o + L, tr − ts } + o T5 = o + L + o

THE LOGGPS MODEL

The LogGP model [2], the base of the LogGPS model, has
ﬁve parameters as follows.
• L: an upper bound on the Latency, incurred in sending a message from its source processor to its target
processor.
• o: the overhead, deﬁned as the length of time that aprocessor is engaged in the transmission or receptionof each message; during this time the processor cannot
perform other operations.
• g: the gap between messages, deﬁned as the minimum time interval between consecutive message transmissions or consecutive message receptions at a processor. The reciprocal of g corresponds to the available per processor communication bandwidth for shortmessages.
• G: the Gap per byte for long messages, deﬁned as thetime per byte for a long message. The reciprocal of G
characterizes the available per processor communication bandwidth for long messages.
• P : the number of processor/memory modules.
Compared with the LogGP model, the LogGPS model has
three diﬀerences as follows: diﬀerences (D1), (D2) and (D3).
Let k be the length of a message in the following (k ≥ 0).
(D1) Add one parameter, S, deﬁned as the threshold formessage length, above which synchronous messages aresent. When k > S, Ps waits for an ACK from Pr.
Otherwise, Ps sends an asynchronous message.
(D2) Divide the overhead, o, between Ps and Pr, and let o +kOs and o + kOr be the send overhead and the receive
overhead, respectively; o represents the overhead forthe ﬁrst byte of a message, and Os and Or represent
the send overhead and the receive overhead per byte
for the subsequent byte of the message, respectively.

(D3) Add one parameter, s, deﬁned as the threshold formessage length, above which messages are sent in multiple packets. Furthermore, divide the Gap, G, between single and multiple packets, i.e., Gap Gl fork ≤ s and Gs for k > s.
Diﬀerence (D1) allows the LogGPS model to decide whether
a message should be sent in asynchronous or synchronous sothat the model captures synchronization. The rest of differences, (D2) and (D3), are ideas to make the model moreaccurate. The beneﬁts of these ideas are shown in §4.3.

3.1 Communication Costs under the ModelIn this section, we deﬁne the communication cost of ak-bytes message under the LogGPS model (Table 3).
Figure 2 shows an example of three messages (send1, send2
and send3) under the LogGPS model, where s = 2 andS = 4.
When k ≤ S, Ps sends asynchronous messages (send1 andsend2). The communication costs are deﬁned by summingup time T1 , T2 (or T2 ) and T3 , each shown in Figure 2.
First, the time to push the ﬁrst byte of a message into the
network, T1 , is deﬁned as the send overhead, or o + kOs .
Second, the time after the departure of the ﬁrst byte at Ps
until the arrival of the last byte at Pr, T2 (or T2 ), is deﬁned
as kGs + L (or sGs + (k − s)Gl + L). This is explained asfollows. (a) Subsequent bytes take Gs cycles each to go out.
(b) After the bytes amount to length s, the subsequent bytes
take Gl cycles each. (c) Each byte transmitted through the
network for L cycles. Third, the time to get the last byte
from the network, T3 , is deﬁned as the receive overhead, oro + kOr . Finally, when k ≤ S, the communication costs aredeﬁned as equations (1) and (2) shown in Table 3.
When k > S, Ps synchronizes to Pr (send3). In addition
to times T1 , T2 and T3 , the communication cost is deﬁned
by summing up the time to establish synchronization, times
T4 and T5 as shown in Figure 2. First, Ps sends a REQ to
Pr. We consider the REQ as a zero-byte message, so that
the REQ arrives at time o + L. Second, Ps waits for an
ACK from Pr. On the other hand, Pr conﬁrms if the REQ
have been arrived when it calls the receive routine. This

Routine
MPI_Send
MPI_Isend
MPI_Recv

MPI_Irecv
MPI_Wait

Table 4: MPI routine costs under the LogGPS model
Condition Cost
k≤S
T1
k>S
T4 + T5 + T1ok≤s
max{T1 + T2 − (tr − ts ), 0} + T3
s < k ≤ S max{T1 + T2 − (tr − ts ), 0} + T3
k>S
max{o + L − (tr − ts ), 0} + o + T5 + T1 + T2 + T3o
max{Tblk − (ti − tw ), o }conﬁrmation takes the receive overhead, or o . Thus, thetime after the call of the send routine until the conﬁrmationof the REQ, T4 , is deﬁned as max{o + L, tr − ts } + o , wherets is the call time of the send routine and tr is the call timeof the matching receive routine. Third, Pr sends an ACK
to Ps. As we did for REQ, we consider the ACK as a zerobyte message, so that the time to communicate the ACK,
T5 , is deﬁned as o + L + o . Finally, after receiving the ACKfrom Pr, Ps sends the original message. After this synchronization, the rest of the time required for communication isequal to equation (2). Therefore, when k > S, we deﬁne
the communication cost as equation (3). Since equation (3)includes the biggest term from terms tr − ts and o + L, theLogGPS model captures synchronization costs.

3.2 MPI routine costs under the ModelIn §3.1, we deﬁned communication costs, but MPI routine
costs are not equal to the communication costs, as shownin Figure 1(a). Furthermore, the performance of MPI programs varies according to the mode of employed MPI routines. That is, the performance depends on whether the programs employ blocking or nonblocking routines (although
the communication costs are the same under both modes).
Therefore, to get better accuracy, we should deﬁne the MPI
routine costs.
MPI libraries are usually implemented on low-level communication libraries. For example, MPICH for the NEC
Cenju-4 uses Paralib/CJ4 [11] and MPICH-SCore does PM[15]. Accordingly, we can apply the LogGPS model according to the following two policies.
(P1) Apply the model to each low-level communication routine, which constructs MPI routines.
(P2) Apply the model to each MPI routine so that disregard
the inside implementation of the MPI routine.
According to policy (P1), we can get an accurate MPI
model but the model is dependent on each MPI implementation. In contrast, according to policy (P2), we can get amodel that is applicable to any implementations. However,
because the model disregards the inside behavior of MPI
routines, an idea to solve paradoxes is needed. The paradox
is, for example, given a model that deﬁnes the MPI Send
cost as a constant value (o) and an MPI implementationthat returns from an MPI Send call after the entire message
has been pushed into the network, the model cannot deﬁne
the MPI Send cost in accurate. This paradox is caused by
the conﬂict between the constant value (o) and the linear
function of message length (k), or the cost to push the entire message into the network. Therefore, in the LogGPS

(4)
(5)
(6)
(7)
(8)
(9)
(10)
(11)

model, all of times T1 , T2 and T3 are represented as linear functions of message length. This representation allows
messages to be pushed in any of times T1 , T2 and T3 andthe model to disregard the inside implementation of MPI
routines. Although the meanings of each parameter couldchange, we choose policy (P2) to achieve goal (G1), that is,
the goal to develop a realistic model for many platforms.
Now, in the following, we deﬁne three MPI routine costs:
MPI Send, MPI Recv and MPI Wait. Table 4 shows somemajor MPI routine costs, including the above three.
First, we deﬁne the MPI Send cost. When k ≤ S, thatis, when sending an asynchronous message, Ps spends thesend overhead, T1 , and returns from the MPI Send (equation (4)). When k > S, Ps synchronizes to Pr. Therefore,
to return from the MPI Send call, the time to establish synchronization, T4 + T5 , is added to T1 (equation (5)).
Second, we deﬁne the MPI Isend cost. When k ≤ S, Ps
returns from the MPI Isend after the start of send operation(equation (6)). When k > S, Ps has to synchronize but canreturn after the send of an ACK (equation (6)).
Besides, if send routines or receive routines are called consecutively, each consecutive call must be called at g intervals
at the shortest. Therefore, all equations shown in Table 4
should include term g in a strict way. However, we disregard
g and use the equations that exclude g. The reason of thisexclusion will be presented in §4.2.
Third, we deﬁne the MPI Wait cost, Twait . Usually, a
blocking routine consists of a nonblocking routine and a waitroutine. Therefore, we compute back Twait from the cost of
the blocking routine, Tblk , as follows. First, we temporarily
replace the nonblocking routine, which matches to the target
MPI Wait, to a blocking routine. Then, we can calculate
Tblk using equations (4), (5) and (7)-(9). Second, if let tw be
the call time of the MPI Wait and ti be the call time of thematching nonblocking routine, then at time tw , a processor
have already processed the partial operation corresponds totime ti − tw while the whole operation corresponds to time
Tblk . Therefore, Twait is deﬁned as equation (11). Equation(11) includes term o to guarantee itself to take a positive
value. Strictly, the most suitable term is the time to conﬁrm
the completion of the communication, but for the simplicityof the model, we substitute the overhead, o .

4. EXPERIMENTAL RESULTS
In this section, we present some experimental results using both the LogGPS model and the LogGP model. The
experiments are structured as follows.
1. The veriﬁcation of the LogGPS model: We veriﬁedthat both diﬀerences (D2) and (D3) (see §3) make themodel more accurate on several platforms (§4.3).

Platform
Cenju-4
MyrinetFast Ethernet

Condition
k≤s
s<k≤S
k>S

Table 5: LogGPS parameters for each platform
L (ns)o (ns) Os (ns) Or (ns) Gs (ns) Gl (ns)0.64×103
7.82×103
7.63
12.77
0.57
-12.74
1.16×103
6.55×103
6.86
2.57
15.48
- 0.7410.67
5.87
191.8974.95
35.22×103 20.59×103

s (bytes)
1028
8191
1023

S (bytes)
1028
16383
16383

Table 6: LogGPS Round Trip Time
Round Trip Time: RT T1
max{T1 + 2T2 + T3 − w, 0} + w + T1 + T3
max{T1 + 2T2 + T3 − w, 0} + w + T1 + T3
max{T2 + T3 + o + L − w, 0} + w + 2T1 + T2 + T3 + 2T4 + 2T5 − (o + L)

2. The usefulness of the LogGPS model: We used themodel to analyze a Gaussian elimination program, anddetected the sender synchronization costs as its performance bottleneck (§4.4). We also tried to eliminate thebottleneck using the model (§4.5)．

4.1 Experimental environments
The parallel platforms we used are an NEC Cenju-4 [11]and a cluster. The cluster consists of sixteen 450MHz Pentium II processors and each is connected by Myrinet [3] andFast Ethernet. The MPI implementations are MPICH [7]for the Cenju-4 and MPICH-SCore [15] for the cluster.
The MPI programs we used are a Round Trip Time (RTT)
measurement program and a Gaussian elimination program[18] (with partial pivoting), the ﬁrst prize winner in NEC
Cenju-3 sections of Parallel Software Contest ’95 (PSC95)[16]. The latter program solves the set of equations, Ax = b,where A is a dense matrix with matrix size n.

4.2 Deriving the LogGPS Parameters
The method for deriving the LogGPS parameters fromeach parallel platform is as follows. First, both parameters S and s are dependent on each MPI implementation,
so that they are derived from its document or its sourcecode (see Table 2). Second, the rest of the parameters except g are derived by comparing the measured RTT using
the RTT measurement program and the modeled RTT using the LogGPS model (see §4.3 for detail). Finally, thegap (g) has little eﬀect on the communication costs of highlevel communication routines, therefore, as did in [14], we
disregard g. Through the experiments, we used equations(4)-(11) that exclude term g. Table 5 shows the values of
the LogGPS parameters for each platform.
Note that Gl < 0 is true. As we presented in §3.2, weapply the LogGPS model to each MPI routine, and disregard its inside implementation. Thus, the meanings of eachparameter could change, and this causes Gl < 0. In §4.3 wewill show that all MPI routine costs, deﬁned as equations(4)-(11), take always positive values, even if Gl < 0.

4.3 Verifying the LogGPS ModelIn this section, we verify the LogGPS model. To do this,we developed a simple RTT measurement program, whichmakes a k-bytes message go and come back between two

TRecv
MPI_Recv

dummy iteration

P0

t
t

P1

3. The comparison of the models: We compared the LogGPS model with the LogGP model and conﬁrmed that
the LogGPS model yields better accuracy (§4.6).

RTT1
w

T1
MPI_Send

(12)
(13)
(14)

MPI_Recv

T20

MPI_Send

T3

ts

tr

Figure 3: Behavior of the RTT measurement program (k ≤ s)processors, as illustrated in Figure 3. To imbalance processor loads, the program has one dummy iteration processed
only one side of the processors. Let w be the length of thetime to process the iteration.
In the following, we build a RTT model using the LogGPS
model (Table 6). For want of space, only when k ≤ s is
described. Let RT T1 be the LogGPS RTT and let RT T2 be
the measured RTT. From Figure 3, RT T1 can be represented
as T1 + w + TRecv , where TRecv is the MPI Recv cost atprocessor P0. Then, as the value of w grows up, P0 becomesbusier than P1, so that we assume that P0 does not wait forP1 to call MPI routines. Therefore, if P0 calls MPI Send attime 0, then P1 calls MPI Send at time ts , or T1 + T2 + T3 .
On the other hand, P0 calls MPI Recv at time tr , or T1 +w. So, using equation (7), TRecv = max{T1 + 2T2 + T3 −w, 0} + T3 . Finally, when k ≤ s, RT T1 can be represented as
equation (12) shown in Table 6. From equation (12), whenw ≥ T1 +2T2 +T3 , RT T1 is independent of term T2 . That is,communication costs T2 can overlap with calculation costs
w. Besides, when s < k ≤ S and when k > S, RT T1 can also
be derived in a similar way, and Table 6 shows the results.
Figure 4 shows the relationship between RT T1 and message length, k, and Figure 5 shows the relationship between
RT T2 and k (when w takes a large value).
Now, we verify the results shown in Figure 4. First, when
w = W and k ≤ S, the gradient of the graph is Os +Or . If weassume that the communication overhead is represented asa constant, o , that is Os = Or = 0, this gradient takes zero.
Thus, the gradient of the graph, where w = W and k ≤ S,
implies that the overhead should be represented as a linear
function of message length. In Figure 5, the gradient takes
non-zero on all platforms. Therefore, it is much accurate
to represent the overhead as a linear function, which we
described in (D2).

300

1800

250

k=s

9000

k=S

k=s=S

150
100

1000
800
600

w=50
w=0

0
0

5000
4000
2000

w=500
w=0

200
0

1000 2000 3000 4000 5000 6000 7000 8000 9000

6000

3000

400

50

w=5000
w=0

1000
0

0

10000 20000 30000 40000 50000 60000 70000

Message length: k (bytes)

0

Message length: k (bytes)(a) Cenju-4 (s=S=1028)

k=S

7000

1200

RTT2 (us)

200

k=s

8000

1400
RTT2 (us)RTT2 (us)

10000

1600

5000 10000 15000 20000 25000 30000 35000
Message length: k (bytes)(b) Myrinet (s=8191,S=16383)(c) Fast Ethernet (s=1023,S=16383)

Figure 5: Measured Round Trip Time for diﬀerent message lengths
D(0) = 8o’+4L

D(W) = 8o’+4L+SOs+sGs+(S-s)Gl

w=W

2Os+Or+Gl

RTT1

D(W)
2(Os+Or+Gl)
2o’+W
W

D(0)

Os+Or

w=0

2(Os+Or+Gl)
4o’+2L02(Os+Or+Gs)sS

message length k (bytes)

Figure 4: LogGPS Round Trip Time for diﬀerent
message lengths

Second, when w = W , the graph is continuous at k = s(Fig. 4). This implies that time T2 should be represented assGs +(k −s)Gl +L. If we assume that time T2 is represented
as kGl + L, then the overhead, o , must take two values, one
for k ≤ s and another for s < k ≤ S, to keep the graphcontinuous at k = s when w = 0. If o takes two values, thegraph becomes discontinuous at k = s when w = W . This
result conﬂicts with the measured result, as shown in Figure
5. Therefore, when w = W , if the graph is continuous at
k = s, time T2 should be represented as sGs + (k − s)Gl + L.
This equation represents the performance character of thewormhole routing, which transmits contiguous packets that
follow the ﬁrst packet. Besides, from Figure 5, the Gap G
takes two values, Gs for k ≤ s and Gl for k > s, as we
described in (D3).
Third, when w = W and k ≤ S, the gradient of the graphis independent of both terms Gs and Gl (Fig. 4). That is,when k ≤ S, if processors are loaded in imbalance, communication libraries have more eﬀect on the performance of
MPI programs than networks. In fact, in Figure 5(c), whenw = 5000 and k ≤ 16383, the communication bandwidth is292 Mbit/s and exceeds the theory bandwidth of the Fast
Ethernet, 100 Mbit/s. This beneﬁt is produced by asynchronous protocols, that is, when P0 calls MPI Recv, themessage from P1 has already arrived at the buﬀer of P0, sothat P0 copies the message from own buﬀer.
Fourth, when w = 0 and s < k ≤ S, the gradient of thegraph is 2(Os + Or + Gl ). If we assume that 2(Os + Or +Gl ) > 0, then all MPI routine costs, deﬁned as equations (4)(11), take positive values. This can be explained as follows.
When Gl < 0, equation (9) is the only equation that is
possible to take a negative value among equations (4)-(11),but Os + Or + Gl > 0 guarantees that equation (9) takes
always a positive value. Therefore, if the assumption 2(Os +Or + Gl ) > 0 (that seems to be always true from Figure 4)
is true, then all MPI routine costs take positive values.
Finally, when w = W , D(w) in Figure 4 is dependent onterm S. Therefore, if processors are loaded in imbalance, theperformance of MPI programs become worse when the message length exceeds the value of S. Furthermore, the valueof S, deﬁned generally by MPI implementations, determines
the degree of performance loss.
Besides, to derive the LogGPS parameters from a parallel
platform, we compare the modeled result in Figure 4 andthe measured result in Figure 5. First, both parameters L
and o can be derived by solving two equations, which areyielded from two vertical axis segments. Similarly, solving
four equations, yielded from four gradients, can derive therest of parameters. The equations on Myrinet are as follows(W = 5 × 105 ns).
4o + 2L =2o + W =Os + Or =2(Os + Or + Gs ) =2(Os + Or + Gl ) =2Os + Or + Gl =2.850902 × 104
5.130990 × 105
9.430108
4.981455 × 101
1.737150 × 101
1.554669 × 101

(ns)
(ns)
(ns)
(ns)
(ns)
(ns)

4.4 An Example of Synchronization Analysis
In this section, we present an example of synchronization
analysis using the LogGPS model. The MPI program weused is the Gaussian elimination program as mentioned in§4.1. See [18] for the detail of the program.
To analyze the program, we developed a tool. The tool requires two inputs, the LogGPS parameters and trace data,and outputs the synchronization cost and predicted times
under the LogGPS model. The trace data is generated byrunning the target MPI program and consists of a sequenceof time-stamped MPI events. An event has the following
data: the call and return time of the MPI routine thatrecorded the event and the ID of the processor that called
the routine and the arguments of the routine. For want of
space, the detail of the tool is omitted.
First, to generate trace data, we executed the Gaussianelimination program on our cluster (Myrinet) with diﬀerent
matrix sizes: n = 128 to 4096. Second, we gave the tool two
inputs: the generated trace data and the LogGPS parameters on Myrinet (see Table 5). Finally, the tool supplied us
the synchronization costs and the predicted times under the
LogGPS model, as shown in the left column of Table 7. The
column shows (1) the measured times of the program, Tm1 ,Table 7: Measured and predicted times for the Gaussian elimination program (LogGPS)
Matrix Original code, S=16383 Original code, S=65536 Fragmented code, S=16383
size
Meas.
Pred.
Err. Meas.
Pred.
Err. Meas.
Pred.
Err.
Tm1
Tp1
σ1
Tm2
Tp2
σ2
Tm3
Tp3
σ3
n
256
0.047
0.050
6.4
0.047
0.050
6.4
0.047
0.050
6.4
0.121
0.128
5.8
0.121
0.128
5.8
0.121
0.128
5.8
512
1024
0.612
0.592
- 3.3
0.612
0.592
- 3.3
0.612
0.592
- 3.3
7.668
7.600
- 0.9
4.403
4.328
- 1.7
4.512
4.401
- 2.5
2048
4096
62.038 62.188
0.2 35.902 33.200- 7.5 43.795 39.571- 9.6
Times in seconds and errors in percentage
Sync. at senderSync. at receiverComm. overhead

Calculation

100%
90%

(M2) Fragment all messages into small messages, where thelength of each small messages is at most S.

80%
70%
60%
50%
40%
30%
20%
10%
0%

(M1) Change the value of S to a longer length by runtime
option.

(M3) Change the algorithm.

256

512 1024 2048 4096
Matrix size(a) Tp1 (Original, S=16383)

256

512 1024 2048 4096
Matrix size

256

512 1024 2048 4096
Matrix size(b) Tp2 (Original, S=65536) (c) Tp3 (Fragmented, S=16383)

Figure 6: Breakdowns of predicted times (LogGPS)(2) the predicted times under the LogGPS model, Tp1 , and(3) the errors, σ1 , deﬁned as σ1 = 100 × (Tp1 − Tm1 )/Tm1 .
The breakdowns of the predicted times, averaged over allprocessors, are also shown in Figure 6(a)From errors σ1 , the LogGPS model predicts the execution time within 7% errors. In addition, under all values of n except 1024, the synchronization costs account forroughly 50% of the predicted times (Fig. 6(a)). Therefore, the synchronization cost seems to be a performancebottleneck of this program. Furthermore, when n ≤ 1024,
the receiver synchronization costs are the major, in contrast,
when n > 1024, the sender synchronization costs are. In thisprogram, the length of messages became long as matrix size,n, grew up, and when n = 1024, the longest message was
16320 bytes near to the value of S, 16383 bytes. Therefore,
when n > 1024, as n grew up, messages were sent by Rndv.
protocol, and the sender synchronization cost increased.
Note that the value of S is 128000 bytes in the MPI implementation used through the contest. Thus, we think thatthe sender synchronization cost was not a performance bottleneck of the program when the contest held. In this time,
the LogGPS model allows us to detect the hidden performance bottleneck by analyzing its synchronization cost witha small value of S.
Thus, the LogGPS model allows us to divide MPI routine
costs into three inner costs, the sender synchronization cost,receiver synchronization cost and communication overhead,so that we can investigate the performance of MPI programsin detail.

4.5 An Example of eliminating the sender synchronization cost
In this section, we try to eliminate the bottleneck detectedin §4.4. Three methods can be employed to do this. Froman easy method, the methods are as follows.

First, method (M1) can be employed on the MPI implementation that can change the value of S by runtime option
and avoids modifying the program. Second, method (M2)
can be employed on any implementations but needs to modify the program to communicate all messages within length
S. Third, method (M3) can also be employed on any implementations but needs to modify the algorithm to reduce
synchronization costs and re-implement the program.
To eliminate the bottleneck, we can use the analysis asfollows. (1) Predict the performance with the actual valueof S, and this let us know what cost is paid for synchronization (our prediction method currently needs a run of
the target program). If we ﬁnd signiﬁcant synchronization
cost from the predicted result, then we have a chance toimprove the performance using this analysis. (2) Re-predictthe performance with the bigger value of S, and this let us
know what performance will be archived when eliminating
the bottleneck. (3) If the predicted performance becomes
better, we can apply method (M1) or (M2) to improve thereal performance. Otherwise, we should try method (M3).
In the following, we describe methods (M1) and (M2).
First, we investigated the longest message from the trace
data, and the length proved to be 65472 bytes when n =4096. We then re-analyzed its synchronization costs with
S = 65536 using the same trace data generated in §4.4. We
also re-executed the program with S = 65536 by specifying
the runtime option of MPICH-SCore (without any modiﬁcation of the program). The center column of Table 7 andFigure 6(b) show the results.
From Tm1 and Tm2 in Table 7, the change of S aﬀects
the measured time, Tm2 , when n > 1024. The same results
can be seen between the predicted times under the LogGPS
model, times Tp1 and Tp2 . From Figure 6(a) and (b), theelimination of the sender synchronization cost shortened thepredicted times, Tm1 , and the ratio of the synchronization
cost dropped from 50% to 7% when n = 4096.
Second, we describe method (M2). From Table 3 andTable 5, the communication cost of an S-byte message iscalculated as 288 μs on Myrinet (S = 16383). On the other
hand, when n = 4096, the total amount length of messages
that exceed the value of S (16383 bytes) was 22.5 MBytes.
Then, to send all fragmented messages, processors have torepeatedly send the fragmented messages for 1438 times.
The total amount communication cost for these messages isTable 8: Comparisons between the LogGPS model and the LogGP model (k: message length)
Item(D1) Synchronization(D2) Overhead o(D3) Bandwidth 1/G

LogGP-1 [1, 14]Constants for every k(included in o)Constants for every k,
divided between Ps and Pr
Constants for every k

10^6

LogGPS
Calculated by the call timeof MPI routines
Two linear functions on k,
divided between Ps and Pr
Two constants,
divided between k ≤ s and k > s

Two constants,
divided between k ≤ s and k > s
Two constants,
divided between k ≤ s and k > s

10^6

10000

blocking send overhead
nonblocking send overhead

10^4

10^3

10^5

Time (us)

10^5

10^4

1000

10^3
1

10

100

1000

gap per byte

blocking recv overhead
nonblocking recv overhead
Time (us)Time (us)LogGP-2 [17]Model separately

10000

100000

100

10
1

10

100

1000

10000

100000

1

10

100

1000

10000

Message length: k (bytes)

Message length: k (bytes)

Message length: k (bytes)(a) Send overhead(b) Recv overhead(c) Gap per byte

100000Figure 7: LogGP-1 parameters for Myrinet
calculated as 0.42 seconds, and this is much smaller than
the synchronization cost, 29.128 seconds when n = 4096.
Therefore, by fragmenting messages, we have a chance toimprove the program performance.
Then, we modiﬁed the program to repeatedly send andreceive messages within length S. Then, we re-executed themodiﬁed program and re-analyzed. The right column ofTable 7 and Figure 6(c) show the results.
As shown in the measured times, Tm3 , we also improved
the performance by method (M2). The predicted times, Tp3 ,show a trend similar to Tm3 . Note that errors σ3 are larger
than errors σ1 and σ2 when n = 4096. This is explained
as follows. If we employ method (M2), then the number ofasynchronous messages grows up, and this loads the buﬀerof the receiver. To avoid the buﬀer to overﬂow, MPI implementations control messages inside MPI routines. However,as the LogGP model does, the LogGPS model also assumes
that no delay occurs when copying messages into a buﬀer.
Therefore, the predicted times under the LogGPS model,
Tp3 , are smaller than the measured times, Tm3 .

4.6 A comparison between the LogGPS Modeland the LogGP ModelIn the following, we present a comparison between the
LogGPS model and the LogGP model. The program used
for the comparison is the Gaussian elimination program usedin the pervious section.
The deﬁnitions of MPI routine costs under the LogGP
model follow the deﬁnitions shown in [1, 14] and [17]. We callthe former LogGP-1 and the latter LogGP-2 in the following.
Table 8 lists the diﬀerences among the models, from theviewpoint of diﬀerences (D1), (D2) and (D3) described in§3. Note that the LogGP-1 model requires deriving bothparameters o and G for every message length. Furthermore,parameter o must be derived for every MPI routine.
First, according to each literature, we derived LogGP parameters. Table 9 and Figure 7 show the derived parameters. Second, we analyzed the synchronization cost of the
program, as we did for the LogGPS model. The trace data
we used were the same as for the LogGPS model. In precise

Table 9: LogGP parameters for Myrinet
Message length (bytes)
Model
Parameter≤ 8191> 8192L (ns)
7.46 ×103
o (ns)
see Fig. 7(a) and (b)LogGP-1
G (ns)
see Fig. 7(c)L (ns)
7.00 ×103
o (ns) 3.83 ×103 72.88 ×103
LogGP-2
G (ns)
24.98
8.85
g is unused in both models

way, we must build a synchronization model for the LogGP2 model, but for the accuracy of the analysis, we analyzed
the synchronization cost in the same way of the LogGPS
model. Table 10 and Figure 8 show the results.
Now we discuss about the results shown in Table 10 and
Figure 8. First, when n = 4096, the LogGP-1 model isinaccurate (σ4 =-45.6%). This is due to the lack of consideration for the sender synchronization cost. The LogGP1 model includes the sender synchronization cost into thesend overhead, os , and deﬁnes os as a constant value forevery message length. Therefore, given a synchronizationbottlenecked program, the model cannot predict its bottleneck (Fig. 8(a)), and the results become inaccurate. In contrast, the LogGP-2 model builds a synchronization modelapart from the communication cost, so that the LogGP-2
model is nearly as accurate as the LogGPS model (σ7 =0.7%). Summarizing the above discussions, both the rise of
bandwidth and need of synchronization are the dominantfactor in long messages. Therefore, to analyze the communication costs of long messages in accurate, models should
consider not only the rise of bandwidth but also the need ofsynchronization.
Second, when n ≤ 1024, the LogGP-1 model is also inaccurate (σ4 =-46.8%). This is due to the method for deriving
the parameters, as described in [1, 14]. Their method callsa measurement routine at each MPI call. Therefore, themeasurement cost could be high compared to the target, or
the cost of MPI routine, especially when the routine sends

Matrix
size
n
256
512
1024
2048
4096

LogGP-1

Table 10: Predicted times for the Gaussian elimination program (LogGP)
Original code, S=16383
Original code, S=65536
Fragmented code, S=16383
LogGP-1
LogGP-2
LogGP-1
LogGP-2
LogGP-1
LogGP-2
Pred.
Err.
Pred.
Err.
Pred.
Err.
Pred.
Err.
Pred.
Err.
Pred.
Err.
Tp4
σ4
Tp7
σ7
Tp5
σ5
Tp8
σ8
Tp6
σ6
Tp9
σ9
0.069
46.8
0.043 - 8.5
0.069
46.8
0.043 - 8.5
0.069
46.8
0.043 - 8.5
0.165
36.4
0.110 - 9.1
0.165
36.4
0.110 - 9.1
0.165
36.4
0.110 - 9.1
0.668
9.2
0.551 - 10.0
0.668
9.2
0.551 - 10.0
0.668
9.2
0.551 - 10.0
4.528 - 37.4
7.486 - 2.4
4.528
8.9
4.225 - 4.0
4.609
2.1
4.284 - 5.0
33.805 - 45.6 61.591 - 0.7 33.805 - 5.8 32.764 - 8.7 40.170 - 8.3 39.129 - 10.7
Times in seconds and errors in percentage
Sync. at senderSync. at receiverComm. overhead

Calculation

LogGP-2

100%
90%

100%
90%

80%
70%

80%
70%
60%

60%
50%
40%

Sync. at receiverComm. overhead

Calculation

50%
40%
30%
20%

30%
20%
10%
0%

Sync. at sender256

512 1024 2048 4096
Matrix size(a) Tp4 (Original, S=16383)

256

512 1024 2048 4096
Matrix size

256

512 1024 2048 4096
Matrix size(b) Tp5 (Original, S=65536) (c) Tp6 (Fragmented, S=16383)

10%
0%

256

512 1024 2048 4096
Matrix size(d) Tp7 (Original, S=16383)

256

512 1024 2048 4096
Matrix size

256

512 1024 2048 4096
Matrix size(e) Tp8 (Original, S=65536) (f) Tp9 (Fragmented, S=16383)

Figure 8: Breakdowns of predicted times (LogGP)a short message. In fact, the measurement cost, measured
by consecutively calling MPI Wtime, is 4 μs on our cluster, and this value is near to the MPI Recv cost, 6.55 μs(length k = 1). Then, we re-measured the parameters using
CPU counter (the Pentium RDTSC instruction), which requires lower overhead, but the predicted results were within
27.7% errors. Therefore, the target for measurement should
be bulked, and its cost should be derived by calculating thecost per call. Furthermore, bulking the MPI routines mustbe performed without loading the buﬀer of the receiver. To
do this, we measured the MPI routine costs indirectly, thatis, we measured RTT and not each MPI routine. In the
RTT measurement program, processors synchronize at every round trip, so only one message is stored in both buﬀers
at every round trip. Therefore, even if processors repeatedly
process the round trip operation, the buﬀer of the receiveris kept to be unloaded, so that we can measure the bulked
costs in accurate.
In contrast, when n ≤ 1024, from errors σ7 , the LogGP-2
model is accurate (maximum of -10.0%) but inferior to theerrors of the LogGPS model, σ1 (maximum of 6.4%). Thisis caused by the representation of the overhead, which the
LogGP-2 deﬁnes as a constant. That is, given a communicationbottlenecked program that communicates many short messages, the LogGP-2 model predicts its communication costlower than measured cost. The above discussions are summarized as follows. The overhead is the dominant factor inshort messages, so that to analyze the cost of short messagesin accurate, models should represent the overhead cost as
precise as possible, and a linear function of message lengthis one good choice.
Besides, the only diﬀerence among the models is the methodfor deriving parameters and the deﬁnitions of MPI routine
costs, so that we conﬁrmed that these diﬀerences greatly
aﬀect the accuracy of the model.

5. CONCLUSIONSIn this paper, we presented a new parallel computationalmodel, the LogGPS model, which is useful to analyze synchronization costs of parallel programs. To get better accuracy for programs written using high-level communication
libraries, the LogGPS model has two additional parameters(G and S) compared with the original LogP model. Parameter S represents the disadvantage of the special support forlong messages, the need of synchronization, while parameterG does the advantage, the raise of bandwidth, as the LogGP
model has done.
We also presented an example of synchronization analysis.
Through the analysis, we conﬁrmed that (1) the sender synchronization cost is a performance bottleneck in MPI programs and (2) the LogGPS model is more accurate than the
LogGP model. Therefore, parameter S is an important parameter to predict the performance of programs written using high-level communication libraries, which automaticallyswitch communication protocols. As a result, synchronization analysis is important when improving the performanceof parallel programs.
Finally, the work, to capture the buﬀer mechanism that
controls asynchronous messages, is remained.

6. ACKNOWLEDGMENTS
This work was supported by Grant-in-Aid for ScientiﬁcResearch, JSPS Research for the Future Program JSPSRFTF99I00903 and Kayamori Foundation of Informational
Science Advancement. We acknowledge the use of the NEC
Cenju-4 at NEC Parallel Processing Center. We would liketo thank the anonymous reviewers for their valuable comments.

7.

REFERENCES[1] K. Al-Tawil and C. A. Moritz. LogGP Quantiﬁed:
The Case for MPI. In Proc. 7th IEEE International
Symp. on High Performance Distributed Computing(HPDC-7), Chicago, IL, August 1998.
[2] A. Alexandrov, M. Ionescu, K. Schauser, and
C. Scheiman. LogGP: Incorporating Long Messages
into the LogP Model — One Step Closer Towards a
Realistic Model for Parallel Computation. In Proc. 7th
Ann. ACM Symp. on Parallel Algorithms andArchitectures (SPAA’95), pages 95–105, Santa
Barbara, CA, July 1995.
[3] N. J. Boden, D. Cohen, R. E. Felderman, A. E.
Kulawik, C. L. Seitz, J. N. Seizovic, and W.-K. Su.
Myrinet–A Gigabit-per-Second Local-Area Network.
IEEE Micro, 15(1):29–36, February 1995.
[4] G. Burns, R. Daoud, and J. Vaigl. LAM: An OpenCluster Environment for MPI. In In Proc. ofSupercomputing Symposium ’94 (SS’94), pages
379–386, Toronto, June 1994. available fromhttp://www.mpi.nd.edu/lam/.
[5] D. Culler, R. Karp, D. Patterson, A. Sahay,
K. Schauser, E. Santos, R. Subramonian, and T. vonEicken. LogP: Towards a realistic model of parallel
computation. In Proc. 4th ACM SIGPLAN Symp. on
Principles and Practice of Parallel Programming(PPoPP’93), pages 1–12, San Diego, CA, May 1993.
[6] A. C. Dusseau, D. E. Culler, K. E. Schauser, and R. P.
Martin. Fast Parallel Sorting Under LogP: Experience
with the CM-5. IEEE Transactions on Parallel andDistributed Systems, 7(8):791–805, August 1996.
[7] W. Gropp, E. Lusk, N. Doss, and A. Skjellum. A
High-Performance, Portable Implementation of the
MPI Message Passing Interface Standard. Parallel
Computing, 22(6):789–828, 1996. available fromhttp://www.mcs.anl.gov/mpi/mpich/.
[8] M. Homewood and M. McLaren. Meiko CS-2
interconnect elan – elite design. In Proc. IEEE Hot
Interconnects ’93 Symp., pages 95–105, August 1993.
[9] IBM Corp. IBM Parallel Enviroment for AIX, MPL
Programming and Subroutine Reference, Document
Number GC23-3893-00, 1995.

[10] IBM Corp. IBM Parallel Enviroment (PE),
http://www.rs6000.ibm.com/software/sp products/
pe.html, 2000.
[11] Y. Kanoh, M. Nakamura, T. Hirose, T. Hosomi, andT. Nakata. User-level Network Interface for a Parallel
Computer Cenju-4. Trans. of Information Processing
Society of Japan, 41(5):1379–1389, 1999.
[12] T. Kielmann, H. E. Bal, and K. Verstoep. Fast
Measurement of LogP Parameters for Message Passing
Platforms. In Proc. 4th Workshop on Runtime
Systems for Parallel Programming, pages 1176–1183,
May 2000.
[13] Message Passing Interface Forum. MPI: A
Message–Passing Interface Standard. International
Journal of Supercomputing Applications, 8(3/4), 1994.
[14] C. A. Moritz. Cost Modeling and Analysis: Towards
Optimal Resource Utilization in Parallel Compuer
Systems. PhD thesis, Royal Institute of Technology,
Stockholm, 1998.
[15] F. O’Carroll, H. Tezuka, A. Hori, and Y. Ishikawa.
The Design and Implementation of Zero Copy MPI
Using Commodity Hardware with a High Performance
Network. In International Conference on
Supercomputing ’98 (SC98), pages 243–250, July 1998.
available from http://pdswww.rwcp.or.jp/dist/score/.
[16] Parallel Software Contest (PSC95).
http://www.info.waseda.ac.jp/muraoka/project/
psc95/, 1995.
[17] D. Sundaram-Stukel and M. K. Vernon. Predictive
Analysis of a Wavefront Application Using LogGP. In
Proc. 7th ACM SIGPLAN Symp. on Principles andPractices of Parallel Programming (PPoPP’99), pages
141–150, Atlanta, GA, May 1999.
[18] O. Tatebe. Software, http://phase.etl.go.jp/%7etatebe/software/index-j.html, 2000.
[19] T. von Eicken, D. E. Culler, S. C. Goldstein, andK. E. Schauser. Active Messages: A mechanism for
integrated communication and computation. In Proc.
19th Ann. International Symp. on Computer
Architecture (ISCA), pages 256–266, Gold Coast, May
1992.