Grantee Research Project Results
1999 Progress Report: High-Performance Environmental Models and Class Libraries of Parallel Algorithms
EPA Grant Number: R825293Title: High-Performance Environmental Models and Class Libraries of Parallel Algorithms
Investigators: Sheng, Peter , Rajasekaran, Sanguthevar
Institution: University of Florida
EPA Project Officer: Aja, Hayley
Project Period: January 1, 1997 through December 31, 1999 (Extended to December 31, 2000)
Project Period Covered by this Report: January 1, 1998 through December 31, 1999
Project Amount: $730,605
RFA: High Performance Computing (1996) RFA Text | Recipients Lists
Research Category: Human Health , Aquatic Ecosystems , Environmental Statistics
Objective:
In order to meet the demand for increased spatial and temporal resolution and uncertainty analysis in environmental models for ecological assessment and water resources management, it is essential to develop high-performance hydrodynamics and water quality models using parallel techniques. In our project, we aim to develop such high-performance environmental models and also develop class libraries for parallel numerical solvers. Specifically, we will (i)develop reusable object-model-based class libraries for parallel numerical solvers and scientific processes related to cross-media environmental modeling and uncertainty, (ii)apply the reusable libraries to a multi-dimensional coupled hydrodynamics-water quality model to produce a high performance hydrodynamics and water quality model, (iii)couple the hydrodynamics and water quality models to a GIS (Geographical Information System) model to enhance the processes of model simulation and calibration, (iv)apply the coupled hydrodynamics-water quality-GIS model to Indian River Lagoon in Florida, and (v)make the class libraries of parallel algorithms accessible to EPA scientists via the Internet.Progress Summary:
We have continued our effort on the development of high performance library algorithms, high performance simulation algorithms, as well as the application of high performance algorithms to multi-dimensional hydrodynamics and water quality model.
On the library side, we have completed the implementation of parallel algorithms for the problems of multiplying matrices, solving banded systems of linear equations, and solving a full system of linear equations. Several algorithms such as Gaussian and Czanky's algorithms have been explored for solving a full system. We are currently considering the solution of sparse systems.
In our recent work [1] we have come up with a simple algorithm for external sorting that is not only asymptotically optimal but also practical. It performs better than the DSM algorithm that people use in practice.
External sorting is an important problem in the manipulation of voluminous data not only in simulation but also in other areas of Engineering. This problem has been studied extensively by many researchers in the past decade. Though a number of asymptotically optimal algorithms are known, they are not practical owing to large constants in their time bounds. In fact the algorithm that is used in practice (DSM) is not asymptotically optimal.
On the high performance simulation algorithm side, we have completed the parallelization of 1D explicit and implicit models. For solving the 1D model equations in parallel, we had introduced the notion of communication factor. The idea is to perform some redundant computations in order to reduce the number of communication steps. A normal parallel simulation algorithm will perform a communication step for every step of simulation. In our approach we perform a communication step only once in 10 or 20 steps of simulation. We had reported previously that this idea resulted in impressive speedups. For example we were able to speedup by a factor of 11.4 using 12 processors.
We have used the same idea to the case of 2D explicit model as well. We get good speedups but not as good as in the case of 1D case. The reason is now the value at any grid point depends on five neighboring values and the communication time is correspondingly more.
For the solution of our 1D simulation model, one of the subroutines needed is for solving a tridiagonal system of linear equations. We wanted to identify the best algorithm for solving a tridiagonal system and hence we have compared experimentally many algorithms and have reported under what conditions each algorithm is preferable over the others [2].
We have also extensively investigated available parallel algorithms for solving tridiagonal systems such as the ones in the hydrodynamics model when an implicit time integration method is used. Even though a number of algorithms are available, they are fairly complex. We have discovered a new simple algorithm for solving general banded system of linear equations [3]. This algorithm is optimal and also performs better than the other algorithms we explored. If we have a system of n banded equations (with a constant bandwidth), our new algorithm takes only O(n/P) time using P processors. This algorithm has been tested using PVM as well as MPI.
On the multi-dimensional modeling, in addition to the continued effort on PVM, we have also been investigating "multi-thread" strategies to improve the performance of a three-dimensional hydrodynamics and water quality model [4 and 5] on a 4-CPU SGI Origin-2000 computer. We have conducted preliminary experiments on two different methods aimed to significantly speed up the code by parallelizing the factorized sparse matrix solver for the "propagation" module. However, algorithms for other parts of the 3-D model have not been parallelized. These preliminary tests have been conducted with a numerical grid of 500x100x5 (x-y-z directions) points for Indian River Lagoon, a large coastal lagoon estuary in Florida. This work will continue in 1999 and performance comparison will be made between PVM and multi-thread algorithms.
We have continued the development of a GIS model for coupling with a hydrodynamics and water quality model. The GIS model, developed with ARCVIEW, can accept and display field data from various sources, produce initial conditions for model simulation, as well as process and display results (both scalar quantities and vectors) from a three-dimensional hydrodynamics and water quality model. The GIS model can be used to aid model simulation and facilitate comparison between model results and field data [6].
Future Activities:
We will continue with the development of (i)class libraries for sparse matrices, (ii)multi-thread algorithms for 2-D and 3-D equations, (iii)PVM algorithms for implicit 2-D equations and 3-D equations, (iv)performance comparison between PVM and multi-thread algorithms. In addition, we will further improve the performance of the "multi-thread" 2-D and 3-D model by making use of parallel algorithms for all the model subroutines. Additional model tests will be conducted with a more refined grid. Following further refinement, the GIS model will be linked to the high performance 3-D model as well.Journal Articles on this Report : 2 Displayed | Download in RIS Format
Other project views: | All 15 publications | 3 publications in selected types | All 3 journal articles |
---|
Type | Citation | ||
---|---|---|---|
|
Rajasekaran S. A framework for simple sorting algorithms on parallel disk systems. Theory of Computing Systems 2001;34(2):101-114. |
R825293 (1999) R825293 (Final) |
Exit |
|
Sheng YP. Pollutant load reduction models for estuaries. Spaulding ML, Blemberg AF, eds. Estuarine and Coastal Modeling, V, American Society of Civil Engineers, Proceeding of the Fifth International Conference, 1997, pp. 1-15. |
R825293 (1998) R825293 (1999) |
not available |
Supplemental Keywords:
RFA, Scientific Discipline, Geographic Area, Ecosystem Protection/Environmental Exposure & Risk, State, computing technology, Environmental Monitoring, class libraries, computer science, parallel numerical solvers, reusable components, software reuse, cross-media modeling, data management, MasPar2, component-based software, information technology, parallel computing, water quality modeling, Florida, hydrodynamics, FLRelevant Websites:
http://www.coastal.ufl.edu/~pete
Progress and Final Reports:
Original AbstractThe perspectives, information and conclusions conveyed in research project abstracts, progress reports, final reports, journal abstracts and journal publications convey the viewpoints of the principal investigator and may not represent the views and policies of ORD and EPA. Conclusions drawn by the principal investigators have not been reviewed by the Agency.