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
- C. Fu and T. Yang,
Run-time Compilation for Parallel Sparse Matrix Computations,
in Proc. of the 10th ACM International Conference on Supercomputing,
Philadelphia, pp. 237-244, May, 1996.
Talk slides.
- C. Fu and T. Yang, Sparse LU Factorization with Partial Pivoting
on Distributed Memory Machines.To appear in ACM/IEEE SuperComputing'96,
November, 1996, Pittsburgh.
HTML and
Postscript
A long version is the technical report
TRCS96-18.
- C. Fu and T. Yang,
Efficient Run-time Support for Irregular Task Computations with Mixed
Granularities,
in Proc. of IPPS '96 - 10th Inter. Parallel Processing Symposium , IEEE.
Hawaii, pp. 823-830, April, 1996.
Talk slides.
- C. Fu, T. Yang, and A. Gerasoulis,
Integrating software pipelining and graph scheduling for iterative
scientific computing,
Lecture Notes in Computer Science,
Proc. of Irregular '95, Lyon, France, Sept. 1995, pp. 127-141.
- T. Yang, C. Fu, A. Gerasoulis and V. Sarkar,
Mapping
iterative task graphs on distributed-memory machines.
Proc. of 24th Inter. Conference on
Parallel Processing, Aug. 1995, Vol II, pp. 151-158.
- T. Yang, C. Fu,
Heuristic Algorithms for Scheduling Iterative
Task Computations on Distributed Memory Machines,
Technical Report TRCS95-16,
Dept. of Computer Science, UCSB, 1995.
- T. Yang, O. Ibarra,
Performance Prediction in Symbolic Scheduling of Partitioned
Programs with Weight Variation .
To appear in Journal of Parallel and Distributed Computing.
A short version appears in Proceedings of IEEE SPDP'95.
Back to Parallel
Systems Lab Home Page or
Back to CS Department Home Page
You are visitor No.
since February 5, 1996.