An Implementation of Interprocedural Bounded Regular Section Analysis.
Regular section analysis, which summarizes interprocedural side effects on subarrays in a form useful to dependence analysis, while avoiding the complexity of prior solutions, is shown to be a practical addition to a production compiler. Optimizing compilers should produce efficient code even in the presence of high-level language constructs. However, current programming support systems are significantly lacking in their ability to analyze procedure calls. This deficiency complicates parallel programming, because loops withcalls can be a significant source of parallelism. The performance of regular section analysis is compared to two benchmarks: the LINPACK library of linear algebra subroutines and the Rice Compiler Evaluation Program Suite (RiCEPS), a set of complete application codes from a variety of scientific disciplines. The experimental results demonstrate that regular section analysis is an effective means of discovering parallelism, given programs written in an appropriately modular programming style.
Introduction
A major goal of compiler optimization research is to generate code that is efficient enough to
encourage the use of high-level language constructs. In other words, good programming practice
This research has been supported by the National Science Foundation under grant CCR 88-09615, by the IBM
Corporation, and by Intel Scientific Computers
should be rewarded with fast execution time.
The use of subprograms is a prime example of good programming practice that requires compiler
support for efficiency. Unfortunately, calls to subprograms inhibit optimization in most programming
support systems, especially those designed to support parallel programming in Fortran. In
the absence of better information, compilers must assume that any two calls can read and write the
same memory locations, making parallel execution nondeterministic. This limitation particularly
discourages calls in loops, where most compilers look for parallelism.
Traditional interprocedural analysis can help in only a few cases. Consider the following loop:
100 CONTINUE
If SOURCE only modifies locations in the Ith column of A, then parallel execution of the loop is
deterministic. Classical interprocedural analysis only discovers which variables are used and which
are defined as side effects of procedure calls. We must determine the subarrays that are accessed
in order to safely exploit the parallelism.
In an earlier paper, Callahan and Kennedy proposed a method called regular section analysis
for tracking interprocedural side-effects. Regular sections describe side effects to common sub-structures
of arrays such as elements, rows, columns and diagonals [1, 2]. This paper describes
an implementation of regular section analysis in the Rice Parallel Fortran Converter (PFC) [3], an
automatic parallelization system that also computes dependences for the ParaScope programming
environment[4]. The overriding concern in the implementation is that it be efficient enough to be
incorporated in a practical compilation system.
Algorithm 1 summarizes the steps of the analysis, whiich is integrated with the three-phase
interprocedural analysis and optimization structure of PFC [5, 6]. Regular section analysis added
less than 8000 lines to PFC, a roughly 150,000-line PL/I program which runs under IBM VM/CMS.
The remainder of the paper is organized as follows. Section 2 compares various methods for
representing side effects to arrays. Section 3 gives additional detail on the exact variety of bounded
regular sections implemented. Sections 4 and 5 describe the construction of local sections and their
propagation, respectively. Section 6 examines the performance of regular section analysis on two
benchmarks: the Linpack library of linear algebra subroutines and the Rice Compiler Evaluation
Local Analysis:
for each procedure
for each array (formal parameter, global, or static)
save section describing shape
for each reference
build ranges for subscripts
merge resulting section with summary MOD or USE section
save summary sections
for each call site
for each array actual parameter
save section describing passed location(s)
for each scalar (actual parameter or global)
save range for passed value
Interprocedural Propagation:
solve other interprocedural problems
call graph construction
classical MOD and USE summary
constant propagation
mark section subscripts and scalars invalidated by modifications as ?
iterating over the call sites
translate summary sections into call context
merge translated sections into caller's summary
Dependence Analysis:
for each procedure
for each call site
for each summary section
simulate a DO loop running through the elements of the section
test for dependences (Banerjee's, GCD)
Algorithm 1: Overview of Regular Section Analysis
Program Suite (Riceps), a set of complete application codes from a variety of scientific disciplines.
Sections 7 and 8 suggest areas for future research and give our conclusions.
Array Side Effects
A simple way to make dependence testing more precise around a call site is to perform inline
expansion, replacing the called procedure with its body [7]. This precisely represents the effects
of the procedure as a sequence of ordinary statements, which are readily understood by existing
dependence analyzers. However, even if the whole program becomes no larger, the loop nest which
contained the call may grow dramatically, causing a time and space explosion due to the non-linearity
of array dependence analysis [8].
To gain some of the benefits of inline expansion without its drawbacks, we must find another
representation for the effects of the called procedure. For dependence analysis, we are interested in
the memory locations modified or used by a procedure. Given a call to procedure p at statement
and an array global variable or parameter A, we wish to compute:
ffl the set M A
of locations in A that may be modified via p called at S 1 and
ffl the set U A
of locations in A that may be used via p called at S 1 .
We need comparable sets for simple statements as well. We can then test for dependence by
intersecting sets. For example, there exists a true dependence from a statement S 1 to a following
statement based on an array A, only if
Several representations have been proposed for representing interprocedural array access sets.
The contrived example in Figure 1 shows the different patterns that they can represent precisely.
Evaluating these methods involves examining the complexity and precision of:
A
Classical Summary Triolet
Regular Sections
Bounds With Bounds & Strides
DAD/Simple Section

Figure

1: Summarizing the References A[1; 2], A[4; 8], and A[10; 6]
ffl representing the sets M A
and U A
merging descriptors to summarize multiple accesses (we call this the meet operation, because
most descriptors may be viewed as forming a lattice),
ffl testing two descriptors for intersection (dependence testing), and
translating descriptors at call sites (especially when there are array reshapes).
Handling of recursion turns out not to be an issue. Iterative techniques can guarantee convergence
to a fixed point solution using Cousot's technique of widening operators [9, 10]. Li and
Yew proposed a preparatory analysis of recursive programs that guarantees termination in three
iterations [11, 12]. Either of these methods may be adapted for regular sections.
2.1 True Summaries
True summary methods use descriptors whose size is largely independent of the number of references
being summarized. This may make the descriptors and their operations more complicated, but
limits the expense of translating descriptors during interprocedural propagation and intersecting
them during dependence analysis.
Classical Methods The classical methods of interprocedural summary dataflow analysis compute
mod and use sets indicating which parameters and global variables may be modified or used
in the procedure [13, 14, 15]. Such summary information costs only two bits per variable. Meet
and intersection may be implemented using single-bit or bit-vector logical operations. Also, there
exist algorithms that compute complete solutions, in which the number of meets is linear in the
number of procedures and call sites in the program, even when recursion is permitted [16].
Unfortunately, our experiences with PFC and Ptool indicate that this summary information is
too coarse for dependence testing and the effective detection of parallelism [1]. The problem is that
the only access sets representable in this method are "the whole array" and "none of the array"
(see

Figure

1). Such coarse information limits the detection of data decomposition, an important
source of parallelism, in which different iterations of a loop work on distinct subsections of a given
array.
Triolet Regions Triolet, Irigoin and Feautrier proposed to calculate linear inequalities bounding
the set of array locations affected by a procedure call [17, 18]. This representation and its intersection
operation are precise for convex regions. Other patterns, such as array accesses with non-unit
stride and non-convex results of meet operations, are given convex approximations.
Operations on these regions are expensive; the meet operation requires finding the convex hull
of the combined set of inequalities and intersection uses a potentially exponential linear inequality
solver [19]. A succession of meet operations can also produce complicated regions with potentially
as many inequalities as the number of primitive accesses merged together. Translation at calls sites
is precise only when the formal parameter array in the called procedure maps to a (sub)array of
the same shape in the caller. Otherwise, the whole actual parameter array is assumed accessed by
the call. The region method ranks high in precision, but is too expensive because of its complex
representation.
2.2 Reference Lists
Some proposed methods do not summarize, but represent each reference separately. Descriptors
are then lists of references, the meet operation is list concatenation (possibly with a check for
duplicates), and translation and intersection are just the repeated application of the corresponding
operations on simple references. However, this has two significant disadvantages:
ffl translation of a descriptor requires time proportional to the number of references, and
ffl intersection of descriptors requires time quadratic in the number of references.
Reference list methods are simple and precise, but are asymptotically as expensive as in-line
expansion.
Linearization Burke and Cytron proposed representing each multidimensional array reference
by linearizing its subscript expressions to a one-dimensional address expression. Their method also
retains bounds information for loop induction variables occurring in the expressions [20]. They
describe two ways of implementing the meet operation. One involves merely keeping a list of the
individual address expressions. The other constructs a composite expression that can be polynomial
in the loop induction variables. The disadvantages of the first method are described above. The
second method appears complicated and has yet to be rigorously described. Linearization in its pure
form is ill-suited to summarization, but might be a useful extension to a true summary technique
because of its ability to handle arbitrary reshapes.
Atom Images Li and Yew extended Parafrase to compute sets of atom images describing the side
effects of procedures [21, 11]. Like the original version of regular sections described in Callahan's
thesis [2], these record subscript expressions that are linear in loop induction variables along with
bounds on the induction variables. Any reference with linear subscript expressions in a triangular
iteration space can be precisely represented, and they keep a separate atom image for each reference.
The expense of translating and intersecting lists of atom images is too high a price to pay for
their precision. Converting atom images to a summary method would produce something similar
to the regular sections described below.
2.3

Summary

Sections
The precise methods described above are expensive because they allow arbitrarily large representations
of a procedure's access sets. The extra information may not be useful in practice; simple
array access patterns are probably more common than others. To avoid expensive intersection and
translation operations, descriptor size should be independent of the number of references summa-
rized. Operations on descriptors should be linear or, at worst, quadratic in the rank of the array.
Researchers at Rice have defined several variants of regular sections to represent common access
patterns while satisfying these constraints [2, 1, 22, 23].
Original Regular Sections Callahan's thesis proposed two regular section frameworks. The
first, resembling Li and Yew's atom images, he dismissed due to the difficulty of devising efficient
standardization and meet operations [2].
Restricted Regular Sections. The second framework, restricted regular sections [2, 1], is limited
to access patterns in which each subscript is
ffl a procedure-invariant expression (with constants and procedure inputs),
ffl unknown (and assumed to vary over the entire range of the dimension), or
ffl unknown but diagonal with one or more other subscripts.
The restricted sections have efficient descriptors: their size is linear in the number of subscripts,
their meet operation quadratic (because of the diagonals), and their intersection operation linear.
However, they lose too much precision by omitting bounds information. While we originally thought
that these limitations were necessary for efficient handling of recursive programs, Li and Yew have
adapted iterative techniques to work with more general descriptors [12].
Bounded Regular Sections Anticipating that restricted regular sections would not be precise
enough for effective parallelization, Callahan and Kennedy proposed an implementation of regular
sections with bounds. That project is the subject of this paper. The regular sections implemented
include bounds and stride information, but omit diagonal constraints. The resulting analysis is
therefore less precise in the representation of convex regions than Triolet regions or the Data Access
Descriptors described below. However, this is the first interprocedural summary implementation
with stride information, which provides increased precision for non-convex regions.
The size of bounded regular section descriptors and the time required for the meet operation are
both linear in the number of subscripts. Intersection is implemented using standard dependence
tests, which also take time proportional to the number of subscripts. 1
Data Access Descriptors Concurrently with our implementation, Balasundaram and Kennedy
developed Data Access Descriptors (DADs) as a general technique for describing data access [22,
23, 24]. DADs represent information about both the shapes of array accesses and their traversal
for our comparison we are interested only in the shapes. The simple section part of a DAD
represents a convex region similar to those of Triolet et al., except that boundaries are constrained
to be parallel to one coordinate axis or at a 45 ffi angle to two axes. Stride information is represented
in another part of the DAD.
Data Access Descriptors are probably the most precise summary method that can be implemented
with reasonable efficiency. They can represent the most likely rectangular, diagonal, trian-
gular, and trapezoidal accesses. In size and in time required for meet and intersection they have
This analysis ignores the greatest common divisor computation used in merging and intersecting sections with strides;
this can take time proportional to the values of the strides.
complexity quadratic in the number of subscripts (which is reasonable given that most arrays have
few subscripts).
The bounded sections implemented here are both less expensive and less precise than DADs.
Our implementation can be extended to compute DADs if the additional precision proves useful.
Bounded Sections and Ranges
Bounded regular sections comprise the same set of rectangular subarrays that can be written using
triplet notation in the proposed Fortran 90 standard [25]. They can represent sparse regions such
as stripes and grids and dense regions such as columns, rows, and blocks.
(n+1):2
Expressions
Ranges of Size 2
Ranges of Size 3
Finite Ranges
Unknown

Figure

2: Lattice for Regular Section Subscripts
3.1 Representation
The descriptors for bounded regular sections are vectors of elements from the subscript lattice in

Figure

2. Lattice elements include:
ffl invariant expressions, containing only constants and symbols representing the values of parameters
and global variables on entry to the procedure;
ffl ranges, giving invariant expressions for the lower bound, upper bound, and stride of a variant
subscript; and
ffl ?, indicating no knowledge of the subscript value.
While ranges may be constructed through a sequence of meet operations, the more common case
is that they are read directly from the bounds of a loop induction variable used in a subscript.
Since no constraints between subscripts are maintained, merging two regular sections for an
array of rank d requires only d independent invocations of the subscript meet operation. We test
for intersection of two sections with a single invocation of standard d-dimensional dependence tests.
Translation of a formal parameter section to one for an actual parameter is also an O(d) operation
(where d is the larger of the two ranks).
3.2 Operations on Ranges
Ranges are typically built to represent the values of loop induction variables, such as I in the
following loop.
ENDDO
We represent the value of I as [l : While l and u are often referred to as the lower and
upper bound, respectively, their roles are reversed if s is negative. We can produce a standard lower-
to-upper bound form if we know l - u or s - 1; this operation is described in detail in Algorithm 2.
Standardization may cause loss of information; therefore, we postpone standardization until it is
required by some operation, such as merging two sections.
begin
if diff and s are both constant then
if sign(diff) 6= sign(s) then return(?) /* empty range */
direction * (abs(diff) mod abs(s))
else if diff is constant then direction = sign(diff)
else if s is constant then direction = sign(s)
else return(?)
select direction
when ?
perfect then return([u
select
end.
Algorithm 2: Standardizing a Range to Lower-Bound-First Form
Expressions in ranges are converted to ranges; for example, 2*I+1 in the above loop is represented
as [(2   l Only invariant expressions are accurately added to or
multiplied with a range; Algorithm 3 constructs approximations for sums of ranges.
Ranges are merged by finding the lowest lower bound and the highest upper bound, then
correcting the stride. An expression is merged with a range or another expression by treating it as
a range with a lower bound equal to its upper bound. Algorithm 4 thus computes the same result
The most interesting subscript expressions are those containing references to scalar parameters
and global variables. We represent such symbolic expressions as global value numbers so that they
may be tested for equality by the standardization and merge operations.
For each procedure, we construct symbolic subscript expressions and accumulate initial regular
sections with no knowledge of interprocedural effects. The precision of our analysis depends on
function build range(e)
begin
if e is a leaf expression (constant, formal, or global value; or ?) then
return(e)
for each subexpression s of e
replace s with build range(s)
select form of e
when
[l 0: u 0: s
return([(l 0+ l
when a
when a   [l
otherwise return(?)
select
end.
Algorithm 3: Moving Ranges to the Top Level of an Expression
recording questions about side effects, but not answering them until the results of other interprocedural
analyses are available.
4.1 Symbolic Analysis
Constructing regular sections requires the calculation of symbolic expressions for variables used in
subscripts. While there are many published algorithms for performing symbolic analysis and global
value numbering [26, 27, 28], their preliminary transformations and complexity make them difficult
to integrate into PFC. Our implementation builds global value numbers with the help of PFC's
existing dataflow analysis machinery.
Leaf value numbers are constants and the global and parameter values available on procedure
entry. We build value numbers for expressions by recursively obtaining the value numbers for
subexpressions and reaching definitions. Value numbers reaching the same reference along different
def-use edges are merged. If either the merging or the occurrence of an unknown operator creates
a unknown (?) value, the whole expression is lowered to ?.
Induction variables are recognized by their defining loop headers and replaced with the inductive
range. (Auxiliary induction variables are currently not identified.) For example, consider the
following code fragment.
function merge(a, b)
begin
if
if
if a is a range then let [l a ; u a ; s a
else let [l a ; u a ; s a
if b is a range then let [l b ;
else let [l b ;
and abs can return ? */
returns a */
if l
else if s
else return([l
end.
Algorithm 4: Merging Expressions and Ranges
DIMENSION A(N)
ENDDO
RETURN
END
Dataflow analysis constructs def-use edges from the subroutine entry to the uses of N and M, and
from the DO loop to the use of I. It is therefore simple to compute the subscript in A's regular
section: M   [1 which is converted to the range names M and N are actually
replaced by their formal parameter indices). Note that expressions that are nonlinear during local
analysis may become linear in later phases, especially after constant propagation.
4.2 Avoiding Compilation Dependences
To construct accurate value numbers, we require knowledge about the effects of call sites on scalar
variables. However, using interprocedural analysis to determine these effects can be costly.
A programming support system using interprocedural analysis must examine each procedure
at least twice: 2 once when gathering information to be propagated between procedures, and again
when using the results of this propagation in dependence analysis and/or transformations. By
precomputing the local information, we can construct an interprocedural propagation phase which
iterates over the call graph without additional direct examination of any procedure.
To achieve this minimal number of passes, all interprocedural analyses must gather local information
in one pass, without the benefit of each others' interprocedural solutions. However, to build
precise local regular sections, we need information about the side effects of calls on scalars used
in subscripts. In the following code fragment, we must assume that M is modified to an unknown
value unless proven otherwise:
DIMENSION A(N)
RETURN
END
To achieve precision without adding a separate local analysis phase for regular sections, we
build regular section subscripts as if side effects did not occur, while annotating each subscript
expression with its hazards, or side effects that would invalidate it. We thus record that A(M) is
modified, with the sole parameter of CLOBBER as a hazard on M. During the interprocedural phase,
after producing the classical scalar side effect solution, but before propagating regular sections, we
check to see if CLOBBER may change M. If so, we change S1's array side effect to A(?). A similar
technique has proven successful for interprocedural constant propagation in PFC [31, 6].
Hazards must be recorded with each scalar expression saved for use in regular section analysis:
scalar actual parameters and globals at call sites as well as array subscripts. When we merge two
expressions or ranges, we take the union of their hazard sets.
4.3 Building Summary Regular Sections
With the above machinery in place, the use and mod regular sections for the local effects of a
procedure are constructed easily. In one pass through the procedure, we examine each reference to
2 This is not strictly true; a system computing only summary information (use, mod) or context information (alias)
can make do with one pass. Both the PFC and IR n /ParaScope systems perform summary and context analysis, as
well as constant propagation, and therefore require at least two passes [30, 5, 6].
a formal parameter, global, or static array. The symbolic analyzer provides value numbers for the
subscripts on demand; the resulting vector is a regular section. After the section for an individual
reference is constructed, it is immediately merged with the appropriate cumulative section(s), then
discarded.
5 Interprocedural Propagation
Regular sections for formal parameters are translated into sections for actual parameters as we
traverse edges in the call graph. The translated sections are merged with the summary regular sections
of the caller, requiring another translation and propagation step if this changes the summary.
To extend our implementation to recursive programs and have it terminate, we must bound the
number of times a change occurs.
5.1 Translation into a Call Context
If we were analyzing Pascal arrays, mapping the referenced section of a formal parameter array to
one for the corresponding actual parameter would be simple. We would only need to replace formal
parameters in subscript values of the formal section with their corresponding actual parameter
values, then copy the resulting subscript values into the new section. However, Fortran provides
no guarantee that formal parameter arrays will have the same shape as their actual parameters,
nor even that arrays in common blocks will be declared to have the same shape in every procedure.
Therefore, to describe the effects of a called procedure for the caller, we must translate the referenced
sections according to the way the arrays are reshaped.
The easiest translation method would be to linearize the subscripts for the referenced section
of a formal parameter, adding the offset of the passed location of the actual parameter [20].
The resulting section would give referenced locations of the actual as if it were a one-dimensional
array. However, if some subscripts of the original section are ranges or non-linear expressions,
linearization contaminates the other subscripts, greatly reducing the precision of dependence anal-
ysis. For this reason, we forego linearization and translate significantly reshaped dimensions as ?.
Algorithm 5 shows one method for translating a summary section for a formal parameter F into a
function translate(bounds F , ref F , bounds A , pass A )
begin
if ref
if not consistent then ref A
else if i ? rank(F) then if consistent then ref A
else ref A
else
replace scalar formal parameters in bounds F and ref F
with their corresponding actual parameters
bounds lo(bounds F [i]) pass A [i]
lo(bounds F [i]) pass A [i]
if consistent then ref A
else if stride(ref i lo(bounds A [i
/* delinearization is possible */
fits in bounds A [i]) or assume fit) then
ref A
else ref A
end for
end.
Algorithm 5: Translating a Summary Section
section for its corresponding actual parameter A. Translation proceeds from left to right through the
dimensions, and is precise until a dimension is encountered where the formal and actual parameter
are inconsistent (having different sizes or non-zero offset). The first inconsistent dimension is also
translated precisely if it is the last dimension of F and the referenced section subscript value(s) fit
in the bounds for A. Delinearization, which is not implemented, may be used to recognize that a
reference to F with a column stride the same as the column size of A corresponds to a row reference
in A.
5.2 Treatment of Recursion
The current implementation handles only non-recursive Fortran. Therefore, it is sufficient to proceed
in reverse invocation order on the call graph, translating sections up from leaf procedures
to their callers. The final summary regular sections are built in order, so that incomplete regular
sections need never be translated into a call site. However, the proposed Fortran 90 standard allows
recursion [25], and we plan an extension or re-implementation that will handle it. Unfortunately, a
straightforward iterative approach to the propagation of regular sections will not terminate, since
the lattice has unbounded depth.
Li and Yew [11] and Cooper and Kennedy [16] describe approaches for propagating subarrays
that are efficient regardless of the depth of the lattice. However, it may be more convenient to
implement a simple iterative technique while simulating a bounded-depth lattice. If we maintain
a counter with the summary regular section for each array and procedure, then we can limit the
number of times we allow the section to become larger (lower in the lattice) before going to ?. The
best way to do this is by keeping one small counter (e.g., two bits) per subscript. Variant subscripts
will then go quickly to ?, leaving precise subscripts unaffected. If we limit each subscript to being
lowered in the subscript lattice k times, then an array of rank d will have an effective lattice depth
of kd + 1.
Since each summary regular section is lowered at most O(kd) times, each associated call site
is affected at most O(kdv) times (each time involving an O(d) merge), where v is the number of
referenced global and parameter variables. In the worst case, we then require O(kd 2 ve) subscript
merge and translation operations, where e is the number of edges in the call graph. This technique
allows us to use a lattice with bounds information while keeping time complexity comparable to
that obtained with the restricted regular section lattice.
6 Experimental Results
The precision, efficiency, and utility of regular section analysis must be demonstrated by experiments
on real programs. Our current candidates for "real programs" are the Linpack library of
linear algebra subroutines [32], the Rice Compiler Evaluation Program Suite, and the Perfect Club
benchmarks [33]. We ran the programs through regular section analysis and dependence analysis
in PFC, then examined the resulting dependence graphs by hand and in the ParaScope editor, an
interactive dependence browser and program transformer [4].
LINPACK Analysis of Linpack provides a basis for comparison with other methods for analyzing
interprocedural array side effects. Both Li and Yew [21] and Triolet [18] found several parallel
calls in Linpack using their implementations in the University of Illinois translator, Parafrase.
Linpack proves that useful numerical codes can be written in the modular programming style for
which parallel calls can be detected.
RiCEPS The Rice Compiler Evaluation Program Suite is a collection of 10 complete applications
codes from a broad range of scientific disciplines. Our colleagues at Rice have already run several
experiments on Riceps. Porterfield modeled cache performance using an adapted version of PFC
[34]. Goff, Kennedy and Tseng studied the performance of dependence tests on Riceps and other
benchmarks [35]. Some Riceps and Riceps candidate codes have also been examined in a study on
the utility of inline expansion of procedure calls [8]. The six programs studied here are two Riceps
codes linpackd and track) and four codes from the inlining study.
Perfect Club Benchmarks This suite was originally collected for benchmarking the performance
of supercomputers on complete applications. While we hope to test the performance of our
implementation on these programs, a delay in receiving them prevented us from obtaining more
than very preliminary results for this paper.
6.1 Precision
The precision of regular sections, or their correspondence to the true access sets, is largely a function
of the programming style being analyzed. Linpack is written in a style which uses many calls to
the BLAS (basic linear algebra subroutines), whose true access sets are precisely regular sections.
We did not determine the true access sets for the subroutines in Riceps, but of the six programs
analyzed, only dogleg and linpackd, which actually call Linpack, exhibited the Linpack coding
style.
While there exist regular sections to precisely describe the effects of the BLAS, our local analysis
was unable to construct them under complicated control flow. With changes to the BLAS to
eliminate unrolled loops and the conditional computation of values used in subscript expressions,
our implementation was able to build minimal regular sections that precisely represented the true
access sets. The modified DSCAL, for example, looks as follows:
DOUBLE PRECISION DA, DX(*)
IF (N .LE.
ENDDO
RETURN
END
Obtaining precise symbolic information is a problem in all methods for describing array side
effects. Triolet made similar changes to the BLAS; Li and Yew avoided them by first performing
interprocedural constant propagation. The fundamental nature of this problem indicates the desirability
of a clearer Fortran programming style or more sophisticated handling of control flow (such
as that described in Section 7).
6.2 Efficiency
We measured the total time taken by PFC to analyze the six Riceps programs. 3 Parsing, local
analysis, interprocedural propagation, and dependence analysis were all included in the execution
times.

Table

1 compares the analysis time required using classical interprocedural summary analysis
alone ("IP only") with that using summary analysis and regular section analysis combined ("IP
RS"). 4
program IP IP %
name Lines Procs only +RS Change
efie 1254
euler 1113 13 117 138 +15
vortex 540 19
track 1711 34 191 225 +15
dogleg 4199 48 272 377 +28
linpackd 28 44 +36
total 9172 142 882 1103 +25

Table

1: Analysis times in seconds (PFC on an IBM 3081D)
3 While we were able to run most of the Perfect programs through PFC, we have not yet obtained reliable timings on
the recently-upgraded IBM system at Rice.
4 We do not present times for the dependence analysis with no interprocedural information because it performs less
analysis on loops with call sites. Discounting this advantage, the time taken for classical summary analysis seems to
be less than 10 percent.
The most time time-consuming part of our added code is the local symbolic analysis for subscript
values, which includes an invocation of dataflow analysis. More symbolic analysis would improve
the practicality of the entire method. Overall, the additional analysis time is comparable to that
required to analyze programs after heuristically-determined inline expansion in Cooper, Hall and
Torczon's study [8].
We have not seen published execution times for the array side effect analyses implemented in
Parafrase by Triolet and by Li and Yew, except that Li and Yew state that their method runs
2.6 times faster than Triolet's [21]. Both experiments were run only on Linpack; it would be
particularly interesting to know how their methods would perform on complete applications.
6.3 Utility
We chose three measures of utility:
ffl reduced numbers of dependences and dependent references,
ffl increased numbers of calls in parallel loops, and
reduced parallel execution time.
Reduced Dependence Table 2 compares the dependence graphs produced using classical interprocedural
summary analysis alone ("IP") and summary analysis plus regular section analysis
All Array Dep. on Calls in Loops
Dependences loop carried loop independent
source IP RS %
efie 12338 12338 177 177 81 81
euler
vortex 1966 1966 220 220 73 73
track 4737 4725 0.25 68 67 1.5 27 26 3.7
dogleg
linpackd 496 399 19.6 191 116 39.3 67 45 32.8
Riceps 23213 22921 1.25 952 818 14.1 358 314 12.3
Linpack 12336 11035 10.5 3071 2064 32.8 1348 1054 21.8

Table

2: Effects of Regular Section Analysis on Dependences
("RS"). 5
Linpack was analyzed without interprocedural constant propagation, since library routines may
be called with varying array sizes. The first set of three columns gives the sizes of the dependence
graphs produced by PFC, counting all true, anti and output dependence edges on scalar and array
references in DO loops (including those references not in call sites). The other sets of columns count
only those dependences incident on array references in call sites in loops, with separate counts for
loop-carried and loop-independent dependences. Preliminary results for eight of the 13 Perfect
benchmarks indicate a reduction of 0.6 percent in the total size of the dependence graphs. 6
Parallelized Calls Table 3 examines the number of calls in Linpack which were parallelized
after summary interprocedural analysis alone ("IP"), after Li and Yew's analysis [21], and after
regular section analysis ("RS"). (Triolet's results from Parafrase resembled Li and Yew's.) Most
(17) of these call sites were parallelized in ParaScope, based on PFC's dependence graph, with no
transformations being necessary. The eight parallel call sites detected with summary interprocedural
analysis alone were apparent in ParaScope, but exploiting the parallelism requires a variant of
statement splitting that is not yet supported. Starred entries (?) indicate parallel calls which were
precisely summarized by regular section analysis, but which were not detected as parallel due to a
deficiency in PFC's symbolic dependence test for triangular loops. One call in QRDC was mistakenly
parallelized by Parafrase [36].
These results indicate, at least for Linpack, that there is no benefit to the generality of Triolet's
and Li and Yew's methods. Regular section analysis obtains exactly the same precision, with
a different number of loops parallelized only because of differences in dependence analysis and
transformations.
Improved Execution Time Two calls in the Riceps programs were parallelized: one in dogleg
and one in linpackd. Both were the major computational loops (linpackd's in DGEFA, dogleg's in
5 The dependence graphs resulting from no interprocedural analysis at all are not comparable, since no calls can be
parallelized and their dependences are collapsed to conserve space.
6 Sections are not yet propagated for arrays in common blocks. This deficiency probably resulted in more dependences
for the larger programs.
routine calls in Parallel Calls
name DO loops IP Li-Yew RS
\DeltaGBCO
\DeltaGECO
\DeltaPBCO
\DeltaPOCO
\DeltaPPCO
\DeltaTRCO
\DeltaGEDI
\DeltaPODI
\DeltaQRDC 9 5 4
\DeltaSIDI
\DeltaSIFA
\DeltaSVDC
\DeltaTRDI
other

Table

3: Parallelization of Linpack
DQRDC). 7 Running linpackd on 19 processors with the one call parallelized was enough to speed its
execution by a factor of five over sequential execution on the Sequent Symmetry at Rice. Further
experiments on improvements in parallel execution time await our acquisition of more Fortran codes
written in an appropriate style.
7 Future Work
More experiments are required to fully evaluate the performance of regular section analysis on
complete applications and find new areas for improvement. Based on the studies conducted so far,
extensions to provide better handling of conditionals and flow-sensitive side effects seem promising.
7.1 Conditional Symbolic Analysis
Consider the following example, derived from the BLAS:
DOUBLE PRECISION DA, DX(*)
ENDDO
RETURN
END
The two computations of the initial value for IX correspond to different ranges for the subscript of
It turns out that these
can both be represented by [1 For the merge operation to produce
this precise result requires that it have an understanding of the control conditions under which
expressions are computed.
7 In the inlining study at Rice, none of the commercial compilers was able to detect the parallel call in dogleg even
after inlining, presumably due to complicated control flow [8].
7.2 Killed Regular Sections
We have already found programs (scalgam and euler) in which the ability to recognize and localize
temporary arrays would cut the number of dependences dramatically, allowing some calls to be
parallelized. We could recognize interprocedural temporary arrays by determining when an entire
array is guaranteed to be modified before being used in a procedure. While this is a flow-sensitive
problem, and therefore expensive to solve in all its generality, even a very limited implementation
should be able to catch the initialization of many temporaries.
The subscript lattice for killed sections is the same one used for use and mod sections; however,
since kill analysis must produce underestimates of the affected region in order to be conservative,
the lattice needs to be inverted. In addition, this approach requires an intraprocedural dependence
analysis capable of using array kill information, such as those described by Rosene [37] and by
Gross and Steenkiste [38].
8 Conclusion
Regular section analysis can be a practical addition to a production compiler. Its local analysis
and interprocedural propagation can be integrated with those for other interprocedural techniques.
The required changes to dependence analysis are trivial-the same ones needed to support Fortran
90 sections.
These experiments demonstrate that regular section analysis is an effective means of discovering
parallelism, given programs written in an appropriately modular programming style. Such a style
can benefit advanced analysis in other ways, for example, by keeping procedures small and simplifying
their internal control flow. Our techniques will not do as well on programs written in a style
that minimizes the use of procedure calls to compensate for the lack of interprocedural analysis in
other compilers. Compilers must reward the modular programming style with fast execution time
for it to take hold among the computation-intensive users of supercomputers. In the long run it
should make programs easier for both their writers and automatic analyzers to understand.

Acknowledgements

We would like to thank our colleagues on the PFC and ParaScope projects, who made this research
possible. We further thank David Callahan for his contributions to regular section analysis, and
Kathryn M c Kinley, Mary Hall, and the reviewers for their critiques of this paper.



--R

"Analysis of interprocedural side effects in a parallel programming environment,"
A Global Approach to Detection of Parallelism.
"PFC: A program to convert Fortran to parallel form,"
"Interactive parallel programming using the ParaScope Editor,"
"An implementation of interprocedural analysis in a vectorizing Fortran compiler,"
"Interprocedural constant propagation,"
"A catalogue of optimizing transformations,"
"An experiment with inline substitution,"
"Abstract interpretation: a unified lattice model for static analysis of programs by construction or approximation of fixpoints,"
"Semantic foundations of program analysis,"
"Interprocedural analysis and program restructuring for parallel pro- grams,"
"Program parallelization with interprocedural analysis,"
A Method for Determining the Side Effects of Procedure Calls.
"An interprocedural data flow analysis algorithm,"
"Efficient computation of flow insensitive interprocedural summary information,"
"Interprocedural side-effect analysis in linear time,"
"Direct parallelization of CALL statements,"
"Interprocedural analysis for program restructuring with Parafrase,"
"A direct parallelization of CALL statements - a review,"
"Interprocedural dependence analysis and parallelization,"
"Efficient interprocedural analysis for program parallelization and re- structuring,"
Interactive Parallelization of Numerical Scientific Programs.
"A technique for summarizing data access and its use in parallelism enhancing transformations,"
"A mechanism for keeping useful internal information in parallel programming tools: the Data Access Descriptor,"
X3J3 Subcommittee of ANSI
"Affine relationships among variables of a program,"
"Symbolic program analysis in almost-linear time,"
"Global value numbers and redundant com- putations,"
"Compiler analysis of the value ranges for variables,"
"The impact of interprocedural analysis and optimization in the IR n programming environment,"
Compilation Dependences in an Ambitious Optimizing Compiler.
Philadelphia: SIAM Publications
"Supercomputer performance evaluation and the Perfect benchmarks,"
Software Methods for Improvement of Cache Performance on Supercomputer Applications.
"Practical dependence testing,"
"Private communication,"
Incremental Dependence Analysis.
"Structured dataflow analysis for arrays and its use in an optimizing compiler,"
--TR
The impact of interprocedural analysis and optimization in the R<sup>n</sup> programming environment
Interprocedural constant propagation
Interprocedural dependence analysis and parallelization
Direct parallelization of call statements
A global approach to detection of parallelism
Analysis of interprocedural side effects in a parallel programming environment
Interprocedural side-effect analysis in linear time
Efficient interprocedural analysis for program parallelization and restructuring
Global value numbers and redundant computations
A technique for summarizing data access and its use in parallelism enhancing transformations
A mechanism for keeping useful internal information in parallel programming tools: the data access descriptor
Structured dataflow analysis for arrays and its use in an optimizing complier
Practical dependence testing
Supercomputer performance evaluation and the Perfect Benchmarks
Efficient computation of flow insensitive interprocedural summary information
An interprocedural data flow analysis algorithm
Abstract interpretation
Interactive Parallel Programming using the ParaScope Editor
A method for determining the side effects of procedure calls.
Compilation dependences in an ambitious optimizing compiler (interprocedural, recompilation)
Interactive parallelization of numerical scientific programs
Software methods for improvement of cache performance on supercomputer applications
Incremental dependence analysis

--CTR
Peiyi Tang, Exact side effects for interprocedural dependence analysis, Proceedings of the 7th international conference on Supercomputing, p.137-146, July 19-23, 1993, Tokyo, Japan
Donald G. Morris , David K. Lowenthal, Accurate data redistribution cost estimation in software distributed shared memory systems, ACM SIGPLAN Notices, v.36 n.7, p.62-71, July 2001
M. Jimnez , J. M. Llabera , A. Fernndez , E. Morancho, A general algorithm for tiling the register level, Proceedings of the 12th international conference on Supercomputing, p.133-140, July 1998, Melbourne, Australia
S. Carr , K. Kennedy, Compiler blockability of numerical algorithms, Proceedings of the 1992 ACM/IEEE conference on Supercomputing, p.114-124, November 16-20, 1992, Minneapolis, Minnesota, United States
D. Brent Weatherly , David K. Lowenthal , Mario Nakazawa , Franklin Lowenthal, Dyn-MPI: Supporting MPI on Non Dedicated Clusters, Proceedings of the ACM/IEEE conference on Supercomputing, p.5, November 15-21,
Linda Burton , William Hatchett , Mari Hobkirk , Charles Powell, Using high performance GIS software to visualize data: a hands-on software demonstration, Proceedings of the 1998 ACM/IEEE conference on Supercomputing (CDROM), p.1-14, November 07-13, 1998, San Jose, CA
Helen Parke , Alisa Chapman, A proposal for preservice student technology competence, Proceedings of the 1998 ACM/IEEE conference on Supercomputing (CDROM), p.1-9, November 07-13, 1998, San Jose, CA
Compilation techniques for block-cyclic distributions, Proceedings of the 8th international conference on Supercomputing, p.392-403, July 11-15, 1994, Manchester, England
Kathryn S. McKinley, Evaluating automatic parallelization for efficient execution on shared-memory multiprocessors, Proceedings of the 8th international conference on Supercomputing, p.54-63, July 11-15, 1994, Manchester, England
Umit Rencuzogullari , Sandhya Dwardadas, Dynamic adaptation to available resources for parallel computing in an autonomous network of workstations, ACM SIGPLAN Notices, v.36 n.7, p.72-81, July 2001
Craig Chase , Kay Crowley , Joel Saltz , Anthony Reeves, Compiler and runtime support for irregularly coupled regular meshes, Proceedings of the 6th international conference on Supercomputing, p.438-446, July 19-24, 1992, Washington, D. C., United States
R. Veldema , R. F. H. Hofman , R. A. F. Bhoedjang , C. J. H. Jacobs , H. E. Bal, Source-level global optimizations for fine-grain distributed shared memory systems, ACM SIGPLAN Notices, v.36 n.7, p.83-92, July 2001
G. Agrawal , A. Sussman , J. Saltz, Compiler and runtime support for structured and block structured applications, Proceedings of the 1993 ACM/IEEE conference on Supercomputing, p.578-587, December 1993, Portland, Oregon, United States
Honghui Lu , Alan L. Cox , Sandhya Dwarkadas , Ramakrishnan Rajamony , Willy Zwaenepoel, Compiler and software distributed shared memory support for irregular applications, ACM SIGPLAN Notices, v.32 n.7, p.48-56, July 1997
Tor E. Jeremiassen , Susan J. Eggers, Static Analysis of Barrier Synchronization in Explicitly Parallel Programs, Proceedings of the IFIP WG10.3 Working Conference on Parallel Architectures and Compilation Techniques, p.171-180, August 24-26, 1994
Mary W. Hall , Ken Kennedy, Efficient call graph analysis, ACM Letters on Programming Languages and Systems (LOPLAS), v.1 n.3, p.227-242, Sept. 1992
Jae Bum Lee , Chu Shik Jhon, Reducing coherence overhead of barrier synchronization in software DSMs, Proceedings of the 1998 ACM/IEEE conference on Supercomputing (CDROM), p.1-18, November 07-13, 1998, San Jose, CA
Keith D. Cooper , Ken Kennedy, Interprocedural side-effect analysis in linear time, ACM SIGPLAN Notices, v.39 n.4, April 2004
Sotiris Ioannidis , Umit Rencuzogullari , Robert Stets , Sandhya Dwarkadas, CRAUL&colon; Compiler and run-time integration for adaptation under load[1]This work was supported in part by NSF grants CDA-9401142, CCR-9702466, and CCR-9705594&semi; and an external research grant from Compaq., Scientific Programming, v.7 n.3-4, p.261-273, August 1999
Jay P. Hoeflinger , Yunheung Paek , Kwang Yi, Unified Interprocedural Parallelism Detection, International Journal of Parallel Programming, v.29 n.2, p.185-215, April 2001
Radu Rugina , Martin Rinard, Automatic parallelization of divide and conquer algorithms, ACM SIGPLAN Notices, v.34 n.8, p.72-83, Aug. 1999
Jaydeep Marathe , Frank Mueller , Tushar Mohan , Bronis R. de Supinski , Sally A. McKee , Andy Yoo, METRIC: tracking down inefficiencies in the memory hierarchy via binary rewriting, Proceedings of the international symposium on Code generation and optimization: feedback-directed and runtime optimization, March 23-26, 2003, San Francisco, California
Sandhya Dwarkadas , Alan L. Cox , Willy Zwaenepoel, An integrated compile-time/run-time software distributed shared memory system, ACM SIGPLAN Notices, v.31 n.9, p.186-197, Sept. 1996
Junjie Gu , Zhiyuan Li , Gyungho Lee, Experience with efficient array data flow analysis for array privatization, ACM SIGPLAN Notices, v.32 n.7, p.157-167, July 1997
Mary H. Hall , Saman P. Amarasinghe , Brian R. Murphy , Shih-Wei Liao , Monica S. Lam, Detecting coarse-grain parallelism using an interprocedural parallelizing compiler, Proceedings of the 1995 ACM/IEEE conference on Supercomputing (CDROM), p.49-es, December 04-08, 1995, San Diego, California, United States
Satish Chandra , James R. Larus, Optimizing communication in HPF programs on fine-grain distributed shared memory, ACM SIGPLAN Notices, v.32 n.7, p.100-111, July 1997
Compiler optimizations for Fortran D on MIMD distributed-memory machines, Proceedings of the 1991 ACM/IEEE conference on Supercomputing, p.86-100, November 18-22, 1991, Albuquerque, New Mexico, United States
Dhruva R. Chakrabarti , Prithviraj Banerjee, Global optimization techniques for automatic parallelization of hybrid applications, Proceedings of the 15th international conference on Supercomputing, p.166-180, June 2001, Sorrento, Italy
Chen Ding , Ken Kennedy, Improving cache performance in dynamic applications through data and computation reorganization at run time, ACM SIGPLAN Notices, v.34 n.5, p.229-241, May 1999
Compiling Fortran D for MIMD distributed-memory machines, Communications of the ACM, v.35 n.8, p.66-80, Aug. 1992
Arun Chauhan , Ken Kennedy, Reducing and Vectorizing Procedures for Telescoping Languages, International Journal of Parallel Programming, v.30 n.4, p.291-315, August 2002
D. Brent Weatherly , David K. Lowenthal , Mario Nakazawa , Franklin Lowenthal, Dyn-MPI: supporting MPI on medium-scale, non-dedicated clusters, Journal of Parallel and Distributed Computing, v.66 n.6, p.822-838, June 2006
Saman P. Amarasinghe , Monica S. Lam, Communication optimization and code generation for distributed memory machines, ACM SIGPLAN Notices, v.28 n.6, p.126-138, June 1993
Exploiting cache affinity in software cache coherence, Proceedings of the 8th international conference on Supercomputing, p.264-273, July 11-15, 1994, Manchester, England
Jaydeep Marathe , Frank Mueller , Tushar Mohan , Sally A. Mckee , Bronis R. De Supinski , Andy Yoo, METRIC: Memory tracing via dynamic binary rewriting to identify cache inefficiencies, ACM Transactions on Programming Languages and Systems (TOPLAS), v.29 n.2, p.12-es, April 2007
Tor E. Jeremiassen , Susan J. Eggers, Reducing false sharing on shared memory multiprocessors through compile time data transformations, ACM SIGPLAN Notices, v.30 n.8, p.179-188, Aug. 1995
Yunheung Paek , Jay Hoeflinger , David Padua, Efficient and precise array access analysis, ACM Transactions on Programming Languages and Systems (TOPLAS), v.24 n.1, p.65-109, January 2002
Junjie Gu , Zhiyuan Li , Gyungho Lee, Symbolic array dataflow analysis for array privatization and program parallelization, Proceedings of the 1995 ACM/IEEE conference on Supercomputing (CDROM), p.47-es, December 04-08, 1995, San Diego, California, United States
Y. Paek , A. Navarro , E. Zapata , J. Hoeflinger , D. Padua, An Advanced Compiler Framework for Non-Cache-Coherent Multiprocessors, IEEE Transactions on Parallel and Distributed Systems, v.13 n.3, p.241-259, March 2002
Manish Gupta , Edith Schonberg , Harini Srinivasan, A Unified Framework for Optimizing Communication in Data-Parallel Programs, IEEE Transactions on Parallel and Distributed Systems, v.7 n.7, p.689-704, July 1996
Radu Rugina , Martin Rinard, Symbolic bounds analysis of pointers, array indices, and accessed memory regions, ACM SIGPLAN Notices, v.35 n.5, p.182-195, May 2000
Evaluation of compiler optimizations for Fortran D on MIMD distributed memory machines, Proceedings of the 6th international conference on Supercomputing, p.1-14, July 19-24, 1992, Washington, D. C., United States
Arun Chauhan , Ken Kennedy, Optimizing strategies for telescoping languages: procedure strength reduction and procedure vectorization, Proceedings of the 15th international conference on Supercomputing, p.92-101, June 2001, Sorrento, Italy
Ayon Basumallik , Rudolf Eigenmann, Optimizing irregular shared-memory applications for distributed-memory systems, Proceedings of the eleventh ACM SIGPLAN symposium on Principles and practice of parallel programming, March 29-31, 2006, New York, New York, USA
Ayon Basumallik , Rudolf Eigenmann, Towards automatic translation of OpenMP to MPI, Proceedings of the 19th annual international conference on Supercomputing, June 20-22, 2005, Cambridge, Massachusetts
M. W. Hall , S. Hiranandani , K. Kennedy , C.-W. Tseng, Interprocedural compilation of Fortran D for MIMD distributed-memory machines, Proceedings of the 1992 ACM/IEEE conference on Supercomputing, p.522-534, November 16-20, 1992, Minneapolis, Minnesota, United States
Steve Carr , R. B. Lehoucq, Compiler blockability of dense matrix factorizations, ACM Transactions on Mathematical Software (TOMS), v.23 n.3, p.336-361, Sept. 1997
Victor Delaluz , Mahmut Kandemir , N. Vijaykrishnan , Anand Sivasubramaniam , Mary Jane Irwin, Hardware and Software Techniques for Controlling DRAM Power Modes, IEEE Transactions on Computers, v.50 n.11, p.1154-1173, November 2001
Kathryn S. McKinley, A Compiler Optimization Algorithm for Shared-Memory Multiprocessors, IEEE Transactions on Parallel and Distributed Systems, v.9 n.8, p.769-787, August 1998
Dhruva R. Chakrabarti , Prithviraj Banerjee, Static Single Assignment Form for Message-Passing Programs, International Journal of Parallel Programming, v.29 n.2, p.139-184, April 2001
Junjie Gu , Zhiyuan Li, Efficient Interprocedural Array Data-Flow Analysis for Automatic Program Parallelization, IEEE Transactions on Software Engineering, v.26 n.3, p.244-261, March 2000
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
Chen Ding , Ken Kennedy, Improving effective bandwidth through compiler enhancement of global cache reuse, Journal of Parallel and Distributed Computing, v.64 n.1, p.108-134, January 2004
Manish Gupta , Sayak Mukhopadhyay , Navin Sinha, Automatic Parallelization of Recursive Procedures, International Journal of Parallel Programming, v.28 n.6, p.537-562, December 2000
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
Radu Rugina , Martin C. Rinard, Symbolic bounds analysis of pointers, array indices, and accessed memory regions, ACM Transactions on Programming Languages and Systems (TOPLAS), v.27 n.2, p.185-235, March 2005
Mary W. Hall , Saman P. Amarasinghe , Brian R. Murphy , Shih-Wei Liao , Monica S. Lam, Interprocedural parallelization analysis in SUIF, ACM Transactions on Programming Languages and Systems (TOPLAS), v.27 n.4, p.662-731, July 2005
Mohammad R. Haghighat , Constantine D. Polychronopoulos, Symbolic analysis for parallelizing compilers, ACM Transactions on Programming Languages and Systems (TOPLAS), v.18 n.4, p.477-518, July 1996
programmingsupport systems;linear algebra subroutines;program testing;index termsoptimizing compilers;procedure calls;application codes;high-level language constructs;subarrays;interprocedural bounded regular section analysis;production compiler;RiceCompiler Evaluation Program Suite;dependence analysis;RiCEPS;scientific disciplines;parallel programming;LINPACK library;program compilers;modular programming style