TY - JOUR
T1 - Evolutionary Game for Task Mapping in Resource Constrained Heterogeneous Environments
AU - Madeo, Dario
AU - Mazumdar, Somnath
AU - Mocenni, Chiara
AU - Zingone, Roberto
PY - 2020/7
Y1 - 2020/7
N2 - Power-aware computing is becoming popular using heterogeneous ecosystem. For recent execution units, the heterogeneity is exhibited via the hybrid cores, as well as via virtual and physical asymmetric cores. The inherent performance disparity between different types of execution units at their different clock frequencies offers a great resources scheduling challenge. Multiple metrics (such as throughput, latency, energy cost) are used to decide whether the scheduling is an optimal solution or not. However, in heterogeneous ecosystem, tasks distribution aiming at optimizing costs is not trivial. During the task mapping, one of the primary challenges is to dynamically identify and map the inherent advantages/features of the heterogeneous or hybrid architectures for each individual task. In this work we deal with the task mapping problem using a multi-objective formulation based on evolutionary game theory to optimize a suitable payoff function. This payoff accounts for the power, workload imbalance, task resource affinity and data offloading costs (from host to accelerator). Here, we report that in a very restrictive resource usage scenario (supporting both over and under subscription), the proposed formulation based on Evolutionary Games on Network equation (EGN) can outperform the traditional resource allocation heuristics (such as best-fit, first-fit). Using an extensive set of simulations, we show that our proposed model can outperform first-fit algorithm from more than 5% up to 34.6% and best-fit algorithm from 4% up to 35.7%.
AB - Power-aware computing is becoming popular using heterogeneous ecosystem. For recent execution units, the heterogeneity is exhibited via the hybrid cores, as well as via virtual and physical asymmetric cores. The inherent performance disparity between different types of execution units at their different clock frequencies offers a great resources scheduling challenge. Multiple metrics (such as throughput, latency, energy cost) are used to decide whether the scheduling is an optimal solution or not. However, in heterogeneous ecosystem, tasks distribution aiming at optimizing costs is not trivial. During the task mapping, one of the primary challenges is to dynamically identify and map the inherent advantages/features of the heterogeneous or hybrid architectures for each individual task. In this work we deal with the task mapping problem using a multi-objective formulation based on evolutionary game theory to optimize a suitable payoff function. This payoff accounts for the power, workload imbalance, task resource affinity and data offloading costs (from host to accelerator). Here, we report that in a very restrictive resource usage scenario (supporting both over and under subscription), the proposed formulation based on Evolutionary Games on Network equation (EGN) can outperform the traditional resource allocation heuristics (such as best-fit, first-fit). Using an extensive set of simulations, we show that our proposed model can outperform first-fit algorithm from more than 5% up to 34.6% and best-fit algorithm from 4% up to 35.7%.
KW - Cost optimization
KW - Evolutionary game theory
KW - Heterogeneous computing
KW - Task allocation
KW - Cost optimization
KW - Evolutionary game theory
KW - Heterogeneous computing
KW - Task allocation
U2 - 10.1016/j.future.2020.03.026
DO - 10.1016/j.future.2020.03.026
M3 - Journal article
SN - 0167-739X
VL - 108
SP - 762
EP - 776
JO - Future Generation Computer Systems - The International Journal of eScience
JF - Future Generation Computer Systems - The International Journal of eScience
ER -