Solving Irregularly Structured Problems
Efficient parallel solutions have been found to many problems. However, there still exists a large class of problems, known as irregularly structured problems, that lack efficient solutions and systems support. This issue is devoted to solving irregularly structured problems. Paper selection is based on the Sixth International Workshop on Solving Irregularly Structured Problems in Parallel (Irregular '99).
The nine papers in this special issue can be classifed in four categories:
- Sparse matrix solvers Ng and Raghavan present their current design and experience in developing a scalable and memory-efficient hybrid of Cholesky factorization and Conjugate Gradients for solving sparse matrix systems. Pellegrini, Roman, and Amestoy present a tight coupling of the nested dissection and Halo approximate minimum degree algorithms to reduce fill-ins and increase concurrency in sparse matrix ordering.
Mesh partitioning
Heber, Biswas, and Gao propose self-avoiding walks as a novel technique to linearize a unstructured mesh. This technique is very useful in the runtime partitioning and load balancing of adaptive grids. Chen and Taylor present ParaPART, a parallel mesh partitioning tool for distributed systems. The system uses parallel simulated annealing to optimize execution performance in distributed environments.
System supports for parallel irregular computation
Lin and Padua present a framework to efficiently calculate the array reaching definition at the statement level, which can facilitate the automatic detection of parallelism in sparse and irregular programs. Benkner presents a language extension (called Halos) for optimizing irregular applications written in High Performance Fortran (HPF). Halo specifies non-local access patterns of distributed arrays and this information can be used by compilers and runtime systems for fast computation and communication. Everaars, Arbab, and Koren present their experience with a new coordination language called MANIFOLD in restructuring a sequential CFD code written in Fortran. This language is suitable for applications involving dynamic process composition and communication patterns.