RELATED 
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:
The excessively small timesteps required by explicit finitedifference models of oil reservoirs make such models highly inefficient. Theoretical analysis has shown, however, that the magnitude of the allowable timesteps 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 thousandfold 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 timesteps 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:
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 scalarmatrix 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 costeffective processing tool for their solution.
Click on emeagwali.com for more information.
