Details of Talks
- Greg Astfalk, Hewlett Packard
- Title: Scaling up to very large parallel systems
- Abstract: There is a desire for dramatically increased levels of
performance from computer systems. The applications to which this
increased performance could be applied are quite diverse. Owing to
this the systems that would be most useful are general-purpose. This
leads us to the question of what would be the architecture of a
general-purpose system of enormous computing power. As a target we
examine what a system of greater than 5 Tflops would resemble within
the next few years.
Our examination looks at several possible ways of getting there (some
of which are silly) and the technological challenges associated with
each alternative. While it would be nice to maintain technological
purity, we will cloud this talk with some genuine constraints. The
dirty words we consider are; physics and economics.
At the end of all of this we describe the impact on the users of the
type of general-purpose system that we feel could actually reach the
multi-Tflop level.
- David Ceperley, NCSA, University of Illinois at Urbana-Champaign
- Title: Testing Parallel Random
Number Generators
- Abstract:
- Mark Durst, NERSC, Lawrence Berkeley National Laboratory
- Title: The Embarrassing
Success of Embarrassing Parallelism
- Abstract: So-called "embarrassingly parallel" computations (roughly speaking,
those with trivially low communication-to-computation ratios) are
becoming the principal beneficiaries of the massively parallel
computing resources currently moving out of the pure research state
and into use as tools for routine scientific computation. I will
describe two such codes gearing up for computational advances at
NERSC, one simple in its overall structure and one alarmingly complex.
I will argue that this often-scorned category of computation is likely
to make further gains in the likely computational environment of the
next decade. Needs for random number generation will be discussed
just enough to keep me from being bodily thrown out of the workshop.
- Karl Entacher, Mathematics, University of Salzburg
- Title: Parallel Streams of Linear Random Numbers in the Spectral Test
- Abstract:
We discuss recent methods of random number generation and
we show how to analyze different substreams of linear congruential
pseudorandom numbers by means of the spectral test.
Such substreams occur in particular simulation setups,
in transformation methods for non-uniform pseudorandom numbers
or when we produce distinct parallel streams of random numbers
for parallel and distributed simulation by the usual
parallelization methods.
Especially in the latter case, two kinds of substreams are
of special interest:
(i) lagged subsequences of random numbers with step sizes K
("leap-frog technique") and
(ii) consecutive disjoint streams of random numbers of length L.
For linear congruential generators, both techniques are easily implemented,
but great attention has to be paid to the quality of such subsequences.
Using the spectral test, we show that almost all linear congruential
generators recently in use produce disastrously
lagged subsequences with very small lags.
Hence, an a-priori analysis of such subsequences is required.
We show how to assess lagged subsequences for the full-period and
non-full-period case.
Analyzing consecutive streams with the spectral test is
related to the well known long-range correlation analysis of
linear congruential generators.
Whereas the latter was carried out to exhibit correlations
between pairs of processors only, the spectral test provides an easy method
to study correlations between an arbitrary number of parallel streams as well.
- James Given, Biotechnology Center, NIST
- Title: A New Class of Parallel Diffusion Algorithms
- Abstract: We have previously used first-passage algorithms to treat random diffusion in
a complex, two-phase environment. These algorithms utilize an efficient
diffusion propagator selected from a library of Laplacian Green's functions
in order to traverse, in a single propagation event,
a large portion of the diffusing particle's environment
which is known to be free of interaction sites; they generalize the
well-known ``walk-on-spheres'' algorithms. This approach was shown
to provide the most rapid and accurate calculations currently available of
translational hydrodynamic friction of an irregularly shaped object, e.g.
a macromolecule. A related class of algorithms, the last-passage algorithms,
utilize probabilistic h-processes; these algorithms provide rapid,
diffusion-based codes for mutual capacitance and diffusion-limited
reaction rate.
Here we introduce a further extension of
this class of algorithms: we show how to solve a general, stationary
Smoluchowski equation by shifting the force-field terms, i.e., all the
terms other than the Laplacian term, to the RHS and treating them
as source terms to be determined self-consistently. These field-
induced source terms then prescribe the rate at which diffusing particles are
created at various points in the system. The newly-created particles
subsequently undergo force-free diffusion in the environment, which we model
using the algorithms just described. In particular, this
provides an efficient algorithm for calculating the solvation energy of a
macromolecule.
- John Halton, Computer Science, University of North Carolina, Chapel Hill
- Title: Why Quasi-Monte-Carlo
methods are statistically valid and how their errors can be
estimated statistically
- Abstract: Quasi-random sequences are extremely
useful, relatively new tools for performing accurate, efficient
Monte Carlo computations. However, two major problems arise in
their use. First, how can statistical and probabilistic concepts
be applied to what are patently deterministic quantities?
Secondly, how can we accurately estimate the errors generated by
quasi-Monte-Carlo calculations? By demonstrating that these
sequences can be viewed, in an appropriate and precisely defined
sense, as representative of random samples drawn from truly
random processes, their use in a statistical setting is
rigorously justified. By further pointing out that a
multi-dimensional quasi-random sequence can be decomposed into
mutually statistically independent sequences (of one or more
dimensions), we can apply the Central Limit Theorem to generate
valid statistical estimates of the errors generated by
computations depending on such sequences.
- Malvin Kalos, Physics, Cornell University
- Title: Tools for Good Practice in Monte Carlo Calculations
- Abstract:
Monte Carlo methods are now well recognized and widely used in many of
the physical and mathematical sciences. They are, under certain
conditions, capable of high accuracy, and often are used to adjudicate
theoretical questions. They are also subject to misuse. I propose a
concerted effort to establish principles of good practice so that
results can be objectively judged for their credibility. More
specifically, I will address the needs for standards and tools to
answer the following generic questions about Monte Carlo results: Are
the random numbers good enough for the results to be believed (at the
level of the quoted confidence limits?) Are the errors computed in a
reliable way? Are there systematic errors (e.g., associated with
convergence to equilibrium) and are they convincingly estimated or
bounded? The issue of determining and ameliorating the effects of the
use of pseudorandom numbers with known or unknown defects is clearly
the most interesting and difficult.
- Miron Livny, Computer Science, University of Wisconsin, Madison
- Title: High Throughput Monte Carlo
- Abstract:
- Michael Mascagni, Mathematics and Scientific
Computing, University of Southern Mississippi
- Title: Future Directions in Random Number Tools
- Abstract:
SPRNG incorporates many developments in parallel random number generation
into a general purpose tool. Clearly, a single tool does not satisfy all
of the future requirements for random number generation. In this talk we
consider some of the requirements for random number generation that were
not met by SPRNG and possible approaches. These include:
- Pseudorandom numbers for distributed systems: CONDOR and SPRNG
- Alternative pseudorandom number generation methods to meet different
Monte Carlo requirements
- Parallel and distributed quasirandom numbers
- Domain specific testing
- Giray Ökten,
University of Alaska, Fairbanks
- Title: High
Dimensional Simulation
- Abstract: Although quasi-Monte Carlo methods
generally provide more accurate estimates than Monte Carlo
methods in "moderate" dimensions, their advantages diminish
quickly as the dimension of the problem increases. In addition,
generation of low-discrepancy sequences may become impractical in
very high dimensions. We will survey the hybrid-Monte Carlo
methods that are proposed to provide remedies for the
difficulties faced in high dimensional problems. We will then
investigate the one based on the so-call ed "mixed" sequences. A
probabilistic result on the discrepancy of mixed sequences as
well as numerical results obtained upon application of these
sequences to problems from numerical integration and
computational finance will be presented.
- Simonetta Pagnuti, ENEA (Italian DOE), Bologna
- Title: A priori and a posteriori
control of correlations in parallel Monte Carlo
- Abstract: Two alternatives are discussed for feeding a parallel machine with
random numbers:
i) the processors cooperating to the solution of a Monte Carlo problem
use subsequences of a unique generator;
ii)each processor uses its own generator.
In both cases the serious problem of stochastic independence of the
coprocessors must be taken into account. Since in most of the widely
used generators strong long-range autocorrelations appear, in the first
case one can safely use only a fraction of the whole sequence: the
smaller the tolerated interdependence, the smaller the fraction that can
be used. Methods for computing such a fraction will be briefly
described. In the second case, where an "a priori" analysis of the
mutual correlations among the several processors seems generally not
feasible, an "a posteriori" control may be performed by means of a
special estimator implemented in the Monte Carlo program, with the
purpose of monitoring the effects of mutual correlations on the variance
of the Monte Carlo result.
- Ashok Srinivasan, NCSA, University of Illinois at Urbana-Champaign
- Title: SPRNG Scalable Parallel
Random Number Generators
- Abstract: We shall discuss the implementation of
the SPRNG Scalable Parallel Random Number Generators, the
accompanying test suite, and test results.
- Todd Urbatsch, Los Alamos National Laboratory
- Title: A Strategy for Parallel Implicit Monte Carlo
- Abstract: For the Accelerated Scientific Computing Initiative (ASCI)
parallel computers at Los Alamos National Laboratory, we are
developing a new Implicit Monte Carlo (IMC) code using the
Fleck-Cummings linearized Monte Carlo method for time-dependent
radiative transfer. Our strategy for parallelism employs the
usual Monte Carlo duplication scheme but permits domain
decomposition, a constraint necessary for the projected size
of our calculations. From the random number generators in our
code, we require repeatability, excellent quality, and longer
periods to accommodate our large calculations. Because our
strategy includes a vast number of particles with increased
communication and storage, the amount of random number
information per particle must be small. Finally, the random
number generator must provide statistically independent random
number streams for new methods research in our code.
- Tony Warnock, Los Alamos National Laboratory
- Title: Effective Error Estimates for Quasi-Monte Carlo Computations
- Abstract:
While quasi-Monte Carlo methods are generally more efficient than
traditional Monte Carlo, they have not been as widely used because
of the difficulty of obtaining effective error estimates. We present
error estimates that are effective for quasi-Monte Carlo computations
along with some new low-discrepancy sequences.
- Pavlos Vranas, Physics, Columbia University
- Title: Lattice QCD on a teraflop parallel supercomputer
- Abstract: Quantum Chromodynamics (QCD) is the theory that describes the strong
nuclear force. This force is responsible for the formation and
interaction of nucleons. By discretizing space time (lattice) it is
possible to simulate this theory on a computer using Monte Carlo
techniques. This approach provides the most powerful tool for
theoretical physics studies of QCD. It is also one of the
computationally most demanding numerical applications. In this talk a
general description of lattice QCD will be given with focus on the
numerical techniques used to simulate the theory on parallel
supercomputers. Also, the QCDSP (QCD Digital Signal Processor)
parallel supercomputer will be described. This machine was designed
and built by a group of theoretical physicists, has an aggregate speed
of 1 Teraflop and is dedicated to lattice QCD simulations.
ashoks@ncsa.uiuc.edu
Last modified:2 Mar 1998