A new O(n log n) scheduling heuristic for parallel decomposition of sparse matrices

The problem of sparse matrix decomposition using distributed memory multiprocessors is addressed. The data partitioning scheme is simple and is based on equalizing the load among the processors. A new O(n log n) task scheduling heuristic with provably deadlock-free properties is presented. The key idea is the ordering of nodes in a task graph that represents the matrix decomposition steps in a levelized manner, based on a new measure, δ the remaining completion time. The method tends to minimize the idle time of processors by revising the overall decomposition schedule by permitting the execution of tasks within these idle periods. For large sparse matrices, the analysis and simulation results show that a multiprocessor with even a small number of processors will exceed the performance of a supercomputer like the Cray X-MP