RAPID: Scheduling and Run-Time Support for Parallel Irregular Computations.

S+: Fast Sparse Gaussian Elimination (LU Factorization) Code

This project focuses on the study of scheduling algorithms and software systems for exploiting data, task and loop parallelism on distributed memory architectures and workstation clusters. The fast scheduling algorithms we have developed provide effective utilization of computing resources for directed acyclic graphs, iterative task graphs with and without cycles, and task graphs with data parallelism. The developed techniques can be used for performance prediction and code optimization. The main applications are scientific computations such as sparse matrix factorization arising from numerical solutions to nonlinear equations, adaptive n-body simulations using the fast multipole method, and image processing.

We are developing a run-time system called RAPID which integrates automatic scheduling techniques and efficient communication schemes for irregular task computations with mixed granularities on message-passing distributed memory machines. The system provides a set of library functions for specifying irregular data objects and tasks that access these objects. It extracts a task dependence graph from data access patterns, and executes tasks efficiently on a distributed memory machine.

Our experimental results on Cray-T3D/T3E and Meiko CS-2 indicate that the RAPID system obtains promising performance in sparse matrix problems and n-body simulation. In particular, using the RAPID system we have obtained high megaflop rate for parallel sparse LU/Gaussian elimination with partial pivoting, which is an open parallelization problem in scientific computing literature. We have optimized our sparse LU code with pivoting and have achieved upto 11.04 GFLOPS on 128 Cray T3E nodes, which is the highest megaflops performance in literature. The previous record was 2.583 GFLOPS on a shared memory machine.

Recently we have also worked on scheduling and runtime support for clustering Web and digital library servers .

This project is supported in part by NSF CAREER CCR-9702640 and a DARPA grant (ONR Contract Number N6600197C8534).

Download RAPID1.0 for Cray-T3E.

Selected Publications on scheduling/run-time support and irregular/sparse applications:

Scheduling and run-time support

Sparse matrix solvers and irregular applications

More publications on scheduling and runtime support

Current members:

Past members :
  • Cong Fu (PhD, 1997. Currently with SUN MICRO)
  • Xiangmin Jiao (MS 1997. Currently with UIUC)
  • Bin Jiang (MS 1999. Currently with Environmental Systems Research Institute)

You are visitor No. 1000 since February 5, 1997.