Predictive Heterogeneity-Aware Application Scheduling for Chip Multiprocessors

Single-ISA heterogeneous chip multiprocessor (CMP) is not only an attractive design paradigm but also is expected to occur as a consequence of manufacturing imperfections, such as process variation and permanent faults. Process variation could cause cores to have different maximum frequencies; whereas permanent faults could cause losses of functional units and/or cache banks randomly distributed on cores, resulting in fine-grained heterogeneous CMPs. Hence, application schedulers for CMPs need to be aware of such heterogeneity to avoid pathological scheduling decisions. However, existing heterogeneity-aware scheduling schemes rely on either trial runs or offline profiled information to schedule the applications, which incur significant performance degradation and are impractical to implement. This paper presents a dynamic and predictive application scheduler for single-ISA heterogeneous CMPs. It uses a set of hardware-efficient online profilers and an analytical performance model to simultaneously predict the applications performance on different cores. Based on the predicted performance, the scheduler identifies and enforces near-optimal application assignment for each scheduling interval without any trial runs or offline profiling. We demonstrate that, using only a few kilo-bytes of extra hardware, the proposed heterogeneity-aware scheduler improves the system throughput by an average of 20.8 percent and the weighted speedup by 11.3 percent compared with the commodity OpenSolaris scheduler. Compared with the best known research scheduler, the proposed scheduler also improves the throughput by 11.4 percent and the weighted speedup by 6.8 percent.