Interactive Parallel Programming using the ParaScope Editor.
The ParaScope Editor, an intelligent interactive editor for parallel Fortran programs, which is the centerpiece of the ParaScope project, an integrated collection of tools to help scientific programmers implement correct and efficient parallel programs, is discussed. ParaScope Editor reveals to users potential hazards of a proposed parallelization in a program. It provides a variety of powerful interactive program transformations that have been shown useful in converting programs to parallel form. ParaScope Editor supports general user editing through a hybrid text and structure editing facility that incrementally analyzes the modified program for potential hazards. It is shown that ParaScope Editor supports an exploratory programming style in which users get immediate feedback on their various strategies for parallelization.
Introduction
The widespread availability of affordable parallel machines has increasingly challenged the
abilities of programmers and compiler writers alike. Programmers, eager to use new machines
to speed up existing sequential scientific codes, want maximal performance with minimal ef-
fort. The success of automatic vectorization has led users to seek a similarly elegant software
solution to the problem of programming parallel computers. A substantial amount of research
has been conducted on whether sequential Fortran 77 programs can be automatically converted
without user assistance to execute on shared-memory parallel machines [2, 3, 7, 8, 42,
49]. The results of this research have been both promising and disappointing. Although such
systems can successfully parallelize many interesting programs, they have not established a
level of success that will make it possible to avoid explicit parallel programming by the user.
Hence, research has turned increasingly to the problem of supporting parallel programming.
Systems for automatic detection of parallelism are based on the analysis of dependences
in a program, where two statements depend on each other if the execution of one affects the
other. The process of calculating dependences for a program is known as dependence analysis.
A dependence crossing between regions that are executed in parallel may correspond to a
data race, indicating the existence of potential nondeterminism in the program. In general,
an automatic parallelization system cannot be allowed to make any transformation which
introduces a data race or changes the original semantics of the program.
The systems for automatic detection of parallelism in Fortran suffer from one principal
drawback: the inaccuracy of their dependence analysis. The presence of complex control flow,
symbolic expressions, or procedure calls are all factors which limit the dependence analyzer's
ability to prove or disprove the existence of dependences. If it cannot be proven that a
dependence does not exist, automatic tools must be conservative and assume a dependence,
lest they enable transformations that will change the meaning of the program. In these
situations, the user is often able to solve the problem immediately when presented with the
specific dependence in question. Unfortunately, in a completely automatic tool the user is
never given this opportunity 1 .
parallelization systems (for example, see [45]) provide a directive that instructs the compiler
to ignore all dependences. The use of broad directives like this is unsound because of the danger that the user
will discard real dependences with the false ones, leading to errors that are hard to detect.
To address this problem, we developed Ptool, an interactive browser which displays the
dependences present in a program [6]. Within Ptool, the user selects a specific loop and is
presented with what the analyzer believes are the dependences preventing the parallelization
of that loop. The user may then confirm or delete these dependences based on their knowledge
of the underlying algorithms of the program. Although Ptool is effective at helping users
understand the parallelism available in a given Fortran program, it suffers because it is a
browser rather than an editor [33]. When presented with dependences, the user frequently
sees a transformation that can eliminate a collection of dependences, only to be frustrated
because performing that transformation requires moving to an editor, making the change,
and resubmitting the program for dependence analysis. Furthermore, Ptool cannot help
the user perform a transformation correctly.
The ParaScope Editor, Ped, overcomes these disadvantages by permitting the programmer
and tool each to do what they do best: the tool builds dependences, provides expert
advice, and performs complex transformations, while the programmer determines which dependences
are valid and selects transformations to be applied. When transformations are
performed, Ped updates both the source and the dependence information quickly and cor-
rectly. This format avoids the possibility of the user accidentally introducing errors into the
program. As its name implies, the ParaScope Editor is based upon a source editor, so it also
supports arbitrary user edits. The current version reconstructs dependences incrementally
after any of the structured transformations it provides and for simple edits, such as the deletion
or addition of an assignment statement. For arbitrary unstructured edits with a broader
scope, batch analysis is used to reanalyze the entire program.
The current prototype of Ped is a powerful tool for exploring parallel programs: it
presents the program's data and control relationships to the user and indicates the effectiveness
of program transformations in eliminating impediments to parallelism. It also permits
arbitrary program changes through familiar editing operations. Ped supports several styles
of parallel programming. It can be used to develop new parallel codes, convert sequential
codes into parallel form, or analyze existing parallel programs. In particular, Ped currently
accepts and generates Fortran 77, IBM parallel Fortran [36], and parallel Fortran for the
Sequent Symmetry [46]. The Parallel Computing Forum is developing PCF Fortran [44].
PCF Fortran defines a set of parallel extensions that a large number of manufacturers are
committed to accepting, obviating the current need to support numerous Fortran dialects.
These extensions will be supported when they emerge.
The remainder of this paper is organized as follows. Section 2 discusses the evolution of
the ParaScope Parallel Programming Environment and in particular the ParaScope Editor.
Section 3 outlines the program analysis capabilities of Ped, and Section 4 describes the
manner in which dependence information is displayed and may be modified. A survey of the
program transformations provided by Ped appears in Section 5. Issues involving interactive
programming in Ped are discussed in Section 6. Section 7 summarizes related research, and
Section 8 offers some conclusions.
Background
Ped is being developed in the context of the ParaScope project [17], a parallel programming
environment based on the confluence of three major research efforts at Rice University: IR n ,
the Rice Programming Environment [23]; PFC , a Parallel Fortran Converter [8]; and Ptool,
a parallel programming assistant [6]. All of these are major contributors to the ideas behind
the ParaScope Editor, so we begin with a short description of each. Figure 1 illustrates the
evolution of ParaScope.
2.1 The IR n Programming Environment
Ped enjoys many advantages because it is integrated into the IR n Programming Environment.
Begun in 1982, the IR n Programming Environment project pioneered the use of interprocedural
analysis and optimization in a program compilation system. To accomplish this, it has
built a collection of tools that collaborate to gather information needed to support interprocedural
analysis while preparing a program for execution. Included in this collection is a source
editor for Fortran that combines the features of text and structure editing, representing programs
internally as abstract syntax trees. Also available are a whole program manager, a
debugger for sequential and parallel programs, interprocedural analysis and optimizations,
and an excellent optimizing scalar compiler.
IR n is written in C and runs under X Windows. It is a mature environment that has
been distributed in both source and executable form to many external sites. One of the
Ptool (1985)
dependence analysis
interprocedural analysis
program transformations
user interface
dependence filters
Ped
ParaScope (1987)
text/structure editor
interprocedural analysis
and optimization

Figure

1 Evolution of ParaScope
goals of IR n has been a consistent user interface that is easy to learn and use. As with any
large system consisting of many independent and related portions, another goal has been to
create a modular, easily modified implementation. The resulting environment is well suited
for integrating and extending our research in parallel programming. ParaScope includes and
builds on all of the functionality of the IR n project.
2.2 PFC
The PFC project was begun in 1979 with the goal of producing an automatic source to
source vectorizer for Fortran. It is written in PL/1 and runs on an IBM mainframe. In recent
years the project has focused on the more difficult problem of automatically parallelizing
sequential code. PFC performs data dependence analysis [9, 13, 14, 56], interprocedural
side effect analysis [25] and interprocedural constant propagation [18]. More recently an
implementation of regular section analysis [20, 32], which determines the subarrays affected
by procedure calls, has been completed. This analysis significantly improves the precision of
PFC's dependence graph, because arrays are no longer treated as single units across procedure
calls. PFC also performs control dependence analysis [28], which describes when the execution
of one statement directly determines if another will execute.
The analyses performed in PFC result in a statement dependence graph that specifies a
partial ordering on the statements in the program. This ordering must be maintained to
preserve the semantics of the program after parallelization. The dependence graph is conservative
in that it may include dependences that do not exist, but cannot be eliminated
because of imprecise dependence analysis. In being conservative, PFC guarantees that only
safe transformations are applied, but many opportunities for parallelism may be overlooked.
A special version of PFC has been modified to export the results of control and data depen-
dence, dataflow, symbolic, and interprocedural analysis in the form of an ascii file for use by
Ptool and Ped.
PFC concentrates on discovering and enhancing loop level parallelism in the original
sequential program. Although loops do not contain all the possible parallelism in a program,
there are several reasons for focusing on them. In scientific and numerical applications, most
computation occurs in loops. Also, separate iterations of a loop usually offer portions of
computation that require similar execution times, and often provide enough computation to
keep numerous processors occupied.
PFC has had many successes. It was influential in the design of several commercial vectorization
systems [47], and it has successfully found near-optimal parallelism for a selected set
of test cases [19]. However, it has not been successful enough to obviate the need for explicit
parallel programming. In large complex loops, it tends to find many spurious race conditions,
any one of which is sufficient to inhibit parallelization. Therefore, we have also turned our
attention to the use of dependence information to support the parallel programming process.
2.3 PTOOL
Ptool is a program browser that was developed to overcome some of the limitations of
automatic parallelizing systems by displaying dependences in Fortran programs. It is in use
as a debugging and analysis tool at various sites around the country, such as the Cornell
National Supercomputing Facility. Ptool was developed at the request of researchers at Los
Alamos National Laboratory who wanted to debug programs parallelized by hand. It uses
a dependence graph generated by PFC to examine the dependences that prevent loops from
being run in parallel. To assist users in determining if loops may be run in parallel, Ptool
also classifies variables as shared or private.
When examining large scientific programs, users frequently found an overwhelming number
of dependences in large loops, including spurious dependences due to imprecise dependence
analysis [33]. To ameliorate this problem, a number of improvements were made in
PFC's dependence analysis. In addition, a dependence filtering mechanism was incorporated
in the Ptool browser which could answers complex queries about dependences based on
their characteristics. The user could then use this mechanism to focus on specific classes of
dependences. Ped incorporates and extends these abilities (see Section 4).
2.4 The ParaScope Editor
The ParaScope Editor is an interactive tool for the sophisticated user. Programmers at Rice,
Los Alamos, and elsewhere have indicated that they want to be involved in the process of
parallel programming. They feel the output of automatic tools is confusing, because it does
not easily map to their original code. Often sequential analysis may be invalidated by the
parallel version or, even worse, be unavailable. This complicates the users' ability to improve
the modified source. They want their program to be recognizable; they want to be in control
of its parallelization; and they want to be able to tailor codes for general usage as well as for
specific inputs. Ped is intended for users of this type.
Ped is an interactive editor which provides users with all of the information available
to automatic tools. In addition, Ped understands the dependence graph and parallel con-
structs, and can provide users with both expert advice and mechanical assistance in making
changes and corrections to their programs. Ped will also update both the source and dependence
graph incrementally after changes. In Ped, a group of specific transformations provide
the format for modifying programs in a structured manner. When changes takes this structured
form, updates are incremental and immediate. Ped also supports general arbitrary
edits. When program changes are unstructured, source updates are done immediately and
dependence analysis of the program is performed upon demand.
3 Program Analysis
3.1 Control and Data Dependences
In sequential languages such as Fortran, the execution order of statements is well defined,
making for an excellent program definition on which to build the dependence graph. The
statement dependence graph describes a partial order between the statements that must
be maintained in order to preserve the semantics of the original sequential program. A
dependence between statement S 1
, denoted S 1
, indicates that S 2
depends on S 1
and that the execution of S 1
must precede S 2
There are two types of dependence, control and data. A control dependence, S 1
indicates that the execution of S 1
directly determines if S 2
will be executed at all. The
following formal definitions of control dependence and the post-dominance relation are taken
from the literature [27, 28].
x is post-dominated by y in G f
if every path from x to stop contains y,
where stop is the exit node of G f
Given two statements x, y 2 G f
, y is control dependent on x if and only if:
1. 9 a non-null path p, from x to y, such that y post-dominates every node
between x and y on p, and
2. y does not post-dominate x.
A data dependence, S 1 indicates that S 1 and S 2 use or modify a common variable in
a way that requires their execution order to be preserved. There are three types of data
dependence [40]:
ffl True (flow) dependence occurs when S 1
stores a variable S 2
later uses.
ffl Anti dependence occurs when S 1
uses a variable that S 2
later stores.
ffl Output dependence occurs when S 1
stores a variable that S 2
later stores.
Dependences are also characterized by either being loop-carried or loop-independent [5, 9].
Consider the following:
ENDDO
The dependence, S 1
, is a loop-independent true dependence, and it exists regardless of
the loop constructs surrounding it. Loop-independent dependences, whether data or control,
are dependences that occur in a single iteration of the loop and in themselves do not inhibit
a loop from running in parallel. For example, if S 1 ffiS 2
were the only dependence in the loop,
this loop could be run in parallel, because statements executed on each iteration affect only
other statements in the same iteration, and not in any other iterations.
In comparison, S 1 ffiS 3
is a loop-carried true dependence. Loop-carried dependences are
dependences that cross different iterations of some loop, and they constrain the order in
which iterations of that loop may execute. For this loop-carried dependence, S 3
uses a value
that was created by S 1
on the previous iteration of the I loop. This prevents the loop from
being run in parallel without explicit synchronization. When there are nested loops, the level
of any carried dependence is the outermost loop on which it first arises [5, 9].
3.2 Dependence Analysis
A major strength of Ped is its ability to display dependence information and utilize it to
guide structured transformations. Precise analysis of both control and data dependences in
the program is thus very important. Ped's dependence analyzer consists of four major com-
ponents: the dependence driver, scalar dataflow analysis, symbolic analysis, and dependence
testing.
The dependence driver coordinates other components of the dependence analyzer by handling
queries, transformations, and edits. Scalar dataflow analysis constructs the control flow
graph and postdominator tree for both structured and unstructured programs. Dominance
frontiers are computed for each scalar variable and used to build the static single assignment
graph for each procedure [26]. A coarse dependence graph for arrays is constructed by
connecting fDefsg with fDefs [ Usesg for array variables in each loop nest in the program.
Symbolic analysis determines and compares the values of expressions in programs. When
possible, this component eliminates or characterizes symbolic expressions used to determine
loop bounds, loop steps, array subscript expressions, array dimensions, and control flow. Its
main goal is to improve the precision of dependence testing. The SSA graph provides a
framework for performing constant propagation [53], auxiliary induction variable detection,
expression folding, and other symbolic analysis techniques.
Detecting data dependences in a program is complicated by array references, since it is
difficult to determine whether two array references may ever access the same memory location.
A data dependence exists between these references only if the same location may be accessed
by both references. Dependence testing is the process of discovering and characterizing data
dependences between array references. It is a difficult problem which has been the subject
of extensive research [9, 13, 14, 56]. Conservative data dependence analysis requires that if
a dependence cannot be disproven, it must be assumed to exist. False dependences result
when conservative dependences do not actually exist. The most important objective of the
dependence analyzer is to minimize false dependences through precise analysis.
Ped applies a dependence testing algorithm that classifies array references according to
their complexity (number of loop index variables) and separability (no shared index variables).
Fast yet exact tests are applied to simple separable subscripts. More powerful but expensive
tests are held in reserve for the remaining subscripts. In most cases, results can be merged
for an exact test [30].
Ped also characterizes all dependences by the flow of values with respect to the enclosing
loops. This information is represented as a hybrid distance/direction vector, with one element
per enclosing loop. Each element in the vector represents the distance or direction of the
flow of values on that loop. The hybrid vector is used to calculate the level of all loop-carried
dependences generated by an array reference pair. The dependence information is
used to refine the coarse dependence graph (constructed during scalar dataflow analysis) into
a precise statement dependence graph.
The statement dependence graph contains control and data dependences for the program.
Since Ped focuses on loop-level parallelism, the dependence graph is designed so that dependences
on a particular loop may be collected quickly and efficiently. The dependences may
then be displayed to the user, or analyzed to provide expert advice with respect to some
transformation. The details of the dependence analysis techniques in Ped are described
elsewhere [38].
3.3 Interprocedural Analysis
The presence of procedure calls complicates the process of detecting data dependences. Interprocedural
analysis is required so that worst case assumptions need not be made when
calls are encountered. Interprocedural analysis provided in ParaScope discovers aliasing, side
effects such as variable definitions and uses, and interprocedural constants [18, 25]. Unfor-
tunately, improvements to dependence analysis are limited because arrays are treated as
monolithic objects, and it is not possible to determine whether two references to an array
actually access the same memory location.
To improve the precision of interprocedural analysis, array access patterns can be summarized
in terms of regular sections or data access descriptors. These abstractions describe
subsections of arrays such as rows, columns, and rectangles that can be quickly intersected
to determine whether dependences exist [12, 20, 32]. By distinguishing the portion of each
array affected by a procedure, regular sections provide precise analysis of dependences for
loops containing procedure calls.
3.4 Synchronization Analysis
A dependence is preserved if synchronization guarantees that the endpoints of the dependence
are always executed in the correct order. Sophisticated users may wish to employ event
synchronization to enforce an execution order when there are loop-carried dependences in a
parallel loop. In these cases, it is important to determine if the synchronization preserves all
of the dependences in the loop. Otherwise, there may exist race conditions.
Establishing that the order specified by certain dependences will always be maintained
has been proven Co-NP-hard. However, efficient techniques have been developed to identify
dependences preserved in parallel loops by post and wait event synchronization [21, 22, 52].
Ped utilizes these techniques in a transformation that determines whether a particular dependence
is preserved by event synchronization in a loop. Other forms of synchronization
are not currently handled in Ped. We intend to expand our implementation and include a
related technique that automatically inserts synchronization to preserve dependences.
Implementation Status
Though the implementation of dependence analysis in Ped has made much progress, several
parts are still under construction. Underlying structures such as the control flow graph,
postdominator tree, and SSA graphs have been built, but are not yet fully utilized by the
dependence analyzer. Ped propagates constants, but does not currently perform other forms
of symbolic analysis. Most dependence tests have been implemented, but work remains for
the Banerjee-Wolfe and symbolic tests. Interprocedural analysis of aliases, side effects, and
constants is performed by the ParaScope environment, but is not integrated with Ped's
dependence analysis. This integration is underway as part of a larger implementation encompassing
both interprocedural symbolic and regular section analysis.
To overcome these gaps in the current implementation of dependence analysis, Ped can
import on demand dependence information from PFC . When invoked with a special option,
PFC utilizes its more mature dependence analyzer to produce a file of dependence information.
Ped then converts the dependence file into its own internal representation. This process is a
temporary expedient which will be unnecessary when dependence analysis in Ped is complete.
4 The Dependence Display
This section describes how Ped's interface allows users to view and modify the results of
program analysis. The persistent view provided by Ped appears in Figure 2. The Ped
window is divided into two panes, the text pane and the dependence pane. The text pane is
on top and consists of two parts; a row of buttons under the title bar, and a large area where
Fortran source code is displayed. 2 The buttons in the text pane provide access to functions
such as editing, saving, searching, syntax checking, and program transformations.
Directly below the text pane is the dependence pane in which dependences are displayed.
It also has two parts: buttons for perusing loops and dependences, and a larger pane for
detailed dependence descriptions. The dependence pane shows the results of program analysis
to users. Since Ped focuses on loop level parallelism, the user first selects a loop for
consideration. Regardless of whether the loop is parallel or sequential, the analysis assumes
sequential semantics and the dependences for that loop are displayed.
The current loop can be set by using the next loop and previous loop buttons in the
dependence pane, or by using the mouse to select the loop header in the text pane. The
loop's header and footer are then displayed in italics for the user. Ped will display all
the dependences for the current loop, or one or more of the loop-carried, loop-independent,
control, or private variable 3 dependences. The type of dependences to be displayed can be
selected using the view button. The default view displays just the loop-carried dependences,
2 The code displayed is a portion of the subroutine newque from the code simple, a two dimensional Lagrangian
hydrodynamics program with heat diffusion, produced by Lawrence Livermore National Laboratory.
3 Private variables are discussed in Section 4.2.

Figure

Ped Dependence Display and Filter
because only they represent race conditions that may lead to errors in a parallel loop.
Although many dependences may be displayed, only one dependence is considered to be
the current dependence. The current dependence can be set in the dependence pane by using
the next dependence and previous dependence buttons, or by direct selection with the mouse.
For the convenience of the user the current dependence is indicated in both panes. In the
dependence pane, the current dependence is underlined; in the text pane, the source reference
is underlined and the sink reference is emboldened.
For each dependence the following information is displayed in the dependence pane: the
dependence type (control, true, anti, or output), the source and sink variable names involved
in the dependence (if any), a hybrid dependence vector containing direction and/or distance
information (an exclamation point indicates that this information is exact), the loop level on
which the dependence first occurs, and the common block containing the array references.
As we will show in the next section, dependences that are of interest can be further classified
and organized to assist users in concentrating on some important group of dependences.
4.1 The Dependence Filter Facility
Ped has a facility for further filtering classes of dependences out of the display or restricting
the display to certain classes. This feature is needed because there are often too many dependences
for the user to effectively comprehend. For example, the filtering mechanism permits
the user to hide any dependences that have already been examined, or to show only the class
of dependences that the user wishes to deal with at the moment. When an edge is hidden, it
is still in the dependence graph, and all of the transformation algorithms still consider it; it
is simply not visible in the dependence display. Users can also delete dependences that they
feel are false dependences inserted as the result of imprecise dependence analysis. When an
edge is deleted, it is removed from the dependence graph and is no longer considered by the
transformation algorithms.
The dependence filter facility is shown in Figure 2. A class of dependences is specified
by a query. Queries can be used to select sets of dependences according to specific criteria.
query criteria are the names of variables involved in dependences, the names of common
blocks containing variables of interest, source and sink variable references, dependence type,
and the number of array dimensions. All of the queries, except for the source and sink variable
references, require the user to type a string into the appropriate query field. The variable
reference criteria are set when the user selects the variable reference of interest in the text
pane, and then selects the sink reference or source reference buttons, or both.
Once one or more of the query criteria have been specified, the user can choose to show or
hide the matching dependences. With the show option all of the dependences in the current
dependence list whose attributes match the query become the new dependence list. In Figure
2, we have selected show with the single query criterion: the variable name, drk. With the
hide option all of the dependences in the current list whose characteristics match the query
are hidden from the current list, and the remaining dependences become the new list. All of
the criteria can be set to empty by using the clear button.
The user can also push sets of dependences onto a stack. A push makes the set of dependences
matching the current query become the current database for all subsequent queries. A
pop returns to the dependence database that was active at the time of the last push. Multiple
pushes and corresponding pops are supported. A show all presents all the dependences that
are part of the current database.
The dependence list can be sorted by source reference, sink reference, dependence type,
or common block. Any group of dependences can be selected and deleted from the database
by using the delete button. Delete is destructive, and a removed dependence will no longer
be considered in the transformation algorithms nor appear in the dependence display. In
Section 6, we discuss the implications of dependence deletion.
4.2 Variable Classification
One of the most important parts of determining whether a loop can be run in parallel is
the identification of variables that can be made private to the loop body. This is important
because private variables do not inhibit parallelism. Hence, the more variables that can
legally be made private, the more likely it is that the loop may be safely parallelized.
The variable classification dialog, illustrated in Figure 3, is used to show the classification
of variables referenced in the loop as shared or private. Initially, this classification is based
upon dataflow analysis of the program. Any variable that is:
ffl defined before the loop and used inside the loop,
ffl defined inside the loop and used after the loop, or

Figure

Ped Variable Classification
ffl defined on one iteration of the loop and used on another
is assumed to be shared. In each of these cases, the variable must be accessible to more than
one iteration. All other variables are assumed to be private. To be accessible by all iterations,
shared variables must be allocated to global storage. Private variables must be allocated for
every iteration of a parallel loop, and may be put in a processor's local storage. Notice in

Figure

3, the first loop is parallel. The induction variable, i, is declared as private, because
each iteration needs to have its own copy.
Consider the second loop in Figure 3, but assume n is not live after the loop. Then the
values of n are only needed for a single iteration of the loop. They are not needed by any
other iteration, or after the execution of the loop. Each iteration of the loop must have its
own copy of n, if the results of executing the loop in parallel are to be the same as sequential
execution. Otherwise, if n were shared, the problem would be that one iteration might use
a value of n that was stored by some other iteration. This problem inhibits parallelism, if n
cannot be determined to be private.
In

Figure

3, the variable classification dialog displays the shared variables in the left
list, and the private variables in the right list for the current loop. If the current loop were
transformed into a parallel loop, variables in the shared list would be implicitly specified to be
in global storage, and the variables in the private list would be explicitly included in a private
statement. The user can select variables from either list with the mouse. Once a variable is
selected the reason for its classification will be displayed. Notice in Figure 3, the variable a
is underlined, indicating that it is selected, and the reason it must be in shared-memory is
displayed at the bottom of the pane.
Users need not accept the classification provided by Ped. They can transfer variables from
one list to the other by selecting a variable and then selecting the arrow button that points
to the other list. When users transfer variables from one list to another, they are making an
assertion that overrides the results of dependence analysis, and there is no guarantee that
the semantics of the sequential loop will be the same as its parallel counterpart.
Usually programmers will try to move variables from shared to private storage to increase
parallelism and to reduce memory contention and latency. To assist users in this task, the
classify vars button supports further classification of the variable lists. This mechanism helps
users to identify shared variables that may be moved to private storage by using transforma-
tions, or by correcting conservative dependences.
5 Structured Program Transformations
Ped provides a variety of interactive structured transformations that can be applied to programs
to enhance or expose parallelism. In Ped transformations are applied according to a
power steering paradigm: the user specifies the transformation to be made, and the system
provides advice and carries out the mechanical details. A single transformation may result in
many changes to the source, which if done one at a time may leave the intermediate program
either semantically incorrect, syntactically incorrect, or both. Power steering avoids incorrect
intermediate stages that may result if the user were required to do code restructuring without
assistance. Also, because the side effects of a transformation on the dependence graph are
known, the graph can be updated directly, avoiding any unnecessary dependence analysis.
In order to provide its users with flexibility, Ped differentiates between safe, unsafe, and
inapplicable transformations. An inapplicable transformation cannot be performed because
it is not mechanically possible. For example, loop interchange is inapplicable when there is
only a single loop. Transformations are safe when they preserve the sequential semantics of
the program. Some transformations always preserve the dependence pattern of the program
and therefore can always be safely applied if mechanically possible. Others are only safe when
the dependence pattern of the program is of a specific form.
An unsafe transformation does not maintain the original program's semantics, but is
mechanically possible. When a transformation is unsafe, users are often given the option to
override the system advice and apply it anyway. For example, if a user selects the parallel
button on a sequential loop with loop-carried dependences, Ped reminds the user of the
dependences. If the user wishes to ignore them, the loop can still be made parallel. This
override ability is extremely important in an interactive tool, where the user is being given
an opportunity to apply additional knowledge that is unavailable to the tool.
To perform a transformation, the user selects a sequential loop and chooses a transformation
from the menu. Only transformations that are enabled may be selected. Transformations
are enabled based on the control flow contained in the selected loop. All the transformations
are enabled when a loop and any loops nested within it contain no other control flow; most
of the transformations are enabled when they contain structured control flow; and only a few
are enabled when there is arbitrary control flow.
Once a transformation is selected, Ped responds with a diagnostic. If the transformation
is safe, a profitability estimate is given on the effectiveness of the transformation. Additional
advice, such as a suggested number of iterations to skew, may be offered as well. If the
transformation is unsafe, a warning explains what makes the transformation unsafe. If the
transformation is inapplicable, a diagnostic describes why the transformation cannot be per-
formed. If the transformation is applicable, and the user decides to execute it, the user selects
the do !transformation name? button. The Fortran source and the dependence graph are
then automatically updated to reflect the transformed code.
The transformations are divided into four categories: reordering transformations, dependence
breaking transformations, memory optimizing transformations, and a few miscellaneous
transformations. Each category and the transformations that Ped currently supports
are briefly described below. 4
5.1 Reordering Transformations
Reordering transformations change the order in which statements are executed, either within
or across loop iterations, without violating any dependence relationships. These transformations
are used to expose or enhance loop level parallelism in the program. They are often
performed in concert with other transformations to structure computations in a way that
allows useful parallelism to be introduced.
ffl Loop distribution partitions independent statements inside a loop into multiple loops
with identical headers. It is used to separate statements which may be parallelized from
those that must be executed sequentially [37, 38, 40]. The partitioning of the statements
is tuned for vector or parallel hardware as specified by the user.
ffl Loop interchange interchanges the headers of two perfectly nested loops, changing
the order in which the iteration space is traversed. When loop interchange is safe, it
can be used to adjust the granularity of parallel loops [9, 38, 56].
4 The details of Ped's implementation of several of these transformations appear in [38].
ffl Loop skewing adjusts the iteration space of two perfectly nested loops by shifting the
work per iteration in order to expose parallelism. When possible, Ped computes and
suggests the optimal skew degree. Loop skewing may be used with loop interchange in
Ped to perform the wavefront method [38, 54].
ffl Loop reversal reverses the order of execution of loop iterations.
ffl Loop adjusting adjusts the upper and lower bounds of a loop by a constant. It is
used in preparation for loop fusion.
ffl Loop fusion can increase the granularity of parallel regions by fusing two contiguous
loops when dependences are not violated [4, 43].
ffl Statement interchange interchanges two adjacent independent statements.
5.2 Dependence Breaking Transformations
The following transformations can be used to break specific dependences that inhibit par-
allelism. Often if a particular dependence can be eliminated, the safe application of other
transformations is enabled. Of course, if all the dependences carried on a loop are eliminated,
the loop may then be run in parallel.
ffl Scalar expansion makes a scalar variable into a one-dimensional array. It breaks
output and anti dependences which may be inhibiting parallelism [41].
ffl Array renaming, also known as node splitting [41], is used to break anti dependences
by copying the source of an anti dependence into a newly introduced temporary array
and renaming the sink to the new array [9]. Loop distribution may then be used
to separate the copying statement into a separate loop, allowing both loops to be
parallelized.
ffl Loop peeling peels off the first or last k iterations of a loop as specified by the user.
It is useful for breaking dependences which arise on the first or last k iterations of the
loop [4].
ffl Loop splitting, or index set splitting, separates the iteration space of one loop into
two loops, where the user specifies at which iteration to split. For example, if do
1, 100 is split at 50, the following two loops result: do
100. Loop splitting is useful in breaking crossing dependences, dependences that cross
a specific iteration [9].
5.3 Memory Optimizing Transformations
The following transformations adjust a program's balance between computations and memory
accesses to make better use of the memory hierarchy and functional pipelines. These
transformations are useful for scalar and parallel machines.
ffl Strip mining takes a loop with step size of 1, and changes the step size to a new user
specified step size greater than 1. A new inner loop is inserted which iterates over the
new step size. If the minimum distance of the dependences in the loop is less than
the step size, the resultant inner loop may be parallelized. Used alone the order of the
iterations is unchanged, but used in concert with loop interchange the iteration space
may be tiled [55] to utilize memory bandwidth and cache more effectively [24].
ffl Scalar replacement takes array references with consistent dependences and replaces
them with scalar temporaries that may be allocated into registers [15]. It improves the
performance of the program by reducing the number of memory accesses required.
Unrolling decreases loop overhead and increases potential candidates for scalar replacement
by unrolling the body of a loop [4, 38].
ffl Unroll and Jam increases the potential candidates for scalar replacement and pipelining
by unrolling the body of an outer loop in a loop nest and fusing the resulting inner
loops [15, 16, 38].
5.4 Miscellaneous Transformations
Finally Ped has a few miscellaneous transformations.
Parallel converts a sequential DO loop into a parallel loop, and vice
versa.
ffl Statement addition adds an assignment statement.
ffl Statement deletion deletes an assignment statement.
ffl Preserved dependence? indicates whether the current selected dependence is preserved
by any post and wait event synchronization in the loop.
ffl Constant replacement performs global constant propagation for each procedure in
the program, using the sparse conditional constant algorithm [53]. Any variable found to
have a constant value is replaced with that value, increasing the precision of subsequent
dependence analysis.
5.5 Example
The following example is intended to give the reader the flavor of this type of transformational
system. Consider the first group of nested loops in Figure 4. Let S 1
be the first assignment
statement involving the array D, and S 2
be the second assignment statement involving the
array E. There are two loop-carried dependences, S 1 ffiS 1
. The first is a true
dependence on D carried by the I loop in the first subscript position, and the second is a true
dependence on E carried by the J loop in the second subscript position. We notice that both
loops are inhibited from running in parallel by different dependences which are not involved
with each other. To separate these independent statements, we consider distributing the
loops. Distribution on the inner loop results in the message shown in Figure 4. The message
indicates what the results of performing distribution on this loop would be. The execution
of distribution results in the following code.
ENDDO
ENDDO
ENDDO
Unfortunately, the dependence on S 1
carried by the I loop still inhibits the I loop parallelism
. We perform distribution once again, this time on the outer loop.

Figure

ENDDO
ENDDO
ENDDO
ENDDO
We have decided to distribute for parallelism in this example. So even though S 2
and S 3
are independent, the algorithm leaves them together to increase the amount of computation
in the parallel loop. If we had selected vectorization they would have been placed in separate
loops.
Continuing our example, notice the second I loop can now be run in parallel, and the inner
J loop in the first nest can be run in parallel. To achieve a higher granularity of parallelism
on the first loop nest, the user can interchange the loops, safely moving the parallelism to
the outer loop. As can be seen in the second loop nest of Figure 4, we have safely separated
the two independent statements and their dependences, achieving two parallel loops.
6 Relating User Changes to Analysis
In previous sections we discussed how users may direct the parallelization process by making
assertions about dependences and variables, as well as by applying structured transforma-
tions. This section first briefly describes editing in Ped. Then, the interaction between
program changes and analysis is examined.
Editing is fundamental for any program development tool because it is the most flexible
means of making program changes. Therefore, the ParaScope Editor integrates advanced
editing features along with its other capabilities. Ped supplies simple text entry and template-based
editing with its underlying hybrid text and structure editor. It also provides search
and replace functions, intelligent and customizable view filters, and automatic syntax and
type checking.
Unlike transformations or assertions, editing causes existing dependence information to be
unreliable. As a result, the transformations and the dependence display are disabled during
editing because they rely on dependence information which may be out of date. After users
finish editing, they can request the program be reanalyzed by selecting the analysis button.
Syntax and type checking are performed first, and any errors are reported. If there are no
errors, dependence analysis is performed. Ped's analysis may be incremental when the scope
of an edit is contained within a loop nest or is an insertion or deletion of a simple assignment
statement. The details of incremental analysis after edits and transformations are discussed
elsewhere [38].
The purpose of an edit may be error correction, new code development, or just to rearrange
existing code. Unlike with transformations, where the correctness of pre-existing source
is assumed, Ped does not know the intent of an edit. Consequently, the user is not advised
as to the correctness of the edit. Instead, the "new" program becomes the basis for dependence
analysis and any subsequent changes. No editing history is maintained. Similarly, any
transformations the user performs before an edit, whether safe or unsafe, are included in the
new basis. However, if prior to editing the user made any assertions, analysis causes them to
be lost.
For example, suppose the user knows the value of a symbolic. Based on this knowledge, the
user deletes several overly conservative dependences in a loop and transforms it into a parallel
loop. Later, the user discovers an error somewhere else in the program and corrects it with
a substantial edit. The user then reanalyzes the program. In the current implementation,
the parallel loop will remain parallel, but any deleted dependences will reappear and, as
experience has shown, annoy users.
As a result, a more sophisticated mechanism is planned [29]. In the future, edges that
are deleted by users will be marked, rather than removed from the dependence graph. Ad-
ditionally, the time, date, user, and an optional user-supplied explanation will be recorded
with any assertions. This mechanism will also support more general types of assertions, such
as variable ranges and values which may affect many dependence edges. These records will
be used during analysis to keep deleted dependences from reappearing. However, to prevent
errors when edits conflict with assertions, users will be given an opportunity to reconsider
any assertions which may have been affected by the edit. Users may delay or ignore this
opportunity. With this mechanism, the assertions will also be available during execution and
debugging. There, if an assertion is found to be erroneous, users can be presented with any
anomalies which may have been ignored, overlooked, or introduced.
7 Related Work
Several other research groups are also developing advanced interactive parallel programming
tools. Ped is distinguished by its large collection of transformations, the expert guidance
provided for each transformation, and the quality of its program analysis and user interface.
Below we briefly describe Sigmacs [48], Pat [50], MIMDizer [1], and Superb [57], placing
emphasis on their unique features.
Sigmacs is an interactive emacs-based programmable parallelizer in the Faust programming
environment. It utilizes dependence information fetched from a project database maintained
by the database server. Sigmacs displays dependences and provides some interactive
program transformations. Work is in progress to support automatic updating of dependence
information after statement insertion and deletion. Faust can compute and display call and
process graphs that may be animated dynamically at run-time [31]. Each node in a process
graph represents a task or a process, which is a separate entity running in parallel. Faust
also provides performance analysis and prediction tools for parallel programs.
Pat can analyze programs containing general parallel constructs. It builds and displays
a statement dependence graph over the entire program. In Pat the program text that corresponds
with a selected portion of the graph can be perused. The user may also view the
list of dependences for a given loop. However, Pat can only analyze programs where only
one write occurs to each variable in a loop. Like Ped, incremental dependence analysis is
used to update the dependence graph after structured transformations [51]. Rather than
analyzing the effects of existing synchronization, Pat can instead insert synchronization to
preserve specific dependences. Since Pat does not compute distance or direction vectors,
loop reordering transformations such as loop interchange and skewing are not supported.
MIMDizer is an interactive parallelization system for both shared and distributed-memory
machines. Based on Forge, MIMDizer performs dataflow and dependence analysis to support
interactive loop transformations. Cray microtasking directives may be output for successfully
parallelized loops. Associated tools graphically display control flow, dependence, profiling,
and call graph information. A history of the transformations performed on a program is
saved for the user. MIMDizer can also generate communication for programs to be executed
on distributed-memory machines.
Though designed to support parallelization for distributed-memory multiprocessors, Superb
provides dependence analysis and display capabilities similar to that of Ped. Superb
also possesses a set of interactive program transformations designed to exploit data parallelism
for distributed-memory machines. Algorithms are described for the incremental update
of use-def and def-use chains following structured program transformations [39].
Conclusions
Programming for explicitly parallel machines is much more difficult than sequential program-
ming. If we are to encourage scientists to use these machines, we will need to provide new
tools that have a level of sophistication commensurate with the difficulty of the task. We
believe that the ParaScope Editor is such a tool: it permits the user to develop programs
with the full knowledge of the data relationships in the program; it answers complex questions
about potential sources of error; and it correctly carries out complicated transformations to
enhance parallelism.
Ped is an improvement over completely automatic systems because it overcomes both the
imprecision of dependence analysis and the inflexibility of automatic parallel code generation
techniques by permitting the user to control the parallelization process. It is an improvement
over dependence browsers because it supports incremental change while the user is reviewing
potential problems with the proposed parallelization. Ped has also proven to be a useful
basis for the development of several other advanced tools, including a compiler [34] and data
decomposition tool [10, 11] for distributed-memory machines, as well an on-the-fly access
anomaly detection system for shared-memory machines [35].
We believe that Ped is representative of a new generation of intelligent, interactive programming
tools that are needed to facilitate the task of parallel programming.

Acknowledgments

We would like to thank Donald Baker, Vasanth Balasundaram, Paul Havlak, Marina Kalem,
Ulrich Kremer, Rhonda Reese, Jaspal Subhlok, Scott Warren, and the PFC research group for
their many contributions to this work. Their efforts have made Ped the useful research tool
it is today. In addition, we gratefully acknowledge the contribution of the IR n and ParaScope
research groups, who have provided the software infrastructure upon which Ped is built.



--R

The MIMDizer: A new parallelization tool.
An overview of the PTRAN analysis system for multiprocessing.
A framework for detecting useful parallelism.
A catalogue of optimizing transformations.
Dependence Analysis for Subscripted Variables and Its Application to Program Transformations.

Automatic decomposition of scientific programs for parallel execution.
PFC: A program to convert Fortran to parallel form.
Automatic translation of Fortran programs to vector form.
An interactive environment for data partitioning and distribution.
A static performance estimator to guide data partitioning decisions.
A technique for summarizing data access and its use in parallelism enhancing transformations.
Dependence Analysis for Supercomputing.
Interprocedural dependence analysis and parallelization.
Improving register allocation for subscripted variables.
Estimating interlock and improving balance for pipelined machines.
ParaScope: A parallel programming environment.
Interprocedural constant propa- gation
Vectorizing compilers: A test suite and results.
Analysis of interprocedural side effects in a parallel programming environment.
Analysis of event synchronization in a parallel programming tool.
Static analysis of low-level synchronization

Blocking linear algebra codes for memory hierarchies.
The impact of interprocedural analysis and optimization in the IR n programming environment.
An efficient method of computing static single assignment form.
Experiences using control dependence in PTRAN.
The program dependence graph and its use in optimization.

Practical dependence testing.
An integrated environment for parallel programming.
Experience with interprocedural analysis of array side effects.
On the use of diagnostic dependency-analysis tools in parallel programming: Experiences using PTOOL
Compiler support for machine-independent parallel programming in Fortran D
Parallel program debugging with on-the- fly anomaly detection



Advanced tools and techniques for automatic parallelization.
The Structure of Computers and Computations
Analysis and transformation of programs for parallel computation.
The structure of an advanced retargetable vectorizer.
Dependence graphs and compiler optimizations.
PCF Fortran: Language Definition
A Guidebook to Fortran on Supercomputers.
Guide to Parallel Programming on Sequent Computer Systems.
A vectorizing Fortran compiler.
SIGMACS: A programmable programming environment.
An empirical investigation of the effectiveness of and limitations of automatic parallelization.

Incremental dependence analysis for interactive parallelization.
Analysis of Synchronization in a Parallel Programming Environment.
Constant propagation with conditional branches.
Loop skewing: The wavefront method revisited.
More iteration space tiling.
Optimizing Supercompilers for Supercomputers.
SUPERB: A tool for semi-automatic MIMD/SIMD parallelization
--TR
The impact of interprocedural analysis and optimization in the R<sup>n</sup> programming environment
Interprocedural constant propagation
Interprocedural dependence analysis and parallelization
A vectorizing Fortran compiler
The program dependence graph and its use in optimization
Automatic translation of FORTRAN programs to vector form
Loop skewing: the wavefront method revisited
A practical environment for scientific programming
Automatic decomposition of scientific programs for parallel execution
Estimating interlock and improving balance for pipelined architectures
A framework for determining useful parallelism
Guide to parallel programming on Sequent computer systems: 2nd edition
Vectorizing compilers: a test suite and results
Static analysis of low-level synchronization
Analysis of interprocedural side effects in a parallel programming environment
An overview of the PTRAN analysis system for multiprocessing
A technique for summarizing data access and its use in parallelism enhancing transformations
An efficient method of computing static single assignment form
More iteration space tiling
On the use of diagnostic dependence-analysis tools in parallel programming
Experiences using control dependence in PTRAN
Improving register allocation for subscripted variables
Analysis of event synchronization in a parallel programming tool
Analysis and transformation in the ParaScope editor
A static performance estimator to guide data partitioning decisions
Parallel program debugging with on-the-fly anomaly detection
Loop distribution with arbitrary control flow
Experience with interprocedural analysis of array side effects
Practical dependence testing
Analysis of synchronization in a parallel programming environment
Incremental dependence analysis for interactive parallelization
Optimizing Supercompilers for Supercomputers
Dependence Analysis for Supercomputing
Dependence graphs and compiler optimizations
A Guidebook to FORTRAN on Supercomputers
Structure of Computers and Computations
Faust
Blocking Linear Algebra Codes for Memory Hierarchies
Constant Propagation with Conditional Branches
Dependence analysis for subscripted variables and its application to program transformations

--CTR
P. Havlak , K. Kennedy, An Implementation of Interprocedural Bounded Regular Section Analysis, IEEE Transactions on Parallel and Distributed Systems, v.2 n.3, p.350-360, July 1991
Eran Gabber , Amir Averbuch , Amiram Yehudai, Portable, Parallelizing Pascal Compiler, IEEE Software, v.10 n.2, p.71-81, March 1993
Yang Bo , Zheng Fengzhou , Wang Dingxing , Zheng Weimin, Interactive and symbolic data dependence analysis based on ranges of expressions, Journal of Computer Science and Technology, v.17 n.2, p.160-171, March 2002
Flanagan , Matthew Flatt , Shriram Krishnamurthi , Stephanie Weirich , Matthias Felleisen, Catching bugs in the web of program invariants, ACM SIGPLAN Notices, v.31 n.5, p.23-32, May 1996
Warren, The D editor: a new interactive parallel programming tool, Proceedings of the 1994 conference on Supercomputing, p.733-ff., December 1994, Washington, D.C., United States
Hiranandani , Ken Kennedy , Chau Wen Tseng , Scott Warren, The D editor: a new interactive parallel programming tool, Proceedings of the 1994 ACM/IEEE conference on Supercomputing, November 14-18, 1994, Washington, D.C.
Ishfaq Ahmad , Yu-Kwong Kwok , Min-You Wu , Wei Shu, CASCH: A Tool for Computer-Aided Scheduling, IEEE Concurrency, v.8 n.4, p.21-33, October 2000
Mary W. Hall , Ken Kennedy , Kathryn S. McKinley, Interprocedural transformations for parallel code generation, Proceedings of the 1991 ACM/IEEE conference on Supercomputing, p.424-434, November 18-22, 1991, Albuquerque, New Mexico, United States
Mary W. Hall , Timothy J. Harvey , Ken Kennedy , Nathaniel McIntosh , Kathryn S. McKinley , Jeffrey D. Oldham , Michael H. Paleczny , Gerald Roth, Experiences using the ParaScope Editor: an interactive parallel programming tool, ACM SIGPLAN Notices, v.28 n.7, p.33-43, July 1993
Gina Goff , Ken Kennedy , Chau-Wen Tseng, Practical dependence testing, ACM SIGPLAN Notices, v.26 n.6, p.15-29, June 1991
Ken Kennedy , Kathryn S. McKinley , Chau-Wen Tseng, Analysis and transformation in the ParaScope editor, Proceedings of the 5th international conference on Supercomputing, p.433-447, June 17-21, 1991, Cologne, West Germany
Thomas Fahringer , Bernhard Scholz, A Unified Symbolic Evaluation Framework for Parallelizing Compilers, IEEE Transactions on Parallel and Distributed Systems, v.11 n.11, p.1105-1125, November 2000
scientific programmers;efficient parallel programs;general user editing;hybrid text;modified program;integrated collection;parascopeproject;exploratory programming style;text editing;FORTRAN;powerful interactive program transformations;interactive programming;Index TermsParaScope Editor;structureediting facility;intelligent interactive editor;parallel programming;parallel Fortran programs