+ + + RELATED WEBSITES: Emeagwali's Website

Reservoir modeling in the oil industry, important enough that 10% of existing supercomputers are devoted to it, also played a critical role in this year's Gordon Bell competition. In fact, the applications in both of the winning entries --- one a seismic model developed by a team from Mobil Research and Development and Thinking Machines Corporation and the other an oil reservoir simulation submitted by a graduate student from the University of Michigan --- were problems from the oil industry. ... Gordon Bell (left) congratulating Philip Emeagwali. The Gordon Bell Prizes are designed to stimulate advances in practical applications of parallel computing. ... The winner in the price/performance category was Philip Emeagwali of the University of Michigan. Emeagwali's oil reservoir simulation model, also implemented on the Connection Machine 2, achieved 365 megaflops per million dollars --- a seven fold improvement over last year's winning entry. "I have checked with several reservoir engineers who feel that his calculation is of real importance and very fast," says Karp. "His explicit method not only generates lots of megaflops, but solves problems faster than implicit methods." Emeagwali is the first to ave applied a pseudo-time approach in reservoir modeling, according to Karp. The awards were presented in February at COMPCON, the IEEE Computer Society's annual spring conference, held in San Francisco. In addition to Karp, the judges were Jack Dongarra (Oak Ridge National Laboratory), Ken Kennedy (Rice University), and David Kuck (University of Illinois). ... The implementation of a petroleum reservoir simulation (in general, a system of multidimensional PDEs) on a massively parallel supercomputer poses enormous mathematical and programming challenges: 1. formulation of a set of governing equations that adequately describe the flow behavior of oil reservoirs and at the same yield good algorithms that are suitable for the machine architecture; 2. design of an algorithm suitable for the architecture and the interprocessor topology; 3. reduction of interprocessor communication time; and 4. decomposition and even distribution of the workload among the processors. The excessively small time-steps required by explicit finite-difference models of oil reservoirs make such models highly inefficient. Theoretical analysis has shown, however, that the magnitude of the allowable time-steps is directly proportional to the square root of the magnitude of the temporal inertial force of the flowing fluid. In many practical situations the acceleration force (the temporal and the convective inertial forces) is several orders of magnitude smaller than the other forces and is therefore neglected in the currently used reservoir equations. Emeagwali's approach was to retain the original convective inertial force and to increase the temporal inertial force artificially. Surprisingly, increases of more than a thousand-fold did not significantly reduce the accuracy of the model. In fact, the stability of the explicit approximations used to discretize the different governing equations was improved drastically, making it possible to use time-steps of several hours instead of a few seconds. In addition, the resulting governing equations were hyperbolic rather than parabolic. In addition to the improved stability properties, the new formulation has other good properties: 1. The numerical approximations of the complete equations allow the direct calculation of the fluid velocity, and such calculations are usually more accurate. 2. The use of only Dirichlet-type boundary conditions yields more accurate numerical solutions in the vicinity of production wells located near the boundary. 3. When the flow becomes turbulent, Darcy's law does not hold, and the governing PDEs currently used are no longer valid. With the complete formulation, conversely, turbulent flows can be conveniently accounted for a quadratic term or some other appropriate empirical relationship to describe the source terms of its conservation of momentum equations. 4. With the complete equations, some of the numerical techniques that have been developed for the solution of hyperbolic conservation laws can be borrowed. Click here for full-scale Connection Machine photograph Interprocessor communication time is one of the main obstacles to very high performance levels on massively parallel computers. Emeagwali approached this problem by creating 128 "artificial," or virtual, processors within each of the CM's 65,536 physical processors (a virtual processor ratio of 128). The challenge then became one of decomposing and distributing the workload evenly among the more than 8 million virtual processors. Although in theory the number of virtual processors that can be created is arbitrary, it is limited in practice by the available memory, since the memory of each physical processor is divided equally among the virtual processors. Each instruction sent to a physical processor is repeated once for each virtual processor within it. Performance does not improve in proportion with the virtual processor ratio, although the close physical location of data in the virtual processors sharing the same memory reduces interprocessor communication time. To balance the workload evenly among processors, Emeagwali used an array shape and dimensions that match the shape and dimensions of the CM processor interconnection topology. The "cshift" command was used to perform all required interprocessor communications effectively. The grid point calculations, which at that point consisted of simple scalar-matrix operations, were then performed simultaneously with no further interprocessor communication. Inherent Parallelism Oil reservoir simulation and a large class of seismic problems are inherently parallel problems. The governing laws are the same at all locations, and interactions are assumed to be local over small times. Parallel computers operating in SIMD mode, as demonstrated by this year's Gordon Bell Prize winners, are a natural, efficient, and cost-effective processing tool for their solution. Reported in SIAM News, May 1990. Click on this icon to Click on emeagwali.com for more information.