Analysis of Parameterized Methods for Problem Partitioning

It is anticipated that in order to make effective use of many future high performance architectures, programs will have to exhibit at least a medium grained parallelism. Methods for aggregating work represented by a directed acyclic graph are of particular interest for use in conjunction with techniques under development for the automated exploitation of parallelism. In this paper we carry out an investigation into methods appropriate for the aggregation, mapping and scheduling of relatively fine grained computations specified by a directed acyclic graph. The solution of very sparse triangular linear systems provides a useful model problem for use in exploring these heuristics. A number of questions that relate to partitioning the work required to solve sparse triangular linear systems are consequently explored. A method is described for using the triangular matrix to generate a parameterized assignment of work to processors and simple expressions are derived that specify the scheduling of computational work. The tradeoffs between load imbalance and synchronization costs as a function of two orthogonal measures of granularity, block size and window size are examined experimentally on a shared memory machine, as well as analytically in the context of a model problem