\documentstyle[psfig,11pt]{article}
%
\setlength{\textheight}{8.75in}
\setlength{\textwidth}{6.25in}
\setlength{\topmargin}{-12pt}
\setlength{\oddsidemargin}{10pt}
\setlength{\evensidemargin}{10pt}
\setlength{\parskip}{.75ex}
%
\title{\bf An Application Perspective on High-Performance Computing
and Communications}

\author{Geoffrey C. Fox \\
\bf Syracuse University \\
Northeast Parallel Architectures Center \\
111 College Place \\
Syracuse, New York  13244 \\
gcf@npac.syr.edu \\
http://www.npac.syr.edu
}

\date{}

\begin{document}
\maketitle

\begin{abstract}
We review possible and probable industrial applications of HPCC
focusing on the software and hardware issues.  Thirty-three separate
categories are illustrated by detailed descriptions of five
areas---computational chemistry; Monte Carlo methods from physics to
economics; manufacturing, and computational fluid dynamics; command and
control, or crisis management; and multimedia services to client
computers and settop boxes.  The hardware varies from tightly-coupled
parallel supercomputers to heterogeneous distributed systems.  The
software models span HPF and data parallelism, to distributed
information systems and object/dataflow parallelism on the Web.

We find that in each case, it is reasonably clear that ``HPCC works in
principle,'' and postulate that this knowledge can be used in a new
generation of software infrastructure based on the WebWindows approach,
and discussed in an accompanying paper.
\end{abstract}

\section{Introduction}

This paper could be viewed as a feasibility study for the success and
viability of HPCC.  We will analyze the majority of large-scale
real-world problems, and find that it is relatively clear that all
``can'' perform well on large-scale parallel and distributed systems.
We put ``can'' in quotes because most applications ``will not,'' in fact,
``run'' well today, and it is quite hard to find the necessary return
on investment for significant industrial investment in the use of HPCC
systems.

We believe that this is not a failure of the concept or the work on
HPCC up to now, but rather that now we know what to do, we must build a
robust HPCC software and systems infrastructure.  In an accompanying
paper \cite{Fox:96c}, we have suggested that the key to HPCC is
implementation of the essential technologies, concepts and capabilities
on top of a pervasive technology, and application base.  In contrast,
today, HPCC is ``top-down'' with a set of beautiful ``niche''
technologies that we can not afford to build, maintain, and integrate into a
robust infrastructure.  Our proposed bottom-up approach is illustrated in
Figure~\ref{fig1.aphp}, which shows both ``high-end''
applications---typically, the so called Grand Challenges
\cite{HPCC:96a}---and the ``integrated'' metaproblems---or national
challenges.  In the analysis that follows, we group possible industrial
uses of parallel computers into 33 broad classes, which include both
Grand and National Challenges.  In the final section, we describe five
particular applications to illustrate the analysis of the relevance of
HPCC in their solution.  These include Grand Challenges, such as Monte
Carlo simulation, computational fluid dynamics, and molecular dynamics
as well as National Challenges, such as multimedia (Web) information
systems, manufacturing, and command and control.  The latter three
areas are ``metaproblems'' (defined precisely in
Section~\ref{sec2.aphp}), which integrate several distributed
applications including component grand challenges, such as vehicle and
process simulation in manufacturing, and weather prediction in command
and control.

\begin{figure}
\centerline{\psfig{figure=fig1.aphp.ps,clip=true,width=5.0in}}
\caption{Integration of Grand Challenges and Pervasive Technologies}
\label{fig1.aphp}
\end{figure}

The bottom-up approach of Figure~\ref{fig1.aphp} is proposed so that
one can build HPCC applications and software on a commercially viable
base \cite{Fox:95k}.  There are two such natural technology
springboards---firstly, shared memory multiprocessors, and secondly,
Web or distributed computing.  The first choice leads to the
interesting distributed shared memory environments, whereas the second
is naturally a message passing environment.  We expect that both these
``viable bases'' should and will be explored.  One important feature
of the broader distributed computing base is that it ``by definition''
includes ``everything,'' and so one can build complete metaproblems in
terms of a single technology framework.

From this point of view, this paper can be considered as a summary of
results and requirements for ``top of the pyramid'' software,
algorithms, and applications that need to be used in designing and
building the bottom-up HPCC technology.

Section~\ref{sec2.aphp} reviews our general study of the structure of
problems, as this is helpful in understanding the appropriate hardware
and software system in each case.

In Section~\ref{sec3.aphp}, we show how the different problem
categories or architectures are addressed by parallel software systems
with different capabilities.  We give illustrative examples, but not
an exhaustive list of existing software systems with these
characteristics.  We consider High Performance Fortran and its
extensions as a data parallel language; message passing systems, such
as those supplied with commercial multicomputers; as well as
approaches to software integration.  In Section~\ref{sec2.aphp}, we
point that our old classification of problems omitted 
{\em metaproblems}---problems built up from several components---each
of which could have its own parallelization issues.
\newpage

Note that our discussion is far more complete in the classic HPCC
(parallel processing, MPP) areas, as we have far more examples, and a
clearer understanding of the programming paradigms have than for the
National (NII) challenges.  However, we indicate where NII (Web)
concepts, such as Java or VRML might fit as our environments evolve
to include these rapidly developing technologies.

In Section~\ref{sec4.aphp}, we combine the previous sections and
describe informally the problem architecture, and possible software and
hardware needs for a selection of ``real-world'' applications.  We have
grouped our discussion into five broad case studies; Monte Carlo
methods; computational chemistry; manufacturing and computational fluid
dynamics; command and control; {\em InfoVISiON}, or the delivery of
multimedia information on the ``digital'' superhighway.  These cover a
range of software issues including, as we discussed, both the grand and
national challenges, and spanning both the bottom and top of the
pyramid.  We conclude with a glossary of some terms used here, and in
the accompanying paper \cite{Fox:96c}.

The applications, and their classification come from a survey of New
York State industry \cite{Fox:92e}, \cite{Fox:94a}, \cite{Fox:94b},
\cite{Fox:94c}, \cite{Fox:94h}, \cite{Fox:94i}, \cite{Mills:93a}.
Tables~1--4 summarizes the industrial opportunities for parallel
computing in the form we will use them.  Some 80 different applications
used in the survey have been broken up into 33 distinct areas.  This is
certainly somewhat arbitrary, and there are many overlaps (and
omissions).  The importance, difficulty of implementation,
and degree of risk also differ from case to case.  However, these
issues will not be discussed here.

Table~1 describes the general guidelines used in organizing Table~4.
Note that we did not directly cover academic areas, and a more complete
list (which included our industrial table) was produced by the
Petaflops meeting \cite{Peta:94a}.  Notice that Tables~1--4 are
organized around the concept of ``information.''  This corresponded to
an early realization from the survey that the major industrial
opportunities for HPCC in New York State were information related.
Thus, for instance, simulation is subtitled ``Information Production''
with say, computational fluid dynamics simulations providing
information to be used in either manufacturing (application 32) or
education (application 33).  It is not directly relevant to this paper,
but the results of this survey caused the ACTION program to refocus its
efforts and evolve into InfoMall \cite{Fox:93c}, \cite{Fox:94f},
\cite{Fox:94h}, \cite{Fox:95b}, \cite{Infourl:95a}, \cite{Mills:94a}.
Here, ``Info'', in InfoMall, refers to the information based
application focus and ``Mall'' to the use of a virtual corporation
(groups of ``storeholders'') to produce the complex integrated
applications enabled by HPCC.

The first column of Table~4 contains the area label and some sample
applications.  There is also a pointer to Section~\ref{sec4.aphp}, if
appropriate.  Algorithmic and other comments are in column two.  The
third and fourth columns describe, respectively, the problem
architecture and an estimate of appropriate parallel software
approach.  The background for these two columns is described in the
following two sections.

\begin{center}
\begin{tabular}{|lp{5.5in}|}
\multicolumn{2}{c}{\bf Table 1: Guidelines used in Developing Categories of 
Industrial and} \\
\multicolumn{2}{c}{\bf Government Applications of HPCC shown in Tables
3--4} \\
% \multicolumn{2}{c}{\bf Industrial and Government Applications of HPCC} \\
% \multicolumn{2}{c}{\bf shown in Tables 3--4} \\
\noalign{\vspace{7pt}}
\hline
$\bullet$& Define information generally to include both CNN headline news
and the insights on QCD gotten from lattice gauge theories.  There are
four broad categories. \\
& \\
$\bullet$&{\bf Information Production} (e.g., Simulation) \\
&$\bullet$ Major concentration of MPPs and Grand Challenges at present \\
& \\
$\bullet$&{\bf Information Analysis} (e.g., Extraction of location of
oil from seismic data, Extraction of customer preferences from purchase
data) \\
&$\bullet$ Growing area of importance and Short term major MPP
opportunity in decision support combined with parallel databases \\
& \\
$\bullet$&{\bf Information Access and Dissemination}---{\em
InfoVision\/} (e.g., Transaction Processing, Video-On-Demand) \\
&$\bullet$ Enabled by National Information Infrastructure.  World Wide
Web, and online services are ``prototype'' \\
&$\bullet$ Very promising medium term market for MPP but need
the NII to be reasonably pervasive before area ``takes off'' \\
&$\bullet$ MPPs used as high performance, high capacity, multi-media
servers \\
& \\
$\bullet$&{\bf Information Integration} \\
& \\
&$\bullet$ Integrates Information Production, Analysis and Access,
e.g., \\
&\ \ \ \ \ -- Decision support in business \\
&\ \ \ \ \ -- Command and Control for Military \\
&\ \ \ \ \ -- Concurrent Engineering and Agile Manufacturing \\
& \\
&$\bullet$ Largest Long Term Market for MPP \\
\hline
\end{tabular}
\end{center}

\begin{center}
\begin{tabular}{|lp{5.0in}|}
\multicolumn2{c}{\bf Table 2: Abbreviations used in Tables 3--4 of
Industrial Applications of HPCC} \\
% \multicolumn2{c}{\bf Table 2: Abbreviations used in Tables 3--4 of} \\
% \multicolumn2{c}{\bf Industrial Applications of HPCC} \\
\noalign{\vspace{7pt}}
\hline
{\bf Adaptive}&Software for Irregular Loosely Synchronous Problems
handled by HPC++, HPF extensions, Message Passing (Table~6) \\
{\bf Asyncsoft}&Parallel Software System for (particular) class of
asynchronous problems (Table~6) \\
{\bf CFD}&Computational Fluid Dynamics \\
{\bf ED}&Event Driven Simulation \\
{\bf FD}&Finite Difference Method \\
{\bf FEM}&Finite Element Method \\
{\bf HPF}&High Performance Fortran \cite{HPF:93a}, \cite{HPFF:95a} \\
{\bf HPF+}&Natural Extensions of HPF \cite{Choudhary:92d},
\cite{HPF:94a}, \cite{HPFapp:95a} \\
{\bf Integration}&Software to integrate components of metaproblems
(Table~6) \\
{\bf MPF}&Fortran plus message passing for loosely synchronous
programming support \\
{\bf PDE}&Partial Differential Equation \\
{\bf TS}&Time Stepped Simulation \\
{\bf VR}&Virtual Reality \\
\hline
\end{tabular}
\end{center}
{\em Note on Language: HPF, MPF use Fortran for illustration,
 one can use parallel Java, C, C++ or any similar extensions of data
parallel or message passing languages} \\

\begin{center}
\begin{tabular}{|p{3.25in}|p{2.25in}|}
\multicolumn{2}{c}{\bf Table 3: Five Categories of Problems} \\
\noalign{\vspace{7pt}}
\hline
\multicolumn1{|c|}{\bf Problem Architecture}&\multicolumn{1}{|c|}{\bf
Overall Software} \\
&\multicolumn{1}{|c|}{\bf Issue} \\
\hline
& \\
{\bf Synchronous\/}: Data Parallel& \\
Tightly coupled and software needs to exploit features of
problem structure to get good performance. Comparatively easy as
different data elements are essentially identical.&Data Parallel \\
\cline{1-1}
\hline
& \\
{\bf Loosely Synchronous\/}: Data Parallel& \\
As above, but data elements, and/or their linkage, are not
identical.  Still parallelizes due to macroscopic time
synchronization.&Data Parallel, but harder to express and implement \\
\hline
& \\
{\bf Asynchronous\/}:& \\
Functional (or data) parallelism that is irregular in space and
time.  Often loosely coupled and so need not worry about optimal
decompositions to minimize communication.  Hard to parallelize
(massively) unless $\ldots$&Difficult Task or object parallel \\
\hline
& \\
{\bf Embarrassingly\/} parallel:& \\
Essentially independent execution of disconnected components
(can involve reductions, e.g., global sums to accumulate information).&
Possible in most software \\
\hline
& \\
{\bf Metaproblems\/}& \\
Asynchronous collection of (loosely) synchronous components
where these programs themselves can be parallelized&Coarse grain 
parallelism---each component data parallel different components typically
integrated by object, dataflow, or task parallel systems. \\
\hline
\end{tabular}
\end{center}

\centerline{\psfig{figure=tab4a.ps,clip=true,width=5.5in}}
\centerline{\psfig{figure=tab4b.ps,clip=true,width=5.5in}}
\centerline{\psfig{figure=tab4c.ps,clip=true,width=5.5in}}
\centerline{\psfig{figure=tab4d.ps,clip=true,width=5.5in}}
\centerline{\psfig{figure=tab4e.ps,clip=true,width=5.5in}}
\centerline{\psfig{figure=tab4f.ps,clip=true,width=5.5in}}
\centerline{\psfig{figure=tab4g.ps,clip=true,width=5.5in}}

\begin{center}
\begin{tabular}{|lp{5.5in}|}
\multicolumn{2}{c}{\bf Table 4: Information Integration Applications 29
to 33} \\
\noalign{\vspace{7pt}}
\hline
$\bullet$&{\bf 29: Real-Time Control Systems} \\
&$\bullet$ Robotics uses Imagery to make decisions (control vehicles) \\
&$\bullet$ Energy management controls power use and generation \\
& \\
$\bullet$&{\bf 30: Electronic Banking} \\
&$\bullet$ Requires Security, Privacy, Authentication, Electronic Cash, etc. \\
& \\
$\bullet$&{\bf 31: Electronic Shopping} \\
& \\
$\bullet$&{\bf 32: Agile Manufacturing---Multidisciplinary Design} \\
&\hspace{2em} {\bf and Concurrent Engineering} (Sec. 4.4) \\
&$\bullet$ Combines CAD with Applications 1 to 3 \\
&$\bullet$ Requires major changes to Manufacturing Infrastructure and 
Approach \\
& \\
$\bullet$&{\bf 33: Education} (Sec. 4.5) \\
&$\bullet$ Many commonalities with Application 25 \\
&$\bullet$ InfoMall Living Schoolbook---6 Schools on ATM network
linked to HPCC InfoVision Servers at NPAC \cite{Mills:95a} \\
\hline
\end{tabular}
\end{center}

This paper is not intended to advocate a particular parallel software
environment or language.  Rather, we want to describe the broad
capabilities of, and give examples of the parallel programming paradigm
needed for the applications of Table~4.  We believe that the
programming functionality needed by a particular application is broadly
determined by the problem architecture described in the following
section.  In discussing software needs, we do not discuss all the
components of the parallel software environment, but just those relevant
for expressing problems.

For this reason, we use broad software classifications using, for
instance, MPF (Fortran plus message passing) as typical of all similar
explicit messaging systems---one could substitute here C plus message
passing, or Fortran~M programming environments.  Again, PVM, MPI, or
any such message passing system could be used without changing the
significance of the tables.  High Performance Fortran is used as a
typical data parallel language, although this has an evolving
definition and similar C++, or even Java, environments could well be
more attractive, and can be substituted in the table.

\section{Problem Architectures}
\label{sec2.aphp}

We have described our classification of problem architectures several
times before, but here we just summarize it.

This classification \cite{Angus:90a}, \cite{Denning:90a},
[Fox:88b;90p;91g;94a], \nocite{Fox:88b} \nocite{Fox:90p}
\nocite{Fox:91g} \nocite{Fox:94a} was deduced from our experience at
Caltech combined with a literature survey that was reasonably complete
up to the middle of 1989.  At Caltech, we developed some 50
applications on parallel machines, 25 of which led to publications in
the scientific literature, describing the results of simulations
performed on our parallel computers \cite{Fox:87d} \cite{Fox:88a},
\cite{Fox:88oo}, \cite{Fox:89n}.  Our Caltech work was mainly on the
hypercube, but the total of 300 references used in original
classification covered work on the Butterfly, transputers, the SIMD
Connection Machine, and DAP.  We originally identified three temporal
structures and one especially important (as it was so simple) spatial
structure, which are the first four entries in Table~3.  Chapter~3 of
\cite{Fox:94a} describes a ``complex systems'' approach to
computation and introduces the spatial and temporal structure of
problems and computers.  We studied software as a mapping
(Figure~\ref{fig2.aphp}) of problems to computers with the software
structure determined by the structure (architecture) of both the
individual complex systems---computers and problems---and their
interrelation.  In Figure~\ref{fig3.aphp}, we summarize issues in the
spatial-temporal plane. ``Space'' here refers to data (problem) or
nodes and their linkage (computer).  ``Time'' is iteration number and
simulation time (problem) or counts clock cycles (computer).

\begin{figure}
\centerline{\psfig{figure=fig1.134c.ps,clip=true,width=5.0in}}
\caption{Computation and Simulation as a Series of Maps}
\label{fig2.aphp}
\end{figure}

\begin{figure}
\centerline{\psfig{figure=fig2.hetero.ps,width=3.75in}}
\caption{Issues Affecting Relation of Machine, Problem, and Software
Architecture}
\label{fig3.aphp}
\end{figure}

The three general temporal structures are called synchronous, loosely
synchronous, and asynchronous.  The temporal structure of a problem is
analogous to the hardware classification into SIMD and MIMD.  Further
detail is contained in the spatial structure or computational graph of
Figure~\ref{fig4.aphp}a describing the problem at a given instant of
simulation time \cite{Fox:88tt}.  This is important in determining the
performance, as shown in Chapter~3 of \cite{Fox:94a} of an
implementation, but it does not affect the broad software issues
discussed here.  In Table~3, we only single out one special spatial
structure, ``embarrassingly parallel,'' where there is little or no
connection between the individual parallel program components.  For
embarrassingly parallel problems, illustrated in
Figure~\ref{fig5.aphp}, the synchronization (both software and
hardware) issues are greatly simplified.

\begin{figure}
\centerline{\psfig{figure=fig6.methods.ps,width=4.5in}}
\caption{(a) Synchronous, Loosely Synchronous (Static), and (b)
Asynchronous (Dynamic) Complex Systems with their Space-Time Structure}
\label{fig4.aphp}
\end{figure}

\begin{figure}
\centerline{\psfig{figure=fig1.epprob.ps,width=4.0in}}
\begin{center}
Example\@:  Divide large database among processors and independently
search each portion of database to answer query.
\end{center}
\caption{Embarrassingly Parallel Problem Class}
\label{fig5.aphp}
\end{figure}

{\em Synchronous\/} problems are data parallel in the language of
Hillis \cite{Hillis:87a} with the restriction that the time dependence
of each data point is governed by the same algorithm.  Both
algorithmically and in the natural SIMD implementation, the problem is
synchronized microscopically at each computer clock cycle.  Such
problems are particularly common in academic applications as they
naturally arise in any description of some world in terms of identical
fundamental units.  This is illustrated in Figure~\ref{fig6.aphp} by
quantum chromodynamics (QCD) simulations of the fundamental elementary
particles that involve a set of gluon and quark fields on a regular
four-dimensional lattice.  These computations form one of the largest
use of supercomputer time in academic computing.

\begin{figure}
\begin{quotation}
\begin{center}
{\bf EXAMPLE OF SYNCHRONOUS PROBLEMS}
\end{center}

\noindent{\em For example:}
\begin{center}
Microscopic Description of Fundamental Interactions \\
--- In Particular, QCD
\end{center}
\vspace*{10pt}

\centerline{\hbox{
\vspace*{0.5in}
\psfig{figure=fig1.issues.ps,width=1.75in}}}

\begin{itemize}
\item Computational structure (almost) identical for all elements in
the data domain

\item Parallelize by regular partition of data domain

\item Run well on SIMD machines

\item Message Passing or High Performance Fortran implementation on
MIMD machines
\end{itemize}
\end{quotation}
\caption{The Synchronous Problem Class}
\label{fig6.aphp}
\end{figure}

{\em Loosely synchronous\/} problems are also typically data parallel,
but now we allow different data points to be evolved with distinct
algorithms.  Such problems appear whenever one describes the world
macroscopically in terms of the interactions between irregular
inhomogeneous objects evolved in a time synchronized fashion.  Typical
examples, as in Figure~\ref{fig7.aphp}, are computer or biological
circuit simulations where different components or neurons are linked
irregularly and modeled differently.  Time driven simulations and
iterative procedures are not synchronized at each microscopic computer
clock cycle, but rather only macroscopically ``every now and then'' at
the end of an iteration or a simulation time step.

\begin{figure}
\centerline{\psfig{figure=fig7.aphp.ps,height=4.5in}}
\caption{The Loosely Synchronous Problem Class}
\label{fig7.aphp}
\end{figure}

Loosely synchronous problems are spatially irregular, but temporally
regular.  The final {\em asynchronous\/} class is irregular in space
and time, as in Figure~\ref{fig4.aphp}b.  A good example is an event
driven simulation, illustrated in Figure~\ref{fig8.aphp}, that can be
used to describe the irregular circuits we discussed above, but now the
event paradigm replaces the regular time stepped simulation.  Other
examples include computer chess \cite{Felten:88i} and transaction
analysis.  Asynchronous problems are hard to parallelize and some may
not run well on massively parallel machines. They require sophisticated
software and hardware support to properly synchronize the nodes of the
parallel machine, as is illustrated by time warp mechanism
\cite{Wieland:89a}.

\begin{figure}
\begin{center}
\bf ASYNCHRONOUS PROBLEMS \\
\end{center}
\vspace{10pt}
For example: \\
The world looked at macroscopically in terms of interactions between
irregular inhomogeneous objects evolved as an event-driven simulation

\vspace{15pt}
\centerline{\psfig{figure=fig1.hetero.ps,width=4.5in}}

\begin{itemize}
\item Parallelize by ``data parallelism'' over space of events but no
automatic algorithmic synchronization
\item Need sophisticated software built on top of message passing
between events to ensure synchronization
\item Speedup very problem-dependent
\item MIMD architectures essential
\item See SIMNET or DSI with very loosely coupled distributed
event-driven simulation
\end{itemize}
\caption{The Asynchronous Problem Class}
\label{fig8.aphp}
\end{figure}

Both synchronous and loosely synchronous problems parallelize on
systems with many nodes.  The algorithm naturally synchronizes the
parallel components of the problem without any of the complex software
or hardware synchronization mentioned above for event driven
simulations.  In the original survey, 90\% of the surveyed applications
fell into the classes that parallelize well.  This includes 14\% from
the embarrassingly parallel classes, and roughly equal (38\% each)
amounts from synchronous or loosely synchronous class.  It is
interesting that massively parallel distributed memory MIMD machines
that have an asynchronous hardware architecture are perhaps most
relevant for loosely synchronous scientific problems.

We have looked at many more applications since the detailed survey in
\cite{Fox:88b}, and the general picture described above remains valid.
Industrial applications have less synchronous and more loosely
synchronous problems than academic problems.  We have recently
recognized that many complicated problems are mixtures of the basic
classifications.  The first major example with which I was involved was
a battle management simulation implemented by my collaborators at JPL
\cite{Fox:94a}, \cite{Meier:89a}.  This is formally asynchronous with
temporally and spatially irregular interconnections between various
modules, such as sensors for control platforms and input/output tasks.
However, each module uses a loosely synchronous algorithm, such as the
multi-target Kalman filter \cite{Gottschalk:90b} or the target-weapon
pairing system.  Thus, the whole metaproblem consists of a few ($\sim
10$--50) large grain asynchronous objects, each of which is a data
parallel synchronous or loosely synchronous algorithm.  This type of
asynchronous problem can be implemented in a scaling fashion on
massively parallel machines.  We call this a metaproblem or
asynchronous combination of several synchronous or loosely synchronous
problems.  A similar example of this asynchronous or embarrassingly
synchronous problem class is machine vision and signal processing,
where one finds an asynchronous collection of data parallel modules to
perform various image processing tasks, such as stereo matching and
edge detection.  Figure~\ref{fig9.aphp} illustrates another example
where we outline an approach to designing a new airframe that involves
aerodynamics, structures, radar signature, and the optimization
discussed later in Section~\ref{cfd}.  This figure also points out the
interesting analogy between heterogeneous metaproblems, and a
heterogeneous computer network.  Section~\ref{cfd} and
Figure~\ref{fig12.aphp} gives a more concrete example of such a
metaproblem, which as usual, involves both database (I/O), and
computational subproblems.

\begin{figure}
\centerline{\psfig{figure=fig8.134c.ps,clip=true,width=4.5in}}
\caption{The Mapping of Heterogeneous Metaproblems onto Heterogeneous
Metacomputer Systems}
\label{fig9.aphp}
\end{figure}

In the above cases, the asynchronous components of the problems
were large grain modules with modest parallelism.  This can be
contrasted with Otto and Felten's MIMD computer chess algorithm, where
the asynchronous evaluation of the pruned tree is ``massively
parallel'' \cite{Felten:88i}.  Here, one can break the problem up into
many loosely coupled but asynchronous parallel components, which give
excellent and scalable parallel performance.  Each asynchronous task
is now a synchronous or loosely synchronous modestly parallel
evaluation of a given chess position.

The World Wide Web is an enormous metasystem with many task parallel
subproblems (Web servers handling many connections). Examples include 
data or task parallel ``applets'' handling computationally
intense client computing for financial modeling, or a VRML
rendering job.  Data parallelism occurs in large data mining
sub-applications on servers with links to Java or VRML clients, that
just handle visualization and interpretation modules.

There were a few examples of metaproblems in our
original survey, but a major part of Table~4, from our New York State
activity, is the Information Integration classification.  This class
includes manufacturing and the applications 25--33, all examples of
metaproblems.  As stated boldly in Table~1, this class is the most
important long-term area for HPCC, and is discussed in
Sections~\ref{cfd} and \ref{CandC}.  Further, as in battle management
case, many problems that formerly appear asynchronous and were
classified in this way in our original survey, are in fact
metaproblems. Thus, the parallelism does not come from the difficult
(impossible?) asynchronous structure, but the synchronous or loosely
synchronous components buried inside the asynchronous shell.  Thus, we
believe metaproblems and their software support to be very important.

\section{Some Software and Machine Issues}
\label{sec3.aphp}

Naturally parallel implementations work ``best'' if the machine
architecture is ``similar'' to that of the problem.  This is
summarized in Table~5 where to be precise, success requires that the
machine architecture ``contains'' (is a superset of) the problem
architecture.  Thus, both SIMD and MIMD machines express synchronous
problems, but SIMD machines are typically unsuitable for loosely
synchronous problems.

\begin{center}
\begin{tabular}{|ll|}
\multicolumn{2}{c}{\bf Table 5: What is the ``Correct'' Machine
Architecture} \\
\multicolumn{2}{c}{\bf for each Problem Class?} \\
\noalign{\vspace{7pt}}
\hline
\multicolumn{1}{|c}{\em Problem Class}&\multicolumn{1}{c|}{\em Machine} \\
\hline
& \\
{\bf Synchronous}&SIMD, MIMD \\
& \\
{\bf Loosely Synchronous}&MIMD, maybe SIMD \\
& \\
{\bf Asynchronous}&MIMD, but may not perform well \\
&without special hardware features \\
& \\
{\bf Compound} & Heterogeneous network \\
{\bf (Metaproblems)}&(including World Wide Web) \\
& \\
{\bf Embarrassingly Parallel}&Network of workstations \\
&MIMD, World Wide Web, \\
&sometimes SIMD \\
\hline
\end{tabular}
\end{center}

Software systems need to be designed so that they can express problems
well, and be targeted to relevant machines.  Software should not be
designed for a particular machine model---it expresses problem and not
machine characteristics.

We have described those issues at length in [Fox:90p;91g;94a], and
\nocite{Fox:90p} \nocite{Fox:91g} \nocite{Fox:94a} here we present
only a simple table (Table~6) mapping the five problem architectures into
possible software environments.  This is presented in a different
fashion for HPF and HPC++ in Figure~\ref{fig10.aphp} and Table~7, which
also points out the distinct runtime support needed for each problem
class.  One always has a tradeoff between performance and flexibility.
Systems listed under ``asynchronous'' in Table~6 can typically also be
used for synchronous and loosely synchronous problems.  As shown in
Figure~\ref{fig11.aphp}, the ``asynchronous'' software used on loosely
synchronous problems will probably provide greater flexibility, but
lower performance than software systems explicitly designed for this
problem class.

\begin{center}
\begin{tabular}{|lp{5.25in}|}
\multicolumn{2}{c}{\bf Table 6: Candidate Software Paradigms for Each
Problem Architectures} \\
\noalign{\vspace{7pt}}
\hline
$\bullet$ & {\bf Synchronous}\@:  High Performance Fortran (HPF)
\cite{Foster:95a}, \cite{HPFCSep:95a}, \cite{Koelbel:94a}; Fortran~77D
\cite{Bozkus:93a}, \cite{Fox:91e}, \cite{Hiranandani:92c}; Vienna
Fortran \cite{Chapman:92b}; C* [Hatcher:91a;91b]; \nocite{Hatcher:91a}
\nocite{Hatcher:91b} Crystal \cite{Chen:88b}; APL; Fortran for SIMD
parallel computers \\
& \\
$\bullet$ & {\bf Loosely Synchronous}\@:  Extensions of the above,
especially HPF \cite{Chapman:94b}, \cite{Choudhary:92d},
\cite{HPF:94a}; and parallel HPC++ \cite{Bodin:91a}, \cite{Chandy:93a},
\cite{Grimshaw:93b}, \cite{Lemke:92a}; Fortran or C plus message
passing \cite{Fox:91m}, \cite{McBryan:94a} \\
& \\
$\bullet$ & {\bf Asynchronous}\@:  Linda [Factor:90a;90b], \nocite{Factor:90a} 
\nocite{Factor:90b} \cite{Gelertner:89a}; CC++ \cite{Chandy:93a}; Time Warp
\cite{Wieland:89a}; PCN \cite{Chandy:90a}; WebWork \cite{Fox:95a},
including Java based distributed simulation \\
& \\
$\bullet$ & {\bf Compound Metaproblems}\@:  AVS [Mills:92a;92b],
\nocite{Mills:92a} \nocite{Mills:92b} \cite{Cheng:93a}; PCN, Linda (or
Trellis built on Linda); Webwork (CGI, Java,and Javascript
Integration) \cite{Fox:96c}; Fortran-M \cite{Foster:95a}.
Generally, extensions of ADA, Fortran, C, or C++ controlling modules
written in synchronous or loosely synchronous approach \\
& \\
$\bullet$ & {\bf Embarrassingly Parallel}\@: Several approaches work? \\
& $\bullet$ PCN, Linda, WebWork, PVM \cite{Sunderam:90a}, Network Express
\cite{Parasoft:88a}, ISIS [Birman:87a;87b;91a] \nocite{Birman:87a}
\nocite{Birman:87b} \nocite{Birman:91a} \\
\hline
\end{tabular}
\end{center}

\begin{center}
\begin{tabular}{|lp{5.0in}|}
\multicolumn{2}{c}{\bf Table 7: Imprecise Mapping of Problem Classes
into Runtime} \\
\multicolumn{2}{c}{\bf and Language Terms} \\
\noalign{\vspace{7pt}}
\hline
$\bullet$&{\bf STATIC Runtime} \\
&$\bullet$ Synchronous and Embarrassingly Parallel
Problems---current HPF \\
& \\
$\bullet$&{\bf ADAPTIVE Runtime} \\
&$\bullet$ Loosely Synchronous but not Synchronous---future
capabilities of High Performance Fortran (HPF+) but can be supported
well in message passing \\
& \\
$\bullet$&{\bf ASYNCHRONOUS Runtime} \\
&$\bullet$ Asynchronous Problems \\
&$\bullet$ Support rollback, as in time warp \\
&$\bullet$ Java thread based systems very promising \\
& \\
$\bullet$&{\bf INTEGRATION Runtime and Programming Environments} \\
&$\bullet$ Metaproblems \\
&$\bullet$ AVS works well, but such integration capability also can be
integrated into languages such as HPC++, Fortran-M \\
&$\bullet$ Web Technology very important---JavaScript integrates
frames in a Netscape Metawindow \\
\hline
\end{tabular}
\end{center}

\begin{figure}
\centerline{\psfig{figure=fig10.aphp.ps,clip=true,width=4.5in}}
\caption{General Applicability of HPF, HPF+, HPC++ Classified by
Problem Architecture and type of Runtime Support needed}
\label{fig10.aphp}
\end{figure}

\begin{figure}
\centerline{\psfig{figure=fig4.meta.ps,clip=true,width=4.5in}}
\caption{Mapping of Asynchronous, Loosely Synchronous, and Synchronous
Levels or Components of Machine, Software and Problem.  Each is
pictured hierarchically with the asynchronous level at the top and
synchronous components at lowest level.  Any one of the components may
be absent.}
\label{fig11.aphp}
\end{figure}

Loosely synchronous problems are in some sense the hardest as they
have difficult irregularities which must be expressed with high
efficiency by the underlying compiler and runtime systems.  We, and
others, have discussed this at length, both in general
[Choudhary:92d;92e], \cite{Fox:90p}, [Goil:94a;95a], 
\nocite{Choudhary:92d} \nocite{Choudhary:92e} \nocite{Goil:94a}
\nocite{Goil:95a}, and in case of High Performance Fortran
\cite{Bogucz:94a}, \cite{Chapman:94b}, \cite{Cheng:94e}, [Choudhary:92g;94c],
\nocite{Choudhary:92g} \nocite{Choudhary:94c} \cite{Fox:94g},
[Hawick:95a;95c], \cite{HPF:94a}, \hfill\break \cite{HPFapp:95a},
\cite{Joubert:95a}, \cite{Muller:95a}, \cite{Robinson:95a},
\cite{Sturler:95a}.  \nocite{Hawick:95a} \nocite{Hawick:95c}

Note that Figure~\ref{fig10.aphp} refers to ``HPF+''---this is some
extension, called officially HPF2 (and later 3 perhaps) of HPF
\cite{HPF:93a}, \cite{HPFF:95a} to fill gaps in the original language.  The
current HPF1 handles most synchronous and embarrassingly applications,
but requires extension to handle the adaptive irregular data structures
typical of loosely synchronous problems.

We now quantify these remarks with three case studies, which will link
the material of Sections~\ref{sec2.aphp} and \ref{sec3.aphp}. 

\section{General HPCC Hardware and Software Issues for Five Case
Studies}
\label{sec4.aphp}

We now illustrate the different machine, problem, and software issues
with five case studies.  These are each broad application areas where
there is no one approach.  Rather, several very distinct application
subclasses are present in each case for which different programming
paradigms and machine architectures are appropriate.  We will move
from compute dominated to communication/data intensive cases.

\subsection{Monte Carlo Methods (Applications 4, 6, 7, 9, 11)}

We have already mentioned in Section~\ref{sec2.aphp}, Quantum
Chromodynamics Simulations as a classic example of large scale Monte
Carlo simulations suitable for parallel machines.  As described in
Chapter~4 of \cite{Fox:94a}, this application is straightforward to
parallelize and very suitable for HPF as the basic data structure is
an array.  The array represents a regular structure in space time as
seen in the simplest finite different problems.  The Monte Carlo occurs
at each grid point and is typically local (nearest neighbor) so that
the overall problem architecture is just like that of a PDE.  This
specific computation is from an academic field, but is typical in
structure of some practical material science problems.  Further, just
as many PDEs have irregular data structures, the same is true of many
Monte Carlos. QCD is typical of simulations of crystalline substances
with a regular array of atoms.  However, many substances---in
particular gases and liquids---have irregular particle distributions
and many of issues discussed briefly in Section~\ref{cfd} for finite
element methods.  As described in Chapter~14 of \cite{Fox:94a}, there
is a subtle point that distinguishes Monte Carlo and PDE algorithms as
one cannot simultaneously update in Monte Carlo, sites with overlapping
neighbors.  This complicates the loosely synchronous structure and can
make problem architecture look like that of asynchronous event driven
simulations---here events are individual Monte Carlo updates.
``Detailed balance'' requires that such events be sequentially (if
arbitrarily) ordered.  In the example of \cite{Johnson:86c} described
in \cite{Fox:94a}, a clever implementation gave good parallel
performance.

Monte Carlo methods can be implemented quite differently---above we
decomposed the underlying physical data.  One can also use ``data
parallelism'' on the random number set used in the simulation.  This
is not possible for QCD for two reasons.  Firstly, the physical
dataset is so large it would not fit in the memory of a single
node---we need to decompose the physical dataset just to get enough
total memory.  More importantly, one can run QCD with several
different starting points.  However, all Monte Carlos---using
importance sampling of the Metropolis type employed by QCD---have a
``thermalization stage'' where one must get ``into equilibrium''
before the sampling is useful.  Thermalization is very time consuming
for QCD and makes multiple starting points of limited value.  However,
there are many cases where this is not true, and as shown in Chapter~7
of \cite{Fox:94a}, one can get an embarrassing parallel architecture
for Monte Carlo problems.  Each instance of the problem has the full
physical dataset, but can be run independently with different random
number streams.  Like many such embarrassingly parallel cases, the
different instances do need to accumulate their data---in this case,
Monte Carlo averages.  One important examples of this class of
application is Quantum Monte Carlo used in many ab initio chemistry
problems \cite{Kalos:85a}.

Yet, a different set of issues comes with a class of Monte Carlo
problems which are termed ``clustered.''  In most physical system
Monte Carlos, one updates a single ``entity'' (grid point or particle)
at a time.  This is very ineffective when there is substantial
correlation between neighboring points.  A simple example comes from
ferromagnetic materials where domains form where spins are locked in
the same direction over large regions.,  Clustering algorithms are
quite hard to find for sequential systems, and their parallelization
is challenging and very different from the earlier examples. As
discussed in Section~12.6 of \cite{Fox:94a}, the algorithm is similar
to that used in region finding in image processing [Copty:93a;94a;95a].
\nocite{Copty:93a} \nocite{Copty:94a} \nocite{Copty:95a}  Parallelism
requires consideration (as in domain decomposition for PDEs) of inter
and intra region issues.

Makivic \cite{Makivic:95a} has described the implementation of
sophisticated path integral Monte Carlos for economic modeling, in
particular for option pricing.  He describes an HPF implementation,
but one would probably use simple parallel C++ (or even Java) in a
production implementation, as parallelization is rather
straightforward with an array holding the different Monte Carlo paths
linked by global reduction operations.  This field shows a
generalization to metaproblems when pricing a full portfolio
consisting of many separate financial instruments.

\subsection{Computational Chemistry and Electromagnetics\hfill\break 
(Applications 3, 7, and 8)}

Many chemistry problems are formulated in terms of states of a
chemical system, which can be labelled by an index corresponding to
species, choice of wave function, or internal excitation (see
Chapter~8 of \cite{Fox:94a}).  The calculation of energy levels,
potential or transition probability can often be related to a matrix
$M_{ij}$ whose rows and columns are just the possible system states.
$M$ is often an approximation to the Hamiltonian of the system or it
could represent overlap between the states.  There are two key stages
in such problems
\begin{description}
\item{a)} firstly, calculate the matrix elements $M_{ij}$
\item{b)} secondly, perform one or more of a set of matrix operations
\end{description}
\begin{itemize}
\begin{itemize}
\item Matrix Multiplication as in change of basis
\item Matrix Eigenvalue determination as in energy level computations
\item Matrix Equation solution as in solving multichannel scattering
problems
\end{itemize}
\end{itemize}

This structure has been elegantly exploited within the ``Global
Array'' programming model built at Pacific Northwest Laboratory
\cite{Nicplocha:94a} with a set of tools (libraries) designed for this
class of computational chemistry problem.

These two steps have very different characteristics.  The matrix
element computations a), is of the embarrassingly parallel case as
each $M_{ij}$ can essentially be calculated independently even though
subexpressions may be shared between two or more distinct $M_{ij}$.
Each $M_{ij}$ is a multi-dimensional integral with the computation
depending on the details of the states $i$ and $j$.  Thus, this
computation is very time consuming and is not suited for SIMD
machines.  The natural parallel algorithm associates sets of $(i,j)$
with each node of a parallel computer.  There are some relatively
straightforward load balancing issues and essentially no internode
communication.  Thus, a MIMD cluster of workstations with modest
networking is sufficient for this step a).  The final matrix
manipulations have quite a different character.  These synchronous
problem components are suitable for SIMD machine and often required
substantial communication so that a workstation cluster will not be
effective.  Matrix multiplication could be exception as it is
insensitive to latency and communication bandwidth for large matrices
and so suitable for workstation clusters.

One of the standard approaches to computational electromagnetics (CEM)
is the method of moments [Harrington:61a;67a;68a], \cite{Jordon:69a}.
\nocite{Harrington:61a} \nocite{Harrington:67a} \nocite{Harrington:68a}
This is a spectral method, which rather than solving the underlying
partial differential equation (Maxwell's), expands the desired
solution in a set of ``moments''.  This leads to a similar situation
to that described above for computational chemistry where $i$ and $j$
label moments for CEM and not the chemical state [Cheng:94a;94c].
\nocite{Cheng:94a} \nocite{Cheng:94c} Note that in both cases, the
matrix $M$ is usually treated as full \cite{Cheng:94c}, and is
quite different from the familiar sparse matrices gotten from
discretizing a partial differential equation.  We note in passing that
such spatial discretization is a quite viable approach to CEM and leads
to a totally different computational problem architecture from the
spectral moment formulation.

HPF can handle both stages of the matrix based CEM or chemistry
problems \cite{Robinson:95a}.  The matrix solution stage exploits
fully the Fortran~90 array manipulation and clearly requires good
compiler support for matrix and vector manipulation primitives.  NPAC's
experience with a production CEM code PARAMOM from the Syracuse
Research Corporation is illuminating \cite{Cheng:94c}.  Both stages
could be implemented  on IBM SP-2 with specialized Fortran code for the
matrix element generation joined to SCALAPACK based matrix solution
\cite{Choi:92c}.  However, the CM-5 implementation was not so simple.
The CMSSL library provided exceptional matrix solution with good use
being made of the CM-5's vector nodes.  However, the matrix element
computation was not so straightforward.  Performance on the CM-5 nodes
was poor and required conversion of the original Fortran~77 to
Fortran~90 to both exploit the vector nodes and link to CMSSL.
However, whereas the Fortran~90 notation was very suitable for matrix
manipulation, it is quite irrelevant for the matrix element generation
stage---as already explained, this exploits the {\tt INDEPENDENT DO\/}
and not the array notation for explicit parallelism.  Thus, we split
the PARAMOM code into a metaproblem with two sub-problems corresponding
to the two stages discussed above.  Now we implemented each stage on the
most appropriate architecture.  The ``embarrassingly parallel''
Fortran~77 matrix element generation stage was run on a network of
workstations, the equation solution stage used the optimized libraries
on the CM-5 or SP-2.  The linkage of these stages used AVS, but one
could alternatively use many other coordination software approaches.
We expect to test our use of World Wide Web technology {\em WebWork\/}
\cite{Fox:95a} on this example.

This simple example illustrates three problem classes: embarrassingly
parallel, synchronous and metaproblems, and associated machine and
software architecture.  There is an interesting software engineering
issue. Typically, one would develop a single Fortran program for such
a computational chemistry or electromagnetics problem.  However,
better is separate modules---in this case, one for each of two
stages---for each part of problem needing different parallel computer
treatment.  In this way, we see the breakup of metaproblems into
components, and use of systems such as AVS as helpful software
engineering strategies [Cheng:92a;94d]. \nocite{Cheng:92a}
\nocite{Cheng:94d}  We have successfully used such an approach to
produce an effective parallel version of the public domain molecular
orbital chemistry code MOPAC \cite{MOPAC:95a}.

Not all chemistry computations have this structure.  For instance,
there is a set of applications such as AMBER and CHARMM that are based
on molecular dynamics simulations, as described in Chapter~16 of
\cite{Fox:94a}, \cite{Ranka:92a}.  These are typically loosely
synchronous problems with each particle linked to a dynamic set of
``nearest neighbors'' combined with long-range nonbonded force
computations.  The latter can either use the synchronous $O(N^2_{\rm
particle})$ algorithm or the faster, but complex loosely synchronous
fast multiple $O(N_{\rm particle})$ or $O(N_{\rm particle} \log N_{\rm
particle})$ approaches \cite{Barnes:86a}, \cite{Edelsohn:91b},
\cite{Goil:94a}, \cite{Goil:95a}, \cite{Greengard:87b},
\cite{Salmon:90a}, \cite{Singh:93a}, \cite{Sunderam:93a},
\cite{Warren:92b}, \cite{Warren:93a}.

\subsection{Computational Fluid Dynamics and Manufacturing
(Applications 1, 2, 3, 4, and 32)}
\label{cfd}

CFD (Computational Fluid Dynamics) has been a major motivator for much
algorithm and software work in HPCC, and indeed extensions of HPF have
largely been based on CFD (or similar partial differential equation
based applications) and molecular dynamics \cite{Bogucz:94a}, 
[Choudhary:92d;94c], \cite{Dincer:95b}, \nocite{Choudhary:92d}
\nocite{Choudhary:94c} \nocite{Goil:94a} \nocite{Goil:95a}
[Goil:94a;95a], [Hawick:95a;95b], \nocite{Hawick:95a}
\nocite{Hawick:95b}, \cite{HPF:94a}.  Partial differential equations
can be quite straightforward on parallel machines if one uses regular
grids, such as those coming from the simplest finite difference
equations.  However, modern numerical methods use either finite
elements or a refinement strategy for finite elements, which gives rise
to irregular meshes.  Approaches, such as domain decomposition and
multigrid, also give use to complex data structures.  From a Fortran
programmer's point of view, simple finite differences can be well
described by Fortran array data structures.  Corresponding
parallelization of such applications is well suited to the current HPF
language, which is centered in decomposing arrays.  All the more
advanced partial differential equation schemes naturally need somewhat
more sophisticated (than simple arrays) data structures, including
arrays of pointers, linked lists, nested arrays, and complex trees.
The latter are also seen in fast multipole particle dynamics problems,
as well as fully adaptive PDE's \cite{Edelsohn:91b}.  Some excellent
methods, such as the Berger-Oliger adaptive mesh refinement
\cite{Berger:84a} require modest HPF extensions as we have shown in our
Grand Challenge work on colliding black holes \cite{Haupt:95a}.
However, as Saltz's group has shown in a set of pioneering projects
\cite{HPF:94a}, many important PDE methods require nontrivial HPF
language extensions, as well as sophisticated runtime support, such as
the PARTI \cite{Saltz:91b} and CHAOS systems \cite{Edjali:95a},
\cite{Hwang:94a}, [Ponnusamy:93c;94b]. \nocite{Ponnusamy:93c}
\nocite{Ponnusamy:94b}  The needed language support can be thought of
as expressing the problem architecture (computational graph as in
Figure~\ref{fig4.aphp}(a), which is only implicitly defined by the
standard (Fortran) code.  Correctly written, this vanilla Fortran
implies all needed information for efficient parallelism.  However,
this information is realized in terms of the values of pointers and
cannot be recognized at compile time for either static or compiler
generated dynamic runtime parallelism.  This fundamental problem is of
course why Fortran is a more successful parallel language than C as
latter naturally uses pointer constructs that obscure the problem
architecture even more.  The runtime support for PDE's must cope with
irregular and hierarchical meshes and provide the dynamic alignment
decomposition and communications optimization that HPF provides for
arrays.

We now move from CFD to manufacturing, or rather design and
manufacturing, which metaproblem includes CFD as a subarea.
Manufacturing is particularly interesting, as it needs all aspects of
the HPCC initiative from powerful computational engines, huge databases
to pervasive secure high-performance networks.  Now we use the word
``manufacturing'' in its broadest sense to include design, the actual
processes that build the product, and the full life cycle maintenance.
HPCC has a natural high profile role in implementing the popular
concept of agile manufacturing, which supposes the model where virtual
corporations generate ``products-on-demand.''  The NII is used to link
collaborating organizations.  HPCC is needed to support instant design
(or more accurately redesign or customization) and sophisticated
visualization and virtual reality ``test drives'' for the customer.  At
the corporate infrastructure level, concurrent engineering involves
integration of the different component disciplines---such as design,
manufacturing, and product life cycle support---involved in
engineering.  These general ideas are tested severely when they are
applied to the design and manufacturing of complex systems such as
automobiles, aircraft, and space vehicles such as shuttles.  Both the
complexity of these products, and in some sense the maturity of their
design, places special constraints and challenges on HPCC.

High-performance computing is important in all aspects of the design of
a new aircraft.  However, it is worth noting that it has been estimated
that less than 5\% of the initial costs of the Boeing~777 aircraft were
incurred in computational fluid dynamics (CFD) airflow
simulations---the ``classic'' Grand Challenge in this field described
above.  On the other hand, over 50\% of these sunk costs could be
attributed to overall systems issues.  Thus, it is useful but not
sufficient to study parallel computing for large scale CFD.  This is
``Amdahl's law for practical HPCC.''  If only 5\% of a problem is
parallelized, one can at best speed up and impact one's
goals---affordability, time to market---by this small amount.  HPCC,
thus, must be fully integrated into the entire engineering enterprise
to be effective.  Very roughly, we can view the ratios of 5\% to 50\%
as a measure of ratio of 1:10 of the relevance of parallel and
distributed computing in this case, or alternatively as the ratio of
``old style'' to ``new style'' HPCC.

The maturity of the field is illustrated by the design criterion used
today.  In the past, much effort has been spent on improving
performance---more speed, range, altitude, size.  These are still
critical under extreme conditions, but basically these just form a
given design framework that suffices to buy you a place at the table
(on the short-list).  Rather, the key design criteria is
competitiveness, including time to market, and total affordability.
Although the design phase is not itself a major cost item, decisions
made at this stage lock in most of the full life cycle cost of an
aircraft with perhaps 80\% of total cost split roughly equally between
maintenance and manufacturing.  Thus, it certainly would be important
to apply HPCC at the design phase to both shorten the design cycle
(time to market) and lower the later ongoing costs of manufacturing
and maintenance.

We take as an example the design of a future military aircraft---perhaps 
10 years from now.  This analysis is taken from a set of NASA sponsored
activities centered on a study of ASOP---Affordable Systems
Optimization Process.  This involved an industrial team, including
Rockwell International, Northrop Grumman, McDonnell Douglas, General
Electric, and General Motors.  ASOP is one of several possible
approaches to multidisciplinary analysis and design (MAD) and the
results of the study should be generally valid to these other MAD
systems.  The hypothetical aircraft design and construction project
could involve six major companies and 20,000 smaller subcontractors.
This impressive virtual corporation would be very geographically
dispersed on both a national and probably international scale.  This
project could involve some 50 engineers at the first conceptual design
phase.  The later preliminary and detailed design stages could involve
200 and 2,000 engineers, respectively.  The design would be fully
electronic and demand major computing, information systems, and
networking resources.  For instance, some 10,000 separate programs
would be involved in the design.  These would range from a parallel CFD
airflow simulation around the plane to an expert system to plan
location of an inspection port to optimize maintainability.  There is a
corresponding wide range of computing platforms from PCs to MPPs and a
range of languages from spreadsheets to high-performance Fortran.  The
integrated multidisciplinary optimization does not involve blindly
linking all these programs together, but rather a large number of
suboptimizations involving at one time a small cluster of these base
programs.  Here we see clearly, an essential role of HPCC to implement
these optimizations, that could well need linking of geographically
separated compute and information systems.  An aircraft is, of course,
a very precise system, which must work essentially flawlessly.  This
requirement implies a very strict coordination and control of the many
different components of the aircraft design.  Typically, there will be
a master systems database to which all activities are synchronized at
regular intervals--perhaps every month.  The clustered suboptimizations
represent a set of limited excursions from this base design that are
managed in a loosely synchronous fashion on a monthly basis.  The
configuration management and database system are both critical and
represent a major difference between manufacturing and command and
control, where in the latter case, real time ``as good as you can do''
response, is more important than a set of precisely controlled
activities.  These issues are characteristic of the linkage of HPCC,
and the NII where, although loosely coupled, the computers on our
global network are linked to ``solve a single problem.''

ASOP is designed as a software backplane (the NII) linking eight major
services or modules shown in Figure~\ref{fig12.aphp}.  These are design
(process controller) engine, visualization, optimization engine,
simulation engine, process (manufacturing, productibility,
supportability) modeling toolkit, costing toolkit, analytic modeling
toolkit, and geometry toolkit.  These are linked to a set of databases
defining both the product and also the component properties.  Parallel
computing is important in many of the base services, but the linkage of
NII, and HPCC technologies is seen in the full system.  Using compute
enhanced Web Technology (such as, WebWork \cite{Fox:95a} in such
systems is natural because one has the mix of geographically
distributed people/computers needing both data and simulation
services.

\begin{figure}
\centerline{\psfig{figure=fig5.hpdc.ps,clip=true,width=5.0in}}
\caption{Affordable Systems Optimization Process (ASOP) Implemented on the
NII for Aeronautics Systems}
\label{fig12.aphp}
\end{figure}

\subsection{Command and Control (Crisis Management)---Application 25}
\label{CandC}

Command Control (sometimes adding in Computing, Communications,
Intelligence Surveillance, and Battle Management with abbreviations
lumped together as BMC$\,^4$IS) is the task of managing and planning a
military operation.  It is very similar to the civilian area of Crisis
management, where the operations involve combating effects of
hurricanes, earthquakes, chemical spills, forest fires, etc.  Both the
military and civilian cases have computational ``nuggets'' where
parallel computing is relevant.  These include processing sensor data
(signal and image processing---Application 15) and simulations of such
things as expected weather patterns and chemical plumes.  In this way,
many of the components (Applications 1 to 12 in Table~4) are linked as
part of this large metaproblem.  One also needs large-scale multimedia
databases with HPCC issues related to those described for InfoVISiON in
Section~\ref{Info}.

High-performance communication is needed to link military planners and
decision makers, crisis managers, experts at so-called anchor desks,
workers (warriors) in the field, information sources such as cable news
feeds, and large-scale database and simulation engines.

A key characteristic of the required HPCC support is adaptivity.
Crises and battles can occur anywhere and destroy an arbitrary
fraction of the existing infrastructure.  Adaptivity means making the
best use of the remaining links, but also deploying and integrating
well mobile enhancements.  The information infrastructure must exhibit
security and reliability or at least excellent fault tolerance
(adaptivity).  Network management must deal with the unexpected
capacity demands and real time constraints.  Priority schemes must
allow when needed critical information (such as the chemical plume
monitoring and military sensor data) precedence over less time
critical information, such as background network video footage.

Needed computing resources will vary from portable handheld systems to
large backend MPPs.  As there will be unpredictable battery (power) and
bandwidth constraints, it is important that uniform user interfaces and
similar services be available on all platforms with, of course, the
fidelity and quality of a service reflecting the intrinsic power of a
given computer.  As with the communications infrastructure, we must
cope with unexpected capacity demands.  As long as the NII is deployed
nationally, computational capacity can be exploited in remote sites.
The Department of Defense envisages using the basic NII (GII)
infrastructure for command and control, augmented by ``theater
extensions'' to bring needed communications into critical areas.  The
``take it as it is'' characteristic of command and control requires
that operating systems and programming models support a general
adaptive mix (metacomputer) of coordinated geographically distributed
but networked computers.  This network will adaptively link available
people (using perhaps personal digital assistants) to large-scale
computation on MPPs and other platforms.  There are large computational
requirements when forecasting in real-time physical phenomena, such as
the weather effects on a projected military action, forest fires,
hurricanes, and the structure of damaged buildings.  On a longer time
scale, simulation can be used for contingency planning and capability
assessment.  Training with simulated virtual worlds supporting
televirtuality, requires major computational resources.  In the
information arena, applications include datamining to detect anomalous
entries (outliers) in large federated multimedia databases.  Data
fusion including sensor input and processing, geographical information
systems (with perhaps three-dimensional terrain rendering), and stereo
reconstruction from multiple video streams are examples of compute
intensive image processing forming part of the needed HPCC
environment.

A critical need for information management involves the best possible
high-level extraction of knowledge from databanks---the crisis manager
must make judgments in unexpected urgent situations---we cannot
carefully tailor and massage data ahead of time.  Rather, we need to
search a disparate set of multimedia databases.  As well as knowledge
extraction from particular information sources, the systematic use of
metadata allowing fast coarse grain searching is very important.  This
is a specific example of the importance of standards in expediting
access to ``unexpected'' databases.  One requires access to databases
specific to crisis region or battlefield, and widespread availability
of such geographic and community information in electronic form is
essential.  There are very difficult policy and security issues, for
many of these databases need to be made instantly available in a
hassle-free fashion to the military commander or crisis manager---this
could run counter to proprietary and security classification
constraints.  The information system should allow both network news and
warriors in the field to deposit in near real-time, digital versions of
their crisis and battlefield videos and images.

As mentioned, we expect that human and computer expertise to be
available in ``anchor desks'' to support instant decisions in the heat
of the battle.  These have been used in a set of military exercises
called JWID (Joint Warrior Interoperability Demonstrations).  We note
that this information scenario is a real-time version of that
described in the next section as InfoVISiON to support the society of
the Information Age.

Command and Control has historically used distributed computing as the
relevant computer and communication resources, are naturally
distributed, and not centralized into a single MPP.  We see such a HPCC
model growing into the standard information support environment for all
the nation's enterprises, including business, education, and society.
We now explore this in the following section.

\subsection{InfoVISiON in Society (Applications 19--24, 26--28, 33)}
\label{Info}

High-performance distributed computers solve problems in science and
engineering.  We think of these problems as simulations of airflow,
galaxies, bridges, and such things.  However, presumably entertaining,
informing, and educating society is an equally valid problem.
Computers and networks of the NII will be able (see
Figure~\ref{fig13.aphp}) to deliver information at many megabits/second
to ``every'' home, business (office), and school ``desk.''  This
network can be considered as a distributed HPCC system because one
expects the information to be stored in a set of distributed multimedia
services that could vary from PCs to large MPPs and be delivered to a
larger set of clients.  As shown in Figure~\ref{fig14.aphp}, one can
estimate that the total compute capability in these servers and clients
will be some hundred times greater than that of the entire set of
supercomputers in the nation.

\begin{figure}
\centerline{\psfig{figure=fig5.732.ps,clip=true,width=4.0in}}
\caption{The basic {\em InfoVISiON\/} scenario as seen by a home in the
year 2000 with an intelligent settop box interfacing the digital home to a
hierarchical network of InfoVISiON servers}
\label{fig13.aphp}
\end{figure}

\begin{figure}
\centerline{\psfig{figure=fig4.732.ps,clip=true,width=4.0in}}
\caption{An estimate of the communication bandwidth and compute capability
contained in the NII and supercomputer industries}
\label{fig14.aphp}
\end{figure}

The computational issues in this application are somewhat different
than those for the previous cases we considered.  Classic data
parallelism and languages, such as High Performance Fortran, are not
important.  Large-scale distributed databases are the heart of this
application, which are accessed through the exploding set of Web
technologies.  Presumably, these will need to migrate from today's
clients (PC/workstations) to more user friendly, and at least
initially less flexible settop box implementations controlling home
entertainment systems.  We will find the same need for data locality
as in large scale simulations.  As shown in Figure~\ref{fig15.aphp},
when the latest Hollywood movie is released on the NII, one will not
have half the nation directly connected to Hollywood.  Rather, data is
automatically replicated or cached on local servers so that one will
only need to communicate such ``hot'' information over a distance of a
few miles.  As in simulation examples, communication bandwidth
will be limited and such steps are needed to reduce demand.

\begin{figure}
\centerline{\psfig{figure=fig6.732.ps,clip=true,width=4.0in}}
\caption{A typical hierarchical server network depicted for a master system
in Hollywood cascading down with a fragment of node systems shown for
central New York}
\label{fig15.aphp}
\end{figure}

InfoVISiON will require simulation, but it will be more loosely
coupled than for say large-scale CFD, and consist of very many
smaller problems.  Interactive videogaming with multiple players
sharing a virtual world is one clear need for simulation on the NII,
and for this the three-dimensional database VRML has been introduced.
However, another example that can use the same technology is remote
viewing and exploration of consumer products, such as cars, furniture,
and large appliances.  Simulation will support virtual reality like
exploration and the automatic customization of such products for
particular customers.

InfoVISiON at its ``simplest'' is ``just'' access to multimedia
database.  But even here the ``media'' can, as in Application~24
include simulation.  Further, InfoVISiON underlies decision support in
business, government, and military areas (Applications 25, 27, and 28),
as well as education (Application 33).  Thus, this HPCC application is
of great importance, and can be expected to a major business
opportunity for the vendors, as shown in Figure~\ref{fig14.aphp}.
\clearpage

\section*{Glossary}
\begin{description}

\item [ACTION] (Advanced Computing Technology is an Innovative
Opportunity Now) The original form of InfoMall focused on large-scale
simulations.

\item [Adaptive] See Table 2.

\item [APL] See Table 6.

\item [Applets] An application interface where referencing (perhaps by a
mouse click) a remote application as a hyperlink to a {\em server\/} causes
it to be downloaded and run on the {\em client}.

\item [ASOP] (Affordable Systems Optimization Process) refers to a
process using multidisciplinary optimization to produce more
affordable systems.

\item [Asynchronous] See Table 3.

\item [Asynchronous Transfer Mode (ATM)] ATM is expected to be the
primary networking technology for the {\em NII\/} to support
multimedia communications.  ATM has fixed length 53 byte messages
(cells) and can run over any media with the cells asynchronously
transmitted.  Typically, ATM is associated with Synchronous
Optical Network (SONET) optical fiber digital networks running at
rates of OC-1 (51.84 megabits/ sec), OC-3 (155.52 megabits/sec) to
OC-48 (2,488.32 megabits/sec).

\item [Asyncsoft] See Table 2.

\item [AVS] See Table 6.

\item [Back Substitution] The stage in {\em LU decomposition\/} where
an upper triangular matrix $U\underline{x}=L^{-1}b$ is solved
``backwards'' from the end.

\item [Bandwidth] The communications capacity (measured in bits per
second) of a transmission line or of a specific path through the
network.  

\item [C$^*$] See Table 6.

\item [C++] See Table 6.

\item [CC++] See Table 6.

\item [CFD] (Computational Fluid Dynamics) refers to computational
solutions of differential equations, such as the Navier Stokes set,
describing fluid motion.

\item [Clustered Computing] A commonly found computing environment
consists of many workstations connected together by a local area
network.  The workstations, which have become increasingly powerful
over the years, can together, be viewed as a significant computing
resource.  This resource is commonly known as cluster of workstations, and
can be generalized to a heterogeneous collection of machines with arbitrary
architecture.

\item [Collective] A communication or processing activity in which
many messages or compute primitives are linked together.

\item [Command and Control] This refers to the computer support decision
making environment used by military commanders and intelligence officers.
It is described in Section~\ref{CandC}.

\item [Computational Graph] The computational or spatial structure of
a problem that is expressed as a dependency graph among linked
elements in the computation.

\item [Conjugate Gradient Method] A technique for solving systems of
linear algebraci equations, which proceeds by minimizing a quadratic
residual error function.  The method is iterative, but quite powerful:
in the absence of roundoff error, it will converge exactly in $M$
steps, where $M$ is the order of the system in question.

\item [Crystal] See Table 6.

\item [Dataflow] A model of parallel computing in which linked
programs are represented by a graph, and execution of a node (of
graph) is triggered by arrival of one or more pieces of data
``flowing'' from previously executed nodes.

\item [Data Fusion] A common {\em command and control\/} approach where the
disparate sources of information available to a military or civilian
commander or planner, are integrated (or fused) together.  Often, a {\em
GIS\/} is used as the underlying environment.

\item [Data Locality and Caching] A key to sequential parallel and
distributed computing is data locality.  This concept involves
minimizing ``distance'' between processor and data.  In sequential
computing, this implies ``caching'' data in fast memory and arranging
computation to minimize access to data not in cache.  In parallel and
distributed computing, one uses migration and replication to minimize
time a given node spends accessing data stored on another node.

\item [Data Mining] This describes the search and extraction of unexpected
information from large databases.  In a database of credit card
transactions, conventional database search will generate monthly statements
for each customer.  Data mining will discover using ingenious algorithms, a
linked set of records corresponding to fraudulent activity.

\item [Data Parallelism] A model of parallel or distributed computing
in which a single operation can be applied to cell elements of a data
structure simultaneously.  Often, these structures are arrays.

\item [Decision Support] Use of computers to supply and process
information needed to make decisions.  Term is typically applied to
business applications.

\item [Distributed Computing] The use of networked heterogeneous
computers to solve a single problem. The nodes (individual computers)
are typically loosely coupled.

\item [Distributed Memory] A computer architecture in which the memory
of the nodes is distributed as separate units.  Distributed memory
hardware can support either a distributed memory programming model,
such as message passing or a shared memory programming model.

\item [Embarrassingly Parallel] A class of problems that can be
broken up into parts, which can be executed essentially independently
on a parallel or distributed computer (see Table 3).

\item [Event Driven Simulation] See Table 2.

\item [Express] See Table 6.

\item [Finite Difference Method] A {\em direct method\/} for the
approximate solution of partial differential equations on a discrete
grid, by approximating derivatives of the unknown quantities on the
grid by linear differences.  SIMD machines typically lend themselves
very well to the efficient implementation to this sort of
applications.  See also {\em finite element method}.

\item [Finite Element Method] An approximate method for solving
partial differential equations by replacing continuous functions by
piecewise approximations defined on polygons, which are referred to as
elements.  Usually, polynomial approximations are used.  The finite
element method reduces the problem of finding the solution at the
vertices of the polygons to that of solving a set of linear equations.
This task may then be accomplished by a number of methods, including
{\em Gaussian elimination}, the {\em conjugate gradient method}, and
the {\em multigrid method}.  See also {\em finite difference method}.

\item [Fortran-M] See Table 6.

\item [Gaussian Elimination] A method for solving sets of simultaneous
linear equations by eliminating variables from the successive
equations.  The original equation in the form $Ax=b$ ($A$ is a matrix,
$b$ the vector of known values, and $x$ the unknown solution vector)
is reduced to $A=LU$ and $Ux=c$, where $U$ is an upper triangular matrix.  The
solution vector $x$ can then be found by {\em back substitution}.  This
method is usually formulated as {\em LU decomposition}.

\item [Geographical Information System (GIS)] A user interface where
information is displayed at locations on a digital map.  Typically, this
involves several possible overlays with different types of information.
Functions, such as image processing and planning (such as shortest path)
can be invoked.

\item [Gigabit] A measure of {\em network\/} performance---one Gigabit/sec is
a bandwidth of $10^9$ bits per second.

\item [Gigaflop] A measure of computer performance---one Gigaflop is
$10^9$ floating point operations per second.

\item [Global Information Infrastructure (GII)] The GII is the natural
world-wide extension of the {\em NII\/} with comparable exciting vision 
and uncertain vague definition.

\item [Grand Challenges] Computation-intensive fundamental problems in
science and engineering, with broad economic and scientific impact,
whose solution can be advanced by applying HPCC technologies and
resources.

\item [HPC++] See Table 6.

\item [High-Performance Computing and Communications (HPCC)] Refers
generically to the federal initiatives, and associated projects and
technologies that encompass {\em parallel computing}, {\em HPDC}, and
the {\em NII}.

\item [High-Performance Distributed Computing (HPDC)] The use of
distributed networked computers to achieve high performance on a
single problem, i.e., the computers are coordinated and
synchronized to achieve a common goal.

\item [High-Performance Fortran (HPF)] A language specification
published in 1993 by experts in compiler writing and parallel
computation, the aim of which is to define a set of directives which
will allow a Fortran~90 program to run efficiently on a distributed
memory machine.  At the time of writing, many hardware vendors have
expressed interests, a few have preliminary compilers (Digital, IBM),
and a few independent compiler producers (APR, Portland Group) also
have early releases.  If successful, HPF would mean data parallel
programs can be written portably for various multiprocessor platforms.

\item [HPF+] See Table 2.

\item [Hyperlink] The user level mechanism (remote address specified in a
{\em HTML\/} or {\em VRML\/} object) by which remote services are accessed
by {\em Web Clients\/} or {\em Servers}.

\item [Hypertext Markup Language (HTML)] A syntax for describing documents
to be displayed on the {\em World Wide Web}.

\item [Hypertext Transport Protocol (HTTP)] The {\em protocol\/} used in
the communication {\em Web Servers\/} and {\em clients}.

\item [InfoMall] (http://www.infomall.syr.edu) A virtual corporation
of some 50 organizations, funded by New York State and led by NPAC at
Syracuse University, aimed at building practical HPCC systems and
applications.

\item [InfoVISiON] Information, Video, Imagery, and Simulation ON
demand is scenario described in Section~\ref{Info} where {\em
multimedia servers\/} deliver multimedia information to clients on
demand---at the click of the user's mouse.

\item [Integrated Service Data Network (ISDN)] A digital multimedia
service standard with a performance of typically 128 kilobits/sec, but
with possibility of higher performance.  ISDN can be implemented using
existing telephone ({\em POTS}) wiring, but does not have the
necessary performance of 1--20 megabits/second needed for full screen
TV display at either VHS or high definition TV (HDTV) resolution.
Digital video can be usefully sent with ISDN by using quarter screen
resolution and/or lower (than 30 per second) frame rate.

\item [Integration Software] See Table 2.

\item [Internet] A complex set of interlinked national and global
networks using the IP messaging protocol, and transferring data,
electronic mail, and {\em World Wide Web}.  In 1995, some 20 million
people could access Internet---typically by {\em POTS}.  The Internet
has some high-speed links, but the majority of transmissions achieve
(1995) bandwidths of at best 100~kilobytes/sec.  the Internet could be
used as the network to support a {\em metacomputer}, but the limited
{\em bandwidth\/} indicates that {\em HPDC\/} could only be achieved
for {\em embarrassingly parallel\/} problems.

\item [Internet Protocol (IP)] The network-layer communication
protocol used in the DARPA Internet.  IP is responsible for
host-to-host addressing and routing, packet forwarding, and packet
fragmentation and reassembly.

\item [Irregular Problems] Problems whose computational graph has an
irregular structure as seen in finite element approaches to simulation
of complex systems.

\item [Java] A distributed computing language ({\em Web Technology\/})
developed by Sun, which is based on C++ but supports {\em Applets}.

\item [JavaScript] A fully interpreted language based loosely on Java,
but aimed at integration of client capabilities of Netscape Web clients
(browsers or navigators).

\item [Latency] The time taken to service a request or deliver a
message which is independent of the size or nature of the operation.
The latency of a {\em message passing\/} system is the minimum time to
deliver a message, even one of zero length that does not have to leave
the source processor.  The latency of a file system is the time
required to decode and execute a null operation.

\item [Linda] See Table 6.

\item [Living School Book] A collaboration involving NYNEX, Syracuse
University School of Education, Columbia Teachers College, and NPAC
developing InfoVISiON applications for six schools on a high-speed ATM
network.

\item [Loose and Tight Coupling] Here, coupling refers to linking of
computers in a network.  Tight refers to low latency, high bandwidth;
loose to high latency and/or low bandwidths.  There is no clear
dividing line between ``loose'' or ``tight.''

\item [Loosely Synchronous] See Table 3.

\item [LU Decomposition] A technique where a matrix $A$ is represented
as the product of a lower triangular matrix, $L$, and an upper
triangular matrix $U$.  This decomposition can be made unique either
by stipulating that the diagonal elements of $L$ be unity, or that the
diagonal elements of $L$ and $U$ be correspondingly identical.

\item [MAD] (Multidisciplinary Analysis and Design, or Multidisciplinary
Optimization) refers to the coupling of several areas, such as
structural dynamics and fluid flow in a combined tradeoff to produce
higher capability vehicles.

\item [Massively Parallel Processing Processor (MPP)] The strict
definition of MPP is a machine with many interconnected processors,
where `many' is dependent on the state of the art.  Currently, the
majority of high-end machines have fewer than 256 processors.  A more
practical definition of an MPP is a machine whose architecture is
capable of having many processors---that is, it is scalable.  In
particular, machines with a distributed memory design (in comparison
with shared memory designs) are usually synonymous with MPPs since they
are not limited to a certain number of processors.  In this sense,
``many'' is a number larger than the current largest number of
processors in a shared-memory machine.

\item [Megabit] A measure of network performance---one Megabit/sec is
a bandwidth of $10^6$ bits per second.  Note eight bits represent one
character---called a byte.

\item [Message Passing] A style of inter-process communication in
which processes send discrete messages to one another.  Some computer
architectures are called message passing architectures because they
support this model in hardware, although message passing has often
been used to construct operating systems and network software for
sequential processors, shared memory, and distributed computers.

\item [Message Passing Interface (MPI)] The parallel programming
community recently organized an effort to standardize the communication
subroutine libraries used for programming on massively parallel
computers such as IBM SP2, Intel's Paragon, Cray's T3D, as well as
networks of workstations.  MPI not only unifies within a common
framework programs written in a variety of exiting (and currently
incompatible) parallel languages but allows for future portability of
programs between machines.

\item [Metacomputer] This term describes a collection of heterogeneous
computers networked by a high-speed wide area network.  Such an
environment would recognize the strengths of each machine in the
Metacomputer, and use it accordingly to efficiently solve so-called
{\em Metaproblems}.  The {\em World Wide Web\/} has the potential to be
a physical realization of a Metacomputer.  

\item [Metaproblem] This term describes a class of problem which is
outside the scope of a single computer architectures, but is instead
best run on a Metacomputer with many disparate designs.  These problems
consist of many constituent subproblems.  An example is the design and
manufacture of a modern aircraft, which presents problems in geometry
grid generation, fluid flow, acoustics, structural analysis,
operational research, visualization, and database management.  The
{\em Metacomputer\/} for such a Metaproblem would be networked
workstations, array processors, vector supercomputers, massively
parallel processors, and visualization engines.

\item [Metropolis] A distinguished Los Alamos scientist whose name is
associated with a particular importance sampling (optimized choice of
points) approach to {\em Monte Carlo\/} methods aimed at statistical
physics problems.

\item [Monte Carlo] An approach in which many independent trials are
used to evaluate integrals, with trial parameters chosen randomly.

\item [Message Passing Fortran (MPF)] See Table 2.

\item [Multimedia Server or Client] Multimedia refers to information
(digital data) with different modalities, including text, images,
video, and computer generated simulation.  Servers dispense this data,
and clients receive it.  Some form of browsing, or searching,
establishes which data is to be transferred.  See also {\em InfoVISiON}.

\item [Multiple-Instruction/Multiple-Data (MIMD)] A {\em parallel
computer\/} architecture where the nodes have separate instruction
streams that can address separate memory locations on each clock
cycle.  All {\em HPDC\/} systems of interest are {\em MIMD\/} when
viewed as a {\em metacomputer}, although the nodes of this metacomputer
could have {\em SIMD\/} architectures.

\item [Multipurpose Internet Mail Extension (MIME)] The format used in
sending multimedia messages between {\em Web Clients\/} and {\em Servers\/}
that is borrowed from that defined for electronic mail.

\item [National Challenges] Information-intensive fundamental
applications that have broad and direct impact on the Nation's
competetitivess and the well-being of its citizens, and that can
benefit from the application of {\em HPCC\/} technologies and resources.

\item [National Information Infrastructure (NII)] The collection of
{\em ATM}, cable, {\em ISDN}, {\em POTS}, satellite, and wireless
networks connecting the collection of $10^8$--$10^9$ computers that
will be deployed across the U.S.A. as set-top boxes, PCs, workstations,
and MPPs in the future.

The NII can be viewed as just the network infrastructure or the full
collection of networks, computers, and overlayed software services.
The {\em Internet\/} and {\em World Wide Web\/} are a prototype of the
NII.

\item [Network] A physical communication medium.  A network may
consist of one or more buses, a switch, or the links joining
processors in a multicomputer.

\item [Node] A parallel or distributed system is made of a bunch of
nodes or fundamental computing units---typically fully fledged
computers in the {\em MIMD\/} architecture.

\item [NPAC] (http://www.npac.syr.edu) The Northeast Parallel
Architectures Center at Syracuse University is an HPCC research and
development organization focusing on industrial relevance.

\item [N(UMA)] UMA---Uniform Memory Access---refers to shared memory
in which all locations have the same access characteristics, including
the same access time.  NUMA (Non-Uniform Memory Access) refers to the
opposite scenario.

\item [Parallel Computer] A computer in which several functional units
are executing independently.  The architecture can vary from {\em
SMP\/} to {\em MPP\/} and the {\em nodes\/} (functional units) are {\em
tightly coupled}.

\item [Partial Differential Equation (PDE)] The most common
mathematical description of physical systems.

\item [PCN] See Table 6.

\item [POTS] The conventional twisted pair based Plain Old Telephone
Service.

\item [Protocol] A set of conventions and implementation methodologies
defining the communication between nodes on a network.  There is a
famous seven layer OSI standard model going from physical link
(optical fiber to satellite) to application layer (such as Fortran
subroutine calls).  Any given system, such as PVM or the Web implements
a particular set of protocols.

\item [PVM] PVM was developed at Emory and Tennessee Universities, and
Oak Ridge National Laboratory.  It supports the {\em message passing\/}
programming model on a network of heterogeneous computers
(http://www. epm.ornl.gov/pvm/).

\item [Quantum Chromodynamics (QCD)] A model of the behavior of matter
on sub-nuclear scales, the simulation of which is very hungry of
computing power.

\item [Regular Problems] Problems whose computational graph has a
regular structure as seen in Quantum Chromodynamics simulations or
many finite different problems.

\item [Runtime] The part of systems support software used when a
program is executed.  This should be contrasted with compile-time
preparation of program.

\item [Settop Box] The interface between the home entertainment system
(now TV) and outside information (now cable).  Future settop boxes
will need personal computer-type functionality, and link to Web
Technology.

\item [Shared Memory] Memory that appears to the user to be contained
in a single address space that can be accessed by any process or any
node (functional unit) of the computer.  Shared memory may have {\em
UMA\/} or {\em NUMA\/} structure.  {\em Distributed computers\/} can
have a shared memory model implemented in either hardware or
software---this would always be NUMA.  Shared memory parallel computers
can be either {\em NUMA\/} or {\em UMA}.

Virtual or Distributed Shared Memory is (the illusion of) a shared
memory built with physically distributed memory.

\item [Single-Instruction/Multiple-Data (SIMD)] A {\em parallel computer\/}
architecture in which every node runs in lockstep accessing a single
global instruction stream, but with different memory locations
addressed by each node.  Such synchronous operation is very unnatural
for the nodes of a {\em HPDC\/} system, or the NII.

\item [Supercomputer] the most powerful computer that is available at
any given time.  As performance is roughly proportional to cost, this
is not very well defined for a scalable parallel computer.
Traditionally, computers costing some \$10~M--\$30~M are termed
supercomputers.

\item [Symmetric Multiprocessor (SMP)] A Symmetric Multiprocessor
supports a shared memory programming model---typically with a {\em UMA\/}
memory system, and a collection of up to 32 nodes connected with a bus.

\item [Synchronous] See Table 3.

\item [Televirtual] The ultimate computer illusion where the user is fully
integrated into a simulated environment and so can interact naturally with
fellow users distributed around the globe.

\item [Teraflop] A measure of computer performance---one Teraflop is
$10^{12}$ floating point operations per second.

\item [Terrain Rendering] The graphics processing of a
three-dimensional scene, typically with a digital map as a 3D
backdrop.

\item [Timewarp] See Table 6.

\item [Time Stepped Simulation (TS)] See Table 2.

\item [Video-on-Demand] A component of {\em InfoVISiON\/} where digital
video (movies, news, etc.) is supplied at the request of clients.

\item [Vienna Fortran] See Table 6.

\item [Virtual Reality (VR)] See Table 2.

\item [Virtual Reality Modeling Language (VRML)] A ``three-dimensional''
HTML that can be used to give a universal description of three-dimensional
objects that supports {\em hyperlinks\/} to additional information.
The latest VRML 2.0 is aimed at supporting virtual environments
implementing televirtuality.

\item [Web Clients and Servers] A distributed set of clients (requesters
and receivers of services) and servers (receiving and satisfying requests
from clients) using {\em Web Technologies}.

\item [WebTop] refers to the implementation of a set of standard desk
top and personal computer tools, which are essential in any computing
environment.

\item [WebWindows] The operating environment created on the World Wide
Web to manage a distributed set of networked computers.  WebWindows is
built from {\em Web clients\/} and {\em Web servers}.

\item [WebWork] (Fox:95a) An environment proposed by Boston University,
Cooperating Systems Corporation, and Syracuse University, which integrates
computing and information services to support a rich distributed
programming environment.

\item [World Wide Web and Web Technologies] A very important software
model for accessing information on the Internet based on hyperlinks
supported by {\em Web technologies}, such as {\em HTTP}, {\em HTML},
{\em MIME}, {\em Java}, {\em Applets}, and {\em VRML}.
\end{description}
\clearpage

\bibliography{/home/sashimi2/kea/bib/doc,/home/sashimi2/kea/bib/SCCS,/home/sashimi2/kea/bib/outside}
\bibliographystyle{gcf_unsrt}
\end{document}


