Premium
On the optimality of Feautrier's scheduling algorithm
Author(s) -
Vivien Frédéric
Publication year - 2003
Publication title -
concurrency and computation: practice and experience
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.309
H-Index - 67
eISSN - 1532-0634
pISSN - 1532-0626
DOI - 10.1002/cpe.780
Subject(s) - computer science , parallelism (grammar) , parallel computing , task parallelism , algorithm , data parallelism , scheduling (production processes) , mathematical optimization , mathematics
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 © 2003 John Wiley & Sons, Ltd.