\documentstyle[11pt]{article}
\input psfig
\setlength{\topmargin}{-0.5in}
\setlength{\textwidth}{4.5in}
\setlength{\textheight}{7.5in}
\setlength{\oddsidemargin}{1in}
\pagestyle{empty}
\begin{document}

\begin{center}
{\bf Software and Hardware Requirements for Some Applications of
Parallel Computing to Industrial Problems}
\end{center}
\bigskip

\begin{center}
{\em Geoffrey C. Fox} \\
gcf@npac.syr.edu \\
http://www.npac.syr.edu
\end{center}

\vspace{.1in}

\begin{center}
Northeast Parallel Architectures Center \\
111 College Place \\
Syracuse University \\
Syracuse, New York  13244-4100
\end{center}

\section{Introduction}

This paper combines a recent survey of industrial applications with a
problem classification developed for largely academic applications.  We
show how this allows one to isolate the parallel computing hardware and
software characteristics needed for each problem.  The industrial
applications come from a survey undertaken of New York State industry
in 1991 and 1992.  Further details of the survey will be found in
\cite{Fox:92e}, \cite{Fox:94b}, \cite{Fox:94h}, \cite{Fox:94c},
\cite{Fox:94i}, \cite{Mills:93a}.  Here, we summarize relevant features
of it in Section~\ref{industry}.  Section~\ref{prob.arc} reviews and
extends a classification of problem architectures originally developed
in 1988 from a rather complete survey of parallel applications at the
time \cite{Fox:88b}, \cite{Fox:88tt}, \cite{Fox:91g}, \cite{Fox:94a}.

In Section~\ref{issues}, 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{prob.arc}, we
point that our old classification of problems omitted what we can call
{\em metaproblems\/}---problems built up from several
components---each of which could have its own parallelization issues.

In Section~\ref{cases}, we combine the previous three sections and
describe informally the problem architecture, and possible software and
hardware needs for a selection of industrial applications.  We have
grouped our discussion into three broad case studies; computational
chemistry; computational fluid dynamics and manufacturing; Monte Carlo
methods.  Each case study covers several of the 33 industrial areas
identified in Section~\ref{industry}.  Further, in each case study, we
find good examples of the different problem architectures and show that
each application area requires a rich software and hardware
architecture support.

\section{Industrial Applications}
\label{industry}

In 1991--92, New York State funded a survey of the industrial
opportunities for parallel computing.  This was part of a project,
ACTION (Advanced Computing Technology is an Innovative Opportunity
Now), at Syracuse University.  ACTION's goal was to accelerate the use
of parallel computing into the industry of New York State.  The
purpose of the survey was to isolate some initial projects and, more
generally, to provide information on which to develop a long-term plan
for ACTION.  Relevant information included the basic parallel
computing software and algorithm technologies needed for particular
industry sectors.  In this paper, we concentrate on the software
capabilities needed for these applications, and also the appropriate
parallel machine architectures.  Further discussion of the survey
technique, particular companies interviewed, and the detailed nature
of the applications will be found in \cite{Fox:92e}, \cite{Fox:94a},
and papers cited earlier.  The survey has inevitable limitations.
There are many important applications---oil exploration is a good
example---that are not well represented in New York State.  Further,
the survey was not complete within its limited geographic region, and
is still being extended.

Tables~1--4 summarizes the industrial opportunities for parallel
computing in the form we will use them.  Some 50 different applications
used in the survey have been broken up into 17 distinct areas.  This is
certainly somewhat arbitrary, and there are many overlaps (and
omissions as discussed).  The importance, difficulty of implementation,
and degree of risk also differ from case to case.  However, these
issues will not be discussed here.
\newpage

\begin{center}
{\bf Table 1: Guidelines used in Developing Categories of} \\
{\bf Industrial and Government Applications of HPCC} \\
{\bf shown in Tables 3--4}
\vspace*{10pt}
\begin{tabular}{|lp{4.15in}|}
\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 MPP and HPCC 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 \\
&$\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{3.75in}|}
\multicolumn2{c}{\bf Table 2: Abbreviations used in Tables 3--4 of} \\
\multicolumn2{c}{\bf Industrial Applications of HPCC} \\
\hline
& \\
{\bf Adaptive}&Software for Irregular Loosely Synchronous Problems
handled by pC++, 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}
\vspace{3pt}
{\em Note on Language: HPF, MPF use Fortran for illustration,} \\
{\em one can use parallel C, C++ or any similar extensions of data
parallel or message passing languages} \\
\newpage

\begin{center}
{\bf Table 3: Five Categories of Problems} \\
\begin{tabular}{|p{3.0in}|p{1.25in}|}
\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 \\
\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 parallel \\
\hline
& \\
{\bf Embarrassingly\/} parallel:& \\
\ \ \ Essentially independent execution of disconnected components
(can involve reductions).&Possible in most software \\
\hline
& \\
{\bf Metaproblems\/}& \\
\ \ \ Asynchronous collection of (loosely) synchronous components
where these programs themselves can be parallelized&Coarse grain task
parallelism---each component data parallel \\
\hline
\end{tabular}
\end{center}

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

\begin{center}
{\bf Table 4: Information Integration Applications 29 to 33} \\
\begin{tabular}{|lp{4.0in}|}
\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, Electronic Cash, etc. \\
& \\
$\bullet$&{\bf 31: Electronic Shopping} \\
& \\
$\bullet$&{\bf 32: Agile Manufacturing---Multidisciplinary Design and
Concurrent Engineering} \\
&$\bullet$ Combines CAD with Applications 1 to 3 \\
&$\bullet$ Requires major changes to Manufacturing Infrastructure and 
Approach \\
& \\
$\bullet$&{\bf 33: Education} \\
&$\bullet$ InfoMall Living Textbook---6 Schools on ATM network
linked to HPCC InfoVision Servers at NPAC \cite{Mills:95a} \\
\hline
\end{tabular}
\end{center}

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'' 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.  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.

This paper is not intended to advocate a particular parallel software
environment or language.  Rather, we want to describe the broad
capabilities in 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 and 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++ environments could well be more attractive,
and can be substituted in the table.

\section{Problem Architectures}
\label{prob.arc}

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~4.  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{fig1.134c}) 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{fig2.134c}, 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=4.5in}}
\caption{Computation and Simulation as a Series of Maps}
\label{fig1.134c}
\end{figure}

\begin{figure}
\centerline{\psfig{figure=fig2.hetero.ps,width=3.75in}}
\caption{Issues Affecting Relation of Machine, Problem, and Software
Architecture}
\label{fig2.134c}
\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{fig3.134c}a describing the problem at a given instant of
simulation time \cite{Fox:88tt}.  This is important in determing 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~4, 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{fig4.134c}, 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{fig3.134c}
\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{fig4.134c}
\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{fig5.134c} 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 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{fig5.134c}
\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 whever 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{fig6.134c}, are computer or biological
circuit simulations where different components or neurons are linked
irregularly and modelled 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=fig1.prob.ps,height=4.5in}}
\caption{The Loosely Synchronous Problem Class}
\label{fig6.134c}
\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{fig3.134c}b.  A good example is an event
driven simulation, illustrated in Figure~\ref{fig7.134c}, 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
\end{itemize}
\caption{The Asynchronous Problem Class}
\label{fig7.134c}
\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{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{fig8.134c} 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 of class and a
heterogeneous computer network.

\begin{figure}
\centerline{\psfig{figure=fig8.134c.ps,clip=true,width=4.5in}}
\caption{The Mapping of Heterogeneous Metaproblems onto Heterogeneous
Metacomputer Systems}
\label{fig8.134c}
\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 asynchornous 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.

There were a few examples mentioned above of metaproblems in our
original survey, but a major part of Table~4, from our New York State
activity, is the Information Integration classification, including
manufacturing and the applications 25--33 are essentially all
metaproblems.  As stated boldly in Table~1, this class is the most
important long-term area for HPCC.  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 very important.

\section{Some Software and Machine Issues}
\label{issues}

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}
{\bf Table 5: What is the ``Correct'' Machine Architecture for each Problem
Class?} \\
\vspace*{10pt}
\begin{tabular}{|ll|}
\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.

\begin{center}
{\bf Table 6: Candidate Software Paradigms for Each Problem
Architectures} \\
\vspace*{10pt}
\begin{tabular}{|lp{4.0in}|}
\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 C++ \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} \\
& \\
$\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; 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}

We have described those issues at length in [Fox:90p;91g;94a], and
\nocite{Fox:90p} \nocite{Fox:91g} \nocite{Fox:94a} here we will just
present 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{fig9.134c} 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{fig10.134c}, 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}
{\bf Table 7: Imprecise Mapping of Problem Classes into Runtime and
Language Terms} \\
\vspace*{10pt}
\begin{tabular}{|lp{4.0in}|}
\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$&{\bf INTEGRATION Runtime and Programming Environments} \\
&$\bullet$ Metaproblems \\
&$\bullet$ AVS works well but also can be integrated into
languages such as HPC++, Fortran-M \\
& \\
\hline
\end{tabular}
\end{center}

\begin{figure}
\centerline{\psfig{figure=fig9.134c.ps,clip=true,width=4.5in}}
\caption{General Applicability of HPF, HPF+, HPC++ Classified by
Problem Architecture and type of Runtime Support needed}
\label{fig9.134c}
\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{fig10.134c}
\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}, \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{fig9.134c} 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{industry},\ref{prob.arc}, and
\ref{issues}.

\section{Machine and Problem Architectures and Appropriate Programming
Paradigms in Three Case Studies}
\label{cases}

We now illustrate the different machine, problem, and software issues
with three 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.

\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 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{fig3.134c}(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 HPF1 provides for
arrays.

Now, let us consider manufacturing as a major industrial application
of PDE's.  Here, HPCC offers an important opportunity to build
futuristic manufacturing systems allowing customizable products with
integrated design (conceptual and detailed), manufacturing process,
sales and support.  This scenario---sometimes called agile
manufacturing---implies other major thrusts including concurrent
engineering and multidisciplinary analysis and design.  Here, we can
use an example where NPAC is working under NASA sponsorship with the
MADIC (Multidisciplinary Analysis and Design Industry Consortium)
collaboration involving Rockwell, Northrop Grumman Vought, McDonnell
Douglas, General Electric, General Motors and Georgia Tech.  We are in
particular involved in establishing for this NASA project, the NII
requirements for a future concurrent engineering concept called ASOP
(Affordable Systems Optimization Process).  Aircraft are now built by
multi-company collaborations with international scope which virtual
corporation needs collaborative and networked software engineering and
workflow support.  Configuration management is a critical need.  ASOP
links a range of disciplines (from manufacturing process simulation,
electromagnetic signature, aeronautics and propulsion computation
linked to CAD databases and virtual reality visualization) using
MDO---multidisciplinary optimization---techniques.  The integration of
conceptual (initial) and detailed design with the manufacturing and
life cycle support phases naturally requires the integration of
information and computing in the support system.  WebWork
\cite{Fox:95a} has been designed for this.  Further, we see this
problem is a heterogeneous metaproblem with perhaps up to 10,000
(Fortran) programs linked together in the full optimization process.
This is basically an embarrassingly parallel meta-architecture with
only a few of the programs linked together at each stage.  The program
complexity varies from a full PDE simulation to an expert system to
optimize location of an inspection port to minimize support costs.  So
efficient parallel solution of PDEs is part, but not all of the support
needed for manufacturing.  HPCC will only have major impact on
manufacturing when it can support such heterogeneous metaproblems,
including large scale database integration.

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

We have already mentioned in Section~\ref{prob.arc}, 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 a synchronous 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 show 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.

\subsection{Summary}

Each of three case studies illustrates how different applications and
different numerical approaches to a given problem, lead to very
different problem architectures and correspondingly the needed
software support.  Although our discussion is not complete, we do
think that it is quite typical, and that a similar situation is seen in
the other applications of Table~4, and summarized in the last two
columns.

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

