The collected papers are available as the Journal of Undergraduate Research in High-Performance Computing, Volume 2, Bogucz, E.A., and Weinman, V.E., editors, Northeast Parallel Architectures Center at Syracuse University Technical Report SCCS-468, November 1992. Copies of this report are available via request to reu-info@npac.syr.edu.
Detecting objects in an image using the generalized Hough algorithm is a computationally intensive problem. An algorithm computing the generalized Hough transform for an MIMD architecture computer is developed. Additional techniques are implemented in an attempt to achieve greater speedups. Supportive experimental results on a CM-5 multicomputer are presented.
A Postscript version of the paper is available for immediate retrieval and viewing.
This paper addresses the determination of a two-dimensional
convex hull on parallel computers. The calculation of a convex hull is
important in a computational geometry approach to determining
roundness error of a drilled hole. In addressing the problem of
roundness error, this drilled hole can be represented by a simple
polygon. Establishing the convex hull of this simple polygon is the
starting point for assessing roundness error in this manufactured work piece.
Several sequential algorithms already exist for finding a two-dimensional
convex hull. Most of these algorithms use recursive
programming techniques in order to obtain the convex hull.
A parallel algorithm was developed from a divide-and-conquer
approach to constructing convex hulls. The algorithm was written in
CM Fortran and was implemented on the Connection Machine
(CM-2). The parallel algorithm uses SCAN subroutines instead of
recursive techniques to obtain the convex hull of a simple polygon.
A Postscript
version of the paper is available for immediate retrieval and viewing.
This paper discusses an efficient parallel implementation of SIMPLE,
an automatic test pattern generation algorithm. A new approach is presented in
which processors that become idle during execution
are reincorporated back into useful computation towards finding a test. The
algorithm is designed for a MIMD-architecture computer and implemented on the
CM-5. The approach is demonstrated to yield significant speedup over previous
implementations.
A Postscript
version of the paper is available for immediate retrieval and viewing.
This paper suggests the need for a discrete space-time model and offers
the graph as a possible solution. A proposed topology on the graph is
examined and shown to be incomplete, leading to the standard metric on the
graph to be accepted. The variety as a dynamical quantity is defined and
numerically analyzed using high speed parallel machines. Graphs of
maximal variety are shown to have or not to have desirable properties in terms
of dimensionality, and are therefore appealing or to be discarded as
possible spacetime structures.
Postscript
version of the paper are available for immediate retrieval and viewing.
This project ported the Advanced Regional Prediction System version 3.0 from
the University of Oklahoma CAPS group (Center for Analysis and Prediction of
Storms) to an MIMD architecture, the Connection Machine 5. The CM-5 is
a distributed-memory MIMD machine with a control processor and 32 processing nodes. The ARPS
project does weather modeling by tracking the behavior of a three-dimensional
disturbance in the atmosphere. The bulk of our research was finding an
optimal mapping of the
data structures from a sequential architecture with one processor to an MIMD
architecture with 32 processors. Creating this mapping involved the design of a processor grid, routines to disperse the data structures onto the processor
grid, and
the development of message-passing features. Message-passing was important in
this project because there were many ``nearest neighbor" calculations.
In these types
of calculations the value is computed based upon neighboring values. When
a point needs a neighbor that is on a separate processor because
of the mapping of the data
structures, messages must be passed between the nodes. The program was done in
FORTRAN with message-passing, using special library routines, and our
preliminary results showed promise for a parallel message-passing code on the
Connection Machine, Model CM-5
Postscript
version of the paper is available for immediate retrieval and viewing.
With the growing strain on database systems, it seems relevant to study the
performance of parallel machines on database operations. One of the most
important database operations is the sort operation. We tested the CM-5
with simulated databases (large arrays) using several sorting algorithms.
The machine's performance was analyzed by observing sort times, sample
times, and communication times. Experiments were done with different
``database'' sizes, and the number of processors used. The long-term goal
is to evaluate the performance of the CM-5 on many database operations.
A Postscript
version of the paper is available for immediate retrieval and viewing.
A trading strategy is developed to evaluate the market profitability
of four different pricing models in detecting
under-priced call options. Included in the evaluation
are the Black-Scholes Model and three binomial
lattice models implemented on parallel
computers. The results show that option pricing models
that incorporate stochastic volatility have higher daily profitability and
are therefore better able to detect under-priced
call options than pricing models that assume constant
volatility (e.g., the Black-Scholes Model). On an average,
none of the four pricing models do significantly better at detecting
under-priced call options than a random selection of
call options. All five trading techniques are found to produce losses when
used in simulated long-term trading.
Postscript
version of the paper is available for immediate retrieval and viewing.
The application of massively parallel computers in simulating disordered
physical systems and in the search for global minima of discrete optimization
problems is addressed. Simulated tempering is a new algorithm that
is presented
as an alternative to the Monte Carlo procedure known as simulated annealing.
A sequential version of this algorithm has been shown to improve greatly
the simulation of a specific spin model as compared to conventional Monte
Carlo
techniques. In the present work, an efficient parallel program that performs
simulated tempering on Ising spin models is produced and implemented on a
MasPar system, using the MasPar Programming Language. The performance of the
parallel version of the algorithm for finding the ground state of an Ising spin
glass is then analyzed and compared to the performance of a parallel version of
the simulated annealing algorithm. It is found that methods for tuning the
variable parameters in the tempering algorithm must be discovered before
simulated tempering can be as effective as simulated annealing for general
optimization problems.
Postscript
version of the paper is available for immediate retrieval and viewing.
This work deals with the development of a parallel algorithm for performing
signal processing using wavelet transforms. Wavelet transforms facilitate
the recognition of patterns in irregular signals. The mathematical method
involves the integration of the projection of the signal and a known function
called a wavelet. The results are displayed graphically, each resulting value
assigned a color. A parallel implementation of the wavelet transform was
developed for the CM-2 in Fortran 90.
A Postscript
version of the paper is available for immediate retrieval and viewing.
A previously reported, parallel method for calculating approximately
maximum planar subgraphs has shown promising results, but was slow.
The results of an initial implementation on the Connection Machine 2
prompted an investigation of more efficient methods of implementing
the procedure. An improved implementation uses many fewer processors
for the calculation, with substantially shorter communication times.
By running several copies of the basic calculation simultaneously, the
program performs one hundred times faster than earlier
implementations.
Postscript
version of the paper is available for immediate retrieval and viewing.
A data-parallel implementation of the Sieve of Eratosthenes
has been used to calculate prime numbers up to
approximately $2^{30}$ in C*. Alternative programming
techniques to implement the sieve approach on the
Connection Machine have been explored. In addition, ways
to visualize the distribution of the prime numbers using the
parallel graphics capability of the CM were investigated.
A Postscript
version of the paper is available for immediate retrieval and viewing.
Environments for coupling symbolic computation with parallel numeric
processing are demonstrated using mathematica and an nCUBE 2
multiple-instruction-thread-multiple-data-stream computer.
The so-called ``Q'' environments provide programming models
that allow distributed symbolic
computing, as well as a bridge between sequential
symbolic computing and distributed numerical computation. Scientific visualization,
one strength of mathematica and a classical weakness of parallel machines, is
showcased as a feature of the Q environments.
Applications that demand parallel symbolic processing also are discussed.
A Postscript
version of the paper is available for immediate retrieval and viewing.
Image processing on a sequential machine is a tediously slow
process. The need for image processing lies in scientific
visualization, the entertainment industry, and a variety of real-world
applications. Processing images is typically a very regular
process. This paper outlines a model for using an SIMD-architecture computer
to expedite the task. AVS, a front-end for a
variety of visualization needs, is employed in this work. AVS is shown to
provide a convenient system for parallel image processing,
as well as providing an easy way to user interface.
A Postscript
version of the paper is available for immediate retrieval and viewing.
Parallel Implementation of a 2-D Convex Hull
Yvette Cordero and Uptal Roy
An Efficient Parallel Implementation of an Automatic Test Pattern Generation Algorithm
Michael Harry and Dennis Shiau
Maximal Variety Graphs: A Model for Spacetime Structure
Ron Maimon and Lee Smolin
MIMD Implementation of
Advanced Regional Prediction System
Nicole LaFontaine and Nancy McCracken
Evaluation of Sorting Techniques on the CM-5
Paul D. Peters and Alok Choudhary
An Evaluation of Market Profitability for Four Stock Option Pricing Models
Neal Roodin and Kim Mills
Evaluation of Simulated Tempering for Optimization Problems
Thomas Rose and Paul Coddington and Enzo Marinari
Parallel Computation of Wavelet Transforms
Jennifer Rubbo and Jacques Lewalle
Fast Programs for Finding Maximum Planar Subgraphs
David G. Solt and Ernest Sibert
A Parallel Approach to Finding Prime Numbers and Visualizing their
Distribution
{Pamela K. Speidel and Ernest Sibert
Q: A System for Doing Mathematics Really Fast by Computer
T.J. Willis and E. A. Bogucz
Image Processing in Parallel: A Simple Model
Matthew Colby Young and Marek Podgorny and Tomacz Haupt