Parallelization of a critical path algorithm on a computer with shared memory

In this paper, we consider parallelisation on a parallel computer with shared memory of the critical path algorithm for 2-steps graph with constant task cost. This graph occurs in the parallelisation of block triangular linear system resolution. We present the parallel execution time including the communication cost of the critical path algorithm and we theoretically and practically determine the optimal value of the block size which minimises the parallel execution time.