Subject: Report Publication

From: [email-masked]
Date: Mon, 6 Dec 93 16:09:48 GMT

SCHEDULE FOR PUBLICATION OF PARKBENCH REPORT
            --------------------------------------------

It seems appropriate that I, as chairman, take responsibility for assembling
the final text for publication of the first PARKBENCH REPORT, and seeing
it through to publication. The version made public at Supercomputing'93 has
been accepted for publication in Wiley's Journal "Scientific Programming" by
the editor Ron Perrott after we respond to his editorial comments. I am
therefore sending by ordinary snail-mail to the committee member responsible 
for each chapter, his chapter with the editor's original annotations, with a 
photocopy of the rest of the report and his covering letter. To ensure rapid
publication I shall follow the following schedule:

1  Jan 1994 - Last day for receipt by RWH of edited chapters from subcommittee
              leaders. Please send the text to me by e-mail but please do not 
              include any screen dumps as e-mail. They clog the mail system 
              and should be ftp'd . If there are no changes, simply omit them
              as I have them already. 
              Any chapters not received by this date will be edited by RWH as 
              best he can.

              My e-mail is:        [email-masked]

15 Jan 1994 - Last day for submission of revised manuscript by RWH to Ron
              Perrott. Submission will be in Latex form. Publication can be 
              expected 3-4 months after this i.e. say May 1994 (spring or 
              summer edition, 1994).

To give you an idea of what to expect, look at Scientific Programming vol 2
numbers 1 & 2 which is a special issue devoted to the HPF report. The editor 
is suggesting that we refer to our present Chapters as Sections instead, as 
has been done with the HPF report. I am against this, because we have always 
calleds them chapters, and they are substantial enough to be so named. Views 
please.

There are some issues to be resolved about the copyright agreement that I
presumably will sign on behalf of the committee. As I see it, the important
thing is that the publisher agrees that the material is in the public domain
and may be freely reproduced without payment by anyone, provided attribution
is made to the Parkbench committee and to Scientific Programming. This seems
to have been achieved by HPF (see second page of above quoted issue of the 
Journal). I shall try to follow this pattern and keep committee members
posted. Also I wish explicitly to add that the material is publically 
available electronically, from the UTK Netlib server. Whatever is agreed 
with the publisher will be put to the committee by e-mail before I sign 
anything.  If you have any comments on these issues, now is the time to
send them to pbwg-comm, so that I may take them into consideration.

                   Best regards
                      Roger Hockney
             (Chairman Parkbench Committee)

---

From: <[email-masked]>
Date: Tue, 21 Dec 93 10:51:49 EST

>1  Jan 1994 - Last day for receipt by RWH of edited chapters from 
                subcommittee leaders. 

Roger,
Here is an updated version of the chapter 6. I tried to get into account all
comments I got from R.H.Perrott.

However, I have not modyfied the following:

 - phrases like "We will ..." . Please, modify them to conform the rest of the
   text.

 - notions of "node compilation" and "a node compiler". For me they are OK.
   Let me know if you think I should change it.     

 - runtime (as opposed to "run time" or "run-time"). The word "runtime" is used
   by Parallel Compiler Runtime Consortium, and as far as I can tell, it is 
   widely accepted by (parallel compiler + runtime) community. 
   [Of course, I do not think that it is that important to make an issue.]

Tom

===============================================================================
% citation: hpff : High Performance Fortran Language Specification, 
%                  High Performance Fortran Forum, Scientific Programming,
%                  Vol 2, Nos 1 and 2, Summer '93.
%   

%------------------------------------------------------------------------
%      PARKBENCH REPORT (fourth draft), File:        compil4.tex
%------------------------------------------------------------------------
%file compil4.tex
%compiled by Tom Haupt for compiler benchmarks subcommittee

\chapter{HPF Compiler Benchmarks\protect
\footnote{assembled by Tom Haupt for Compiler Benchmarks subcommittee}}

\section{Objectives}

For most users, the performance of codes generated by a compiler is what
actually matters. This can be inferred from running HPF version of
PARKBENCH codes described in chapter 4 and 5. For HPF compiler developers 
and implementators, however, {\it an additional} benchmark suite may be 
very useful: the benchmark suite that can evaluate specific HPF compilation 
phases and the compiler runtime support. For that purpose, the relevant metric
is the ratio of execution times of compiler generated to hand coded 
programs as a function of the problem size and number of processors engaged 
in the computation.

The compilation process can be logically divided into several phases,
and each of them influence the efficiency of the resulting code. The
initial stage is parsing of a source code which results in an internal
representation of the code. It is followed by compiler transformations,
like data distribution, loop transformations, computation distribution, 
communication detection, sequentialization, insertion of calls to a
runtime support, and others. This we will call a HPF-specific phase of
compilation. The compilation is concluded by code generation phase. For
portable compilers that output Fortran 77 + message passing code, the node
compilation is factorized out and the efficiency of the node
compiler can be evaluated separately.  

This benchmark suite addresses the HPF-specific phase only. Thus, it is
well suited for performance evaluation of both translators (HPF to
Fortran 77 + message passing) and genuine HPF compilers. The parsing phase is 
an element of the conventional compiler technology and it is not of
interest in this context. The code generation phase involves
optimization techniques developed for  sequential compilers (in
particular, Fortran 90 compilers) as well as micro-grain parallelism or
vectorization. The object codes for specific platforms may be strongly
architecture dependent (e.g., may be very different for processors with
vector capabilities than for those without it). Evaluation of
performance of these aspects require different techniques than these
proposed here. 

It is worth noting, that the HPF-phase strongly affects the possibility
of optimization of the node codes. For example, insertions of calls to
the communication library may prohibit the node compiler from performing many
standard optimizations without expensive interprocedural analysis.
Therefore, its capability to exploit opportunities for optimizations at HPF
level and to generate the output code in such a  way that it can be further
optimized by the node compiler is an important element of evaluation of
HPF compilers. Nevertheless, evaluation of the HPF-phase separately is
very valuable since the hand coded programs face the same problems. We
will address these issues in future releases of the benchmark suite. 

Compilers for massively parallel and distributed systems are still the
object of research and laboratory testing rather than commercial
products. The parallel compiler technology  as well as methods of
evaluating it are not mature yet. Nevertheless, the advent of the HPF 
standard gives opportunity to develop systematic benchmarking techniques. 

The current definition of HPF \cite{hpff} cannot be recognized as an ultimate 
solution for parallel computing. Its limitations are well known, and many 
researchers are working on extensions to HPF to address a broader class of real
life, commercial and scientific applications. We expect new language
features to be added to the HPF definition in future versions of HPF,
and we will extend the benchmark suite accordingly. On the other hand,
new parallel languages based on languages other than Fortran, notably
C++, are becoming more and more popular. Since the parallelism is inherent in
a problem and not its representation, we anticipate many commonalities
in the parallel languages and corresponding compiler technologies,
notably sharing the runtime support. Therefore, we decided to address
this benchmark suite to these aspects of the compilation process that
are inherent to parallel processing in general, rather than testing
syntactic details of HPF.

\section{Low Level HPF Compiler Benchmarks}

\subsection{Overview}

The benchmark suite comprises several simple, synthetic applications which test
several aspects of  HPF compilation. The current version of the suite
addresses the basic features of HPF, and it is designed to measure
performance of early implementations of the compiler. They concentrate
on testing parallel implementation of explicitly parallel statements,
i.e., array assignments, FORALL statements, INDEPENDENT DO loops, and
intrinsic functions with different mapping directives. In addition, the
low level compiler benchmarks address problem of passing distributed arrays
as arguments to subprograms.

The language features not included in the HPF subset are not addressed in this
release of the suite. The next releases will contain more kernels that
will address all features of HPF, and also they will be sensitive to
advanced compiler transformations.

The codes included in this suite are either adopted from existing benchmark
suites, NAS suite \cite{NAS}, Livermore Loops \cite{Liv}, and the Purdue Set \cite{Rice}, or are developed
at Syracuse University.

\subsection{FORALL statement - kernel FL}
FORALL statement provides a convenient syntax for simultaneous assignments
to large groups of array elements. Such assignments lie at the heart of the
data parallel computations that HPF is designed to express. The idea behind 
introducing FORALL in HPF is to generalize Fortran 90 array assignments to
 make expressing parallelism easier. Kernel FL provides several examples of 
FORALL statements that are difficult or inconvenient to write using Fortran 90 syntax.

\subsection{Explicit template - kernel TL}
Parallel implementation of the array assignments, including FORALL
statements, is a central issue for an early HPF compiler. Given a data
distribution, the compiler distributes computation over available
processors. An efficient compiler achieves an optimal load balance with
minimum interprocessor communication. 

Sometimes, the programmers may help the compiler to minimize 
interprocessor communication by suitable data mapping, in particular by
defining a relative alignment of different data objects. This may be
achieved by aligning the data objects with an explicitly declared
template. Kernel TL provides an example of this kind.

\subsection{Communication detection in array assignments - kernels AA, SH, ST, and IR}
Once the data and iteration space is distributed, the next step that
strongly influences efficiency of the resulting codes is communication
detection and code generation to execute data movement. In general, the
off-processor data elements must be gathered before execution of an
array assignment, and the results are to be scattered to destination
processors after the assignment is completed. In other words, some of
the array assignments may require a preprocessing phase to determine
which off-processor data elements are needed and execute the gather
operation. Similarly, they may require postprocessing (scatter). Many
different techniques may be used to optimize these operations. To
achieve high efficiency, it may be very important that the compiler is
able to recognize structured communication patterns, like shift,
multicast, etc. Kernels AA, SH, and ST introduce different structured
communication patterns, and kernel IR is an example of an array
assignment that requires unstructured communication (because of
indirections). 

\subsection{INDEPENDENT assertion - kernel EP}

In addition to array assignments and FORALL statments, parallelism may be
expressed by using INDEPENDENT assertions.  The EP kernel test the performance
of  INDEPENDENT DO construct with NEW variables. 

\subsection{Non-elemental intrinsic functions - kernel RD}

Fortran 90 intrinsics and HPF functions offer yet another way to express
parallelism. Kernel RD tests implementation of several reduction functions. 

\subsection{Passing distributed arrays as subprogram arguments - kernels AS, IT, IM and EI}
The last group of kernels, demonstrate passing distributed arrays as subprogram arguments. They represents three
typical cases: 

\begin{enumerate}
\item a known mapping of the actual argument is to be preserved by the dummy
argument (AS). 
\item mapping of the dummy argument is to be inherited from the actual
argument, thus no remapping is necessary. The mapping is known at
compile time (IT).
\item mapping of the dummy argument is to be identical to that of the
actual argument, but the mapping is not known at compile time (IM).
\end{enumerate} 

\section{Summary}

The synthetic compiler benchmark suite described here is an addition to the
benchmark kernels and applications described in chapter 4 and 5. It is
not meant as a tool to evaluate the overall performance of the compiler
generated codes. It has been introduced as an aid for compiler
developers and implementators to address some selected aspect of the HPF
compilation process. In the current version, the suite does not comprise
a comprehensive sample of HPF codes. Actually, it addresses only the HPF
subset. Hopefully, this way, we will contribute to the establishment of a 
systematic compiler benchmarking methodology. We intend to continue our 
effort to develop a complete, fully representative HPF benchmark suite. 

% ----------------------------------------------------------------------------