On the optimality of Feautrier's scheduling algorithm
Feautrier's scheduling algorithm is the most powerful existing algorithm for parallelism detection and extraction, but it has always been known to be suboptimal. However, the question as to whether it may miss some parallelism because of its design has not been answered. We show that this is not the case. Therefore, for an algorithm to find more parallelism than this algorithm, one needs to remove some of the hypotheses underlying its framework. Copyright (C) 2003 John Wiley Sons, Ltd.
scheduling automatic parallelization farkas' lemma vertex method