\subsubsection{Research Accomplishments}

\paragraph{Support for Machine-Independent Parallel Programming.}
This project focuses on compiler and tool support for exploiting data
parallelism.  Over the past year, the group's efforts have focused
primarily on research and development of advanced optimization
techniques for the d{\small HPF} compiler.  The aim of this work is to
enable {\small HPF} compilers to generate parallel codes that approach
hand-coded performance. A milestone in this work has been achieving
within 15\% of the performance of a hand-coded Message Passing
Interface ({\small MPI}) program for the {\small NAS} {\small BT}
application benchmark through semi-automatic parallelization of a
sequential version of the benchmark with modifications to less than
6\% of the source code. This achievement was possible through the
development of new compiler techniques for interprocedural analysis,
selective replication of computation to reduce communication,
preserving temporal cache locality during parallelization, and a
compiler-based strategy for exploiting wavefront parallelism. We have
also made progress on d{\small HPF} code-generation for shared-memory
systems, and enhanced tool support for tracking complex relationships
between source program fragments and their corresponding generated
code.

\paragraph{Scalable I/O.}
The Scalable I/O Consortium ({\small SIO}) is now coming to the end of
its grant lifetime. Rice's contributions this year have been rather
limited due to the departure of key personnel, but previous work has
culminated in a prototype compiler and work on automatically
generating out-of-core applications. This work will continue, with
funding from the {\small NPACI} partnership. The final report of the
{\small SIO} project will soon be available through its Web site at
{\tt http://www.cacr.caltech.edu/SIO/}.

\paragraph{Performance Tools for HPF.}  We continued to enhance the
SvPablo tools for capturing, displaying, analyzing, and correlating
dynamic performance data with {\small HPF} source code.  We also
extended SvPablo to support analysis of Fortran 77 and Fortran 90
codes, in addition to its previous support for {\small HPF} and C.  In
addition, we integrated SvPablo with the Virtue immersive
visualization system, which supports real-time display of
hierarchical, three-dimensional graphs.  This integration relies on an
extension of SvPablo that generates static procedure call and code
region graphs, together with dynamic performance data on their
traversal.  Virtue then displays the animated call graphs, allowing
interactive ``drill down'' to explore increasing levels of detail.
This work is part of a broader effort to support both real-time
display and interactive analysis of wide-area computations, and
exploration of compiler code transformations. The SvPablo distribution
is available at {\tt
http://vibes.cs.uiuc.edu/Project/SvPablo/SvPabloOverview.htm}.

\paragraph{Irregular Problem Support.} Compiler work at Maryland has
concentrated on extending support to programs that use pointers.
Constructing {\small DEF/USE} chains for statements with pointers
provides compilers with information about the set of statements that
may traverse the pointer links constructed by a particular statement.
One application is traversal-pattern-aware pointer analysis. A
shortcoming of previously proposed pointer analysis techniques is that
they are performed without knowledge of traversal patterns for the
data structures to be constructed.  Typical examples of programs with
conflicting definitions and uses are programs containing cyclic data
structures but having acyclic traversal patterns. With knowledge of
traversal patterns, compilers can perform pointer analysis only on the
set of statements that are specified by traversal patterns.

\paragraph{Data Parallel Library Interoperability.} Runtime library work at
Maryland has focused on developing techniques for transferring data
between distributed data structures owned by different data parallel
runtime libraries. These techniques have been implemented in the
Maryland Meta-Chaos library, which currently is capable of
transferring data between (distributed) arrays that have been created
using {\small HPF}, the Maryland {\small CHAOS} and Multiblock {\small
PARTI} libraries, the Indiana pC++ runtime library, and the {\small
UC} San Diego KeLP library.  The underlying mechanisms for
implementing the Meta-Chaos services have been improved by using the
{\small ISI}/Argonne Globus metacomputing services for resource
allocation and interprocessor communication.

\paragraph{Performance Analysis.}
Syracuse and Maryland are collaborating on a {\small DARPA}-sponsored
project to develop a framework that makes it possible to provide
approximate predictions of the performance that can be achieved by
sophisticated new applications on new high-performance architectures.
A simulation-based framework has been developed and applied to both
loosely-synchronous adaptive applications and data exploration/fusion
applications.  Initial results are quite promising, with validation
experiments showing that the simulators can predict the performance of
application kernels quite accurately, and that we can trade off
accuracy of the predictions for simulation time.

\paragraph{WebFlow: Programming with the Web.}  Our research in this area
addresses needs for high-level programming environments and tools to
support distance computing on heterogeneous distributed commodity
platforms and high-speed networks, spanning across labs and
facilities. More specifically, we are developing WebFlow---a scalable,
high-level, commodity standards-based {\small HPDC} system that
integrates high-level front-ends for visual programming (in Tier 1),
distributed object-based, scalable, reusable Web server and Object
broker Middleware (in Tier 2), and a high-performance backend
implemented using the metacomputing toolkit of {\small GLOBUS} (in
Tier 3).  We demonstrated prototypes of WebFlow at Supercomputing~`97
and at the Alliance~`98 meeting, where we used WebFlow as a high-level
interface to Globus.  The click-drag-and-drop metaphor was used to
create a network of computational modules and to distribute it over a
virtual metacomputer.

\paragraph{Common Runtime Support for Parallel Languages (PCRC).}  Syracuse
has delivered the {\small NPAC} kernel runtime library, a C++ class
library implemented on top of {\small MPI}.  Classes in the library
implement a Distributed Array Descriptor ({\small DAD}) that supports
all {\small HPF} distribution formats and alignment options. The
library provides an extensive set of collective data movement routines
and collective array arithmetic routines.  In collaboration with the
University of Peking and the Harbin Institute of Technology, Syracuse
developed a research {\small HPF} compiler that uses the {\small NPAC}
library to manage array access and communication.  The library is also
being used as a foundation of the HPJava programming environment.

\paragraph{HPJava: A Java Environment for Parallel Programming.}
Syracuse is developing a Java environment for distributed-memory
{\small SPMD} parallel computing called HPJava.  This will eventually
contain Java bindings for distributed-array-oriented libraries,
general {\small MIMD} programming libraries, and a preprocessor for an
extended dialect of Java.  The HPJava language model captures the
{\small HPF} distributed array model in special syntax, but assumes
that the programmer directly calls high-level runtime functions for
communication and array manipulation.  In the last year, the HPJava
language definition has been devised, work on the translator has
commenced, and Java bindings of suitable runtime functions have been
implemented.  The first usable component of the HPJava environment is
the mpiJava binding of {\small MPI}.

\paragraph{Java Grande Forum.}  The Java Grande Forum is a group of academic
and industrial partners aiming to promote Java standards for
communication and compute intensive applications.  The process was
initiated after a series of successful workshops on Java for
Computational Science and Engineering---held in Syracuse, Las Vegas,
and Palo Alto---demon\-str\-ated a broad community interest in the
area.  The stated goal of the Java Grande Forum is to develop
community consensus and recommendations for either changes to Java or
establishment of standards (frameworks) for Grande libraries and
services.  See {\tt
http://www.npac.syr.edu/javagrande/charterindex.html}.

\paragraph{Optimizing Java.}  We have continued our investigation of
compiler optimizations for scientific applications in Java. We have
designed and implemented a set of scientific benchmarks that have
shown that the major performance penalties in using Java for
scientific applications come from the object-oriented design of such
applications, rather than from poor Java execution environments. We
have implemented novel techniques for inlining in our prototype
compiler. These techniques have shown significant performance
improvement on certain Java programs. We are extending their
applicability and effectiveness to a broader range of scientific Java
programs. Our challenge is to develop an {\it almost whole program
optimization} scheme that would use these techniques to automatically
transform an object-oriented program into an optimized,
non-object-oriented version, without sacrificing the Java portability
and security features.
