\input /home/swan/joann/macros/setup
\baselineskip=14pt
\vsize=9.25truein
\hoffset=-.2truecm
\tolerance=10000
\def\starline{\hbox to \hsize{* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *}}
\centerline{\fourteenpoint\bf California Institute of Technology}
\smallskip
\centerline{\fourteenpoint\bf C$^3$P Reports}
\smallskip
\centerline{\fourteenpoint\bf January 1 -- December 31, 1987}
\bigskip
\bigskip
\bigskip\starline\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
$\rm C^3P-468$\ \ \ \ \ \ \ (Short Code:  Aloisio:87a)
\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 $\rm 120\,ms$ to compute the DFT of 5040 complex points
using 32 nodes of Caltech-JPL Mark~III Hypercube.  It took $\rm 105\,ms$
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 QCD and Neural Nets on the Hypercube}
\par\noindent
{\bf A. Kolawa, J. Apostolakis, C. F. Baillie, H. Ding, J. Flower, G. C.
Fox, W. Furmanski, S. Otto, and R. Gupta}
\par\noindent
$\rm C^3P-467$\ \ \ \ \ \ \ (Short Code:  Apostolakis:87a)
\par
We contrast the use of the hypercube concurrent computer on two
different problem classes.  The first is a regular Monte Carlo; the
study of Quantum Chromodynamics (QCD) theory of the strong interaction
between fundamental particles.  The second is an irregular time
evolution of a neural network; we discuss the general theory for
arbitrary interconnects showing how different approached are optimal as
a function of the spareness and regularity of the networks.  The
generality of the hypercube for scientific computations is illustrated
by its success on these very different problems.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf CrOS III on Ncube --- The Limits}
\par\noindent
{\bf Clive Baillie and Jon Flower}
\par\noindent
$\rm C^3P-492$\ \ \ \ \ \ \ (Short Code: Baillie:87b)
\par
This is (hopefully) the last memo about CrOS~III on the Ncube.
Previously, we have outlined the implementatio of CrOS~III (and Cubix)
on the Ncube [$\rm C^3P-432$] and described a library of fast functions
to go with it [$\rm C^3P-434$].  Here, we will specify the various
limits associated with our implementation of CrOS~III (both Fast and
Slow) on the Ncube.}

*********************
\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Benchmarking Concurrent
Supercomputers}
\par\noindent
{\bf Clive F. Baillie and Edward W. Felten}
\par\noindent
$\rm C^3P-$\ \ \ \ \ \ \ (Short Code:  )
\par
}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Optimizing with a Distributed-Memory
Parallel Processor}
\par\noindent
$\rm C^3P-465$\ \ \ \ \ \ \ (Short Code:  Barajas:87a)
\par
We consider the minimization of a global cost function by many
independent processing elements.  Each processor may independently make
a potentially beneficial change, but taken together the changes may be
detrimental.  This phenomenon we call a parallel collision.  We consider
several algorithms for avoiding these collisions, which are variants on
a greedy algorithm and on simulated annealing.  Our test-bed is a graph
coloring problem derived from the design of a load-balancer for a
parallel processor.  We conclude that special parallel variants improve
performance considerably in some cases.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Caltech Lattice QCD Program
Conversion from Parallel C to Parallel Fortran for Performance
Comparisons}
\par\noindent
{\bf Kenneth Barish}
\par\noindent
$\rm C^3P-471$\ \ \ \ \ \ \ (Short Code:  Barish:87a)
\par
As a way to compare different parallel machines for actual scientific
problems, we have undertaken a project of adapting the Caltech Lattice
QCD program for different machines and benchmarking the performance.}
\par
The Lattice QCD program was written to take advantage of the computing
power of parallel computers with hypercube architecture to do these CPU
intensive physical calculations.  Quantum Chromo-Dynamics (QCD) is a
gauge theory description of the strong interactions of quarks and
gluons, the fundamental constitutents of elementary particle physics.
The theory allows calculations at high energies of these interactions by
perturbation techniques.  Unforotunately, most experimental data are
only available at low energies where these techniques are not valid.  An
alternative approach is to calculate the effects by representing the
space-time continuum on a lattice.  The physics results attainable with
this technique are limited by the size and power of the computers.  In
particular, for parallel machines, the limits are the number of nodes,
the power of each node, and the parallel efficiency of the program.
This study is aimed at helping determine which computers are best to
expand for performing more ambitious physics calculations.
\par
The code for the Lattice QCD program was originally written in C for the
hypercubes, and so far, it has been benchmarked for computers that use
that language (NCUBE, Intel, Caltech/JPL Mark~I, II, III).  The
motivation for my work in translating the program to Fortran has been to
extend the comparison of machines to different machines (e.g., the
Sequent Balance and CRAY).  I have made this translation to Fortran.
Also, as a part of the program of comparing machines, I have studied the
performance of this program on the Sequent Balance machine at Argonne
National Labs.  (The program will be benchmarked on the CRAY by people
at SDSC.)  Although the Balance uses C as well as Fortran, the Fortran
version allows us to parallelize the program by using parallel DO loops.

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

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Hypercubes are General-Purpose
Multiprocessors}
\par\noindent
{\bf Marina Chen, Erik DeBenedictis, Geoffrey C. Fox, Jingke Li, and
David W. Walker}
\par\noindent
$\rm C^3P-499$\ \ \ \ \ \ \ (Short Code: Chen:87a)
\par
This is a submission for the Gordon Bell Aware for multiprocessor speedup
in the general purpose category.  The entry is for the hypercube
architecture.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Hyperswitch Network for the
Hypercube Computer}
\par\noindent
{\bf E. Chow, H. Madan, J. Peterson, D. Grunwald, and D. Reed}
\par\noindent
$\rm C^3P-484$\ \ \ \ \ \ \ (Short Code:  Chow:87a)
\par
The performance of a parallel algorithm depends in a large part on the
interconnection topology of the multicomputer system.  The method
presented in this paper realizes a kind of interconnection network,
called a hyperswitch network, that is achieved using a mixture of static
and dynamic topologies.  Here, available or fault free paths need not be
specified by a source because the routing header can be modified in
response to congestion or faults encountered as a path is established.
This method can be accomplished in a static topology such as the
hypercube network if the nodes have switching elements which are capable
of performing the necessary routing header revisions dynamically.
Detailed simulation results show that the hyperswitch network is
consistently more efficient than fixed path routing for large message
traffic conditions.  The simulation results also show that the
hyperswitch network has equivalent latency overhead for messages with
localized and antilocal destinations (i.e., less than a 25\% difference
between diameter 1 and 5).}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Profiling C Programs on the NCUBE}
\par\noindent
{\bf Rob Fatland and Rod Morison}
\par\noindent
$\rm C^3P-456$\ \ \ \ \ \ \ (Short Code:  Fatland:87a)
\par
Optimizing C code on the NCUBE can be facilitated by determining what
percentage of the total execution time is spent by each of the program
subroutines.  Examining the program's execution profile on each of the
nodes gives a clear picture of load balancing and reveals any
excessively time consuming subroutines.  By linking a profiling library
to node object files and calling the appropriate bookkeeping routines,
programs written for vertex, cubix, or icubix on the NCUBE can be
profiled to fairly good accuracy.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf A Guide to Debugging with NDB}
\par\noindent
{\bf Jon Flower}
\par\noindent
$\rm C^3P-489$\ \ \ \ \ \ \ (Short Code: Flower:87c)
\par
NDB is a symbolic, assembly level debugger for the hypercube nodes.  But
what does this mean to you, the user?  Before getting into the dirty
details of what you do to make it work, it is porbably best to just
summarize what it can and (more importantly) can't do.}
\par
The word {\it symbolic\/} means that NDB knows about the variables and
subroutines in your program by name.  You don't have to go scrabbling
around in some large hex dump to find the addresses of your variables
(although you can do this if you're that way inclined).
\par
The word {\it debugger\/} means pretty much nothing.  However, it does
have certain associated concepts that one has come to expect of
debuggers.  For example, one wants to be able to print out data, find
out where the program has got to and run interactively with
breakpoints.  NDB can do all of these things.  Furthermore, NDB can do
them on arbitrary collections of hypercube nodes---this is why it is a
hypercube debugger.
\par
The words {\it assembly level\/} in the announcement are the problem.
Basically, this means that NDB doesn't really understand the Fortran or
C source code that you typed, but only the assembly code that the
compilers produced.  This means, for instance, that to insert a
breakpoint you have to find the appropriate place in the assembly code,
rather than just saying ``Stop at line 13 in noddy.c''.  While this
seems to be a severe restriction at first, it isn't necessarily so since
many of the useful debugger operations can be performed without
breakpoints.  Furthermore, NDB does know a certain amount about your
source code so that when it tells you where the program has got to it
also tries to tell you what line of the source corresponds to this
location---agreed this is no substitute for the real thing, but at least
it tries!!
\par
Having described what the various words in the statement of NDB mean and
their ramifications, there seems no alternative but to describe how you
go about it.  What follows is an introduction to the various
possibilities available.  It is not an exhaustive list---for that you
should consult the manual page which is attached as an appendix to this
document.  However, we try to at least demonstrate one flavor of all the
commands in the hope that those similar which are left out can be
understood.
\par
This sytem is implemented on both the XENIX and AXIS systems.  The
differences between the two operating systems unfortunately mean that
some of NDB's features are not available on some systems.  Typically, we
have tried to indicate where this is so in the text by means of
footnotes.

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Debugging Aids on the NCUBE}
\par\noindent
{\bf Jon Flower}
\par\noindent
$\rm C^3P-491$\ \ \ \ \ \ \ (Short Code: Flower:87d)
\par
Debugging is one of those topics, like politics and religion, that
should only be addressed with friends.  Everyone cherishes the firm
belief that as they get older and more experienced, their codes will
have less bugs which will be easier to find until the ultimate goal is
reached and one automatically generates ``bug free'' code.  Wish on.}
\par
This article is about debugging.  Even worse, it is about debuggin on a
parallel computer---that mysterious black box which silently consumes
source code and leaves one with the hopeful feeling that when nothing
emerges, it's just because the program is running a little slower than
expected rather than the dreaded ``hang''.
\par
It is probably safe to say that no-one knows how to debug codes on
parallel machines.  The problems are different from those encountered on
sequential computers in strange and horrible ways.  Asynchronous
distributed codes have their own kind of bug whose most unpleasant
feature is the fact that it only happens once in every fifteen runs and
then goes away completely every time you try to track it down.
\par
Having said this we are about to discuss a set of tools, implemented on
the NCUBE, which are designed to find bugs.  ``Designed'' is probably
too strong a word.  Most of the utilities described cam about in a
desperate struggle to find some obscure problem---some of them worked
and others did not.
\par
The basic division of this paper is into four sections.  The first
describes the fairly simple things that one can do within the CUBIX
framework.  The second discusses the RAM file implemented in CUBIX which
allows data to be preserved across calls to the machine initialization
function {\tt ninit}.  These two sections are particular to CUBIX.  In
contrast, the last two describe facilities which are available to all
NCUBE programs.  The first of these is a simple data monitoring
capability and the last section describes a new interactive debugger
which was specifically designed for the debugging of loosely synchronous
codes.  Only a brief introduction is given and the interested reader is
referred to the companion paper, {\it An Introduction to Debugging with
NDB}, $\rm C^3P-489$.
\par
The author claims no responsibility for most of these tools irrespective
of whether or not they are helpful.  Many people spent ``years'' of
their lives developing these systems and all credit is due them.

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

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf The Caltech Concurrent Computation
Program Annual Report 1986--1987}
\par\noindent
{\bf Geoffrey C. Fox and Paul Messina}
\par\noindent
$\rm C^3P-487$\ \ \ \ \ \ \ (Short Code:  Fox:87c)
\par
We survey the research of the Caltech Concurrent Computation Program
($\rm C^3P$) in the period covering approximately September 1, 1986 to
October 30, 1987.  $\rm C^3P$ is an integrated multi-disciplinary
research effort centered on the study of parallel systems and the
hypercube, in particular.  The research covers areas of computer
systems, hardware, software, and algorithms but we emphasize an
application based point of view.  In the future, we see a growing
importance in the areas of software tools, supercomputing for a broad
range of architectures, and neural networks.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Piriform (Olfactory) Cortex Model on the 
Hypercube}
\par\noindent
{\bf W. Furmanski, J. M. Bower, M. E. Nelson, M. A. Wilson, and G. C. Fox}
\par\noindent
$\rm C^3P-404b$\ \ \ \ \ \ \ (Short Code:  Furmanski:87a)
\par
We present a concurrent hypercube implementation of a neurophysiological model 
for the piriform (olfactory) cortex.}
\par
The project was undertaken as the first step towards constructing a general 
neural network simulation on the hypercube, suitable both for applied and 
biological nets.
\par
The method presented here is expected to be useful for a class of complex and 
computationally expensive network models with long range connectivity and non-
homogeneous activity patterns.  The hypercube communication for the fully 
interconnected case is efficiently realized by the {\it fold\/} algorithm, 
constructed previously for problems in concurrent matrix algebra whereas the 
patchy activity is successfully load balanced by the scattered decomposition.  
We discuss also briefly other communication strategies, relevant for sparse 
and variable connectivities.
\par
Sample numerical results presented here were derived on the NCUBE hypercube at 
Caltech.

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf CALTRAX: The Tracking Program for
Simulation-87}
\par\noindent
{\bf Thomas D. Gottschalk}
\par\noindent
$\rm C^3P-478$\ \ \ \ \ \ \ (Short Code:  Gottschalk:87a)
\par
This document provides a brief overview of the multiple-target,
multiple-sensor tracking program CALTRAX included in the $\rm BM/C^3$
demonstration (Simulation-87) prepared by Caltech campus/JPL for the
U.S. Air Force Electronic Systems Division.  This program is designed to
provide estimates of launch vehicle parameters which are subsequently
used by the battle management module of Simulation-87.  The discussions
in this note are brief and qualitative, with essentially all details
relegated to the three companion papers in this documentation package.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Precision Filters for Boost Phase
Tracking}
\par\noindent
{\bf Thomas D. Gottschalk}
\par\noindent
$\rm C^3P-479$\ \ \ \ \ \ \ (Short Code:  Gottschalk:87b)
\par
Filter prescriptions are presented for the estimation of launch
parameters for targets traveling along deterministic trajectories.
Three specific filter modesl are considered: a 3-Stage filter model for
tracking from a geostationary sensor, a conventional extended Kalman
filter for geostationary tracking, and an extended Kalman filter for
tracking from a low earth orbit sensor.  Parameter estimation results
from Monte Carlo simulations are presented for these tracking
algorithms, and relative merits of the different schemes are examined.
A hybrid tracking prescription, combining the speed of the GEO extended
Kalman filter and the robust initialization behavior of the 3-Stage
filter model, is briefly discussed.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf A New Multi-Target Tracking Model}
\par\noindent
{\bf Thomas D. Gottschalk}
\par\noindent
$\rm C^3P-480$\ \ \ \ \ \ \ (Short Code:  Gottschalk:87c)
\par
This note describes the new multi-target tracking formalism used as part
of the Caltech campus/JPL hypercube $\rm BM/C^3$ demonstration for the
Air Force Electronic Systems Division (ESD).  An effective formalism for
processing multi-target threats is developed.  Key elements include: i)
a batch-mode processor which can initiate new tracks at any time during
threat evolution, ii) a kinematic flocal plane tracker which solves the
track$\leftrightarrow$hit association problem without prior knowledge
assumptions on the nature of the underlying trajectories, and iii) a
precision tracking package which provides launch parameter estimates to
be used by other $\rm BM/C^3$ functions.  An efficient hypercube
implementation of the tracking prescription is presented, and initial
stereo processing capabilities are demonstrated.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Concurrent Stereo Tracking and the
Assignment Problem}
\par\noindent
{\bf Thomas D. Gottschalk}
\par\noindent
$\rm C^3P-481$\ \ \ \ \ \ \ (Short Code:  Gottschalk:87d)
\par
This work presents extensions of the Simulation-87 multi-target tracking
algorithm to include stereo processing using tracking results from two
(geostationary) sensors.  The basic prescription for correlating and
combining track parameter estimates from two sensors is briefly
reviewed.  The central issue in full-scale stereo processing---the
correlation of (large) track files from two sensors---is discussed in
detail, and an efficient implementation of a modified nearest-neighbor
formalism is presented.  The task of integrating the tracking module
with other components of the full Simulation-87 demonstration is
discussed, and the primary `report' prepared by the tracking module is
described in detail.  Concurrent implementations of the stereo
processing and report functions are presented.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Performance of Vortex Flow
Simulations on the Hypercube}
\par\noindent
{\bf K. Harstad}
\par\noindent
$\rm C^3P-500$\ \ \ \ \ \ \ (Short Code: Harstad:87a)
\par
Performance times on the Mark~III Hypercube were measured for the
problem of vortex element simulation of turbulent flow.  Excellent load
balancing and high speedup efficiencies were demonstrated.  With future
use of a Weitek vector floating point unit at the nodes, it is projected
that a 128 node system will rival a Cyber 205 vector computer in
computation speed for this type of problem.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Plasma Particle Simulations on the
Mark~III Hypercube}
\par\noindent
{\bf P. C. Liewer, V. K. Decyk, J. Dawson, and G. C. Fox}
\par\noindent
$\rm C^3P-460$\ \ \ \ \ \ \ (Short Code:  Liewer:87a)
\par
Plasma particle simulations are used extensively for the study of
nonlinear phenomena in both space and laboratory plasmas.  Here, a
well-benchmarked plasma simulation code has been implemented on the
32-node JPL Mark~III hypercube to study the applicability of parallel
architecture to particle simulation models.  In the sequential version
of the code, about 90\% of the computation time is spent updating the
particle positions and velocities.  When implemented in parallel on
Mark~III Hypercube, this part of the code was sped up by a factor of
about 27 (83\% efficiency).  Computation times on the Mark~III have also
been compared with times on a variety of other computers.}

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Advanced Computer Architectures}
\par\noindent
{\bf Geoffrey C. Fox and Paul C. Messina}
\par\noindent
$\rm C^3P-476$\ \ \ \ \ \ \ (Short Code:  Messina:87a)
\par
Conventional computers attack problems one step at a time.  Advanced
computers are able to do several parts of the problem at once, just as a
team of workmen might divide a task to complete it more quickly.}
\par
Parallel processing, in which a single computing task is divided among
several processors (units that do coputational work), is exemplified by
this board from an NCUBE computer.  Each of the 64 brown squares is a
processor that has roughly the power of a VAX~11/750 minicomputer.  The
black rectangles are memory units; six of them (totaling half a megabyte
of memory) are dedicated to each processor.  The computer into which
this board fits may have from one to 16 such boards (or as many as 1,024
processors) in addition to a host board, which contains a master
processor that distributes work and data to the other processors.  This
computer represents a middle ground in parallel processing.  Some
parallel systems include fewer but more powerful processors (the
CRAY~X-MP, in a certain configuration, consists of four supercomputers
linked in parallel), whereas others include a greater number of less
sophisticated processors (the Connection Machine can include 65,536 very
simple processors).

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Solving Finite Element Equations on
Concurrent Computers}
\par\noindent
{\bf B. Nour-Omie, A. Raefsky, and G. Lyzenga}
\par\noindent
$\rm C^3P-463$\ \ \ \ \ \ \ (Short Code:  Nour-Omid:87b)
\par
This paper discusses the development of a concurrent algorithm for the
solution of systems of equations arising in finite element
applications.  The approach is based on a hybrid of direct elimination
method and preconditioned conjugate iteration.  Two different
preconditioners are used; diagonal scaling and a concurrent
implementation of incomplete LU.  First, an automatic procedure is used
to partition the finite element mesh into sub-structures.  The
particular mesh partition is chosen to minimize an estimate of the cost
for evaluating the solution using this algorithm on a concurrent
computer.  These procedures are implemented in a finite element program
on the JPL/Caltech Mark~III hypercube computer.  An overview of the
structure of this program is presented.  The performance the solution
method is demonstrated with the aid of a number of numerical test runs,
and its advantages for concurrent implementations are discussed.
Efficiency and speed-up factors over sequential machines for the
numerical examples are highlighted.}

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

\bigskip\starline\bigskip
\vbox{\par\noindent{\twelvepoint\bf Three Dimensional Plots by the
Painter's Algorithm}
\par\noindent
{\bf Roy Williams}
\par\noindent
$\rm C^3P-455$\ \ \ \ \ \ \ (Short Code:  Williams:87c)
\par
The so-called painter's algorithm is a fast and easy method of drawing a
picture of a set of polygons.  The polygons are distributed in
three-dimensional space and are projected to the two-dimensional picture
plane and then drawn.  The painter's algorithm consists of doing this
with firstly the polygons being not only drawn but filled, and secondly
the polygons being drawn in an order such that if several projected
polygons intersect, then they are drawn in order of distance from the
viewer.  Thus the furthest polygon is drawn first and the nearest drawn
last.  The ability of the rendering hardware to fill polygons obviates
the need for a complex hidden-line removal as would be the case for a
pen plotter.}
\par
The painter's algorithm makes mistakes, because it may not be possible
to sort the polygons in the way mentioned above: this can be seen by
taking three sheets of paper $A$, $B$, $C$, and laying $A$ partly over
$B$, $B$ partly over $C$, $C$ partly over $A$.  In the software
described below, the sorting key is the distance of the center of the
polygon from the viewer: it may be that the center of $A$ is behind the
center of $B$, but $A$ hides $B$.  Often, however, the painter's
algorithm makes no such mistakes, so that its simplicity and speed make
it useful.

