
\documentstyle[12 pt]{article}

\textheight=8.0in
\voffset=-0.5in
\textwidth=6.0in
\hoffset=-0.5in

\begin{document}

\title{\large \bf{Quarterly R\&D Status Report No. 11}\\
  \large \bf{Common Runtime Support for High Performance Languages}}

\author{\sf Period Covered \\
    \sf From: 1 January 1997 \\
    \sf To: 31 March 1997 \vspace{10mm} }

\date{\bf April 15, 1997}
    
\maketitle

\begin{center}
Prepared By \vspace{3mm} \\
Geoffrey C. Fox \\
Northeast Parallel Architectures Center \\
at Syracuse University \\
111 College Place \\
Syracuse, NY 13244-4100 \vspace{10mm} \\
Prepared For \vspace{3mm} \\
ESC/ENS \\
5 Eglin Street, Building 1704 \\
Hanscom AFB, MA 01731-2116 \\
Attn.: Mr. Harry Koch \vspace{10mm} \\
Sponsored By \vspace{3mm} \\
Advanced Research Projects Office/CSTO \\
\underline{Common Runtime Support for High Performance Parallel Languages}\\
ARPA Order No. B526 \\
Issued by ESC/ENS under contract \\
\# F19628-94-C-0057
\end{center}

\section*{Program Technical Status}

\subsection*{A. Description of progress during reporting period, supported
by reasons for any changes reported previously}

During this reporting period, all tasks continued to move forward.
Further, we now have essentially completed the planning of last phases of 
the project and have a good draft plan for full completion of the runtime 
in two stages.

\begin{description}
\item[Task 1:] Common Code and Data Descriptor. As reported earlier,
       this specification has been completed, and a common runtime,
       the major undertaking of this project,
       is being built based on the specification.
\item[Task 2:] Address Translation Mechanism. Syracuse group has completed
       the implementation of an address translation scheme in the
       current runtime system, which include support mainly for regular
       problems; Maryland group has implemented a scheme (chaos) for irregular
       problems plus some initial work (meta-chaos) on enabling 
       interoperability of different mechanisms. 
\item[Task 3:] Common Computational Functions. In the current runtime,
       most HPF intrinsic functions have been implemented. In particular,
       the class of {\tt XXX\_PREFIX} functions are implemented in this
       reporting period.
\item[Task 4:] Common Data Movement Routines. Syracuse group has 
       implemented an extensive set of data movement routines in the
       runtime, including {\tt remap} for regular problems, and
       {\tt gather/scatter} for irregular problems. Florida group
       has developed some advanced algorithm for {\tt combining-scatter}
       type of operations and have done some experiments, but yet to be 
       implemented within general PCRC runtime framework.

       In fact, the above four tasks are essential pieces implemented
       in the PCRC runtime system, which have been completed 80\%.
\item[Task 5:] Common Data Movement Deriving and Optimization Routines.
       There are two facets of this work. One is, as mentioned in
       last report, to devise a mechanism for effective data movement
       between different data arrangements. This is interoperability
       problem. The other is to devise proper algorithm for compiler
       to use or call during runtime to determine the optimal data
       movement functions. For the former, as mentioned in Task 2,
       {\em meta-chaos } idea has been developed and initial experiment
       has been done; for the latter, Syracuse group has developed
       an effective algorithm which is used in retargeting compiler
       as required by Task 8.
\item[Task 6:] Common Compiler Data Movement Interface Specification.
       As reported in last report, a draft had been completed. A
       final revision is being conducted. 
\item[Task 7:] Software Engineering Issues. We continue the emphasis
       on the quality of deliverable software. In particular, GNU systems
       and conventions are employed to manage the development process.
\item[Task 8:] Retargeting Current Compilers Based on the Runtime
       System. The retargeting activities continue at Syracuse.
       In particular, an HPF 1.0 front-end was released to public
       domain in this reporting period (January, 1997), see \\
        http://www.npac.syr.edu/projects/pcrc/hpffe.html

       Work on Java front-ends was pursued at Indiana, Maryland, and 
       Syracuse.
\end{description}

\subsection*{B. Description of any special programs developed or major
items of experiments or special equipment purchased or constructed during
reporting period}

As Java gets its dominance in Internet programming, we believe it will
also be widely used in scientific and engineering computation. Thus, 
in addition to the HPF 1.0 front-end as mentioned above, we've
also developed a Java front-end, which is now in testing stage.

Also, as HPF has evolved to version 2.0, we have extended our HPF
front-end to cover HPF 2.0, which is also in testing stage.

\subsection*{C. Notifications of any changes in key personnel associated
with the contract during the reporting period}

No change during this reporting period.

\subsection*{D. Summary of substantive information derived from noteworthy
trips, meetings, and special conferences held in connection with the
contract during the reporting period}

\begin{itemize}
\item A Workshop on Java for Scientific and Engineering Computation
      was held in Syracuse in late December, 1996. (This important
      event was not reported in last report.) Over 50 people from
      academia, industry, and national labs participated.
      This discussed how the PCRC runtime could be used by Java
      compilers.
\item Poster-presented Syracuse HPF front-end in the first HPF Users 
      Group Annual Meeting held in Santa Fe, NM, February, 1997.
\end{itemize}
     
\subsection*{E. Summary of any problems or areas of concern on which
procuring activity or guidance is required}

Due to some changes in member institutions, the original plan,
in particular, the statement about developing seven compilers 
sharing one runtime, needs to be modified. This reflects changes
in focus of the collaborating research groups. Further the value of PCRC
runtime to Java compiler has been established by PCRC. Our revised focus
includes the runtime to be demonstrated in 3 compiled languages
(parallel C++, Fortran (2 compilers), Java) and in SPMD mode.
We have found it hard at times to get timely quarterly reports 
from our subcontractors.
This has been addressed by frequent less formal communication
between the PI's.
However we intend to require formal submitted 
of the next quarterly contractors report so
that we can get a clear commitment to the revised plan
which is attached as a draft in the appendix.

\subsection*{F. Statement relative to the apparent sufficiency of
contractually prescribed effort to achieve the objectives of the contract}

The contractually prescribed effort is sufficient to achieve the
objectives of this contract.

\subsection*{G. Related accomplishments: i.e., scientific papers published,
etc.}

The following is a partial list of related reports/papers completed during this
reporting period.

\begin{enumerate}
\item
Geoffrey Fox, Wojtek Furmanski, ``Computing on the Web - New Approaches 
to Parallel Processing - Petaop and Exaop Performance in the Year 2007,''
NPAC Technical Report, SCCS-784, January, 1997.
\item 
Xiaoming Li, ``Runtime Oriented HPF Compilation'', 
NPAC Technical Report, SCCS-779, January 31, 1997.
\item
Geoffrey Fox, Xiaoming Li, Yuhong Wen, Guansong Zhang,
``Studies of Integration and Optimization of Interpreted and
Compiled Languages,'' NPAC Technical Report, SCCS-780, February 12, 1997. 
\item 
B. Carpenter, Y-J. Chang, G. Fox, et at, ``Experiments with
HPJava,'' Workshop on Java for Sci\&Eng Computation, Dec., 1996.
\item
Marina Chen and James Cowie, ``Java's Role in Distributed Collaboration,''
Workshop on Java for Sci\&Eng Computation, Dec., 1996.
\item
Aart J.C. Bik and Dennis Gannon, ``Automatically Exploiting Implicit
Parallelism in Java,''
Workshop on Java for Sci\&Eng Computation, Dec., 1996.
\item
Seungjo Bae, Khaled A. Alsabti, and Sanjay Ranka, ``Array
Combining Scatter Functions on Coarse-Grained Distributed
Memory Parallel Machines,'' Feb, 1997.
\item
G. Agrawal and J. Saltz, ``Interprocedural Data Flow Based Optimizations 
for Distributed Memory Compilation,'' Software: Practice and Experience, 
December, 1996 (to appear). 
\item
M. Cierniak and Wei Li, ``Optimizing Java Bytecodes,''
Workshop on Java for Sci\&Eng Computation, Dec., 1996. 
\item
Zoran Budimlic and Ken Kennedy, ``Optimizing Java -- Theory and Practice,''
Workshop on Java for Sci\&Eng Computation, Dec., 1996. 
\end{enumerate}

\subsection*{H. Planned activities and milestones for the next reporting
period}

As requested in a previous formal letter,
we are requesting a 9 months no cost extension (NCE) of this 
project from September 30, 1997 to June 30, 1998, in order to fulfill
the requirement specified in the project. A detailed two stage working
plan is attached as in the appendix. See Program Financial Status section
for the financial aspect of this extended period.

\subsection*{I. List of all equipment purchased during reporting period}

None.

\pagebreak

\section*{Program Financial Status}

The table below provides information required by contract.

\vspace{5mm}

\small
\begin{tabular}{| c | c | c | c | c | c | c |} \hline
\begin{tabular}{c}
WORK BREAKDOWN \\ 
STRUCTURE 
\end{tabular} & \multicolumn{3}{c|}
                {CUMULATIVE TO DATE} & 
                \multicolumn{3}{c|}{AT COMPLETION} \\ \hline
ELEMENT & \begin{tabular}{c}
          Planned \\
          Expended
          \end{tabular} & \begin{tabular}{c}
                          Actual \\
                          Expended 
                          \end{tabular} & \begin{tabular}{c}
                          Percent \\
                          Completed
                          \end{tabular} & BAC & LRE & Remarks \\ \hline
        & & & & & & \\ \hline
CLIN 0001 & & & & & & \\ \hline
Syracuse University & 3,218,954 & 2,693,343 & & & & \\ \hline
 \& subcontractors & & & & &  & \\ \hline
        & & & & & & \\ \hline
        & & & & & & \\ \hline
        & & & & & & \\ \hline
TOTAL &  3,218,954 & 2,693,343 & 84.70\% & & & \\ \hline
\end{tabular}
\normalsize

\vspace{5mm}

\begin{itemize}
\item[A.] Is current funding sufficient for the current FY ?  ~~~YES (see
below)

To date, a total of \$3,218,954 has been received. The original proposal
estimated a total cost of \$3,346,224, thus leaving \$127,270 balance 
to carry project through June 30, 1998.

\item[B.] What is the next Fiscal Year's funding requirement at current
anticipated levels ? ~~~ \$127,270.

\item[C.] Have you included in the report any explanation of the above data
and are they cross-referenced ? ~~~Yes.

\end{itemize}

\vspace{5mm}

\begin{tabbing}
\underline{Distr}\=\underline{ibution:} \\
\> ARP\=A/CSTO (2 org) \\
\> \> 3701 N. Fairfax Drive \\
\> \> Arlington, VA 22203-1714 \\
\> ESC/ENK (ltr only) \\
\> \> 5 Eglin Street \\
\> \> Hanscom AFB, MA 01731-2116 \\
\> \> Attn.: Mr. Dale V. Hawley
\end{tabbing}

\pagebreak

\section*{Appendix: Draft Revised SOW and Work Plan}

As indicated in the above, we are requesting a no cost extension of
this project until June 30, 1998. We divide the
period from April 1, 1997 to June 30, 1998 in two stages. Stage 1 is
from April 1, 1997 to August 31, 1997. Stage 2 is from September 1, 1997
to June 30, 1998. In this appendix, a revised statement
of work is provided corresponding to the new situation, then a detailed working
plan is described. This current draft will be replaced by a formal
plan in the 
next quarterly with clearer roles for each subcontractor.

\subsection*{Revised statement of work}

We will continue the activities towards the deliverables stated in
project proposal. In particular, the following items are identified
as distinct software packages delivered to the public domain.

\begin{itemize}
\item
PCRC runtime system. A partial release in the summer of 1997, and
a full release at the new requested end date.
\item
An HPF compiler using the PCRC runtime. 
\item
A retargeted shpf compiler using the PCRC runtime.
\item
A compiler/interpreter research and development infrastructure,
including multiple front-ends (HPF, C++, and Java) and tools.
\end{itemize}

After further negotiating with the subcontractors, we will
demonstrate the feasibility of parallel C++ and Java compiler
utilizing the PCRC runtime.

The following institutions will be involved in the project for
the remaining period.
\begin{itemize}
\item Syracuse University --- lead, responsible for majority of the
      implementation work.
\item Cooperating Systems --- help in software quality assurance and 
      documentation.
\item University of Maryland --- responsible for interoperability
      among different runtimes.
\item University of Rochester --- help in the feasibility study of
      a Java compiler using the PCRC runtime, and partial
      implementation.
\item University of Florida --- implement novel combining-scatter
      functions in PCRC runtime, studies of new algorithms for PCRC functions.
\item Indiana University --- help in the feasibility study of
      pC++ and Java compilers using the PCRC runtime, and
      implementation of pC++.
\item Texas --- Parts of DAGH system included in runtime.
\item Rice --- modest involvement, especially with Java compiler 
      requirements.
\end{itemize}
 
\subsection*{Draft two stage work plan including a no-cost extension period}

\noindent
(The declared role of Indiana and Texas is under discussion.)

\noindent
\paragraph{Stage 1 (April 1, 1997 to August 31, 1997):} aiming at accomplishing 
basic PCRC requirement and having a public domain PCRC runtime release.

We identify the following working items.
\begin{enumerate}
\item
A quality public domain runtime in C++.

    This runtime will be considered as PCRC proper. It will be based on 
and extended from Adlib.  It will be rich in contents, fulfilling most of 
the claims in PCRC project proposal, in particular, task 1, 2, 3, 4.

   To have a quality public release, the following work has to be completed.
\begin{itemize}
\item[a.] ghost region support
\item[b.] sorting functions
\item[c.] new combining scatter functions
\item[d.] experiment on interoperability between Syracuse runtime and
          Maryland runtime.
\item[e.] Adlib documentation
\item[f.] PCRC documentation
\item[g.] testsuite and tests
\item[h.] Fortran interface
\item[i.] Java interface
\end{itemize}

Syracuse will be the main force in the implementation work. Cooperating
Systems will help in testing and documentation. Florida will be
responsible for item {\tt c}. Maryland will implement item {\tt d}.
Rochester is involved in {\tt i}; Rice in {\tt h} and {\tt i}.
\item
An operational HPF compiler using the PCRC runtime.

Many issues that are not addressed by many groups'
     compiler efforts, such as separate compilation of
     subprograms, full support of FORALL statement, will
     be handled. This is part of task 8.

   To achieve this goal, the following work has to be done:
\begin{itemize}
\item[a.] documentation
\item[b.] demos and tests
\item[c.] ghost area support
\item[d.] full FORALL statement
\item[e.] procedure interface
\item[f.] retargeting Southampton shpf compiler to PCRC runtime
\end{itemize}

Syracuse will be the main force in the implementation work. Cooperating
Systems will help in testing and documentation. 

\item
Preparation for stage 2.

While successful completion of the above two items fulfills some of
the basic
PCRC requirements, namely, we will have two compilers using a single
runtime, at least one more compiler, which uses the same runtime, for 
a language of different nature is desirable. We will investigate the
possibility here. Primary candidate might be C++ or Java. We do this
in the context of constructing a quality compiler/interpreter development 
infrastructure. In particular, we will build a system which incorporate
HPF/Java/C++ front-ends and related tools, together with some
studies/experiments on compilation of Java/C++ based on PCRC runtime. 
Robustness of the system will be emphasized. 

   To achieve this goal, the following work has to be done:

\begin{itemize}
\item[a.] unparser of Java front-end
\item[b.] Java compilation study
\item[c.] Integration of pC++ front-end with HPF/Java front-end
\item[d.] pC++ compilation study
\item[e.] xsageop documentation
\item[f.] system documentation
\item[g.] demos and tests
\end{itemize}

Syracuse will be the main force in the implementation work. Cooperating
Systems will help in testing and documentation. Rochester will help
for item {\tt b}. Indiana will help for item {\tt d}.

\end{enumerate}

\paragraph{Stage 2 (September 1, 1997 to June 30, 1998)}: aiming to fulfill 
all PCRC requirement.
         
The following items are current identified and important 
additions are being negotiated with Indiana for C++.

\begin{enumerate}
\item
Enhancement of PCRC runtime.

\begin{itemize}
\item[a.] a fully operational connection between NPAC library and 
        Maryland library via meta-chaos or other means
\item[b.] design and implement one-sided communication (put/get) in PCRC runtime
\item[c.] provide support for irregularly distributed arrays in PCRC
      runtime (HPF-2-style irregular block distribution formats and/or
      Adlib-style ``non-Cartesian arrays'').
\item[d.] more demo and tests
\item[e.] more documents
\end{itemize}

Syracuse will be the main force in the implementation work. Cooperating
Systems will help in testing and documentation. Maryland will help
for item {\tt a}. 
\item   
A quality public domain compiler/interpreter construction infrastructure.

\begin{itemize}
\item[a.] further polish our multi front-end (HPF, pC++, Java)
\item[b.] a selected set of tools built around our multi front-end 
\end{itemize}

Syracuse will be the main force in the implementation work. Cooperating
Systems will help in testing and documentation.

\item
A releasable HPF compiler.

\begin{itemize}
\item[a.] support for general FORALL constructs
\item[b.] support for INDEPENDENT directive
\item[c.] some support for HPF 2.0 features
\end{itemize}

Syracuse will be the main force in the implementation work. Cooperating
Systems will help in testing and documentation. 

\item
An infrastructure supporting SPMD programming practice. 

This is to be a valuable by-product of this project that we have been
seeing its emergence from our work, namely our runtime may also
be effectively used as an infrastructure to support SPMD programming. 
In particular, application programmers will not have to
use {\tt send()} and {\tt receive()} in their code. Instead, they
use high level facilities provided by the runtime.

Particular work needed for this product includes optimization,
extensive testing on both functionality and portability, and
documentation. Syracuse will be mainly responsible for it.
\end{enumerate}
\end{document}
