Apportionment Heuristics for Mapping Tasks in Heterogeneous Computing Systems
Date Issued
2011-09-14
Author(s)
Kocarev, Ljupcho
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.
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.
Subjects
File(s)![Thumbnail Image]()
Loading...
Name
Apportionment_Heuristics_for_Mapping_Tas.pdf
Size
159.45 KB
Format
Adobe PDF
Checksum
(MD5):553886bb9cb123be4ebe900b11f23ab7