Workshop on   High-Performance Monte Carlo Tools

April 23-24, 1998 Stennis Space Center, MS

Organizers:

Michael Mascagni: University of Southern Mississippi

Ashok Srinivasan, David Ceperley: NCSA, University of Illinois, Urbana-Champaign  

 


Summary

This workshop was organized to discuss tools that enable Monte Carlo computations on parallel and distributed systems. The organizers brought together a diverse group of speakers who presented new work in the areas of Monte Carlo algorithms, parallel Monte Carlo applications, parallel and distributed computing tools, random number generation, and recent trends in high-performance parallel and distributed computing. The organizers of the workshop have recently completed development of a library for parallel random number generation, named SPRNG. The goal of this workshop is to place this new high-performance Monte Carlo tool in the context of current and future user needs, applications requirements, recent theoretical results, and future computing trends.

The program for the workshop began with a discussion of issues related to the testing of parallel random numbers given by David Ceperley of NCSA. The next talk, by Simonetta Pagnutti of ENEA-Bologna (Italy), described recent results on the theoretical analysis of correlation found in common parallel random number generators and on the possibility to control correlations' effects during a Monte Carlo computation. This talk was followed by Karl Entacher of the University of Salzburg (Austria) who discussed the geometrical quality of random numbers and another theoretical way to study the quality of random numbers. Miron Livny of the University of Wisconsin then presented his distributed computing package, CONDOR. CONDOR could be a power tool for distributed Monte Carlo, especially when outfitted with SPRNG.

The next cluster of talks focused on different applications areas in Monte Carlo. The various speakers were asked to present their application area in detail and to think about any special random number requirements for their application. Todd Urbatsch of Los Alamos National Laboratory spoke about thermal radiative transfer calculations using time-Implicit Monte Carlo on parallel machines. Besides the algorithmic challenges, this application furnishes some of the most stringent requirements for random numbers. Next, Mal Kalos of Cornell University's Physics Department spoke about new Monte Carlo algorithms for solving the fermionic Schödinger equation. In this talk he also advocated the use of controllably bad random number generators (generators constructed with known correlations) to help understand quality in Monte Carlo computations. This talk was followed by Pavlos Vranas of Columbia University's Physics Department who presented the algorithmics of lattice quantum chromo dynamics and described the construction of a 400 gigaflop lattice QCD machine machine out of commodity DSPs and custom designed ASICs, a considerable undertaking. The applications talk concluded with James Given of the National Institute of Standards and Technology who spoke about a new class of diffusion algorithms for the point solution of elliptic partial differential equations. Besides describing the new algorithms, he described a wide variety of physical quantities that could be calculated effectively with this new methods

On the second day, the morning began with three talks on quasirandom numbers. These are numbers that attempt to be as evenly distributed as possible, but unlike the pseudorandom numbers described on the previous day, do not need to pass statistical tests. Tony Warnock of Los Alamos National Laboratory spoke about some new results that directly impact the use of quasirandom numbers on parallel machines: error bounds for combining of results obtained from different quasirandom streams. It turns out that even though quasirandom numbers have quicker convergence that pseudorandom numbers in some applications, N quasirandom streams combine to reduce the error as O(N ^{1/2}), just like combining pseudorandom number streams!! The next speaker, John Halton from Computer Science at the University of North Carolina, Chapel Hill, proved that result. The third quasirandom number speaker, Giray Ökten of the University of Alaska-Fairbanks, spoke on some new constructions of quasirandom sequences that combine traditional quasirandom sequences with pseudorandom sequences. This series of talks was meant to address some of the mathematical difficulties behind providing parallel streams of quasirandom numbers. During the extensive discussion on this topic, new results on how to use full period pseudorandom numbers to provide many, related, quasirandom streams was presented. This seems like a promising approach that needs more study.

The next speaker was Greg Astfalk, Chief Scientist of Hewlett Packard's High-Performance System's Division. He shared his views on the future of high-performance computing. Two of the most telling points he made are that vector architectural features (such as flat memory [i.e., no cache], low latency, extremely high sustainable memory bandwidth, multiple pipes to memory, hardware support for gather/scatter, efficient single word access, vector instructions -- it is all the other parts of the vector architecture that matter more than the vector instructions themselves) are dead; and that almost all vendors seem to be converging on clusters of SMPs for their high-end products. These clusters will be based on the same SMPs that make up their server and high-end workstation markets: success will be based on maximally leveraging commodity technology. The last two speakers spoke about SPRNG and its suitability for this community. Ashok Srinivasan of NCSA described SPRNG in detail, and Michael Mascagni of the University of Southern Mississippi, presented SPRNG in terms of the design decisions that were made in its implementation. This lead into a broad discussion on whether SPRNG was the right tool for the present, and what are things that an improved SPRNG should have for the future. The conclusion was that SPRNG is well designed for current applications, but that new generators should be designed to better meet the demands of ASCI-class applications. In addition, applications based testing, coupled with a web-accessible test site would serve both the theoretical and applications community. Quasirandom numbers should be made available for parallel and distributed computing, but it was clear that a better mathematical understanding of key issues here will be required, first. The actual discussion topics follow.

 


ashoks@ncsa.uiuc.edu

Last modified: 6 May 1998