C3P-689 [Alkalaj:88a]
"The Use of Parallel Logic Programming in CAD/CAM Applications"
L. Alkalaj and A. H. Bond

A study of the use of concurrent prolog for programming intelligent CAD/CAM 
systems is reported.

The work has implications for CAD/CAM workstation design, specification 
languages for CAD/CAM, and CAD/CAM programming methodology.

Intelligent CAD/CAM functions were defined by exergesis from an existing set 
of intelligent CAD/CAM functions written in Prolog.

Two of these, viz.
\item{1.}Global satisfaction of constraints over a geometric structure.
\item{2.}Layered feature generation

were analyzed, and parallel logic programming descriptions of them designed.  
These descriptions used the powerful programming techniques possible in 
Concurrent Prolog.  They were implemented in Flat Concurrent Prolog and run on 
a serial computer.

The main conclusion reached was that parallel programming techniques, possible 
in Concurrent Prolog, are very suitable for programming of intelligent CAD/CAM 
functions, and lead to succinct, understandable and efficient programs.

Therefore, a promising potential strategy for providing intelligent CAD/CAM 
workstations is to use a parallel workstation, and Concurrent Prolog.


C3P-679 [Amaldi:88a]
"Stability-Capacity Diagram of a Neural Network with Ising Couplings"
E. Amaldi and S. Nicolis

The stability-capacity diagram of a fully connected neural network, whose 
couplings take the values 1 and $-1$ with equal probability, is determined 
numerically.  Two different optimization methods (simulated annealing and tabu 
search) are used and their relevant features are discussed.  Clear evidence of 
replica symmetry breaking is found.


C3P-654 [Angus:88b]
"NSIM: A Hypercube Simulator"
Ian G. Angus

We describe a software package that provides a simulated environment for 
development and execution of applications on a Hypercube.  The provided 
software is specialized to a Hypercube running the CrOS3 operating system; 
however, we will indicate how one can implement a wide variety of alternative 
topologies and/or operating systems.  A number of utilities are also provided 
to help enhance the user's productivity.  This version of the simulator runs 
under either UNIX or under VMS.


C3P-530 [Baillie:88b]
"A Comparison of the CM with the DAP for Lattice Gauge Theory"
Clive F. Baillie and G. Stuart Pawley

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


C3P-606 [Fox:88d]
"Problems and Approaches for a Teraflop Processor"
Alexander H. Frey and Geoffrey C. Fox

This paper discusses problems associated with designing a processor capable of 
sustaining a teraflop ($10^{12}$ floating point operations per second) of 
processing power.  Several researchers have speculated on achieving this 
performance.  The technical problems of a practical design are shown to be 
formidable.  However, none of these problems requires a technology 
breakthrough for their solution.  The predictable advances of the next 
generation of technology together with a major engineering effort is all that 
will be required to build such a parallel machine with usable teraflop 
processing power.


C3P-602 [Tuazon:88a]
"Mark IIIfp Hypercube Concurrent Processor Architecture"
J. Tuazon, J. Peterson, and M. Pniel

The Mark~IIIfp Hypercube is a new generation of hypercube concurrent processor 
system developed at JPL/Caltech, with peak performance of 5~Mips, 14~Mflops 
per node, and a peak communication rate of 6~Mbytes per second.  Each node 
utilizes two Motorola MC68020 microprocessors, an MC68882 scalar floating- 
point coprocessor, and a Weitek 8000 floating-point chip set.  One of the 
MC68020 processors serves as the application and computational processor, the 
other is dedicated to communication.  The three processors are interconnected 
through a common system bus and share 4~Mbytes of dynamic memory.  Each 
processor has his own fast local memory, which increases parallelism, 
minimizes shared memory referencing, reduces memory contentions and improves 
system performance.


C3P-584 [Chiu:88d]
"A Parallel Computer for Lattice Gauge Theories"
Ting-Wai Chiu

A parallel computer especially designed for the calculations in lattice gauge 
theories is proposed.  The final device will contain 256 nodes running in MIMD 
mode with a computational power abaout one billion 32-bit floating point 
operations per second.  Each node is controlled by the Motorola 68020/68882 
microprocessors, (the Weitek floating-point processors) and two megabyte 
static RAM.  The architecture is designed to allow rapid execution of the 
numerically intensive calculations in lattice gauge theories.  In this paper, 
we outline the hardware and software design of the first four nodes which have 
been built and tested.


C3P-587 [Ho:88a]
"PC-CUBE, the IBM PC-based Hypercube"
Alex Ho, Geoffrey Fox, David Walker, Scott Snyder, Douglas Chang, 
Stanley Chen, Matt Breaden

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


C3P-573 [Ho:88d]
"MAC-CUBE, The Macintosh-Based Hypercube"
Alex Ho, Geoffrey Fox, David Walker, Matt Breaden, Stanley Chen, Allen 
Knutson, Sho Kuwamoto, and Terry Cole

The MAC-CUBE is a Macintosh-based hypercube.  It uses Appletalk hardware and 
software as the medium for the nodal connections.  At the physical level 
Appletalk has a bus topology.  Hypercube connectivity is emulated on the 
Appletalk local area network while the hypercube communication protocol is 
integrated in the Appletalk software.  Available for MAC-CUBE is the 
Crystalline Operating System~III (CrOS III).  MAC-CUBE provides a programming 
environment similar to any other hypercube systems running CrOS~III.  It 
allows inexpensive hands-on experience with a concurrent machine.  Data can be 
displayed on graphics monitor and/or stored locally at each node.  In addition 
to the low cost, these capabialities of the Mac-Cube makes it an indepensable 
instructional and development tool for parallel processing.  Some application 
programs which are taken from the book, "Solving Problems on Concurrent 
Processors" [Fox:88a] have been implemented with graphics enhancement on Mac-
Cube.  The applications are solving the Mandelbrot set in the complex plane, 
and solving a two-dimensional Laplace equation using finite difference.


C3P-568 [Baillie:88f]
"Comparisons of Concurrent Tracking on Various Hypercubes",
C. F. Baillie, T. D. Gottschalk, and A. Kolawa

The concurrent multi-target tracking code is ported to and run on the Intel 
iPSC and Ncube hypercubes.  The (minor) difficulties in this porting are 
noted.  The biggest single problem in running the tracking program is found to 
be the rather limited node memories on the iPSC and Ncube machines.  Timing 
results for the analysis of a sample threat on the iPSC,  Ncube and Mark~III 
hypercubes are presented.  The relative performances of the various machines 
are found to be consistent with prior expectations.  A fairly large sample 
scenario is investigated using 4 through 8-dimensional Ncube configurations, 
and variations of Ncube performance for differing levels of CrOS porting are 
examined.  Initial results of running the tracking program on the BBN 
Butterfly are also presented.


C3P-569 [Baillie:88c]
"Comparing Communication in Concurrent Processor Operating Systems"
Clive F. Baillie

I have developed a simple program which exercises communication in concurrent 
processor operating systems.  It allows comparison of both the programming 
model used in the operating system and the efficiency of its implementation.  
I have run this program with both loosely synchronous and multi-tasking 
operating systems on the Caltech/JPL Mark~II Hypercube and the BBN Butterfly.


C3P-511 [Walker:88g]
"Performance Evaluation of Scientific Programs on Advanced Architecture 
Computers"
D. W. Walker, Paul Messina, and Clive F. Baillie

Recently a number of advanced architecture machines have become commercially 
available.  These new machines promise better cost-performance then 
traditional computers, and some of them have the potential of competing with 
current supercomputers, such as the CRAY~X-MP, in terms of maximum 
performance.  This paper describes an on-going project to evaluate a broad 
range of advanced architecture computers using a number of complete scientific 
application programs.  The computers to be evaluated include (1) distributed-
memory machines such as the NCUBE, INTEL and Caltech/JPL hypercubes, and the 
MEIKO computing surface, (2) shared-memory, bus architecture machines such as 
the Sequent Balance and the Alliant, (3) very long instruction word machines 
such as the Multiflow Trace 7/200 computer, (4) ``traditional'' supercomputers 
such as the CRAY~X-MP and CRAY~2, and (5) SIMD machines such as the Connection 
Machine.  Currently 11 application codes from a number of scientific 
disciplines have been selected, although it is not intended to run all codes 
on all machines.  Results are presented for two of the codes (QCD and missile 
tracking), and future work is proposed.


C3P-490b [Walker:88c]
"Performance of a QCD Code on the NCUBE Hypercube"
David W. Walker

The performance of a pure gauge QCD code on the NCUBE hypercube is analyzed.  
Both load imbalance and communication contribute to the concurrent overhead, 
with the load imbalance term becoming dominant for sufficiently large 
hypercubes.  The performance model is compared with timings measured on the 
NCUBE using both the standard and fast versions of the CrOS~III communication 
systems.


C3P-610 [Barhen:88a]
"The Pebble Crunching Model for Load Balancing in Concurrent Hypercube 
Ensembles"
Sandeep Gulati, Jacob Barhen, and S. Sitharama Iyengar

The successful development of fifth generation systems require enormous 
computational capability and flexibility necessitating the ability to achieve 
operational response in hard real-time through optimal resource utilization.  
This entails dynamically balancing the computational load among all the 
processing nodes in the system.  We propose a graph-theoretic, receiver-
initiated, distributed protocol for dynamic load balancing protocol in large-
scale hypercube ensembles.  Using attributed hypergraphs as the primary data 
structure for constraint modeling and dynamic optimization, we consider 
systems running precedence-constrained heterogeneous tasks.  Fault Tolerance 
is ensured by incorporating an integrity check for the decision nodes and 
their subsequent reelection if needed.  Simulation studies are used to 
evaluate the performance of the algorithm.


C3P-591 [Salmon:88b]
"A Mathematical Analysis of the Scattered Decomposition"
John Salmon

A theoretical basis for the scattered decomposition is worked out in some 
detail.  The basic result has been part of the ``folklore'' for some time, but 
has never been proved.  The load imbalance expected from a scattered 
decomposition of a set of computational tasks is proportional $n^{-
1/2}\sigma_{task}\over m_{task}$, where $n$ is the number of tasks assigned to 
each processor, $m_{task}$ is the mean time per task and $\sigma_{task}$ is 
the root mean square deviation time per task.  The constant of proportionality 
is of O(1), and is very slowly increasing function of the number of 
processors.


C3P-363b [Fox:88e]
"Load Balancing Loosely Synchronous Problem with a Neural Network
G. C. Fox and W. Furmanski

Hopfield and Tank have introduced the use of neural networks for the solutions 
of optimization problems such as the traveling salesman problem.  Here we show 
how to generalize this method to decompose {\it loosely synchronous} problems 
onto parallel machines and in particular the hypercube.  In this case, 
decomposition or load balancing can be formulated graph theoretically in terms 
of optical partitioning of the {\it computational graph} into $N = 2^d$ 
subgraphs.  The algorithm has a suggestive spin system interpretation, with 
the ferromagnetic interaction minimizing the communication and the long range 
paramagnetic force balancing the load.  The optimal fixed point of the network 
is in the Higgs phase of the magnet, with the domains of constant spontaneous 
magnetization representing the optimal decomposition map.

The method is fast, reliable and admits various simple implementations: 
sequential concurrent on the hypercube, analog on the neural network with 
adaptive weights (``learning'').

We analyze the sequential performance of various mean field based network 
algorithms and we compare the network approach with the statistical Monte 
Carlo techniques of simulated annealing.


C3P-497 [Koller:88a]
"A Dynamic Load Balancer on the Intel Hypercube"
Jeff Koller

A class of commonly encountered problems requires dynamic load balancing for 
efficient use of concurrent processors.  We are developing a test bed for 
dynamic load balancing studies, and have chosen the MOOS operating system and 
the intel iPSC as our environment.  We discuss these choices, and how we are 
implementing a general purpose dynamic load balancer.   


C3P-521 [Fox:88f]
"A String Theory for Time Dependent Complex Systems and its Application to 
Automatic Decomposition"
Geoffrey C. Fox and Wojtek Furmanski

We introduce a string or world line formalism that provides a general 
description of time dependent complex systems.  We show that it can be applied 
to mapping general problems onto both sequential and parallel computers.  In 
principle it unifies the concepts of an optimizing compiler with that of 
parallel decomposition.  We show that it reproduces and smoothly interpolates 
both our original load balancing methods for {\it loosely synchronous} 
problems and optimal communication and combining algorithms such as {\it 
index} and {\it fold}.  We evaluate two explicit implementations, the {\it 
neural\_router} and {\it neural\_accumulator}, which use an optimizing neural 
network.


C3P-586 [Salmon:88a]
"MOOSE: A Multi-Tasking Operating System for Hypercubes"
John Salmon, Seal Callahan, Jon Flower, and Adam Kolawa

GET ABSTRACT


C3P-577 [Griffiths:88a]
"Ada Tasking on the Sequent Balance"
Mike Griffiths

GET ABSTRACT


C3P-527 [Felten:88a]
"Coherent Parallel C"
Edward W. Felten and Steve W. Otto

Coherent Parallel C (CPC) is an extension of C for parallelism.  The 
extensions are not simply parallel {\it for\/} loops; instead, a data parallel 
programming model is adopted.  This means that one has an entire process for 
each data object.  An example of an ``object'' is one mesh point in a finite 
element solver.  How the processes are actually distributed on a parallel 
machine is transparent --- the user is to image that an entire processor in a 
distributed-memory environment is dedicated to each process.  This simplifies 
programming tremendously: complex {\it if\/} statements associated with domain 
boundaries disappear; problems which do not exactly match the machine size and 
irregular boundaries are all handled transparently.

The usual communication calls are not seen at all at the user level.  
Variables of other processes (which may or may not be on another processor) 
are merely accessed (global memory).  The first pass of the CPC compiler 
schedules the necessary communications in an efficient, coherent manner.  
Processes in CPC are insulated from one another and interact in a 
deterministic manner.  This allows tractable debugging.  Standard C I/O is 
provided, with simple extensions for parallelism.

We currently have a CPC runtime system implemented on an NCUBE and have 
started implementing a true compiler for the language.

CPC is not specific to distributed memory machines.  Implementation of this 
language on other architectures is natural -- for example, there seems to be 
no fundamental problem with CPC on shared-memory parallel computers.


C3P-598 [Mazer:88a]
"A Dataflow-Based APL for the Hypercube"
Alan S. Mazer

GET ABSTRACT


C3P-314b [Fox:88h]
"Optimal Communication Algorithms for Regular Decompositions on the Hypercube"
G. C. Fox and W. Furmanski

We discuss optimal communication and decomposition algorithms for a class of 
regular problems on concurrent compters with a hypercube topology, using a 
general technique we call the method of cube geodesics.

We address the calculation of various transformations (convolutions, 
functionals, etc.) of data distributed over the hypercube; examples are the 
Fast Fourier Transform, matrix algorithms, global scalar products and vector 
sums, sorting.  These all involve long distance internode interactions and 
require more intricate communication that the simple local problems with 
static spatial decomposition such as partial differential equations.

We believe that our library of optimal communication routines is applicable to 
these and many other problems.  The simple example of a database application 
is sketched.  We implement the algorithms on the Caltech/JPL Mark~II hypercube 
and present a detailed performance analysis.


C3P-405b [Fox:88g]
"Hypercube Algorithms for Neural Network Simulation: The Crystal\_Accumulator 
and the Crystal\_Router"
G. C. Fox and W. Furmanski

We discuss communication algorithms relevant for neural network modeling on 
distributed memory concurrent computers with a hypercube topology.  Full, 
intermediate (medium range) and sparse network connectivities are analyzed.  
We point out that the flexible hypercube topology allows for the efficient 
implementation of the broad class of network algorithms with a variety of 
connectivity patterns.  We find algorithms {\it index, crystal\_router, fold 
{\rm and\/} crystal\_accumulator} which are appropriate in different cases 
depending on the sparseness and regularity of the network interconnect.  We 
show that there are natural analogies between biological communication paths 
and the interconnects of a distributed memory concurrent computer.


C3P-627 [Jefferson:88a]
"The Status of the Time Warp Operating System"
David Jefferson, Brian Beckman, Fred Wieland, Leo Blume, Michael DiLoreto, 
Phillip Hontalas, Peter Reiher, Kathryn Sturdevant, Jack Tupman, John Wedel, 
and Herb Younger

The Time Warp Operating System (TWOS) is a special-purpose operating system 
designed to support parallel discrete event simulation.  It has been under 
experimental development at the Jet Propulsion Laboratory for four years, and 
runs primarily on the JPL/Caltech Mark~III Hypercube, although it has been 
ported to several other systems.  Its main distinction is that it incorporates 
a full implementation of the Time Warp mechanism, which is based on the 
unusual synchronization primitives of process rollback and message-antimessage 
annihilation.

In this paper, we discuss the status of the TWOS project at JPL, and present 
preliminary data from some of the performance experiments we have conducted on 
a Pool Balls benchmark, along with our analysis of them.


C3P-585 [Furmanski:88a]
"g - a compact langugae for real-time graphics"
W. Furmanski and D. Gates

We propose a medium level C-based language for computer graphics applications.  
The main objective is to provide real-time graphics (interactive video), hence 
the emphasis in the language design is on optimal speed of the machine code 
(to minimize system overheads) and on the compactness of the g code (so that 
no manuals are necessary).

The language coexists and fully cooperates with C.  The modular structure of 
the g data sector admits various programming models (sequential/concurrent, 
local/network extended).  Portable design of the g compiler allows for various 
graphics configurations with adjustable speed/portabality ratio.  The 
compiler output is machine-independent ``machine'' code, to be explicitly 
interpreted on a given graphics device.

The g programming environment consists of a g compiler (written in C), a 
portable (but slow) g interpreter (written in C) and a set of optimized 
interpreters for individual machines/devices (written in assembly).


C3P-576 [Morison:88a]
"Interactive Performance Display and Debugging using the NCUBE Real-Time 
Graphics System"
Rodney Morison

The NCUBE Real-Time Graphics System is an option for NCUBE/7 and NCUBE/10 
hypercube systems.  It is a parallel graphics interface that is able to 
display up to 30 frames per second of hypercube output.  Systems such as this 
are potentially well suited to real time display of output from parallel 
programs.  This paper discusses the issues of real time display for 
performance monitors on MIMD computers that have a high bandwidth graphics 
interface such as the one mentioned above.  Several monitors for an 
asynchronous parallel ....... WHERE'S THE REST OF THIS??????


C3P-600 [Warren:88a]
"Graphics Techniques in Concurrent Simulation"
Van Warren

This paper discusses work occurring in the hypercube simulation laboratory and 
visualization schemes for concurrent simulation.  The principle contribution 
of this work is that of a cost effective technical approach to simulation 
visualization.  This approach is being replicated and applied to contemporary 
large scale simulation problems of interest around the country.

Since the hypercube graphics interface is a working prototype, there is a mix 
of practice and experience along with novel approaches to contemporary 
graphics problems.  A discussion of techniques which accelerated graphics 
development is included.  Among these are issues of interpreted vs. compiled 
tools for simulation visualization and supercomputer-display interface 
methodology.  A survey of other significant efforts in combining hypercubes 
and graphics is provided.  Finally, the issue of interactive simulation 
exploration via real time displays is discussed with an eye toward the future.


C3P-575 [Angus:88a]
"FORTRAN CUBIX: Definition and Implementation"
Ian G. Angus

An I/O facility for FORTRAN programmers is defined for use with the 
Crystalline Operating system and the CUBIX I/O library.  All of the external 
I/O switches and file types of the F77 standard FORTRAN are supported from 
within the nodes of a Hypercube.  This is expected to both ease the 
development of FORTRAN applications and to greatly facilitate the conversion 
of existing sequential programs into concurrent versions.

The implementation is portable to most machines that have both a C and 
FORTRAN compiler.  The FORTRAN compiler is not required to have the ability to 
parse I/O statements.  The only nonportable components of this package are, 
the interface codes to bridge between C and FORTRAN, and the implementation of 
your favorate FORTRAN extensions.


C3P-531 [Flower:88a]
"Parallel Programmin in Comfort"
Jon Flower

We describe a set of software utilities designed to facilitate the writing of 
parallel codes and porting sequential ones.  Emphasis is placed on 
portability so that code can be developed simultaneously on a sequential and 
a parallel machine, and so that the completed code can be run and maintained 
on a wide variety of machine architectures.

We describe the CrOS communication package for parallel machines, the CUBIX 
system to allow a code to run in parallel or sequentially, the PLOTIX parallel 
graphics foundation, and the parallel debugger NDB.

While the system described has been implemented on qualitatively different 
machines the particular version described here is most efficient for the 
hypercube architecture, and was developed on NCUBE hypercubes under both the 
AXIS or XENIX operating systems.


C3P-522 [Fox:88b]
"What Have We Learned from Using Real Parallel Machines to Solve Real 
Problems?"
Geoffrey C. Fox

We briefly review some key scientific and parallel processing issues in a 
selection of some 84 existing applications of parallel machines.  We include 
the MIMD hypercube transputer array, BBN Butterfly, and the SIMD ICL DAP, 
Goodyear MPP, and Connection Machine from Thinking Machines.  We use a space-
time analogy to classify problems and show how a division into synchronous, 
loosely synchronous and asynchronous problems is helpful.  This classifies 
problems into those suitable for SIMD or MIMD machines, and isolates the 
asynchronous class as that for which major uncertainties as to possible 
parallelism exist.  Interestingly, about half of the scientific applications 
run excellently on SIMD machines with the other half able to take special 
advantage of the MIMD architecture.


C3P-571 [Gorham:88a]
"Hypercube Data Analysis in Astronomy:  Optical Interferometry and Millisecond 
Pulsar Searches"
Peter Gorham, Thomas Prince, and Stuart Anderson

Astronomical data sets are beginning to live up to their name, in both their 
sizes and the complexity of the analysis required.  Here, we discuss two 
astronomical data analysis problems which we have begun to implement on a 
hypercube concurrent processor environment:  The intensive image processing 
required in an optical interferometry porject, and the large scale power 
spectral analysis required by a search for millisecond-period radio pulsars.  
In both cases, the analysis proceeds largely in the Fourier domain, and we find 
that the problems are readily adaopted to a concurrent environment.  In the 
following report, we outline briefly the astronomical background for each 
problem, then discuss the general computational requirements, and finally 
present possible hypercube algorithms and results achieved to date.


C3P-581 [Apostolakis:88d]
"Statistical Gravitational Lensing on the Mark~III Hypercube"
John Apostolakis and Christopher S. Kochanek

We describe a parallel algorithm for the nonlinear optics problem of 
gravitational lensing.  The method is a ``ray-tracing'' method which studies 
the statistical properties of the image population associated with a 
gravitational lens.  A parallel computer is needed because the spatial 
resolution requirements of the problem make the program too large to run on 
conventional machines.  The program is implemented on the Mark~III hypercube 
to take maximum advantage of this machine's 128~Mbytes of memory.  The 
concurrent implementation uses a scattered domain decomposition and the 
CrOs~III communications routines.  The communications in the problem are so 
irregular that no completely satisfactory implementation was made in terms of 
the execution time of the program:  the maximum speed-up relative to a 
sequential implementation is a factor of four on a 32-node machine.  However, 
the goal of efficiently using all of the Mark~III's memory was achieved, and 
the execution time was not the limiting factor in the problem.  If the crystal 
router were used, the implementation would be much more efficient.  
Development of the program was terminated at this stage, however, because we 
were able to extract the physics of interest without the more sophisticated 
communications routines.


C3P-593 [Warren:88b]
"An $O(N\log N)$ Hypercube N-body Integrator"
Mike Warren and John Salmon

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


C3P-404b [Furmanski:87a]
"Piriform (Olfactory) Cortex Model on the Hypercube",
J. M. Bower, M. E. Nelson, and M. A. Wilson

We present a concurrent hypercube implementation of a neurophysiological model 
for the piriform (olfactory) cortex.

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.

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.

Sample numerical results presented here were derived on the NCUBE hypercube at 
Caltech.


C3P-583 [Battiti:88a]
"Collective Stereopsis on the Hypercube"
Roberto Battiti

A cooperative algorithm for extracting disparity information from stereo image 
pairs has been implemented on the NCUBE hypercube computer.

Software is written in C-language, using communication routines of the {\it 
``Crystalline Operating System'' CrOSIII} designed at Caltech within the 
Caltech Concurrent Computation Program.  Some tests have been done using 
Julesz's random-dot stereograms.

Although the software is reasonably versatile and can be easily adapted for 
different flavors of stereo algorithms, the method used is that presented by 
Marr and Poggio.

As a preliminary stage for the stereo matching problem, a ``filtering'' 
program to extract physically meaningful primitives from images of a given 
scene has been written and tested on various types of images.


C3P-632 [Bond:88a]
"Parallel Vision Techniques on the Hypercube Computer"
Alan H. Bond and David Fashena

Parallel algorithms for programming low-level vision mechanisms on the JPL-
Caltech hypercube are reported.  These concern principally edge and region 
finding.  $256\times 256$ eight-bit images were used.

We discuss the problem of programming a hypercube computer, and the Caltech 
approach to load balancing.  We then discuss the distribution of images over 
the hypercube and the I/O problem for images.

In edge finding, we programmed convolution using a separable kernel 
computational approach.  This was tested with $5\times 5$ and $32\times 32$ 
masks.

In region finding, we developed two different parallel histogram techniques.  
The first finds a global histogram for the image by a completely parallel 
technique.  This method, which was developed from the Fox-Furmanski scalar 
product method, allows each histogram bucket to be computed by a separate 
processor, each processor regarding the hypercube as a different tree, and all 
buckets being computed in parallel by a complete interleaving of all 
communications required.  Similarly, the global histogram can then be 
distributed over the hypercube, so that all processors have the entire global 
histogram, by a completely parallel technique.

The second histogramming method finds a spatially local histogram within each 
processor and then connects locally found regions together.

Work in progress includes the application of a Hopfield neural net approach to 
region finding.


C3P-528 [Ho:88c]
"Pattern Recognition by Neural Network Model on Hypercubes"
Alex Ho and Wojtek Furmanski

The objective of this work is to study the performance characteristics of the 
back-propagation model for pattern recognition.  Specifically, the test case 
of recognition of Chinese characters is studied on an ELXSI-6400 and Mark~III 
hypercube.  Preliminary results indicate that local spatial decomposition of 
characters in the training set leads to simple parallel implementation of the 
neural net model on hypercubes, and also serves as an effective pre-processor 
which provides high quality of recognition and good efficiency.


C3P-574 [Ding:88a]
"Polymer Simulation on the Hypercube"
Hong-Qiang Ding

The Monte Carlo simulation of a model polymer is implemented on the Mark~III 
Hypercube computer under the CrOS operating system.  The polymer model and the 
simulation method are discussed.  The key features of the implementation are 
given.  The results show that hypercube computers are well suited for the 
polymer simulations.


C3P-570 [Hipes:88b]
"Chemical Reaction Dynamics: Integration of Coupled Sets of Ordinary 
Differential Equations on the Caltech Hypercube"
Paul G. hipes, Tim Mattson, Mark Y.-S. Wu, and Aron Kuppermann

Use of the Caltech/JPL hypercube multicomputer to solve problems in chemical 
dynamics is the subject of this paper.  The specific application is quantum 
mechanical atom diatomic molecule reactive scatterieng.  one methodology for 
solving this dynamics problem on a sequential computer is based on symmetrized 
hyperspherical coordinates.  We will discuss our strategy for implementing the 
hyperspherical coordinate methodology on the hypercube.  In particular, the 
performance of a parallel integrator for the special system of ordinary 
differential equations which arises in this application is discussed.


C3P-588 [Skjellum:88a]
"Waveform Relaxation for Concurrent Dynamic Simulation of Distillation 
Columns"
Anthony Skjellum and Sven Mattisson

The need for cost-effective, high-speed computing is essential in many aspects 
of chemical engineering practice, notably for the simulation of large-scale 
dynamic systems.  The arrival of powerful, highly concurrent message-passing 
multicomputers potentially offers such economical large-scale computing 
capability.  Development of appropriate, efficient algorithms which realize 
this potential must therefore become an important area of ongoing research and 
development in chemical engineering.  Desired {\it orders-of-magnitude\/} 
speed-up strongly motivates the use of novel algorithmic approaches for large-
scale simulation.


C3P-596 [Calalo:88a]
"Finite Difference Time Domain Soluation of Electromagnetic Scattering on the 
Hypercube"
Ruel H. Calalo, James R. Lyons, and William A. Imbriale

Electromagnetic fields interacting with a dielectric or conducting structure 
produce scattered electromagnetic fields.  To model the fields produced by 
complicated, volumetric structures, the finite difference time domain (FDTD) 
method employs an iterative solution to Maxwell's time dependent curl 
equations.  Implementations of the FDTD method intensively use memory and 
perform numerous calculations per time step iteration.  We implemented an FDTD 
code on the California Institute of Technology/Jet Propulsion Laboratory 
Mark~III Hypercube.  This code allows us to solve problems requiring as many 
as 2,048,000 unit cells on a 32-node Hypercube.  For smaller problems, the 
code produces solutions in a fraction of the time to solve the same problems 
on sequential computers.


C3P-562 [Liewer:88b]
"A Universal Concurrent Algorithm for Plasma Particle-in-Cell Simulation 
Codes"
Paulette C. Liewer, Viktor K. Becyk, John M. Dawson, and Geoffrey C. Fox

We have developed a new algorithm for implementation of plasma particle-in-
cell (PIC) simulation codes on concurrent processors.  This algorithm, termed 
the universal concurrent PIC algorithm (UC-PIC), has been utilized in a one-
dimensional electrostatic PIC code on the JPL Mark~III Hypercube parallel 
computer.  To decompose the problem using the UC-PIC algorithm, the physical 
domain of the simulation is divided into sub-domains, equal in number to the 
number of processors, such that all sub-domains have roughly equal numbers of 
particles.  For problems with non-uniform particle densities, these sub-
domains will be of unequal physical size.  Each processor is assigned a sub-
domain, with nearest neightbor sub-domains assigned to nearest neighbor 
processors.  Using this algorithm in the Mark~III PIC code, the increase in 
speed in going from 1 to 32 processors for the dominant portion of code (push 
time, defined below) was 29, yielding a parallel efficiency of 90\%.  Although 
implemented on a hypercube concurrent computer, this algorithm should also be 
efficient for PIC codes on other parallel architectures and on sequential 
computers where part of the data resides in external memory.


C3P-495 [Walker:88b]
"The Flux-Corrected Transport Algorithm on the NCUBE Hypercube"
David W. Walker and Geoffrey C. Fox

This work describes the implementation of a finite-difference algorithm, 
incorporating the flux-corrected transport technique, on the NCUBE hypercube.  
The algorithm is used to study two-dimensional, convectively-dominated fluid 
flows, and as a sample problem the onset and growth of the Kelvin-Helmholtz 
instability is investigated.  Timing results are presented for a number of 
different sized problems on hypercbues of dimension up to nine.  These results 
are interpreted by means of a simple performance model.  The extension of the 
algorithm to the three-dimensional case is also discussed.


C3P-613 [Clayton:88a]
"Acoustic Wavefield Propagation Using paraxial Extrapolators'
Robert W. Graves and Robert W. Clayton

Modeling by paraxial extrapolators is applicable to wave propagation problems 
in which most of the energy is traveling within a restricted angular cone 
about a principle axis of the problem.  Frequency domain finite-difference 
solutions are readily generated by using this technique.  Input  models can be 
described either by specifying velocities or appropriate media parameters on a 
two or three dimensional grid of points.  For heterogeneous models, 
transmission and reflection coefficients are determined at structural 
boundaries within the media.  The direct forward scattered waves are modeled 
with a single pass of the extrapolator operator in the paraxial direction for 
each frequency.  The first-order back scattered energy can then be modeled by 
extrapolation (in the opposite direction) of the reflected field determined on 
the first pass.  Higher order scattering can be included by sweeping through 
the model with more passes.

The chief advantages of the paraxial approach are 1) active storage is reduced 
by one dimension as compared to solutions which must track both up-going and 
down-going waves simultaneously, thus even realistic three-dimensional 
problems can fit on today's computers, 2) the decomposition in frequency 
allows the technique to be implemented on highly parallel macahines, such as 
the hypercube, 3) attenuation can be modeled as an arbitrary function of 
frequency, and 4) only a small number of frequencies are needed to produce 
movie-like time slices.

By using this method, a wide range of seismological problems can be addressed, 
including strong motion analysis of waves in three-dimensional basins, the 
modeling of VSP reflection data, and the analysis of whole earth problems such 
as scattering at the core-mantle boundary or the effect of tectonic boundaries 
on long-period wave propagation.


C3P-592 [Goldsmith:88a]
"A Hypercube Ray-tracer"
John Salmon and Jeff Goldsmith

We describe a hypercube ray-tracing program for rendering computer graphics.  
For small models, which fit in the memory of a single processor, the ray-
tracer uses a scattered decomposition of pixels to balance the load, and 
achieves a very high efficiency.  The more interesting case of large models, 
which cannot be stored in a single processor, requires a decomposition of the 
model data as well as the pixels.  We present algorithms for constructing a 
decomposition based upon information about the frequency with which different 
elements of the model are accessed.  The resulting decomposition is 
approximately optimized to minimize communication and achieve load balance.


C3P-567 [Gottschalk:88a]
"Concurrent Multiple Target Tracking"
Thomas D. Gottschalk

A concurrent algorithm for multiple target tracking is presented.  The 
underlying tracking formalism is first described by way of a sequential 
program, and the issues in generalizing the tracker for efficient concurrent 
implementations are discussed in detail.  Typical tracking results on the 
Mark~III hypercube are presented.


C3P-601 [Wieland:88a]
"Implementing a Distributed Combat Simulation on the Time Warp Operating 
System"
Frederick Wieland, Lawrence Hawley, and Abe Feinberg

Utilizing the Time Warp Operating System, the CTLS project at JPL has 
produced a distributed combat simulation called STB-87 and measured its 
performance on the JPL Mark~III Hypercube.  By applying the spiral model of 
software development, the CTLS project will produce a series of software test 
beds, to culminate in the completion of a working prototype theater level 
simulation three to five years hence.  STB-87, the first software test bed, is 
a ground-based combat simulation decomposed into objects which communicate via 
time-stamped messages.  The use of incremental object-based design, coding, 
and testing has been helpful when developing a parallel simulation.  The 
performance measurements show that, with the appropriate choice of object 
granularity, STB-87 is able to achieve a speed-up factor of 12 running on a 
32-node Mark~III Hypercube.


C3P-605 [Flower:88b]
"Lattice Gauge Theory on the Hypercube"
John Apostolakis, Clive Baillie, Hong-Qiang Ding, and Jon Flower

Lattice gauge theory, an extremely computationally intensive problem, has been 
run successfully on hypercubes for a number of years.  Herein we give a flavor 
of this work, discussing both the physics and the computing behind it.


C3P-572 [Baillie:88d]
"QED on the Connection Machine"
Clive Baillie, S. Lennart Johnsson, Luis Ortiz, and G. Stuart Pawley

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


C3P-589 [Callahan:88a]
"Non-Local Path Integral Monte Carlo on the Hypercube: Exchange Interactions 
in Solid Helium"
Sean Callahan

Some interesting physical properties of solid $^3$He are described and the 
physical observable calculated using Monte Carlo path integral techniques is 
defined.  The relationship between the path integral and the observable is 
outlined.  The parallel algorithm is explained and finally, timing results are 
presented for runs of the identical code on one parallel computer and two 
sequential computers:  The NCUBE hypercube, the CRAY~X-MP, the Elxsi~6400.


C3P-612 [Werner:88a]
"Dynamical Simulations of Granular Materials using the Caltech Hypercube"
B. T. Werner and P. K. Haff

A technique for simulating the motion of granular materials using the Caltech 
Hypercube is described.  We demonstrate that grain dynamics simulations run 
efficiently on the Hypercube and therefore that they offer an opportunity for 
greatly expanding the use of parallel simulations in studying granular 
materials.  Several examples, which illustrate how the simulations can be used 
to extract information concerning the behavior of granular materials, are 
discussed.


C3P-523 [Aloisio:88a]
"The Prime Factor Non-binary Discrete Fourier Transform and use of 
Crystal\_Router as a General Purpose Communication Routine"
J. S. Kim, G. C. Fox, G. Aloisio, and N. Veneziani

We have implemented one of the Fast Fourier Transform algorithms, the Prime 
Factor algorithm (PFA), on the hypercube.  On sequential computers, the PFA 
and other discrete Fourier transforms (DFT) such as the Winograd algorithm 
(WFA) are known to be very efficient.  Howver, both algorithms require full 
data shuffling and are thus challenging to any distributed memory parallel 
computers.  We use a concurrent communication algorithm, called the {\it 
Crystal\_Router\/} for communicating shuffled data.  We will show that the 
speed gained in reduced arithmetic compared to binary FFT is sufficient to 
overcome the extra communication requirement up to a certain number of 
processors.  Beyond this point the standard Cooley-Tukey FFT algorithm has the 
best performance.  We comment briefly on the application of the DFT to signal 
processing in synthetic aperture radar (SAR).


C3P-579 [Felten:88g]
"Chess on a Hypercube"
Edward W. Felten and Steven W. Otto

We report our progress on computer chess last described at the Second 
Conference on Hypercubes.  Our program follows the strategy of currently 
successful sequential chess programs: searching of an alpha-beta pruned game 
tree, iterative deepening, transposition and history tables, specialized 
endgame evaluators, and so on.  The search tree is decomposed onto the 
hypercube (an NCUBE) using a recursive version of the principal-variation-
splitting algorithm.  Roughly speaking, subtrees are searched by teams of 
processors in a self-scheduled manner.

A crucial feature of the program is the global hashtable.  Hashtables are 
important in the sequential case, but are even more central for a parallel 
chess algorithm.  The table not only stores knowledge but also makes the 
decision at each node of the chess tree whether to stay sequential or to split 
up the work in parallel.  In the language of Knuth and Moore, the 
transposition table decides whether each node of the chess tree is a type 2 or 
a type 3 node and acts accordingly.  For this data structure, the hypercube is 
used as a shared-memory machine.  Multiple writes to the same location are 
resolved using the priority system which decides which entry is of more value 
to the program.  The hashtable is implemented as ``smart'' shared memory.

Search times for related subtrees vary widely (up to a factor of 100) so 
dynamic reconfiguration of processors is necessary to concentrate on such 
``hot spots'' in the tree.  A first version of the program with dynamic load 
balancing has recently been completed and out-performs the non-load-balancing 
program by a factor of three.  The current speedup of the program is 101 out 
of a possible 256 processors.

The program has played in several tournaments, facing both computers and 
people.  Most recently it scored 2--2 in the ACM North American Computer Chess 
Championship.


C3P-611 [Witkowski:88a]
"Concurrent I/O System for the Hypercube Multiprocessor"
Andrew Witkowski, Kumar Chandrakumar, and Greg Macchio

This paper describes the Concurrent I/O (CIO) system for the Hypercube 
Multiprocessor.  Our system has three components: Architecture, User 
Interface, and Programming Paradigm.  The architecture of the system is based 
on clusters.  Each cluster has a hypercube topology and contains either 
computing nodes or I/O nodes.  This architecture scales well, provides a 
convenient naming convention and offers independent connectivity between the 
I/O nodes.  The routing algorithm confines the I/O traffic within the I/O 
clusters.  Clusters can be connected in a variety of ways suitable for such 
diverse applications as graphics and database systems.  The system provides a 
programming paradigm where several nodes of a multiprocessor can cooperate on 
creating a file.


C3P-182c [Kolawa:88a]
"Use of the Hypercube for Symbolic Quantum Chromodynamics"
A. Kolawa and G. C. Fox

A new numerical approach by Furmanski and Kolawa to quantum chromodynamics is 
based on diagonalizing the underlying Hamiltonian.  This method involves the 
generation of states by repeated action of a potential operator.  This 
symbolic calculation is dominated by the time it takes to search the database 
of existing states to verify if a generated state is identical to one 
previously found.  We implement this algorithm on the Caltech/JPL Mark~II 
hypercube and analyze its performance of both a simple database search and one 
optimized for this aplication.  We show that the hypercube performance can be 
modeled in a fashion similar to conventional numerical (loosely synchronous) 
applications.


C3P-526 [Chiu:88b]
"Shift-Register Sequence Random Number Generators on the Hypercube Concurrent 
Computers"
Ting-Wai Chiu

We discuss the design of a class of shift-register sequence random number 
generators for the MIMD parallel computers, and particularly for the hypercube 
concurrent computers.  The simplest implementation is to have each processor 
generating its own sequence provided that the initial seeds are linearly 
independent.  We generate these initial seeds by using distinct linear 
congruential generators and finally bit-by-bit-exclusive-or with the system 
time in microseconds.  Our shift-register sequence random number generators 
are coded in C and run single processor as well as on the combined sequence 
produced by all processors.  The tests include chi-square, Kolmongorov-
Smirnov, auto-correlation, runlength and n-tuple distribution tests.  A 
statistical test has been devised for testing the sequences of random number 
generated by a MIMD parallel computer.  Our test results indicate that our 
generators do provide independent sequences of random numbers with extremely 
long periods.


C3P-631 [Walker:88d]
"Portable Programming within a Message-Passing Model: the FFT as an Example"
David W. Walker

This paper describes a portable programming environment for MIMD concurrent 
processors based on an object-oriented, message-passing paradigm.  The basis 
of this environment is the Virtual Machine Loosely Synchronous Communication 
System (VMLSCS) which is designed to be used for loosely synchronous problems.  
VMLSCS is structured to make efficient use of hierarchical memory, and permits 
communication and calculation to be overlapped on certain concurrent 
processors.  As an example, the use of VMLSCS in performing both one-
dimensional and multi-dimensional fast Fourier transforms (FFTs) on concurrent 
multiprocessors is described.  It is shown that all necessary interprocessor 
communication can be performed by a single routine, {\it vm\_index}.  Thus the 
construction of a portable concurrent FFT rests on the implementation of {\it 
vm\_index\/} on the target machines.  In the multi-dimensional algorithm a 
strip decomposition is applied to each of the directions in turn so that each 
of the FFTs performed in a particular direction are done in one processor.  
This allows fast sequential one-dimensional FFTs to be exploited.  The 
implementation of {\it vm\_index\/} on both homogeneous and inhomogeneous 
hypercubes, and shared memory multi-processors is discussed.


C3P-590 [Felten:88c]
"Best-First Branch-and-Bound on a Hypercube"
Edward W. Felten

The branch-and-bound technique is a common method for finding exact solutions 
to difficult problems in combinatorial optimization.  This paper will discuss 
issues surrounding implementation of a particular branch-and-bound algorithm 
for the traveling-salesman problem on a hypercube multi-computer.

The natural parallel algorithm is based on a number of asynchronous processes 
which interact through a globally shared list of unfinished work.  In a 
distributed-memory environment we must find a non-centralized version of this 
shared data structure.  In addition, detecting termination of the computation 
is tricky; an algorithm will be presented which ensures proper termination.  
Finally, issues affecting performance will be discussed.


C3P-578 [Hipes:88a]
"Gauss-Jordan Inversion with Pivoting on the Caltech Mark~II Hypercube"
Paul G. Hipes and Aron Kuppermann

The performance of a parallel Gauss-Jordan matrix inversion algorithm on the 
Mark~II hypercube at Caltech is discussed.  We will show that parallel Gauss-
Jordan inversion is superior to parallel Gaussian elimination {\it for 
inversion}, and discuss the reasons for this.  Empirical and theoretical 
efficiencies for parallel Gauss-Jordan inversion as a function of matrix 
dimension for different numbers and configurations of processors are 
presented.  The theoretical efficiencies are in {\it quantitative\/} agreement 
with the empirical efficiencies.


C3P-348b [Ho:88b]
"LU Decomposition of Banded Matrices and the Solution of Linear Systems on 
Hypercubes"
T. Aldcroft, A. Cisneros, G. C. Fox, and W. Furmanski, D. W. Walker

We describe the solution of linear systems of equations, $Ax=b$, on 
distributed-memory concurrent computers whose interconnect topology contains a 
two-dimensional mesh.  $A$ is assumed to be an $M\times M$ banded matrix.  The 
problem is generalized to the case in which there are $n_b$ distinct right-
hand sides, $b$, and can thus be expressed as $AX=B$, where $X$ and $B$ are 
both $M\times n_b$ matrices.  The solution is obtained by the LU decomposition 
method which proceeds in three stages:  (1) LU decomposition of the matrix 
$A$, (2) forward reduction, (3) back substitution.  Since the matrix $A$ is 
banded a simple rectangular subblock decomposition of the matrices $A$, $X$, 
and $B$ over the nodes of the ensemble results in excessive load imbalance.  
A scattered decomposition is therefore used to decompose the data.  The 
sequential and concurrent algorithms are described in detail, and models of 
the performance of the concurrent algorithm are presented for each of the 
three stages of the algorithm.  In order to ensure numerical stability the 
algorithm is extended to include partial pivoting.  Performance models for the 
pivoting case are also given.  Results from a 128-node Caltech/JPL Mark~II 
hypercube are presented, and the performance models are found to be a good 
agreement with these data.  Indexing overhead was found to contribute 
significantly to the total concurrent overhead.


C3P-386b [Furmanski:88b]
"Optimal Matrix Algorithms on Homogeneous Hypercubes"
Geoffrey C. Fox, Wojtek Furmanski, and David W. Walker

This paper describes a set of concurrent algorithms for matrix algebra, based 
on a library of collective communication routines for the hypercube.  We show 
how a systematic application of scattering reduces load imbalance.  A number 
of examples are considered (Gaussian elimination, Gauss-Jordan matrix 
inversion, the power method for eigenvectors, and tridiagonalization by 
Householder's method), and the concurrent efficiences are discussed.


C3P-502 [Williams:88a]
"DIME: A Programming Environment for Unstructured Triangular Meshes on a 
Distributed-Memory Parallel Processor"
Roy D. Williams

DIME (Distributed Irregular Mesh Environment) is a user environment written in 
C for manipulation of an unstructured triangular mesh in two dimensions.  The 
mesh is distributed among the separate memories of the processors, and 
communication between processors is handled by DIME; thus the user writes C-
code referring to the elements and nodes of the mesh and need not be unduly 
concerned with the parallelism.  A tool is provided for the user to make an 
initial coarse triangulation of a region, which may then be adaptively refined 
and load-balanced.  DIME provides many graphics facilities for examining the 
mesh, including contouring and a Postscript hard-copy interface.  DIME also 
runs on sequential machines.

