Efficient and fair scheduling of placement constrained threads on heterogeneous multi-processors

Cloud computing platforms are increasingly deploying multi-processors that are heterogeneous in the resource capacities or functionality of their processors (Instruction Set Architecture, or ISA). ISA heterogeneity (e.g., CPU vs GPU) or administrative policies can additionally create placement constraints whereby certain threads may only execute on a subset of the available cores. Fair CPU scheduling in such settings poses novel challenges that we address in this paper. First, we describe the conditions for a feasible allocation. We then develop a general utility optimal scheduling framework that, when appropriately parameterized, adjusts the trade-off between fairness and throughput, and captures a variety of notions of fairness (proportional fair, max-min fair, etc.). Finally, we design a low-complexity quantum-level scheduling algorithm, called CMFS. We evaluate the efficacy of CMFS via simulations and identify promising future directions.