Parallelizing the Critical Path

For many parallel matrix computations the execution time is determinedby the length of the critical path. The baseline approach used to reduce the execution time is to adjust the task granularity. If the tasks are made smaller, the length of the critical path will decrease and by extension reduce the execution time for the computation. However, reducing the size of the tasks lowers the efficiency and adds parallel overhead. Another way to lessen the impact of the critical path is to parallelize the critical tasks. In theory, this would speed up the execution of the critical path while avoiding the problems associated with a finer granularity for the non-critical tasks. The aim of this paper is to investigate if an extended approach that incorporates a parallelization of the critical path, in addition to adjusting the granularity, can significantly outperform the baseline approach of simply adjusting the granularity. A comparative study is presented that measures the extended approach’s performance against the baseline approach, using triangular linear solve as the reference computation. The results show that the extended approach can outperform the baseline approach, most notably when there is an abundance of available cores. Redistribution of data and a change in the parallel task model are identified as possible areas of improvement