SHAPE: A Parallelization Tool for Sparse Matrix Computations

We describe the design, implementation and performance of a Sparse Hybrid Automatic Parallelization Environment (SHAPE). SHAPE partitions and schedules sparse matrix computations for Cholesky factorization with the goal of achieving good performance at low cost, while providing flexibility for use as an experimental tool. It employs efficient parallelization algorithms which reduce the communication cost without adversely affecting the load balance by using a hybrid mixture of column and block partitions. Through several parameters, SHAPE aims for portability across a diverse range of sparse matrix structures and message-passing multiprocessors with different communication cost parameters. We present preliminary timing results on the iPSC/860 and compare the performance of SHAPE with that of a commonly used column-based method. The results show that SHAPE significantly reduces computation time, number of messages, and overall communication time for a variety of test matrices.Technical report dcs-tr-29