A Performance Analysis Tool for Performance Debugging ofMessage Passing Parallel Programs
Fumihiko Ino and Kenichi Hagihara
Graduate School of Information Science and Technology
Osaka University
1-3 Machikaneyama, Toyonaka, Osaka 560-8531, Japan
E-mail: ino,hagihara@ist.osaka-u.ac.jp
Abstract
This paper describes the design and implementation of
Gordini, a performance analysis tool that is capable of automatically locating places in the source code where a communication optimization technique can be applied for performance debugging of message passing parallel programs.
Our automatic search approach is based on data dependence analysis on trace ﬁles. It currently supports threetechniques: communication–computation overlap, message
aggregation, and collective communication. In case studies, Gordini assists us in improving the performance of sophisticated programs coded by experts, the two ﬁrst prize
winners of software contests. Therefore, we believe that our
automatic approach is useful for application developers tolocate communication bottlenecks in programs.

1 Introduction
Developing efﬁcient parallel applications is not easycompared to sequential applications.
For example,
message passing parallel applications with inappropriate
data/workload distribution can easily result in poor performance due to frequent communication and load imbalanceamong processors. Therefore, to create faster applications,
it is important to locate and eliminate performance bottlenecks that limit application performance.
In order to assist developers in performance analysis of
message passing parallel applications, many performance
analysis tools [5] have been proposed in the past. Such tools
offer useful capabilities based on postmortem analysis of a
trace ﬁle, namely a ﬁle of time-stamped events recorded
during program execution. For example, Paragraph [8],VAMPIR [13], Jumpshot [23], and TAU [18] provide thetimeline view of events and messages, which enables developers to intuitively understand the status and behavior ofprocessors along the time axis. They also are capable ofdisplaying several diagrams with statistical analysis of program execution and that of communication primitives.
In contrast to these postmortem tools, some tools employ dynamic instrumentation techniques to analyze largescale applications running for hours or days on hundreds ofprocessors. AIMS [22] supports source code instrumentation, runtime monitoring, graphical execution proﬁles, performance indices, and automated modeling techniques inorder to support performance visualization, proﬁling, andmodeling. Paradyn [12] performs automatic runtime analysis for performance bottleneck search based on thresholds
and a set of hypotheses structured in a hierarchy. For example, it locates a synchronization bottleneck if waiting timeis greater than 20% of the program’s execution time.
Thus, earlier tools offer useful capabilities for performance analysis. However, only Paradyn guides developers
directly to performance bottlenecks in applications. Most of
the tools need developers to (1) locate performance bottlenecks in graphical views, (2) identify the causal reasons fortheir occurrences, and (3) determine the methods for theirelimination. All of the above performance debugging processes are due to developers. Therefore, even if developers notice that a communication routine spends most of theoverall execution time, they must guess the causal reasons.
For example, it may be due to the long waiting time forsynchronization between processors, or simply be due tothe accumulated time for iterative execution of the routine
inside a loop body. Accordingly, some developers fail to
identify the causal reasons, resulting in poor performance.
Furthermore, ﬁnding performance bottlenecks in largescale applications is not easy for developers, because suchapplications usually generate large trace ﬁles, which makegraphical views complicated. These complicated views lose
the visual advantage of intuitive understanding, so that evenexperienced developers may miss performance bottlenecks
hidden in graphical views.

Proceedings of the 2004 International Conference on Parallel Processing Workshops (ICPPW’04)
1530-2016/04 $20.00 © 2004 IEEE

Paradyn supports this search process by locating performance bottlenecks with their causal reasons. However, developers need to consider how to eliminate the bottlenecks.
Furthermore, because its search strategy is structured in ahierarchy like as modules, routines, and statements, somebottlenecks can be missed in a higher level of the hierarchy.
Therefore, detailed analysis may be required to expose thebottlenecks hidden in a lower level of the hierarchy.
To overcome issues (1)–(3), our tool aims at satisfying
the following two requirements.

MPI program

Developers

Coding

GordiniAutomatic
instrumentation

Performance visualization- Source code view
- Line/circle diagram view
- Timeline view

Performance analysis- Hotspot analysis- Communication analysis- CPU time analysis

Performance bottleneck search

R1: The tool is capable of locating performance bottlenecks automatically.
R2: The tool is capable of guiding developers how to eliminate the located performance bottlenecks.
Satisfying the above requirements frees developers fromperformance bottleneck search and from determining themethods for bottleneck elimination, allowing them to focus
on program modiﬁcation.
In this paper, we describe the design and implementationof Gordini, a performance analysis tool that aims at satisfying requirements R1 and R2 for message passing parallel
programs. The key capability of Gordini is automatic bottleneck search based on data dependence analysis on trace
ﬁles. Gordini directs developers to places in the source code
where communication optimization techniques can be applied. It currently supports the following three techniques:communication–computation overlap [17], message aggregation [2], and collective communication. We also present
some case studies in which Gordini successfully improves
the performance of sophisticated programs.

2 Overview of Gordini
2.1 Architecture
Gordini currently supports parallel programs written using the C language and the Message Passing Interface (MPI)
standard [11]. It runs on computing platforms where theC++ language and the Tcl/Tk toolkit, a graphical user interface (GUI) toolkit, are available.
Gordini consists of three components: performance bottleneck search, performance analysis, and performance visualization modules, as shown in Figure 1. The performance visualization module offers typical views including
line/circle diagram and timeline views for presenting performance analysis results. It also provides a source codeview for presenting bottleneck search results. Visualizing
the bottlenecks directly on the source code is essential toassist developers in performance debugging. If they are notpresented on the source code, developers have to locate theplaces that trigger the bottlenecks. Therefore, developers

MPI_Send (sbuf, 1, ...
i = i + k;

- Communication-computation overlap- Message aggregation- Collective communication

mpi2g

G_MPI_Send (FILE, LINE, sbuf, 1, ...
i = i + k; G_CAL(FILE, LINE, 3, &(i), &(i), &(k));

Compilation
Linkage
Parallel execution

Instrumentation
library

Parallel computer
Generation
Trace files

Figure 1. Performance debugging processwith Gordini.

can fail to eliminate them, if the search results are not associated with the source code.
Figure 1 shows the performance debugging process with
Gordini. First of all, developers must instrument the target
MPI programs to generate trace ﬁles. This instrumentation
can automatically be done by mpi2g, an instrumentation
tool provided by Gordini. It performs pattern matching to
replace all of the MPI routines and assignments in the program with instrumented routines and assignments, respectively. Next, they have to execute the instrumented code ona parallel computer so that generate trace ﬁles. Giving thetrace ﬁles to Gordini provides developers helpful insights
and hints for performance improvement. According to thisinformation, developers are required to investigate whether
the located places can easily be modiﬁed, and if possible,
they can apply optimization techniques to the places.
Figure 2 shows an example of the source code view,which present search results obtained by data dependence
analysis (described later in Section 3). The right-side
window presents a performance bottleneck located on thesource code. On the other hand, the left-side windowshows the same bottleneck located for every event, aiming to present more detailed results. This event-level view
is motivated by a situation where optimization techniques
are conditionally applicable to a statement. For example,
suppose that an assignment is placed inside a loop body.
Then, this statement generates many computation events,and only the ﬁrst ten of them may be allowed to overlap
with a communication routine, as presented in Figure 2. To
deal with this conditional case, Gordini presents the resultson the event-level view in addition to the source code view.
In Figure 2, there is a triple-nested iteration at lines 78,
84, and 85. In this case, developers can overlap communication with computation in three steps. First, they should
separate the middle loop into two loops, a loop for the

2 Workshops (ICPPW’04)
Proceedings of the 2004 International Conference on Parallel Processing
1530-2016/04 $20.00 © 2004 IEEE

Table 1. Events andrecorded in trace ﬁles.
Event typeAll
Computation
Send/receive

theirinformation

Recorded information
Event ID, corresponding source code,and occurrence time
Read/write address
All arguments including source/destination
process, send/receive address, and its size

ation between buffers.

Figure 2. Source code view of Gordini. The
right- and left-side windows present a search
result for statements and events, respectively. The right-side window indicates that
send and receive routines at lines 81 and 83
can overlap with computations at lines 86 and89. The left-side window shows this in moredetail and enumerates overlappable eventswith their corresponding lines in the sourcecode and their execution number associatedwith each loop. It indicates that communication events generated from lines 81 and 83
can overlap with computation events generated from line 86 during from the ﬁrst to thetenth iterations of the most inner loop (line85) under the ﬁrst iterations of the remaining
two loops (lines 78 and 84).

ﬁrst ten iterations and a loop for the remaining iterations.
Then, they should replace blocking routines (MPI_Send
and MPI_Recv) with nonblocking routines (MPI_Isend
and MPI_Irecv), and ﬁnally, placing waiting routines(MPI_Wait) between the separated loops realizes overlap.

2.2 Trace File Generation
Trace ﬁles are generated for each process participating inparallel execution. The processes record all events occurred
during the execution. Table 1 shows the recorded eventswith their information classiﬁed into two groups: common
information recorded for every event and unique information recorded for speciﬁc events. This information is thebasis for the bottleneck search module of Gordini.
A send event and a receive event correspond to an execution of a send routine and that of a receive routine. A computation event corresponds to an execution of other statements such as an assignment to a variable and a copy oper-

3 Performance Bottleneck Search Based on
Data Dependence Analysis
This section describes the key capability of Gordini, anautomatic bottleneck search based on data dependence analysis. Due to the space limitation, we present algorithms
for communication–computation overlap and message aggregation.

3.1 Motivation for Data Dependence Analysis
All the three techniques mentioned in Section 1 havea common characteristic. That is, they try to eliminate
communication bottlenecks by optimizing the execution order of statements. Therefore, when applying these techniques to a program, it is necessary to take into consideration data dependence among executed statements, namely
events. Otherwise, the modiﬁed program may show buggy
behaviors due to broken dependences. Thus, data dependence analysis is required to search places where the threetechniques can be applied.
denote a relation that represents data dependenceLetamong events. Data dependence from event to event ,, can be classiﬁed into the following three types: output, ﬂow, and anti dependences [2]. For events and  suchthat
, the occurrence of must be prior to that of .
We also deﬁne relationfrom a set of events to an represents that, where
event.
is a set of events and  is an event.



 

3.2 Search Algorithm for
Computation Overlap

Communication–

In order to assist developers in communication–
computation overlap, Gordini computes a set of computation events for each communication event in a trace ﬁle.
Figure 3 describes our search algorithm forcommunication–computation overlap.
The algorithm
½  ¾       , where  reprerequires trace ﬁlesents the -th event occurred on a process and  represents 

3 Workshops (ICPPW’04)
Proceedings of the 2004 International Conference on Parallel Processing
1530-2016/04 $20.00 © 2004 IEEE

Algorithm for communication–computation overlap
 ½  ¾      , a trace ﬁle with  events
Input:
Outputs:  ½  ¾        and ½  ¾       , where represents a set of computation events that canoverlap with communication event 
1. ;
2. for   downto do begin
3.
if (  is not communication event) then continue;
 
;
4.

5.
 ;  ;to  do begin// Forward search
6.
for
7.
if (   ) then break;8.
Add event  to set  ;9.
end
  downto do begin // Backward search
10.
for
11.
if (    ) then break;12.
Add event  to set  ;13.
end
14. end

















Figure3.
Searchalgorithm
communication–computation overlap.

for

ej-1

ei , ei ek+1

ejProcess 2











Time

...
ei (=cm)ek+1

Om: Overlappable with ei

Process 1Figure 5. Search algorithm for message aggregation.

Data dependence

ej-1

Algorithm for message aggregation
 ½  ¾      , a trace ﬁle with  events
Input:
Outputs: ½  ¾       ,  sets of aggregatable send events;
1. // Pre-processing
2. for   downto do begin
3.
if (  is not send event) then continue;  downto do begin
4.
for
5.
if (    ) then break;6.
Swap event  with event  ·½ ;7.
end
8. end;9. // Event classiﬁcation
10. while (  ) do begin
11.
if (  is not send event) then continue;
 
;
12.

13.
 ;  ;
14.
while (  ) do begin
 
;
15.
16.
if (   ) then break;17.
if (  is not send event) then continue;
18.
Add event  to set  ;19.
end
20. endek
Time

Figure 4. Search process for communication–
computation overlap.

the number of events. Then, it returns a set of commu ½  ¾      , where   
nication events,
is a communication event and     is the numberof communication events in  , with its overlappable
computation events ½  ¾       , where  is a set ofcomputation events overlappable with      .
Figure 4 shows a search process for communication–
computation overlap. Because any computation event  thatoverlaps with communication event  must satisfy       , for communication event    , thealgorithm computes a sequence of events    ·½      such that ½          ·½      . To compute this, the algorithm performs forward andbackward search from  until ﬁnding event  such that   and    , respectively.
Thus, the algorithm searches computation events thatcan overlap with a communication event. Another ap-

proach is to search communication events that can overlap with a computation event. However, this opposite approach possibly results in less overlappable events because
programs usually use temporary working variables, whichcause many data dependences among computation events
due to repeated assignments to the variables. Therefore,
searching from communication events is necessary to avoid
such many data dependences among computation events.
Note here that our algorithm independently analyzes
each of trace ﬁles generated on processes. Because the algorithm is based on data dependence analysis, it does not require clock synchronization of processors during trace ﬁlegeneration. We discuss on the timing gap among processors’ clocks later in Section 5.3.

3.3 Search Algorithm for Message Aggregation
Our algorithm for message aggregation classiﬁes thesend events in a trace ﬁle into groups of send events suchthat all events in the same group can be aggregated into one
message send.
Figure 5 describes the algorithm, which requires traceﬁle   ½  ¾       , and then returns  sets of send
events ½  ¾     , where       is a groupof send events that can be aggregated with each other and 
is the number of classiﬁed groups.

4 Workshops (ICPPW’04)
Proceedings of the 2004 International Conference on Parallel Processing
1530-2016/04 $20.00 © 2004 IEEE(0) Initial state

4 Case Studies

Data dependence

ej

ej

ei

ei
Time

Process 1

...
Time

Process 2(1) Pre-processing
Moving ei forward before ej
TimeProcess 1

...
Time

Process 2
Data dependence(2) Event classification

Am

ej+1

Am: Events aggregatable with ei
ei (=cm)

Time

Process 1

...

ei+1
Process 2

ej+1

ej

Time

ei+2

Figure 6. Search process for message aggregation.

The algorithm mainly consists of two processing stages.
In the ﬁrst stage, it alters the execution order of send eventsin order to aggregate more events. After this alternation,
the algorithm generates a pre-processed trace ﬁle in which
send events are moved forward as long as data dependences
are kept. In the succeeding stage, the algorithm classiﬁes
aggregatable send events from the head to the tail of the
pre-processed trace ﬁle.
Figure 6 shows a search process for message aggrega  , the algorithm computes ation. For send event
sequence of events ·½  ·¾       such that      ·½                  is all of the events sending , where   

to the same destination in ·½  ·¾       . To compute
this, it performs forward search from  until ﬁnding event
such that   .
During the event classiﬁcation stage, the algorithm investigates whether the occurrence of send events can be delayed. Therefore, all events in  must be aggregated with
 . Forthe last occurred event   , where  example, all events in  presented in Figure 6 must be
aggregated with event  . Note here that the pre-processing
stage enables event ·¾ to be grouped into  . Without the pre-processing stage,    ·½ prevents adding
event ·¾ to  , because ·¾ is originally occurred after ·½ .

In order to demonstrate the usefulness of Gordini, weapplied Gordini to two sophisticated MPI programs [1, 20]that won the ﬁrst prize in NEC Cenju-3 category of Parallel
Software Contest (PSC) held in 1995 [14] and in 1996 [15].
We tried to improve their performance on an NEC Cenju3 [10] and an NEC Cenju-4 [9] using trace ﬁles generated
on a cluster of PCs. The reason why we use our cluster for
trace ﬁle generation is simply due to the limitation on usageof the storage available on the Cenju-3 and Cenju-4.
Note here that using trace ﬁles for different platforms is
an uncritical problem for regular programs, which show thesame behavior for different inputs. This beneﬁt comes fromour data dependence analysis approach that requires only
the order of occurred events.
Our cluster has a total of 16 nodes with Pentium II processors running at 450MHz. These nodes are interconnected by a Myrinet switch [3] yielding a full-bandwidth of
1.28 Gb/s. The MPI implementation used for experiments
is MPICH [6], a scalable implementation available on mostof distributed memory multiprocessor systems.

4.1 Case 1:
Performance Improvement by
Communication–Computation Overlap
The ﬁrst program [20] solves a system of linear equations, , by using Gaussian elimination, where
represents a known dense matrix of size  , represents
the required solution vector, and  represents a known vector of size . The source code is approximately in 5000
lines. In the contest, it solves several equations ranging
from   to  on a 64-node Cenju-3.
We instrumented all statements in the kernel of the code,
including MPI routines, assignments, and memory copy
primitives, but excluded uncritical statements, for example,
assignments for array initialization. Then, we executed the
instrumented program with   on   , where  isthe number of processors. The trace ﬁles are 70 MB in sizeand contains approximately 1.2 million events.
Table 2 summarizes search results obtained by Gordini after about 20 minutes search on a Pentium II
450MHz computer. Gordini indicates that communication–
computation overlap and message aggregation can be applied to this program, however, collective communication
is inapplicable.
According to these results, we investigated if the locatedplaces can easily be modiﬁed, and then decided to apply
communication–computation overlap to two places. The
remaining places are left as they are, because applying thetechniques to these places is not easy due to the structure of
the source code. For example, Gordini points out that several communication routines can be aggregated, however,

5 Workshops (ICPPW’04)
Proceedings of the 2004 International Conference on Parallel Processing
1530-2016/04 $20.00 © 2004 IEEE

Table 2. Search results obtained by Gordini.
Trace ﬁles are generated on 4 processors.
,  , and  represent the number of locatedevents in trace ﬁles, that of located MPI routines in source code, and the time in minutes
required for search, respectively.
Gaussian
Optimization technique

ResultsComm.–Comput. overlap
Message aggregation
Collective comm.



922 14
244 6
0
0



DFT

 



Time

Results





22
20
20

109
12
0

22
2
0



Time



5
2
1

Table 3. Execution time for Gaussian elimination program on Cenju-4, where  represents
the number of processors.

Problem
Execution time (s) Speedup Execution time (s) Speedup
size
BeforeAfter(%)
Before
After
(%)



128
256
512
1024
2048
4096

½

¾

0.014
0.014
0.054
0.047
0.351
0.240
3.367
1.918
29.454 15.783
234.418 121.515



½

¾



0.0
12.9
31.6
43.0
46.4
48.2

0.023
0.052
0.152
0.846
7.149
60.114

0.023
0.052
0.135
0.577
4.084
31.748

0.0
0.0
11.2
31.8
42.9
47.2

they are called from different loops placed in different ﬁles.
We also prevent modifying the places with short execution
time, because such places are small bottlenecks, which possibly give little improvement on the overall performance.
½ ¾ ½ , where ½ andTable 3 shows ½ , ¾ , and 
¾ are the execution times before and after program modiﬁcation, respectively, and  is the speedup on execution time.
Here, the execution time is measured for Gaussian elimination and backward substitution on the Cenju-4. Because theoriginal program is modiﬁed after the software contest, we
failed to measure its execution time on the Cenju-3 due toruntime error.
Although there is no improvement when   ,speedup  increases with problem size , so that ½ reduces
approximately in half when    . Thus, we obtain better improvement as  increases. This better improvement isderived from the modiﬁed places that emerge as larger bottlenecks with the increase of . Actually, by measuring ,
the accounting rate of the time for the modiﬁed places to theoverall time ½ on    , we found that  increases from
7.6% to 99.5% when increasing  from 256 to 4096. Thus,
this program has a performance characteristic that enables
reducing more execution time as problem size increases.

4.2 Case 2: Performance Improvement by Message Aggregation
We also applied Gordini to a complex DFT program [1]that won the ﬁrst prize in PSC’96. In this contest, it solves a
problem with size    on a 128-node Cenju-3.
The program is approximately in 1000 lines.
As we did in Section 4.1, we instrumented only the kernel of this program by using mpi2g. We then generated a
trace ﬁle for    and   .
As shown in Table 2, Gordini points out that
communication–computation overlap and message aggregation can be applied to the program. According to theseresults, we modiﬁed all the located places: 16 places forcommunication–computation overlap and two places formessage aggregation. The remaining places are small bottlenecks, so that we disregarded them. Note here thatmessage aggregation was applied to collective (gather andbroadcast) communication routines.
Table 4 shows ½ ,   ,  , ¾ , and speedup  ½ ¾ ½ , where ½ is the execution time before program modiﬁcation,   ,  , and ¾ are the execution timeafter applying communication–computation overlap, after
applying message aggregation, after applying both, respectively. Note here that the problem size of    on   is unmeasured due to physical memory exhaustion.
  , message aggreWhen    andgation gives shorter execution time than communication–
computation overlap. In contrast, the most effective technique when    and    is communication–
computation overlap rather than message aggregation.
This can be explained as follows. The cost for collective communications increases with , because at least  
communication steps are required to gather (or broadcast)data. At each step, receiver processors need to wait for
sender processors. Therefore, applying message aggregation to collective communications reduces the occurrence of
this waiting operation, realizing shorter waiting time. Thus,
message aggregation further reduces the execution time as increases. Furthermore, increasing  with ﬁxed decreases the amount of computations per processor, so thatthe accounting rate of communication time to overall time
becomes larger while that of computation time becomes
smaller. In this situation, reducing communication time
is more effective than masking it with computation time,so that message aggregation gives better improvement thancommunication–computation overlap.
inOn the other hand, decreasing  with ﬁxed
creases the amount of computations per processor, so that
communication–computation overlap is expected to yield
better improvement. Actually, ½ and   when  indicate that it reduces the execution time by 0.022
s on    , however, it fails to reduce it on   .

6 Workshops (ICPPW’04)
Proceedings of the 2004 International Conference on Parallel Processing
1530-2016/04 $20.00 © 2004 IEEE

Table 4. Execution time for complex discrete Fourier transform (DFT) program on Cenju-3, where
represents the number of processors.   ,  , and ¾ are the execution time after applying
communication–computation overlap, after applying message aggregation, after applying both, respectively.

 



Execution time (s)Before
After

16
32
64
128

1.565
0.877
0.450
0.213

½

 

1.543
0.865
0.447
0.213



1.560
0.865
0.440
0.193

¾

1.538
0.855
0.438
0.193

Speedup
(%)



1.73
2.51
2.67
9.39

5 Discussion
5.1 Usefulness of Gordini
Gordini focuses on the fact that communication, as well
as load imbalance, probably tends to be sources of performance bottlenecks on current distributed memory multiprocessor systems. Therefore, the performance of programs
written by MPI beginners can probably be improved by thethree search functions of Gordini, because such programs
usually take little care to performance.
In contrast, MPI experts carefully write programs toachieve higher performance. However, our case studies
show that Gordini also can improve the performance of
sophisticated programs. This improvement indicates that,even MPI experts can leave performance bottlenecks unaddressed, because earlier tools focus only on statistical performance data such as the execution time and the amount of
messages. Such statistical data never makes developers becertain whether all bottlenecks are already eliminated. On
the other hand, Gordini focuses on data dependence so thatlocates every place where the three optimization techniques
can be applied. Thus, the advantage of Gordini is to enable
developers to prevent leaving performance bottlenecks fromthe viewpoint of data dependence analysis.
When using earlier tools, which perform statistical analysis on performance data, it is a time consuming task to locate the places where communication–computation overlap
is applicable, because this technique masks communication
time with computation time as long as data dependence is
kept. Such statistical tools do not consider data dependence,
so that developers have to search overlappable statementsin the source code. In contrast, Gordini directly locatessuch places in the source code, so that it frees developersfrom searching them. However, developers must investigate whether they actually can overlap the located places,
as described later in Section 6.
The statistical analysis approach does not effectively  Execution time (s)Before
After

½

—
3.990
2.021
1.030

 

—
3.878
1.972
1.011



—
3.972
1.974
0.972

¾

—
3.874
1.927
0.965

Speedup
(%)



—
2.91
4.65
6.31

work for programs where all of statements spend uniformly
the same execution time, because it probably present uniform graphical views for such programs, so that developers
are unable to locate performance bottlenecks. In the worst
case, they may believe that there is no performance bottleneck. Gordini can deal with such programs because it
focuses on data dependence rather than statistical data.
However, our data dependence analysis locates performance bottlenecks without regarding the execution time.
Therefore, it can direct developers to the places with short
execution time, where only little improvement can beachieved. Actually, in Section 4.1, we found that there isalmost no improvement on execution time when  is a smallvalue (%). A similar situation occurs in Section 4.2,
which shows less improvement due to short communication
time. Therefore, we think that the combined use of data
dependence and statistical data analyses is essential to efﬁciently improve the performance of parallel programs. For
example, developers can locate performance bottlenecks bydata dependence analysis, and then they can give priority
to the located bottlenecks by sorting their execution timethrough the use of statistical data analysis.

5.2 Automatic Search Approach
Gordini frees developers from performance bottlenecksearch. This capability classiﬁes performance data into
two groups, useful data relating to performance bottlenecks
and the other remaining data, so that enables presenting
only useful data to developers. For example, for the Gaussian elimination program presented in Section 4.1, Gordini shows only 20 lines of the source code, 14 lines forcommunication–computation overlap, and 6 lines for message aggregation, from trace ﬁles containing 1.2 million
events. Thus, automatic search approach is necessary topresent less but useful performance information to developers.
Because the current implementation of Gordini holds the

7 Workshops (ICPPW’04)
Proceedings of the 2004 International Conference on Parallel Processing
1530-2016/04 $20.00 © 2004 IEEE

entire of trace ﬁles in order to search performance bottlenecks, it has a limitation on the size of trace ﬁles. For example, a computer with 2 GB of main memory can deal
with the maximum of 22 million events. However, this limitation will be eliminated because the algorithms presented
in Section 3 requires a portion of trace ﬁles so that allows
the on-the-ﬂy computation of bottleneck search.
Generally, the size of trace ﬁles increases with that ofproblems and the number of processes. Therefore, satisfying requirement R1 presented in Section 1 is essential toensure the performance improvement of parallel programs.

Any tool based on trace ﬁles should consider the timing
gap among processors’ clocks because this gap causes discrepancies, for example, the occurrence time of a receive
event is prior to that of a matching send event. Although
MPI provides a wall clock mechanism (MPI_Wtime), it
is not precise enough for event based tools where an event
corresponds to an execution of a statement. This timing gap
is a trivial issue for Gordini, because its data dependence
analysis requires only the occurrence order of events.
However, if a wall clock mechanism removes this gap
in the future, our analysis can be augmented by exploiting the occurrence time of events. For example, deﬁning
a wait event from the occurrence of a send event and that ofa matching receive event may realize more useful analysis
based on wait events.

best of our knowledge, only Hall et al. [7] presents a strategy for interprocedural optimization but they manually applies optimizations according to the strategy, because they
have not implemented interprocedural optimizations in their
compiler. Thus, most of static approaches are based on local
optimizations, where optimizations are restricted to a single
block/loop in the source code, mainly due to the complexityand expense of global optimizations such as interprocedural
optimizations.
Gordini currently considers data dependence but no control dependence. Therefore, developers have to investigate
the located places whether they are actually overlappable.
For example, suppose that Gordini points out that statement
S1 is overlappable with communication routine C. If the
program is written as if-S1-else-S2, then developers haveto check if S2 is also overlappable with routine C. If there isdata dependence between S2 and C, developers are required
further to check if the branch always executes S1. Watanabe and Yuasa address this problem by restricting the search
space into a block, where no control dependence exists.
Summarizing the above discussions, postmortem approach locates more overlappable computations than static
approach does, so that yields higher performance. However,it requires developers to investigate if the located bottlenecks have control dependence, while static approach guarantees valid optimizations by means of rigorous analysis.
Therefore, postmortem approach is effective for developers
to give a helpful advice for deterministic applications thatshow regular behavior in every program execution.

6 Related Work

7 Conclusions

Gordini currently needs trace ﬁles generated by program
execution. In contrast to this postmortem approach, Watanabe and Yuasa [21] employ static approach for communication optimization in a data parallel compiler. They present
a compilation technique that realizes communication–
computation overlap without program execution. Theirtechnique realizes communication–computation overlap bymoving assignments, however, it assumes that overlappableassignments and communications are placed in the same
block, so that it is unable to overlap communication withcomputation across different blocks. On the other hand,
Gordini is based on postmortem analysis, which is independent of the structure of the source code. Overlapping
communication with more assignments is essential to yieldhigher performance, because communication routines generally require more execution time than assignments do.
Other data parallel compilers [4, 7, 16, 19] also perform
communication optimization including message aggregation and collective communication. However, most of themfocus on a single nested loop because optimization acrossdifferent loops is a complex and expensive problem. To theWe have presented the design and implementation of
Gordini, which is capable of locating places in the sourcecode where typical optimization techniques can be applied.
Gordini performs data dependence analysis on trace ﬁlesand supports three techniques for communication bottlenecks: communication–computation overlap, message aggregation, and collective communication. Gordini guides
developers to performance bottlenecks in the source codeand presents a speciﬁc technique for their elimination.
In case studies, Gordini successfully assists us in improving the performance of two sophisticated MPI programs that won the ﬁrst prize of parallel software contests.
Therefore, we believe that our automatic search approachbased on data dependence analysis is useful to improve theperformance of message passing parallel programs.
In particular, our approach is effective for MPI programswith the following three characteristics.

5.3 Clock Synchronization

Regular behavior: Postmortem approach is effective fordeterministic applications that show regular behavior
in every program execution.

8 Workshops (ICPPW’04)
Proceedings of the 2004 International Conference on Parallel Processing
1530-2016/04 $20.00 © 2004 IEEE

Communication bottlenecks: Because we currently focus
on communication bottlenecks, our approach can improve applications with communication bottlenecks
but needs other techniques to improve applications
with computation or input/output bottlenecks.
Global bottlenecks: In contrast to the above two requirements, this clariﬁes the difference between the effectiveness of postmortem approach and that of static approach. Postmortem approach is effective for global
bottlenecks, namely performance bottlenecks acrossdifferent blocks, as well as local bottlenecks, namely
performance bottlenecks within a single block.
Future work includes the development of performance
prediction method for guiding developers to places onlywith signiﬁcant improvement. This method is essential
to prevent misleading developers into wrong modiﬁcation
with performance loss. Furthermore, coupling Gordini withstatic techniques could provide more rigorous search. For
example, control dependence can be addressed by performing rigorous data ﬂow analysis at the instrumentation time.

Acknowledgments
This work was partly supported by JSPS Grant-in-Aid
for Young Scientists (B)(15700030) and Network Development Laboratories, NEC. We would like to thank the anonymous reviewers for their valuable comments.

References[1] T. Araki. Algorithm for complex discrete Fourier transform(DFT), June 1996. http://phase.hpcc.jp/phase/
sacsis/PSC96/archives/winners/araki.html(In Japanese).
[2] D. F. Bacon, S. L. Graham, and O. J. Sharp. Compiler transformations for high-performance computing. ACM Computing Surveys, 26(4):345–420, Dec. 1994.
[3] N. J. Boden, D. Cohen, R. E. Felderman, A. E. Kulawik,
C. L. Seitz, J. N. Seizovic, and W.-K. Su. Myrinet: A gigabitper-second local area network. IEEE Micro, 15(1):29–36,
Feb. 1995.
[4] Z. Bozkus, A. N. Choudhary, G. Fox, T. Haupt, S. Ranka,
and M.-Y. Wu. Compiling Fortran 90D/HPF for distributed
memory MIMD computers. J. Parallel and Distributed Computing, 21(1):15–26, Apr. 1994.
[5] S. Browne, J. Dongarra, and K. London. Review of
performance analysis tools for MPI parallel programs,
Dec. 1997. http://www.cs.utk.edu/˜browne/
perftools-review/.
[6] W. Gropp, E. Lusk, N. Doss, and A. Skjellum. A highperformance, portable implementation of the MPI message
passing interface standard. Parallel Computing, 22(6):789–
828, Sept. 1996.

[7] M. W. Hall, S. Hiranandani, K. Kennedy, and C.-W. Tseng.
Interprocedural compilation of Fortran D. J. Parallel andDistributed Computing, 38(2):114–129, Nov. 1996.
[8] M. T. Heath and J. A. Etheridge. Visualizing the performance of parallel programs. IEEE Software, 8(5):29–39,
Sept. 1991.
[9] T. Hosomi, Y. Kanoh, M. Nakamura, and T. Hirose. A
DSM architecture for a parallel computer Cenju-4. In Proc.
6th Int’l Symp. High-Performance Computer Architecture(HPCA’00), pages 287–300, Jan. 2000.
[10] N. Koike. NEC Cenju-3: A microprocessor-based parallel
computer. In Proc. 8th Int’l Symp. Parallel Processing Conf.
(IPPS’94), pages 396–401, Apr. 1994.
[11] Message Passing Interface Forum. MPI: A message-passing
interface standard. Int’l J. Supercomputer Applications andHigh Performance Computing, 8(3/4):159–416, 1994.
[12] B. P. Miller, M. D. Callaghan, J. M. Cargille, J. K.
Hollingsworth, R. B. Irvin, K. L. Karavanic, K. Kunchithapadam, and T. Newhall. The Paradyn parallel performancemeasurement tool. IEEE Computer, 28(11):37–46, Nov.
1995.
[13] W. E. Nagel, A. Arnold, M. Weber, H.-C. Hoppe, andK. Solchenbach. VAMPIR: Visualization and analysis of
MPI resources. J. Supercomputing, 12(1):69–80, Jan. 1996.
[14] Parallel Software Contest (PSC’95), 1995. http://phase.hpcc.jp/phase/sacsis/PSC95/.
[15] Parallel Software Contest (PSC’96), 1996. http://phase.hpcc.jp/phase/sacsis/PSC96/.
[16] W. Pugh and E. Rosser. Iteration space slicing and its application to communication optimization. In Proc. 11th ACM
Int’l Conf. Supercomputing (ICS’97), pages 221–228, July
1997.
[17] M. J. Quinn and P. J. Hatcher.
On the utility ofcommunication–computation overlap in data-parallel programs. J. Parallel and Distributed Computing, 33(2):197–
204, Mar. 1996.
[18] S. Shende and A. D. Malony. Integration and applicationof TAU in parallel Java environments. Concurrency andComputation: Practice and Experience, 15(3/5):29–39, Mar.
2003.
[19] E. Su, A. Lain, S. Ramaswamy, D. J. Palermo, E. W. Hodges
IV, and P. Banerjee. Advanced compilation techniques in the
PARADIGM compiler for distributed-memory multicomputers. In Proc. 9th ACM Int’l Conf. Supercomputing (ICS’95),
pages 424–433, July 1995.
[20] O. Tatebe. LU decomposition on distributed memory machines. In IPSJ SIG Notes, 95-HPC-57, pages 55–60, Aug.
1995. http://phase.hpcc.jp/people/tatebe/
software/ (In Japanese).
[21] N. Watanabe and T. Yuasa. A code motion techniquefor communication optimization of data-parallel languages.
Trans. IPSJ, 40(3):1257–1266, Mar. 1999. (In Japanese).
[22] J. Yan, S. Sarukkai, and P. Mehra. Performance measurement, visualization and modeling of parallel and distributed
programs using the AIMS toolkit. Software: Practice andExperience, 25(4):429–461, Apr. 1995.
[23] O. Zaki, E. Lusk, W. Gropp, and D. Swider. Toward scalable performance visualization with Jumpshot. Int’l J. High
Performance Computing Applications, 13(2):277–288, June
1999.

9 Workshops (ICPPW’04)
Proceedings of the 2004 International Conference on Parallel Processing
1530-2016/04 $20.00 © 2004 IEEE