\input /home/sushi/kea/vax/macros.tex
\input /home/sushi/kea/bjfonts.tex
\baselineskip=14pt
\vsize=9.25truein
\hsize=6.5truein
\hoffset=-.2truecm
\tolerance=10000
\def\starline{\hbox to \hsize{* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *}}
\centerline{\twelvepoint\bf California Institute of Technology}
\smallskip
\centerline{\twelvepoint\bf C$^3$P Reports}
\smallskip
\centerline{\twelvepoint\bf January 1 -- December 31, 1990}
\bigskip
\bigskip
\vbox{\par\noindent{\twelvepoint\bf A Concurrent Implementation of the Prime 
Factor Algorithm on Hypercube}
\par\noindent
{\bf G. Aloisio, G. C. Fox, J. S. Kim, and N. Veneziani}
\par\noindent
C$^3$P-468b \ \ \ \ \ \ \ (Short Code: Aloisio:90a)
\par
The Prime Factor Algorithm (PFA) is an efficient Discrete Fourier
Transform (DFT) computation algorithm, where a one-dimensional DFT is
turned into a multi-dimensional DFT, consisting of a few short DFTs
whose lengths are mutually prime and then an efficient algorithm is
exploited for the short DFTs.  The data sequences in the Cooley-Tukey
algorithm are in order, easily manageable and well-suited for vector
processor and any parallel machines.  On the contrary, the PFA works on
DFTs of different lengths and heavily shuffles the updated data for
computing of subsequent order DFTs.  That poses a challenging problem
for a distributed memory machine.}
\par
We have implemented the PFA on hypercube using CrOS~III communication
routines, taking 120ms to compute the DFT of 5040 complex points using
32 nodes of Caltech-JPL Mark~III Hypercube.  It took 105ms to do a DFT
of 4096 complex points using the Cooley-Tukey algorithm with the same
hardware configuration.  We analyze the performance of hypercubes
Mark~III, NCUBE, and iPSC and the relative importance of communication
and calculation.
\par
With the current communication speed the Cooley-Tukey algorithm performs
fast on a massively concurrent processor and the PFA is advantageous
when the number of processors are less than 64 or so.  Our experience in
PFA also serves as a useful guide to a multi-dimensional FFT
implementation using any algorithm.

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf The Design of a Parallel/Pipeline
Multiprocessor System for Fast DFT Algorithms Computation}
\par\noindent
{\bf G. Aloisio, M. Bochicchio, G. C. Fox, R. Albrizio, A. Mazzone, and
N. Veneziani}
\par\noindent
C$^3$P-918 \ \ \ \ \ \ \ (Short Code:  Aloisio:90b)
\par
The results of an experience aimed to develop concurrent DFT algorithms
and their transposition on a parallel/pipeline architecture are
reported.  The standard Cooley-Tukey FFT algorithm and the Price Factor
algorithm are referred for the structure design.}
\par
The problems related to the balancing of the computational load between
successive pipeline levels are solved, in order to define an optimal
configuration, taking also into account the data rate on the I/O
channels.  Logical schemes of the structure are reported for the whole
system configuration and for the single processing element (PE).
\par
Moreover, the hardware implementation of a PE development system, based
on the concurrent use of a T800 transputer and the AT\&T DSP32-C chip,
is also presented.

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Computational Load Evaluation for
the Real-time Compression of X-SAR Raw Data}
\par\noindent
{\bf G. Aloisio, N. Veneziani, G. C. Fox and G. Milillo}
\par\noindent
C$^3$P-740b\ \ \ \ \ \ \ (Short Code: Aloisio:90c)
\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 Heterogeneous Hypercube Based on
Strengthened Nodes for a Fast Processing of SAR Raw-Data}
\par\noindent
{\bf G. Aloisio, M. Bochicchio, and C. Marzocca}
\par\noindent
C$^3$P-962\ \ \ \ \ \ \ (Short Code:  Aloisio:90d)
\par
A family of high performance processing elements has been conceived to
implement flexible multiprocessor structures for real-time
applications.  The floating-point capabilities of the INMOS transputer
components (T222-T805) have been improved, by using the AT\&T
floating-point Digital Signal Processors (DSP32-DSP32C), allowing to
achieve up to $\rm 25\,Mflops$, $\rm 30\,MIPS$.}
\par
In the paper, the design of a single board T800/DSP-32C based is
presented and the simulation results of its specialization in signal
processing applications are also reported.  A comparative test between
the traditional Cooley-Tukey FFT Algorithm (CTA) and the Prime Factor
Algorithm (PFA) shows that a 4096 complex points radix 4-CTA takes $\rm
16.6\,ms$, while for a 5040 complex points PFA about $\rm 32.3\,ms$ are
needed.
\par
A flexible development system has been also realized to allow a careful
design of various ``Strengthened Nodes'', since it can be used as a
test-bed to compare the performance of different DSPs available on the
market, when they are connected to components of the transputer family.
\par
``Strengthened Nodes'' will be used in heterogeneous multiprocessor
structures specialized for Synthetic Aperture Radar (SAR) data
processing.

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Discovery of Two Radio Pulsars in
the Globular Cluster M15}
\par\noindent
{\bf S. B. Anderson, P. W. Gorham, S. R. Kulkarni, T. A. Prince, and A.
Wolszczan}
\par\noindent
C$^3$P-864\ \ \ \ \ \ \ (Short Code: Anderson:90a)
\par
We report the discovery of two radio pulsars, ${\rm 2127+11B}$ and 
${\rm 2127+11C}$, in the globular cluster M15 (NGC~7078).  The discovery 
follows the earlier detection of the first pulsar in M15, 
${\rm 2127+11A^1}$.  ${\rm PSR 2127+11B}$ has a period of 56-ms and is
apparently an isolated pulsar while ${\rm PSR 2127+11C}$ has a
rotational period of 30-ms and is in a highly eccentric binary system
with an orbital period of 8.05-h.  Preliminary timing observations have
yielded the Keplerian parameters for this system.  We argue that the
companion is either another neutron star or a massive white dwarf,
suggesting a high density of massive stellar remnants in the core of
M15.  In addition, the discovery of three pulsars in one cluster alone
suggests a high abundance of radio pulsars in globular clusters.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Lattice Spin Models and New Algorithms 
--- A Review of Monte Carlo Computer Simulations}
\par\noindent
{\bf Clive F. Baillie}
\par\noindent
C$^3$P-854 \ \ \ \ \ \ \ (Short Code: Baillie:90a)
\par
We review Monte Carlo computer simulations of spin models --- both
discrete and continuous.  We explain the phenomenon of critical slowing
which seriously degrades the efficiency of standard local Monte Carlo
algorithms such as the Metropolis algorithm near phase transitions.  We
then go onto describe in detail the new algorithms which ameliorate the
problem of critical slowing down, and give their dynamical critical
exponent values.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Cluster Identification Algorithms
for Spin Models --- Sequential and Parallel}
\par\noindent
{\bf C. F. Baillie and P. D. Coddington}
\par\noindent
C$^3$P-855\ \ \ \ \ \ \ (Short Code:  Baillie:90b)
\par
Monte Carlo cluster update algorithms are extremely efficient for
simulating spin models near their phase transitions, where local update
algorithms suffer severe critical slowing down.  Unfortunately, as the
cluster algorithms are highly irregular as well as non-local, they are
much more difficult to parallelize efficiently.  The main difficulty
lies in identifying which spins belong to which cluster.  In this paper
we investigate a number of cluster identification algorithms, both
sequential and parallel, which we have implemented on serial, SIMD and
MIMD computers.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Crumpling Dynamically Triangulated
Random Surfaces in Higher Dimensions}
\par\noindent
{\bf C. F. Baillie, R. D. Williams, and D. A. Johnston}
\par\noindent
C$^3$P-867\ \ \ \ \ \ \ (Short Code:  Baillie:90c)
\par
Recent numerical simulations have revealed an unexpected second order
crumpling transition for {\it dynamically\/} triangulated random
surfaces embedded in three and four dimensions, raising the possibility
of defining a continuum string theory at this point.  In this paper we
explore the behavior of the transition in higher embedding dimensions
($d=5,6,8,10,15,20,26$) and find that the second order transition
persists, in disagreement with analytical predictions using the ${1\over
d}$ expansion, which might be expected to be valid for large $d$.  We
discuss the discrepancy and also observe that the variation of the phase
transition point with $d$ rules out the possibility that the continuum
theory is a hexatic membrane.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Non-Universality in Dynamically
Triangulated Random Surfaces with Extrinsic Curvature}
\par\noindent
{\bf C. F. Baillie, R. D. Williams, and D. A. Johnston}
\par\noindent
C$^3$P-868\ \ \ \ \ \ \ (Short Code:  Baillie:90d)
\par
Earlier simulations of dynamically triangulated random surfaces with a
pure Gaussian (Polyakov) action have suggested that the incorporation of
a term which is equivalent to the square of the scalar curvature, $R^2$,
in the continuum can affect the properties of the surfaces, despite the
fact that such a term appears to be irrelevant on dimensional grounds.
However, simulations by the current authors and Catterall of dynamically
triangulated random surfaces with extrinsic curvature produced
essentially identical results despite differing coefficients for the
$R^2$ term.  In this short note we show that small (positive or
negative) values of this coefficient have little effect but that large
values do produce measurable effects.  This explains the concordance of
our previous results with Catterall's and also provides evidence for
non-universal behavior in the random surface model.}

\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:90e)
\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 Lattice QCD: Commercial vs
Home-grown Parallel Computers}
\par\noindent
{\bf Clive F. Baillie}
\par\noindent
C$^3$P-878\ \ \ \ \ \ \ (Short Code:  Baillie:90f)
\par
Numerical simulations of Lattice QCD have been performed on practically every 
computer, since its inception almost twenty years ago.  Lattice QCD is an 
ideal problem for parallel machines as it can be easily domain decomposed.  In 
fact, the urge to simulated QCD has led to the development of several home-
grown parallel ``QCD machines'', in particular the Caltech Cosmic Cube, the 
Columbia Machine, IBM's GF11, APE in Rome and the Fermilab Machine.  These 
machines were built because, at the time, there were no commercial parallel 
computers fast enough.  Today, however, the situation has changed with the 
advent of computers like the Connection Machine-2 and the NCUBE-2.  Herein, I 
shall explain why Lattice QCD is such a parallel problem and compare two 
large-scale simulations of it --- one on the commercial Connection Machine and 
the other on the latest Caltech/JPL hypercube.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Numerical Simulations of Dynamically
Triangulated Random Surfaces on Parallel Computers with 100\% Speedup}
\par\noindent
{\bf Clive F. Baillie and Roy D. Williams}
\par\noindent
C$^3$P-879\ \ \ \ \ \ \ (Short Code:  Baillie:90g)
\par
We are currently performing large-scale numerical simulations of dynamically 
triangulated random surfaces on several parallel computers.  Herein, we 
briefly explain the importance of random surface simulations and describe in 
detail our computer program that simulates such surfaces with extrinsic 
curvature in arbitrary dimension.  As this program is an ideal benchmark of 
the scalar performance of a computer, we also present performance measurements 
for it on several sequential and parallel machines.}

\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:90h)
\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 Further Investigations of the
Crumpling Transition in Dynamically Triangulated Random Surfaces}
\par\noindent
{\bf Clive F. Bailie, Roy D. Williams, Simon M. Catterall, and Desmond A.
Johnston}
\par\noindent
C$^3$P-917 \ \ \ \ \ \ \ (Short Code:  Baillie:90i)
\par
We examine further the critical behavior of dynamically triangulated random
surfaces (DTRS) with extrinsic curvature at their second order crumpling 
transition. We show that the string tension in these models may be scaling 
near the transition in such a way that the physical string tension is finite, 
unlike models containing only a Polyakov term, suggesting that one can use 
DTRS as a discretization of sub-critical string theory. We explore the 
universality properties of DTRS, showing that an apparently irrelevant term 
can affect the phase transition. We also find that the observed phase 
transition persists when the surfaces are embedded in higher dimensions, 
contradicting the naive expectations of a saddle point expansion.}

\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:90j)
\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 A New MCRG Calculation of the
Critical Behavior of the 3d Ising Model}
\par\noindent
{\bf C. F. Baillie}
\par\noindent
C$^3$P-937\ \ \ \ \ \ \ (Short Code:  Baillie:90k)
\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, many
more operators --- 53 even spin and 46 odd spin --- are measured.
Secondly, larger lattices are used.  Lastly, we are incorporating more
efficient methods of spin update (Wolff's cluster algorithm).  We are
aiming to collect at least one hundred thousand measurements at two
temperatures on two lattice sizes --- $64^3$ and $128^3$.  Currently, we
have finished the runs for the first temperature and are about half-way
through those for the second.  Here we present results for the first
temperature.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Comparison of Cluster Algorithms for
2-d Potts Models}
\par\noindent
{\bf Clive F. Baillie and Paul D. Coddington}
\par\noindent
C$^3$P-945\ \ \ \ \ \ \ (Short Code:  Baillie:90l)
\par
We have measured the dynamical critical exponent $z$ 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 times differ considerably between 
algorithms, the critical exponents are the same.  The results for $q=2$ favor 
a logarithmic increase in the autocorrelation time with lattice size, implying
that $z$ is zero.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf A Comparison Cluster Algorithms for
Potts Models}
\par\noindent
{\bf Clive F. Baillie and Paul D. Coddington}
\par\noindent
C$^3$P-835\ \ \ \ \ \ \ (Short Code:  Baillie:90m)
\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 Clive F. Baillie, Desmond A. Johnston, and Gregory W. Kilcup}
\par\noindent
C$^3$P-800b\ \ \ \ \ \ \ (Short Code:  Baillie:90n)
\par
We review the status of lattice computer calculations in Quantum
Chromo-dynamics (QCD) and mention a new field of computational
high-energy physics---that of Strings or random surfaces.  After outline
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 current 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 {\it solved\/}!}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf An Interactive Environment for Data
Partitioning and Distribution}
\par\noindent
{\bf V. Balasundaram, G. Fox, K. Kennedy, and U. Kremer}
\par\noindent
C$^3$P-883\ \ \ \ \ \ \ (Short Code:  Balasundaram:90a)
\par
An approach to distributed memory parallel programming that has recently
become popular is one where the programmer explicitly specifies the data
decomposition using language extensions, and a compiler generates all
the communication.  While this frees the programmer from the tedium of
thinking about message-passing, no assistance is provided in determining
the data decomposition scheme that gives the best performance on the
target machine.  In this paper, we propose an interactive software tool
that provides assistance for this very task.  The proposed tool also
computes performance estimates for any chosen data partitioning scheme,
allowing the programmer to experiment with several different strategies
without ever running the program on the machine.}

\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 Vasanth Balasundaram}
\par\noindent
C$^3$P-843\ \ \ \ \ \ \ (Short Code:  Balasundaram:90e)
\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 Static Performance Estimator}
\par\noindent
{\bf Vasanth Balasundaram}
\par\noindent
C$^3$P-941\ \ \ \ \ \ \ (Short Code:  Balasundaram:90f)
\par
This document describes the software implementation details of the
Performance Estimator designed as part of the CRPC Distributed Memory
Compilation Project.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf The 2D Heisenberg Antiferromagnet in
$\rm High-T_{c}$ Superconductivity, A Review of Numerical Techniques and
Results}
\par\noindent
{\bf T. Barnes}
\par\noindent
C$^3$P-873\ \ \ \ \ \ \ (Short Code:  Barnes:90a)
\par
In this article, we review numerical studies of the quantum Heisenberg
antiferromagnet on a square lattice, which is a model of the magnetic
properties of the undoped ``precursor insulators'' of the high
temperature superconductors.  We begin with a brief pedagogical
introduction and then discuss zero and nonzero temperature properties
and compare the numerical results to analytic calculations and to
experiment where appropriate.  We also review the various algorithms
used to obtain these results, and discuss algorithm developments and
improvements in computer technology which would be most useful for
future numerical work in this area.  Finally, we list several
outstanding problems which may merit further investigation.}

\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 Roberto Battiti}
\par\noindent
C$^3$P-900\ \ \ \ \ \ \ (Short Code:  Battiti:90a)
\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 {\it 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.  {\it 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 Real-Time Multiscale Vision on a
Two-Dimensional Mesh of Processors}
\par\noindent
{\bf Roberto Battiti}
\par\noindent
C$^3$P-932\ \ \ \ \ \ \ (Short Code:  Battiti:90b)
\par
This paper investigates the use of large grain size multicomputers for
solving low- and intermediate-level computer vision problems.  The
realization of a general multiresolution framework on a two-dimensional
grid of processors is analyzed, presenting the resulting speedup and
total solution time as a function of algorithmic and technological
parameters.  The scheme is then specialized for two significant
problems: surface reconstruction and optical flow.  While the first can
be solved with the standard full multigrid approach, the second requires
using an adaptive grid determined by a local decision:  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.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf An Adaptive Multiscale Scheme for
Real-Time Motion Field Estimation}
\par\noindent
{\bf Roberto Battiti}
\par\noindent
C$^3$P-933\ \ \ \ \ \ \ (Short Code:  Battiti:90c)
\par
The problem considered in this work is that of estimating the motion
field (i.e., the projection of the velocity field onto the image plane)
from a temporal sequence of images.}
\par
Generic images contain different objects with diverse spatial
frequencies and motion amplitudes.  To deal with this complex
environment in a fast and effective way, biological visual systems use
parallel processing, visual channels at different resolutions and
adaptive mechanisms.  In this paper a new adaptive multiscale scheme is
proposed, in which the spatial discretization scale is based on a local
estimate of the errors involved.  Considering the constraints for
real-time operation, flexibility and portability, the scheme can be
implemented on MIMD parallel computers with medium size grains with high
efficiency.
\par
Tests with ray-traced and video-acquired images for different motion
ranges show that this method produces a better estimation with respect
to the homogeneous ({\it non}-adaptive) multiscale method.

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf A Computational Model for
Organizations of Cooperating Intelligent Agents}
\par\noindent
{\bf Alan H. Bond}
\par\noindent
C$^3$P-923 \ \ \ \ \ \ \ (Short Code:  Bond:90a)
\par
A computational model is developed, which captures properties of
relationship and organization in sets of distributed intelligent
agents.  The model is inspired by sociological theory, and uses
centrally a concept of commitment.}
\par
Symbolic interactionist concepts in sociology are reviewed from the
perspective of Distributed Artificial Intelligence.  This includes the
work of Anselm Strauss and Elihu Gerson.
\par
A formulation of the concept of commitment is proposed.  The concept is
propagated into notions of agent and organization.
\par
A formulation and computational model of the basic notion of commitment
is given, which represents commitments as mutually agreed constraints on
action, belief and world state.
\par
The issues of agent integrity, plans and resources, and their
representation, are then discussed, and computational mechanisms
defined.
\par
An organization is defined as a set of agents with consistent mutual
commitments.  A mechanism is defined to check and enforce the
consistency of these commitments.

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Toward a Parallel CAD/CAM System}
\par\noindent
{\bf Alan H. Bond and Vernon Austel}
\par\noindent
C$^3$P-924 \ \ \ \ \ \ \ (Short Code:  Bond:90b)
\par
This paper describes progress proving feasibility of a parallel
intelligent CAD/CAM system, based on parallel logic programming
techniques, a parallel logic programming language and general-purpose
computer hardware.}
\par
A feature cascade approach to CAD/CAM processes, developed in previous
work in Prolog, was used.  The action of the system is to respond to
design changes to a CAD/CAM model, by updating the model and deriving
all concurrent engineering consequences for feedback to the designer.
The system could take its input from a 3D wireframe model in CADAM,
using an auxiliary Prolog package, however, in general, it assumed an
input boundary representation form, i.e., representations of 3D faces
and edges, which is available from many CAD systems.
\par
The parallel logic programming language, Strand, was selected, after
some study of Flat Concurrent Prolog and Parlog.  A number of approaches
to CAD/CAM modeling in Strand were examined, and a maximally
process-based approach adopted.  This process model is described in
detail.
\par
The model was implemented and initial performance results obtained, for
runing on a shared memory machine with 24 processors, a Sequent
Symmetry.  This implementation used realistic CAD/CAM data.  The load
balancing strategy used was a uniform distribution of the model over the
processors.  The system was run on 1--20 processors and exhibited
acceptable parallelism:  time $\propto$ 1/number of processors, $n$ with
an efficiency, $T_1/\lbrack T_n^{\ast}n\rbrack$ of about 0.5.
\par
The contribution of the work is to have developed a practical approach
to CAD/CAM systems for parallel workstations.  This approach involves a
synthesis of
\item{1.}A methodology of responding to design changes.
\item{2.}The use of data forms in predicate logic.
\item{3.}A knowledge representational approach of concurrent engineering
using a feature cascade model.
\item{4.}A system software strategy of using Strand, which is
commercially supported, and which potentially allows many different
types of parallel machine to be used.
\item{5.}A Strand CAD/CAM modeling method of using a network of
processes.
\item{6.}An appropriate load balancing strategy, expressible in Strand.

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf QCD on the Connection Machine:
Beyond *Lisp}
\par\noindent
{\bf Ralph G. Brickner, Clive F. Baillie, and S. Lennart Johnsson}
\par\noindent
C$^3$P-936\ \ \ \ \ \ \ (Short Code:  Brickner:90a)
\par
We report on the status of code development for a simulation of Quantum
Chromodynamics (QCD) with dynamical Wilson fermions on the Connection
Machine model CM-2.  Our original code, written in *Lisp, gave
performance in the near-GFLOPS range.  We have rewritten the most
time-consuming parts of the code in the low-level programming system
CMIS, including the matrix multiply and the communication.  Current
versions of the code run at approximately 3.6~Gflops for the fermion
matrix inversion, and we expect the next version to reach or exceed
5~Gflops.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Gauge Theories on the Random-Block
Lattice}
\par\noindent
{\bf T. W. Chiu}
\par\noindent
C$^3$P-955\ \ \ \ \ \ \ (Short Code:  Chiu:90a)
\par
Gauge theories are formulated on the random-block lattice in which the
sites are cartesian product of $D$ sets of random coordinates, one from
each dimension, where $D$ is the dimension of the space-time.  Some
numerical results of the pure gauge theories are presented.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Cluster Algorithms for Spin Models
on MIMD Parallel Computers}
\par\noindent
{\bf Paul D. Coddington and Clive F. Baillie}
\par\noindent
C$^3$P-862\ \ \ \ \ \ \ (Short Code:  Coddington:90a)
\par
Parallel computers are ideally suited to the Monte Carlo simulation of
spin models using the standard Metropolis algorithm, since it is regular
and local.  However local algorithms have the major drawback that near a
phase transition the number of sweeps needed to generate a statistically
independent configuration increases as the square of the lattice size.
New algorithms have recently been developed which dramatically reduce
this `critical slowing down' by updating clusters of spins at a time.
The highly irregular and non-local nature of these algorithms means that
they are much more difficult to parallelize efficiently.  Here we
introduce the new cluster algorithms, explain some sequential algorithms
for identifying and labeling connected clusters of spins, and then
outline some parallel algorithms which have been implemented on MIMD
machines.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Parallel Cluster Algorithms}
\par\noindent
{\bf P. D. Coddington and C. F. Baillie}
\par\noindent
C$^3$P-946\ \ \ \ \ \ \ (Short Code:  Coddington:90b)
\par
Cluster update algorithms dramatically reduce critical slowing down in
spin models, but unlike the standard Metropolis algorithm, it is not
obvious how to implement these algorithms efficiently on parallel or
vector computers.  Here we present two different parallel
implementations of the Swendsen-Wang algorithm which give reasonable
efficiencies on various MIMD parallel computers.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Spin Correlations in the
Antiferromagnet Crystals $\bf La_2\,Cu\,O_4$ and $\bf K_2\,N_i\,F_4$}
\par\noindent
{\bf H.-Q. Ding and M. S. Makivi\'c}
\par\noindent
C$^3$P-896\ \ \ \ \ \ \ (Short Code:  Ding:90a)
\par
The recent progress in studying the spin correlations of the quantum 2D
antiferromagnet systems is reviewed.  The theoretical results agree well
with the neutron scattering experiments on both spin-${1\over 2}\,\rm
La_2\,Cu\,O_4$ and spin-1$\,\rm K_2\,N_i\,F_4$.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Calculation of the Heavy Quark
Potential at Large Separation on a Hypercube Parallel Computer}
\par\noindent
{\bf H.-Q. Ding, C. F. Baillie, and G. C. Fox}
\par\noindent
C$^3$P-779b\ \ \ \ \ \ \ (Short Code:  Ding:90b)
\par
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}/\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 The 600 Megaflops Performance of the
QCD Code on the Mark~IIIfp Hypercube}
\par\noindent
{\bf H.-Q. Ding}
\par\noindent
C$^3$P-799b\ \ \ \ \ \ \ (Short Code:  Ding:90c)
\par
A QCD code running on the state-of-art parallel supercomputer --- the
128-node JPL/Caltech Mark~IIIfp hypercube achieves a sustained speed of
$\rm 600\,Mflops$.  The performance characteristics of the Mark~IIIfp
are measured.  A vectorized communication scheme is used to minimize the
communication overhead.  The speedup is shown to be linear and increases
as the grain size increases.  It reaches 100 on the 128-node
configuration.  Many issues of general interest to parallel computations
are discussed.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Quark Potential at Large Distance:
Evidence of Scaling from Lattice Gauge Simulations on a Hypercube
Supercomputer}
\par\noindent
{\bf H.-Q. Ding}
\par\noindent
C$^3$P-914\ \ \ \ \ \ \ (Short Code:  Ding:90d)
\par
The static $q \bar q$ potential is measured using Wilson line 
operator-operator correlations with high statistics on a hypercube parallel 
supercomputer.  On $24^3$x14 and $16^3$x24 lattices at $\beta$=6.1 we 
obtained  $\sigma a^2 \simeq 0.026$ and on $24^3$x16 and $16^3$x24 lattices 
at $\beta$=6.2, $\sigma a^2 \simeq 0.023$.  Together with $\sigma a^2 \simeq 
0.033$ at $\beta$=6 in the previous calculation, the asymptotic scaling 
is satisfied within about 90\% accuracy, leading to a unique continuum limit
value  ${{\sqrt \sigma} / {\Lambda_L} } = 78 \pm 5 $. The coupling constant
is  found to be $\alpha \simeq 0.54 \pm 0.11$.  This new result compares
favorably with that obtained from Charmonium experimental data, but 
is significantly different from earlier calculations which based on
smaller distance points.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Phase Transitions in Two-Dimensional
Quantum Spin Systems --- Monte Carlo Simulations on a Hypercube
Supercomputer}
\par\noindent
{\bf H.-Q. Ding}
\par\noindent
C$^3$P-915\ \ \ \ \ \ \ (Short Code:  Ding:90e)
\par
A series of large scale Quantum Monte Carlo simulations of the 2-d quantum 
spin systems are carried out on the 64-node Caltech/JPL MarkIIIfp Hypercube 
Supercomputer. On lattices as large as 96x96 and 128x128, we obtained 
conclusive evidences of the Kosterlitz-Thouless phase transition in the 
{\it XY} model, Ising-like transition in the anisotropic Heisenberg
model, and detailed low temperature behavior on the isotropic Heisenberg
model. These previously unknown results have made deep impact on our
understanding of critical phenomenon and phase transitions, and have quite
wide applications in currently active researches, including 2-d 
superfluidity, melting, and high temperature superconductivity. Universality 
classes of these O(1), O(2) and O(3) symmetries in 2-d quantum system are 
found to be the same of the corresponding classical systems.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Asymptotic Scaling of the Heavy
Quark Potential in Lattice QCD}
\par\noindent
{\bf H.-Q. Ding}
\par\noindent
C$^3$P-916\ \ \ \ \ \ \ (Short Code:  Ding:90f)
\par
The scaling behavior of the heavy quark $q \bar q$ potential is studied
by measuring Wilson line operator-operator correlations via extensive 
simulations on large lattices. By using large size loops (up to 16x12) and 
extracting the potential at large distance $R \geq 4$, we found that
the string tension satisfies the two loop asymptotic scaling within about 
95\% accuracy at the coupling $\beta$=6.0, 6.1, 6.2 and $\alpha$ remains a 
constant. Thus the scaling of the string tension sets in at around $\beta=6$. 
The obtained value, ${{\sqrt \sigma} / {\Lambda_L} } = 78 \pm 4 $ and
$\alpha \simeq 0.54 \pm 0.11$ agree well with the potential model analysis
on $c \bar c$ and $ b \bar b$ system. Among the existing underlying string 
theories, our results favors the Neveu-Schwarz string theory.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Spin Correlations 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:90g)
\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 Kosterlitz-Thouless Transition in
the Two-dimensional Quantum $XY$ Model}
\par\noindent
{\bf H.-Q. Ding and M. S. Makivic}
\par\noindent
C$^3$P-851b\ \ \ \ \ \ \ (Short Code:  Ding:90h)
\par
Convincing numerical evidence is obtained via extensive quantum Monte
Carlo simulations on square lattices as large as $96\times 96$ that the
spin-$1\over 2$ $XY$ model undergoes a Kosterleitz-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
specific heat increases very rapidly near $T_c$ and exhibits a peak
around $kT/J=0.45$.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Antiferromagnetic Transitions in
High-T$_c$ Materials}
\par\noindent
{\bf H.-Q. Ding}
\par\noindent
C$^3$P-953\ \ \ \ \ \ \ (Short Code:  Ding:90i)
\par
The N\'eel ordering transition of the 2D spin-1/2 Heisenberg
antiferromagnet is studied in the small in-plane anisotropy limit
through extensive quantum Monte Carlo simulations on lattices as large
as $96\times 96$.  At an Ising-like anisotropy energy $h^A = 0.0025$,
the system orders at $T_c/kT = 0.295$.  This striking effect and related
results agree with a wide class of experiments and give some insight
into these materials.}

\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-845b\ \ \ \ \ \ \ (Short Code:  Ding:90k)
\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 Heavy Quark Potential in Lattice QCD
--- A Review of Recent Progress at Caltech}
\par\noindent
{\bf H.-Q. Ding}
\par\noindent
C$^3$P-963\ \ \ \ \ \ \ (Short Code:  Ding:90l)
\par
Recent progress on the calculation of the $q\bar{q}$-potential is
reviewed.  Scaling is discussed from the perspective of critical
phenomenon.  Methods for fitting the correlations of Polyakov operators
and the Wilson loops are reviewed and two new methods, the iterative
method and the improved ratio method, are discussed in detail.  These
new methods are used to analyze/re-analyze the previously published data
on Polyakov loops and new data on large Wilson loops.  Convincing
numerical evidences together with several analytical arguments strongly
support the conclusion that the asymptotic scaling sets in at $\beta\sim
6$ with $\sqrt{\sigma}/\Lambda_L = 79\pm 3$ and $\alpha = 0.43\pm 0.03$.
These results agree well with the potential model analysis of
experimental data on $c\bar{c}$ and $b\bar{b}$ systems, and favors the
Neveu-Schwarz strings as the underlying string theory.  Finally, key
issues on the use of the parallel computers are explored, with the
conclusion that parallel computers are highly suitable for these
floating-point intensive computations.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Parallel Finite Elements Applied to
the Electromagnetic Scattering Problem}
\par\noindent
{\bf R. D. Ferraro, T. Cwik, N. Jacobi, P. C. Liewer, T. G. Lockhart, G.
A. Lyzenga, J. Parker, and J. E. Patterson}
\par\noindent
C$^3$P-903\ \ \ \ \ \ \ (Short Code:  Ferraro:90a)
\par
A 2D electromagnetic finite element analysis code which runs on the
JPL/Caltech Mark~IIIfp Hypercube is being upgraded to handle fully three
dimensional scattering problems.  The EM code uses finite element to
model a finite problem domain which may include regions of anisotropic
or nonuniform dielectric properties.  It solves the single frequency
source driven vector wave equation for electric or magnetic fields in
this domain.  The code is being implemented as a testbed for finite
elements as applied to EM problems, with several types of elements,
radiation boundary condition strategies, and parallel solvers.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf A 2D Electrostataic PIC Code for the
Mark~III Hypercube}
\par\noindent
{\bf R. D. Ferraro, P. C. Liewer, and V. K. Decyk}
\par\noindent
C$^3$P-905\ \ \ \ \ \ \ (Short Code:  Ferraro:90b)
\par
We have implemented a 2D electrostatic plasma particle in cell (PIC)
simulation code on the Caltech/JPL Mark~IIIfp Hypercube.  The code
simulates plasma effects by evolving in time the trajectories of
thousands to millions of charged particles subject to their
self-consistent fields.  Each particle's position and velocity is
advance din time using a leap frog method for integrating Newton's
equations of motion in electric and magnetic fields.  The electric field
due to these moving charged particles is calculated on a spatial grid at
each time step by solving Poisson's equation in Fourier space. These two
tasks represent the largest part of the computation.  To obtain
efficient operation on a distributed memory parallel computer, we are
using the General Concurrent PIC (GCPIC) algorithm previously developed
for a 1D parallel PIC code.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Challenges in High Performance
Computing}
\par\noindent
{\bf Geoffrey C. Fox}
\par\noindent
C$^3$P-858\ \ \ \ \ \ \ (Short Code: Fox:90a)
\par
This is a set of foils describing the challenges in parallel computing
with particular reference to problems affecting the air force.  We cover
conventional and neural network approaches.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf AI Technology Research in the
Syracuse Computational Science Center}
\par\noindent
{\bf Geoffrey C. Fox}
\par\noindent
C$^3$P-889\ \ \ \ \ \ \ (Short Code:  Fox:90c)
\par
We propose several projects within the recent RADC BAA on AI Technology.  
These consist of application design and implementation.  Much of the work 
will be done in terms of MOVIE, a new object oriented software engineering 
designed for simulating complex systems.  The aspects of MOVIE of general 
applicability to all projects are given in the appendix.  We also describe 
the current plans for the Computational Science Center here.  The algorithmic 
research uses the ideas of physical computation which combine neural networks, elastic 
networks, and simulated annealing.  This has already been applied with 
success to navigation, tracking and clustering problems.  We enclose key 
papers.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Parallel Programming as an
Optimization Problem or Intelligent Compilers for Parallel Computers}
\par\noindent
{\bf Geoffrey C. Fox and Vasanth Balasundaram}
\par\noindent
C$^3$P-891\ \ \ \ \ \ \ (Short Code: Fox:90d)
\par
For at least the next few years, FORTRAN will be a critical language for
scientific computation.  One can view it either as a primary user
interface or as a portable ``machine-language'' for which excellent
compilers exist and which is a target for more user-friendly systems.
Mapping a scientific problem onto a high performance computer can be
viewed as a hard optimization problem where one minimizes some
combination of user program development time and production program
execution time.  We consider how expert systems, neural networks,
simulated annealing, and related methods can be integrated into a
FORTRAN compiler to both give better code and feedback to the user on
the appropriateness of a particular problem to particular hardware.}

\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-910\ \ \ \ \ \ \ (Short Code:  Fox:90e)
\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 Optimization and the Travelling
Salesmen}
\par\noindent
{\bf Geoffrey C. Fox}
\par\noindent
C$^3$P-922.4 \ \ \ \ \ \ \ (Short Code:  Fox:90f)
\par
We contrast different approaches to optimization; heuristics,
combinatorial optimization, expert systems, and physical (pertaining to
nature) optimization.  The latter include genetic algorithms, simulated
and new deterministic annealing, neural and elastic networks, and
information theoretic approaches.  Different problems are suitable for
different methods.  They have different trade-offs in areas of
robustness, accuracy, speed, dependence on problem size and ease of
parallelization.  We illustrate this with track finding where for
different parameter (track density, noise) regimes, one will use 
combinatorial, annealing or neural approaches.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Computational Science}
\par\noindent
{\bf Geoffrey C. Fox}
\par\noindent
C$^3$P-939\ \ \ \ \ \ \ (Short Code:  Fox:90m)
\par
We describe computational science using examples from our experience at
Caltech.  We define it to include both doing science with computers and
the science of developing the tools and ideas that make them useful.  We
describe some initial plans for Computational Science at Syracuse.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Exploring Glueball Wavefunctions on
the Lattice}
\par\noindent
{\bf Rajan Gupta, Apporva Patel, Clive F. Baillie, Gregory Kilcup, and
Stephen Sharpe}
\par\noindent
C$^3$P-943\ \ \ \ \ \ \ (Short Code:  Gupta:90a)
\par
  We calculate the string tension and $\oplus$ and $2^{++}$ glueball
masses in pure gauge QCD using an improved lattice action.  We compare 
various operator smearing methods, and find that the best glueball signal 
is obtained using smeared Wilson loops of size about $0.5\ fm$.  Our 
results for mass-ratios, $m_{0^{++}} / \sqrt{\sigma}  = 3.5(3)$ and 
$m_{2^{++}} / m_{0^{++}} = 1.6(2)$, are consistent with those computed 
with the simple plaquette action.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Parallel Algorithms for One and
Two-Vehicle Navigation}
\par\noindent
{\bf Eitan Gurewitz, Geoffrey Fox, and Yiu-fai Wong}
\par\noindent
C$^3$P-876\ \ \ \ \ \ \ (Short Code:  Gurewitz:90a)
\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 An Automata Model of Granular
Materials}
\par\noindent
{\bf Gary M. Gutt}
\par\noindent
C$^3$P-890\ \ \ \ \ \ \ (Short Code:  Gutt:90a)
\par
A new modeling technique (the Lattice Grain Model) is presented for the 
simulation of two-dimensional granular systems involving large numbers ($\sim 
10^4$ to $10^6$) of grains.  These granular systems ({\it e.g.,\/} rock 
slides, planetary rings, industrial powders, {\it etc.\/}) may include both 
high shear rate regions as well as static plugs of grains and cannot easily be 
handled within the framework of existing continuum theories such as soil 
mechanics.}
\par
The Lattice Grain Model (LGrM) is similar to the Lattice Gas Model (LGM), 
which was introduced as a discrete model of fluids, in that the computation is 
carried out by means of cellular automata which evolve according to a simple 
set of rules based on local iterations.  This allows large simulations to be 
programmed onto a hypercube concurrent processor in a straightforward manner.  
However, it differs from LGM in that it includes the inelastic collisions and 
volume-filling properties of macroscopic grains.
\par
Examples to be presented will include Couette flow, flow through an hourglass, 
and gravity-driven flows around obstacles.

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Studies of Electron-Molecule
Collisions on the Mark~IIIfp Hypercube}
\par\noindent
{\bf Paul Hipes, Carl Winstead, Marco Lima, and Vincent McKoy}
\par\noindent
C$^3$P-909\ \ \ \ \ \ \ (Short Code:  Hipes:90a)
\par
We report on a distributed memory implementation and initial
applications of a program for calculating electron-molecule collision
cross sections.  Runs on the Mark~IIIfp hypercube show that large-grain
MIMD machines are well suited for these applications.  Some results of
studies of $e^-\, -Si_2\,H_6$ and $e^-\, -Si\,F_4$ collisions will be
discussed.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Parallel Neural Net Path-Planner on 
Hypercube and Transputer}
\par\noindent
{\bf Alex W. Ho and Geoffrey C. Fox}
\par\noindent
C$^3$P-848\ \ \ \ \ \ \ (Short Code: Ho:90a)
\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 Portable Asteroids on Hypercube or
Transputers}
\par\noindent
{\bf Alex W. Ho and Geoffrey C. Fox}
\par\noindent
C$^3$P-880\ \ \ \ \ \ \ (Short Code:  Ho:90b)
\par
A multi-play 3D Asteroids video game designed to be used as a testbed
for evaluating controller algorithms was described in [Ho:89b].  The
original version of the game and a separate interactive 3D graphics
interface for a human player were implemented, based on CrOS~III and
VERTEX, on an NCUBE-1 hypercube equipped with a parallel Real-Time
Graphics board.  The Asteroids and interactive graphics interface
programs are examples of parallel programs which communicate with each
other in a space-shared multi-processor environment.}
\par
We have successfully ported the Asteroids and the interactive graphics
interface to run on NCUBE using ParaSoft EXPRESS.  The new version of
these programs were further ported to run on a SUN~386i with an add-on
Transputer board.  We present general design considerations that enable
easy migration of communicating parallel programs to any other hardware
platform that runs EXPRESS.  We also report specific experience of
porting Asteroids and an associated interactive player interface program
on an NCUBE hypercube to a SUN~386i Transputer-based system, with no
modification of codes.

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Learning to Plan Near-Optimal
Collision-Free Paths}
\par\noindent
{\bf Alex W. Ho and Geoffrey C. Fox}
\par\noindent
C$^3$P-881\ \ \ \ \ \ \ (Short Code: Ho:90c)
\par
A new approach to find a near-optimal collision-free path is presented.  The 
path planner is an implementation of the adaptive error back-propagation 
algorithm which learns to plan ``good'', if not optimal, collision-free paths 
from human-supervised training samples.}
\par
Path planning is formulated as a classification problem in which class labels 
are uniquely mapped onto the set of maneuverable actions of a robot or 
vehicle.  A multi-scale representational scheme maps physical problem domains 
onto an arbitrarily chosen fixed size input layer of an error back-propagation 
network.  The mapping does not only reduce the size of the computation domain, 
but also ensures applicability of a trained network over a wide range of 
problem sizes.  Parallel implementation of the neural network path planner on 
hypercubes or Transputers based on ParaSoft {\bf Express} is simple and 
efficient.  Simulation results of binary terrain navigation indicate that the 
planner performs effectively in unknown environment in the test cases.

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Neural Network Near-Optimal Motion
Planning for a Mobile Robot on Binary and Varied Terrains}
\par\noindent
{\bf Alex W. Ho and Geoffrey C. Fox}
\par\noindent
C$^3$P-882\ \ \ \ \ \ \ (Short Code: Ho:90d)
\par
We present an efficient approach to plan a near-optimal collision-free
path for a mobile robot on binary or varied terrains.  Motion planning
is formulated as a classification problem in which class labels are
uniquely mapped onto a set of maneuverable robot motions.  The neural
network motion planner is an implementation of the popular adaptive
error back-propagation model.  The motion planner learns to plan
``good'', if not optimal, collision-free path from supervision in the
form of training samples.}
\par
A multi-scale representational scheme, as a consequence of a
vision-based terrain sampling strategy, maps physical problem domains
onto an arbitrarily chosen fixed size input layer of an error
back-propagation network.  The mapping does not only reduce the size of
the computation domain, but also ensures applicability of a trained
network over a wide range of problem sizes.  Simulation results of
binary terrain navigation indicate that the planner performs effectively
in unknown environment in the test cases.  Preliminary results of the
capability of the model in learning varied terrain navigation are also
presented.

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Multi-Scale, Vision-Based Navigation
on Distributed-Memory MIMD Computers}
\par\noindent
{\bf Alex W. Ho and Geoffrey C. Fox}
\par\noindent
C$^3$P-911\ \ \ \ \ \ \ (Short Code:  Ho:90e)
\par
A neural net approach to near-optimal robot navigation based on a
multi-scale, vision-based terrain representation is presented.  In our
supervised neuromorphic formulation, an approximate retinal map of a
binary or varied terrain, results in a natural multi-scale
representation, carries information about global trajectory planning,
local obstacle avoidance, homing signal, and a notion of optimality for
any time instance.  The approach copes with slowly time-varying
environment in which obstacles can either be static or moving slowing
relative the motion of the robot at hand.  The multi-scale
representation does not only reduce size of computation domain but also
ensures the applicability of trained network to unknown environment of
different sizes.  The network algorithm was implemented on hypercube as
well as Transputer-based distributed-memory MIMD computers for fast
training.  Performances of the neural network navigation controller for
binary and varied terrains are presented.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Competitive-Cooperative System of
Distributed Artificial Neural Agents}
\par\noindent
{\bf Alex W. Ho and Geoffrey C. Fox}
\par\noindent
C$^3$P-925\ \ \ \ \ \ \ (Short Code:  Ho:90f)
\par
A framework for simulations of hierarchical organizations of interacting, 
distributed artificial intelligent agents on distributed-memory, MIMD 
computers is presented.  Interactions among aggregates of intelligent agents 
in an organization are restricted to obey competition and cooperation 
criteria.}
\par
Each intelligent agent in an organization is a parallel implementation of a 
feed-forward multi-layer perceptrons neural network using error 
back-propagation (BP) as the learning rule. In this preliminary study,
{\it domination}, viewed as a type of deterministic genetic algorithm (GA,)
is chosen to be the preferred form of interaction.  
\par
The framework exploits the hierarchical nature intrinsic in an organizational 
approach to problem-solving.  It takes advantage of parallelism at different 
levels of granularity, from domain decomposition within the agents to coarse 
grain team-level interaction.  Transputer-based simulation results for a test 
problem of learning the solution to a parity function of predicate order 10
is discussed.

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Hypercubes for Critical Space Flight
Command Operations}
\par\noindent
{\bf J. C. Horvath, T. Tang, L. P. Perry, R. C. Cole}
\par\noindent
C$^3$P-898\ \ \ \ \ \ \ (Short Code:  Horvath:90a)
\par
Controlling interplanetary spacecraft and planning their activities, as
currently practiced, requires massive amounts of computer time and
personnel.  To improve this situation, it is desired to use advanced
computing to speed up and automate the commanding process.  Several
design and prototype efforts have been underway at JPL to understand the
appropriate roles for concurrent processors in future interplanetary
spacecraft operations.  Here we report on an effort to identify likely
candidates for parallelism among existing software systems that both
generate commands to be sent to the spacecraft and simulate what the
spacecraft will do with these commands when it receives them.  We also
describe promising results from efforts to create parallel prototypes of
representative portions of these software systems on the JPL/Caltech
Mark~III hypercube.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf An Automatic and Symbolic
Parallelization System for a Distributed Memory Parallel Computer}
\par\noindent
{\bf K. Ikudome, G. C. Fox, A. Kolawa, and J. W. Flower}
\par\noindent
C$^3$P-877\ \ \ \ \ \ \ (Short Code:  Ikudome:90a)
\par
Despite the fact that distributed memory parallel computers promise virtually 
unlimited, cost effective performance, they suffer from comparison with more 
conventional architectures due to the difficulties in programming.  while the 
issues of data dependency have already been explored for shared memory and 
``vector'' machines, distributed memory machines also require explicit data 
decomposition.  Direct user parallelization has already shown this to be an 
extremely effective methodology and has directed the development of 
appropriate runtime systems to support the communication and decomposition 
needs of such programs.  One such example is the {\bf Express\/} system used 
in this paper.}
\par
It is not, in general, possible to automate the parallelization of general 
sequential programs.  One of our goals, therefore, is to delineate those 
applications and those software engineering practices which allow automatic 
parallelization.  Similar to the vectorizing compiler of the CRAY machines, 
{\bf ASPAR} allows many users who have little interest in the details of 
distributed memory parallel computers to use them.
\par
This paper describes {\bf ASPAR} (Automatic and Symbolic PARallelization 
system) which is a source-to-source parallelizing system for distributed 
memory parallel computers.  It analyzes a complete sequential program with 
respect to data-dependency and data-decomposability and then translates it to 
parallel code using the data decomposition tools of {\bf Express}.  Currently, 
this system has been implemented for the language C, but it has been designed 
to be expanded to other common languages such as Fortran.
\par
In addition to the automatic parallelizing facility, this system includes 
interactive graphic tools which allow the user to easily analyze problems 
which prevent the successful automatic parallelization of the code.  These 
tools can display program flow, data flow, the parallelism inherent in FOR 
loops and other appropriate information in a graphic window.  These tools also 
allow the user to supplement the parallelism supplied automatically in cases 
where additional knowledge of the underlying methods allows for additional, or 
better performance.
\par
To evaluate {\bf ASPAR} we applied it to several applications such as the 
Conjugate Gradient Method for banded linear equations and PDEs.  The results 
are shown in this paper.

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Parallel Sorting on Symult 2010}
\par\noindent
{\bf P. Peggy Li and Yu-Wen Tung}
\par\noindent
C$^3$P-901\ \ \ \ \ \ \ (Short Code:  Li:90a)
\par
In this paper, three sorting algorithms, Bitonic sort, Shell sort and
parallel Quicksort are studied.  We analyze the performance of these
algorithms and compare them with the empirical results obtained from the
implementations on the Symult Series 2010, a distributed-memory,
message-passing MIMD machine.  Each sorting algorithm is a combination
of a parallel sort component and a sequential sort component.  These
algorithms are designed for sorting $M$ elements of random integers on a
$N$-processor machine, where $M>N$.  We found that Bitonic sort is the
best parallel sorting algorithm for small problem size, ($M/N < 64$),
and the parallel Quicksort is the best for large problem size.  The new
Parallel Quicksort algorithm with a simple key selection method achieves
a decent speed-up comparing with other versions of parallel Quicksort on
similar parallel machines.  Although Shell sort has a worse theoretical
time complexity, it does achieve linear speedup for large problem size
by using a synchronization step to detect early termination of the
sorting steps.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Dynamic Load Balancing in a
Concurrent Plasma PIC Code on the JPL/Caltech Mark~III Hypercube}
\par\noindent
{\bf P. C. Liewer, E. W. Leaver, V. K. Decyk, and J. M. Dawson}
\par\noindent
C$^3$P-894\ \ \ \ \ \ \ (Short Code: Liewer:90a)
\par
Dynamic load balancing has been implemented in a concurrent
one-dimensional electromagnetic plasma particle-in-cell (PIC) simulation
code using a method which adds very little overhead to the parallel
code.  In PIC codes, the orbits of many interacting plasma electrons and
ions are follows as an initial value problem as the particles move in
electromagnetic fields calculated self-consistently from the particle
motions.  The code was implemented using the GCPIC algorithm in which
the particles are divided among processors by partitioning the spatial
domain of the simulation.  The problem is load-balanced by partitioning
the spatial domain so that each partition has approximately the same
number of particles.  During the simulation, the partitions are
dynamically recreated as the spatial distribution of the particles
changes in order to maintain processor load balance.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Two Dimensional Spin-$\bf 1\over 2$
Heisenberg Antiferromagnet: A Quantum Monte Carlo Study}
\par\noindent
{\bf Miloje S. Makivi\'c and Hong-Qiang Ding}
\par\noindent
C$^3$P-897\ \ \ \ \ \ \ (Short Code:  Makivic:90a)
\par
Spin-$1\over 2$ nearest neighbor Heisenberg antiferromagnet on a square
lattice is studied via a large scale Quantum Monte Carlo simulation.  We
developed a fast and efficient multi-spin coding algorithm on a parallel
supercomputer, based on Suzuki-Trotter transformation.  We performed
high statistics simulations on lattices as large as $128\times 128$
spins, in the temperature range of $0.25J$ to $2.5J$.  We calculated energy,
specific heat, uniform and staggered susceptibility, and staggered
correlation function, from which we deduce the correlation length.  For
temperatures higher than $J$, the results are in excellent agreement
with high-temperature series expansion.  At low temperatures, the long
wavelength behavior is essentially classical.  Our data show that the
correlation length and staggered susceptibility are quantitatively well
described by the renormalized classical picture at 2-loop level of
approximation.  From the divergence of correlation length, we deduce the
value of quantum renormalized spin stiffness, $\rho_s/J = 0.199(2)$.  We
give evidence that the correlation function is of Ornstein-Zernicke
type.  By comparing the largest measured correlation lengths with
neutron scattering experiments on $\rm La_2\,Cu\,O_4$, we deduce the
value of effective exchange coupling $J = 1450\pm 30\,\rm K$.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Highly Parallel Computing and
Modelling of Electron Cyclotron Resonance Plasmas for Diamond Film
Deposition}
\par\noindent
{\bf Vincent McKoy and Yuh-Han Shing}
\par\noindent
C$^3$P-935\ \ \ \ \ \ \ (Short Code:  McKoy:90a)
\par
Electron cyclotron resonance (ECR) microwave plasma enhanced chemical
vapor deposition (PECVD) is an emerging thin film deposition technology
which offers the advantages of high plasma density, high ionization
ratio, and controllable electron and ion energies.  We propose a joint,
theoretical modelling and experimental plasma diagnostics research
program which has the potential of identifying optimized ECR plasma
conditions for diamond film depositions.  Such an accomplishment would
represent a significant benchmark in predictive modelling of processing
plasmas.}
\par
This effort hinges on our development of a highly parallel computational
methodology which allows us to exploit the high-performance,
cost-effective computing of the JPL/Caltech hypercube to determine the
electron impact dissociation cross sections of methane as a function of
energy.  Such dissociation cross sections are known to be critical in
initiating the chemistry of these plasmas.  A knowledge of these cross
sections makes it possible to fine-tune the level of methane
dissociation in the ECR plasmas.
\par
ECR plasma diagnostics experiments will be performed by using a Langmuir
probe to determine the plasma density and the electron temperature.
Optical emission spectroscopy will be employed to monitor the atomic
hydrogen effect on diamond film depositions.  The electron impact
dissociation rates of methane in ECR plasmas can then be modelled with
these calculated cross sections and the measured plasma
characteristics.  The freedom to adjust the ECR plasma parameters and
the knowledge of methane dissociation rates will provide a unique
opportunity for understanding the fundamentals of methane ECR plasmas
and for developing optimized ECR deposition conditions for diamond thin
films.

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf A General Framework for Complex
Time-Driven Simulations on Hypercubes}
\par\noindent
{\bf David L. Meier, Kathleen L. Cloud, Joan C. Horvath, Lynn D. Allan,
Wayne H. Hammond, and Heath A. Maxfield}
\par\noindent
C$^3$P-960\ \ \ \ \ \ \ (Short Code:  Meier:90a)
\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 {\it subcubes\/}
of arbitrary size ({\it task parallelism\/}).  Each subcube runs a
separate application using {\it data parallelism\/} and {\it
synchronous\/} communications internal to the subcube.  Communications
between subcubes are performed with {\it asynchronous\/} messages.
Subcubes can each define their own parameters and commands which drive
their particular application.  These are collected and organized by the
Control Processor (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 ({\it on-board parallelism\/}) as well as the pipelined
floating point processor on each node ({\it 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{\twelvepoint\bf Benchmarking Advanced Architecture
Computers}
\par\noindent
{\bf P. Messina, C. F. Baillie, E. W. Felten, P. G. Hipes, D. W. Walker,
R. D. Williams, W. Pfeiffer, A. Alagar, A. Kamrath, R. H. Leary, and J.
Rogers}
\par\noindent
C$^3$P-712b\ \ \ \ \ \ \ (Short Code: Messina:90a)
\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
\par
\item{(1)}shared-memory bus architecture machines such as the Alliant~FX/8, 
the Encore Multimax, and the Sequent Balance and Symmetry, 
\item{(2)}shared-memory network-connected machines such as the Butterfly, 
\item{(3)}distributed-memory machines such as the NCUBE, Intel and Jet 
Propulsion Laboratory (JPL)/Caltech hypercubes, 
\item{(4)}very long instruction word machines such as the Cydrome Cydra-5, 
\item{(5)}SIMD machines such as the Connection Machine, and 
\item{(6)}``traditional'' supercomputers such as the CRAY~X-MP, CRAY-2, and 
SCS-40.}  
\par
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.
The CRAYs offer the best performance on the benchmark suite;  the 
shared memory multiprocessor machines generally permitted some parallelism, 
and when coupled with substantial floating point capabilities (as in 
the Alliant~FX/8 and Sequent Symmetry), provided an order of magnitude 
less speed than the CRAYs.  Likewise, the early generation hypercubes 
studied here generally ran slower than the CRAYs, but permitted 
substantial parallelism from each of the application codes.

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Computational Efficiency: A Common 
Organizing Principle for Parallel Computer Maps and Brain Maps?}
\par\noindent
{\bf Mark E. Nelson and James M. Bower}
\par\noindent
C$^3$P-863\ \ \ \ \ \ \ (Short Code: Nelson:90a)
\par
It is well-known that neural responses in particular brain regions are
spatially organized, but no general principles have been developed that
relate the structure of a brain map to the nature of the associated
computation.  On parallel computers, maps of a sort quite similar to
brain maps arise when a computation is distributed across multiple
processors.  In this paper we will discuss the relationship between maps
and computations on these computers and suggest how similar
considerations might also apply to maps in the brain.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf A Branch-and-Cut Algorithm for the
Resolution of Large-Scale Symmetric Traveling Salesman Problems}
\par\noindent
{\bf M. Padberg and G. Rinaldi}
\par\noindent
C$^3$P-922.9 \ \ \ \ \ \ \ (Short Code:  Padberg:90a)
\par
We describe an algorithm for solving large-scale instances of the
Symmetric Traveling Salesman Problem (STSP) to optimality.  The core of
the algorithm is a ``polyhedral'' cutting-plane procedure that exploits
a subset of the system of linear inequalities defining the convex hull
of the incidence vectors of the hamiltonian cycles of a complete graph.
The cuts are generated by several identification procedures that we have
described in a companion paper.  Whenever the cutting-plane procedure
does not terminate with an optimal solution the algorithm uses a
tree-search strategy that, differently from branch-and-bound, keeps on
producing cuts after branching.  The algorithm has been implemented in
FORTRAN.  We used two different linear programming (LP) packages as the
LP solver.  We describe the implementation of the algorithm and the
interface with one of the LP solvers in sufficient detail to permit the
replication of our experiments.  We report computational results with up
to 42 STSPs with sizes ranging from 48 to 2,392 nodes.  Most of the
medium-sized test problems are taken from the literature, all others are
large-scale real-world problems.  All of the instances we consider in
our study were solved to optimality by the algorithm in ``reasonable''
computation times.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf An Examination of Finite Element
Formulations and Parameters for Accurate Parallel Solution of
Electromagnetic Scattering Problems}
\par\noindent
{\bf J. W. Parker, R. D. Ferraro, P. C. Liewer}
\par\noindent
C$^3$P-904\ \ \ \ \ \ \ (Short Code:  Parker:90a)
\par
In conjunction with the development of a test bed for finite element
approaches for solving three-dimensional electromagnetic scattering
problems on the JPL/Caltech Mark~IIIfp Hypercube, we have developed
guidelines for choosing parameters which improve accuracy at the cost of
computational resources.  We show results of a series of numerical
experiments through which we can now predict the required mesh density
and the radius of a given type of absorbing boundary which are needed to
obtain virtually any desired degree of accuracy for a given finite
element type.  This type of guideline set is important for
three-dimensional finite element computations, because the number of
unknowns scales as the cube of both the linear node density per
wavelength, and the radius of a spherical absorbing boundary.  We
examine several finite element formulations, including both node- and
edge-based elements, and discuss their relative merits for accuracy vs.
computational resources, ease of parallel implementation, and parallel
efficiency.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Concurrent Implementation of a Fast
Vortex Method}
\par\noindent
{\bf Fran\c cois P\'epin and Anthony Leonard}
\par\noindent
C$^3$P-906\ \ \ \ \ \ \ (Short Code:  Pepin:90a)
\par
Vortex methods are a powerful tool for the numerical simulation of
incompressible flows at high Reynolds number.  They are based on a
discrete representation of the vorticity field and in the inviscid
limit, the computational elements, or vortices, are simply advected at
the local fluid velocity.  The numerical approximations transform the
vorticity equation, a non-linear PDE, into a N-body problem.  The
$O(N^2)$ time complexity usually associated with these problems has
limited the number of computational elements to a few thousands.  This
paper is concerned with the concurrent implementation of fast vortex
methods that reduce the time complexity to $O(N\log N)$.  The fast
algorithm that is used combines a binary tree data structure with high
order expansions for the induced velocity field.  The implementation of
this particular algorithm on an MIMD architecture is discussed.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf TSPLIB --- A Traveling Salesman
Problem Library}
\par\noindent
{\bf Gerhard Reinelt}
\par\noindent
C$^3$P-922.10 \ \ \ \ \ \ \ (Short Code:  Reinelt:90a)
\par
This paper contains the description of a traveling salesman problem
library (TSPLIB) which is mean to provide researchers with a broad set
of test problems from various sources and with various properties.  For
every problem a short description is given along with known lower and
upper bounds.  If computational tests on a problem were published the
corresponding reference is given.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf A Deterministic Annealing Approach to 
Clustering}
\par\noindent
{\bf Kenneth Rose, Eitan Gurewitz, and Geoffrey Fox}
\par\noindent
C$^3$P-857\ \ \ \ \ \ \ (Short Code: Rose:90a)
\par
A deterministic annealing technique is proposed for the nonconvex
optimization problem of clustering.  This method aims at converging to
the global minimum of the given cost function.  A set of temperature
parameterized Gibbs probability density functions relate each data point
to each cluster.  An effective cost function is defined and minimized at
each temperature.  It is shown that as the temperature approaches zero,
the algorithm becomes the K-means algorithm.  The method is independent
of the initial choice of cluster means.  Simulation results are given
and show that the method is not sensitive to local minima.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf A Nonconvex Cost Optimization
Approach to Tracking Multiple Targets by a Parallel Computational
Network}
\par\noindent
{\bf Kenneth Rose, Eitan Gurewitz, and Geoffrey Fox}
\par\noindent
C$^3$P-875\ \ \ \ \ \ \ (Short Code: Rose:90b)
\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 Statistical Mechanics and Phase
Transitions in Clustering}
\par\noindent
{\bf Kenneth Rose, Eitan Gurewitz, and Geoffrey C. Fox}
\par\noindent
C$^3$P-893\ \ \ \ \ \ \ (Short Code: Rose:90c)
\par
A new approach to clustering based on statistical physics is presented.
the problem is formulated as fuzzy clustering and the association
probability distribution is obtained by maximizing the entropy at a
given average variance.  The corresponding Lagrange multiplier is
related to the ``temperature'' and motivates a deterministic annealing
process where the free energy is minimized at each temperature.
Critical temperatures are derived for phase transitions when existing
clusters split.  It is a hierarchical clustering estimating the most
probable cluster parameters at various average variances.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Vector Quantization by Deterministic
Annealing}
\par\noindent
{\bf Kenneth Rose, Eitan Gurewitz, and Geoffrey C. Fox}
\par\noindent
C$^3$P-895\ \ \ \ \ \ \ (Short Code:  Rose:90d)
\par
A deterministic annealing approach is suggested to search for the
optimal vector quantizer given a set of training data.  No prior
knowledge is assumed on the source density, and the principle of maximum
entropy is used to obtain the association probabilities at a given
average distortion.  The corresponding Lagrangian multiplier is
inversely related to the ``temperature'' and is used to control the
annealing process.  In this process the system undergoes a sequence of
phase transitions when existing clusters split.  A hierarchy of
quantizers is obtained, estimating the most probable reproduction values
at various average distortions.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Constrained Clustering as an
Optimization Method}
\par\noindent
{\bf Kenneth Rose, Eitan Gurewitz, and Geoffrey C. Fox}
\par\noindent
C$^3$P-919\ \ \ \ \ \ \ (Short Code:  Rose:90e)
\par
Our deterministic annealing approach to clustering, derived on the basis of 
the principle of maximum entropy, is independent of the initial state, and 
producesv natural hierarchical clustering solutions by going through a 
sequence of phase transitions.  This approach is modified here for a larger 
class of optimization problems by adding constraints to the free energy.  The 
concept of constrained clustering is explained, and three examples are given 
where it is used as means to introduce deterministic annealing.  First, the 
previous clustering method is improved by adding cluster mass variables and a 
total mass constraint.  Secondly, the Travelling Salesman Problem is 
reformulated as constrained clustering, yielding the Elastic Net approach to 
the problem.  More insight is gained by identifying a second Lagrange 
multiplier which is related to the tour length, and can also be used to 
control the annealing process.  Finally, the ``open path'' constraint 
formulation is shown to relate to self-organization and dimensionality
reduction in unsupervised learning.  A similar annealing procedure is 
applicable in this case as well.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Deterministic Annealing, Clustering,
and Optimization}
\par\noindent
{\bf Kenneth Rose}
\par\noindent
C$^3$P-950\ \ \ \ \ \ \ (Short Code:  Rose:90f)
\par
This work introduces the concept of deterministic annealing (DA) as a
useful approach to clustering and other related optimization problems.
It is strongly motivated by analogies to statistical physics, but is
formally derived within information theory and probability theory.  This
approach enables escaping local optima that plague traditional
techniques, without the extremely slow schedules typically required by
stochastic methods.  The clustering solutions obtained by DA are totally
independent of the choice of initial configuration.}
\par
A probabilistic framework is constructed, which is based on the
principle of maximum entropy.  The association probabilities at a given
average distortion are Gibbs distributions parametrized by the
corresponding Lagrange multiplier $\beta$, which is inversely
proportional to the temperature in the physical analogy.  By computing
marginal probabilities within the framework, an effective cost is
obtained, which is minimized to find the most probable set of cluster
representatives at a given temperature.  This effective cost is the free
energy in statistical mechanics, which is indeed optimized at
isothermal, stochastic equilibrium.
\par
Within the probabilistic framework, annealing is introduced by
controlling the Lagrange multiplier $\beta$.  This annealing is
interpreted as gradually reducing the ``fuzziness'' of the
associations.  Phase transitions are identified in the process, which
are, in fact, cluster splits.  A sequence of phase transitions produces
a hierarchy of fuzzy-clustering solutions.  Critical $\beta$ are
computed exactly for the first phase transition and approximately for
the following ones.
\par
Specific algorithms are derivable from the general approach, to address
different aspects of clustering in the large variety of application
fields.  Here, algorithms are derived, and simulation results are
presented for the three major classes, namely, hard clustering, fuzzy
clustering, and hierarchical clustering.  From the experimental results
it appears that DA is substantially superior to traditional techniques.
\par
The last part of the work extends the approach to deal with a larger
family of optimization problems that can be reformulated as constrained
clustering.  A probabilistic framework for constrained clustering is
derived based on the principle of maximum entropy.  It is shown that for
our annealing purpose, the constraint can be directly applied to the
free energy.  Three examples of constrained clustering are discussed.
Mass-constrained clustering is formulated and yields an improvement of
the clustering procedure.  The process is now independent of the number
of representatives and their multiplicity in the clusters.  Secondly,
the travelling salesman problem (TSP) is reformulated as constrained
clustering, yielding the elastic net approach.  A second Lagrange
multiplier is identified, which is used to obtain a more powerful
annealing method.  Finally, self-organization of neural networks is
shown to be closely related to TSP, and a similar annealing method is
suggested.  A fuzzy solution is sought to obtain the optimal net for a
given training data set.

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Statistical Mechanics as the
Underlying Theory of `Elastic' and `Neural' Optimizations}
\par\noindent
{\bf Petar D. Simic}
\par\noindent
C$^3$P-787\ \ \ \ \ \ \ (Short Code: Simic:90a)
\par
There is an interesting connection between two, recently popular,
methods for finding good approximate solutions to hard optimization
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 the 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
`mean-field' 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 have interesting implications for the general problem of mapping
optimization problems to `neural' and `elastic' networks, and suggest a
natural and systematic way to generalize the elastic-net and `neural'
methods to a large class of hard optimization problems.  We derive a new
algorithm of the elastic-net type based on statistical mechanics.  It
has some of the `positive' ingredients of the elastic-net method, yet it
does not have an intrinsic problem (discussed in this paper) of the
original algorithm.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Zipcode:  A Portable Multicomputer
Communication Library atop the Reactive Kernel}
\par\noindent
{\bf Anthony Skjellum, Alvin P. Leung, and Manfred Morari}
\par\noindent
C$^3$P-870\ \ \ \ \ \ \ (Short Code:  Skjellum:90a)
\par
Sophisticated multicomputer applications require efficient, flexible, 
convenient underlying communication primitives.  In the work described here, 
{\it Zipcode,\/} a new, portable communication library, has been designed, 
developed, articulated and evaluated.  The primary goals were:  high 
efficiency compared to lowest-level primitives, user-definable message receipt 
selectivity, as well as abstraction of collections of processes and message 
selectivity to allow multiple, independently conceived libraries to work 
together without conflict.}
\par
{\it Zipcode\/} works atop the Caltech {\it Reactive Kernel,\/} a portable, 
minimalistic multicomputer node operating system.  Presently, the {\it 
Reactive Kernel\/} is implemented for Intel iPSC/1, iPSC/2, and Symult S2010 
multicomputers and emulated on shared-memory computers as well as networks of 
Sun workstations.  Consequently, {\it Zipcode\/} addresses an equally wide 
audience, and can plausibly be run in other environments.

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Concurrent DASSL Applied to Dynamic
Distillation Column Simulation}
\par\noindent
{\bf Anthony Skjellum and Manfred Morari}
C$^3$P-892\ \ \ \ \ \ \ (Short Code: Skjellum:90b)
\par
The accurate, high-speed solution of systems of ordinary
differential-algebraic equations (DAE's) of low index is of great
importance in chemical, electrical and other engineering disciplines.
Petzold's Fortran-based DASSL is the most widely used sequential code
for solving DAE's.  We have devised and implemented a completed new C
code, {\it Concurrent DASSL\/}, specifically for multicomputers and
patterned on DASSL.  In this work, we address the issues of data
distribution and the performance of the overall algorithm, rather than
just that of individual steps.  {\it Concurrent DASSL\/} is designed as
an open, application-independent environment below which linear algebra
algorithms may be added in addition to standard support for dense and
sparse algorithms.  The user may furthermore attach explicit data
interconversions between the main computational steps, or choose
compromise distributions.  A ``problem formulator'' (simulation layer)
must be constructed above {\it Concurrent DASSL\/}, for any specific
problem domain.  We indicate performance for a particular chemical
engineering application, a sequence of coupled distillation columns.
Future efforts are cited in conclusion.}

\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-839b\ \ \ \ \ \ \ (Short Code:  Skjellum:90d)
\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 Numerical Studies in High
Temperature Superconductivity: Band Structure Calculations}
\par\noindent
{\bf B. Szpunar}
\par\noindent
C$^3$P-872\ \ \ \ \ \ \ (Short Code:  Szpunar:90a)
\par
In this article we review the basic ideas of band structure calculations, in 
particular in the area of high temperature superconductivity, and discuss 
results found by our group in some detail.  We also indicate developments in 
computing technology which will be of greatest utility for the more extensive 
calculations to be carried out in future band structure studies.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Parallel Sorting on the Hypercube
Concurrent Processor}
{\bf Tillie Tang}
\par\noindent
C$^3$P-934\ \ \ \ \ \ \ (Short Code:  Tang:90a)
\par
This paper describes a generalized version of a previously published
parallel sort algorithm, ``parallel shell merge''.  This version was
implemented on the JPL/Caltech Mark~III hypercube concurrent processor.
Each node starts out with a sublist of items to be sorted first
internally, and then among the other nodes.  Parallel shell merge is an
algorithm used to produce a whole sorted list across the hypercube once
each sublist is sorted internally.  This version is general in the sense
that it allows sublists of very different sizes to be sorted as well as
being able to handle balanced sublists.  This general version performs
quite well when it is used to sort balanced loads of data; however,
there are some efficiency losses due to the generalization, but they are
acceptable.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Experiments with Multicomputer 
LU-Decomposition}
{\bf Eric Van de Velde}
\par\noindent
C$^3$P-725\ \ \ \ \ \ \ (Short Code:  Velde:90a)
\par
We present a new concurrent LU-decomposition algorithm based on implicit
pivoting of both rows and columns.  This algorithm is, to a large
extent, independent of the distribution of the matrix over the
concurrent processes.  As a result, it can be used in programs with
dynamically varying data distributions.  Another advantage is that most
pivoting strategies are easily incorporated.  We also introduce two new,
intrinsically concurrent, pivoting strategies:  multirow and multicolumn
pivoting.}
\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 Symult 2010 and the iPSC/2 shows
that, for performance considerations, pivoting is equivalent to
randomizing the data distribution.

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Applications of Adaptive Data
Distributions}
\par\noindent
{\bf Eric F. Van de Velde and Jens Lorenz}
\par\noindent
C$^3$P-902\ \ \ \ \ \ \ (Short Code:  Velde:90b)
\par
Continuation methods compute paths of solutions of non-linear equations
that depend on a parameter.  This paper examines some aspects of the
multicomputer implementation of such methods.  The computation is done
on the Symult Series 2010 multicomputer.}
\par
One of the main issues in the development of concurrent programs is load
balancing, achieved here by using appropriate data distributions.  In
the continuation process, a large number of linear systems have to be
solved.  For nearby points along the solution path, the corresponding
system matrices are closely related to each other.  Therefore, pivots
which are good for the LU-decomposition of one matrix are likely to be
acceptable for a whole segment of the solution path.  This suggests to
choose certain data distributions that achieve good load balancing.  In
addition, if these distributions are used, the resulting code is easily
vectorized.
\par
To test this technique, the invariant manifold of a system of two
identical nonlinear oscillators is computed as a function of the
coupling between them.  This invariant manifold is determined by the
solution of a system of non-linear partial differential equations that
depends on the coupling parameter.  A symmetry in the problem reduces
this system to one single equation, which is discretized by finite
differences.  The solution of this discrete nonlinear system is followed
as the coupling parameter is changed.

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Characterizing the Parallel
Performance of a Large-Scale, Particle-In-Cell Plasma Simulation Code}
\par\noindent
{\bf David W. Walker}
\par\noindent
C$^3$P-912\ \ \ \ \ \ \ (Short Code:  Walker:90b)
\par
The efficient implementation of particle-in-cell (PIC) plasma simulation
codes on distributed memory concurrent computers is made difficult by
the conflicting objectives of balancing the computational load and
minimizing interprocessor communication.  This paper surveys previous
work on PIC plasma simulation codes on advanced architecture computers,
identifies the main issues in parallelizing such codes, and discusses
different decomposition schemes.  For MIMD concurrent computers the
adaptive Eulerian (AE) decomposition scheme is attractive because it
seeks to maintain approximate load balance dynamically while avoiding
excessive non-local communication.  The load balance and communication
characteristics of a large-scale AE/PIC code on the hypercube are
investigated by simulating the behavior of the parallel code on a
Cray-2.  The results show that for the three-dimensional problems
studied, in which the particle distribution is highly inhomogeneous, the
communication of data between the particle and mesh decompositions
dominates the communication overhead.  Performing the load balancing may
also make a significant contribution to the concurrent overhead if the
grain size is sufficiently small.  The advantages of the simulation
approach in investigating the behavior of concurrent large-scale
applications are discussed, together with portability and software
engineering issues.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf An Empirical Study of Data
Partitioning and Replication in Parallel Simulation}
\par\noindent
{\bf Frederick Wieland, Lawrence Hawley, and Leo Blume}
\par\noindent
C$^3$P-907\ \ \ \ \ \ \ (Short Code:  Wieland:90a)
\par
Two of the important design decisions in developing a parallel program
are how the data space is to be partitioned and how much data
replication there should be among the various processes.  In this paper,
we propose a strategy for handling data distribution and replication for
the problem of proximity detection in a parallel combat simulation.  The
strategy is compared with similar strategies proposed for other
distributed simulations.  Performance results are presented using JPL's
Time Warp Operating System with 70 processors on a BBN Butterfly
GP1000.  It is found that this distributed proximity detection algorithm
generalizes well and has acceptable performance.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Performance of a Distributed 
Unstructured-Mesh Code for Transonic Flow}
\par\noindent
{\bf Roy D. Williams}
\par\noindent
C$^3$P-856\ \ \ \ \ \ \ (Short Code: Williams:90a)
\par
An algorithm has been implemented for calculation of steady solutions of
the two-dimensional Euler equations using an unstructured 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.}
\par
In this paper I present execution times for the code using different
numbers of processors on three distributed memory machines, being a
Meiko computing Surface with 32 processors, an NCUBE with 256 processors
and a Symult S2010 with 192 processors.  For comparison purposes I also
present timings for the CRAY~Y-MP, using one processor.

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Hypercube Simulation of Electric
Fish Potentials}
\par\noindent
{\bf Roy D. Williams, Brian Rasnow, and Christopher Assad}
\par\noindent
C$^3$P-869\ \ \ \ \ \ \ (Short Code: Williams:90c)
\par
We present a simulation of the electrosensory input of the weakly
electric fish {\it Apteronotus leptorhynchus\/}.  This fish senses its
environment by producing a sinusoidal voltage difference between its
body and tail sections, causing an electric field and a current
distribution in the surrounding water.  If an object is nearby which has
different electrical conductivity from the surrounding water, the current
distribution is disturbed on the skin of the fish.  The fish senses this
difference from the usual current distribution, and infers the presence
and location of the object.}
\par
Mathematically, the problem is to solve a potential equation in the
domain exterior to the fish with Cauchy boundary conditions, in the
presence of an induced dipole arising from the object, and extract the
potential difference across the fish skin.
\par
We have created an unstructured triangular mesh covering the
two-dimensional manifold of the fish skin, using the Distributed
Irregular Mesh Environment (DIME), then used the Boundary Element Method
to solve for the potential derivative at the fish skin.
\par
The computational problem is the solution of a full set of simultaneous
linear equations, where there is an equation for each node of the
boundary mesh, typically about 100--200.  We have used an NCUBE
hypercube to calculate the matrix elements and solve these equations,
once for each relative position of the fish and the test object.  We
present some early results from the simulation.

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Performance of Load Balancing
Algorithms for Unstructured Mesh Calculations}
\par\noindent
{\bf Roy D. Williams}
\par\noindent
C$^3$P-913 \ \ \ \ \ \ \ (Short Code:  Williams:90d)
\par
In a finite element mesh has a sufficiently regular structure, it is
easy to decide in advance how to distribute the mesh among the
processors of a distributed-memory parallel processor, but if the mesh
is unstructured, the problem becomes much more difficult.  The
distribution should be made so that each processor has approximately
equal work to do, and such that communication overhead is minimized.}
\par
If the mesh is solution-adaptive, i.e., the mesh and hence the load
balancing problem change discretely during execution of the code, then
it is most efficient to decide the optimal mesh distribution in
parallel.  In this paper three parallel algorithms, Orthogonal Recursive
Bisection (ORB), Eigenvector Recursive Bisection (ERB) and a simple
parallelization of Simulated Annealing (SA) have been implemented for
load balancing a dynamic unstructured triangular mesh on 16 processors
of an NCUBE machines.
\par
The test problem is a solution-adaptive Laplace solver, with an initial
mesh of 280 elements, refined in seven stages to 5772 elements.  We
present execution times for the solver resulting from the mesh
distributions using the three algorithms, as well as results on
imbalance, communication traffic and element migration.
\par
The load balancing itself is fastest with ORB, but a very long run of SA
produces a saving of 21\% in the execution time of the Laplace solver.
ERB is only a little slower than ORB, yet produces a mesh distribution
whose execution time is 15\% faster than ORB.

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Express:  Portable Parallel
Programming}
\par\noindent
{\bf Roy D. Williams}
\par\noindent
C$^3$P-944\ \ \ \ \ \ \ (Short Code:  Williams:90e)
\par
We present an overview of the ParaSoft Express parallel programming system: 
its paradigm, capabilities, communication methods and the latest extensions.
We present measurements of communication parameters and timings for an LU
decomposition benchmark. These were measured on an 8-processor CRAY~X-MP, a
128-processor Intel iPSC/860, a 512-processor Ncube/1 and a 4-processor 
network of Sun Sparcstations.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Quantum Mechanical Reactive Scattering 
using a High-Performance Distributed-Memory Parallel Computer}
\par\noindent
{\bf Yi-Shuen Mark Wu, Steven A. Cuccaro, Paul G. Hipes, and Aron Kuppermann}
\par\noindent
C$^3$P-860\ \ \ \ \ \ \ (Short Code: Wu:90a)
\par
We have performed accurate three-dimensional quantum mechanical reactive
scattering calculations for the $\rm H+H_2$ system on the Caltech/JPL
Mark~IIIfp 64 processor hypercube, using the method of symmetrized
hyperspherical coordinates and local hyperspherical surface functions.
The results and timing obtained demonstrate that such distributed memory
parallel architectures are competitive with the CRAY~X-MP, CRAY~2 and
CRAY~Y-MP supercomputers and should allow the study of larger, more
complicated chemical systems.  In addition, we show that a selection
rule for scattering resonances developed previously and tested for
$J=0,1$ resonances is also satisfied by the $J=2$ resonances obtained in
the present calculations.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Test Suite and Performance for
Fortran90 Compilers}
\par\noindent
{\bf Min-You Wu and Geoffrey Fox}
\par\noindent
C$^3$P-947\ \ \ \ \ \ \ (Short Code: Wu:90b)
\par
We summarize the status of our project to build a test suite of
applications for the FortranD Compiler Project.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf An Outline of Fortran90 Compiler for
Distributed Memory Systems}
\par\noindent
{\bf Min-You Wu and Geoffrey Fox}
\par\noindent
C$^3$P-948\ \ \ \ \ \ \ (Short Code:  Wu:90c)
\par
This outline briefly describes the basic issues of a Fortran90 compiler
for distributed memory systems.  We discuss compiler directives, data
partitioning and sequentialization, the techniques for the active area,
communication insertion, and implementation of intrinsic functions.  We
also introduce some basic optimization techniques.  This outline does
not cover all aspects of the compiler, neither the details of
implementations.  Some primitive transformations are discussed without
formal description.}

\end
