\input /home/sushi/kea/vax/macros.tex
\input /home/sushi/kea/bjfonts.tex
\baselineskip=14pt
\vsize=9.25truein
\hoffset=-.2truecm
\tolerance=10000
\def\starline{\hbox to \hsize{* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *}}
\centerline{\twelvepoint\bf California Institute of Technology}
\smallskip
\centerline{\twelvepoint\bf C$^3$P Reports}
\smallskip
\centerline{\twelvepoint\bf January 1 -- December 31, 1988}
\bigskip
\bigskip
\vbox{\par\noindent{\twelvepoint\bf LU Decomposition of Banded Matrices and 
the Solution of Linear Systems on Hypercubes}
\par\noindent
{\bf T. Aldcroft, A. Cisneros, G. C. Fox, and W. Furmanski, D. W. Walker}
\par\noindent
$\rm C^3P-348b$\ \ \ \ \ \ \ (Short Code:  Aldcroft:88a)
\par
We describe the solution of linear systems of equations, $Ax=b$, on 
distributed-memory concurrent computers whose interconnect topology contains a 
two-dimensional mesh.  $A$ is assumed to be an $M\times M$ banded matrix.  The 
problem is generalized to the case in which there are $n_b$ distinct right-
hand sides, $b$, and can thus be expressed as $AX=B$, where $X$ and $B$ are 
both $M\times n_b$ matrices.  The solution is obtained by the LU decomposition 
method which proceeds in three stages:  (1) LU decomposition of the matrix 
$A$, (2) forward reduction, (3) back substitution.  Since the matrix $A$ is 
banded a simple rectangular subblock decomposition of the matrices $A$, $X$, 
and $B$ over the nodes of the ensemble results in excessive load imbalance.  
A scattered decomposition is therefore used to decompose the data.  The 
sequential and concurrent algorithms are described in detail, and models of 
the performance of the concurrent algorithm are presented for each of the 
three stages of the algorithm.  In order to ensure numerical stability the 
algorithm is extended to include partial pivoting.  Performance models for the 
pivoting case are also given.  Results from a 128-node Caltech/JPL Mark~II 
hypercube are presented, and the performance models are found to be a good 
agreement with these data.  Indexing overhead was found to contribute 
significantly to the total concurrent overhead.}

\bigskip\starline\bigskip
\vbox{\par\noindent
{\bf Transparencies} from a poster session by T. Aldcroft {\it et
al.}, entitled ``LU Decomposition of Banded Matrices and the Solution of
Linear Systems on the Hypercube'', presented at the Third Conference on
Hypercube Concurrent Computers and Applications, January 1988.
C$^3$P-508 (Short Code:  Aldcroft:88b)}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf The Use of Parallel Logic Programming in 
CAD/CAM Applications}
\par\noindent
{\bf L. Alkalaj and A. H. Bond}
\par\noindent
$\rm C^3P-682$\ \ \ \ \ \ \ (Short Code:  Alkalaj:88a)
\par
A study of the use of concurrent prolog for programming intelligent CAD/CAM 
systems is reported.}
\par
The work has implications for CAD/CAM workstation design, specification 
languages for CAD/CAM, and CAD/CAM programming methodology.
\par
Intelligent CAD/CAM functions were defined by exergesis from an existing set 
of intelligent CAD/CAM functions written in Prolog.
\par
Two of these, viz.
\item{1.}Global satisfaction of constraints over a geometric structure.
\item{2.}Layered feature generation
\par
were analyzed, and parallel logic programming descriptions of them designed.  
These descriptions used the powerful programming techniques possible in 
Concurrent Prolog.  They were implemented in Flat Concurrent Prolog and run on 
a serial computer.
\par
The main conclusion reached was that parallel programming techniques, possible 
in Concurrent Prolog, are very suitable for programming of intelligent CAD/CAM 
functions, and lead to succinct, understandable and efficient programs.
\par
Therefore, a promising potential strategy for providing intelligent CAD/CAM 
workstations is to use a parallel workstation, and Concurrent Prolog.

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf The Prime Factor Non-binary Discrete 
Fourier Transform and use of Crystal\_Router as a General Purpose 
Communication Routine}
\par\noindent
{\bf J. S. Kim, G. C. Fox, G. Aloisio, and N. Veneziani}
\par\noindent
$\rm C^3P-523$\ \ \ \ \ \ \ (Short Code:  Aloisio:88a)
\par
We have implemented one of the Fast Fourier Transform algorithms, the Prime 
Factor algorithm (PFA), on the hypercube.  On sequential computers, the PFA 
and other discrete Fourier transforms (DFT) such as the Winograd algorithm 
(WFA) are known to be very efficient.  However, both algorithms require full 
data shuffling and are thus challenging to any distributed memory parallel 
computers.  We use a concurrent communication algorithm, called the {\it 
Crystal\_Router\/} for communicating shuffled data.  We will show that the 
speed gained in reduced arithmetic compared to binary FFT is sufficient to 
overcome the extra communication requirement up to a certain number of 
processors.  Beyond this point the standard Cooley-Tukey FFT algorithm has the 
best performance.  We comment briefly on the application of the DFT to signal 
processing in synthetic aperture radar (SAR).}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Stability-Capacity Diagram of a Neural 
Network with Ising Couplings}
\par\noindent
{\bf E. Amaldi and S. Nicolis}
\par\noindent
$\rm C^3P-679$\ \ \ \ \ \ \ (Short Code:  Amaldi:88a)
\par
The stability-capacity diagram of a fully connected neural network, whose 
couplings take the values 1 and $-1$ with equal probability, is determined 
numerically.  Two different optimization methods (simulated annealing and tabu 
search) are used and their relevant features are discussed.  Clear evidence of 
replica symmetry breaking is found.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf FORTRAN CUBIX: Definition and 
Implementation}
\par\noindent
{\bf Ian G. Angus}
\par\noindent
$\rm C^3P-575$\ \ \ \ \ \ \ (Short Code:  Angus:88a)
\par
An I/O facility for FORTRAN programmers is defined for use with the 
Crystalline Operating system and the CUBIX I/O library.  All of the external 
I/O switches and file types of the F77 standard FORTRAN are supported from 
within the nodes of a Hypercube.  This is expected to both ease the 
development of FORTRAN applications and to greatly facilitate the conversion 
of existing sequential programs into concurrent versions.}
\par
The implementation is portable to most machines that have both a C and 
FORTRAN compiler.  The FORTRAN compiler is not required to have the ability to 
parse I/O statements.  The only nonportable components of this package are, 
the interface codes to bridge between C and FORTRAN, and the implementation of 
your favorite FORTRAN extensions.

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf NSIM: A Hypercube Simulator}
\par\noindent
{\bf Ian G. Angus}
\par\noindent
$\rm C^3P-654$\ \ \ \ \ \ \ (Short Code:  Angus:88b)
\par
We describe a software package that provides a simulated environment for 
development and execution of applications on a Hypercube.  The provided 
software is specialized to a Hypercube running the CrOS3 operating system; 
however, we will indicate how one can implement a wide variety of alternative 
topologies and/or operating systems.  A number of utilities are also provided 
to help enhance the user's productivity.  This version of the simulator runs 
under either UNIX or under VMS.}

\bigskip\starline\bigskip
\vbox{\par\noindent
{\bf Transparencies} from a poster session by J. Apostolakis {\it et
al.}, entitled ``Statistical Gravitational Lensing'', presented at the Third 
Conference on Hypercube Concurrent Computers and Applications, January 1988.
C$^3$P-557 (Short Code:  Apostolakis:88a)}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Supercomputer Applications of the
Hypercube}
\par\noindent
{\bf J. Apostolakis, C. Baillie, R. W. Clayton, H.-Q. Ding, J. Flower,
G. C. Fox, T. D. Gottschalk, B. H. Hager, H. B. Keller, A. K. Kolawa, S.
W. Otto, T. Tanimoto, E. F. Van de Velde, J. Barhen, J. R. Einstein, and
C. C. Jorgensen}
\par\noindent
C$^3$P-550\ \ \ \ \ \ \ (Short Code:  Apostolakis:88b)
\par
This is chapter 11 in a book summarizing the highlights of a
supercomputing conference held in 1987.  It consists of an overview of
hypercube work by the Caltech Concurrent Computation Program with the
general lessons learned --- these cover hardware, software and
applications.  Specific parallel applications are covered with
multi-grid algorithms, lattice gauge theories in physics, neural
networks and robotics, geophysics, and multi-target tracking by Kalman
filters.}

\bigskip\starline\bigskip
\vbox{\par\noindent
{\bf Transparencies} from a poster session by J. Apostolakis {\it
et al.}, entitled ``Lattice Gauge Theory with Fermions'', presented at
the Third Conference on Hypercube Concurrent Computers and Applications,
January 1988.  C$^3$P-556 (Short Code:  Apostolakis:88c)}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Statistical Gravitational Lensing on the 
Mark~III Hypercube}
\par\noindent
{\bf John Apostolakis and Christopher S. Kochanek}
\par\noindent
$\rm C^3P-581$\ \ \ \ \ \ \ (Short Code:  Apostolakis:88d)
\par
We describe a parallel algorithm for the nonlinear optics problem of 
gravitational lensing.  The method is a ``ray-tracing'' method which studies 
the statistical properties of the image population associated with a 
gravitational lens.  A parallel computer is needed because the spatial 
resolution requirements of the problem make the program too large to run on 
conventional machines.  The program is implemented on the Mark~III hypercube 
to take maximum advantage of this machine's 128~Mbytes of memory.  The 
concurrent implementation uses a scattered domain decomposition and the 
CrOs~III communications routines.  The communications in the problem are so 
irregular that no completely satisfactory implementation was made in terms of 
the execution time of the program:  the maximum speed-up relative to a 
sequential implementation is a factor of four on a 32-node machine.  However, 
the goal of efficiently using all of the Mark~III's memory was achieved, and 
the execution time was not the limiting factor in the problem.  If the crystal 
router were used, the implementation would be much more efficient.  
Development of the program was terminated at this stage, however, because we 
were able to extract the physics of interest without the more sophisticated 
communications routines.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf A Comparison of the CM with the DAP for 
Lattice Gauge Theory}
\par\noindent
{\bf Clive F. Baillie and G. Stuart Pawley}
\par\noindent
$\rm C^3P-530$\ \ \ \ \ \ \ (Short Code:  Baillie:88b)
\par
Lattice gauge theory is one of the most challenging large-scale scientific 
computations: a state of the art calculation requires at least $10^{14}$ 
floating-point operations, necessitating the use of advanced architecture 
massively parallel computers such as the Connection Machine (CM) made by 
Thinking Machines Corporation (TMC), and the Distributed Array Processor (DAP) 
made in the past by International Computers Limited (ICL) and currently by 
Active Memory Technology (AMT).  The most important gauge theory to be solved 
is that describing the sub-nuclear world of high energy physics:  Quantum 
Chromo-dynamics (QCD).  The simplest example of a gauge theory is Quantum 
Electro-dynamics (QED), the theory which describes the interaction of 
electrons and photons.  Simulation of QCD requires computer software very 
similar to that for the simpler QED problem.  Code for QED has been written, 
tested and benchmarked for the CM, and this is compared with similar code for 
the DAP.  Experience with the DAP allows us to predict performances for QCD 
code on the CM, showing the latter to be a very serious proposition for such 
large-scale scientific computations.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Comparing Communication in Concurrent 
Processor Operating Systems}
\par\noindent
{\bf Clive F. Baillie}
\par\noindent
$\rm C^3P-569$\ \ \ \ \ \ \ (Short Code:  Baillie:88c)
\par
I have developed a simple program which exercises communication in concurrent 
processor operating systems.  It allows comparison of both the programming 
model used in the operating system and the efficiency of its implementation.  
I have run this program with both loosely synchronous and multi-tasking 
operating systems on the Caltech/JPL Mark~II Hypercube and the BBN Butterfly.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf QED on the Connection Machine}
\par\noindent
{\bf Clive Baillie, S. Lennart Johnsson, Luis Ortiz, and G. Stuart Pawley}
\par\noindent
$\rm C^3P-572$\ \ \ \ \ \ \ (Short Code:  Baillie:88d)
\par
Physicists believe that the world is described in terms of gauge theories.  A 
popular technique for investigating these theories is to discretize them onto 
a lattice and simulate numerically by a computer, yielding so-called lattice 
gauge theory.  Such computations require at least 10$^{14}$ floating-point 
operations, necessitating the use of advanced architecture supercomputers such 
as the Connection Machine made by Thinking Machines Corporation.  Currently, 
the most important gauge theory to be solved is that describing the sub-
nuclear world of high energy physics: Quantum Chromo-dynamics (QCD).  The 
simplest example of a gauge theory is Quantum Electro-dynamics (QED), the 
theory which describes the interaction of electrons and photons.  Simulation 
of QCD requires computer software very similar to that for the simpler QED 
problem.  Our current QED code achieves a computational rate of 1.6 million 
lattice site updates per second for a Monte Carlo algorithm, and 7.4 million 
site updates per second for a microcanonical algorithm.  The estimated 
performance for a Monte Carlo QCD code is 200,000 site updates per second (or 
5.6~Gflops/sec).}

\bigskip\starline\bigskip
\vbox{\par\noindent
{\bf Transparencies} from a poster session by C. Baillie {\it et
al.}, entitled ``A Comparison of Multiple-target Tracking Performance of
Difference Concurrent Computers'', presented at the Third Conference on
Hypercube Concurrent Computers and Applications, January 1988.
C$^3$P-547 (Short Code:  Baillie:88e)}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Comparisons of Concurrent Tracking on 
Various Hypercubes}
\par\noindent
{\bf C. F. Baillie, T. D. Gottschalk, and A. Kolawa}
\par\noindent
$\rm C^3P-568$\ \ \ \ \ \ \ (Short Code:  Baillie:88f)
\par
The concurrent multi-target tracking code is ported to and run on the Intel 
iPSC and Ncube hypercubes.  The (minor) difficulties in this porting are 
noted.  The biggest single problem in running the tracking program is found to 
be the rather limited node memories on the iPSC and Ncube machines.  Timing 
results for the analysis of a sample threat on the iPSC,  Ncube and Mark~III 
hypercubes are presented.  The relative performances of the various machines 
are found to be consistent with prior expectations.  A fairly large sample 
scenario is investigated using 4 through 8-dimensional Ncube configurations, 
and variations of Ncube performance for differing levels of CrOS porting are 
examined.  Initial results of running the tracking program on the BBN 
Butterfly are also presented.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Lattice QCD --- As A Large Scale 
Scientific Computation}
\par\noindent
{\bf Clive F. Baillie and David W. Walker}
\par\noindent
$\rm C^3P-641$\ \ \ \ \ \ \ (Short Code:  Baillie:88g)
\par
Lattice QCD (Quantum Chromo-dynamics) is one of the most computationally 
intensive large scale scientific computations.  It can therefore be made to 
run efficiently on any computer.  As part of the Concurrent Supercomputing 
Initiative at Caltech (CSIC), we have benchmarked lattice QCD on several MIMD 
computers:  NCUBE, Caltech/JPL Mark~III, and Intel iPSC/1 hypercubes 
(distributed memory computers); Sequent Balance and Symmetry, Alliant FX/8, 
and BBN Butterfly Plus (shared memory computers).  Herein we explain the 
computations required for lattice QCD, describe and contrast the different 
concurrent supercomputers used, and present the results of our lattice QCD 
benchmarks.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Spin Operators for the 3-d Ising
Model}
\par\noindent
{\bf Clive Baillie and Kenneth Barish}
\par\noindent
$\rm C^3P-648$\ \ \ \ \ \ \ (Short Code:  Baillie:88h)
\par
We are interested in performing a Monte Carlo Renormalization Group
(MCRG) calculation for the 3-d Ising model.  This technique, suggested
by Ma in 1976 and improved by Swendsen in 1979, combines Monte Carlo
(MC) simulations of statistical-mechanical models with a renormalization
group (RG) analysis of their critical properties.  Of course, this
calculation has been done before but that was almost five years ago.
Therefore, we are repeating it today, with an order of magnitude more
computing power, in order to better determine the Ising model's critical
properties.  In particular, we wish to check hyperscaling.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Visit to SCRI at FSU to Benchmark
ETA$^{10}$}
\par\noindent
{\bf Clive F. Baillie}
\par\noindent
$\rm C^3P-657b$\ \ \ \ \ \ \ (Short Code:  Baillie:88i)
\par
To benchmark three complete scientific codes --- QCD, Tracker and Vortex
--- and two common linear algebra computations --- LU Decomposition and
Matrix Multiply --- on the ETA$^{10}$ located in the Supercomputer
Computations Research Institute (SCRI) at Florida State University (FSU)
in one week.}
\par
This was actually accomplished in August, however in October/November I
re-did QCD (with a small correction and an extra data set), Tracker and
Vortex (with an extra data set each), and LU Decomposition and Matrix
Multiply (both corrected and with full data sets).

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Using a Shared Memory Computer as a 
Distributed Memory Computer}
\par\noindent
{\bf Clive F. Baillie}
\par\noindent
$\rm C^3P-658$\ \ \ \ \ \ \ (Short Code:  Baillie:88j)
\par
In this paper I discuss how to use a shared memory machine, such as the BBN 
Butterfly, as a distributed memory machine, such as a hypercube.  To show that 
this is indeed possible I have implemented the Crystalling Operating System 
(CrOS) developed by Caltech for hypercubes on the Butterfly.  Hence programs 
written in terms of CrOS for the hypercube can run {\it unchanged\/} on the 
Butterfly --- I give an example of this being done.  For applications with 
localized data this is efficient as well as portable.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf QCD with Dynamical Wilson Fermions}
\par\noindent
{\bf Clive F. Baillie, Rajan Gupta, Gregory W. Kilcup, Apoorva Patel, and 
Stephen Sharpe}
\par\noindent
$\rm C^3P-674$\ \ \ \ \ \ \ (Short Code:  Baillie:88k)
\par
We presents first results of a study of QCD with two flavors of dynamical 
Wilson fermions using the exact Hybrid Monte Carlo Algorithm (HMCA).  We 
evaluate the performance of the algorithm and its potential for large scale 
computations.  Results for the finite temperature transition for $N_t = 4, 6$ 
using $4\times 6^3$ and $6\times 8^3$ lattices respectively are presented at 
$\beta = 5.3, 5.4, 5.5$.  We also give Wilson loop expectation values at 
$\beta = 5.3$ for six values of $\kappa$ obtained on $8^4$ lattices.  The data 
show evidence for screening in the $q\bar q$ potential.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Metropolis and Langevin Time}
\par\noindent
{\bf C. F. Baillie and D. A. Johnston}
\par\noindent
$\rm C^3P-680$\ \ \ \ \ \ \ (Short Code:  Baillie:88l)
\par
We show that a linear relation between Metropolis and Langevin time in 
computer simulations observed by Meakin, et al., for spinodal decomposition is 
also true for lattice gauge theories.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Comparing Shared and Distributed Memory 
Computers}
\par\noindent
{\bf Clive F. Baillie}
\par\noindent
$\rm C^3P-719$\ \ \ \ \ \ \ (Short Code:  Baillie:88m)
\par
There are two distinct types of MIMD (Multiple Instruction, Multiple Data) 
computers: the shared memory machine, e.g., Butterfly, and the distributed 
memory machine, e.g., Hypercubes, Transputer arrays.  Typically these utilize 
different programming models:  the shared memory machine has monitors, 
semaphores and fetch-and-add; whereas the distributed memory machine uses 
message passing.  Moreover there are two popular types of operating systems: a 
multi-tasking, asynchronous operating system and a crystalling, loosely 
synchronous operating system.}
\par
In this paper, I firstly describe the Butterfly, Hypercube and Transputer 
array MIMD computers, and review monitors, semaphores, fetch-and-add and 
message passing; then I explain the two types of operating systems and ive 
examples of how they are implemented on these MIMD computers.  Next, I discuss 
the advantages and disadvantages of shared memory machines with monitors, 
semaphores and fetch-and-add, compared to distributed memory machines using 
message passing, answering questions such as ``is one model `easier' to 
program than the other?'' and ``which is `more efficient'?''  One may think 
that a shared memory machine with monitors, semaphores and fetch-and-add is 
simpler to program and runs faster than a distributed memory machine using 
message passing but we shall see that this is not necessarily the case.  
Finally, I briefly discuss which type of operating system to use and on which 
type of computer.  This, of course, depends on the algorithm one wishes to 
compute.

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Comparing Communication in Concurrent 
Processor Operating Systems}
\par\noindent
{\bf Clive Baillie}
\par\noindent
$\rm C^3P-535$\ \ \ \ \ \ \ (Short Code:  Baillie:88n)
\par
I have developed a simple program which exercises communication in concurrent 
processor operating systems.  It allows comparison of both the programming 
model used in the operating system and the efficiency of its implementation.  
I have run this program with both loosely synchronous and multi-tasking 
operating systems on the Caltech/JPL Mark~II Hypercube and the BBN Butterfly.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf QED on the Connection Machine}
\par\noindent
{\bf Clive Baillie, Lennart Johnsson, Luis Ortiz and Stuart Pawley}
\par\noindent
$\rm C^3P-536$\ \ \ \ \ \ \ (Short Code:  Baillie:88o)
\par
Physicists believe that the world is described in terms of gauge theories.  A 
popular technique for investigating these theories is to discretize them onto 
a lattice and simulate numerically by a computer, yielding so-called lattice 
gauge theory.  Such computations require at least $10^{14}$ floating-point 
multiplications, necessitating the use of advanced architecture supercomputers 
such as the Connection Machine made by Thinking Machines Corporation.  
Currently, the most important gauge theory to be solved is that describing the 
sub-nuclear world of high energy physics:  Quantum Chromo-dynamics (QCD).  The 
simplest example of a gauge theory is Quantum Electro-dynamics (QED), the 
theory which describes the interaction of electrons and photons.  Simulation 
of QCD requires computer software very similar to that for the simpler QED 
problem.  Hence, as the first step in using the Connection Machine for QCD 
calculations we have written, tested and benchmarked a QED code.  We obtain a 
computational rate of several million lattice site updates per second.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Benchmarking Concurrent
Supercomputers}
\par\noindent
{\bf Clive F. Baillie and Edward W. Felten}
\par\noindent
$\rm C^3P-453$\ \ \ \ \ \ \ (Short Code:  Baillie:88p)
\par
We are benchmarking concurrent supercomputers running ``loosely
synchronous'' algorithms, which are distinguished by a regular topology
and time-stepped calculation.  We define and measure performance
characteristics for three classes of computer:  MIMD distributed memory
machines, MIMD shared memory machines, and SIMD machines.  Using these
we predict the performance of a scientific application --- Monte Carlo
Lattice QCD --- on several concurrent supercomputers.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf The Pebble Crunching Model for Load 
Balancing in Concurrent Hypercube Ensembles}
\par\noindent
{\bf Sandeep Gulati, Jacob Barhen, and S. Sitharama Iyengar}
\par\noindent
$\rm C^3P-610$\ \ \ \ \ \ \ (Short Code:  Barhen:88a)
\par
The successful development of fifth generation systems require enormous 
computational capability and flexibility necessitating the ability to achieve 
operational response in hard real-time through optimal resource utilization.  
This entails dynamically balancing the computational load among all the 
processing nodes in the system.  We propose a graph-theoretic, receiver-
initiated, distributed protocol for dynamic load balancing protocol in large-
scale hypercube ensembles.  Using attributed hypergraphs as the primary data 
structure for constraint modeling and dynamic optimization, we consider 
systems running precedence-constrained heterogeneous tasks.  Fault Tolerance 
is ensured by incorporating an integrity check for the decision nodes and 
their subsequent reelection if needed.  Simulation studies are used to 
evaluate the performance of the algorithm.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Numerical Solution of High
Temperature Superconductor Spin Systems}
\par\noindent
{\bf T. Barnes}
\par\noindent
$\rm C^3P-638$\ \ \ \ \ \ \ (Short Code:  Barnes:88a)
\par
Recent experimental work on high temperature superconductors suggests
that these materials may be regarded as two dimensional
antiferromagnetic quantum spin systems.  This has stimulated intense
theoretical interest in the two dimensional Hubbard and Heisenberg
models, which are thought to describe these systems in certain limits.
In this paper we describe a numerical study of the two dimensional
Heisenberg model using a Hamiltonian Monte Carlo algorithm which
simulates the Euclidean time Schr\"odinger equation using random walks.
This algorithm allows the numerical measurement of energies and
expectation values of the ground state of a specified Hamiltonian.  We
also discuss the optimization of the algorithm and show that energy
measurement errors can be made arbitrarily small with sufficiently well
chosen importance sampling.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Evidence for a Phase Transition in
the Zero Temperature Anisotropic 2D Heisenberg Antiferromagnet}
\par\noindent
{\bf T. Barnes, D. Kotchan and E. S. Swanson}
\par\noindent
$\rm C^3P-653$\ \ \ \ \ \ \ (Short Code:  Barnes:88b)
\par
We describe a Monte Carlo study of the ground state of the two
dimensional anisotropic Heisenberg antiferromagnet.  Values of the
energy per spin and the rms $\hat z$ staggered magnetization are
determined for a range of transverse couplings.  There is evidence for a
sharp transition from finite to zero antiferromagnetic $\hat z$ spin
alignment at isotropy.  This may imply that the {\it isotropic}
Heisenberg antiferromagnet is unsuitable as a model of the high
temperature superconductors.  We also compare our results with previous
conjectures regarding the ground state of the anisotropic system.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Collective Stereopsis on the Hypercube}
\par\noindent
{\bf Roberto Battiti}
\par\noindent
$\rm C^3P-583$\ \ \ \ \ \ \ (Short Code:  Battiti:88a)
\par
A cooperative algorithm for extracting disparity information from stereo image 
pairs has been implemented on the NCUBE hypercube computer.}
\par
Software is written in C-language, using communication routines of the {\it 
``Crystalline Operating System'' CrOSIII} designed at Caltech within the 
Caltech Concurrent Computation Program.  Some tests have been done using 
Julesz's random-dot stereograms.
\par
Although the software is reasonably versatile and can be easily adapted for 
different flavors of stereo algorithms, the method used is that presented by 
Marr and Poggio.
\par
As a preliminary stage for the stereo matching problem, a ``filtering'' 
program to extract physically meaningful primitives from images of a given 
scene has been written and tested on various types of images.

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Surface Reconstruction and
Discontinuity Detection:  A Hierarchical Approach}
\par\noindent
{\bf Roberto Battiti}
\par\noindent
$\rm C^3P-676$\ \ \ \ \ \ \ (Short Code:  Battiti:88b)
\par
A fast hierarchical scheme for reconstructing a piecewise smooth surface
from noisy data is proposed.  Line element detectors ({\it discontinuity
neurons}) on different scales are coupled in a coherent way to a
multiscale ``smoothing'' algorithm.  A new scheme for the interaction of
the {\it discontinuity neurons} with nearby neurons on different layers
has been tested on ``Randomville'' images with promising results.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Collective Stereopsis on the
Hypercube}
\par\noindent
{\bf Roberto Battiti}
\par\noindent
$\rm C^3P-540$\ \ \ \ \ \ \ (Short Code:  Battiti:88c)
\par
A cooperative algorithm for extracting disparity information from stereo
image pairs has been implemented on the NCUBE hypercube computer.}
\par
Software is written in C-language, using communication routines of the
{\it ``Crystalling Operating System''} CrOSIII designed at Caltech
within the Caltech Concurrent Computation Program.  Some tests have been
done using Julesz's random-dot stereograms.
\par
Although the software is reasonably versatile and can be easily adapted
for different flavors of stereo algorithms, the method used is that
presented by Marr and Poggio.
\par
As a preliminary stage for the stereo matching problem, a ``filtering''
program to extract physically meaningful primitives from images of a
given scene has been written and tested on various types of images.

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Parallel Vision Techniques on the 
Hypercube Computer}
\par\noindent
{\bf Alan H. Bond and David Fashena}
\par\noindent
$\rm C^3P-632$\ \ \ \ \ \ \ (Short Code:  Bond:88a)
\par
Parallel algorithms for programming low-level vision mechanisms on the JPL-
Caltech hypercube are reported.  These concern principally edge and region 
finding.  $256\times 256$ eight-bit images were used.}
\par
We discuss the problem of programming a hypercube computer, and the Caltech 
approach to load balancing.  We then discuss the distribution of images over 
the hypercube and the I/O problem for images.
\par
In edge finding, we programmed convolution using a separable kernel 
computational approach.  This was tested with $5\times 5$ and $32\times 32$ 
masks.
\par
In region finding, we developed two different parallel histogram techniques.  
The first finds a global histogram for the image by a completely parallel 
technique.  This method, which was developed from the Fox-Furmanski scalar 
product method, allows each histogram bucket to be computed by a separate 
processor, each processor regarding the hypercube as a different tree, and all 
buckets being computed in parallel by a complete interleaving of all 
communications required.  Similarly, the global histogram can then be 
distributed over the hypercube, so that all processors have the entire global 
histogram, by a completely parallel technique.
\par
The second histogramming method finds a spatially local histogram within each 
processor and then connects locally found regions together.
\par
Work in progress includes the application of a Hopfield neural net approach to 
region finding.

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf The Development and Coordination of
Models in Aircraft Design}
\par\noindent
{\bf Alan H. Bond and Richard J. Ricci}
\par\noindent
$\rm C^3P-688$\ \ \ \ \ \ \ (Short Code:  Bond:88e)
\par
The cooperation of specialists with distributed knowledge is examined,
in the context of knowledge-based support for collaboration among
different engineering departments in carrying out large design tasks.}
\par
It is found that
\item{1.}there is a central model, which is the main design
representation;
\item{2.}each specialist department has its own private justification
modeling system;
\item{3.}as the aircraft design proceeds, the various models are refined
in parallel;
\item{4.}models are continually reformulated, and are modified to
coordinate with the central design, and with models used by other
specialists;
\item{5.}this is achieved by flows of correctional information, in the
form of evaluations and suggestions.
\par
Descriptions are given, in a uniform method of relationship structures,
of models used by the aerodynamics, structures, aeromechanics and weight
departments.  The types and forms of coordination information flowing
among the models are described.

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf The Cooperation of Experts in 
Manufacturing}
\par\noindent
{\bf Alan H. Bond}
\par\noindent
$\rm C^3P-689$\ \ \ \ \ \ \ (Short Code:  Bond:88f)
\par
The cooperation of specialists with distributed knowledge is examined, in the 
context of knowledge-based support for collaboration among different 
engineering departments in carrying out large design tasks.}
\par
It is concluded that
\item{1.}each specialist department has its own private justification 
language, but interacts with another department using a common shared 
language;
\item{2.}there may be little shared knowledge, and the shared language may 
involve an abstracted subset of the private languages of the collaborators;
\item{3.}collaborative reasoning can be limited because of
\itemitem{$\bullet$}{\it expression\/} problems, not being able to ask the 
right questions,
\itemitem{$\bullet$}{\it rules of interaction\/} and protocol, arising from 
legalistic procedures or from proof strategy,
\itemitem{$\bullet$}{\it performance\/} problems, not having sufficient 
resources, due to the complexity of resolving the distribution.
\par
A simple model for collaborative reasoning is proposed, which defines a 
collaboration strategy as a dialogue game.

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf A Survey of Distributed Artificial
Intelligence}
\par\noindent
{\bf A. H. Bond and L. Gasser}
\par\noindent
$\rm C^3P-407b$\ \ \ \ \ \ \ (Short Code:  Bond:88g)
\par
The new and diverse area of Distributed Artificial Intelligence is
critically reviewed from a very general organizing viewpoint.}
\par
The difficult conceptual problems of understanding distributed
aggregations of agents and knowledge yield a set of fundamental
theoretical issues arising from {\it distribution\/} and {\it
interaction\/} of all aspects of the intelligence system.
\par
A theoretical scheme is presented for representing the organizational
structure of distributed systems.
\par
The issue of {\it interest\/} or rationality of the agents and system is
discussed.
\par
We also review representational issues in distributed artificial
intelligence, including architectural issues, control issues and
knowledge representation issues.
\par
We survey implementations, including development tools and machines.

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Multiple Perspective Organizational
Analysis of Distributed Artificial Intelligence}
\par\noindent
{\bf A. H. Bond and L. Gasser}
\par\noindent
$\rm C^3P-407b$\ \ \ \ \ \ \ (Short Code:  Bond:88h)
\par
A theoretical scheme is presented for representing the organizational
structure of distributed systems.  This scheme analyzes all aspects of
the distributed artificial intelligence system in terms of the structure
of their {\it distribution\/} and {\it interaction}.  The concepts of
{\it interest\/} and {\it rationality\/} of the agents and system are
described.  A system may be best analyzed in a {\it rationalized\/}
form, in which all actions are a result of rational decision in each
agents' best interest.}
\par
In our scheme, a DAI system is first described by a set of {\it
perspectives}.  Each perspective is a relational structure consisting of
organizational elements, relations among them and actions defined upon
elements and relations.  For example, perspectives might describe
communication structure, task structure, power structure, knowledge
structure and the distribution of basic resources.  Perspectives are
then combined and integrated to form the complete organization.  This
involves reconciliation driven by knowledge of organization
well-formedness.  The processional aspects of the organization are
represented by a script which describes the activities of the
organization in using the organizational structures previously defined.
\par
This theoretical scheme is not a rigorously formal device but rather a
method of analysis.  It is illustrated by several key examples of
organizations used in Distribute Artificial Intelligence systems.

\bigskip\starline\bigskip
\vbox{\par\noindent
{\bf Transparencies} from a talk by J. Bower {\it et al.}, entitled
``CNS in the Context of the Caltech Concurrent Computation Program'',
presented at the DOE Site Review, January 1988.  C$^3$P-621 (Short
Code: Bower:88a)}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf The JPL/Caltech Mark~IIIfp Hypercube}
\par\noindent
{\bf P. Burns, J. Crichton, D. Curkendall, B. Eng, C. Goodhart, R. Lee,
R. Livingston, J. Peterson, M. Pniel, J. Tuazon, and B. Zimmerman}
\par\noindent
$\rm C^3P-607$\ \ \ \ \ \ \ (Short Code:  Burns:88a)
\par
The Mark~IIIfp Hypercube and its operating system software represent the
culmination of the efforts of the JPL/Caltech Campus collaboration
started in 1983 with the design and construction of the Mark~II
8086-based machine.}
\par
The Mark~III, a Motorola 68020/68881-based machine, was first made
operational in a prototype version in May~1985.  JPL is currently adding
a high-performance Weitek-based floating-point accelerator and will
construct a single, 128-node, gigaflop machine during this year.

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Finite Difference Time Domain Solution 
of Electromagnetic Scattering on the Hypercube}
\par\noindent
{\bf Ruel H. Calalo, James R. Lyons, and William A. Imbriale}
\par\noindent
$\rm C^3P-596$\ \ \ \ \ \ \ (Short Code:  Calalo:88a)
\par
Electromagnetic fields interacting with a dielectric or conducting structure 
produce scattered electromagnetic fields.  To model the fields produced by 
complicated, volumetric structures, the finite difference time domain (FDTD) 
method employs an iterative solution to Maxwell's time dependent curl 
equations.  Implementations of the FDTD method intensively use memory and 
perform numerous calculations per time step iteration.  We implemented an FDTD 
code on the California Institute of Technology/Jet Propulsion Laboratory 
Mark~III Hypercube.  This code allows us to solve problems requiring as many 
as 2,048,000 unit cells on a 32-node Hypercube.  For smaller problems, the 
code produces solutions in a fraction of the time to solve the same problems 
on sequential computers.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Finite Difference Time Domain Solution of 
Electromagnetic Scattering on the Hypercube}
\par\noindent
{\bf Ruel H. Calalo, James R. Lyons, William R. Imbriale}
\par\noindent
$\rm C^3P-542$\ \ \ \ \ \ \ (Short Code:  Calalo:88b)
\par
Electromagnetic fields interacting with a dielectric or conducting structure 
produce scattered electromagnetic fields.  To model the fields produced by 
complicated, volumetric structures, the finite difference time domain (FDTD) 
method employs an iterative solution to Maxwell's time dependent curl 
equations.  The FDTD method intensively uses memory and performs numerous 
calculations per time step.  We implemented a FDTD code on the California 
Institute of Technology/Jet Propulsion Laboratory Mark~III Hypercube.  This 
code allows us to solve problems requiring more than a million unit cells in a 
fraction of the time to execute the same problems on a VAX/785.}
\par
The goal of the FDTD code is to track the propagation of an incident 
electromagnetic wave into a volume of space containing a dielectric or 
conducting structure and observe the wave's interaction with the scattering 
object.  Wave tracking is complete when sinusoidal steady state behavior 
occurs at each lattice cell or after a sufficient number of cycles of the 
incident field.

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Non-Local Path Integral Monte Carlo on 
the Hypercube: Exchange Interactions in Solid Helium}
\par\noindent
{\bf Sean Callahan}
\par\noindent
$\rm C^3P-589$\ \ \ \ \ \ \ (Short Code:  Callahan:88a)
\par
Some interesting physical properties of solid $^3$He are described and the 
physical observable calculated using Monte Carlo path integral techniques is 
defined.  The relationship between the path integral and the observable is 
outlined.  The parallel algorithm is explained and finally, timing results are 
presented for runs of the identical code on one parallel computer and two 
sequential computers:  The NCUBE hypercube, the CRAY~X-MP, the Elxsi~6400.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Exchange Interactions in Solid 
$\bf ^3He$ on a Parallel Computer}
\par\noindent
{\bf Sean Macauley Callahan}
\par\noindent
$\rm C^3P-645$\ \ \ \ \ \ \ (Short Code:  Callahan:88b)
\par
We have developed a method of calculating the Gruneisen parameter, 
$\gamma\equiv\partial\ln/\ln v$ ($J$ --- exchange splitting, $v$ --- molar 
volume), for energy splittings that are due to atoms exchanging lattice sites 
in fermionic systems for which the exchange splittings are small compared with 
the lattice kinetic and potential energies.  The method involves making two 
separate path integral Monte Carlo calculations, one for a path (sequence of 
particle positions in time) that does not involve atoms exchanging lattice 
sites, and one for a path in which the atoms do exchange lattice sites.  The 
difference between a quantity calculated for the two systems is related to the 
Gruneisen parameter.}
\par
The central results of this thesis are firstly, that there is no significant 
variation of the Gruneisen parameters for two, three and four particle 
exchange ($\gamma_2, \gamma_3$ and $\gamma_4$, respectively) for solid $\rm 
^3He$, in going from $\rm 24\,cm^3/mole$ for $\gamma_2$.  Since no significant 
variation was observed, the values calculated for different molar volumes were 
combined to give best estimates for the Gruneisen constants, $\gamma_2 = 
15.9\pm .8$, $\gamma_3 = 16.4\pm 1.4$ and $\gamma_4 = 13.8\pm 1.5$.  The 
second results is that the magnitudes of the Gruneisen parameters are very 
similar for the three types of exchange despite their significantly different 
geometry.  Some very limited runs were done for a system of hard spheres.  It 
is interesting that for the hard sphere diameter chosen, the Gruneisen 
parameters are of the same order as for solid $\rm ^3He$, $\gamma_2 = 
21.7\pm .8$, $\gamma_3 = 16.8\pm 2.1$ and $\gamma_4 = 19.3\pm 1.9$ for the 
small test systems checked.  The final results relates to $\rm ^3He$ deposited 
on a graphite surface.  The Gruneisen parameter for three particle exchange for 
a two-dimensional system with a triangular mesh is found to be consistent with 
$\gamma_3 = 50\pm 5$ for a range of nearest-neighbor, lattice spacings from 
$\rm 3.2\AA$ to $\rm 3.6\AA$.  This is inconsistent with experiment, 
indicating that three particle exchange confined to two dimensions does not 
account for the ferromagnetic properties of this system, as was claimed 
previously.

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Non-Local Path Integral Monte-Carlo on 
the Hypercube}
\par\noindent
{\bf Sean Callahan}
\par\noindent
$\rm C^3P-553$\ \ \ \ \ \ \ (Short Code:  Callahan:88c)
\par
$\rm ^3He$ solidifies at temperatures below $\rm 10\,K$ and at pressures 
greater than 30 atmospheres.  The relative simplicity of the constituents and 
the rich behavior of the system makes this an attractive medium for increasing 
our understanding of complex magnetic systems.  Near melting pressure and 
below approximately $\rm 1\,mK$, a region easily accessible experimentally 
with modern demagnetization cryostats, atoms exchanging places in the lattice 
are responsible for nuclear magnetic ordering.  Magnetic dipole interactions 
are several orders of magnitude smaller have little effect.  It turns out that 
exchange interactions are in turn several orders of magnitude smaller than the 
lattice energies and so each type of exchange ($2, 3, 4,\ldots$ particles) may 
be treated independently.  This simplification allows for the calculation of 
the volume dependence of each type of exchange.  This quantity, a Grunesian 
parameter, may be calculated using path integral Monte Carlo techniques.  This 
calculation will be described in enough detail to allow for a description of 
the parallel implementation of the algorithm on the NCUBE hypercube.  Timing 
results will also be presented.}
\par
Finally, the reason that Grunesian parameters are of interest is that 
experimentally it is the pressure (or volume) dependence of the exchange rates 
that are measured.

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Caltech Missile Tracking Program
--- A Benchmark Comparison:  NCUBE and T800 vs. Sequent Balance and
Symmetry}
\par\noindent
{\bf Huy T. Cao and Clive F. Baillie}
\par\noindent
$\rm C^3P-673$\ \ \ \ \ \ \ (Short Code:  Cao:88a)
\par
As a way to compare different MIMD parallel computers for actual
scientific applications, we adapted the Caltech missile tracking program
(written by Thomas D. Gottschalk) for distributed memory hypercube
computers such as the NCUBE to the shared memory bus architecture
Sequent Balance and Symmetry machines, and then benchmarked the relative
performance.}
\par
The missile tracking program calculates trajectories, given a set of
missile coordinates each time step.  Such calculations are quite time
consuming, since by brute force the problem must, on the basis of new
data points, extend old tracks or eliminate them.  Parallelization can
greatly decrease real run time.
\par
The heart of the program, where the real missile tracking takes place,
consists of master(), nl\_filt() and batch().  The routine master()
finds track extensions using a rough filter; then nl\_filt() deletes bad
extensions using a precision filter; and finally batch() initiates new
tracks.

\bigskip\starline\bigskip
\vbox{\par\noindent
{\bf Transparencies} from a talk by J. Cavano {\it et al.}, entitled
``Software Development Issues for Parallel Processing'', presented at
the IEEE COMPSAC Meeting, Chicago, October 1988.  C$^3$P-671 (Short
Code: Cavano:88a)}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Schwinger Model on the Random Block
Lattice}
\par\noindent
{\bf Ting-Wai Chiu}
\par\noindent
$\rm C^3P-647$\ \ \ \ \ \ \ (Short Code:  Chiu:88a)
\par
Fermion propagator and vacuum polarization tensor of the Schwinger model
are studied on the random block lattice, in the free field limit and
weak coupling perturbation theory respectively.  The ensemble averaged
fermion propagator and the vacuum polarization tensor agree with their
respective values in the continuum theory for distances greater than
three average lattice spacings.  In momentum space, the ensemble
averaged fermion propagator also agrees with the continuum propagator,
in 2-d and 4-d respectively.  These results support the possibility of
having a chiral fermion interacting with the dynamical gauge field, on
the random block lattice, with the correct continuum limit.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Shift-Register Sequence Random Number 
Generators on the Hypercube Concurrent Computers}
\par\noindent
{\bf Ting-Wai Chiu}
\par\noindent
$\rm C^3P-526$\ \ \ \ \ \ \ (Short Code:  Chiu:88b)
\par
We discuss the design of a class of shift-register sequence random number 
generators for the MIMD parallel computers, and particularly for the hypercube 
concurrent computers.  The simplest implementation is to have each processor 
generating its own sequence provided that the initial seeds are linearly 
independent.  We generate these initial seeds by using distinct linear 
congruential generators and finally bit-by-bit-exclusive-or with the system 
time in microseconds.  Our shift-register sequence random number generators 
are coded in C and run single processor as well as on the combined sequence 
produced by all processors.  The tests include chi-square, 
Kolmogorov-Smirnov, auto-correlation, runlength and n-tuple distribution 
tests.  A statistical test has been devised for testing the sequences of 
random number generated by a MIMD parallel computer.  Our test results 
indicate that our generators do provide independent sequences of random 
numbers with extremely long periods.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Fermion Propagators on a Four Dimensional 
Random-Block Lattice}
\par\noindent
{\bf Ting-Wai Chiu}
\par\noindent
$\rm C^3P-507$\ \ \ \ \ \ \ (Short Code:  Chiu:88c)
\par
Fermion propagators, composite boson propagators and the fermion condensate 
are calculated numerically on the four-dimensional random-block lattice 
respectively.  The ensemble-averaged fermion propagator agrees with the 
continuum propagator for distances greater than three average lattice 
spacings.  The results on the fermion condensate show that the chiral symmetry 
of the doubled modes is broken in the continuum limit.  The Goldstone boson 
arising from the broken symmetry is revealed by examining the composite 
pseudo-scalar propagator.  The doubled fermion and the Goldstone boson both 
acquire masses of the order of inverse lattice spacing and thus decouple from 
the theory in the continuum limit.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf A Parallel Computer for Lattice Gauge 
Theories}
\par\noindent
{\bf Ting-Wai Chiu}
\par\noindent
$\rm C^3P-584$\ \ \ \ \ \ \ (Short Code:  Chiu:88d)
\par
A parallel computer especially designed for the calculations in lattice gauge 
theories is proposed.  The final device will contain 256 nodes running in MIMD 
mode with a computational power about one billion 32-bit floating point 
operations per second.  Each node is controlled by the Motorola 68020/68882 
microprocessors, (the Weitek floating-point processors) and two megabyte 
static RAM.  The architecture is designed to allow rapid execution of the 
numerically intensive calculations in lattice gauge theories.  In this paper, 
we outline the hardware and software design of the first four nodes which have 
been built and tested.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Vacuum Polarization on the 4-D 
Random-Block Lattice}
\par\noindent
{\bf Ting-Wai Chiu}
\par\noindent
$\rm C^3P-693$\ \ \ \ \ \ \ (Short Code:  Chiu:88e)
\par
Fermions interacting with dynamical gauge fields are studied in the 4-d 
random-block lattice in the weak coupling perturbation theory.  Vacuum 
polarization tensors of massless and massive QED are obtained respectively.  
The ensemble-averaged vacuum polarization tensors agree with the corresponding 
values in continuum QED for distances greater than two average lattice 
spacings.  These results support the possibility of having a chiral fermion 
interacting with the dynamical gauge field, on the 4-d random block lattice, 
with the correct continuum limit.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf A Parallel Computer for Lattice Gauge 
Theories}
\par\noindent
{\bf Ting-Wai Chiu}
\par\noindent
$\rm C^3P-560$\ \ \ \ \ \ \ (Short Code:  Chiu:88g)
\par
A parallel computer especially designed for the calculations in lattice gauge 
theories is proposed.  The final device will contain 256 nodes running in MIMD 
mode with a computational power about one billion 32-bit floating point 
operations per second.  Each node is controlled by the Motorola 68020/68882 
microprocessors, (the Weitek floating-point processors) and two megabyte 
static RAM.  The architecture is designed to allow rapid execution of the 
numerically intensive calculations in lattice gauge theories.  In this paper, 
we outline the hardware and software design of the first four nodes which have 
been built and tested.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Shift-Register Sequence Random Number 
Generators}
\par\noindent
{\bf Ting-Wai Chiu}
\par\noindent
$\rm C^3P-561$\ \ \ \ \ \ \ (Short Code:  Chiu:88h)
\par
We discuss the design of a class of shift-register sequence random number 
generators for the MIMD parallel computers, and particularly for the Hypercube 
concurrent computers.  The simplest implementation is to have each processor 
generating its own sequence provided that the initial seeds are linearly 
independent.  We generate these initial seeds by using distinct linear 
congruential generators and finally bit-by-bit-exclusive or with the system 
time in microseconds.  Our shift-register sequence random number generators 
are coded in C and run under the CUBIX.  The statistical tests are performed 
on each sequence generated by an individual processor as well as on the 
combined sequence produced by all processors.  The tests include chi-square, 
Kolmogorov-Smirnov, auto-correlation, runlength and n-tuple distribution 
tests.  A new statistical test has been devised for testing the sequences of 
random numbers generated by a MIMD parallel computer.  The test results 
indicate that our generators do provide independent sequences of random 
numbers with extremely long periods.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf SURF Report --- Three Dimensional
Asteroid on Hypercube}
\par\noindent
{\bf D. Chu}
\par\noindent
$\rm C^3P-677$\ \ \ \ \ \ \ (Short Code:  Chu:88b)
\par
This project is to create a three dimensional asteroid video game on the
hypercube in the C programming language.  Its glorified features
comparing to the common two dimensional asteroid game demonstrate the
efficiency of the hypercube.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Robust Vortex Methods for 
Three-Dimensional Incompressible Flows}
\par\noindent
{\bf K. Chua, A. Leonard, F. Pepin, and G. Winckelmans}
\par\noindent
$\rm C^3P-690$\ \ \ \ \ \ \ (Short Code:  Chua:88a)
\par
Vortex methods for the numerical simulation of incompressible, 
three-dimensional flows at high Reynolds number are discussed.  Particular 
emphasis is placed on schemes that (1) prevent the excessive generation of 
mesh elements, (2) include viscous effects, and (3) are relatively inexpensive 
even as the number of elements becomes large.  Several simulations are 
presented involving the interaction of vortex rings.}

\bigskip\starline\bigskip
\vbox{\par\noindent
{\bf Transparencies} from a poster session by R. Clayton {\it et
al.}, entitled ``FD Wave Modeling --- Seismic Data Processing'',
presented at the Third Conference on Hypercube Concurrent Computers and
Applications, January 1988.  C$^3$P-564 (Short Code: Clayton:88b)}

\bigskip\starline\bigskip
\vbox{\par\noindent
{\bf Transparencies} from a talk by R. Clayton, entitled ``Geophysics at
Caltech in the Context of the Caltech Concurrent Computation Program'',
presented at the DOE Site Review, January 1988.  C$^3$P-618 (Short Code:
Clayton:88c)}

\bigskip\starline\bigskip
\vbox{\par\noindent
{\bf Transparencies} from a talk by T. Cole, entitled ``Concurrent
Computation at JPL'', presented at the DOE Site Review, January 1988.  
C$^3$P-622 (Short Code: Cole:88a)}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Acoustic Wavefield Propagation Using
Paraxial Extrapolators}
\par\noindent
{\bf Robert W. Graves and Robert W. Clayton}
\par\noindent
$C^3P-613$\ \ \ \ \ \ \ (Short Code:  Clayton:88a)
\par
Modeling by paraxial extrapolators is applicable to wave propagation problems 
in which most of the energy is traveling within a restricted angular cone 
about a principle axis of the problem.  Frequency domain finite-difference 
solutions are readily generated by using this technique.  Input  models can be 
described either by specifying velocities or appropriate media parameters on a 
two or three dimensional grid of points.  For heterogeneous models, 
transmission and reflection coefficients are determined at structural 
boundaries within the media.  The direct forward scattered waves are modeled 
with a single pass of the extrapolator operator in the paraxial direction for 
each frequency.  The first-order back scattered energy can then be modeled by 
extrapolation (in the opposite direction) of the reflected field determined on 
the first pass.  Higher order scattering can be included by sweeping through 
the model with more passes.}
\par
The chief advantages of the paraxial approach are 1) active storage is reduced 
by one dimension as compared to solutions which must track both up-going and 
down-going waves simultaneously, thus even realistic three-dimensional 
problems can fit on today's computers, 2) the decomposition in frequency 
allows the technique to be implemented on highly parallel machines, such as 
the hypercube, 3) attenuation can be modeled as an arbitrary function of 
frequency, and 4) only a small number of frequencies are needed to produce 
movie-like time slices.
\par
By using this method, a wide range of seismological problems can be addressed, 
including strong motion analysis of waves in three-dimensional basins, the 
modeling of VSP reflection data, and the analysis of whole earth problems such 
as scattering at the core-mantle boundary or the effect of tectonic boundaries 
on long-period wave propagation.

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Seecube User's Manual}
\par\noindent
{\bf Alva L. Couch}
\par\noindent
$\rm C^3P-501$\ \ \ \ \ \ \ (Short Code:  Couch:88a)
\par
{\it Seecube\/} is a software package that allows the programmer of a
parallel computer with a hypercube communications geometry to visualize
communications within parallel programs.  A diagnostic library on the
hypercube generates an event trace for each processor during a parallel
program execution.  This trace is transformed into a displayable normal
form, and this normal form data is displayed interactively using a
variety of graphical representations.  Using the displays, the
programmer can judge design assumptions, view program performance, and
compare alternative algorithms.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf A Programming Model for the Mark~III 
Hypercube with Multiple Processor Nodes}
\par\noindent
{\bf Barbara A. Zimmermann and Gerald A. Crichton}
\par\noindent
$\rm C^3P-541$\ \ \ \ \ \ \ (Short Code:  Crichton:88a)
\par
The Caltech/JPL Mark~III Hypercube originally consisted of an ensemble of 
processing elements each containing two Motorola M68020 processors --- one 
M68020 processor and a M68881 Floating-Point coprocessor used for data 
processing, the other M68020 processor dedicated to hypercube communications.  
Element code preparation for the hypercubes could be done on a variety of Unix 
M68020 based workstations serving as hosts, e.g., Counterpoint, Sun 
Microsystems, Masscomp, using the native Unix compilers.}
\par
In the interest of achieving even greater computational capability a third 
processing element, the Weitek XL system, was added to enhance floating point 
performance.  Each of what is now three processing elements is configured with 
cpu, local static memory, communication peripherals, clocks, and control 
logic.  In addition, the share four megabytes of dynamic memory on the node 
card.  The Weitek architecture is quite different from the Motorola and 
introduced the task of assembling a program image for the elements which 
combined modules using different instruction sets.  We will describe a 
programming model and environment that accommodates the operation of the three 
processors, and addresses the issues of shared resources, host independent 
program preparation, and extended Crystalling communications.
\par
The design of the programming model and the associated environment attempts to 
satisfy three objectives:  optimum hypercube performance, intranode 
concurrency, and simple programming procedures.  The model will be presented in 
four parts.  Part~1 describes the memory model and management procedures for 
shared memory.  Part~2 describes the Unix loader procedure for preparing 
executable files for the elements, and the role the Unix runtime libraries 
play in the Mark~III program environment.  Part~3 discusses the tools provided 
to use the Weitek and one of the Motorola processors in a concurrent fashion 
--- one as master the other as slave --- within the constraints imposed by 
shared main memory.  Part~4 describes the Crystalling communication 
environment consistent with concurrent operation of two or more of the 
processors.

\bigskip\starline\bigskip
\vbox{\par\noindent
{\bf Transparencies} from a poster session by G. Crichton {\it et
al.}, entitled ``The Programming Environment for the Caltech/JPL
Mark~III'', presented at the Third Conference on Hypercube Concurrent
Computers and Applications, January 1988.  C$^3$P-543 (Short Code:
Crichton:88b)}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Polymer Simulation on the Hypercube}
\par\noindent
{\bf Hong-Qiang Ding}
\par\noindent
$\rm C^3P-574$\ \ \ \ \ \ \ (Short Code:  Ding:88a)
\par
The Monte Carlo simulation of a model polymer is implemented on the Mark~III 
Hypercube computer under the CrOS operating system.  The polymer model and the 
simulation method are discussed.  The key features of the implementation are 
given.  The results show that hypercube computers are well suited for the 
polymer simulations.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf A Performance Analysis of the Polymer 
Simulation on the Hypercubes:\hfill\break  Mark~III vs. FPS T-Series}
\par\noindent
{\bf Hong-Qiang Ding}
\par\noindent
$\rm C^3P-566$\ \ \ \ \ \ \ (Short Code:  Ding:88b)
\par
The performance features of a polymer simulation on the Mark~III Hypercube is 
analyzed.  Using these results and known FPS T-Series characteristic 
parameters, we discuss the expected performance on the T-Series.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Performance of a QCD Code on
Mark~IIIfp}
\par\noindent
{\bf Hong-Qiang ding}
\par\noindent
$\rm C^3P-624$\ \ \ \ \ \ \ (Short Code:  Ding:88c)
\par
The pure gauge QCD code is ported on Mark~IIIfp.  With critical parts of
codes rewritten in assembly and vectorized communication, the final
program runs at $\rm 4.3\,Mflops$ per node.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf A Fast Random Number Generator for 
Mark~IIIfp}
\par\noindent
{\bf Hong-Qiang Ding}
\par\noindent
$\rm C^3P-629$\ \ \ \ \ \ \ (Short Code:  Ding:88d)
\par
A random number generator, $X_n = (X_{n-127} + X_{n-63}) \hbox{mod} 2^{31}$, 
is implemented on the Mark~IIIfp, written in Weitek XL assembly language.  It 
has a period longer than $2^{127}$ and it takes $\rm 4\,\mu sec$ to generate 
a random number including normalizing into [0,1).}

\bigskip\starline\bigskip
\vbox{\par\noindent
{\bf Transparencies} from a poster session by H. Q. Ding, entitled
``Polymer Simulation on the Caltech/JPL Mark~III Hypercube'', presented
at the Third Conference on Hypercube Concurrent Computers and
Applications, January 1988.  C$^3$P-554 (Short Code: Ding:88f)}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Coherent Parallel C}
\par\noindent
{\bf Edward W. Felten and Steve W. Otto}
\par\noindent
$\rm C^3P-527$\ \ \ \ \ \ \ (Short Code:  Felten:88a)
\par
Coherent Parallel C (CPC) is an extension of C for parallelism.  The 
extensions are not simply parallel {\it for\/} loops; instead, a data parallel 
programming model is adopted.  This means that one has an entire process for 
each data object.  An example of an ``object'' is one mesh point in a finite 
element solver.  How the processes are actually distributed on a parallel 
machine is transparent --- the user is to image that an entire processor in a 
distributed-memory environment is dedicated to each process.  This simplifies 
programming tremendously: complex {\it if\/} statements associated with domain 
boundaries disappear; problems which do not exactly match the machine size and 
irregular boundaries are all handled transparently.}
\par
The usual communication calls are not seen at all at the user level.  
Variables of other processes (which may or may not be on another processor) 
are merely accessed (global memory).  The first pass of the CPC compiler 
schedules the necessary communications in an efficient, coherent manner.  
Processes in CPC are insulated from one another and interact in a 
deterministic manner.  This allows tractable debugging.  Standard C I/O is 
provided, with simple extensions for parallelism.
\par
We currently have a CPC runtime system implemented on an NCUBE and have 
started implementing a true compiler for the language.
\par
CPC is not specific to distributed memory machines.  Implementation of this 
language on other architectures is natural -- for example, there seems to be 
no fundamental problem with CPC on shared-memory parallel computers.

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Generalized Signals: An Interrupt-Based 
Communication System for Hypercubes}
\par\noindent
{\bf Edward W. Felten}
\par\noindent
$\rm C^3P-433b$\ \ \ \ \ \ \ (Short Code:  Felten:88b)
\par
This paper describes a communication system designed to support highly 
asynchronous application or system software on a distributed-memory 
multicomputer such as a hypercube.  The system is called generalized signals 
because it is based on the {\it signal\/} facility in System~V UNIX, with 
enhancements to allow signals to carry data.}
\par
Any processor can send a signal to any other processor at any time.  When a 
signal arrives, the receiving processor traps to a user-specified subroutine; 
when this subroutine is finished the interrupted code is resumed.  Signal 
interrupts happen in a controlled manner, thereby simplifying the programmer's 
task.  There is a facility for protection of critical sections in user 
programs.
\par
The generalized signals system has been implemented on the NCUBE hypercube.  
This implementation is based on a modified version of NCUBE's VERTEX 
message-passing system.  Generalized signals can coexist the VERTEX messages 
and the enhancements to VERTEX are transparent to ordinary programs.

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Best-First Branch-and-Bound on a 
Hypercube}
\par\noindent
{\bf Edward W. Felten}
\par\noindent
$\rm C^3P-590$\ \ \ \ \ \ \ (Short Code:  Felten:88c)
\par
The branch-and-bound technique is a common method for finding exact solutions 
to difficult problems in combinatorial optimization.  This paper will discuss 
issues surrounding implementation of a particular branch-and-bound algorithm 
for the traveling-salesman problem on a hypercube multi-computer.}
\par
The natural parallel algorithm is based on a number of asynchronous processes 
which interact through a globally shared list of unfinished work.  In a 
distributed-memory environment we must find a non-centralized version of this 
shared data structure.  In addition, detecting termination of the computation 
is tricky; an algorithm will be presented which ensures proper termination.  
Finally, issues affecting performance will be discussed.

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Multi-Scale Training of a Large 
Backpropagation Net}
\par\noindent
{\bf Edward W. Felten and Steve W. Otto}
\par\noindent
$\rm C^3P-608$\ \ \ \ \ \ \ (Short Code:  Felten:88e)
\par
The shortcomings of automatic learning in neural networks can be overcome by 
incorporating features of the problem into the weight space.  We teach a 
multi-layer perceptron to recognize hand-printed characters by using a 
multi-scale method.  This leads to better performance for learning rates and 
for generalization than direct use of back-propagation.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf A Safe Vertex}
\par\noindent
{\bf Edward W. Felten and Steve W. Otto}
\par\noindent
$\rm C^3P-614$\ \ \ \ \ \ \ (Felten:88f)
\par
The VERTEX message passing system provided with NCUBE hypercubes is unsafe.  
The system can fail under high message loads.  We have implemented a message 
passing system with the same ``look and feel'' as VERTEX but which is instead 
based upon the {\it crystal\_router} running at clock interrupt time.  The 
system is written mostly in C with a few bits of assembly code to run the DMA 
devices.  This implies that safety checks (are the buffers full?) and complex 
error handling mechanisms can be easily implemented at the C level.  A first 
version works, is safe, and is faster than VERTEX in the high volume limit, 
slower in the low volume case.  At the very least, this system will be 
interesting for high message traffic applications, such as disk backup.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Chess on a Hypercube}
\par\noindent
{\bf Edward W. Felten and Steven W. Otto}
\par\noindent
$\rm C^3P-579$\ \ \ \ \ \ \ (Short Code:  Felten:88g)
\par
We report our progress on computer chess last described at the Second 
Conference on Hypercubes.  Our program follows the strategy of currently 
successful sequential chess programs: searching of an alpha-beta pruned game 
tree, iterative deepening, transposition and history tables, specialized 
endgame evaluators, and so on.  The search tree is decomposed onto the 
hypercube (an NCUBE) using a recursive version of the principal-variation-
splitting algorithm.  Roughly speaking, subtrees are searched by teams of 
processors in a self-scheduled manner.}
\par
A crucial feature of the program is the global hashtable.  Hashtables are 
important in the sequential case, but are even more central for a parallel 
chess algorithm.  The table not only stores knowledge but also makes the 
decision at each node of the chess tree whether to stay sequential or to split 
up the work in parallel.  In the language of Knuth and Moore, the 
transposition table decides whether each node of the chess tree is a type 2 or 
a type 3 node and acts accordingly.  For this data structure, the hypercube is 
used as a shared-memory machine.  Multiple writes to the same location are 
resolved using the priority system which decides which entry is of more value 
to the program.  The hashtable is implemented as ``smart'' shared memory.
\par
Search times for related subtrees vary widely (up to a factor of 100) so 
dynamic reconfiguration of processors is necessary to concentrate on such 
``hot spots'' in the tree.  A first version of the program with dynamic load 
balancing has recently been completed and out-performs the non-load-balancing 
program by a factor of three.  The current speedup of the program is 101 out 
of a possible 256 processors.
\par
The program has played in several tournaments, facing both computers and 
people.  Most recently it scored 2--2 in the ACM North American Computer Chess 
Championship.

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Chess on a Hypercube}
\par\noindent
{\bf Steve W. Otto and Edward W. Felten}
\par\noindent
$\rm C^3P-579b$\ \ \ \ \ \ \ (Short Code:  Felten:88h)
\par
We have been developing a parallel chess program to run on distributed memory, 
multiple instruction stream computers.  Our program follows the strategy of 
currently successful sequential chess programs: searching of an alpha-beta 
pruned game tree, iterative deepening, transposition and history tables, 
specialized endgame evaluators, and so on.  The search tree is decomposed onto 
a hypercube (an NCUBE) using a recursive version of the principal-variation-
splitting algorithm.  Roughly speaking, subtrees are searched by teams of 
processors in a self-scheduled manner.}
\par
A crucial feature of the program is the global hashtable.  Hashtables are 
important in the sequential case, but are even more central for a parallel 
chess algorithm.  The table not only stores knowledge but also makes the 
decision at each node of the chess tree whether to stay sequential or to split 
up the work in parallel.  In the language of Knuth and Moore, the 
transposition table decides whether each node of the chess tree is a type 2 or 
a type 3 node and acts accordingly.  For this data structure the hypercube is 
used as a shared-memory machine.  Multiple writes to the same location are 
resolved using a priority system which decides which entry is of more value to 
the program.  The hashtable effectively forms a ``smart'' shared memory.
\par
Search times for related subtrees vary widely (up to a factor of 100) so 
dynamic reconfiguration of processors is necessary to concentrate on such 
``hot spots'' in the tree.  A first version of the program with dynamic load 
balancing has recently been completed and out-performs the non-load-balancing 
program by a factor of three.  The current speedup of the program is 
conservatively estimated to be 101 on 256 nodes and 170 for 512 nodes.  
Improvements to these efficiencies are possible and are being pursued.
\par
The program has played in several tournaments, facing both computers and 
people.  Most recently it scored 2--2 in the ACM North American Computer Chess 
Championship.

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf A Highly Parallel Chess Program}
\par\noindent
{\bf Edward W. Felten and Steve W. Otto}
\par\noindent
$\rm C^3P-579c$\ \ \ \ \ \ \ (Short Code:  Felten:88i)
\par
We have developed a parallel chess program to run on distributed memory,
multiple instruction stream computers.  The game tree is decomposed
between processors using a recursive version of the
principal-variation-splitting algorithm.  Search times for related
subtrees vary widely (up to a factor of 100) so dynamic reconfiguration
of processors is necessary to concentrate on ``hot spots'' in the tree.
A crucial feature of the program is the global hashtable; for this data
structure we use a distributed-memory machine in a shared-memory mode.
The speedup of the program is conservatively estimated to be 170 on a
512-processor NCUBE hypercube.}

\bigskip\starline\bigskip
\vbox{\par\noindent
{\bf Transparencies} from a poster session by E. Felten, entitled
``Parallel Branch and Bound Algorithm'', presented at the Third
Conference on Hypercube Concurrent Computers and Applications, January
1988.  C$^3$P-534 (Short Code: Felten:88j)}

\bigskip\starline\bigskip
\vbox{\par\noindent
{\bf Transparencies} from a poster session by E. Felten {\it et al.},
entitled ``Coherent Parallel C'', presented at the Third Conference on
Hypercube Concurrent Computers and Applications, January 1988.
C$^3$P-537 (Short Code: Felten:88k)}

\bigskip\starline\bigskip
\vbox{\par\noindent
{\bf Transparencies} from a talk by E. Felten {\it et al.}, entitled
``Chess on a Hypercube'', presented at the Third Conference on Hypercube
Concurrent Computers and Applications, January 1988.  C$^3$P-546 (Short
Code: Felten:88m)}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Parallel Programming in Comfort}
\par\noindent
{\bf Jon Flower}
\par\noindent
$\rm C^3P-531$\ \ \ \ \ \ \ (Short Code:  Flower:88a)
\par
We describe a set of software utilities designed to facilitate the writing of 
parallel codes and porting sequential ones.  Emphasis is placed on 
portability so that code can be developed simultaneously on a sequential and 
a parallel machine, and so that the completed code can be run and maintained 
on a wide variety of machine architectures.}
\par
We describe the CrOS communication package for parallel machines, the CUBIX 
system to allow a code to run in parallel or sequentially, the PLOTIX parallel 
graphics foundation, and the parallel debugger NDB.
\par
While the system described has been implemented on qualitatively different 
machines the particular version described here is most efficient for the 
hypercube architecture, and was developed on NCUBE hypercubes under both the 
AXIS or XENIX operating systems.

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Lattice Gauge Theory on the Hypercube}
\par\noindent
{\bf John Apostolakis, Clive Baillie, Hong-Qiang Ding, and Jon Flower}
\par\noindent
$\rm C^3P-605$\ \ \ \ \ \ \ (Short Code:  Flower:88b)
\par
Lattice gauge theory, an extremely computationally intensive problem, has been 
run successfully on hypercubes for a number of years.  Herein we give a flavor 
of this work, discussing both the physics and the computing behind it.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf What Have We Learned from Using Real 
Parallel Machines to Solve Real Problems?}
\par\noindent
{\bf Geoffrey C. Fox}
\par\noindent
$\rm C^3P-522$\ \ \ \ \ \ \ (Short Code:  Fox:88b)
\par
We briefly review some key scientific and parallel processing issues in a 
selection of some 84 existing applications of parallel machines.  We include 
the MIMD hypercube transputer array, BBN Butterfly, and the SIMD ICL DAP, 
Goodyear MPP, and Connection Machine from Thinking Machines.  We use a space-
time analogy to classify problems and show how a division into synchronous, 
loosely synchronous and asynchronous problems is helpful.  This classifies 
problems into those suitable for SIMD or MIMD machines, and isolates the 
asynchronous class as that for which major uncertainties as to possible 
parallelism exist.  Interestingly, about half of the scientific applications 
run excellently on SIMD machines with the other half able to take special 
advantage of the MIMD architecture.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Problems and Approaches for a Teraflop 
Processor}
\par\noindent
{\bf Alexander H. Frey and Geoffrey C. Fox}
\par\noindent
$\rm C^3P-606$\ \ \ \ \ \ \ (Short Code:  Fox:88d)
\par
This paper discusses problems associated with designing a processor capable of 
sustaining a teraflop ($10^{12}$ floating point operations per second) of 
processing power.  Several researchers have speculated on achieving this 
performance.  The technical problems of a practical design are shown to be 
formidable.  However, none of these problems requires a technology 
breakthrough for their solution.  The predictable advances of the next 
generation of technology together with a major engineering effort is all that 
will be required to build such a parallel machine with usable teraflop 
processing power.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Load Balancing Loosely Synchronous 
Problem with a Neural Network}
\par\noindent
{\bf G. C. Fox and W. Furmanski}
\par\noindent
$\rm C^3P-363b$\ \ \ \ \ \ \ (Short Code:  Fox:88e)
\par
Hopfield and Tank have introduced the use of neural networks for the solutions 
of optimization problems such as the traveling salesman problem.  Here we show 
how to generalize this method to decompose {\it loosely synchronous} problems 
onto parallel machines and in particular the hypercube.  In this case, 
decomposition or load balancing can be formulated graph theoretically in terms 
of optical partitioning of the {\it computational graph} into $N = 2^d$ 
subgraphs.  The algorithm has a suggestive spin system interpretation, with 
the ferromagnetic interaction minimizing the communication and the long range 
paramagnetic force balancing the load.  The optimal fixed point of the network 
is in the Higgs phase of the magnet, with the domains of constant spontaneous 
magnetization representing the optimal decomposition map.}
\par
The method is fast, reliable and admits various simple implementations: 
sequential concurrent on the hypercube, analog on the neural network with 
adaptive weights (``learning'').
\par
We analyze the sequential performance of various mean field based network 
algorithms and we compare the network approach with the statistical Monte 
Carlo techniques of simulated annealing.

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf A String Theory for Time Dependent 
Complex Systems and its Application to Automatic Decomposition}
\par\noindent
{\bf Geoffrey C. Fox and Wojtek Furmanski}
\par\noindent
$\rm C^3P-521$\ \ \ \ \ \ \ (Short Code:  Fox:88f)
\par
We introduce a string or world line formalism that provides a general 
description of time dependent complex systems.  We show that it can be applied 
to mapping general problems onto both sequential and parallel computers.  In 
principle it unifies the concepts of an optimizing compiler with that of 
parallel decomposition.  We show that it reproduces and smoothly interpolates 
both our original load balancing methods for {\it loosely synchronous} 
problems and optimal communication and combining algorithms such as {\it 
index} and {\it fold}.  We evaluate two explicit implementations, the {\it 
neural\_router} and {\it neural\_accumulator}, which use an optimizing neural 
network.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Hypercube Algorithms for Neural Network 
Simulation: The Crystal\_Accumulator and the Crystal\_Router}
\par\noindent
{\bf G. C. Fox and W. Furmanski}
\par\noindent
$\rm C^3P-405b$\ \ \ \ \ \ \ (Short Code:  Fox:88g)
\par
We discuss communication algorithms relevant for neural network modeling on 
distributed memory concurrent computers with a hypercube topology.  Full, 
intermediate (medium range) and sparse network connectivities are analyzed.  
We point out that the flexible hypercube topology allows for the efficient 
implementation of the broad class of network algorithms with a variety of 
connectivity patterns.  We find algorithms {\it index, crystal\_router, fold 
{\rm and\/} crystal\_accumulator} which are appropriate in different cases 
depending on the sparseness and regularity of the network interconnect.  We 
show that there are natural analogies between biological communication paths 
and the interconnects of a distributed memory concurrent computer.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Optimal Communication Algorithms for 
Regular Decompositions on the Hypercube}
\par\noindent
{\bf G. C. Fox and W. Furmanski}
\par\noindent
$\rm C^3P-314b$\ \ \ \ \ \ \ (Short Code:  Fox:88h)
\par
We discuss optimal communication and decomposition algorithms for a class of 
regular problems on concurrent computers with a hypercube topology, using a 
general technique we call the method of cube geodesics.}
\par
We address the calculation of various transformations (convolutions, 
functionals, etc.) of data distributed over the hypercube; examples are the 
Fast Fourier Transform, matrix algorithms, global scalar products and vector 
sums, sorting.  These all involve long distance internode interactions and 
require more intricate communication that the simple local problems with 
static spatial decomposition such as partial differential equations.
\par
We believe that our library of optimal communication routines is applicable to 
these and many other problems.  The simple example of a database application 
is sketched.  We implement the algorithms on the Caltech/JPL Mark~II hypercube 
and present a detailed performance analysis.

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf High Performance Parallel Supercomputing 
Application, Hardware, and Software Issues for a Teraflop Computer}
\par\noindent
{\bf Geoffrey C. Fox and Alexander Frey}
\par\noindent
$\rm C^3P-451b$\ \ \ \ \ \ \ (Short Code:  Fox:88i)
\par
We discuss the issues that will be faced in developing a supercomputer with 
teraflop performance in the next few years.  Lessons of current parallel 
applications, hardware, and software are surveyed.  We consider MIMD systems 
with up to 64K nodes and show that a teraflop machine requires no technical 
breakthroughs and can be expected to have wide applicability.}

\bigskip\starline\bigskip
\vbox{\par\noindent
{\bf Transparencies} from a poster session by G. Fox {\it et al.},
entitled ``Further Details on Space-time Picture of Problems and
Computers --- I.  Particle-process Analogy'', presented at the Third
Conference on Hypercube Concurrent Computers and Applications, January
1988.  C$^3$P-533 (Short Code: Fox:88o)}

\bigskip\starline\bigskip
\vbox{\par\noindent
{\bf Transparencies} from a poster session by G. Fox {\it et al.},
entitled ``Further Details on Space-time Picture of Problems and
Computers --- II.  The [Time] Aspects of Problems and Dualty --- problem
[Space] $>$ Distributed Memory --- Problem [Time] $>$ Hierarchical
Memory'', presented at the Third Conference on Hypercube Concurrent Computers 
and Applications, January 1988.  C$^3$P-533b (Short Code: Fox:88p)}

\bigskip\starline\bigskip
\vbox{\par\noindent
{\bf Transparencies} from a poster session by G. Fox {\it et al.},
entitled ``Further Details on Space-time Picture of Problems and
Computers --- III.  Asynchronous and Dynamic Time Dependence --- The
String Formalism'', presented at the Third Conference on Hypercube Concurrent 
Computers and Applications, January 1988.  C$^3$P-533c (Short Code: Fox:88q)}

\bigskip\starline\bigskip
\vbox{\par\noindent
{\bf Transparencies} from a talk by G. Fox, entitled ``Current Status of
the Caltech Concurrent Computation Program'', presented at the DOE Site
Review, January 1988.  C$^3$P-616 (Short Code: Fox:88s)}

\bigskip\starline\bigskip
\vbox{\par\noindent
{\bf Transparencies} from a talk by G. Fox, entitled ``Future of
the Caltech Concurrent Computation Program'', presented at the DOE Site
Review, January 1988.  C$^3$P-617 (Short Code: Fox:88t)}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Issues in Software Development for
Concurrent Computers}
\par\noindent
{\bf Geoffrey C. Fox}
\par\noindent
$\rm C^3P-640$\ \ \ \ \ \ \ (Short Code:  Fox:88u)
\par
Over the last few years, substantial research, including that at
Caltech, has shown the viability of several parallel computer
architectures for a broad range of problems.  No longer need we ask
``does parallel computing work?'' but rather ``how does parallel
computing work?''  Aspects of the last question include ``which
architecture is appropriate for which problem?'' and ``how we build
software''.  These are related questions in that some of the hardware
architectural choices affect the programmability.  For instance, the
tradeoffs between distributed and shared memory are partly between
hardware cost and programmability.  In Fig.~1, we indicate four MIMD
architectures introduced in [Fox:87d] which have the tradeoffs between
construction, software and performance indicated in Table~1.}
\par
There are at least three rather difference approaches to programming
such machines which are shown in Fig.~2.

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Report for 1988 on the Caltech
Concurrent Computation Program}
\par\noindent
{\bf Geoffrey Fox and Paul Messina}
\par\noindent
$\rm C^3P-685$\ \ \ \ \ \ \ (Short Code:  Fox:88v)
\par
This annual report covers the research of the Caltech Concurrent Computation 
Program $\rm (C^3P)$ in the period December 1987 -- November 1988.  Previous 
annual reports are available as [Fox:86f] and [Fox:87c].  Our research is 
interdisciplinary and its organization is described in Sec.~IIA.  We consider 
$\rm C^3P's$ research to be in the area of ``Computational Science'' and this 
field is described in Sec.~IIC and elaborated in Sec.~X which outlines our 
educational activities.  Sec.~IIB describes our current status and
Sec.~IIID our plans for the next year.  These include stronger ties with 
Computer Science and Applied Mathematics as part of both our research and 
the development of Computational Science as an academic area.}
\par
The research of $\rm C^3P$ is described in Secs.~III through IX.  Each of 
these sections starts with a general overview and is followed by several
subsections describing particular projects within the area covered by
the section.  We note that the sophistication of the projects and their
descriptions are quite variable.  Some represent the work of established
research groups and others individual graduate student projects.  The index 
at the end of this document lists all these projects which are labeled
numerically within each section.
\par
This annual report concludes with a description of educational activities 
in Sec.~X.\ \ Sec.~XI lists $\rm C^3P$ researchers and collaborators with a 
cross reference to the earlier sections, as well as sponsors of our work.  
Sec.~XII lists reports produced as part of $\rm C^3P$ research.

\bigskip\starline\bigskip
\vbox{\par\noindent
{\bf Transparencies} from a talk by G. Fox, entitled ``Lessons from and
Future of Research in Parallel Computing in the Caltech Concurrent
Computation Program'', presented at the USC Symposium, December 1988.
C$^3$P-686 (Short Code: Fox:88x)}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Quarterly Report for Support of the
Caltech Initiative in Supercomputing}
\par\noindent
{\bf Geoffrey C. Fox, Paul C. Messina, and Thomas A. Prince}
\par\noindent
$\rm C^3P-633$\ \ \ \ \ \ \ (Short Code:  Fox:88y)
\par
This quarterly report describes work carried out under the Joint
Tactical Fusion Program at the California Institute of Technology.
Until January, the work had been part of a project at Caltech called the
Concurrent Supercomputing Initiative at Caltech (CSIC).  In January
1988, the Institute established an outgrowth of CSIC, the Caltech
Concurrent Supercomputing Facilities (CCSF).  Starting at that time, the
JTF work has been performed jointly by CCSF and the existing Caltech
Concurrent Computation Program $\rm (C^3P)$.}

\bigskip\starline\bigskip
\vbox{\par\noindent
{\bf Abstract} from G. Fox {\it et al.}, entitled ``The Use of Neural
Networks in Parallel Software Systems'', presented for the Purdue
Conference, December 1988.  C$^3$P-642 (Short Code: Fox:88aa)}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf The Use of Neural Networks in
Parallel Software Systems}
\par\noindent
{\bf G. Fox, W. Furmanski, and J. Koller}
\par\noindent
$\rm C^3P-642b$\ \ \ \ \ \ \ (Short Code:  Fox:88bb)
\par
A neural network is a highly interconnected set of simple neurons, the
network serving to pass the output value of each neuron to inputs of
others with given strengths.  Because of the parallelism involved, a
neural network is capable of significant computation.  However, unlike
a conventional computer, this power does not reside in the neurons
themselves, but in the pattern and strengths of the network connections,
which store both information and algorithms.  The network operates by
transforming a given initial set of output values into a stable final
configuration.  Thus to use a neural network as a computer, one picks
some interpretation for the possible configurations of outputs, then
``programs'' the network by adjusting the dynamics (possibly by
learning).  Applications suggested till not include content addressable
memory, combinatorial optimization, pattern matching, vision, and
various difficult artificial intelligence problems.}
\par
We discuss a view of computing that makes our neural network approach
feasible.  Then we examine a simpler limiting case, where we have
implemented some of these ideas as practical load balancing tools.  We
show how to solve routing problems and discuss (parallel) code
generation.  Since these problems require large networks, we also
discuss how network performance can be improved.  Finally, we discuss
how a course grained parallel processor could benefit from neural
networks, and envisible the user-friendly ``autonomous hypercube''.

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Code Generation by a Neural
Network:  General Principles and Elementary Examples}
\par\noindent
{\bf G. C. Fox and J. G. Koller}
\par\noindent
$\rm C^3P-650$\ \ \ \ \ \ \ (Short Code:  Fox:88cc)
\par
Analog neural networks can be used to solve complex computational
problems simply and quickly.  In their seminal paper, Hopfield and Tank
showed how the exponentially complex Traveling Salesman Problem could be
attacked by setting up a network of analog ``neurons''.  The neurons are
coupled together with interaction strengths that are functions of the
intercity distances, and the system is started in a random state and
allowed to come to equilibrium.  The final state of the system can then
be interpreted as an almost optimal path for the traveling salesman to
follow.}
\par
This example suggests neural networks may be useful in other practical
optimization problems, where a good but not necessarily optimal
solution is required.  The speed with which the network computes a
solution would more than make up for the slight loss of optimality.  In
this paper we investigate one such application.
\par
The optimization problem we consider is of great importance, namely the
code optimization performed by an optimizing compiler.  To be specific,
we look at the generation of machine code from compiler intermediate
code, because it is well defined and known to be NP-complete.  It may
turn out eventually that neural networks are more suited to some other
aspect of compiler optimization, but at this stage of our study we wish
merely to demonstrate the feasibility of a neural approach, show that
neural networks can handle the type of logic involved, and develop some
of the tools.
\par
To make this paper self-contained, we have included simple introductions
to neural networks and rudimentary compiler theory.

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Concurrent Supercomputers in Science}
\par\noindent
{\bf Geoffrey C. Fox and David Walker}
\par\noindent
$\rm C^3P-646$\ \ \ \ \ \ \ (Short Code:  Fox:88dd)
\par
We describe how advances in computer technology and parallel processing
will lead to powerful supercomputers.  We can expect by the year 2000,
to have machines with many terabytes of memory and teraflop performance,
i.e., capable of $10^{12}$ floating operations per second --- a factor
of $10^7$ better than an IBM-PC or VAX~11/780.  We expect such machines
to lead to a revolution in computational science.}
\par
We describe the technological trends, why parallel processing is (and
will continue to be) successful, and give examples of its application to
a variety of scientific fields.

\bigskip\starline\bigskip
\vbox{\par\noindent
{\bf Transparencies} from a talk by G. Fox {\it et al.}, entitled
``Lessons from and Future of Research in the Caltech Concurrent
Computation Program'', presented at the IBM Europe Institute on
Parallel-Vector Processing, July 1988.  C$^3$P-655 (Short Code: Fox:88ee)}

\bigskip\starline\bigskip
\vbox{\par\noindent
{\bf Transparencies} from a talk by G. Fox, entitled ``Applications of
Neural Networks (and Simulated Annealing) to Optimization Problems for
Complex Systems'', presented at the Fourth International Symposium on
Biological and Artificial Intelligence Systems, September 1988.
C$^3$P-667 (Short Code: Fox:88ff)}

\bigskip\starline\bigskip
\vbox{\par\noindent
{\bf Transparencies} from a talk by G. Fox, entitled ``Some
Applications of Neural Networks to Parallel Processing and Other
Problems'', presented at the Hughes Seminar, October 1988.  C$^3$P-675
(Short Code: Fox:88hh)}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Neural Network Techniques for
Parallel Processing}
\par\noindent
{\bf G. Fox, W. Furmanski, and J. Koller}
\par\noindent
$\rm C^3P-683$\ \ \ \ \ \ \ (Short Code:  Fox:88jj)
\par
Neural network hardware is currently being developed by many groups, and
neural devices will probably be generally available within the next five
years.  It is thus appropriate to ask if these advances can be of use in
conventional computers.  We have investigated applications of analog
neural networks as supporting devices for parallel processors, and
neural simulations as tools for problem decomposition, routing, load
balancing, and parallel code generation.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Neural Networks and Dynamic Complex
Systems}
\par\noindent
{\bf Geoffrey Fox, Wojtek Furmanski, Alex Ho, Jeff Koller, Petar Simic,
and Isaac Wong}
\par\noindent
$\rm C^3P-695$\ \ \ \ \ \ \ (Short Code:  Fox:88kk)
\par
We describe the use of neural networks for optimization and inference
associated with a variety of complex systems.  We show how a string
formalism can be used for parallel computer decompositions, message
routing and sequential optimizing compilers.  We extend these ideas to a
general treatment of spatial assessment and distributed artificial
intelligence.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf High Performance Parallel
Supercomputing Application, Hardware, and Software Issues for a Teraflop
Computer}
\par\noindent
{\bf Geoffrey C. Fox and Alexander Frey}
\par\noindent
$\rm C^3P-451c$\ \ \ \ \ \ \ (Short Code:  Fox:88ll)
\par
We discuss the issues that will be faced in developing a supercomputer
with teraflop performance in the next few years.  Lessons of current
parallel applications, hardware, and software are surveyed.  We consider
MIMD systems with up to $\rm 64\,K$ nodes and show that a teraflop
machine requires no technical breakthroughs and can be expected to have
wide applicability.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf A Review of Automatic Load Balancing
and Decomposition Methods for the Hypercube}
\par\noindent
$\rm C^3P-385$\ \ \ \ \ \ \ (Short Code:  Fox:88mm)
\par
We give a brief review of the research at Caltech on methods to
automatically decompose or load balance problems on the hypercube
concurrent computer.  We have several promising methods and are
implementing a dynamic load balancer on the hypercube.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf A Graphical Approach to Load
Balancing and Sparse Matrix Vector Multiplication on the Hypercube}
\par\noindent
{\bf Geoffrey C. Fox}
\par\noindent
$\rm C^3P-327b$\ \ \ \ \ \ \ (Short Code:  Fox:88nn)
\par
We consider the implementation on a hypercube concurrent computer, of
matrix vector multiplication $y=Ax$ where $A$ is a large sparse matrix.
A good decomposition is crucial for the case when each column of $A$ has
on the average fewer non-zero elements than there are nodes in the
hypercube.  We review simulated annealing and neural network methods for
generating a hypercube decomposition for this problem.  We introduce a
new graphical method, orthogonal recursive bisection, which can be
applied to general problems and is successful on this test case.  The
performance of the concurrent computer depends strongly on any
correlations in the placement of non-zero elements of $A$.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf The Hypercube and the Caltech
Concurrent Computation Program --- A Microcosm of Parallel Computing}
\par\noindent
{\bf Geoffrey C. Fox}
\par\noindent
$\rm C^3P-422$\ \ \ \ \ \ \ (Short Code:  Fox:88oo)
\par
We describe the history of the Caltech Concurrent Computation Program
which has developed the hypercube and shown it to be a relatively
general purpose supercomputer.  We contrast machines built at Caltech
with those developed commercially; both routes have their problems.  We
record our stumbling progress to an adequate set of software tools on
the hypercube and speculated on the lack of tools and standards as the
fundamental stumbling block to the rapid development of concurrent
computing.  Originally, we asked if parallel computing would ``work'';
the future will see the comparison of several viable architectures for
high performance concurrent supercomputers.  We anticipate some of the
issues that will arise as we compare fine grain machines like the
Connection Machine, shared memory machines like the BUTTERFLY, and
distributed memory computers like the Hypercube.}

\bigskip\starline\bigskip
\vbox{\par\noindent
{\bf Transparencies} from a talk by G. Fox {\it et al.}, entitled ``The
Prime Factor (non-binary) Discrete Fourier Transform (DFT) and Use of
Crystal Router as a General Purpose Communication Routine'', presented
at the Third Conference on Hypercube Concurrent Computers and
Applications, January 1988.  C$^3$P-505 (Short Code: Fox:88pp)}

\bigskip\starline\bigskip
\vbox{\par\noindent
{\bf Transparencies} from a talk by G. Fox, entitled ``What Have We
Learnt from Using Real Parallel Machines to Solve Real Problems?'',
presented at the Third Conference on Hypercube Concurrent Computers and
Applications, January 1988.  C$^3$P-506 (Short Code: Fox:88qq)}

\bigskip\starline\bigskip
\vbox{\par\noindent
{\bf Transparencies} from a poster session by G. Fox {\it et al.},
entitled ``Optimal Matrix Algorithms and Communication Routines on the
Hypercube'', presented at the Third Conference on Hypercube Concurrent
Computers and Applications, January 1988.  C$^3$P-510 (Short Code:
Fox:88rr)}

\bigskip\starline\bigskip
\vbox{\par\noindent
{\bf Transparencies} from a talk by G. Fox, entitled ``The Caltech
Concurrent Computation Program Status and Some Future Plans'', presented
at the Project Review, December 1988.  C$^3$P-698 (Short Code: Fox:88ss)}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf The Physical Structure of Concurrent
Problems and Concurrent Computers}
\par\noindent
{\bf Geoffrey C. Fox and Wojtek Furmanski}
\par\noindent
$\rm C^3P-493$\ \ \ \ \ \ \ (Short Code:  Fox:88tt)
\par
We introduce a physical analogy to describe problems with high
performance concurrent computers on which they are run.  We show that
the spatial characteristics of problems lead to their parallelism and
review the lessons from use of the early hypercubes and a natural
particle-process analogy.  We generalize this picture to include the
temporal structure of problems and show how this allows us to unify
distributed, shared, and hierarchical memories as well as SIMD
architectures.  We also show how neural network methods can be used to
analyze a general formalism based on interacting strings and these lead
to possible rela-time schedulers and decomposers for massively parallel
machines.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf The Physical Structure of Concurrent
Problems and Concurrent Computers}
\par\noindent
{\bf Geoffrey C. Fox and Wojtek Furmanski}
\par\noindent
$\rm C^3P-493$\ \ \ \ \ \ \ (Short Code:  Fox:88uu)
\par
We introduce a physical analogy to describe problems with high
performance concurrent computers on which they are run.  We show that
the spatial characteristics of problems lead to their parallelism and
review the lessons from use of the early hypercubes and a natural
particle-process analogy.  We generalize this picture to include the
temporal structure of problems and show how this allows us to unify
distributed, shared, and hierarchical memories as well as SIMD
architectures.  We also show how neural network methods can be used to
analyze a general formalism based on interacting strings and these lead
to possible rela-time schedulers and decomposers for massively parallel
machines.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf g --- A Compact Language for Real-time 
Graphics}
\par\noindent
{\bf W. Furmanski and D. Gates}
\par\noindent
$\rm C^3P-585$\ \ \ \ \ \ \ (Short Code:  Furmanski:88a)
\par
We propose a medium level C-based language for computer graphics applications.  
The main objective is to provide real-time graphics (interactive video), hence 
the emphasis in the language design is on optimal speed of the machine code 
(to minimize system overheads) and on the compactness of the g code (so that 
no manuals are necessary).}
\par
The language coexists and fully cooperates with C.  The modular structure of 
the g data sector admits various programming models (sequential/concurrent, 
local/network extended).  Portable design of the g compiler allows for various 
graphics configurations with adjustable speed/portability ratio.  The 
compiler output is machine-independent ``machine'' code, to be explicitly 
interpreted on a given graphics device.
\par
The g programming environment consists of a g compiler (written in C), a 
portable (but slow) g interpreter (written in C) and a set of optimized 
interpreters for individual machines/devices (written in assembly).

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Optimal Matrix Algorithms on Homogeneous 
Hypercubes}
\par\noindent
{\bf Geoffrey C. Fox, Wojtek Furmanski, and David W. Walker}
\par\noindent
$\rm C^3P-386b$\ \ \ \ \ \ \ (Short Code:  Furmanski:88b)
\par
This paper describes a set of concurrent algorithms for matrix algebra, based 
on a library of collective communication routines for the hypercube.  We show 
how a systematic application of scattering reduces load imbalance.  A number 
of examples are considered (Gaussian elimination, Gauss-Jordan matrix 
inversion, the power method for eigenvectors, and tridiagonalization by 
Householder's method), and the concurrent efficiences are discussed.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Integrated Vision Project on the
Computer Network}
\par\noindent
{\bf W. Furmanski and G. C. Fox}
\par\noindent
$\rm C^3P-623$\ \ \ \ \ \ \ (Short Code:  Furmanski:88c)
\par
We discuss a project involving the integration of early vision modules,
which can be considered as the first step towards a real time machine
vision system.  Various software and hardware issues associated with
such a large scale computation are analyzed.  A multilayer design for
early vision is proposed, inspired by current multigrid techniques and
offering a convenient tool for module integration and for various
distributed implementations.}

\bigskip\starline\bigskip
\vbox{\par\noindent
{\bf Transparencies} from a poster session by W. Furmanski, entitled
``Real Time Graphics for Complex Systems'', presented at the Third
Conference on Hypercube Concurrent Computers and Applications, January
1988.  C$^3$P-555 (Short Code: Furmanski:88d)}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf A Hypercube Ray-tracer}
\par\noindent
{\bf John Salmon and Jeff Goldsmith}
\par\noindent
$\rm C^3P-592$\ \ \ \ \ \ \ (Short Code:  Goldsmith:88a)
\par
We describe a hypercube ray-tracing program for rendering computer graphics.  
For small models, which fit in the memory of a single processor, the ray-
tracer uses a scattered decomposition of pixels to balance the load, and 
achieves a very high efficiency.  The more interesting case of large models, 
which cannot be stored in a single processor, requires a decomposition of the 
model data as well as the pixels.  We present algorithms for constructing a 
decomposition based upon information about the frequency with which different 
elements of the model are accessed.  The resulting decomposition is 
approximately optimized to minimize communication and achieve load balance.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Hypercube Data Analysis in Astronomy:  
Optical Interferometry and Millisecond Pulsar Searches}
\par\noindent
{\bf Peter Gorham, Thomas Prince, and Stuart Anderson}
\par\noindent
$\rm C^3P-571$\ \ \ \ \ \ \ (Short Code:  Gorham:88a)
\par
Astronomical data sets are beginning to live up to their name, in both their 
sizes and the complexity of the analysis required.  Here, we discuss two 
astronomical data analysis problems which we have begun to implement on a 
hypercube concurrent processor environment:  The intensive image processing 
required in an optical interferometry project, and the large scale power 
spectral analysis required by a search for millisecond-period radio pulsars.  
In both cases, the analysis proceeds largely in the Fourier domain, and we find 
that the problems are readily adopted to a concurrent environment.  In the 
following report, we outline briefly the astronomical background for each 
problem, then discuss the general computational requirements, and finally 
present possible hypercube algorithms and results achieved to date.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Computational Aspects of Bispectral
Analysis in Interferometric Imaging}
\par\noindent
{\bf Peter W. Gorham}
\par\noindent
$\rm C^3P-637$\ \ \ \ \ \ \ (Short Code:  Gorham:88b)
\par
Although many approaches to phase recovery in the techniques of speckle
interferometry and discrete-element optical interferometry are now being
currently used, the most promising are those which make use of the
closure phase principle (Jennison 1957; Rogstad 1968), which provides an
observable phase which is immune to atmospheric corruption, and contains
the desired object phases.  The general mathematical support for the
closure phase quantity is provided by the bispectrum function (Hoffmann,
et al. 1983;), which is a third moment of the complex visibility of the
observed (and therefore atmospherically corrupted) source distribution.
Specifically, triple products of all visibility elements which can be
mapped onto a triangle of discrete interferometer elements, are included
in the bispectrum.  This constraint implies that the bispectrum volume
spans four dimensions, since it is effectively a vector product of the
aperture plane with itself, corresponding to the two independent legs of
the baseline triangles.}
\par
In the following, we discuss progress we have made with developing
algorithms to minimize the computational and storage needs of the full
bispectrum and find powerful and cheap computers to do the job.  We have
assumed that the solution to compute only a reduced portion of the
bispectrum, chosen to provide adequate information for the image
reconstruction but perhaps sacrificing some dynamic range in the final
map, will ultimately be deemed unsatisfactory if these techniques are to
be pushed to their limits.  We have also avoided using a CRAY or
comparable machine because we were interested in exploring the
alternative of relatively inexpensive concurrent processing computers,
which we feel will soon supplant the sequential machines such as the
CRAY series for large scale data analysis.

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Speckle/Bispectrum Results}
\par\noindent
{\bf Peter Gorham}
\par\noindent
$\rm C^3P-705$\ \ \ \ \ \ \ (Short Code:  Gorham:88c)
\par
In this memo, which is the first attempt to flesh out the ideas for
forthcoming paper(s), we will cover the following:
\item{(1)}CLEAN as an amplitude calibration technique for FFA and
annulus speckle data (and probably also NRM);
\item{(2)}Bispectral analysis reconstructions of BS5747 $\rm (\beta
CrB)$, and 2~Pallas, from the April and July data sets, respectively.}
\par
We would appreciate any feedback on this stuff.  There are some obvious
holes which we will try to fill in later iterations; these will be
mentioned as we go along.  But since I think we are finally on the
downhill side of the FFA and annulus imaging, it is time to begin to
collect our thoughts.

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Concurrent Multiple Target Tracking}
\par\noindent
{\bf Thomas D. Gottschalk}
\par\noindent
$\rm C^3P-567$\ \ \ \ \ \ \ (Short Code:  Gottschalk:88a)
\par
A concurrent algorithm for multiple target tracking is presented.  The 
underlying tracking formalism is first described by way of a sequential 
program, and the issues in generalizing the tracker for efficient concurrent 
implementations are discussed in detail.  Typical tracking results on the 
Mark~III hypercube are presented.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Ada Tasking on the Sequent Balance}
\par\noindent
{\bf Mike Griffiths}
\par\noindent
$\rm C^3P-626$\ \ \ \ \ \ \ (Short Code:  Griffiths:88b)
\par
The aim of this study was to evaluate the Ada tasking environment on a
shared memory architecture and to investigate whether Ada program
structure would be significantly altered in a distributed memory
environment.  The configuration used was a Sequent Balance~21000 with 24
processors, 24~MB of memory together with the Verdix Ada Development
System (V5.41) in its parallel mode.  This system was at Argonne
National Laboratory.}
\par
The method chosen was to recode, in Ada for the Sequent, two problems
which were fairly well understood in their C versions on the hypercube.
The problems were picked so as to be as different in structure as
possible:  the first (solving the one-dimensional wave equation) is {\it
regular\/} in the sense that decomposition is simple from the geometry
of the problem and communication occurs at well-defined intervals.  The
second (the traveling salesman solved by branch and bound techniques) is
{\it irregular\/} in that decomposition is not obvious from the
structure and communication is unpredictable.

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Ada Tasking on the Sequent Balance}
\par\noindent
{\bf Mike Griffiths}
\par\noindent
$\rm C^3P-545$\ \ \ \ \ \ \ (Short Code:  Griffiths:88c)
\par
The aim of this study is to evaluate the Ada tasking environment on a
Sequent Balance.  The configuration is:
\item{$\bullet$}Sequent Balance 8000
\item{$\bullet$}10 processors (only eight used)
\item{$\bullet$}16 MB shared memory
\item{$\bullet$}Verdix ADA Development System (VADS) V5.41}
\par
In order to have some means for comparison, we chose a well understood
problem as a test, the solution of the one-dimensional wave equation.
It was hoped to answer the following questions:
\item{$\bullet$}How does writing a program in Ada using the rendezvous
compare to using the Caltech Crystalline Operation System (CrOS).
\item{$\bullet$}How efficient is the rendezvous in this implementation.
\item{$\bullet$}Does the solution ``scale'' properly.

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Design and Implementation of a
Concurrent Image Processing Workstation Based on the Mark~III Hypercube}
\par\noindent
{\bf Steven L. Groom, Meemong Lee, Alan S. Mazer, and Winifred I.
Williams}
\par\noindent
$\rm C^3P-599$\ \ \ \ \ \ \ (Short Code:  Groom:88a)
\par
Various image processing algorithms have been implemented on the
hypercube architecture and many success stories have been reported.
However, the traditional approach to programming the hypercube has been
to write programs which perform a single operation or a fixed set of
operations upon data items.  This approach has several drawbacks when
considered for use in an interactive computing environment.  First, it
is difficult to process data with a sequence of simple programs in the
Mark~III Hypercube because the Mark~III software does not support
sharing of data between successive programs.  This means that data must
be reloaded into the cube for each individual program.  It also implies
that programs should be fairly large and complete, to minimize the
repeated downloading of large data items for multiple programs.
However, the entire program must be able to fit within the hypercube
node memory, which limits what a program can do by putting a restriction
on its size.  Furthermore, large programs limit the amount of memory
available for data, which must also be present in memory if the
communications overhead is to be effectively reduced.  The development
of an interactive image processing workstation based on the Mark~III
Hypercube requires satisfactory solutions to these and other problems.}
\par
The voluminous nature of certain types of image data makes the
availability of ample memory space a special concern, which tends to rule
out large, complex programs.  However, the flexibility required to be
effective in an interactive environment tends to require just such a
program.  Clearly, another method for dealing with the tradeoff between
volume of data and program size and complexity is needed.
\par
One approach to the problem of limited memory size is to load the
complete program into the cube, and feed the data to the cube in pieces
small enough to fit into the available memory.  When the program
finishes with a piece, the piece is released and the next one downloaded
and processed, and so on until the data has been processed.  This
approach works for some problems, but not for others which need repeated
access to different parts of the data, making a single pass over the
data insufficient.  Even if a single pass is sufficient, the data must
still be sent to the cube and results sent back for each operation (or
sequence of operations) performed.

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf The Phase Transition in the 2-D XY
Model}
\par\noindent
{\bf Rajan Gupta, Jerry DeLapp, George G. Batrouni}
\par\noindent
$\rm C^3P-643$\ \ \ \ \ \ \ (Short Code:  Gupta:88a)
\par
We present detailed results for the susceptibility, correlation length
and specific heat for the $XY$ model near the critical point calculated
on the FPS T-Series hypercube.  The best fit to both the susceptibility
and the correlation length data is obtained using the
Kosterlitz-Thouless scaling form and gives $\nu = 0.500(1)$.  The
critical temperature is estimated to be $T_c = 0.898(1)$.  The exponent
$\eta$ shows considerable deviation from 1/4 down to $T=1.03$.  The
simulations are done on $64^2$, $128^2$, $256^2$ and $512^2$ lattices
using an over-relaxed algorithm.  With present optimization this
algorithm decorrelates as $\tau = 0.15\xi^{1.2}$.  Similar reduction in
critical slowing down is anticipated for all continuous spin models and
lattice gauge theories.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Finite Element Solution of Thermal
Convection on a Hypercube Concurrent Computer}
\par\noindent
{\bf Michael Gurnis, Arthur Raefsky, Gregory A. Lyzenga, and Bradford H.
Hager}
\par\noindent
$\rm C^3P-595$\ \ \ \ \ \ \ (Short Code:  Gurnis:88a)
\par
Numerical solutions to thermal convection flow problems are vital to
many scientific and engineering problems.  One fundamental geophysical
problem is the thermal convection responsible for continental drift and
sea floor spreading.  The earth's interior undergoes slow creeping flow
$\rm (\sim cm/yr)$ in response to the buoyance forces generated by
temperature variations caused by the decay of radioactive elements and
secular cooling.  Convection in the earth's mantle, the $\rm 3000\,km$
thick solid layer between the crust and core, is difficult to model for
three reasons: (1) Complex rheology --- the effective viscosity depends
exponentially on temperature, on pressure (or depth) and on the
deviatoric stress; (2) the buoyance forces driving the flow occur in
boundary layers thin in comparison to the total depth; and (3) spherical
geometry --- the flow in the interior is fully three dimensional.
Because of these many difficulties, accurate and realistic simulations
of this process easily overwhelm current computer speed and memory
(including the CRAY~X-MP and CRAY~2) and only simplified problems have
been attempted (e.g., Christensen and Yuen, 1984; Furnis, 1988; Jarvis
and Peltier, 1982).}
\par
As a start in overcoming these difficulties, a number of finite element
formulations have been explored on hypercube concurrent computers.
Although two coupled equations are required to solve this problem (the
momentum or Stokes equation and the energy or advection-diffusion
equation), we will concentrate our efforts on the solution to the latter
equation in this paper.  Solution of the former equation is discussed
elsewhere (Lyzenga, et al., 1988).  We will demonstrate that linear
speedups and efficiencies of 99 percent are achieved for sufficiently
large problems.

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Gauss-Jordan Inversion with Pivoting on 
the Caltech Mark~II Hypercube}
\par\noindent
{\bf Paul G. Hipes and Aron Kuppermann}
\par\noindent
$\rm C^3P-578$\ \ \ \ \ \ \ (Short Code:  Hipes:88a)
\par
The performance of a parallel Gauss-Jordan matrix inversion algorithm on the 
Mark~II hypercube at Caltech is discussed.  We will show that parallel Gauss-
Jordan inversion is superior to parallel Gaussian elimination {\it for 
inversion}, and discuss the reasons for this.  Empirical and theoretical 
efficiencies for parallel Gauss-Jordan inversion as a function of matrix 
dimension for different numbers and configurations of processors are 
presented.  The theoretical efficiencies are in {\it quantitative\/} agreement 
with the empirical efficiencies.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Chemical Reaction Dynamics: Integration 
of Coupled Sets of Ordinary Differential Equations on the Caltech Hypercube}
\par\noindent
{\bf Paul G. hipes, Tim Mattson, Mark Y.-S. Wu, and Aron Kuppermann}
\par\noindent
$\rm C^3P-570$\ \ \ \ \ \ \ (Short Code:  Hipes:88b)
\par
Use of the Caltech/JPL hypercube multicomputer to solve problems in chemical 
dynamics is the subject of this paper.  The specific application is quantum 
mechanical atom diatomic molecule reactive scattering.  one methodology for 
solving this dynamics problem on a sequential computer is based on symmetrized 
hyperspherical coordinates.  We will discuss our strategy for implementing the 
hyperspherical coordinate methodology on the hypercube.  In particular, the 
performance of a parallel integrator for the special system of ordinary 
differential equations which arises in this application is discussed.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf A Gauss-Jordan Decomposition and
System Solver for Distributed Memory Multicomputers}
\par\noindent
{\bf Paul G. Hipes}
\par\noindent
$\rm C^3P-652$\ \ \ \ \ \ \ (Short Code:  Hipes:88c)
\par
I will discuss the advantages of a new Gauss-Jordan type algorithm for
solving systems of equations in multicomputer environments.  Three main
points are made.  First, by saving the Gauss-Jordan multipliers, it is
possible to solve subsequent right hand sides {\it a posteriori\/} in
the same number of operations as when the LU decomposition of the
coefficient matrix is available.  Second, on a hypercube the calculation
of the multipliers requires nearly the same {\it execution time\/} as
the construction of the LU decomposition.  Finally, on a hypercube the
Gauss-Jordan solution phase is significantly faster than solving two
triangular systems as required using the LU decomposition.  These points
are valid for full coefficient matrices.}

\bigskip\starline\bigskip
\vbox{\par\noindent
{\bf Transparencies} from a poster session by P. Hipes {\it et al.},
entitled ``Integration of Coupled Sets of Ordinary Differential
Equations on the Caltech Hypercubes:  Matrix Inversion'', presented at
the Third Conference on Hypercube Concurrent Computers and Applications,
January 1988.  C$^3$P-548 (Short Code: Hipes:88d)}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf PC-CUBE, the IBM PC-based Hypercube}
\par\noindent
{\bf Alex Ho, Geoffrey Fox, David Walker, Scott Snyder, Douglas Chang, 
Stanley Chen, Matt Breaden}
\par\noindent
$\rm C^3P-587$\ \ \ \ \ \ \ (Short Code:  Ho:88a)
\par
PC-CUBE is an ensemble of IBM PCs or close compatibles connected in the 
hypercube topology with ordinary computer cables.  Communication occurs at the 
rate of 115.2~K-baud via the RS-232 serial links.  Available for PC-CUBE is 
the Crystalline Operating System III (CrOS III), Mercury Operating System, 
CUBIX and PLOTIX which are parallel I/O and graphics libraries.  A CrOS 
performance monitor was developed to facilitate the measurement of 
communication and computation time of a program and their effects on 
performance.  Also available are CXLISP, a parallel version of the XLISP 
interpreter; GRAFIX, some graphics routines for the EGA and CGA; and a general 
execution profiler for determining execution time spent by program 
subroutines.  PC-CUBE provides a programming environment similar to all 
hypercube systems running CrOS III, Mercury and Cubix.  In addition, every 
node (personal computer) has its own graphics display monitor and storage 
devices.  These allow data to be displayed or stored at every processor, which 
has much instructional value and enables easier debugging of applications.  
Some application programs which are taken from the Book "Solving Problems on 
Concurrent Processor" [Fox:88a] were implemented with graphics enhancement on 
PC-CUBE.  The applications range from solving the Mandelbrot set, Laplace 
equation, wave equation, long range force interaction, to WaTor, an ecological 
simulation.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Mac-Cube User's Guide}
\par\noindent
{\bf Alex W. Ho, Matt Breaden, and Stanley Chen}
\par\noindent
$\rm C^3P-582$\ \ \ \ \ \ \ (Short Code:  Ho:88b)
\par
Mac-Cube was developed in the summer of 1987 as one of the Caltech
Summer Undergraduate Research Fellowship projects.  Message-passing on
Mac-Cube is based on Mac-CrOS which is an implementation of the
Crystalline Operating System~III for the Macintosh family of personal
computers (Mac, Mac Plus, Mac SE, and Mac //).  Communication is
supported through the AppleTalk local area network.  The system is
highly compatible with Caltech/JPL (also known as the $\rm C^3P$ ---
Caltech Concurrent Computation Program) hypercube CrOS~III.  It is
assumed that the reader is familiar with Chapter~10 of {\it Solving
Problems with Concurrent Processors\/} by Fox, et al. (Prentice Hall,
1989) and with the CrOS reference manual $\rm (C^3P-253b)$, as well as
with the Macintosh computer and the Macintosh Programmer's Workshop
(MPW) software.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Pattern Recognition by Neural Network 
Model on Hypercubes}
\par\noindent
{\bf Alex Ho and Wojtek Furmanski}
\par\noindent
$\rm C^3P-528$\ \ \ \ \ \ \ (Short Code:  Ho:88c)
\par
The objective of this work is to study the performance characteristics of the 
back-propagation model for pattern recognition.  Specifically, the test case 
of recognition of Chinese characters is studied on an ELXSI-6400 and Mark~III 
hypercube.  Preliminary results indicate that local spatial decomposition of 
characters in the training set leads to simple parallel implementation of the 
neural net model on hypercubes, and also serves as an effective pre-processor 
which provides high quality of recognition and good efficiency.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf MAC-CUBE, The Macintosh-Based Hypercube}
\par\noindent
{\bf Alex Ho, Geoffrey Fox, David Walker, Matt Breaden, Stanley Chen, Allen 
Knutson, Sho Kuwamoto, and Terry Cole}
\par\noindent
$\rm C^3P-573$\ \ \ \ \ \ (Short Code:  Ho:88d)
\par
The MAC-CUBE is a Macintosh-based hypercube.  It uses Appletalk hardware and 
software as the medium for the nodal connections.  At the physical level 
Appletalk has a bus topology.  Hypercube connectivity is emulated on the 
Appletalk local area network while the hypercube communication protocol is 
integrated in the Appletalk software.  Available for MAC-CUBE is the 
Crystalline Operating System~III (CrOS III).  MAC-CUBE provides a programming 
environment similar to any other hypercube systems running CrOS~III.  It 
allows inexpensive hands-on experience with a concurrent machine.  Data can be 
displayed on graphics monitor and/or stored locally at each node.  In addition 
to the low cost, these capabilities of the Mac-Cube makes it an indispensable 
instructional and development tool for parallel processing.  Some application 
programs which are taken from the book, "Solving Problems on Concurrent 
Processors" [Fox:88a] have been implemented with graphics enhancement on Mac-
Cube.  The applications are solving the Mandelbrot set in the complex plane, 
and solving a two-dimensional Laplace equation using finite difference.}

\bigskip\starline\bigskip
\vbox{\par\noindent
{\bf Transparencies} from a poster session by A. Ho {\it et al.},
entitled ``PC-CUBE'', presented at the Third Conference on Hypercube
Concurrent Computers and Applications, January 1988.  C$^3$P-558 (Short
Code: Ho:88e)}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf CXLISP --- A Concurrent XLISP
Interpreter on the Hypercube}
\par\noindent
{\bf Alex W. Ho and Scott Snyder}
\par\noindent
$\rm C^3P-559$\ \ \ \ \ \ \ (Short Code:  Ho:88f)
\par
Concurrent XLISP (CXLISP) on PC-Cube, the IBM PC-based hypercube, is
version 1.7 of David Betz's XLISP experimental Lisp interpreter with
Mercury functions added to it.  Originally, CXLISP was an implementation
of version 1.4 of XLISP on Mark~III hypercube by Alan Louie and Alan
Bond.  The PC-Cube implementation is essentially the same as the
Mark~III version except for minor modifications.}
\par
XLISP is an implementation of a LISP interpreter with an experimental
object-oriented extension capability on small computers.  Currently, it
has been implemented on VAX under VAX/VMS, on 8086/8088 under MS-DOS, on
68000 under CP/M-68k, on the Apple Macintosh, on the Atari 520ST and
also on Amiga.
\par
In addition to many built-in traditional LISP functions, XLISP defines
the objects {\it Object\/} and {\it Class\/} as primitives.  {\it
Object\/} is the root of the class hierarchy tree and {\it Class\/} is
the only object of which all classes are instances.
\par
The current design of CXLISP implements nine new built-in functions of
which six are Mercury functions. The control processor (CP) and node
programs are identical except for the top level main routine.  They use
the same object files for all of the other function subroutines.

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Parallel 3D Asteroids, a Status
Report}
\par\noindent
{\bf Alex W. Ho, Geoffrey C. Fox, Scott Snyder, Diana Chu, and Ted
Mlynar}
\par\noindent
$\rm C^3P-681$\ \ \ \ \ \ \ (Short Code:  Ho:88h)
\par
We have implemented on NCUBE a 3D Asteroids video game.  The Asteroids
features battle of spacecrafts in a 3D toroidal space with inert
meteorites of various sizes.  The game supports multi-players and mixed
communication protocols.  It can be played either in interactive or
batch mode.  In interactive mode a player can maneuver a spacecraft by
keyboard or graphics tablet control.  3D visual display of the game uses
the NCUBE Real-Time Parallel Graphics Board which has 16 NCUBE processors
and a Hitachi HD63484 drawing/video chip.  In batch mode spacecrafts can
be controlled by user-supplied software controllers.  The modular
structure of the game allows easy replacement of game objective, game
rules, and spacecraft controllers.  the flexibility of module
substitution allows the game be used as a test-bed for different
implementation of controller strategies and algorithms which are
constrained by various game rules.}

\bigskip\starline\bigskip
\vbox{\par\noindent
{\bf Transparencies} from a poster session by A. Ho {\it et al.},
entitled ``The MAC-CUBE, a Macintosh-based Hypercube'', presented at the
Third Conference on Hypercube Concurrent Computers and Applications,
January 1988.  C$^3$P-544 (Short Code: Ho:88i)}

\bigskip\starline\bigskip
\vbox{\par\noindent
{\bf Transparencies} from a talk by A. Ho {\it et al.}, entitled
``Pattern Recognition by Neural Network on Hypercubes'', presented at
the Third Conference on Hypercube Concurrent Computers and Applications,
January 1988.  C$^3$P-552 (Short Code: Ho:88j)}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf The Status of the Time Warp Operating 
System}
\par\noindent
{\bf David Jefferson, Brian Beckman, Fred Wieland, Leo Blume, Michael 
DiLoreto, Phillip Hontalas, Peter Reiher, Kathryn Sturdevant, Jack Tupman, 
John Wedel, and Herb Younger}
\par\noindent
$\rm C^3P-627$\ \ \ \ \ \ \ (Short Code:  Jefferson:88a)
\par
The Time Warp Operating System (TWOS) is a special-purpose operating system 
designed to support parallel discrete event simulation.  It has been under 
experimental development at the Jet Propulsion Laboratory for four years, and 
runs primarily on the JPL/Caltech Mark~III Hypercube, although it has been 
ported to several other systems.  Its main distinction is that it incorporates 
a full implementation of the Time Warp mechanism, which is based on the 
unusual synchronization primitives of process rollback and message-antimessage 
annihilation.}
\par
In this paper, we discuss the status of the TWOS project at JPL, and present 
preliminary data from some of the performance experiments we have conducted on 
a Pool Balls benchmark, along with our analysis of them.

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf The Two Screen Gravitational Lens}
\par\noindent
{\bf Christopher S. Kochanek and John Apostolakis}
\par\noindent
$\rm C^3P-644$\ \ \ \ \ \ \ (Short Code:  Kochanek:88a)
\par
Gravitational lensing by systems of two galaxy-like potentials located
at different redshifts and separations are studied.  We show that there
is roughly a 1--10\% chance of a gravitational lens system begin
affected by two lenses at the same redshift, and that there is roughly a
1--10\% chance of a gravitational lens system being affected by two
lenses at different redshifts.  We show that two lenses interact
significantly for transverse separations $\lea 4r_{+,0}$ where $r_{+,0}$
is the radius of the outer critical line of the singular potential.
Nearly aligned lenses at different redshifts show interactions over
almost all of redshift space.  The interactions can lead to either
increases or decreases in the total cross section relative to the cross
section of two isolated lenses depending on the system's geometry, and
the amplification of the brightest images.  Section increases or
decreases relative to a system of two isolated lenses depends both on
the geometry of the system, and on the magnification of the brightest
images.  The behavior of the image structures is dominated by the
effects of caustics, and in particular the fold caustics, as in the
single screen case.  Typical image separations are $\sim 2r_{+,0}$ as
in the isolated lenses; larger separations are found only as the
distance between the most widely separate images in the lens, in which
case the separations approach $\sim 4r_{+,0}$.  This means that
``chaining'' marginal lenses together cannot explain the so called dark
matter lenses $2345+007$, $1635+267$, and $0023+171$ for which there are
only two images widely separated images.  Highly amplified images are
almost always part of a high image multiplicity system (five to seven
images rather than three images).  This amplification bias is associated
with high image multiplicities.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Use of the Hypercube for Symbolic Quantum 
Chromodynamics}
\par\noindent
{\bf A. Kolawa and G. C. Fox}
\par\noindent
$\rm C^3P-182c$\ \ \ \ \ \ \ (Short Code:  Kolawa:88a)
\par
A new numerical approach by Furmanski and Kolawa to quantum chromodynamics is 
based on diagonalizing the underlying Hamiltonian.  This method involves the 
generation of states by repeated action of a potential operator.  This 
symbolic calculation is dominated by the time it takes to search the database 
of existing states to verify if a generated state is identical to one 
previously found.  We implement this algorithm on the Caltech/JPL Mark~II 
hypercube and analyze its performance of both a simple database search and one 
optimized for this application.  We show that the hypercube performance can be 
modeled in a fashion similar to conventional numerical (loosely synchronous) 
applications.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf A Dynamic Load Balancer on the Intel 
Hypercube}
\par\noindent
{\bf Jeff Koller}
\par\noindent
$\rm C^3P-497$\ \ \ \ \ \ \ (Short Code:  Koller:88a)
\par
A class of commonly encountered problems requires dynamic load balancing for 
efficient use of concurrent processors.  We are developing a test bed for 
dynamic load balancing studies, and have chosen the MOOS operating system and 
the intel iPSC as our environment.  We discuss these choices, and how we are 
implementing a general purpose dynamic load balancer.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf The MOOS~II Manual}
\par\noindent
{\bf Jeff Koller}
\par\noindent
$\rm C^3P-662$\ \ \ \ \ \ \ (Short Code:  Koller:88b)
\par
MOOS~II is a new operating system for the Intel iPSC/1 hypercube,
featuring dynamic multitasking, interrupt driven communications, and
object oriented programming.  It includes support for dynamic load
balancing.  The original MOOS operating system, developed at Caltech by
John Salmon, et al, is available on the NCUBE and Caltech Mark~II
hypercubes and is referred to as MOOS~I, so that programs running under
the latter will in general need to be changed to run under MOOS~II.}
\par
This manual is intended to be a self-contained reference to MOOS~II, so
some of the material in reference [1] is repeated where necessary.
\par
MOOS~II has been developed on the iPSC to study dynamic load balancing
algorithms.  MOOS~I is unsuitable for this, because neither the
proprietary NCUBE processor nor the 806 on the Mark~II offer memory
management or operating system protection.  The 80286 on the iPSC is a
more advanced processor, with a wide range of useful features.  The most
significant change in MOOS~II has been to isolate the operating system
kernel from the user processes.  This results in a more robust system,
and easier debugging.  Details of the design of MOOS~II will be made
available later in a separate document.

\bigskip\starline\bigskip
\vbox{\par\noindent
{\bf Transparencies} from a talk by J. Koller, entitled ``Neural
Compiler Talk'', presented at California Institute of Technology, August
1988.  C$^3$P-663 (Short Code: Koller:88c)}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Physical Optimization and Dynamic
Load Balancing}
\par\noindent
{\bf J. G. Koller, G. C. Fox, and W. Furmanski}
\par\noindent
$\rm C^3P-670$\ \ \ \ \ \ \ (Short Code:  Koller:88d)
\par
The purpose of this paper is to report on a dynamic load balancer
currently running on an Intel hypercube.  We will also review the
optimization methods used by our system as these are not widely known.
These methods are based on analogies with physical systems, and include
simulated annealing, neural networks, and various related relaxation
approaches.  Over the last few years, our group at Caltech and others
have investigated a number of applications of such methods, and have
found that they provide a convenient, fast and powerful approach to many
difficult optimization problems encountered in distributed
architectures.  In this paper, we will outline these approaches and give
examples of their successes, in the hope that readers find them
applicable to other problems as well.}
\par
The specific optimization we discuss is load balancing on a medium grain
MIMD hypercube, first as a static problem, then as a dynamic one.  We
being by discussing the general ideas behind physical optimization, then
review some specific algorithms, and the relation between static and
dynamic problems.  In Section~7, we discuss MOOS, the hypercube
operating system we have written, and in Section~8 we explain the
dynamic load balancer.

\bigskip\starline\bigskip
\vbox{\par\noindent
{\bf Transparencies} from a talk given by A. Kuppermann, entitled
``Quantum Chemical Reaction Dynamics with Concurrent Processors'',
presented at the DOE Site Review, January 1988.  C$^3$P-551 (Short Code:
Kuppermann:88a)}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf NCUBE Simulation of Polymer Rings}
\par\noindent
{\bf James Kuyper, Jr.}
\par\noindent
$\rm C^3P-749$\ \ \ \ \ \ \ (Short Code:  Kuyper:88a)
\par
In this project, I investigated the properties of polyethylene rings
with the formula CnH2n.  Expectation values of various properties of the
molecules were calculated for a range of temperatures and ring sizes.
These values were calculated by using a Monte Carlo integration over the
allowed states, weighted by exp(-E/k*T).  The weighting was achieved by
using the Metropolis algorithm.  This involves establishing a starting
state, and then repeatedly randomly perturbing it.  As each
perturbation is generated, it is accepted if the change in E, dE, is
negative.  If dE is positive, the perturbation is still accepted with a
probability of exp(-dE/k*T).  In equilibrium, the density of states
produced by this method will be proportional to exp(-E/k*T).}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Concurrent Image Processing
Executive (CIPE)}
\par\noindent
{\bf Meemong Lee, Greg T. Cooper, Steven L. Groom, Alan S. Mazer, and
Winifred I. Williams}
\par\noindent
$\rm C^3P-669$\ \ \ \ \ \ \ (Short Code:  Lee:88a)
\par
This report describes the design and implementation of a Concurrent
Image Processing Executive (CIPE), which is intended to become the
support system software for a prototype high performance science
analysis workstation.  The target machine for this software is a
JPL/Caltech Mark~IIIfp Hypercube hosted by either a MASSCOMP~5600 or a
Sun-3, Sun-4 workstation; however, the design will accommodate other
concurrent machines of similar architecture, i.e., local memory,
multiple-instruction-multiple-data (MIMD) machines.  The CIPE system
provides both a multi-mode user interface and an applications programmer
interface, and has been designed around four loosely coupled modules:
(1) user interface; (2) host-resident executive; (3) hypercube-resident
executive; and (4) application functions.  The loose coupling between
modules allows modification of a particular module without significantly
affecting the other modules in the system.  In order to enhance
hypercube memory utilization and to allow expansion of image processing
capabilities, a specialized program management method, incremental
loading, was devised.  To minimize data transfer between host and
hypercube, a data management method which distributes, redistributes,
and tracks data set information was implemented.  The data management
also allows data sharing among application programs.  The CIPE software
architecture provides a flexible environment for scientific analysis of
complex remote sensing image data, such as imaging spectrometry,
utilizing state-of-the-art concurrent computation capabilities.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Three-Dimensional Interactions of
Vortex Tubes}
\par\noindent
{\bf A. Leonard and K. Chua}
\par\noindent
$\rm C^3P-691$\ \ \ \ \ \ \ (Short Code:  Leonard:88a)
\par
In this paper, we study vortex interactions in three-dimensional
incompressible flows.  In particular, we concentrate on strong
interactions of vortex tubes.  These tubes are initially vortex rings in
close proximity.  Several notable phenomena result from these
interactions: (1) complex motions of the space curves of the vortex
tubes, (2) development of internal structure (other than swirling flow)
such as axial flows and vortex breakdown, and (3) reconnection of vortex
lines.}
\par
We take the view that the dominant vortex structures in a turbulent flow
are these tube-like structures and that the above mentioned phenomena
are important ingredients in the fluid dynamics of turbulence.
Associated with these tubes, of course, is the unsteady, nearly
irrotational flow that surrounds them.  Here we have the possibility of
advection (most likely chaotic) of weak vorticity fields, i.e., passive
vector transport, by the dynamically significant vortex tubes.  We
suggest that this latter phenomenon will have little effect on the fluid
dynamics but would have a major impact on the transport of passive
scalars or vectors, e.g., heat transfer, chemical reactions, etc.
\par
We study these interactions by numerical simulation using a vortex
method.  In this method, elements of vector-valued vorticity are
convected with the local fluid velocity and the vorticity vector
associated with an element is continually strained by the local velocity
gradient. At each timestep the velocity field and its gradient are
computed from the Biot-Savart law.  Viscous effects are represented by
modifying the internal structure of each element.  This technique is
described in more detail in the next section and in section~III we
present the results of our numerical experiments.

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf A Universal Concurrent Algorithm for 
Plasma Particle-in-Cell Simulation Codes}
\par\noindent
{\bf Paulette C. Liewer, Viktor K. Becyk, John M. Dawson, and Geoffrey C. Fox}
\par\noindent
$\rm C^3P-562$\ \ \ \ \ \ \ (Short Code:  Liewer:88b)
\par
We have developed a new algorithm for implementation of plasma particle-in-
cell (PIC) simulation codes on concurrent processors.  This algorithm, termed 
the universal concurrent PIC algorithm (UC-PIC), has been utilized in a one-
dimensional electrostatic PIC code on the JPL Mark~III Hypercube parallel 
computer.  To decompose the problem using the UC-PIC algorithm, the physical 
domain of the simulation is divided into sub-domains, equal in number to the 
number of processors, such that all sub-domains have roughly equal numbers of 
particles.  For problems with non-uniform particle densities, these sub-
domains will be of unequal physical size.  Each processor is assigned a sub-
domain, with nearest neighbor sub-domains assigned to nearest neighbor 
processors.  Using this algorithm in the Mark~III PIC code, the increase in 
speed in going from 1 to 32 processors for the dominant portion of code (push 
time, defined below) was 29, yielding a parallel efficiency of 90\%.  Although 
implemented on a hypercube concurrent computer, this algorithm should also be 
efficient for PIC codes on other parallel architectures and on sequential 
computers where part of the data resides in external memory.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf A General Concurrent Algorithm for
Plasma Particle-in-Cell Simulation Codes}
\par\noindent
{\bf Paulett C. Liewer and Viktor K. Decyk}
\par\noindent
$\rm C^3P-649$\ \ \ \ \ \ \ (Short Code:  Liewer:88c)
\par
We have developed a new algorithm for implementing plasma
particle-in-cell (PIC) simulation codes on concurrent processors with
distributed memory.  This algorithm, named the general concurrent PIC
algorithm (GCPIC), has been used to implement an electrostatic PIC code
on the 32-node JPL Mark~III Hypercube parallel computer.  To decompose a
PIC code using the GCPIC algorithm, the physical domain of the particle
simulation is divided into sub-domains, equal in number to the number of
processors, such that all sub-domains have roughly equal numbers of
particles.  For problems with non-uniform particle densities, these
sub-domains will be of unequal physical size.  Each processor is
assigned a sub-domain and is responsible for updating the particles in
its sub-domain.  This algorithm has led to a very efficient parallel
implementation of a well-benchmarked one-dimensional PIC code.  The
dominant portion of the code, updating the particle positions and
velocities, is nearly 100\% efficient when the number of particles is
increased linearly with the number of hypercube processors used so that
the number of particles per processor is constant.  For example, the
increase in time spent updating particles in going from a problem with
11,264 particles run on one processor 360,448 particles on 32 processors
was only 3\% (parallel efficiency of 97\%).  Although implemented on a
hypercube concurrent computer, this algorithm should also be efficient
for PIC codes on other parallel architectures and for large PIC codes on
sequential computers where part of the data must reside on external
disks.}

\bigskip\starline\bigskip
\vbox{\par\noindent
{\bf Transparencies} from a talk by P. Liewer {\it et al.}, entitled
``Plasma Particle Simulations on the JPL Mark~III Hypercube'', presented
at the Third Conference on Hypercube Concurrent Computers and
Applications, January 1988.  C$^3$P-538 (Short Code: Liewer:88d)}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf A General Concurrent Algorithm for
Plasma Particle-in-Cell Simulation Codes}
\par\noindent
{\bf Paulett C. Liewer and Viktor K. Decyk}
\par\noindent
$\rm C^3P-649b$\ \ \ \ \ \ \ (Short Code:  Liewer:88e)
\par
We have developed a new algorithm for implementing plasma
particle-in-cell (PIC) simulation codes on concurrent processors with
distributed memory.  This algorithm, named the general concurrent PIC
algorithm (GCPIC), has been used to implement an electrostatic PIC code
on the 32-node JPL Mark~III Hypercube parallel computer.  To decompose a
PIC code using the GCPIC algorithm, the physical domain of the particle
simulation is divided into sub-domains, equal in number to the number of
processors, such that all sub-domains have roughly equal numbers of
particles.  For problems with non-uniform particle densities, these
sub-domains will be of unequal physical size.  Each processor is
assigned a sub-domain and is responsible for updating the particles in
its sub-domain.  This algorithm has led to a very efficient parallel
implementation of a well-benchmarked one-dimensional PIC code.  The
dominant portion of the code, updating the particle positions and
velocities, is nearly 100\% efficient when the number of particles is
increased linearly with the number of hypercube processors used so that
the number of particles per processor is constant.  For example, the
increase in time spent updating particles in going from a problem with
11,264 particles run on one processor 360,448 particles on 32 processors
was only 3\% (parallel efficiency of 97\%).  Although implemented on a
hypercube concurrent computer, this algorithm should also be efficient
for PIC codes on other parallel architectures and for large PIC codes on
sequential computers where part of the data must reside on external
disks.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Implementing Finite Element Software
on Hypercube Machines}
\par\noindent
{\bf Gregory A. Lyzenga. Arthur Raefsky, and Bahram Nour-Omid}
\par\noindent
$\rm C^3P-594$\ \ \ \ \ \ \ (Short Code:  Lyzenga:88a)
\par
The finite element method (FEM) has been historically and continues to
be an important computation-intensive application for the solution of a
wide range of numerical simulation problems in science and engineering.
The purpose of this paper is to describe recent research into the
adaptation of finite element programming techniques to coarse-grained
parallel computers, with emphasis on hypercubes and other similar
multicomputers.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Hypercube Multicomputers and Their
Use in Observational and Theoretical Astrophysics}
\par\noindent
{\bf David L. Meier}
\par\noindent
$\rm C^3P-252$\ \ \ \ \ \ \ (Short Code:  Meier:88a)
\par
The architecture, evolution, and use in astrophysics of hypercube
multicomputers is described.  Because of their potential for great speed
at reduced cost, and because they can be utilized with high efficiency,
multicomputers promise to be an important class of machines for
astrophysics as parallel processing becomes increasingly important in
the near future.}

\bigskip\starline\bigskip
\vbox{\par\noindent
{\bf Transparencies} from a talk by P. Messina, entitled ``Performance
Study of Missile Tracking Algorithm on Selected Computer
Architectures'', presented at the Project Review, September 1988.
C$^3$P-668 (Short Code: Messina:88a)}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Interactive Performance Display and 
Debugging using the NCUBE Real-Time Graphics System}
\par\noindent
{\bf Rodney Morison}
\par\noindent
$\rm C^3P-576$\ \ \ \ \ \ \ (Short Code:  Morison:88a)
\par
The NCUBE Real-Time Graphics System is an option for NCUBE/7 and NCUBE/10 
hypercube systems.  It is a parallel graphics interface that is able to 
display up to 30 frames per second of hypercube output.  Systems such as this 
are potentially well suited to real time display of output from parallel 
programs.  This paper discusses the issues of real time display for 
performance monitors on MIMD computers that have a high bandwidth graphics 
interface such as the one mentioned above.  Several monitors for an 
asynchronous parallel.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf The $\bf t$-Expansion at Low
Orders:  Ground State Energy Density Calculations in Lattice Systems}
\par\noindent
{\bf Pablo Moscato}
\par\noindent
$\rm C^3P-684$\ \ \ \ \ \ \ (Short Code:  Moscato:88a)
\par
The $t$-expansion, a nonperturbative, systematic and analytic method for
the calculation of ground-state expectation values of a Hamiltonian, is
applied in two lattice systems; the XY Model in $1+1$ dimensions and an
SU(2) lattice gauge theory in $3+1$ space-time dimensions.  The
procedure makes use of the expansion of the operator $e^{-tH}$ and
Pad\'e method are usually performed to extrapolate the resulting
$t$-series.  Previous work in the lattice shows that it needs
calculation of connected matrix elements of high-order powers of the
Hamiltonian.  In this paper, a new technique which was recently
introduced in Molecular Quantum Chemistry, is applied in these two
lattice models.  Ground-state energy densities calculated using the two
techniques in tandem show that high-order connected diagrams
calculations can be avoided thanks to the fast convergence achieved.}

\bigskip\starline\bigskip
\vbox{\par\noindent
{\bf Transparencies} from a talk by F. P\'epin {\it et al.}, entitled
``Vortex Dynamics on Concurrent Computers'', presented at the Third
Conference on Hypercube Concurrent Computers and Applications, January
1988.  C$^3$P-615 (Short Code: Pepin:88a)}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf A High-Speed Message-Driven
Communication Architecture}
\par\noindent
{\bf J. Peterson, E. Chow, H. Madan}
\par\noindent
$\rm C^3P-628$\ \ \ \ \ \ \ (Short Code:  Peterson:88a)
\par
The performance of a message-passing multiple instruction multiple data
(MIMD) concurrent computer depends in large part on the communication
processing overhead.  A high-speed communication architecture is
proposed for a hypercube-type supercomputer to attain the specific goals
of message-driven processing.  These goals include:  direct hardware
execution of messages, queueing of messages (using various paradigms),
adaptive message routing, and special local registers for fast context
switching.  A hyperswitch network capable of high-speed switching is
used to perform message routing.  Available communication paths are
pruned by the routing algorithm in response to congestion within the
network to evaluate the best-first available path between any two
nodes.  Simulation results show that this architecture reduces message
reception latency by two to three orders of magnitude when compared to
commercial hypercube systems.  This communication architecture extends
the application of parallel systems to supercomputer problems that place
heavy demand on the communication network for high bandwidth, low
latency, and non-local communication.  Detailed simulation studies for
the proposed communication architecture are presented.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Benchmarking and Optimization of
Scientific Codes on the CRAY~X-MP, CRAY~2, and SCS-40 Vector Computers}
{\bf Wayne Pfeiffer, Arnold Alagar, Anke Kamrath, Robert H. Leary, and
Jack Rogers}
\par\noindent
$\rm C^3P-699$\ \ \ \ \ \ \ (Short Code:  Pfeiffer:88a)
\par
Various scientific codes were benchmarked on three vector computers:
the CRAY~X-MP/48 and CRAY~2 supercomputers, and the SCS-40/XM
minisupercomputer.  On the X-MP, two FORTRAN compilers were also
compared.  The benchmarks, which were initially all in FORTRAN,
consisted of six research codes from Caltech, the 24 Livermore loops,
and two cases from the LINPACK benchmark.  As a corollary effort, the
effect of manual optimization on the Caltech codes was also considered,
including the selected use of assembly-language math routines.}
\par
On each machine the ratio of the maximum to the minimum speeds for the
various benchmarks was more than a factor of 50.  The maximum speed for
all-FORTRAN codes was more than 80\% of the peak speed on the X-MP, and
SCS, but less than 40\% of the peak speed on the CRAY~2.  Despite is
faster clock, the CRAY~2 generally ran slow than the X-MP, typically by
factors of 1.3 to 1.4, at least for the in-core benchmarks considered
here.  The poorer performance of the CRAY~2 was due to its lack of
chaining, its single port between each CPU and memory, and its
relatively slow memory.  The SCS-40 ran slower than the X-MP roughly in
proportion to the clock speed ratio, which is 4.7.  The inherently
better scalar performance of the SCS was offset by the poorer
performance of its compiler.
\par
On the X-MP, the new CFT77 2.0 compiler was found to produce
significantly faster code than CFT 1.14 typically by factors of 1.2 to
1.3.  This was obtained, however, at the expense of compilation times
that were four to five times longer.  Regardless of the compiler, manual
optimization was still found to be worthwhile.  For three of the Caltech
codes compiled with CFT77, run time speedups of from 2.4 to 15.7 were
achieved due to FORTRAN optimization only.

\bigskip\starline\bigskip
\vbox{\par\noindent
{\bf Transparencies} from a talk by T. Prince, entitled
``Computationally Intensive Data Analysis in Astronomy and
Astrophysics'', presented at the DOE Site Review, January 1988.
C$^3$P-619 (Short Code: Prince:88a)}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf A Mathematical Analysis of the Scattered 
Decomposition}
\par\noindent
{\bf John Salmon}
\par\noindent
$\rm C^3P-591$\ \ \ \ \ \ \ (Short Code:  Salmon:88b)
\par
A theoretical basis for the scattered decomposition is worked out in some 
detail.  The basic result has been part of the ``folklore'' for some time, but 
has never been proved.  The load imbalance expected from a scattered 
decomposition of a set of computational tasks is proportional $n^{-
1/2}\sigma_{task}\over m_{task}$, where $n$ is the number of tasks assigned to 
each processor, $m_{task}$ is the mean time per task and $\sigma_{task}$ is 
the root mean square deviation time per task.  The constant of proportionality 
is of O(1), and is very slowly increasing function of the number of 
processors.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Ray Tracing}
\par\noindent
{\bf John Salmon}
\par\noindent
$\rm C^3P-565$\ \ \ \ \ \ \ (Short Code:  Salmon:88c)
\par
We describe a fully functional hypercube ray tracer for rendering
computer graphics.  For small models, which fit in the memory of a
single processor, the ray tracer uses a scattered decomposition of
pixels to balance the load, and achieves a very high efficiency.  The
more interesting case of large models, which cannot be stored in a
single processor, requires a decomposition of the model data as well as
the pixels.  An estimate of the frequency with which data items will be
needed is used to construct this decomposition so as to minimize
communication and achieve load balance.  The resulting ray tracer uses
the full memory and processing power of the hypercube to render
extremely high quality ray-traced images.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf MOOSE:  A Multi-Tasking Operating
System for Hypercubes}
\par\noindent
{\bf J. Salmon, J. Flower, A. Kolawa, and S. Callahan}
\par\noindent
$\rm C^3P-603$\ \ \ \ \ \ \ (Short Code:  Salmon:88d)
\par
MOOSE is a complete multi-tasking operating system running on Caltech
Mark~II and NCUBE hypercubes.  It consists of three main sub-systems:
\item{1.}A task management system,
\item{2.}A communication system, and
\item{3.}A process synchronization system.}
\par
The multi-tasking features of MOOSE are useful for addressing highly
asynchronous or unpredictable problems which cannot be adequately
decomposed statically.  MOOSE has been employed in a ray tracer with a
distributed database.

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Waveform Relaxation for Concurrent 
Dynamic Simulation of Distillation Columns}
\par\noindent
{\bf Anthony Skjellum and Sven Mattisson}
\par\noindent
$\rm C^3P-588$\ \ \ \ \ \ \ (Short Code:  Skjellum:88a)
\par
The need for cost-effective, high-speed computing is essential in many aspects 
of chemical engineering practice, notably for the simulation of large-scale 
dynamic systems.  The arrival of powerful, highly concurrent message-passing 
multicomputers potentially offers such economical large-scale computing 
capability.  Development of appropriate, efficient algorithms which realize 
this potential must therefore become an important area of ongoing research and 
development in chemical engineering.  Desired {\it orders-of-magnitude\/} 
speed-up strongly motivates the use of novel algorithmic approaches for large-
scale simulation.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Highly Concurrent Dynamic Simulation
in Chemical Engineering:  {\it Issues, Methodologies, Model Problems,
Progress}}
\par\noindent
{\bf Anthony Skjellum, Manfred Morari, Sven Mattisson, and Lena Peterson}
\par\noindent
$\rm C^3P-692$\ \ \ \ \ \ \ (Short Code:  Skjellum:88b)
\par
We discuss large-scale concurrent simulation on multicomputers (binary
N-cubes or ``hypercubes'', and 2D meshes).  We describe hardware
characteristics (scalability, granularity, communication, performance
potential), and software attributes (programming model, communication
primitives), while indicating the driving issues of concurrent computing
(speedup, Amdahl's law, load balancing), and describing the challenges
of concurrent dynamic simulation.}
\par
We cover the solution of ordinary initial-value problems in terms of
building-block operations including model evaluation (residual
calculation), Jacobian (iteration matrix) computation, integration
overheads, LU-decomposition and equation forward- and back-solving.  We
discuss the importance of the relative costs of these operations to the
overall performance of the concurrent algorithms.  Our simulation code
{\it Concurrent DASSL\/} implements these numerical procedures following
the lead of the {\it DASSL\/} code, a recognized sequential single-rate
integration package.
\par
A number of interesting chemical engineering simulations will be
solvable within the {\it Concurrent DASSL\/} framework.  At this time,
we quote specific features of dynamic distillation simulation to
motivate anticipated performance on second-generation multicomputer
systems.

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Waveform Relaxation for Concurrent
Dynamic Simulation of Distillation Columns}
\par\noindent
{\bf Anthony Skjellum, Manfred Morari, and Sven Mattisson}
\par\noindent
$\rm C^3P-539$\ \ \ \ \ \ \ (Short Code:  Skjellum:88c)
\par
The distillation column and its variants are arguably the most important
class of unit operations in chemical plants.  Dynamic models consist of
differential-algebraic systems with stiff, nonlinear ordinary
differential equations modeling fluid flow, mass and energy balances,
and nonlinear algebraic equations modeling the vapor-liquid
equilibrium.  A multicomponent system with a practical number of columns
can have on the order of one thousand equations or more.  Furthermore,
physical property calculations for vapor-liquid equilibrium can be
outstandingly arduous.  Hence, the dynamic simulation of distillation
columns continues to receive serious attention because detailed models
often have huge computing requirements.  It is therefore natural to seek
concurrent algorithms suitable for large-scale concurrent computers in
order to obtain significant simulation speedup.}
\par
In this research effort, we are taking the first steps toward reaching
this goal.  We consider a highly simplified binary distillation model
with simple vapor-liquid equilibrium.  A set of stiff, coupled nonlinear
ordinary differential equations result.  Importantly, these
simplifications still allow us to capture three central issues:
stiffness, large problem size, and computational difficulties arising
from systems which incorporate coupled columns.  Waveform relaxation was
chosen as the solution approach because it offers large speedup
potential.  For example, temporal latency of subsystems can be
exploited, implying reduced computational effort for such subsystems
and, correspondingly, the opportunity for greater overall speedup in the
total simulation.
\par
Because of the success of the Mattisson's {\it CONCISE\/} simulator for
VLSI circuit simulation via waveform relaxation, we have formulated the
distillation model within this program.  We represent the current status
of the project in this poster session; the software is being implemented
on a hypercube computer system supporting asynchronous message-passing
and should be readily portable to other operating environments offering
similar communication primitives.  We indicate how the use of more
demanding distillation models (including, for example, complex
vapor-liquid equilibrium) is likely to change concurrent efficiency.
Furthermore, we note that redundant programming effort is avoided by
extension of extant, mature concurrent software.  Future directions of
this research and related plans are also mentioned.

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Application of Multicomputers to
Large-Scale Dynamic Simulation in Chemical and Electrical Engineering:
{\it Unifying Themes, Software Tools, Progress}}
\par\noindent
{\bf Anthony Skjellum, Lena Peterson, Sven Mattisson, and Manfred Morari}
\par\noindent
$\rm C^3P-750$\ \ \ \ \ \ \ (Short Code:  Skjellum:88d)
\par
We discuss large-scale concurrent simulation on multicomputers (binary
N-cubes or ``hypercubes'', and 2D meshes).  We describe hardware
characteristics (scalability, granularity, communication, performance
potential), and software attributes (programming model, communication
primitives), while indicating the driving issues of concurrent computing
(speedup, Amdahl's law, load balancing), and describing the challenges
of concurrent dynamic simulation.}
\par
We cover the solution of initial-value problems in terms of
building-block operations including model evaluation, Jacobian
computation, integration overheads, LU-decomposition and equation
forward- and back-solving.  We discuss the importance of the relative
costs of these operations to the overall performance of the concurrent
algorithms.  In this light, we indicate the potentially higher
performance of waveform relaxation, a novel numerical technique.
\par
Subsequently, we describe our concurrent simulation programs: {\it
Concurrent DASSL\/} and {\it CONCISE}, designed to support sequential an
novel numerical integration techniques, respectively.  We support
single-rate integration (BDF-based) and waveform relaxation
(Picard-Lindel\"of iterations).
\par
Our application areas are chemical and electrical engineering from which
we draw distillation simulation and VLSI-circuit simulation,
respectively.  Preliminary speedup results are quoted for circuit
simulation; we describe additional planned work in our joint efforts.

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Mark~IIIfp Hypercube Concurrent Processor 
Architecture}
\par\noindent
{\bf J. Tuazon, J. Peterson, and M. Pniel}
\par\noindent
$\rm C^3P-602$\ \ \ \ \ \ \ (Short Code:  Tuazon:88a)
\par
The Mark~IIIfp Hypercube is a new generation of hypercube concurrent processor 
system developed at JPL/Caltech, with peak performance of 5~Mips, 14~Mflops 
per node, and a peak communication rate of 6~Mbytes per second.  Each node 
utilizes two Motorola MC68020 microprocessors, an MC68882 scalar floating- 
point coprocessor, and a Weitek 8000 floating-point chip set.  One of the 
MC68020 processors serves as the application and computational processor, the 
other is dedicated to communication.  The three processors are interconnected 
through a common system bus and share 4~Mbytes of dynamic memory.  Each 
processor has his own fast local memory, which increases parallelism, 
minimizes shared memory referencing, reduces memory contentions and improves 
system performance.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf A Concurrent Direct Solver for
Sparse Unstructured Systems}
\par\noindent
{\bf Eric F. Van de Velde}
\par\noindent
$\rm C^3P-604$\ \ \ \ \ \ \ (Short Code:  Velde:88a)
\par
The direct solution by Gaussian elimination of large sparse unstructured
systems must achieve two goals:  first, solve the system in a
numerically stable fashion, and second, minimize the fill generated
during LU-decomposition.  In a concurrent environment, it is also
necessary to balance the load of the computations.  To achieve these
three goals simultaneously, it is necessary to find a successful
combination of pivoting strategy and data distribution.  The best
combination is usually application dependent.  We used a formal program
development technique to develop concurrent LU-decomposition and
triangular solve algorithms, whose correctness is independent of
specific pivoting strategies or data distributions.  The resulting
algorithms form a general purpose framework for the development of
specific, application dependent sparse solvers.  We discuss several
pivoting strategies of practical and theoretical interest that can be
incorporated in the solver, as well as specific data distributions and a
general purpose sparse matrix data structure.}

\bigskip\starline\bigskip
\vbox{\par\noindent
{\bf Transparencies} from a talk by E. Van de Velde, entitled ``Applied
Mathematics and Concurrent Computing'', presented at the DOE Site
Review, January 1988.  C$^3$P-620 (Short Code: Velde:88b)}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf The Formal Correctness of an
LU-Decomposition Algorithm}
\par\noindent
{\bf Eric F. Van de Velde}
\par\noindent
$\rm C^3P-625$\ \ \ \ \ \ \ (Short Code:  Velde:88c)
\par
We give a formal correctness proof of an LU-decomposition algorithm for
multicomputers.  The correctness of an initial specification is proven
by reformulating well known numerical analysis theorems about Gaussian
Elimination as a program correctness argument.  Subsequently, the
program is gradually transformed into a form suitable for multicomputer
implementation.  Each of the elementary program transformations is shown
to preserve correctness.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Data Redistribution and Concurrency}
\par\noindent
{\bf Eric F. Van de Velde}
\par\noindent
$\rm C^3P-635$\ \ \ \ \ \ \ (Short Code:  Velde:88d)
\par
The role of data distribution in concurrent computations is twofold:
achieving load balanced computations and minimizing the number of
synchronization points and/or message exchanges.  It is clear that the
optimal data distribution is dependent on the particular algorithm.
However, when faced with typical application programs several algorithms
involving varying types of computation may have to be performed on the
same data at different stages of the computation.  In between these
stages, a redistribution of the data may be necessary.  Memory is often
a constraining factor in highly concurrent machines and there is
usually great advantage if the data redistribution can be done in
place.  In this paper, we propose a general in place concurrent data
redistribution algorithm and we identify the data distributions that can
be mapped into one another by the proposed technique.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Performance Evaluation of Scientific
Programs on Advanced Architecture Computers}
\par\noindent
{\bf David W. Walker, Paul Messina, and Clive F. Baillie}
\par\noindent
$\rm C^3P-580$\ \ \ \ \ \ \ (Short Code:  Walker:88a)
\par
Recently, a number of advanced architecture machines have become
commercially available.  These new machines promise better
cost-performance then traditional computers, and some of them have the
potential of competing with current supercomputers, such as the
CRAY~X-MP, in terms of maximum performance.  This paper describes an
on-going project to evaluate a broad range of advanced architecture
computers using a number of complete scientific application programs.
The computers to be evaluated include (1) distributed-memory machines
such as the NCUBE, Intel and Caltech/JPL hypercubes, and the Meiko
computing surface, (2) shared-memory, bus architecture machines such as
the Sequent Balance and the Alliant, (3) very long instruction word
machines such as the Multiflow Trace~7/200 computer, (4) ``traditional''
supercomputers such as the CRAY~X-MP and CRAY~2, and (5) SIMD machines
such as the Connection Machine.  Currently, 11 application codes from a
number of scientific disciplines have been selected, although it is not
intended to run all codes on all machines.  Results are presented for
two of the codes (QCD and missile tracking), and future work is
proposed.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf The Flux-Corrected Transport Algorithm on 
the NCUBE Hypercube}
\par\noindent
{\bf David W. Walker and Geoffrey C. Fox}
\par\noindent
$\rm C^3P-495$\ \ \ \ \ \ \ (Short Code:  Walker:88b)
\par
This work describes the implementation of a finite-difference algorithm, 
incorporating the flux-corrected transport technique, on the NCUBE hypercube.  
The algorithm is used to study two-dimensional, convectively-dominated fluid 
flows, and as a sample problem the onset and growth of the Kelvin-Helmholtz 
instability is investigated.  Timing results are presented for a number of 
different sized problems on hypercubes of dimension up to nine.  These results 
are interpreted by means of a simple performance model.  The extension of the 
algorithm to the three-dimensional case is also discussed.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Performance of a QCD Code on the NCUBE 
Hypercube}
\par\noindent
{\bf David W. Walker}
\par\noindent
$\rm C^3P-490b$\ \ \ \ \ \ (Short Code:  Walker:88c)
\par
The performance of a pure gauge QCD code on the NCUBE hypercube is analyzed.  
Both load imbalance and communication contribute to the concurrent overhead, 
with the load imbalance term becoming dominant for sufficiently large 
hypercubes.  The performance model is compared with timings measured on the 
NCUBE using both the standard and fast versions of the CrOS~III communication 
systems.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Portable Programming within a 
Message-Passing Model: the FFT as an Example}
\par\noindent
{\bf David W. Walker}
\par\noindent
$\rm C^3P-631$\ \ \ \ \ \ \ (Short Code:  Walker:88d)
\par
This paper describes a portable programming environment for MIMD concurrent 
processors based on an object-oriented, message-passing paradigm.  The basis 
of this environment is the Virtual Machine Loosely Synchronous Communication 
System (VMLSCS) which is designed to be used for loosely synchronous problems.  
VMLSCS is structured to make efficient use of hierarchical memory, and permits 
communication and calculation to be overlapped on certain concurrent 
processors.  As an example, the use of VMLSCS in performing both one-
dimensional and multi-dimensional fast Fourier transforms (FFTs) on concurrent 
multiprocessors is described.  It is shown that all necessary interprocessor 
communication can be performed by a single routine, {\it vm\_index}.  Thus the 
construction of a portable concurrent FFT rests on the implementation of {\it 
vm\_index\/} on the target machines.  In the multi-dimensional algorithm a 
strip decomposition is applied to each of the directions in turn so that each 
of the FFTs performed in a particular direction are done in one processor.  
This allows fast sequential one-dimensional FFTs to be exploited.  The 
implementation of {\it vm\_index\/} on both homogeneous and inhomogeneous 
hypercubes, and shared memory multi-processors is discussed.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf A Portable Programming Environment
for Multiprocessors}
\par\noindent
{\bf David W. Walker and Geoffrey C. Fox}
\par\noindent
$\rm C^3P-496$\ \ \ \ \ \ \ (Short Code:  Walker:88e)
\par
This paper discusses the issues involved in designing a portable
programming environment for large grain-size MIMD concurrent
processors.  In addition, a detailed description of such an environment
is given, and its implementation on the distributed memory Mark~IIIfp
hypercube and the shared memory ETA$^{10}$ is outlined.}

\bigskip\starline\bigskip
\vbox{\par\noindent
{\bf Transparencies} from a talk by D. Walker {\it et al.}, entitled
``Concurrent Computers in Science'', presented at the Conference on
Computer in Physics Instruction, August 1988.  C$^3$P-651 (Short Code:
Walker:88f)}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Performance Evaluation of Scientific 
Programs on Advanced Architecture Computers}
\par\noindent
{\bf D. W. Walker, Paul Messina, and Clive F. Baillie}
\par\noindent
$\rm C^3P-511$\ \ \ \ \ \ \ (Short Code:  Walker:88g)
\par
Recently a number of advanced architecture machines have become commercially 
available.  These new machines promise better cost-performance then 
traditional computers, and some of them have the potential of competing with 
current supercomputers, such as the CRAY~X-MP, in terms of maximum 
performance.  This paper describes an on-going project to evaluate a broad 
range of advanced architecture computers using a number of complete scientific 
application programs.  The computers to be evaluated include (1) distributed-
memory machines such as the NCUBE, INTEL and Caltech/JPL hypercubes, and the 
MEIKO computing surface, (2) shared-memory, bus architecture machines such as 
the Sequent Balance and the Alliant, (3) very long instruction word machines 
such as the Multiflow Trace 7/200 computer, (4) ``traditional'' supercomputers 
such as the CRAY~X-MP and CRAY~2, and (5) SIMD machines such as the Connection 
Machine.  Currently 11 application codes from a number of scientific 
disciplines have been selected, although it is not intended to run all codes 
on all machines.  Results are presented for two of the codes (QCD and missile 
tracking), and future work is proposed.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Graphics Techniques in Concurrent 
Simulation}
\par\noindent
{\bf Van Warren}
\par\noindent
$\rm C^3P-600$\ \ \ \ \ \ \ (Short Code:  Warren:88a)
\par
This paper discusses work occurring in the hypercube simulation laboratory and 
visualization schemes for concurrent simulation.  The principle contribution 
of this work is that of a cost effective technical approach to simulation 
visualization.  This approach is being replicated and applied to contemporary 
large scale simulation problems of interest around the country.}
\par
Since the hypercube graphics interface is a working prototype, there is a mix 
of practice and experience along with novel approaches to contemporary 
graphics problems.  A discussion of techniques which accelerated graphics 
development is included.  Among these are issues of interpreted vs. compiled 
tools for simulation visualization and supercomputer-display interface 
methodology.  A survey of other significant efforts in combining hypercubes 
and graphics is provided.  Finally, the issue of interactive simulation 
exploration via real time displays is discussed with an eye toward the future.

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf An $O(N\log N)$ Hypercube N-body 
Integrator}
\par\noindent
{\bf Mike Warren and John Salmon}
\par\noindent
$\rm C^3P-593$\ \ \ \ \ \ \ (Short Code:  Warren:88b)
\par
The gravitational N-body algorithm of Barnes and Hut has been successfully 
implemented on a hypercube concurrent processor.  The novel approach of their 
sequential algorithm has demonstrated itself to be well suited to hypercube 
architectures.  The sequential code achieves $O(N\log N)$ speed by recursively 
dividing space into subcells, thereby creating a hierarchical grouping of 
particles.  Computing interactions between these groups dramatically reduces 
the amount of communication between processors, as well as the number of force 
calculations.  Parallelism is achieved through an irregular spatial grid 
decomposition.  Since the decomposition topology is not simple, a general 
loosely synchronous communication routine has been developed.  Operations are 
simplified if the conventional grey code decomposition is modified so that the 
bits are taken alternately from each cartesian dimension.  A speed-up of 180 
has been achieved for a 500,000 particle two-dimensional calculation on 256 
processors.  A speed-up of 65 has been obtained for a 64,000 particle three-
dimensional calculation on 256 processors.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf An $\bf O(N\log N)$ Hypercube N-body
Integrator}
\par\noindent
{\bf Michael Warren}
\par\noindent
$\rm C^3P-639$\ \ \ \ \ \ \ (Short Code:  Warren:88c)
\par
The gravitational N-body algorithm of Barnes and Hut has been
successfully implemented on a hypercube concurrent processor.  The novel
approach of their sequential algorithm has demonstrated itself to be
well suited to hypercube architectures.  The sequential code achieves
$O(N\log N)$ speed by recursively dividing space into subcells, thereby
creating a hierarchical grouping of particles.  Computing interactions
between these groups dramatically reduces the amount of communication
between processors, as well as the number of force calculations.
Parallelism is achieved through a spatial grid decomposition.  Since the
decomposition topology is not simple, a general loosely synchronous
communication routine has been developed which has several advantages
over traditional methods.  A speedup of 180 has been achieved for a
500,000 particle two-dimensional calculation on 256 processors.  A
three-dimensional simulation investigating galactic halo formation with
over $10^5$ particles has been successfully completed.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Dynamical Simulations of Granular 
Materials using the Caltech Hypercube}
\par\noindent
{\bf B. T. Werner and P. K. Haff}
\par\noindent
$\rm C^3P-612$\ \ \ \ \ \ \ (Short Code:  Werner:88a)
\par
A technique for simulating the motion of granular materials using the Caltech 
Hypercube is described.  We demonstrate that grain dynamics simulations run 
efficiently on the Hypercube and therefore that they offer an opportunity for 
greatly expanding the use of parallel simulations in studying granular 
materials.  Several examples, which illustrate how the simulations can be used 
to extract information concerning the behavior of granular materials, are 
discussed.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Implementing a Distributed Combat 
Simulation on the Time Warp Operating System}
\par\noindent
{\bf Frederick Wieland, Lawrence Hawley, and Abe Feinberg}
\par\noindent
$\rm C^3P-601$\ \ \ \ \ \ \ (Short Code:  Wieland:88a)
\par
Utilizing the Time Warp Operating System, the CTLS project at JPL has 
produced a distributed combat simulation called STB-87 and measured its 
performance on the JPL Mark~III Hypercube.  By applying the spiral model of 
software development, the CTLS project will produce a series of software test 
beds, to culminate in the completion of a working prototype theater level 
simulation three to five years hence.  STB-87, the first software test bed, is 
a ground-based combat simulation decomposed into objects which communicate via 
time-stamped messages.  The use of incremental object-based design, coding, 
and testing has been helpful when developing a parallel simulation.  The 
performance measurements show that, with the appropriate choice of object 
granularity, STB-87 is able to achieve a speed-up factor of 12 running on a 
32-node Mark~III Hypercube.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf DIME: A Programming Environment for 
Unstructured Triangular Meshes on a Distributed-Memory Parallel Processor}
\par\noindent
{\bf Roy D. Williams}
\par\noindent
$\rm C^3P-502$\ \ \ \ \ \ \ (Short Code:  Williams:88a)
\par
DIME (Distributed Irregular Mesh Environment) is a user environment written in 
C for manipulation of an unstructured triangular mesh in two dimensions.  The 
mesh is distributed among the separate memories of the processors, and 
communication between processors is handled by DIME; thus the user writes C-
code referring to the elements and nodes of the mesh and need not be unduly 
concerned with the parallelism.  A tool is provided for the user to make an 
initial coarse triangulation of a region, which may then be adaptively refined 
and load-balanced.  DIME provides many graphics facilities for examining the 
mesh, including contouring and a Postscript hard-copy interface.  DIME also 
runs on sequential machines.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf The $\rm C^3P$ Video Equipment:  A
Progress Report}
\par\noindent
{\bf Roy Williams}
\par\noindent
$\rm C^3P-532$\ \ \ \ \ \ \ (Short Code:  Williams:88b)
\par
The $\rm C^3P$ group has recently acquired the basic hardware for making
computer generated video movies.  This report describes the hardware,
how to use it, some of the software available, and how to use the
equipment from a remote mainframe.  At present the mainframe can only be
the Sun-server wega or its clients.  In the near future the NCUBE's may
serve as the mainframe.}

\bigskip\starline\bigskip
\vbox{\par\noindent
{\bf Transparencies} from a talk by R. Williams, entitled ``Distributed
Irregular Mesh Environment'', presented at the Third Conference on
Hypercube Concurrent Computers and Applications, January 1988.
C$^3$P-549 (Short Code: Williams:88c)}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Free-Lagrange Hydrodynamics with a
Distributed-Memory Parallel Processor}
\par\noindent
{\bf Roy Williams}
\par\noindent
$\rm C^3P-424b$\ \ \ \ \ \ \ (Short Code:  Williams:88d)
\par
The PIFL (Parallel Irregular Free-Lagrange) code solves two-dimensional
hydrodynamics with the mesh vertices moving with the fluid, with no
rezoning.  The irregular mesh is made of triangles and each processor
deals with one or more connected domains of fluid.  After each time step
the mesh is topologically restructured, mesh points may be created or
destroyed, and there is a local load-balance.  Every few steps there is
a global load balance.  The code runs on a hypercube under Cubix and is
designed to run most efficiently in the limit of a large number of
large-memory processors.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Supersonic Fluid Flow in Parallel
with an Unstructured Mesh}
\par\noindent
{\bf Roy D. Williams}
\par\noindent
$\rm C^3P-636$\ \ \ \ \ \ \ (Short Code:  Williams:88e)
\par
I have implemented an algorithm for time-accurate solutions of the
two-dimensional compressible Euler equations using an irregular
triangular mesh.  The code runs on distributed or shared memory or
sequential machines, and is written using the Distributed Irregular Mesh
Environment (DIME).  DIME is a programming environment for calculations
with such meshes, with adaptive mesh refinement and dynamic load
balancing.  Results are presented for an example of a Mach~3 flow over a
step, computed with a 32-processor NCUBE hypercube.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Concurrent I/O System for the Hypercube 
Multiprocessor}
\par\noindent
{\bf Andrew Witkowski, Kumar Chandrakumar, and Greg Macchio}
\par\noindent
$\rm C3P-611$\ \ \ \ \ \ \ (Short Code:  Witkowski:88a)
\par
This paper describes the Concurrent I/O (CIO) system for the Hypercube 
Multiprocessor.  Our system has three components: Architecture, User 
Interface, and Programming Paradigm.  The architecture of the system is based 
on clusters.  Each cluster has a hypercube topology and contains either 
computing nodes or I/O nodes.  This architecture scales well, provides a 
convenient naming convention and offers independent connectivity between the 
I/O nodes.  The routing algorithm confines the I/O traffic within the I/O 
clusters.  Clusters can be connected in a variety of ways suitable for such 
diverse applications as graphics and database systems.  The system provides a 
programming paradigm where several nodes of a multiprocessor can cooperate on 
creating a file.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf A Programming Model for the Mark~III
Hypercube with Multiple Processor Nodes}
\par\noindent
{\bf Barbara A. Zimmerman and Gerald A. Crichton}
\par\noindent
$\rm C^3P-597$\ \ \ \ \ \ \ (Short Code:  Zimmerman:88a)
\par
The Caltech/JPL Mark~III Hypercube originally consisted of an ensemble
of processing elements each containing two Motorola M68020 processors
--- one M68020 processor and a M68881 Floating-Point coprocessor used
for data processing, the other M68020 processor dedicated to hypercube
communications.  In the interest of achieving even greater computational
capability a third processing element, the Weitek~XL system, was added
to enhance floating point performance.  Each of what is now three
processing elements is configured with cpu, local statis memory,
communication peripherals, clocks, and control logic.  In addition, they
share four megabytes of dynamic memory on the node card.  We will
describe a programming model and environment that accommodates the
operation of the three processors, preparation, extended Crystalline
communications, and intranode concurrency.}

\vfill\eject
\bye
