\documentstyle{article}
%
\def\lea{\mathrel{\raise .4ex\hbox{\rlap{$<$}\lower 1.2ex\hbox{$\sim$}}}}
\def\gea{\mathrel{\raise .4ex\hbox{\rlap{$>$}\lower 1.2ex\hbox{$\sim$}}}}
%
\newcommand{\medStrut}{{\rule{0cm}{4.0ex}}}
%
\newdimen\digitwidth
\setbox1=\hbox{0}
\digitwidth=\wd1
\catcode`"=\active
\def"{\kern\digitwidth}
%

\title{Achievements and Prospects for Parallel Computing}

\author{Geoffrey C. Fox \\
        Northeast Parallel Architectures Center \\
        Syracuse University \\
        111 College Place \\
        Syracuse, New York  13244 \\
        gcf@nova.npac.syr.edu}
\begin{document}
\maketitle

\begin{abstract}
Parallel computing works for the majority of large scale computations.  The 
development of parallel hardware designs has been largely transferred to 
industry, while universities continue major research efforts into better 
software environments.  We describe a classification of problems and how 
different software models are needed for portable user friendly high 
performance implementations on parallel machines.  The education of a new 
generation of computational scientists will be a major challenge to our 
universities. 
\end{abstract} 

\newpage
\section{Introduction}

In 1981, I listened to a Physics colloquium given by Carver Mead at Caltech.  
Carver was a pioneer in the development of VLSI, and explained how 
developments in this technology would inevitably lead to parallel computers.  
At the time, we were using our relatively new VAX11/780 to perform crude 
Quantum Chromodynamics (QCD) simulations with week-long runs.  That talk 
changed my career, as I realized that QCD would naturally run in parallel.  
While waiting for the initial 64~node 8086-8087 based hypercube to be 
completed, I realized that we (now a collaboration with Carver's colleague, 
Chuck Seitz, in the Caltech Computer Science Department) had a machine that 
appeared to be generally useful in science.  Thus was born the Caltech 
Concurrent Computation Program ($\rm C^3P$) which, from 1983--1990, 
investigated the question:
\begin{quote}
``Is the hypercube (and later more general parallel architectures) effective 
in numerically intensive scientific and engineering calculations?''
\end{quote}

I have described the history of $\rm C^3P$ elsewhere \cite{Fox:87d}, 
\cite{Fox:88oo} with the culmination \cite{Fox:89n} that in 1989 (eight years 
after believing Carver's dream), we finally obtained parallel computers that 
were truly Supercomputers.  In a series of articles, I have described some 
highlights of the fifty significant applications we built for the hypercube 
\cite{Fox:89b}, \cite{Fox:89i}, \cite{Fox:89n}, \cite{Fox:90o}.  Here, I will 
concentrate on other areas---hardware, software and education---but I 
emphasize that these were each built on the experience of 
\begin{quote} 
``Using Real Hardware with Real Software to Solve Real Problems'' 
\end{quote} 

Indeed, this motto will continue to be a guiding principle in the new program 
that I am setting up at Syracuse University.

The research of $\rm C^3P$ taught me several lessons.
\begin{itemize}
\item Parallel Computing works for essentially all computationally intense 
problems.
\item Computation will grow in importance---fed by high performance 
parallel computers---and will ``change the world''---in academia, 
industry, day to day life and government applications.
\item We need to develop new educational approaches to train the next 
generation of scientists who will have the interdisciplinary skills to 
exploit new computers for new problems.
\end{itemize}

My time at Caltech, and in particular with $\rm C^3P$, were immensely 
rewarding and Caltech was one of the very few universities where a program 
like $\rm C^3P$ could have succeeded.  Now, we know both that parallel 
computers work and how to exploit them for leading edge academic 
applications.  The new challenges are different.  We must make parallel 
computing available to a broad range of users both in academia and more 
importantly in the real world of industry---only in this way will it enter the 
mainstream of computing.  This principle underlies my vision of the future of 
parallel computing.  Correspondingly, at Syracuse University, we will have 
some similarities with $\rm C^3P$.  It will be interdisciplinary but with a 
different focus---the Syracuse Center for Computational Science will emphasize 
education and the integration of parallel computing into industry. 

This paper has three major sections describing respectively, the status and 
prospects for hardware, software and education.  We will see my focus on 
applications in the chapter on software, which we discuss from this point of 
view.

\section{Hardware Prospects}

Parallel Computers were surveyed by Paul Messina for this conference, and I 
will just make a few general remarks.  University and industry research has 
developed the basic principles of parallel computer hardware, and this 
knowledge has been successfully transferred to industry which can be expected 
to produce future hardware.  The time of large scale machines designed and 
built in universities has passed.

Existing machines can be classified into three broad architectural areas; 
MIMD distributed memory or multicomputers; SIMD distributed memory; MIMD 
shared memory or multiprocessors.  My interest is in the first 
two---distributed memory---machines which can be expected to realize the 
highest and most cost effective performance.  Shared memory machines will 
certainly be important in the near future, and this software (as opposed to 
hardware) structure will be of great importance even on distributed memory 
hardware.

There are several effective large-scale distributed memory machines now 
available; the Connection Machine CM-2, INTEL~i860, and NCUBE2 custom 
hypercube all having multi-gigaflop peak performance.  We should also
mention the Butterfly TC2000, which can be viewed as a shared memory
machine, but is better thought of as a distributed memory machine with a
switch interconnect that gives, in particular, low latency.  It is not
clear if this design can produce the high (peak) performance of the
other distributed memory architetures.  Smaller (in size and price) systems 
include those based on transputers, and the SIMD AMT~DAP and Maspar machines. 
Although all these machines are very usable, many of them have rather clear 
design or implementation flaws.  These are in the areas of communication 
bandwidth and latency, input/output subsystems including the host or 
interface computer.  More generally, system integration needs to be improved. 
The communication issues can be illustrated with the measurements shown in 
Table~1 \cite{Dunigan:90a}, \cite{Hu:90a}, \cite{Williams:90e}. 

\begin{table}
\begin{center}
\begin{tabular}{||p{1.5in}|c|c|c||}
\hline
&\multicolumn{1}{|c}{$t_{\rm flop}$ node}&
\multicolumn{1}{|c|}{$t_{\rm comm}/t_{\rm flop}$}&
\multicolumn{1}{|c||}{$t_{\rm lat}/t_{\rm flop}$}
\\
\multicolumn{1}{||c}{Machine}&\multicolumn{1}{|c}{Floating Point}&
\multicolumn{1}{|c|}{Communication}&\multicolumn{1}{c||}{Message}
\\
&\multicolumn{1}{|c}{Time}&
\multicolumn{1}{|c|}{Time/64 bit Word}
&\multicolumn{1}{c||}{Latency}
\\
\cline{3-4}&\multicolumn{1}{|c}{($\mu\,$s)}&\multicolumn{2}{|c||}{(measured 
in units of a typical}
\\
&&\multicolumn{2}{|c||}{node floating point time)}
\\
\hline
\medStrut
Transputer System &&& \\
--- Direct&2\phantom{.}"&"2.2&""13 \\
\ \ (no routing) &&& \\
--- Express&2\phantom{.}"&"2.8&"300 \\
\ \ (routing software) &&& \\
INTEL i860&0.1&60\phantom{.}"&1400 \\
Express &&& \\
NCUBE 1&7\phantom{.}"&"2\phantom{.}"&"100 \\
Express &&& \\
\hline
\end{tabular}
\caption{Communication and Calculation Parameters}
\end{center}
\end{table}

We would expect future systems to be able to achieve $t_{\rm comm}/t_{\rm 
flop}$ (typical node to node communication time per word/typical
floating point node calculation time) in range $1\rightarrow 10$ which is 
the value needed for general applicability of the machine.  However, even 
the current i860 based INTEL systems with the high value of 
$t_{\rm comm}/t_{\rm flop}\sim 60$ perform well on many applications.

The issue of latency is less clear and cannot be separated from questions of 
network topology or node interconnection.  Often these points, latency and 
topology, are treated separately with more attention being given to the 
interconnection scheme.  We now find in current machines, interconnects
using meshes, hypercubes, and switches with or 
without automatic routing hardware.  These have all been successful and there 
is no convincing argument in favor of any one interconnect scheme.  Most 
theoretical studies use unrealistic message-passing models, such as random 
message traffic which is a poor representation of the highly correlated 
communication needs in scientific computation.  Further, the current systems 
have too few nodes to allow decisive experiments which could distinguish 
different interconnect methods.  Even less is known about latency which 
deserves greater study, and this one of the areas where further research is 
needed to refine the architecture of future machines. 

There is no uniquely good machine, as is illustrated by the current 
commercial systems which are all broadly successful.  We can expect 
architectural diversity to continue within the design space indicated by 
today's existing and planned machines.  Such a range of machines implies that 
the software must be portable and insensitive to changes in topology, 
granularity (number of nodes, memory per node), latency and if possible the 
choice between SIMD and MIMD.  To motivate our research in algorithms, 
applications and software, we can imagine what one of the year 2000 teraflop 
computers will look like.  It could have perhaps $N\sim 10,000$ nodes, each 
realizing some 200 megaflops. Maybe the architecture would be hierarchical; 
perhaps a 1024 element hypercube, with each element consisting of around ten 
processors sharing the same memory system.  Such machines will exist before 
the year 2000 but at higher price and with technology trade-offs (e.g., are 
optical interconnects cost-effective?) which will affect the architecture and 
hence ``balance'' and ``generality'' of the machine.  We can expect that some 
or all of today's parallel computer companies will grow as the field matures; 
new enterprises will be formed and traditional computer manufacturers will 
move into the field.  In particular, Digital and IBM, with their systems 
integration experience, may be major players.  This growth is currently 
limited by software tools and the need to increase the number of industrial 
applications that run on parallel machines.

In the above, we have discussed ``conventional'' parallel machines.  These 
will be the top of the line supercomputers and get unbelievable performance 
on most problems.  In particular, special purpose machines, such as those in 
high energy physics (QCD) and computational fluid dynamics, will no longer be 
cost effective.  Major special purpose hardware will only be justified in 
areas like neural networks, which use a radically distinct computational 
methodology.

\section{Software}

The greatest challenge, and least agreement among practitioners, is found in 
software support for parallel computers.  We will discuss this in the context 
of the layered structure shown in Figure~1, and introduced to me by Ken 
Kennedy for the Center for Research in Parallel Computation.  Of the four 
layers, the uncertainty centers on the third; namely, on high-level 
relatively general systems such as Parallel Fortran.  It is not clear as to 
the nature of this software level, and if one can usefully satisfy the
conflicting demands of generality in application and high (reasonable)
performance scaling to a variety of current and future architectures.  Before 
returning to this, let us quickly discuss the other levels.  We should first 
note that we will not discuss the support software that is critical for a 
reasonable environment; this includes debuggers, libraries, performance 
evaluation and visualization tools.  These are important, but not the subject 
of this paper. 

\begin{figure}
\begin{center}
{\bf Software Layers}
\vspace*{6.0in}
\caption{Software Layers for Parallel Computers}
\end{center}
\end{figure}

The top layer, with software systems such as NASTRAN (finite elements)
and CHARMM (molecular dynamics), is particularly important in industry.
These systems will certainly be at least as important for parallel systems, 
especially as there is an even greater need to shield the user from the 
immature parallel computers.  However, it inevitably will take some time to 
produce these systems.  This work will be accelerated when standards are 
established for the lower levels, two and three.  Fortran and C, plus message 
passing (level two), are clearly effective in giving high performance 
implementations on MIMD distributed machines.  Indeed, essentially all 
successful work, including the some fifty hypercube applications we did 
within $\rm C^3P$ at Caltech, has used this approach.  As long as you 
parameterize the number of nodes, this software is formally portable; and the 
same program will run on the NCUBE and INTEL hypercubes, a network of 
workstations, and even multi-headed IBM 3090's and CRAY vector 
Supercomputers.  This portability is supported by the commercial system, 
{\em Express}, for level-one software which is the outgrowth of our CrOS 
software developed at Caltech \cite{Fox:88a}.  However, this portability does 
not preserve performance; each machine involves different optimizations in 
the message passing and node programs to reflect tradeoffs for
\begin{itemize}
\item Granularity (number of nodes)
\item Communication bandwidth and latency\hfill (1)
\item Interconnect topology
\item Overlap (or not) of communication and calculation
\item Node architecture
\end{itemize}

We can illustrate this with our QCD (high energy physics) calculations on the 
hypercube.  The original code developed for the Cosmic Cube in 1983 was run 
with little change on the later Mark~II (JPL) and commercial NCUBE-1 
hypercubes.  However, substantial changes were needed when it was used on the 
more powerful (500 megaflops on 128 nodes) Mark~III (JPL) hypercube.  The 
relatively higher communication latency implied substantial rearrangement of 
the message passing and a reordering of the algorithm to allow communication 
to be blocked into a smaller number of larger messages.  The poor compiler 
required assembly language coding of key parts of the node program to exploit 
the WEITEK~XL vector floating point unit.  We never did exploit the possible 
overlap of communication and calculation which was available on the Mark~III. 
This would have increased performance by 25\% and was possible in principle, 
but clumsy to implement.  We believe that these optimizations in (1) above, 
can be performed by appropriate compilers, and this is a minimal goal for the 
higher level-three software systems.

There are many message passing systems including:
\begin{center}
\begin{tabbing}
Reactive Kernel/Cosmic Environment \= (Cornell, Ohio State) \kill
OCCAM \> (Inmos) \\
Reactive Kernel/Cosmic Environment \> (Caltech) \\
Express \> (ParaSoft, Caltech) \\
Trollius \> (Cornell, Ohio State) \\
Tiny \> (Edinburgh) \\
Vertex \> (NCUBE) \\
NX \> (INTEL)
\end{tabbing}
\end{center}

These offer comparable functionality with different tradeoffs in the area of 
portability, performance and collective (higher level) communication support. 
The latter includes broadcast and its generalizations, and the various 
primitives for data shuffling developed particularly by \cite{Ho:86a} and 
\cite{Ho:89f}, and others \cite{Fox:86c}, \cite{Fox:88g}, \cite{Fox:88h}, 
\cite{Stout:87a}, \cite{Valiant:88a}.  Further work is needed to define the 
more sophisticated primitives, but it should soon be possible to agree on a 
standard message passing interface which would provide a portable base on 
which to build the higher level software.

As illustrated in Figure~2, we view software as a map of a problem onto a 
computer.  As such, it is sensitive to the architecture (structure) of both 
problem and computer.  My goal would be software specialized (optimized) for 
a broad class of problem architectures which is designed to run portably on 
all parallel architectures.  We will illustrate this idea a little later.

\begin{figure}
\vspace*{3.5in}
\caption{Computation and simulation as a series of maps.}
\end{figure}

We would like to develop a classification of problem architectures and 
present here a simple division of problems into three classes; each of which 
presents different software challenges and solutions (at level three).  
Previously, we have introduced the concept of the spatial and temporal 
aspects of a problem.  We can, rather, generally view a computation as an 
algorithm performed on the many elements of a data set; the algorithm is 
repeated corresponding to an increasing iteration count or the simulation of 
the data set for increasing time.  The structure (often called computational 
graph) of the data set and algorithm we will refer to as the spatial structure 
of the problem.  We call the nature of iteration, recursion, or time 
simulation, as the temporal structure.  We described in \cite{Fox:88b} three 
distinct temporal structures; synchronous, loosely synchronous and 
asynchronous.  Synchronous problems are characterized by identical algorithms 
being applied to all points in their data set.  Loosely synchronous problems 
do not have a tight lockstep with microscopic synchronization, but rather 
macroscopic time synchronization.  An example is a simulation evolving from 
$t$ to $t + \delta t, t + 2\delta t$\ with different algorithms at each data 
point, but natural synchronization at the beginning and end of each time 
step. Asynchronous problems have no natural synchronization in the time 
evolution of the different data points.

In table~2, we introduce three problem architectures which are imaginatively 
labelled Classes I, II and III.  These classes are not clearly defined and 
merge into each other.  Further, a given application may consist of several 
components which fall into different classes.  From our point of view, 
Fortran~90 is not regarded as the natural language for SIMD computers.  
Rather, it is the natural language for synchronous (SIMD) Class~I
problems \cite{Fox:91d}.  One can, in fact, implement this language 
efficiently on SIMD and MIMD machines.  This portability between SIMD and 
MIMD has been implemented for the analogous language $\rm C^\ast$ 
\cite{Quinn:90a}, the functional language crystal \cite{Chen:88b}, and we are 
currently implementing a Fortran~90 to F77+MP (MP = message passing) 
preprocessor for MIMD machines \cite{Wu:91a}.  We expand on this later. 

\begin{table}
\vspace*{3.0in}
\caption{Three Problem Architectures}
\end{table}

\nocite{Berryman:91a}
\nocite{Chandy:90a}
\nocite{Foster:90a}
\nocite{Furmanski:91a}
\nocite{Gelernter:89a}
\nocite{Saltz:87a}
\nocite{Saltz:90a}
\nocite{Salmon:90a}
\nocite{Williams:89b}

Class~III problems consist of irregular problems with no time 
synchronization.  These are, in principle, very hard to parallelize as is 
illustrated by the major efforts devoted to parallelizing event driven 
simulations \cite{Wieland:89a}.  This class can be parallelized when the 
parts are independent or loosely coupled and so synchronization overheads 
are small.  The loose coupling makes these problems suitable for distributed 
systems (e.g., networks of workstations) which have lower communication 
bandwidth and higher latency than the dedicated parallel machines.  The 
powerful (and hence higher software overhead) programming environments for 
distributed computers are natural here; an object oriented formalism is one 
obvious possibility.

The situation with Class~II problems is less clear and a major research area 
for us.  We have described in \cite{Fox:89t} the astrophysical N-body 
simulation with the $N\log N$ Barnes-Hut clustering method.  It is not easy 
either to implement on SIMD machines or to code in Fortran~90.  We can 
understand this as stemming from the fact that the algorithm's data structure 
is an irregular dynamic tree.  This cannot be represented in Fortran~90 which 
only has array and vector data structures.  We are currently investigating if 
adding extra (e.g., tree) data structures to Fortran~90 will allow one to 
address the N-body problem and other applications (e.g., quicksort) with a 
recursive or divide and conquer architecture.  Saltz and his colleagues at 
NASA ICASE have shown that Fortran can be used for irregular finite element 
(more generally sparse matrix) problems with extensions to handle pointers 
\cite{Berryman:91a}, \cite{Saltz:90a}.  Similarly, Fortran~90 with vector 
value subscripts can handle at least some of these problems 
\cite{Johnsson:90a}, \cite{Mathur:89a}; correspondingly, the Connection 
Machine can run these problems successfully \cite{Fox:90p}.  We can 
understand these successes as reflecting that an array, albeit an array of 
pointers (addresses), is an appropriate data structure.  Fortran~90D is 
Fortran augmented by those possible additional data structures and parallel 
decomposition constructs will have some general utility.  We expect that most 
(scientific) problems in Class~I and II will be elegantly expressed in 
Fortran~90D.  With similar extensions implemented as ``user hints'', we 
should be able to parallelize F77 codes in these classes.  Ken Kennedy's group
at Rice is building this Fortran~77D compiler for distributed memory parallel 
machines \cite{Fox:91e} \cite{Wu:90b}; this will either produce directly 
F77+MP or possibly more usefully Fortran~90D. 

CMFortran implements the essential parallel constructs in Fortran~90 
and also the {\em forall\/} statement.  We include the latter in Fortran~90D 
and can illustrate its importance with a typical chemical reaction 
\cite{Wu:90a}, \cite{Hipes:90a} or potential calculation.  This involves an 
``embarrassingly parallel'' (Class~III) calculation of the values of matrix 
elements combined with (Class~I) matrix algebra (multiplication, inversion and 
eigenvalues).  These two steps may be represented respectively by the {\em 
forall\/} and natural parallel array constructs in Fortran~90D.  We need 
decomposition statements in Fortran~90D and these are extensions of the LAYOUT 
and ALIGN commands of CMFortran.  These instruct the compiler how to break up 
(either statically or dynamically) the arrays over the nodes \cite{Fox:91e}. 

Above, we have described how Fortran~90 provides a possible high level 
language for Class~I, and extensions may extend its utility into Class~II.  A 
major goal is to examine further applications to understand which features 
cannot be expressed in one of these ways and so provide a test suite of 
``skeletons in the programming language closet''.  These (like the irregular 
finite element and N-body problems) are the applications for which we need 
new languages.  We do not really need new ways of expressing matrix 
multiplication and Laplace's equation; what we know now is sufficient.  
Nevertheless, many new language projects are tested and perhaps motivated by 
these unrealistic problems.  I hope that our classification of problems and 
its refinement will focus the development of parallel languages and 
environments on the difficult problems that need to be solved.  

Many problems are best regarded as built of several modules which can be
considered as belonging to one of the three classes discussed above.
This more general and important case is discussed in \cite{Fox:91c}.
We conclude by illustrating the parallelization of Fortran~90 for four small 
Class~I problems.

\section{Experiments with Fortran~90 on MIMD Multicomputers}

These results come from the joint project \cite{Wu:90b} between Rice 
University (Ken Kennedy's group) and my research group at Syracuse.  We are 
building a library of problems designed to test languages and parallelizing 
compilers.  For each problem, we build several versions; in particular,
\begin{description}
\item [P1)] Fortran 77
\item [P2)] Fortran 90D (CMFortran)
\item [P3)] Hand coded Fortran 77 + Message Passing
\item [P4)] ``What we think a parallelizing compiler could produce for a MIMD 
multicomputer from Fortran~77 (P1)''
\item [P5)] ``What we think a parallelizing compiler could produce for a MIMD 
multicomputer from Fortran~90 (P2)''
\end{description}

We are using the results of these experiments to build the compilers that 
realize our expectations for P4) and P5).  The Fortran~90D compiler is a 
collaboration with the ParaSoft Corporation.

Our results in Tables~3A, 3B, 3C, 3D are only preliminary but already 
interesting.

\begin{center}
\begin{tabular}{||l|ccccc||}
\hline
&\multicolumn{5}{|c||}{Execution Time (Seconds)} \\
&\multicolumn{5}{|c||}{v.\ Number of Processors} \\
&\multicolumn{5}{|c||}{on iPSC2 Hypercube} \\
&\multicolumn{1}{|c}{1}&\multicolumn{1}{c}{2}&\multicolumn{1}{c}{4}&
\multicolumn{1}{c}{8}&\multicolumn{1}{c||}{16} \\
\hline
\medStrut
P3) Original Hand & 85.4&58.1&31.1&16.0&8.42 \\
\ \ \ \ \ Coded F77+MP &&&&& \\
&&&&& \\
P5) F77+MP from   & 80.0&50.2&26.6&13.8&7.72 \\
\ \ \ \ \ Fortran 90   &&&&& \\
&&&&& \\
P3) Revised Hand  & 73.4&50.1&26.9&13.8&7.53 \\
\ \ \ \ \ Coded F77+MP &&&&& \\
\hline
\end{tabular}
\end{center}
\begin{center}
Table 3A.\ Gaussian Elimination ($256\times 256$ matrix)
\end{center}

\begin{center}
\begin{tabular}{||l|ccccc||}
\hline
&\multicolumn{5}{|c||}{Execution Time (Seconds)} \\
&\multicolumn{5}{|c||}{v.\ Number of Processors} \\
&\multicolumn{5}{|c||}{on iPSC2 Hypercube} \\
&\multicolumn{1}{|c}{1}&\multicolumn{1}{c}{2}&\multicolumn{1}{c}{4}&
\multicolumn{1}{c}{8}&\multicolumn{1}{c||}{16} \\
\hline
\medStrut
P3) Hand Coded & "71.7&35.9&17.9&"8.98&4.83 \\
\ \ \ \ \ F77+MP &&&&& \\
&&&&& \\
P5) F77+MP from & 139.6&69.1&35.5&18.1"&9.40 \\
\ \ \ \ \ Fortran 90   &&&&& \\
\hline
\end{tabular}
\end{center}
\begin{center}
Table 3B.\ N-body Simulation (1024 Particles)
\end{center}


\begin{center}
\begin{tabular}{||l|ccccc||}
\hline
&\multicolumn{5}{|c||}{Execution Time (Seconds)} \\
&\multicolumn{5}{|c||}{v.\ Number of Processors} \\
&\multicolumn{5}{|c||}{on iPSC2 Hypercube} \\
&\multicolumn{1}{|c}{1}&\multicolumn{1}{c}{2}&\multicolumn{1}{c}{4}&
\multicolumn{1}{c}{8}&\multicolumn{1}{c||}{16} \\
\hline
\medStrut
P3) Original Hand & 36.8&23.3"&14.2"&8.32&4.82 \\
\ \ \ \ \ Coded F77+MP &&&&& \\
&&&&& \\
P3) Optimized Hand & 13.0&"6.67&"3.42&1.75&0.91 \\
\ \ \ \ \ Coded F77+MP &&&&& \\
&&&&& \\
P5) Optimized F77+MP & 18.8&10.1"&"5.36&2.84&1.50 \\
\ \ \ \ \ from Fortran 90 &&&&& \\
\hline
\end{tabular}
\end{center}
\begin{center}
Table 3C.\ Fast Fourier Transform (16384 Points)
\end{center}

\begin{center}
\begin{tabular}{||l|c|c|c||}
\hline
\multicolumn{1}{||c}{Implementation}&\multicolumn{1}{|c}{Size}&
\multicolumn{1}{|c}{Machine}&\multicolumn{1}{|c||}{Performance} \\
&\multicolumn{1}{|c|}{of Code}&&\multicolumn{1}{|c||}{(megaflops)} \\
&\multicolumn{1}{|c|}{(lines)}&& \\
\hline
\medStrut
\ \ \ \ \ Original C Code & 1500 & CRAY X-MP & $\sim$ 1 \\
&&(1 C.P.U.) & \\
&&& \\
P2) Fortran 90 & "600 & CM-2 & 66\phantom{.}" \\
&&(8 K) & \\
&&& \\
P5) F77 Produced by Hand & 1500 & CRAY Y-MP & 20\phantom{.}" \\
\ \ \ \ \ from Fortran 90 && (1 C.P.U.) & \\
&&& \\
P5) F77+MP by Hand & 1650 & NCUBE-1 & "3.3 \\
\ \ \ \ \ from Fortran 90 && 16 node & \\
&& hypercube & \\
&&& \\
&& NCUBE-2 & 20\phantom{.}" \\
&& 16 node & \\
&& hypercube & \\
&&& \\
&& INTEL i860 & 80\phantom{.}" \\
&& 16 node & \\
&& hypercube & \\
\hline
\end{tabular}
\\
Table 3D.\ Climate Modelling Code \protect\cite{Keppenne:90a}
\end{center}

For a problem with a simple topology, LU decomposition in Table~3A, the 
Fortran~90 code produced essentially as good a code as the direct Fortran~77+ 
Message Passing.  Indeed, the ``automatic'' Fortran~90 procedure pointed out a 
possible improvement in our handed codes F77+MP; this is the difference 
between lines one and three of Table~3A.  In Table~3B, our current automatic 
approach for the N-body problem loses a factor of two compared to the best 
parallel implementation; this is due to inefficient communication and one may 
need to change the Fortran~90 implementation to allow the compiler to optimize 
this. In this sense, the user will need to understand some issues of 
parallelism, even when writing ``explicitly parallel'' code as with 
Fortran~90.  Note the example in Table~3B is the simple $O(N^2)$ algorithm and 
not the more interesting and challenging $O(N(\log N))$ approach discussed 
earlier.  In Table~3C, we find a 50\% degradation in performance on the FFT 
for the Fortran~90 approach.  This indicates that Fortran~90 does not 
optimally support the hierarchical data structures found in the FFT.  As 
already discussed, we expect that the final Fortran~90D language will include 
new data structures---over and above the arrays and vectors in Fortran~90.  We 
already mentioned a possible ``tree'' data structure needed for the Class~II 
clustering approach for the N-body problem. 

Finally in Table~3D, we come to a ``real'', albeit small in code size, 
problem.  The original climate modelling code has been used in production 
\cite{Keppenne:89a} on CRAY and SUN computers.  We saw in this project an 
interesting division of labor.  The first rewriting from C to Fortran~90 was 
performed by the application expert.  The further conversions into Fortran~77 
and Fortran~77+ message passing were performed by ``computer scientists'' 
without deep knowledge of the application \cite{Keppenne:90a}.  In this case, 
we believe that no automatic method could have parallelized the original C 
code, but that our planned automatic approach would be able to perform the 
MIMD parallelization from Fortran~90.  The result of this project is a 
portable code running well on the CRAY, Connection Machine and hypercubes.  
Note that we even improved the sequential performance (line one vs. line
three of Table~3D) by an order of magnitude.  The original C code made 
extensive use of pointers which had several repercussions.  It made 
vectorization hard on the CRAY; it made the code impossible to automatically 
parallelize as the ``structure of problem'' was expressed in dynamic pointer 
values; it made the code hard to port except by the domain expert. 

Our initial experiments are sufficiently encouraging that we believe that a 
language like Fortran~90 will become an efficient vehicle for Class~I 
applications.  We also hope that it can be extended with higher level data 
structures to accommodate the more complex ``problem architectures'' seen in 
Class~II problems.

\section{Computational Science Education}

The emergence of computation as a fundamental methodology implies major 
changes in our educational system which will challenge our universities, 
community colleges, and schools in the next decade \cite{Fox:90o}.  Computers 
are being used in schools, even at the kindergarten level.  This is 
necessary, but not sufficient.  We need not only to teach students how to 
program, but instill the understanding that computing is fundamental and will 
change the nature of both their careers and their day-to-day life.  
Computing, like the traditional reading, writing and arithmetic is a key 
enabling skill whose use and {\em understanding\/} permeates all other 
activities.  Looking at applicants for graduate school (in Physics at 
Caltech), I saw few students who viewed computers as anything but a rather 
tiresome tool.  Why is this when most of them come from prestigious 
undergraduate institutions where the very latest computers abounded?  
The reason may be that such students are typically not given any courses that 
treat computation as fundamental and exciting.  They are taught by faculty 
whose vision of computing comes from a time when computers were a useful but 
unexciting tool.  This will change.

The Federal High Performance Computing Initiative developed the concept of 
interdisciplinary teams to tackle the grand challenges and their 
implementations on parallel machines.  This idea was part of my Caltech 
Concurrent Computation Program but interestingly enough, something else 
happened as well.  Namely, the majority of the research was performed by 
interdisciplinary individuals who combined the skills of a computer scientist 
with those of an application area such as Physics or Chemistry.  It is this 
phenomenon that inspired much of my thoughts on computational science.  You 
may argue that ``jack of all trades, master of none'' implies that 
interdisciplinary scientists are not competitive.  I believe this is a valid 
concern, but the negative conclusion can be avoided.  I propose that 
Computational Science should be an interdisciplinary program with degrees 
given in the traditional fields.  Undergraduates, Masters or Ph.D. students 
will get degrees in the Computational Science Program such as
\begin{itemize}
\item ``Undergraduate degree in Physics in the Computational Science Program''
(in my point of view, this is a long way of saying an undergraduate degree in 
Computational Physics)
\item ``Masters in Chemistry with a minor in Computer Science''
\item ``Ph.D. in Computer Science with a Masters Degree in Economics''
\end{itemize}

Computational Science students will need new curricula, and this will require 
cooperation and understanding from the traditional disciplines.  For instance,
the requirements for a degree in Physics within the Computational Science 
Program may require fewer base Physics courses than the traditional Physics 
degree, with this reduction made up by a set of computational courses.  
There are typically electives in any set of course requirements and so these 
reductions in the base (in our example, Physics) academic area need not be 
significant.  In some institutions and some departments, these changes may 
not be accepted, and a different implementation of Computational Science will 
be needed.  We must gain experience as to what works and what doesn't.  
Students will enter a program in Computational Science with a variety of 
aspirations and skills.  For instance, freshman undergraduates may initially 
be interested in Physics, but later decide to graduate in Computer Science.  
We need a good set of courses to accommodate the different initial skills and 
allow a student to switch from a focus on Computer Science to one on an 
application area---or vice versa.  Not only are such curricula in their 
infancy but, as found while teaching at Caltech, the lack of relevant books 
is a severe handicap.  We will develop the curricula, books and the needed 
educational software.

A Chemist graduating from the Computational Science program will be well 
grounded in Chemistry, but have a broad knowledge of Computer Science.  The 
latter  will enable the Chemist to use computers and new computer science 
techniques more effectively than a Chemist without the computational science 
background. Thus, he or she will be a better Chemist, and in this way the 
interdisciplinary scientist is not handicapped.  A Computer Scientist 
graduating in our new program will have a sound basis in Computer Science and 
an understanding of the computational needs and algorithms of one or more 
application areas.  The latter knowledge will enable our Computer Scientist to 
develop better compilers, debuggers and visualization aids because he or she 
understands the needs of the applications. 

Thus, I believe that Computational Science is an exciting and viable area 
which can be implemented within the existing academic framework.  I intend to 
pursue this vigorously at Syracuse.  In particular, we will develop the new 
courses (definition, notes, books, software).  We will work with the 
international community to establish common guidelines for the teaching of 
Computational Science and build a consensus that it is important.

\section{Conclusions}

Technology has opened several new opportunities, both in research and 
education.  We are at the beginning of changes which will have profound 
implications for academia, industry and society.  Parallel computing, 
discussed here, is only one part of this revolution.

\vspace{\bigskipamount}
\thanks{I would like to thank Paul Messina 
and his colleagues, especially Almerico Murli from the University of Naples, 
for their warm hospitality and an excellent conference.  This work was 
supported by the Department of Energy:  Applied Mathematical 
Sciences---Grant:\ DE-FG03-85ER25009; Joint Tactical Fusion Program Office; 
and the National Science Foundation under Cooperative Agreement No.
CCR-8809165 --- the Government has certain rights in this material.}

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