New Cost Metrics for Iterative Task Assignment Algorithms in Heterogeneous Computing Systems

Task assignment and scheduling algorithms for Hetero-geneous computing systems can be classified as iterative and non-iterative techniques, and are designed to optimize a specific cost function defined on the system. The quality of the solutions generated is controlled by the nature of this cost metric. The common metrics that are used include min-imizing the overall execution time or minimizing the load on the maximum loaded processor. In this work, a new set of cost metrics have been proposed that can be used by itera-tive task assignment algorithms. These metrics exploit the fact that in iterative algorithms the mapping of the subtasks to the processors is known at every iteration. They reflect the actual scheduling cost of the application, thereby im-proving the quality of the solutions generated by the algo-rithm. The proposed metrics are evaluated using the learn-ing automata based iterative algorithm [15]. Observations are made regarding the nature of the metrics from the re-sults obtained