\input /home/swan/joann/macros/setup
\baselineskip=14pt
\vsize=9.25truein
\hsize=6.5truein
\hoffset=-.2truecm
\tolerance=10000
\def\starline{\hbox to \hsize{* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *}}
\centerline{\fourteenpoint\bf California Institute of Technology}
\smallskip
\centerline{\fourteenpoint\bf C$^3$P Reports}
\smallskip
\centerline{\fourteenpoint\bf January 1 -- December 31, 1989}
\bigskip
\bigskip
\vbox{\par\noindent
{\twelvepoint\bf X-SAR digital processor:  Computational load for real-time}
\par\noindent
{\bf G. Aloisio, N. Veneziani, G. C. Fox and G. Milillo}
\par\noindent
C$^3$P-740\ \ \ \ \ \ \ (Short Code: Aloisio:89a)
\par
Referring to specific signal processing techniques to optimize the
computation of the fast convolution, the computational load and the
data transfer profiles, for the real-time focusing of X-SAR (Synthetic
Aperture Radar) raw data are evaluated.}
\par
Due to the variety of the possible configurations for the X-SAR sensor,
our numerical evaluations have been made first for a specific, operative
mode, constituted by:  platform altitude of 255 Km, off-nadir angle of
45$^\circ$, PRF of 1860 Hz and coarse resolution.  In this case we
deduced, as optimal, a data set decomposition into two balanced subswaths,
which would be distributed to two concurrent processing chains, each with
a parallel-pipeline structure.  The processing peaks obtained correspond
to about 187 MFlops to have a real-time compression of a single subswath's
range line and to about 170 MFlops for the compression of an azimuth line,
the interpolation and the final detection of the SAR image.  The global
system data rate instead is estimated as 7.1 Mbytes/sec in input and as
5.48 Mbytes/sec in output; peaks of even 22 bytes/sec have been found inside
the subswath processor, depending on the complex data format used during the
whole processing, with a 32-bit dynamic for each channel (I and Q).
\par
These results are very useful and give an important indication of how the
mission parameters influence the profiles evaluated for the computational
load and the data transfer rate.

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf A method to reduce the inter-node
communications for a concurrent implementation of the Prime Factor Algorithm}
\par\noindent
{\bf G. Aloisio, E. Lopinto and G. Fox}
\par\noindent
C$^3$P-773\ \ \ \ \ \ \ (Short Code: Aloisio:89b)
\par
The Prime Factor Algorithm (PFA) allows to efficiently compute the 1-D
Discrete Fourier Transform (DFT) by means of a multidimensional mapping,
which turns the 1-D DFT into shorter transforms of mutually prime lengths.}
\par
Different approach for a concurrent implementation of PFA can be adopted,
depending on the number of the processing elements (PE) involved in the
computation.
\par
In our previous approach, the decomposition technique was optimized to
exploit the maximum number of available PEs, in a large Hypercube
architecture.  Since the DFTs of the same order were distributed to PEs
and processed in parallel, an heavy data communication among the nodes
was required to properly compute the successive DFTs.
\par
In this paper, we present a new approach allowing to use a number of PEs
less or equal to the maximum prime factor of the multidimensional mapping.
By a proper data distribution, each node performs a large amount of its
computation on local data set, with a drastic reduction in the extra
communications.  The efficiency improvement with respect to the previous
approach has a mean value of about 75\%.

\bigskip\starline\bigskip
\vbox{\par\noindent
{\bf Transparencies} from a talk by G. Aloisio {\it et al.}, entitled ``A 
Method to Reduce the Inter-node Communications for a Concurrent 
Implementation of the Prime Factor Algorithm'', presented at the Fourth 
Conference on Hypercubes, Concurrent Computers and Applications, Santa Clara, 
March 1989.  C$^3$P-751 (Short Code: Aloisio:89c)}

\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:89a)
\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 seminar by C. Baillie, entitled ``Lattice gauge
theory and QCD:  An overview of algorithms'', presented at Caltech, January
1989.  C$^3$P-707 (Short Code: Baillie:89a)}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Parallel computing comes of
age:  Supercomputer calculations for lattice QCD and spin models
on advanced architecture computers}
\par\noindent
{\bf C. F. Baillie and G. C. Fox}
\par\noindent
C$^3$P-711\ \ \ \ \ \ \ (Short Code: Baillie:89b)
\par
Lattice QCD (Quantum Chromo-dynamics) is one of the most computationally
intensive large scale scientific computations.  It has been the main
driving force behind the development of several highly parallel advanced
architecture computers, and it has consumed a substantial amount of CPU
time on most high performance computers world-wide.}
\par
Herein we explain the computations required for lattice QCD, both in the
quenched theory and in the fully interacting theory with dynamical fermions
(using both Wilson and staggered fermion formulations); and for lattice
spin models, both discrete and continuous.  We include the current
state-of-the-art lattice gauge theory algorithms.
\par
We are running lattice gauge theories on the Caltech/JPL Mark IIIfp, the
NCUBE and the FPS T-series hypercubes, as well as on the AMT DAP 510 and
the TMC Connection Machine 2 SIMD computers, and traditional vector
supercomputers like the CRAY X-MP.  Hence we can contrast the implementation
of lattice QCD and spin models on all these computers, comparing the
vectorization and parallelization techniques used.  Moreover, we describe
the relative performances obtained.

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Lattice spin models and new algorithms}
\par\noindent
{\bf C. F. Baillie}
\par\noindent
C$^3$P-777\ \ \ \ \ \ \ (Short Code: Baillie:89c)
\par
We review computer simulations of spin models -- both discrete and
continuous -- and explain in detail the new algorithms which ameliorate
the problem of critical slowing down in these simulations.}

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

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf QCD with dynamical fermions on the Connection
Machine}
\par\noindent
{\bf C. F. Baillie, R. G. Brickner, R. Gupta and L. Johnsson}
\par\noindent
C$^3$P-786\ \ \ \ \ \ \ (Short Code: Baillie:89e)
\par
We have implemented Quantum Chromo-dynamics (QCD) on the massively-parallel
Connection Machine, in $^\ast$Lisp.  The code uses dynamical Wilson fermions
and the Hybrid Monte Carlo algorithm to update the lattice.  We describe our
program and give performance measurements for it.  With no tuning or
optimization, the code runs at approximately 1000 Mflops on a 64K CM-2.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Computational Status and Prospects of Lattice
Calculations in High Energy Physics}
\par\noindent
{\bf C. F. Baillie, D. A. Johnston and G. W. Kilcup}
\par\noindent
C$^3$P-792\ \ \ \ \ \ \ (Short Code: Baillie:89f)
\par
We review the status of lattice computer calculations in high energy physics, that
is, for the theories of Quantum Chromo-dynamics (QCD) and Strings.  After outlining
Monte Carlo Field Theory we explain in detail both QCD and Strings -- describing how
these theories are discretized on a lattice, what one can calculate and how much
computer time is required. We include a summary of the concurrent QCD machines which
have been, and are being, built.  We speculate on the prospects for such work.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Status and Prospects of the Computational
Approach to High Energy Physics}
\par\noindent
{\bf C. F. Baillie, D. A. Johnston and G. W. Kilcup}
\par\noindent
C$^3$P-800\ \ \ \ \ \ \ (Short Code: Baillie:89g)
\par
We review the status of lattice computer calculations in Quantum Chromo-dynamics
(QCD) and mention a new field of computational in high energy physics -- that of
Strings or random surfaces.  After outlining Monte Carlo Field Theory we explain
in detail both QCD and Strings -- describing how these theories are discretized
on a lattice, what one can calculate and how much computer time is required. We
include a summary of the concurrent QCD machines which have been, and are being,
built. We speculate on the prospects for such work - including a prediction for
when QCD will be ``solved''!}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Crumpling in dynamical triangulated
random surfaces with extrinsic curvature}
\par\noindent
{\bf C. F. Baillie, D. A. Johnston, and R. D. Williams}
\par\noindent
C$^3$P-807\ \ \ \ \ \ \ (Short Code:  Baillie:89h)
\par
We present the results of a numerical simulation of dynamically
triangulated random surfaces of fixed topology with extrinsic
curvature.  We use two different discretizations of the extrinsic
curvature and observe the differing nature of the crumpling transitions
and smooth phases.  The effect of the extrinsic curvature on both the
extrinsic and intrinsic geometry of the model is examined in three and
four dimensions.  We also discuss the similarities between our
simulation and those of surfaces of fixed triangulation and consider the
connection between models with extrinsic curvature and superstrings.
Finally, we speculate on the role of topology changes in random surface
simulations and Liouville theory.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Computational aspects of simulating
dynamically triangulated random surfaces}
\par\noindent
{\bf C. F. Baillie, D. A. Johnston, and R. D. Williams}
\par\noindent
C$^3$P-808\ \ \ \ \ \ \ (Short Code:  Baillie:89i)
\par
We briefly outline string theory, explain how it is formulated
discretely on a computer in terms of dynamically triangulated random
surfaces, and describe a computer program that simulates such surfaces
with extrinsic curvature embedded in arbitrary dimension.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Using SIMD massively-parallel computers 
for lattice calculations in physics}
\par\noindent
{\bf C. F. Baillie}
\par\noindent
C$^3$P-829\ \ \ \ \ \ \ (Short Code: Baillie:89j)
\par
Lattice calculations are now an established computational technique for high 
energy and condensed matter physics.  Moreover, with the current availability 
of massively-parallel advanced architecture SIMD computers approaching 
supercomputer performance --- in particular, the TMC Connection Machine and 
the AMT TAP --- which, as we shall demonstrate, are tailor made for such 
problems, numerical simulations of lattice QCD and spin models using these 
machines are very effective.  We have been performing lattice simulations of 
the 3D Ising spin model on the DAP and of QCD with dynamical fermions on the 
Connection Machine.  Herein, I describe what these calculations are, how they 
have been implemented on the SIMD computers and the performances obtained.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf A new MCRG calculated of the critical 
behavior of the 3D Ising model --- preliminary results}
\par\noindent
{\bf C. F. Baillie, K. N. Barish, R. Gupta, and G. S. Pawley}
\par\noindent
C$^3$P-831\ \ \ \ \ \ \ (Short Code: Baillie:89k)
\par
We have undertaken a large-scale computer simulation of the 3D Ising model 
using the Monte Carlo Renormalization Group (MCRG) method.  Our calculation 
improves on past calculations in three ways.  Firstly, larger lattices are 
used --- we have run on $128^{3}$ as well as $64^{3}$.  Secondly, many more 
spin operators --- 53 even and 46 odd --- are measured.  Lastly, we have 
incorporated more efficient ways of spin update --- Wolff's single-cluster 
variant of the Swendsen and Wang algorithm.  In addition to calculating the 
critical temperature, the thermal and magnetic exponents, and improving the 
estimate of the correction-to-scaling exponent, we are aiming to verify the 
presence of redundant operators.  We do not yet have sufficient statistics to 
give final results so here we describe our calculation and present preliminary 
results which demonstrate that we have control over both finite size effects 
and systematic errors arising from truncation.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf A comparison of cluster algorithms
for Potts models}
\par\noindent
{\bf C. F. Baillie and P. D. Coddington}
\par\noindent
C$^3$P-835\ \ \ \ \ \ \ (Short Code: Baillie:89l)
\par
We have measured the dynamical critical exponents for the Swendsen-Wang
and the Wolff cluster update algorithms, as well as a number of variants
of these algorithms, for the $q=2$ and $q=3$ Potts models in two
dimensions.  We find that although the autocorrelation lengths differ
considerably between algorithms, the critical exponents are the same.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Status and prospects of the
computational approach to high energy physics}
\par\noindent
{\bf C. F. Baillie, D. A. Johnston, and G. W. Kilcup}
\par\noindent
C$^3$P-800b\ \ \ \ \ \ \ (Short Code: Baillie:89m)
\par
We review the status of lattice computer calculations in Quantum Chromo-
dynamics (QCD) and mention a new field of computational in high energy physics 
--- that of Strings or random surfaces.  After outlining Monte Carlo Field 
Theory we explain in detail both QCD and Strings --- describing how these 
theories are discretized on a lattice, what one can calculate and how much 
computer time is required.  We include a summary of the concurrent QCD 
machines which have been, and are being, built.  We speculate on the prospects 
for such work --- including a prediction for when QCD will be ``solved''.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf A comparison of the CM with the DAP
for lattice gauge theory}
\par\noindent
{\bf C. F. Baillie and G. S. Pawley}
\par\noindent
C$^3$P-530\ \ \ \ \ \ \ (Short Code: Baillie:89n)
\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 Chromodynamics
(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.  Thus, as a first step
towards computer simulation of QCD, we have developed code for QED on
the CM, and compared this 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 Lattice QCD --- As a large scale
scientific computation}
\par\noindent
{\bf C. F. Baillie and D. W. Walker}
\par\noindent
C$^3$P-641\ \ \ \ \ \ \ (Short Code: Baillie:89o)
\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 A mechanism for keeping useful
internal information in parallel programming tools:  The data access
descriptor}
\par\noindent
{\bf V. Balasundaram}
\par\noindent
C$^3$P-843\ \ \ \ \ \ \ (Short Code:  Balasundaram:89a)
\par
An important aspect of any parallel programming tool is its ability to 
provide useful information that can help the user optimize a program for 
efficient parallel execution, or debug a parallel program.  In many parallel 
programming tools, {\it data dependence\/} information is a fundamental 
requirement for the implementation of the various utilities provided by the 
tool.}
\par
Experience has shown that while data dependence is a powerful concept, it
sometimes causes several complexities both in internal analysis and 
programmer-tool interaction. These problems can be overcome by summarizing 
the effect of data dependences in parts of the program.  This paper presents 
a mechanism for summarizing data accesses in numerical scientific programs, 
that is easy to implement and manipulate in a programming tool.
\par
Data dependence is treated as an intersection between data access summaries,
which allows data dependence and data access to be treated in a unified 
manner.  This is useful in a parallel programming tool, where internal 
analyses use data dependences, but external interaction must be done using 
high-bandwidth conceptual information, such as data access summaries.

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf A computer simulation of the 3D Ising 
model:  Two methods to determine critical exponents}
\par\noindent
{\bf K. N. Barish}
\par\noindent
C$^3$P-819\ \ \ \ \ \ \ (Short Code: Barish:89a)
\par
This senior thesis presents results (the values of the critical exponents) of 
a computer simulation of the 3-dimensional Ising model.  The results have been 
obtained by two methods.  The first is a brute force method, which gives a 
physical feel for the Ising model and produces approximate answers.  The 
second is Monte Carlo Renormalization Group (MCRG), in which 99 spin operators 
are evaluated.  Brute force was carried out on a lattice of size $32^3$; MCRG 
on $32^3$, $64^3$, and preliminary data on $128^3$.  The ultimate goal of this 
work is to improve the accuracy of the critical exponents by an order of 
magnitude, and study the effects of a large number of spin operators.  For 
this thesis, I focus on the effects of the large number of spin operators on a 
$64^3$ system.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Critical Behavior of the 2D anisotropic
Heisenberg antiferromagnet:  A numerical test of spin-wave theory}
\par\noindent
{\bf T. Barnes, K. J. Cappon, E. Dagotto, D. Kotchan and E. S. Swanson}
\par\noindent
C$^3$P-722\ \ \ \ \ \ \ (Short Code: Barnes:89a)
\par
We present results from a numerical study of the spin-excitation energy gap
of the two dimensional anisotropic Heisenberg antiferromagnet.  Our study
finds a nonzero gap for Ising-like anisotropy which approaches zero at the
isotropic point.  With XY-like anisotropy, the system is planar antialigned
and remains gapless, which is consistent with the nearly gapless spin-wave
dispersion relation observed in the high-T$_c$ precursor insulators.  Near
isotropy the gap is not well described by the $g < 1$ spin-wave theory
prediction $E_{gap} = 2\sqrt{1-g^{2}}$.  Possible sources of this discrepancy
are discussed; one such effect, ``softening'' of the mean antiferromagnetic
background by quantum fluctuations, provides corrections to spin-wave theory
which bring it into agreement with our Monte Carlo results.  This effect
may require reinterpretation of neutron scattering and far-infrared absorption
data in the determination of the precursor insulator spin Hamiltonian.  Our
results also clarify the physical mechanisms underlying the Mermin-Wagner
theorem and allow a higher-dimensional generalization of the Haldane
conjecture.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Accelerated back-propagation learning:  Two
optimization methods}
\par\noindent
{\bf R. Battiti}
\par\noindent
C$^3$P-714\ \ \ \ \ \ \ (Short Code: Battiti:89a)
\par
Two methods of increasing performance of the back-propagation
learning algorithm are presented and their results are compared
with those obtained by optimizing parameters in the standard
method.  The first method requires adaptation of a scalar learning
rate in order to decrease the energy value along the gradient
direction in a close to optimal way.  The second one is derived
from the conjugate gradient method with inexact linear searches.
The strict locality requirement is relaxed but parallelism of
computation is maintained, allowing efficient use of concurrent
computation.  For medium-size problems, typical speedups of one
order of magnitude are obtained.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Surface reconstruction and discontinuity
detection:  A fast hierarchical approach on a two-dimensional mesh}
\par\noindent
{\bf R. Battiti}
\par\noindent
C$^3$P-732\ \ \ \ \ \ \ (Short Code: Battiti:89b)
\par
Recently multiscale techniques have been proposed for solving low-level
vision problems in optimal time (i.e., time proportional to the number
of pixels).  In the present work, this method is extended to incorporate
a discontinuity detection step cooperating with the smoothing phase on
all scales.  Activation of line element detectors that signal the
presence of relevant discontinuities is based on information gathered
from neighboring points at the same and different scales.}
\par
Since the required computation is local, parallelism can be profitably
used.  A mapping of the required data structure onto a two-dimensional
mesh of processors is suggested.  Domain decomposition is shown to be
close to optimal for a MIMD computer capable of containing many individual
cells in each processor.
\par
Some examples of the proposed multiscale solution techniques are shown
for two different cases.  In the first case (shape from shading), a 
surface is reconstructed from first derivative information collected in
a preliminary step from the intensity data.  In the second, noisy depth
constraints are given directly and the optimally smooth surface is fitted
to the data.

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Low level image processing with high level
``emergent properties'':  Color based segmentation using the heat diffusion
equation}
\par\noindent
{\bf R. Battiti}
\par\noindent
C$^3$P-776\ \ \ \ \ \ \ (Short Code: Battiti:89c)
\par
The problem considered in this work is that of {\it image segmentation based on
color differences.}  These dissimilarities are detected by considering changes
in the relative intensity of the red, green and blue components of the pixels
adjacent to a given discontinuity.}
\par
The computational framework incorporates a {\it discontinuity detection} process
into a multigrid relaxation algorithm, with the goal of recovering ``significant''
discontinuities at different scales.  Line processes are activated in a
deterministic way, depending on local evidence collected from neighboring
line processes (at different scales) and from neighboring intensity values.
Computational complexity is $O (n)$ for an image with $n$ pixels and convergence
time is a small multiple of that required by one relaxation step at the finest
grid.
\par
A final relaxation step restricted within the detected boundaries is then
suggested as a way of ``coloring'' the delineated regions in a uniform way. 
Exploiting a physical analogy (intensity $\rightarrow$ temperature), this step
is equivalent to solving a discretized version of the heat diffusion equation
with insulated boundaries.
\par
The algorithm has been implemented with high efficiency on a MIMD parallel
computer with distributed memory.  A {\it coarse grain} domain decomposition
is found to be useful for this and other multiscale problems.

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf A multiscale approach to surface reconstruction
with discontinuity detection}
\par\noindent
{\bf R. Battiti}
\par\noindent
C$^3$P-676b\ \ \ \ \ \ \ (Short Code: Battiti:89d)
\par
A fast multiscale scheme for reconstructing a piecewise smooth surface from
sparse and noisy data is proposed in which line element detectors ({\it line
processes}) at different resolutions are coupled in a coherent way to a
multiscale ``smoothing'' algorithm acting on the depth points.  A new strategy
for the interaction of the line processes with a neighborhood of depth points
and line processes at various scales has been tested on ``Randomville'' images
(random collection of quadrilateral structures in the image plane) with 
promising results.  Performance of the algorithm degrades gracefully when the
sampling rate of the constraining data is reduced to a small fraction (down to
10\%) of the grid points at the finest scale.  Comparison with reconstruction
time required by one scale algorithm shows a speed-up of at least two orders
of magnitude for $129\times 129$ test images.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Teaching neural networks with the
memoryless quasi-Newton method:  Automatic parameter tuning and fast
convergence}
\par\noindent
{\bf R. Battiti}
\par\noindent
C$^3$P-841\ \ \ \ \ \ \ (Short Code: Battiti:89e)
\par
Standard back-propagation learning for feed-forward neural networks is
known to have slow convergence properties.  Furthermore, no general
prescription is given for selecting the appropriate learning rate, so
success is dependent on a trial and error process.  In this work, a
well-known optimization technique (the BFGS memoryless quasi-Newton
method) is employed to speed up convergence and to select parameters.
The strict locality requirements is relaxed but parallelism of
computation is maintained, allowing efficient use of concurrent
computation.  While requiring only limited changes to back-propagation,
this method yields a speed-up of up from one to three orders of
magnitude for medium-size networks.}
\par
Comparisons are done with back-propagation using optimal parameters and
with a version of it employing learning rate adaptation.  This last
method is in itself interesting, since it converges in a number of
iterations close to that of optimized back-propagation, with no need for
parameter optimization.

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Low level image segmentation with
high level ``emergent properties'':  Color based segmentation}
\par\noindent
{\bf R. Battiti}
\par\noindent
C$^3$P-776b \ \ \ \ \ \ \ (Short Code: Battiti:89f)
\par
The presented method incorporates a discontinuity detection process into
a multigrid relaxation algorithm, with the goal of recovering
``significant'' discontinuities at different scales.  Line processes are
activated in a deterministic way, depending on local properties of both
neighboring line processes (at different scales) and neighboring
continuous variables.  Computational complexity is $O(n)$ for an image
with $n$ pixels and convergence time is a small multiple of that
required by one relaxation step at the finest grid.}
\par
The suggested scheme is applied to the problem of image segmentation
based on color differences.  These dissimilarities are detected by
considering changes in the relative intensity of the red, green and blue
components of the pixels adjacent to a given discontinuity.
\par
A final relaxation step restricted within the detected boundaries is
then suggested as a way of ``coloring'' the delineated regions in a
uniform way.
\par
The algorithm has been implemented with high efficiency on a MIMD
parallel computer with distributed memory.  A {\it coarse grain\/}
decomposition is found to be useful for this and other multiscale
problems.

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Multiscale methods, parallel
computation, and neural networks for computer vision}
\par\noindent
{\bf R. Battiti}
\par\noindent
C$^3$P-850\ \ \ \ \ \ \ (Short Code: Battiti:89g)
\par
This thesis presents new algorithms for low and intermediate level
computer vision.}
\par
The guiding ideas in the presented approach are those of hierarchical
and adaptive processing, concurrent computation, and supervised
learning.
\par
Processing of the visual data at different resolutions is used not only
to reduce the amount of computation necessary to reach the fixed point,
but also to produce a more accurate estimation of the desired
parameters.  The presented {\it adaptive multiple scale technique\/} is
applied to the problem of motion field estimation.  Different parts of
the image are analyzed at a resolution that is chosen in order to
minimize the error in the coefficients of the differential equations to
be solved.  Thests with video-acquired images show that velocity
estimation is more accurate over a wide range of motion with respect to
the homogeneous scheme.  In some cases introduction of {\it explicit
discontinuities\/} coupled to the continuous variables can be used to
avoid propagation of visual information from areas corresponding to
objects with different physical and/or kinematic properties.
\par
The human visual system uses concurrent computation in order to process
the vast amount of visual data in ``real-time''.  Although with
different technological constraints, parallel computation can be used
efficiently for computer vision.  All the presented algorithms have been
implemented on {\it medium grain distributed memory multicomputers\/}
with a speed-up approximately proportional to the number of processors
used.  A simple two-dimensional domain decomposition assigns regions of
the multiresolution pyramid to the different processors.  The
inter-processor communication needed during the solution process is
proportional to the linear dimension of the assigned domain, so that
efficiency is close to 100\% if a large region is assigned to each
processor.
\par
Finally, learning algorithms are shown to be a viable technique to
engineer computer vision systems for different applications starting
from multiple-purpose modules.  In the last part of the thesis a well
known optimization methods {\it (the Broyden-Fletcher-Goldfarb-Shanno
memoryless quasi-Newton method)\/} is applied to simple classification
problems and shown to be superior to the ``error back-propagation''
algorithm for numerical stability, automatic selection of parameters,
and convergence properties.

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Chaotic Advection and Dynamical Systems Analysis
using Caltech/JPL Hypercubes}
\par\noindent
{\bf D. Beigie, A. Leonard and S. Wiggins}
\par\noindent
C$^3$P-752\ \ \ \ \ \ \ (Short Code: Beigie:89a)
\par
We investigate the chaotic transport and mixing of fluids in some model
flows using dynamical systems techniques.  Computer simulation allows us
to illustrate the essential structure of the bulk transport and to quantify
reaction rates across material boundaries in certain cases of chemically
reacting flows.  Such simulations follow the time evolution of material
curves which stretch and fold in a violent way (due to the chaotic nature
of our models), and hence they track a large number of points to approximate
the curves.  Each point moves independently of others and defines an orbit
of our dynamical system, so that the computation evolves in parallel a great
number of orbits.  Concurrent computers are thus appropriate here.  Spatially
varying stretch rates encourage dynamic insertion and deletion of points to
maintain a good approximation of the material curve, causing problems with
load balancing.  However, reasonable load balance can be achieved by a
scattered decomposition of the initial curve to more evenly distribute the
stretch rates among the nodes, followed by infrequent redistribution of the
curve in cases of highly localized stretching.  Further, node communication
on local memory machines can be kept at zero with minimal inefficiency by
having adjacent nodes share the boundary points in the decomposition.  Other
relevant simulations track in parallel isolated material points rather than
curves; here there is no need for point insertion and hence parallelization
is trivial.  Some simulations have been completed on Caltech/JPL hypercubes
and sequential machines, and others are still being developed.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Pure gauge QCD on the Connection Machine}
\par\noindent
{\bf R. Brickner and C. Baillie}
\par\noindent
C$^3$P-710\ \ \ \ \ \ \ (Short Code: Brickner:89a)
\par
We are part of a collaboration developing software to perform large-scale
Quantum Chromo-dynamics (QCD) computations on the massively-parallel
Connection Machine.  This machine offers the potential of peak execution
rates in excess of Cray 2 or Y-MP systems currently available to us, so it
is natural to test the suitability of this machine for our application.  For
this purpose, we have obtained performance results for a pure gauge QCD code
written entirely in $^\ast$Lisp.  At the same time, we are working on the
final debugging of a dynamical Wilson fermion QCD code; performance figures
for the fermion code are not yet available  This paper first gives a brief
description of the Connection Machine and an outline of QCD.  Then we describe
our pure gauge program in some detail.  We end with timings and performance
measurements obtained on a 64K machine at Thinking Machines Corporation.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Implementation and performance evaluation of
multigrid methods on hypercubes: Part I}
\par\noindent
{\bf L. Brochard}
\par\noindent
C$^3$P-771\ \ \ \ \ \ \ (Short Code: Brochard:89a)
\par
We present a two-fold study of multigrid methods on hypercubes.  The first
study presents parallel implementations of standard multigrid methods to
solve a 2D potential flow over an airfoil using finite elements on a regular
grid, and their efficiencies on two different hypercubes: a 256-node Ncube
and a  32-node Mark III.  The second study presents a performance model of
these methods, compares it with experimental results and uses it to study
the efficiency of different parallel implementations of standard multigrid
methods depending on the cycle type, the problem granularity and some machine
and program parameters.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Implementation and performance evaluation of
multigrid methods on hypercubes: Part II}
\par\noindent
{\bf L. Brochard}
\par\noindent
C$^3$P-772\ \ \ \ \ \ \ (Short Code: Brochard:89b)
\par
We present a two-fold study of multigrid methods on hypercubes.  The first study
presents V and W cycles parallel implementations of standard multigrid methods
to solve a 2D potential flow over an airfoil using finite elements on a regular
grid, and their efficiencies on two different hypercubes: a 256-node Ncube and a
32-node Mark III.  The second study presents a performance model of these methods,
compares it with experimental results and uses it to study the efficiency of
different parallel implementations of standard multigrid methods depending on the
cycle type, the problem granularity and some machine and program parameters.  We
present also an analysis to take into account the load imbalance that appeared in
our computation.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Synchronization and load imbalance effects of
parallel iterative algorithms}
\par\noindent
{\bf L. Brochard, J.-P. Prost and F. Faurie}
\par\noindent
C$^3$P-783\ \ \ \ \ \ \ (Short Code: Brochard:89c)
\par
Waiting time due to processor synchronization can be a source of overhead in a
parallel computation, particularly when some load imbalance occurs.  Taking
the example of an iterative process, we present a theoretical, experimental
and simulation study of the maximum time of the process, depending on various
kinds of synchronization schemes.  Synchronizations barrier are the more costly,
while full asynchronous schemes minimize the waiting time.  Between those two
extremes, weaker synchronization schemes where each process waits for only a
subset of the others, are shown to be efficient to reduce the cost of the
synchronization scheme, and the waiting time due to the load imbalance.  Domain
decomposition is shown to be a good example of the application of some of these
results.}

\bigskip\starline\bigskip
\vbox{\par\noindent
{\bf Transparencies} from seminar by M. L. Brown, entitled ``A hypercube image
processing language'', presented at JTF Concurrent Processing Applications
Coordination Meeting, Caltech, March 1989.  C$^3$P-753 (Short Code: Brown:89a)}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf A Hypercube Image Processing Language}
\par\noindent
{\bf M. L. Brown}
\par\noindent
C$^3$P-754\ \ \ \ \ \ \ (Short Code: Brown:89b)
\par
Presently, a large gap exists between algorithms for Image Processing
presented in an Algol-algorithmic format, and the actual implementation
of Image Processing Software for the Hypercube.  A computer language and
implementation, designed as a Hypercube Image Processing Language (HIPL),
are presented.  The current C language dialect used for the Hypercube is
enhanced and extended to a Very High Level Language (VHLL), including
Image Processing Constructs at the Implementation Level.  The language
uses the principles of Data Abstraction and Information Hiding to enable
the programmer to concentrate exclusively on the problem of Image
Processing, leaving the programming details and many Image Processing
High Level Commands to be handled by the implemented language.  The
objective of the Hypercube Image Processing Language is to reliably and
efficiently implement Image Processing Algorithms and Techniques to
Hypercube Software for Concurrent Processing.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Hypercube matrix computation task --- 
report for 1986--1988}
\par\noindent
{\bf R. H. Calalo, W. A. Imbriale, N. Jacobi, P. C. Liewer, T. G. Lockhart, G. 
A. Lyzenga, J. R. Lyons, F. Manshadi, and J. E. Patterson}
\par\noindent
C$^3$P-743\ \ \ \ \ \ \ (Short Code: Calalo:89a)
\par
A major objective of the Hypercube Matrix Computation effort at the Jet 
Propulsion Laboratory (JPL) is to investigate the applicability of a parallel 
computing architecture to the solution of large-scale electromagnetic 
scattering problems.  Three scattering analysis codes are being implemented 
and assessed on a JPL/California Institute of Technology (Caltech) Mark~III 
Hypercube.  The codes, which utilize different underlying algorithms, give a 
means of evaluating the general applicability of this parallel architecture.  
The three analysis codes being implemented are a frequency domain method of 
moments code, a time domain finite difference code, and a frequency domain 
finite elements code.  These analysis capabilities are being integrated into 
an electromagnetics interactive analysis workstation which can serve as a 
design tool for the construction of antennas and other radiating or scattering 
structures.}
\par
This document is a summary of the first two years of work on the Hypercube 
Matrix Computation effort.  It includes both new developments and results as 
well as work previously reported in the ``Hypercube Matrix Computation Task:  
Final Report for 1986--87'' (JPL Publication 87-18).

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Random coupling models of lattice
fermion}
\par\noindent
{\bf T.-W. Chiu}
\par\noindent
C$^3$P-813\ \ \ \ \ \ \ (Short Code: Chiu:89a)
\par
Random-coupling models for free lattice fermions on the four-dimensional
regular lattice are discussed.  The fermion propagators in position
space and in momentum space are studied respectively.  The results
showed that an arbitrarily short-range strong random coupling between
neighboring spinors does not necessarily confine the double modes and
yield the correct continuum limit.  This naturally leads to the more
fundamental viewpoint that in order to avoid the fermion doubling
problem which is only an artifact on any single lattice, one must sum
the path integrals on all different lattices provided that the
superposition of these lattices can give a good approximation to the
manifold of spacetime continuum.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Hyper-spherical coordinate reactive 
scattering using variational surface function}
\par\noindent
{\bf S. A. Cuccaro, P. G. Hipes, and A. Kuppermann}
\par\noindent
C$^3$P-720\ \ \ \ \ \ \ (Short Code:  Cuccaro:89a)
\par
An efficient numerical method of calculating surface functions for accurate 
quantum mechanical three-dimensional reactive scattering using symmetrized 
hyper-spherical coordinates has been developed.  This method is at least 20 
times faster than the finite-element method used previously and its accuracy 
is demonstrated for the $H+H_2$ system.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Symmetry analysis of accurate ${\bf H+H_2}$ 
resonances}
\par\noindent
{\bf S. A. Cuccaro, P. G. Hipes, and A. Kuppermann}
\par\noindent
C$^3$P-821\ \ \ \ \ \ \ (Short Code:  Cuccaro:89b)
\par
We have performed accurate quantum mechanical three-dimensional reactive 
scattering calculations for both partities of the $J=1$ partial wave of the 
$H+H_2$ system up to total energies of ${\rm 1.75\,eV}$.  The collision 
lifetime resonance spectra for both $J=0$ and $J=1$ are discussed in terms of 
the characteristics of the system's potential energy surface and of a simple 
physical model involving its symmetry properties.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Heavy quark potential at large separation}
\par\noindent
{\bf H.-Q. Ding, C. F. Baillie and G. C. Fox}
\par\noindent
C$^3$P-779\ \ \ \ \ \ \ (Short Code: Ding:89a)
\par
The static $q\bar q$ potential is measured on $24^3 \times 10$, $12^3 \times 24$
and $16^3 \times 24$ lattices at $\beta =6.0$ with high statistics.  Using
Wilson line operator-operator correlations, we find ${\sqrt\sigma\over\Lambda_L}
\simeq 77$ and $\alpha\simeq 0.59$, with a modified $\chi^2$ fit which exhibits
better stability than the standard $\chi^2$ fit.  This new result compares
favorably with that obtained from Charmonium experimental data, but is
significantly different from many previous lattice calculations.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Performance of a QCD code on MarkIIIfp
Hypercube II}
\par\noindent
{\bf H.-Q. Ding}
\par\noindent
C$^3$P-799\ \ \ \ \ \ \ (Short Code: Ding:89b)
\par
The QCD code with vectorized communication is timed on the MarkIIIfp 
hypercube up to 128-nodes.  The speedup is shown to be linear and increases 
as the size of the computation increases.  On 128-node, a sustained speed of 
479 Mflops is achieved.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Spin corelations of 2D quantum
antiferromagnet at low temperatures and a direct comparison with neutron
scattering experiments}
\par\noindent
{\bf H.-Q Ding and M. S. Makivic}
\par\noindent
C$^3$P-844\ \ \ \ \ \ \ (Short Code:  Ding:89c)
\par
Correlation functions of the spin-${1\over 2}$ 2-dimensional Heisenberg
antiferromagnet at low temperatures are computed via a large scale
Monte-Carlo simulation on $128\times 128$ lattices.  The correlation
length is found to be accurately described by the exponentially
divergent form typical of classical Heisenberg spins in two dimensions.
The large correlation lengths measured are directly compared with the
neutron scattering experiments on $La_2CuO_4$.  The excellent fit
provides a first principles determination of the exchange coupling:
$j=1450\pm 30K$.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Quantum Spin Calculations on a
Hypercube Parallel Supercomputer}
\par\noindent
{\bf H.-Q. Ding and M. S. Makivic}
\par\noindent
C$^3$P-845\ \ \ \ \ \ \ (Short Code:  Ding:89d)
\par
A large scale Quantum Monte Carlo simulation is performed on the Mark~IIIfp 
Hypercube supercomputer to systematically study the quantum spin dynamics of 
the recently discovered high-$T_c$ superconducting mother material.  The 
algorithm is very efficiently implemented on the Hypercube.  The 
three-dimensional lattice is partitioned into a ring of processor nodes.  
Parallelism is also achieved by running several independent simulations on 
several processor rings simultaneously.  The local updates are easily handled 
by the CROS communication system.  Global updates are efficiently implemented 
by a ``gather --- scatter'' routines written in CROS calls.  Spins are packed 
into 32-bit words along the time direction.  Local updates are vectorized 
along time direction.  We also report a systematic performance analysis.  The 
efficiency of the implementation is over 90\%.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf 64-bit Mark~IIIfp hypercube:  A
preliminary performance evaluation}
\par\noindent
{\bf H.-Q. Ding}
\par\noindent
C$^3$P-847\ \ \ \ \ \ \ (Short Code: Ding:89e)
\par
The characteristic timings and a preliminary performance of the QCD
codes on the 64-bit Mark~IIIfp node is reported.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf A Kosterlitz-Thouless transition in the 
quantum $XY$ model in 2D}
{\bf H.-Q. Ding and M. S. Makivic}
\par\noindent
C$^3$P-851\ \ \ \ \ \ \ (Short Code:  Ding:89f)
Conclusive evidence is obtained via a large scale Monte Carlo simulation that 
the Spin-${1\over 2}XY$ magnet in two-dimension undergoes a Kosterlitz-
Thouless phase transition at $kT_c/J=0.350(4)$.  Correlation length and in-
plane susceptibility diverge at $T_c$ precisely according to the form predicted 
by Kosterlitz and Thouless for the classical $XY$ model.  The temperature 
derivative of specific heat exhibits a very sharp peak around $T_c$, 
suggesting that the KT transition is of third order.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Calculation of the heavy quart
potential at large separation on a hypercube parallel computer}
{\bf H.-Q. Ding, C. F. Baillie, and G. C. Fox}
\par\noindent
C$^3$P-779b\ \ \ \ \ \ \ (Short Code:  Ding:89g)
The static $q\bar q$ potential is measured on $24^3 \times 10$, $24^3
\times 12$, $12^3 \times 24$ and $16^3 \times 24$ lattices at $\beta =
6.0$ with high statistics.  Using Wilson line operator-operator
correlations, we find ${\sqrt\sigma\over\Lambda_L}\simeq 77$ and
$\alpha\simeq 0.58$.  This new result compares favorably with that
obtained from Charmonium experimental data, but is significantly
different from many previous lattice calculations.  Our calculations use
a hypercube parallel computer which in its full configuration performs
at 0.6 gigaflops on this application.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Parallelizing a real application code:  
Is it worth it?}
\par\noindent
{\bf E. Felten, P. Messina and R. Williams}
\par\noindent
C$^3$P-713\ \ \ \ \ \ \ (Short Code: Felten:89a)
\par
We have studied issues involved in porting a real application to a
distributed memory machine while attempting to keep the code efficient
and portable.  MACH2 is a magnetohydrodynamic simulation code written
with about 20000 lines of FORTRAN.  Moderate parallelism may be extracted
by domain-decomposing the algorithm, but the existing algorithm is not
suitable for a massively parallel machine.  This is partly because the
code is actually used with relatively coarse meshes; and partly because
the code requires a large equation of state database, and we discuss
parallel implementations of this.  We also discuss algorithmic changes
to exploit parallelism, such as parallel multigrid and parallel operator
splitting techniques.  We have made a small version of MACH2, which runs
on distributed memory machines; with an automatic load-balancer, and a
mesh-generator and optimizer.  We present timings of this small version.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Multi-scale training of a large
back-propagation net}
\par\noindent
{\bf E. Felten, O. Martin, S. Otto, and J. Hutchinson}
\par\noindent
C$^3$P-608b \ \ \ \ \ \ \ (Short Code: Felten:89b)
\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 Experience on the hypercube}
\par\noindent
{\bf G. C. Fox}
\par\noindent
C$^3$P-716\ \ \ \ \ \ \ (Short Code: Fox:89b)
\par
A review of lessons learned and techniques for improving the performance of
the hypercube on a variety of scientific problems.  This was submitted as a
section of a paper ``Communication and Data Motion,'' edited by David Salzman
of JVNC.}

\bigskip\starline\bigskip
\vbox{\par\noindent
{\bf Transparencies} from talk by G. C. Fox, entitled ``Applications of parallel
supercomputers'' presented at Syracuse, March 1989.  C$^3$P-726 (Short
Code: Fox:89d)}

\bigskip\starline\bigskip
\vbox{\par\noindent
{\bf Transparencies} from talk by G. C. Fox, entitled ``State of the hypercube
1989'', presented at the Fourth Conference on Hypercubes, Concurrent Computers
and Applications, Santa Clara, March 1989.  C$^3$P-727 (Short Code: Fox:89e)}

\bigskip\starline\bigskip
\vbox{\par\noindent
{\bf Transparencies} from talk by G. C. Fox, entitled ``Some neural network
applications at Caltech'', presented at JTF Concurrent Processing Applications
Coordination Meeting, March 1989.  C$^3$P-742.1 (Short Code: Fox:89g)}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf A note on neural networks for trackfinding}
\par\noindent
{\bf G. C. Fox}
\par\noindent
C$^3$P-748\ \ \ \ \ \ \ (Short Code: Fox:89h)
\par
We propose a neural network approach to trackfinding that is analogous to our
string formalism for navigation and routing problems.  We show that it is
particularly attractive for problems with a large number of possibly clustered
tracks, and many false measurements.  The neural network approach is, in these
difficult cases, not subject to the combinatorial explosion of the traditional
multi-target Kalman filter methods.  Our methods are analogous to those used
for edge detection and feature extraction in a multi-dimensional image.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf 1989 -- The first year of the parallel
supercomputer}
\par\noindent
{\bf G. C. Fox}
\par\noindent
C$^3$P-769\ \ \ \ \ \ \ (Short Code: Fox:89i)
\par
Parallel Computing has come of age with several commercial and in-house systems
available which not only promise, but realize supercomputer or better performance.
We survey several major computations underway on hypercubes, transputer arrays and
the SIMD Connection Machine CM-2 and AMT DAP.  Where possible, we compare parallel
implementations with those on CRAY and other high performance conventional
computers.  We summarize these experiences as a set of lessons for applications,
decomposition, performance, hardware and software for parallel machines.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Applications of neural networks and parallel
processing}
\par\noindent
{\bf G. C. Fox}
\par\noindent
C$^3$P-781\ \ \ \ \ \ \ (Short Code: Fox:89j)
\par
Neural Networks are a general approach to artificial intelligence including
problems of scheduling and routing information.  They can be used to dynamically
assign work and route messages on parallel computers.  On the other hand,
parallel computers can be used to simulate artificial and biological neural
networks.}
\par
We describe our research in these synergistic areas including an object oriented
approach to complex system simulation and applications of neural networks to
vehicle navigation and message routing.

\bigskip\starline\bigskip
\vbox{\par\noindent
{\bf Transparencies} from a talk by G. C. Fox, entitled ``Campus Research for
ESD and Related to ESD Mission'', Caltech, May 1989.  C$^3$P-788 (Short
Code: Fox:89k)}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Code generation by a generalized neural 
network:  General principles and elementary examples}
\par\noindent
{\bf G. C. Fox and J. G. Koller}
\par\noindent
C$^3$P-650b\ \ \ \ \ \ \ (Short Code:  Fox:89l)
\par
We discuss the possibility of using neural network optimization to perform 
optimized code generation, and list possible benefits.  The approach used by 
Hopfield and Tank to treat the traveling salesman is extended to cover the 
motion of abstract quantities through a computer.  A simple general method for 
constructing complicated syntactic constraints is introduced, applicable to 
both sequential and parallel target architectures.  We test the approach on 
some very elementary examples of sequential code, by simulation.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Parallel computing comes of
age:  Supercomputer level parallel computations at Caltech}
\par\noindent
{\bf G. C. Fox}
\par\noindent
C$^3$P-795\ \ \ \ \ \ \ (Short Code: Fox:89n)
\par
Parallel supercomputers are now in regular use at Caltech for several major
scientific calculations.  We use this experience to abstract a set of lessons for
applications, decomposition, performance, hardware and software.  We consider
hypercubes, transputer arrays, networks of work stations, and the SIMD Connection
Machine CM-2 and AMT DAP.  These are contrasted, where possible, with CRAY and
other high performance conventional computers.  Applications covered are lattice
gauge theory, string dynamics, statistical and condensed matter physics, plasma
physics, astronomical data analysis, quantum chemistry, graphics ray tracing, grain
dynamics, astrophysical particle dynamics, computer chess, and Kalman filters.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Applications of parallel
supercomputers: scientific results and computer science lessons}
\par\noindent
{\bf G. C. Fox}
\par\noindent
C$^3$P-806\ \ \ \ \ \ \ (Short Code: Fox:89p)
\par
Parallel Computing has come of age with several commercial and in-house
systems that deliver supercomputer performance.  We illustrate this with
several major computations completed or underway at Caltech on
hypercubes, transputer arrays and the SIMD Connection Machine CM-2 and
AMT DAP.  Applications covered are lattice gauge theory, computational
fluid dynamics, subatomic string dynamics, statistical and condensed
matter physics, theoretical and experimental astronomy, quantum
chemistry, plasma physics, grain dynamics, computer chess, graphics ray
tracing, and Kalman filters.  We use these applications to compare the
performance of several advanced architecture computers including the
conventional CRAY and ETA-10 supercomputers.  We describe which problems
are suitable for which computers in the terms of a matching between
problem and computer architecture.  This is part of a set of lessons we
draw for hardware, software, and performance.  We speculate on the
emergence of new academic disciplines motivated by the growing
importance of computers.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf The use of neural networks in
parallel software systems}
\par\noindent
{\bf G. C. Fox, W. Furmanski, and J. Koller}
\par\noindent
C$^3$P-642b\ \ \ \ \ \ \ (Short Code:  Fox:89q)
\par
We describe the use of neural networks as an optimization or artificial
intelligence aid to parallel computing.  Applications include
load-balancing, message-routing and optimizing compilers.  We speculate
on future computers, nodes consisting of conventional digital nodes
combined with special purpose neural networks for dynamic optimization
of functions within and between nodes.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Practical parallel supercomputing:  
Examples from chemistry and physics}
\par\noindent
{\bf G. C. Fox, P. Hipes, and J. Salmon}
\par\noindent
C$^3$P-818\ \ \ \ \ \ \ (Short Code:  Fox:89t)
\par
We use two large simulations, the chemical reaction dynamics of $H+H_2$ and 
the collision of two galaxies to show that current parallel machines are 
capable of large supercomputer level calculations.  We contrast the different 
architectural tradeoffs for these problems and draw some implications for 
future production parallel supercomputers.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf CISE Research Instrumentation for a
Program in Physical Computation and Complex Systems}
\par\noindent
{\bf G. C. Fox and T. A. Prince}
\par\noindent
C$^3$P-814\ \ \ \ \ \ \ (Short Code:  Fox:89u)
\par
The program in Physical Computation and Complex Systems (PCCS) at the
California Institute of Technology will purchase a Titan~III
super-graphics computer which will be dedicated to support research in
computational science and engineering.  Physical Computation and Complex
Systems is a new Ph.D. degree-granting academic program within the
Division of Physics, Mathematics, and Astronomy at Caltech which has the
objective of developing unified approaches to abstraction, modeling, and
computation as applied to the natural world.  The program involves
research in fundamental properties of complex systems, physical
optimization methods, and the appropriate computational techniques
needed for large-scale problem solving on advanced architecture
computers.  The equipment requested under this proposal will be used for
several research projects carried out under the PCCS research program
including:  portable parallel software tools, visualization in neural
network algorithms, cellular automata, N-body simulation algorithms, and
computationally intensive image and power spectrum analysis techniques
on concurrent computers.  A strong thrust of PCCS is the close
relationship between fundamental research in computational algorithms
and software, and their application to important current problems in
scientific research.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Parallel Supercomputers for
University High-Performance Scientific Computation}
\par\noindent
{\bf G. C. Fox and P. Messina}
\par\noindent
C$^3$P-827\ \ \ \ \ \ \ (Short Code:  Fox:89w)
\par
These foils are from a presentatioan by G. Fox at NSF on September 22,
1989.  It gives an overview of the state of parallel computing with
three examples from Caltech by production scientific computation on
parallel computers.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Hands-on parallel processing}
\par\noindent
{\bf G. C. Fox, A. W. Ho, P. Messina, and T. Cole}
\par\noindent
C$^3$P-828\ \ \ \ \ \ \ (Short Code: Fox:89x)
\par
We review parallel computing from an elementary point of view and
describe two cheap ways of implementing systems as a network of
Macintosh's or PC's.  This software is available, electronically, via
the citlib facility.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Parallel computing}
\par\noindent
{\bf G. C. Fox}
\par\noindent
C$^3$P-830\ \ \ \ \ \ \ (Short Code:  Fox:89y)
\par
Advances in technology are leading to dramatic decreases in size and cost of 
basic computer components.  These are the building blocks of very powerful 
parallel machines designed so that very many ($10^{3}$--$10^{6}$) individual 
computers can work together to solve a given problem.  This approach has 
striking analogies with nature's and society's approach to problem solving.  
Use of parallel supercomputers will revolutionize many fields of science and, 
indeed, our way of life.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf A neural network approach to multi-vehicle 
navigation}
\par\noindent
{\bf G. Fox, E. Gurewitz, Y. Wong}
\par\noindent
C$^3$P-833\ \ \ \ \ \ \ (Short Code:  Fox:89aa)
\par
We develop a neural network formulation for multi-vehicle navigation on a two-
dimensional surface.  Here, a time-linking map is generated for each 
individual vehicle using techniques similar to the known shortest path 
algorithms for an isolated vehicle.  Neural networks are then applied to 
generate non-conflicting paths minimizing the time of travel.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Parallel machines as production 
supercomputers}
\par\noindent
{\bf G. C. Fox}
\par\noindent
C$^3$P-834\ \ \ \ \ \ \ (Short Code:  Fox:89bb)
\par
A variety of parallel machines have been used in the last year at Caltech for 
scientific computations at sustained performance levels that exceed that of the 
conventional CRAY approach to supercomputing.  We follow a general overview of 
what type of problems run well on what types of machine with some particular 
examples.  Lattice gauge theories, string dynamics, very large astrophysical 
particle simulations, data analysis on a variety of machines; the Connection 
Machine, NCUBE and in-house Mark~III hypercube.  We draw lessons for the 
computer center manager and the computer and computational scientist.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf MOVIE --- a software environment for 
contemporary computing}
\par\noindent
{\bf W. Furmanski}
\par\noindent
C$^3$P-822\ \ \ \ \ \ \ (Short Code:  Furmanski:89b)
\par
We discuss here the new software environment for large scale computation --- 
MOVIE (Metashell based Object oriented Visual Interactive Environment) --- 
designed and implemented recently at Caltech within the Caltech Concurrent 
Computation Project.  The goal of the system is to provide the integrated 
object oriented software environment, enabling for efficient high level 
programming, suitable for the broad class of computationally intensive 
problems in science and engineering, supporting high level model for the 
interactive graphics, compatible with current industrial standards and 
portable across a variety of computer architectures.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf MOVIE --- a software environment for
modeling complex adaptive systems}
\par\noindent
{\bf W. Furmanski and G. Fox}
\par\noindent
C$^3$P-838\ \ \ \ \ \ \ (Short Code: Furmanski:89d)
\par
We discuss here the basic elements of the new software system for large
scale computation --- MOVIE --- (Metashell based Object oriented Visual
Interactive Environment), recently designed and implemented at Caltech
within the Caltech Concurrent Computation Program.}
\par
From the research perspective, the goal of the MOVIE project is to
create a simulation environment for modeling complex systems, with the
focus on computational structures capable to adapt and act
``intelligently'', such as ensembles of image processing, early
vision, neural network and Artificial Intelligence modules, integrated
in the form of ``neural robots''.  The high level MOVIE model, based on
portable communication and computation protocol is suitable for large
scale ``intelligence engineering'' by modeling such systems in
distributed heterogeneous multicomputer environment and porting
successful implementations to dedicated massively parallel hardware.
\par
From the software engineering point of view, the MOVIE model offers a
platform for unifying elements of contemporary computing such as
networking, windowing, parallelism, number crunching and symbolic
processing.  The basic idea, borrowed from Sun NeWS, is to use an
appropriately extended PostScript as the unifying language.  The MOVIE
extension aims at promoting PostScript to a general purpose high level
object oriented language with a high performance user expandable
computational sector, fully compatible with the Adobe model for 2D
graphics and the Sun~X11/NeWS model for windowing and multitasking.

\bigskip\starline\bigskip
\vbox{\par\noindent
{\bf Transparencies} from talk by W. Furmanski, entitled ``MOVIE:  Meta-shell
based object oriented visual interactive environment'', presented at JTF 
Concurrent Processing Applications Coordination Meeting, March 1989.  
C$^3$P-742.2 (Short Code: Furmanski:89a)}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Diffraction-limited
imaging.  III:  30 milliarcsecond closure phase imaging of six binary
stars with the Hale 5m telescope}
\par\noindent
{\bf P. W. Gorham, A. M. Ghez, S. R. Kulkarni, T. Nakajima,
G. Neugebauer, J. B. Oke and T. A. Prince}
\par\noindent
C$^3$P-791\ \ \ \ \ \ \ (Short Code: Gorham:89a)
\par
We present images of six binary stars which show diffraction-limited resolution
for the Hale 5m telescope.  This corresponds to a resolution of $\sim 30$
milliarcseconds at 630 nm.  The images were constructed from analysis of
photon-limited speckle interferograms, with between $\sim 200-1100$ recorded
photons per atmospheric coherence time.  Using a new application of the CLEAN
algorithm, used commonly in synthesis mapping in radio astronomy, the
diffraction-limited Fourier amplitudes of the objects were first recovered.
The recovery of the object Fourier phase was accomplished through bi-spectral
analysis of the specklegrams.  This analysis yields the object closure phases,
from which the Fourier phases are then extracted by a least-squares
minimization.  Direct Fourier inversion then produces the final images
reported here.}
\par
The dynamic range of the resulting images varies from 3:1 to about 20:1.  The
seeing for the majority of observations was estimated to be $\sim 1.2^{\prime
\prime}$ on average.  Thus, for these simple objects, such imaging techniques
are capable of achieving a factor of 40 improvement in resolution while retaining
a contract of 2-3 magnitudes, under photon-noise limited conditions.
\par
The closure phase, first utilized in radio astronomy, is found to be generally
immune to the loss of phase coherence produced by atmospheric seeing over a
filled-aperture optical telescope.  However, significant bias in the closure
phase may be present in some regions of the bi-spectrum; such bias is probably
due to telescope or detector aberrations.  We find that phase recovery is still
quite robust using less-biased regions of the bi-spectrum.

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Recovery of diffraction-limited
object autocorrelations from astronomical speckle interferograms using
the CLEAN algorithm}
\par\noindent
{\bf P. W. Gorham, A. M. Ghez, and T. A. Prince}
\par\noindent
C$^3$P-804\ \ \ \ \ \ \ (Short Code:  Gorham:89b)
\par
We present a new technique for processing speckle interferometric data,
which uses the CLEAN algorithm, invented by Hogbom (1974) for the
deconvolution of the effects of irregular array spacings in aperture
synthesis radio maps.  Since atmospheric seeing is essentially a
convolution process of the average atmospheric transfer function with
the object structure, deconvolution may be used to recover
diffraction-limited amplitude information, as Labeyrie described in
1970.  However, speckle interferometry formally prescribes Fourier
deconvolution of the energy spectrum of the object, through a division
process that is difficult to apply to noise-limited data.  We find that
deconvolution of the image autocorrelation function, using CLEAN, is
robust under noisy conditions, is straightforward to apply, and yields
results of high quality.  We present results using photon-noise-limited
specklegrams taken with the Hale 5~m telescope at Palomar under a
variety of seeing conditions.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Identification of physics processes
using neural network classifiers}
\par\noindent
{\bf T. D. Gottschalk and R. Nolty}
\par\noindent
C$^3$P-842\ \ \ \ \ \ \ (Short Code: Gottschalk:89c)
\par
The utility of event classification schemes based on feed-forward neural
network models is explored.  Various classification networks are
examined for a simple test problem:  the identification of bottom
production of $e^{+}e^{-}$ annihilation at $E_{CM} = 14\,{\rm GeV}$.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf QCD with dynamical Wilson fermions}
\par\noindent
{\bf R. Gupta, A. Patel, C. F. Baillie , G. Guralnik, G. W. Kilcup and S. R. Sharpe}
\par\noindent
C$^3$P-674b\ \ \ \ \ \ \ (Short Code: Gupta:89a)
\par
We present results from a study of QCD with two flavors of Wilson fermions 
using the Hybrid Monte Carlo Algorithm, which incorporates the effects of 
fermion loops exactly.  We evaluate the performance of the algorithm and its 
potential for large scale computations.  We argue that in the best case the 
algorithm slows down as $V^{5/4} m_{q}^{13/4}$ at fixed gauge coupling.  We 
present improved algorithms for calculating the inverse and the determinant 
of the Wilson fermion operator.  Results for the finite temperature 
transition on $4 \times 6^3$ and $6\times 8^3$ lattices are presented at 
$\beta =5.2-5.6$.  We also give Wilson loop expectation values obtained on 
$8^4$ lattices at $\beta = 5.3$ for six values of $\kappa$.  The data show 
evidence for screening in the $q\bar q$ potential.  Lastly, on comparing 
Wilson and staggered fermion results we find that $\beta = 5.3$ is far from 
the scaling region.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Parallel Algorithms for One and
Two-Vehicle Navigation}
\par\noindent
{\bf E. Gurewitz, G. Fox, and Y. Wong}
\par\noindent
C$^3$P-852\ \ \ \ \ \ \ (Short Code:  Gurewitz:89b)
\par
A two vehicle navigator on a discrete space is analyzed.  The concept of
linking time maps as source to optimal path planning is discussed.  The
rules for constructing these maps are given in a cellular automata
mode.  The implementation of these rules on a parallel computer is
presented.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf The physics of granular systems}
\par\noindent
{\bf G. M. Gutt}
\par\noindent
C$^3$P-785\ \ \ \ \ \ \ (Short Code:  Gutt:89a)
\par
To gain an improved understanding of the physics of granular systems, 
investigations of two aspects of continuum theories of granular flows and a 
new paradigm for modeling granular systems are presented.}
\par
The analogy between a flowing granular system and a molecular gas allows the 
adaptation of elements of the kinetic theory of gasses to a continuum theory of 
granular flow.  Two significant areas of difference between gasses and granular 
materials are the additional degrees of freedom due to the spin and surface 
roughness of the grains and the boundary conditions between a granular flow 
and a bounding surface.  Using techniques from the field of nonequilibrium 
thermodynamics, equations of motion and constitutive relations are obtained 
which include the effects of the spin and surface roughness of the grains.  
Also, boundary conditions on continuum theories for flows of smooth grains are 
presented, emphasizing the need to allow for several ``slip'' degrees of 
freedom.
\par
In order to obtain a more general description of large scale effects in 
granular systems involving both flowing and static assemblies of grains, a 
model is developed (the lattice grain dynamics paradigm) for simulating 
systems containing large numbers of grains.  This model is based on concepts 
from the fields of cellular automata, lattice gasses, and particle dynamics 
simulations.

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Comparison of LU and Gauss-Jordan system
solvers for distributed memory multicomputers}
\par\noindent
{\bf P. G. Hipes}
\par\noindent
C$^3$P-652b\ \ \ \ \ \ \ (Short Code: Hipes:89a)
\par
I will contrast the LU algorithm and a variant of the Gauss-Jordan
algorithm for solving general systems of equations in multicomputer
(distributed memory) environments.  Three main points are made.
First, by saving the Gauss-Jordan multipliers, it is possible to
solve subsequent right-hand sides of a posteriori in the same number
of operations as when the LU decomposition of the coefficient matrix
is available.  Second, in some cases on a hypercube the calculation
of the multipliers requires the same execution time as the construction
of the LU decomposition.  Finally, on a hypercube the Gauss-Jordan
solution phase can be significantly faster than solving two triangular
systems as required using the LU decomposition.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Matrix multiplication on the JPL/Caltech
Mark IIIfp Hypercube -- preliminary draft}
\par\noindent
{\bf P. G. Hipes}
\par\noindent
C$^3$P-746\ \ \ \ \ \ \ (Short Code: Hipes:89b)
\par
A fast matrix multiplier for the JPL/Caltech Mark IIIfp hypercube is
described.  The matrices are assume to be square and their dimensions
are integral multiples of the number of processors in a two-dimensional
mesh of processors.  Details of the implementation of the multiplier
which uses explicit intraprocessor blocking and hand optimized assembler
for the Weitek XL fast floating point processor are given.  Timings are
presented for a range of matrix sizes on 1, 16, 32, 64, and 128 processor
machines.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Brief report on a parallel 
electron-molecule scattering program}
{\bf Paul G. Hipes}
\par\noindent
C$^3$P-815\ \ \ \ \ \ \ (Short Code: Hipes:89c)
\par
The multichannel Schwinger variational method of electron-molecule scattering 
has been modified and augmented to run on the JPL/Caltech Mark~IIIfp 
hypercube.  The code is originally from the CRAY~X-MP and was not turned for 
high performance.  Instead, the methodology has been explored and an 
impressive amount of science has been done on the CRAY.  This report is a 
short overview of the porting of this CRAY code to the hypercube where 
performance is the central issue; any urges to change the methodology have not 
been indulged.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Comparison of LU and Gauss-Jordan
system solvers for distributed memory multicomputers}
\par\noindent
{\bf P. G. Hipes}
\par\noindent
C$^3$P-652c\ \ \ \ \ \ \ (Short Code: Hipes:89d)
\par
I will contrast the LU algorithm and a variant of the Gauss-Jordan
algorithm for solving general systems of equations in multicomputer
(distributed memory) 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, in some cases on a hypercube the calculation of the
multipliers requires the same {\it execution\/} time as the construction
of the LU decomposition.  Finally, on a hypercube the Gauss-Jordan
solution phase can be significantly faster than solving two triangular
systems as required using the LU decomposition.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf A back-prop controller for land and space
vehicles}
\par\noindent
{\bf A. Ho}
\par\noindent
C$^3$P-735\ \ \ \ \ \ \ (Short Code: Ho:89a)
\par
Path-planning for land vehicle navigation is usually formulated
as an optimization problem.  We reported here about results of 
a new approach to find a good path, if not optimal, by solving
a classification problem.  The land vehicle controller implements
a back-propagation model for classification.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf 3-D asteroids using parallel graphics
on NCUBE:  A testbed for evaluating controller algorithms}
\par\noindent
{\bf A. Ho, G. Fox, S. Snyder, D. Chu and T. Mylner}
\par\noindent
C$^3$P-681b\ \ \ \ \ \ \ (Short Code: Ho:89b)
\par
We have implemented on NCUBE a 3-D Asteroids video game system.  The system
functions as a testbed for evaluating intelligent controller algorithms
within a simulated space battle framework.  The Asteroids features battle
of spacecrafts in a 3-D toroidal space with inert meteorites of various
sizes. It supports multi-players and mixed communication protocols.  The
game can be played either in interactive or batch mode.  In interactive
mode a player can maneuver a spacecraft by keyboard or graphics tablet
control like a regular pc-based video game.  3-D 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 objectives,
game rules, and spacecraft controllers.  The flexibility of module
substitution allows fast prototyping of different controller strategies
and algorithms which are constrained by various game rules.  The system
also allows algorithms that run on distinct subcubes of a hypercube to
compete with one another.}

\bigskip\starline\bigskip
\vbox{\par\noindent
{\bf Transparencies} from a talk by A. Ho {\it et al.}, entitled ``3-D
Asteroids using Parallel Graphics on NCUBE'',  presented at the Fourth
Conference on Hypercubes, Concurrent Computers and Applications, Santa Clara,
March 1989.  C$^3$P-755 (Short Code: Ho:89c)}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Parallel neural net path-planner on
hypercube and transputer}
\par\noindent
{\bf A. W. Ho and G. C. Fox}
\par\noindent
C$^3$P-848\ \ \ \ \ \ \ (Short Code: Ho:89d)
\par
The task of finding a ``good'' path is of prime importance to any
automated vehicle navigation controller.  This task has been formulated
as problems in computational geometry, which is commonly reduced to a
graph search problem.  We report here the preliminary results of a new
approach that finds a ``good'', if not optimal, path dynamically and in
real-time by casting the task as a classification problem [Ho:89a].  The
path-planner implements a back-propagation model for classification.
The multi-scale representational strategy used for mapping the problem
domain onto the input space of the back-propagation model ensures the
applicability of the trained network to instances of the problem, which
differ in the distribution of obstacles and the size of the problem
domain.  Software simulations based on the parallel computer EXPRESS
operating system run, without modification of code, in Transputer-based
systems as well as hypercube concurrent processor, with satisfactory
efficiency.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Spacecraft sequencing on the Hypercube
concurrent processor}
\par\noindent
{\bf J. C. Horvath and R. C. Cole}
\par\noindent
C$^3$P-756\ \ \ \ \ \ \ (Short Code: Horvath:89a)
\par
The activity of planetary spacecraft is controlled with ``sequences''
of commands broadcast across space by the antennas of the deep space
network.  A spacecraft user (e.g., the scientist in charge of an
instrument) specifies spacecraft activities at a relatively high level.
The process of ``sequence generation'' takes these high-level activities
and generates a command sequence at a low-enough level so that the
spacecraft will be able to act on it while not doing itself any harm.
The software that performs this expansion and verification for JPL flight
projects, SEQGEN, runs on the Univax 1100 series of computers.  We rewrote
a small but representative portion of the expander section of SEQGEN for
the JPL/Caltech Mark II hypercube concurrent processor.  Speedups of 1.9
on two nodes (93\% efficiency) and of 3.1 on four nodes (78\% efficiency)
have been achieved in a prototype.  We describe this prototype and the
ongoing design of a parallel sequencing and verification system.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Using Centaur on Express systems}
\par\noindent
{\bf A. Kolawa}
\par\noindent
C$^3$P-825\ \ \ \ \ \ \ (Short Code: Kolawa:89a)
\par
We implement the Centaur operating system within the {\it Express\/}
environment providing both loosely synchronous and asynchronous
communication modes.  This allows Mark~III Centaur applications to run
on the broad range of parallel machines supporting {\it Express\/}.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf The MOOS II operating system and dynamic
load balancing}
\par\noindent
{\bf J. Koller}
\par\noindent
C$^3$P-730\ \ \ \ \ \ \ (Short Code: Koller:89a)
\par
MOOS II is a compact but comprehensive operating system now
available on the iPSC/1 at Caltech.  We discuss the features
of MOOS II that make it suitable for dynamic load balancing
experiments, and compare it to other distributed operating
systems currently available.  We describe a simple general 
purpose dynamic load balancer now running on the iPSC/1 and
discuss its limitations.  The applicability of the lessons 
learned to later generation machines is addressed.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Physical optimization and load balancing
algorithms}
\par\noindent
{\bf J. Koller, G. C. Fox, W. Furmanski and P. Simic}
\par\noindent
C$^3$P-731\ \ \ \ \ \ \ (Short Code: Koller:89b)
\par
We describe our experiences with a class of optimization
algorithms based on analogies with physical systems, including
simulated annealing and neural nets.  We discuss what they have
in common and their success in treating optimization problems
in parallel processing.}

\bigskip\starline\bigskip
\vbox{\par\noindent
{\bf Transparencies} from talk by J. Koller, entitled ``Dynamic load balancing
algorithms for MOOS'', presented at JTF Concurrent Processing Applications
Coordination Meeting, March 1989.  C$^3$P-742.3 (Short Code: koller:89c)}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Centaur:  A mixed
synchronous/asynchronous communication protocol for the Mark~III
hypercube}
\par\noindent
{\bf R. A. Lee and C. E. Goodhart}
\par\noindent
C$^3$P-774\ \ \ \ \ \ \ (Short Code: Lee:89a)
\par
We describe a new message passing system, CENTAUR, which combines a
general purpose asynchronous system with a more specialized but higher
performance loosely synchronous crystalline protocol.  This has been
used to run efficiently parallel tracking, and other loosely synchronous
algorithms, within a general event-driven formalism.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Concurrent Image Processing
Executive (CIPE)}
\par\noindent
{\bf M. Lee, S. Groom, A. Mazer, and W. Williams}
\par\noindent
C$^3$P-810\ \ \ \ \ \ \ (Short Code: Lee:89b)
\par
This paper presents a concurrent image processing executive (CIPE)
implemented on a JPL/Caltech Mark~IIIfp hypercube.  The major goals of
CIPE are to provide an architecture independent interactive image
processing environment for end users and an easy-to-use programming
environment for image processing algorithm/program developers.  The
design objective of CIPE is to utilize the architectural characteristics
of a Mark~IIIfp hypercube system while maintaining the architecture
independent overall executive structure.  CIPE achieves the objective
via three interconnected components: host monitor, user interface, and
hypercube monitor where the architecture dependency is isolated in the
hypercube monitor.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Application of hypercube computers to
plasma particle-in-cell simulation codes}
\par\noindent
{\bf P. C. Liewer, B. A. Zimmerman, V. K. Decyk and J. M. Dawson}
\par\noindent
C$^3$P-717\ \ \ \ \ \ \ (Short Code: Liewer:89a)
\par
Both one-dimensional electrostatic and electromagnetic plasma particle-in-cells
codes have been implemented on the Caltech/JPL Mark IIIfp Hypercube, a parallel
computer with distributed memory.  The codes were implemented using the General
Concurrent Particle-in-Cell Algorithm [Liewer and Decyk, 1989].  Performance
results for the parallel electrostatic code, a well-benchmarked code, are given
and compared with other supercomputers.  The performance of the 64 processor
Mark IIIfp on the most computationally intensive portion of the code exceeds
that of a 1 processor CRAY XMP.  The electromagnetic particle code, to be used
to study electron heating in the Earth's bow shock, is briefly described.}

\bigskip\starline\bigskip
\vbox{\par\noindent
{\bf Transparencies} from a talk by P. C. Liewer {\it et al.},
entitled ``A general concurrent algorithm for plasma particle-in-cell
simulations'', presented at the Fourth Conference on Hypercubes, Concurrent
Computers and Applications, Santa Clara, March 1989.  C$^3$P-758 (Short
Code: Liewer:89b)}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf A general concurrent algorithm for
plasma particle-in-cell simulation codes}
\par\noindent
{\bf P. C. Liewer and V. K. Decyk}
\par\noindent
C$^3$P-649b\ \ \ \ \ \ \ (Short Code: Liewer:89c)
\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 of 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 to sub-domain and is responsible for updating the particles i
its sub-domain.  This algorithm has led to a very efficient parallel
implementation of a well-benchmarked 1-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 to 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 Concurrent computations of invariant manifolds}
\par\noindent
{\bf J. Lorenz and E. F. Van de Velde}
\par\noindent
C$^3$P-759\ \ \ \ \ \ \ (Short Code: Lorenz:89a)
\par
It is a challenging computational problem to find manifolds $M$ which
are invariant under the flow of a dynamical system.  We consider the
special case where the system is partitioned in the form}
$$
\cases{d\theta /dt = f (\theta ,r) \cr
 dr/dt = g(\theta ,r)\cr}
$$
\par\noindent
and $\theta$ is a vector of periodic variables.  Then we ask for an attracting
invariant manifold $M$ parametrized by $\theta$.  A typical example is given by
two coupled oscillators where one asks for an invariant torus in the four
dimensional state space.
\par
There are two different analytical approaches, both leading to interesting
numerical problems.  The first approach uses partial differential equations,
the second approach is based on the Hadamard graph transform.  We discuss
the numerical analysis aspects of these two approaches, both of which lend
themselves to concurrent computations.
\par
Each step of the Hadamard graph transform requires the solution of a large
number of ordinary boundary value problems.  These can be solved independently
of each other, but communications are necessary to compute a new global
interpolant after each step of the graph transform. The new interpolant
gives an improved approximation to the invariant manifold.
\par
The partial differential equations approach leads to somewhat more standard
problems:  After discretization and linearization one has to solve large
linear systems; these have a special sparsity structure.  Concurrency is
exploited in the solution of these systems.
\par
For an efficient treatment of the corresponding systems on sequential
machines we refer to Ref.~3.

\bigskip\starline\bigskip
\vbox{\par\noindent
{\bf Transparencies} from a talk by G. Lyzenga {\it et al.}, entitled ``Parallel
processing of finite element simulations:  Hypercubes and related multiprocessors'',
presented at the Fourth Conference on Hypercubes, Concurrent Computers and
Applications, Santa Clara, March 1989.  C$^3$P-757 (Short Code: Lyzenga:89a)}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Large-step Markov chains for the traveling 
salesman problem}
\par\noindent
{\bf O. Martin, S. W. Otto, and E. W. Felten}
\par\noindent
C$^3$P-836\ \ \ \ \ \ \ (Short Code:  Martin:89a)
\par
We propose and test a new class of Markov chain Monte Carlo search procedures 
for the TSP.  The Monte Carlo explores only locally optimal tours (e.g., 
3-opt) in the space of all possible tours.  It has the property of being able 
to make large, global changes to the tour, even at low temperatures, thus 
overcoming large barriers in tour space.  More generally, this approach leads 
to better algorithms for other optimization problems by putting deterministic 
local search techniques into stochastic algorithms.}
\par
For the local search, we devise a fast 3-opt which, within our Markov chain, 
has time complexity near linear in $N$ where $N$ is the number of cities in 
the TSP.  The 3-opt tours are sampled by using an accept/reject procedure on a 
large step taking one 3-opt tour into another.  The large step consists of a 
special kind of 4-change followed by 3-opt minimization.  We test this 
algorithm on a number of TSP instances.  The power of the method is 
illustrated by solving the LIN318 problem, and the AT\&T 532 city problem to 
which the exact solutions are known.

\bigskip\starline\bigskip
\vbox{\par\noindent
{\bf Transparencies} from a talk by A. S. Mazer and G. T. Cooper, entitled
``User Interfaces in Cipe''.  C$^3$P-760 (Short Code: Mazer:89a)}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf A general framework for complex time-driven
simulations on Hypercubes}
\par\noindent
{\bf D. L. Meier, K. C. Cloud, J. C. Horvath, L. D. Allan, W. H. Hammond and
H. A. Maxfield}
\par\noindent
C$^3$P-761\ \ \ \ \ \ \ (Short Code: Meier:89a)
\par
We describe a general framework for building and running complex time-driven
simulations with several levels of concurrency.  The framework has been
implemented on the Caltech/JPL Mark IIIfp hypercube using the Centaur
communications protocol.  Our framework allows the programmer to break the
hypercube up into one or more subcubes of arbitrary size (task parallelism).
Each subcube runs a separate application using data parallelism and
synchronous communications internal to the subcube.  Communications between
subcubes are performed with asynchronous messages.  Subcubes can each define
their own parameters and commands which drive their particular application.
These are collected and organized by the CP in order that the entire
simulation can be driven from a single command-driven shell.  This system
allows several programmers to develop disjoint pieces of a large simulation
in parallel and to then integrate them with little effort.  Each programmer
is, of course, also able to take advantage of the separate data and I/O
processors on each hypercube node in order to overlap calculation and
communication (on-board parallelism) as well as the pipelined floating point
processor on each node (pipelined processor parallelism).}
\par
We show, as an example of the framework, a large space defense simulation.
Functions (sensing, tracking, etc.) each comprise a subcube; functions are
collected into defense platforms (satellites); and many platforms comprise
the defense architecture.  Software in the CP uses simple input to determine
the node allocation to each function based on the desired defense architecture
and number of platforms simulated in the hypercube.  This allows many
different architectures to be simulated.  The set of simulated platforms,
the results, and the messages between them are shown on color graphics
displays.  The methods used herein can be generalized to other simulations
of a similar nature in a straightforward manner.

\bigskip\starline\bigskip
\vbox{\par\noindent
{\bf Transparencies} from a talk by D. L. Meier {\it et al.}, entitled ``A
general framework for complex time-driven simulations on
hypercubes''.  C$^3$P-762 (Short Code: Meier:89b)}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Benchmarking advanced architecture computers}
\par\noindent
{\bf P. Messina, A. Alagar, C. F. Baillie, E. Felten, P. G. Hipes, A. Kamrath,
R. H. Leary, W. Pfeiffer, J. Rogers, D. W. Walker and R. D. Williams}
\par\noindent
C$^3$P-712\ \ \ \ \ \ \ (Short Code: Messina:89a)
\par
Recently a number of advanced architecture machines have become
commercially available.  These new machines promise better cost-performance
than 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 the methodology and results of a pilot
study of the performance of a broad range of advanced architecture computers
using a number of complete scientific application programs.  The computers
evaluated include (1) distributed-memory machines such as the NCUBE, Intel
and Jet Propulsion Laboratory (JPL)/Caltech hypercubes, (2) shared-memory
bus architecture machines such as the Sequent Balance 21000 and the Alliant
FX/8, (3) very long instruction word machines such as the Cydrome Cydra-5,
(4) ``traditional'' supercomputers such as the CRAY X-MP and CRAY-2 and
(5) SIMD machines such as the Connection Machine.  Seven application codes
from a number of scientific disciplines have been used in the study, 
although not all the codes were run on every machine.  The methodology and
guidelines for establishing a standard set of benchmark programs for advanced
architecture computers are discussed.}

\bigskip\starline\bigskip
\vbox{\par\noindent
{\bf Transparencies} from talk by P. Messina, entitled ``The Caltech Concurrent
Supercomputing Facilities'', presented at JTF Concurrent Processing Applications
Coordination Meeting, March 1989.  C$^3$P-742.4 (Short Code: Messina:89b)}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Designing neural networks using genetic
algorithms}
\par\noindent
{\bf G. F. Miller, P. M. Todd, S. U. Hegde}
\par\noindent
C$^3$P-797\ \ \ \ \ \ \ (Short Code: Miller:89a)
\par
We present a genetic algorithm method that evolves neural network architectures
for specific tasks.  Each network architecture is represented as a connection
constraint matrix mapped directly into a bit-string genotype.  Modified standard
genetic operators act on populations of these genotypes to produce network
architectures with higher fitnesses over successive generations.  Architecture
fitness is assessed by training particular network instantiations and recording
their final performance error.  Three applications of this method to simple 
network mapping tasks are discussed.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf On genetic crossover operators for relative
order preservation}
\par\noindent
{\bf P. Moscato}
\par\noindent
C$^3$P-778\ \ \ \ \ \ \ (Short Code: Moscato:89a)
\par
Genetic Algorithms is a population-based optimization strategy that has been
successfully applied to many {\it real world} and {\it academic} problems.
The crossover operator plays a very important role in genetic algorithms
since it is the element that generates the exchange of information between
individuals during the search.  This paper shows how the careful design of
these crossover operators should be essential to avoid loss of information.
This is shown graphically using the Travelling Salesman Problem as an example
of one application of genetic algorithms where the relative order preservation
of the structure of the configurations is extremely important when the diversity
of the individuals is small.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf t-expansion and the Mathieu equation}
\par\noindent
{\bf P. Moscato and C. Riveros}
\par\noindent
C$^3$P-782\ \ \ \ \ \ \ (Short Code: Moscato:89b)
\par
The t-expansion, a nonperturbative analytic method for calculating the
ground-state expectation values of arbitrary operators of the Hamiltonian,
is applied to the Mathieu equation.  Confirming previous results in other
systems, a t-expansion up to order $t^2$ is sufficient to recover the behavior
of the exact solution.  A very good performance is observed when a variational
wave function of the form $| \psi_0 \geq \exp (\gamma V(x)/2)$ is used in the
calculation of connected moments of the Hamiltonian.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Stochastic vs. deterministic update in simulated
annealing}
\par\noindent
{\bf P. Moscato and J. F. Fontanari}
\par\noindent
C$^3$P-789\ \ \ \ \ \ \ (Short Code: Moscato:89c)
\par
We propose an algorithm which has several of the characteristics of simulated
annealing but whose update is deterministic.  The results of the comparison
between the two algorithms indicate that the stochastic hopping over barriers
in simulated annealing does not play a major role in the search of the near
optimal minima.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf A competitive-cooperative approach to complex
combinatorial search}
\par\noindent
{\bf M. Norman and P. Moscato}
\par\noindent
C$^3$P-790\ \ \ \ \ \ \ (Short Code: Moscato:89d)
\par
Combinatorial optimization problems confront us with the problem of searching
in a huge configuration space.  Associated with each of these configurations is
the value of a utility function and the optimization task generally consist of
finding the configuration which has either the lowest or the highest cost of
all.  Among the most difficult of these problems are those which belong to the
NP-complete class for which, it is conjectured, there does not exist a
polynomial-time algorithm that can give optimal solutions.  We have designed
a Competitive-Cooperative Search to deal with these problems.  A number of
distinguishable individuals, arranged in a certain topology, compete and
cooperate with each other during the search.  The method uses techniques from
Simulated Annealing and Genetic Algorithms and is inspired by biological
evolution analogies.  Its performance is being tested on the Lin-Kernighan
318-cities Travelling Salesperson Problem, for which the optimal tour is known,
among the $O(10^{655})$ configurations.  The approach shows natural parallelism
since competition and cooperation between individuals enhances its performance.
Owing to the surprisingly good results obtained during the testing, and the
generality of the approach, it promises excellent results in other scientific
and technological optimization problems.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf On evolution, search, optimization,
genetic algorithms and martial arts:  Towards memetic algorithms}
\par\noindent
{\bf P. Moscato}
\par\noindent
C$^3$P-826\ \ \ \ \ \ \ (Short Code: Moscato:89e)
\par
We review a variety of novel optimization algorithms involving
competition and cooperation strategies.  This includes generalized and
genetic annealing methods, i.e., physical optimization methods.  We
discuss the traveling salesman, as well as a family of problems due to
Kauffman.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Diffraction-limited imaging II.\ optical 
aperture-synthesis imaging of two binary stars}
\par\noindent
{\bf T. Nakajima, S. R. Kulkarni, P. W. Gorham, A. M. Ghez, G. Neugebauer, J. 
B. Oke, T. A. Prince, and A. C. S. Readhead}
\par\noindent
C$^3$P-805\ \ \ \ \ \ \ (Short Code:  Nakajima:89a)
\par
We have used the technique of nonredundant masking at the Hale 5~m telescope 
and radio VLBI imaging software to make optical aperture-synthesis maps of two 
binary stars, $\beta$ Corona Borealis and $\sigma$ Herculis.  The dynamic 
range of the map of $\beta$ CrB, a binary star with a separation of 230 
milliarcsec, is about 50:1.  For $\sigma$ Her, we find a separation of 70 
milliarcsec and the dynamic range of our image is 30:1.  These maps 
demonstrate the potential of the nonredundant masking technique for 
diffraction-limited imaging of astronomical objects with high dynamic range.  
We find that the optimal integration time for measuring the closure phase is 
longer than that for measuring the fringe amplitude.  There is not a close 
relationship between amplitude errors and phase errors, as is found in radio 
astronomy, and amplitude self-calibration is less effective at optical 
wavelengths than at radio wavelengths.  The primary-beam sensitivity 
correction made in radio interferometry is not necessary for optical 
interferometry.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Analysis of text using a neural network:  A
hypercube implementation}
\par\noindent
{\bf D. S. Newhall and J. C. Horvath}
\par\noindent
C$^3$P-770\ \ \ \ \ \ \ (Short Code: Newhall:89a)
\par
This paper presents an implementation of a back-propagation neural network
simulation on the Caltech/JPL Mark III hypercube concurrent processor.  A
back-propagation network comprises several layers of simple processing units
connected together in a feed-forward pattern.  Every connection has a
certain strength, or ``weight''.  The algorithm used to ``learn'' a problem
changes these weights in such a way that when patterns are presented to
the network, the output state reached by the network moves toward a ``correct''
state for each pattern.  The network used in this study is designed for
pattern recognition in text.  The problem used for the efficiency and
generalization studies was that of recognition of the names of the ten
digits written in text.  In order to test how well the network learned
the task, it was presented with patterns it had not yet encountered, such
as the names of the digits with various spelling errors.  After a sufficient
number of training examples, the network was consistently able to categorize
these novel patterns with at least 80\% accuracy.  For this problem, the
efficiency of the algorithm's use of the parallel resources was on average
95\% for 8 nodes, dropping to just under 70\% for 32 nodes.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf The BBN Butterfly used to simulate a 
molecular liquid}
\par\noindent
{\bf G. S. Pawley and C. F. Baillie}
\par\noindent
C$^3$P-529\ \ \ \ \ \ \ (Short Code:  Pawley:89a)
\par
The problems involved in simulating a liquid on a MIMD and on a SIMD computer 
are analyzed and compared, with specific reference to the BBN Butterfly and the 
ICL DAP respectively.  A description of the Butterfly is given and the MIMD 
simulation on it is analyzed in detail.  Aspects of the system software of 
relevance to this simulation are presented and the programming practicalities 
are discussed.  Timings are given for the molecular dynamics liquid $SF_6$ 
simulation on the Butterfly, and a breakdown is given for the performance 
factors for this parallel computer.  The performance on this complete problem 
using a 44-processor machine was in excess of 0.5~Mflops per processor.}

\bigskip\starline\bigskip
\vbox{\par\noindent
{\bf Transparencies} from a talk by T. Prince, entitled ``Millisecond
and Megaflops'', presented at the Physics Research Colloquium,
California Institute of Technology, November 2, 1989.  C$^3$P-865 (Short 
Code: Prince:89a)}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf A Nonconvex Cost Optimization
Approach to Tracking Multiple Targets}
\par\noindent
{\bf K. Rose, E. Gurewitz, and G. Fox}
\par\noindent
C$^3$P-853\ \ \ \ \ \ \ (Short Code:  Rose:89a)
\par
The problem of tracking multiple targets in the presence of displacement
noise and clutter is formulated as a nonconvex optimization problem.
The form of the suggested cost function is shown to be suitable for the
Graduated Non-Convexity algorithm, which can be viewed as deterministic
annealing.  The method is first derived for the two-dimensional
(spatial/temporal) case, and then generalized to the multi-dimensional
case.  The complexity grows linearly with the number of targets.
Computer simulations show the performance with crossing trajectories.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Using parallel computers for very large N-body
simulations:  Shell formation using 180K particles}
\par\noindent
{\bf J. Salmon, P. Quinn and M. Warren}
\par\noindent
C$^3$P-780\ \ \ \ \ \ \ (Short Code: Salmon:89a)
\par
We have used a parallel version of the Barnes-Hut C treecode running on a
parallel supercomputer (a 512 node NCUBE) at the Caltech Concurrent Computing
Project to follow the evolution of systems with very large numbers of particles
($N > 180,000$).  Many important problems in astrophysics demand large $N$, and in
particular we have studied the fully self-consistent formation of stellar shells
around an elliptical parent galaxy via the merger with another elliptical of
one tenth its mass.  The final system shows a spread in shell radii similar to
that in observed shell galaxies.  Major changes in the structure and dynamics
of the primary have resulted from the merger.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Using parallel computers for very large 
N-body simulations:  shell formation using 180K particles}
\par\noindent
{\bf J. Salmon, P. Quinn, and M. Warren}
\par\noindent
C$^3$P-780b\ \ \ \ \ \ \ (Short Code:  Salmon:89b)
\par
We have used a parallel version of the Barnes-Hut C tree code running on a 
parallel supercomputer (a 512 node NCUBE) at the Caltech Concurrent Computing 
Project to follow the evolution of systems with very large numbers of 
particles ($N > 180,000$).  Many important problems in astrophysics demand 
large $N$ and in particular we have studied the fully self-consistent formation 
of stellar shells around an elliptical parent galaxy via the merger with 
another elliptical of one-tenth its mass.  The final system shows a spread in 
shell radii similar to that in observed shell galaxies.  Major changes in the 
structure and dynamics of the primary have resulted from the merger.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf The design of a run-time system integrable
with programming environments for distributed memory machines}
\par\noindent
{\bf J. Saltz, R. Mirchandaney, G. Fox and D. M. Nicol}
\par\noindent
C$^3$P-700\ \ \ \ \ \ \ (Short Code: Saltz:89a)
\par
There exists substantial data level parallelism in scientific problems.  For
many of these problems, the performance that can be obtained from the current
generation of distributed memory machines is in the supercomputer range.  The
development of new distributed memory machines with even more impressive
performance is at hand.  It is generally accepted, however, that any large
scale exploitation of the power of the new generation of machines requires
the development of programming environments that allow software development
to progress at a reasonable rate.  We are currently designing such a
programming environment at Yale.}

\bigskip\starline\bigskip
\vbox{\par\noindent
{\bf Transparencies} from talk by P. Simic, entitled ``Statistical
mechanics of computation:  applications to optimization and learning'',
presented at JTF Concurrent Processing Applications Coordination Meeting,
March 1989.  C$^3$P-742.5 (Short Code: Simic:89a)}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Statistical Mechanics as the Underlying
Theory of ``Elastic'' and ``Neural'' Optimizers}
\par\noindent
{\bf P. D. Simic}
\par\noindent
C$^3$P-787\ \ \ \ \ \ \ (Short Code: Simic:89b)
\par
There is an interesting connection between two recently popular methods for
solving hard computational problems, the ``neural'' approach of Hopfield and
Tank, and the elastic-net method of Durbin and Willshaw.  They both have an
underlying statistical-mechanics foundation and can be derived as the leading
approximation to the thermodynamic free energy of related physical models.  The
apparent difference in form of the two algorithms comes from different handling
of constraints when evaluating the thermodynamic partition function.  If all
the constraints are enforced ``softly'', the leading approximation to the
thermodynamic free energy is just the neural-network Lyapunov function.  If, on
the other hand, half of the constraints are enforced ``strongly'', the leading
approximation to the thermodynamic free energy is the elastic-net Lyapunov
function.  Our results suggest a natural and systematic way to generalize the
elastic-net method to a large class of hard computational problems.  We derive
a new algorithm of the elastic-net type based on statistical mechanics.  It has
the ``positive'' ingredients of the elastic-net method, yet, it doesn't have an
intrinsic problem (discussed in this paper) of the original algorithm.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Synthetic aperture radar processing using 
the hypercube concurrent architecture}
\par\noindent
{\bf D. Simoni, B. Zimmermann, J. Patterson, C. Wu, and J. Peterson}
\par\noindent
C$^3$P-775\ \ \ \ \ \ \ (Short Code:  Simoni:89a)
\par
A Synthetic Aperture Radar (SAR) is a spaceborne or airborne radar that allows 
high resolution images of the ground below to be obtained by the use of 
transmission and reception of electromagnetic radiation.  Current trends in 
the field point to the production of real-time SAR imagery.  The production of 
an image normally requires a number of digital signal processing steps.  
Existing techniques make use of specialized hardware devices or general 
purpose computers attached to array processors to perform these steps 
sequentially.  The considerable amount of processing time that is spent 
storing and retrieving the intermediate results between each step in the 
processing sequence creates a bottleneck for achieving fast system 
throughput.}
\par
We show that the Caltech/JPL Mark~IIIfp Hypercube is a cost-effective solution 
to this problem.  The Mark~IIIfp's architecture combines very high-speed 
computational power and data routing with the flexibility to handle different 
SAR data processing requirements without the need for changes in hardware.  We 
use a task decomposition approach by which the required processing steps are 
mapped onto subcubes within the Hypercube.  The processing steps are executed 
in parallel and produce an ``assembly line''-like stream of data, thus 
eliminating the need for intermediate storage.  This feature alone makes the 
Hypercube an attractive alternative to conventional methods.  Data are 
transferred to and from the Mark~IIIfp through Concurrent I/O nodes that allow 
several nodes within each subcube to concurrently access and work on different 
pieces of an images.  Furthermore, since each node in the Mark~IIIfp contains 
both a data processor and a communications processor, data transfers between 
subcubes take place without interrupting the calculations within the 
application.
\par
We present a discussion of the processing requirements using this approach, 
including performance comparisons between the technique described here and 
existing systems.  An analysis of communication versus computation loads is 
also presented.  Finally, we discuss possible extensions to the SAR processing 
system which include the introduction of specialized digital signal processing 
boards into the Hypercube topology, as well as the high-speed, dynamic routing 
Hyperswitch communications network.

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Concurrent DASSL:  structure, application
and performance}
\par\noindent
{\bf A. Skjellum, M. Morari, S. Mattisson and L. Peterson}
\par\noindent
C$^3$P-733\ \ \ \ \ \ \ (Short Code: Skjellum:89a)
\par
We investigate solution of low-index differential-algebraic (DAE) systems in
terms of building blocks: residuals (model evaluation), Jacobian formation,
integration overheads, LU factorization, and forward- (back-) substitution.
Their relative costs impact overall performance; individual efficiencies depend
on multicomputer granularity.  Our simulation code, Concurrent DASSL, is based
on Petzold's DASSL, a recognized sequential code for DAE systems.  Presently,
we are poised to investigate achievable concurrent performance of sequential
numerics for a class of dynamic simulation applications.}
\par
To facilitate an efficient, general-purpose code, we have developed a new
communications layer, Zipcode.  It provides object-oriented abstraction of
process lists, allowing several logical two-dimensional process grids to be
simultaneously supported.  Grids provide the underlying communications
framework for the building-block operations.  Data redistributions between
building-block operations can consequently be described as grid-to-grid
conversions within this paradigm.  We indicate the essentials of Zipcode,
its relation to the underlying operating system, the Reactive Kernel/Cosmic
Environment developed at Caltech, as well as software overhead issues.
\par
The lower granularity of second-generation hardware is key to Concurrent
DASSL's efficiency for a variety of simulation applications.  We comment
on speedup, again with a view towards the building-block operations.  We
indicate, qualitatively, expected performance for simulation problems that
are naturally medium-grain, such as dynamic flowsheet simulation (an important
chemical engineering application).  We also outline the interrelation of our
work to Van de Velde's, whose full and sparse linear algebra libraries are
incorporated into our system.
\par
We describe the need for a supplementary software interface for automatic
creation of the distributed simulation database.  We plan to couple Concurrent
DASSL with Mattisson and Peterson's CONCISE waveform-relaxation simulator,
providing a comprehensive simulation tool.

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf LU Factorization of Sparse,
Unsymmetric Jacobian Matrices on Multicomputers: Experience, Strategies,
Performance}
\par\noindent
{\bf Anthony Skjellum, Alvin P. Leung, and Manfred Morari}
\par\noindent
C$^3$P-839\ \ \ \ \ \ \ (Short Code:  Skjellum:89b)
\par
Efficient sparse linear algebra {\it cannot\/} be achieved as a
straightforward extension of the dense case, even for concurrent
implementations.  This paper details a new, general-purpose unsymmetric
sparse LU factorization code built on the philosophy of Harwell's
$MA28$, with variations.  We apply this code in the framework of
Jacobian-matrix factorizations, arising from Newton iterations in the
solution of nonlinear systems of equations.  Serious attention has been
paid to the data-structure requirements, complexity issues and
communication features of the algorithm.  Key results include reduced
communication pivoting for both the ``analyze'' A-mode and repeated
B-mode factorizations, and effective general-purpose data distributions
useful incrementally to trade-off process-column load balance in
factorization against triangular solve performance.  Future planned
efforts are cited in conclusion.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf High performance of cellular
automata fluids on the Connection Machine}
\par\noindent
{\bf Z.-Y. Su and G. C. Fox}
\par\noindent
C$^3$P-811\ \ \ \ \ \ \ (Short Code: Su:89a)
\par
We compare the Connection Machine and SUN for cellular automata
simulations.  We show how different strategies can dramatically impact
the performance.  Numerical results are presented for three different
applications.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Three dimensional geometry from image
processing on the JPL/CIT Hypercube}
\par\noindent
{\bf  S. P. Synnott, J. E. Riedel, J. A. Stuve, P. Halamek and W. J. Lehr}
\par\noindent
C$^3$P-763\ \ \ \ \ \ \ (Short Code: Synnott:89a)
\par
We describe an approach to estimating on the Hypercube the three dimensional
physical properties of planetary objects from the two dimensional images
returned from NASA's planetary missions, and from the Hubble Space Telescope.
The Hypercube is used in a simple parallel mode with each node assigned
calculations for a subset of the image pixels, with no internodal communication
required.  The estimation uses an iterative linear least squares approach
where the data are the pixel brightness values in the images, and partials of
theoretical models of these brightness values are computed for use in a square
root formulation of the normal equations.  The underlying three dimensional
model of the object consists of a triaxial ellipsoid overlaid with a spherical
harmonic expansion to describe low to mid-spatial frequency topographic or
surface composition variations.  Partials can be calculated for the parameters
describing overall body shape, orientation, topography and reflection
characteristics, as well as for camera pointing.  We discuss some of the
possible applications of the program, describe the essentials of the technical
approach and summarize our progress and results to date.}

\bigskip\starline\bigskip
\vbox{\par\noindent
{\bf Transparencies} from a talk by S. P. Synnott {\it et al.}, entitled
``Three-dimensional planetary object modeling and estimation on the
JPL/CIT Mark-III Hypercube''.  C$^3$P-764 (Short Code: Synnott:89b}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Parallel joins on the Mark III Hypercube}
\par\noindent
{\bf E. Upchurch, D. Curkendall, K. Cloud, A. Loomis and J. Geiselman}
\par\noindent
C$^3$P-765\ \ \ \ \ \ \ (Short Code: Upchurch:89a)
\par
A large body of work on parallel joins exists but relatively little
addresses hypercube architectures and still less reports results for
actual implementations on real hypercube machines.  This paper presents
and analyzes several parallel join algorithms implemented on the
Mark III Hypercube at JPL.  Implementation code is parametrized to
allow investigation of a wide range of join performance factors under
a synthetic database workload.  Results show the critical need to
balance:  communications, local join processing, relation size and
subcube dimension.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Experiments with multicomputers of
LU-decomposition}
\par\noindent
{\bf E. Van de Velde}
\par\noindent
C$^3$P-725\ \ \ \ \ \ \ (Short Code: Velde:89a)
\par
We present a concurrent LU-decomposition algorithm based on implicit
pivoting of both rows and columns.  Most pivoting strategies are thus
easily incorporated.  This algorithm is implemented such that it is,
to a large extent, independent of the data distribution.}
\par
With this program, we study the performance of concurrent LU-decomposition
as a function of data distribution and pivoting strategy.  We show that
LU-decomposition with some pivoting strategies is both faster and numerically
more stable than LU-decomposition without pivoting.  Experimental evidence on
the Ametek 2010 shows that, for performance considerations, pivoting is
equivalent to randomizing the data distribution.

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Multicomputer matrix computations:  Theory
and practice}
\par\noindent
{\bf E. F. Van de Velde}
\par\noindent
{C$^3$P-766}\ \ \ \ \ \ \ (Short Code: Velde:89b)
\par
We explore a strategy for concurrent program development.  It is
significant that just two basic techniques, data distribution and
recursive doubling, are sufficient for the development of many
linear algebra computations.}
\par
When constructing a concurrent library, it is counterproductive
to develop ``optimal algorithms'' for each component.  The problem
is that optimality is not stable under program composition.  A user
program based on individually optimized components may be very
inefficient due to interfaces between components.  Invariably, these
interfaces must perform some type of data redistribution.  We implement
our algorithms such that their correctness is, to a large extent,
independent of data distribution.  This allows the user to choose the
most convenient and/or the most efficient distribution for a particular
application and/or hardware.  Another benefit is that the need for
interfaces is minimized.
\par
We applied the above ideas in the development of a multicomputer
library for linear algebra computations.  The library includes most
basic operations and a representative selection of advanced algorithms
for full and sparse matrices.  We present some timing results from the
Ametek multicomputer.

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf The performance of a distributed
combat simulation with the time warp operating system}
\par\noindent
{\bf F. Wieland, L. Hawley, A. Feinberg, M. DiLoreto, L. Blume,
J. Ruffles, P. Reiher, B. Beckman, P. Hontalas, S. Bellenot and D. Jefferson}
\par\noindent
C$^3$P-798\ \ \ \ \ \ \ (Short Code: Wieland:89a)
\par
This paper analyzes the performance of a discrete-event combat simulation
executed on a parallel processor under control of the Time Warp Operating
System.  Time Warp is in a class of distributed simulation methods called
{\it optimistic methods} which have proven to be useful over a wide range
of simulations.  The combat simulation used for this performance study,
called STB88, is a division-corps model incorporating a number of different
types of computations.  The speedup for three versions of this model on the
Caltech/JPL Mark III Hypercube and the BBN Butterfly parallel processors was
measured relative to an efficient sequential execution of the same model on
the same hardware.  The results indicate that STB88 version 1 achieves a 
speedup of 28.6 on 60 Mark III processors, while STB88 version 2 achieves
a speedup of 36.8 on 100 Butterfly processors.  Version 3 of STB88 achieved
a speedup of 38.5 on 128 Mark III processors.  The versions differed only in
their interface to Time Warp.  On the Butterfly, the sequential execution
execution completed in 2 hours, while the 100 processor execution completed
in 3.2 minutes.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Distributed irregular finite elements}
\par\noindent
{\bf R. Williams and R. Glowinski}
\par\noindent
C$^3$P-715\ \ \ \ \ \ \ (Short Code: Williams:89a)
\par
DIME is a programming environment for manipulation of irregular triangular
meshes with a distributed memory machine.  We have added a software layer
DIMEFEM which manipulates Finite Element representations of functions and
allows the stating and solving of variational statements.  An application of
DIMEFEM is an incompressible Navier-Stokes solver with a three-stage implicit
time step, using quasi-optimally preconditioned conjugate gradient for the
Stokes solver and Newtons' method in the space of quadratic Lagrangian
Elements for the nonlinear solver.  The codes run on NCUBE hypercubes and
transputer machines.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Supersonic fluid flow in parallel with
an unstructured mesh}
\par\noindent
{\bf R. D. Williams}
\par\noindent
C$^3$P-636b\ \ \ \ \ \ \ (Short Code: Williams:89b)
\par
An algorithm has been implemented 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 Distributed processing of an irregular
tetrahedral mesh}
\par\noindent
{\bf R. D. Williams and E. W. Felten}
\par\noindent
C$^3$P-793\ \ \ \ \ \ \ (Short Code: Williams:89c)
\par
A triangular or tetrahedral mesh is a flexible and general description of space,
and when combined with the Finite Element method can be used to simulate
nonlinear three dimensional continuum systems.  This note is a didactic proposal
for implementing such a mesh in arbitrary dimensions, using a distributed memory
parallel processor.  The mesh is the Delaunay triangulation, which is the dual of
the Voronoi tessellation of a set of nodes.  Message-passing parallel algorithms
are described for creation, refinement, and load balancing of such a mesh, and for
basic operations such as matrix-vector products and vector-vector products.  An
analysis of the memory requirements for various Finite Element schemes is given,
and a criterion is given for when refinement may be carried out in parallel.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Parallel computing}
\par\noindent
{\bf R. D. Williams, C. F. Baillie, G. C. Fox, A. Kolawa, P. Messina,
and D. Walker}
\par\noindent
C$^3$P-837\ \ \ \ \ \ \ (Short Code: Williams:89e)
\par
This tutorial describes how to use multicomputers in scientific
computation.  We give explicit examples using {\it Express\/} on
transputer and other systems.  The contents are:
\item{1.}Introduction to Parallel Processing
\item{2.}Programming with Cubix
\item{3.}{\it Express}
\item{4.}Communication Methods with Examples
\item{5.}Applications of Parallel Processing
\item{6.}Performance
\item{7.}Advanced Concepts}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Use of neural networks for path planning}
\par\noindent
{\bf Y.-F. Wong and G. C. Fox}
\par\noindent
C$^3$P-784\ \ \ \ \ \ \ (Short Code: Wong:89a)
\par
For some problems, it is natural to consider the solution as a path in the
space-time domain.  We are investigating using neural network for decision-making
when the information is spatially and temporally indexed.  Here, we consider an
optimal path problem where we have some vehicles in a two-dimensional space
navigating from starting positions to finishing positions, avoiding some
obstacles.  We will discuss neural network approach, parallel implementation
on the hypercube and multi-scale techniques.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Spacecraft activity planning in a
multiprocessor environment}
\par\noindent
{\bf E. B. Zamani, J. R. George, C. E. Collins, and B. A. Zimmerman}
\par\noindent
C$^3$P-744\ \ \ \ \ \ \ (Short Code: Zamani:89a)
\par
Spacecraft activity planning is the process whereby requests for spacecraft
time and resources from scientists are integrated into a feasible sequence.
Since the number of scientists' requests is usually too large for all of them
to be performed, some mechanism is necessary to resolve conflicts and specify
an optimum command sequence.  The development of a feasible sequence plan is
an expensive and labor-intensive process requiring many months of effort.
This paper will describe an environment, PLANNER, which supports interactive,
on-line activity planning by scientists augmented by automatic sequence
planning using a hypercube parallel processor.  In PLANNER, the spacecraft
components are modeled using an object-oriented programming methodology and
the C$^{++}$ language.  Activity sequences are entered, conflicts are detected,
and an activity display is generated giving a visual representation of the
state of the spacecraft along a timeline of the mission.  PLANNER, using
object-oriented techniques and the power of parallel processing, is a major
step toward the development of a rapid automated sequence plan.  Further,
PLANNER may provide a significant contribution in the research of autonomous
spacecraft, eventually moving the burden of planning to on-board systems not
constrained by the time delays of ground-based systems.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf An object-oriented environment for the
Caltech/JPL Mark III Hypercube}
\par\noindent
{\bf B. A. Zimmerman and G. A. Crichton}
\par\noindent
C$^3$P-767\ \ \ \ \ \ \ (Short Code: Zimmerman:89a)
\par
It has been said that ``object-oriented programming will be in the
80's and 90's what structured programming was in the 1970's''.  More
importantly, the paradigm represents a potentially promising methodology
to unifying the design of Operating Systems, Knowledge Based Systems,
Databases, and sophisticated User Interfaces.  We will describe an
object-oriented environment for the JPL Hypercube Project based on the
C++ language.  The environment provides C++ for three computer platforms:
Motorola M68020/M68882, Weitek XL, Motorola M88000, and also a Sun
Microsystems Workstation acting as host.  Though still in the early phase
of development, this support has already been targeted for applications
in automatic space mission planning, graphics, and multiple target tracking.}

\bigskip\starline\bigskip
\vbox{\par\noindent
{\bf Transparencies} from a talk by B. A. Zimmerman and G. A. Crichton,
entitled ``An object-oriented environment for the Caltech/JPL Mark IIIfp
Hypercube''.  C$^3$P-768 (Short Code: Zimmerman:89b)}

\end
