Efficient Critical Task Scheduling Parallel Programs on a Bounded Number of Processors

International audienceIn this paper, we present an efffficient algorithm for compile time scheduling of parallel programs on a bounded num ber of processors system with distributed memory. Our algorithm (CTS Critical Task Scheduling) is a greedy list scheduling heuristics based on attribute priority called Task Criticalness wich provides a good measure of the task im portance. CTS has a time complexity of O(ep + v log v) which is better than all the others scheduling algorithms to our knowledge. Experimental results also demonstrate the superiority of CTS over the other algorithms in terms of speed and solution quality