Apportionment Heuristics for Mapping Tasks in Heterogeneous Computing Systems

Abstract

One of the biggest problems in heterogeneous computing is how tasks should be mapped in these kinds of environments. Because this problem of mapping tasks has been shown to be NP-complete, it requires heuristic techniques. Therefore, we present new schedulers based on the apportionment methods used in elections. In order to obtain the performances of these schedulers we compare them with other known and used heuristics in many different parameters. The presented heuristics can be used when the tasks are big and when they can be divided in smaller sub-tasks. The idea behind the new schedulers is to use apportionment methods (used for elections), such as: the Hamilton’s method, Jefferson’s Method, Webster’s method, Huntington-Hill method, Balance method and pure proportional method. Intuitively the Hamilton’s method favors the bigger tasks (i.e. gives them more CPU power). The comparison in this paper shows that these apportionment methods can cope well with the other methods when the number of tasks in the system is no bigger than a certain level. The new apportionment scheduler, based on Hamilton’s method, copes well with the existing ones and it outperforms the other schedulers when some conditions are met.