Evolutionary Game for Task Mapping in Resource Constrained Heterogeneous Environments

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%.