Date: Wed, 15 Jan 1997 00:35:12 GMT Server: Apache/1.0.2 Content-type: text/html Content-length: 4871 Last-modified: Wed, 27 Nov 1996 22:58:50 GMT RAPID

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

This project focuses on the study of scheduling algorithms for exploiting data, task and loop parallelism, and the development of run-time support on message-passing architectures. 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 main applications are targeted at 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 and Meiko CS-2 indicate that the system obtains promising performance in sparse matrix problems for which actual speedups have been hard to obtain in the literature. In particular, using the RAPID system we have obtained good performance for parallel sparse LU/Gaussian elimination with partial pivoting, which is an open parallelization problem in scientific computing literature.

Contact persons: Cong Fu (cfu@cs.ucsb.edu), Prof. Tao Yang (tyang@cs.ucsb.edu)

Selected Publications

More related publications


Back to Parallel Systems Lab Home Page or Back to CS Department Home Page

You are visitor No. since February 5, 1996.