Efficient Scheduling Mechanism For Dynamic Heterogeneous Chip Multiprocessors

The trends in energy-efficient computing and the increasing process variation in underlying fabrication indicate that future chip multiprocessors (CMPs) will feature heterogeneity. The basic idea of performance-asymmetric multicore/manycore architectures is to exploit both single-thread performance through few sophisticated out-of-order cores and thread-level parallelism through a large amount of simple cores. In fact, an asymmetric CMP will only be at its most efficient when the granularity of the processing cores matches the granularity of parallelism in the tasks. However, the concurrency characteristics of tasks may vary widely during different execution phases. This requires the asymmetric CMPs should have the capability of adjusting the granularities of on-chip processing cores according to the characteristics of workloads at runtime. Therefore, recent research has proposed dynamic heterogeneous chip multiprocessors (DHCMPs), which typically consist of a large number of small base core equivalents (BCEs) that can be aggregated to form larger (performance-asymmetric) logical cores. The number and types of logical cores can be dynamically reconfigured by system software at runtime.However, DHCMPs only enable the reconfiguration of chip computing resources (i.e. BCEs), while depending on the system scheduler to estimate the characteristics and resource demands of workloads and exploit the benefits of dynamic heterogeneity. But the scheduling mechanisms and algorithms on DHCMPs have not yet been well studied. Thus, this dissertation aims to build a scheduling framework which can efficiently support the rapid computing resource reconfiguration, while developing a logical core allocation algorithm which can efficiently estimate the resource demands of tasks, and a task scheduling algorithm which can provide priority-based fairness on DHCMPs. The main research contents and achievements can be summarized into the following four aspects:1. Re-explored the hardware/OS interface in the context of DHCMPs. A simple and uniform logic core abstraction was exposed to OS, while six OS-visible primitives were abstracted from the possible reconfiguring operations on DHCMPs. The relationship between process schedule tick and resource allocation tick was also studied, and we found that using the schedule tick is able to match the frequency demands for sampling program phase behavior and adjusting computing resources. 2. Developed a scheduling framework on DHCMPs, which employs the centralized run queue (CRQ) to support the rapid changing number of logical cores. The creation or release of a logical core responds to the enqueue or dequeue operation on CRQ, thus avoiding the expensive updates among per-core data structures. Furthermore, a pipeline-like scheduling scheme was proposed to hide the large decision overhead caused by the CRQ, which makes the CRQ-based scheduling framework be a practical design.3. Exploited the relationship between program phase behavior and the typical microarchitectural parameters. Designed an IPC-based phase detection algorithm that aims to identify program’s execution phases at runtime. Based on this algorithm, a phase-aware efficiency-driven logical core allocation algorithm, PERA, was proposed. By evaluating program’s execution efficiency, PERA estimates the resource demands of each program in each stable phase. Through implementing PERA as a state machine which transfers only one state at each execution, the algorithm can keep O(1) time complexity.4. Proposed an EDP algorithm to provide fair scheduling on DHCMPs. Besides keeping homogeneous tasks to get performance proportional to their priorities, EDP can ensure equal-priority heterogeneous tasks to get equivalent performance affections when running simultaneously. By exploiting the benefits of dynamic heterogeneity, EDP is. also able to improve system performance. Our experimental results demonstrated that, while providing good fairness, EDP on DHCMP outperforms the best performing fair scheduler on fixed symmetric and asymmetric CMPs by as much as26.2%and11.8%in average task turnaround time, and by33.6%and12.5%in system throughput, respectively.The proposed scheduling framework in this dissertation can be used as a general platform to conduct further research on DHCMP-oriented scheduling algorithms. We expect that the logical core allocation algorithm PERA, fair scheduling algorithm EDP, and our exploration on program behavior could be helpful for future scheduling work on asymmetric CMPs. Furthermore, the pipeline-like scheduling scheme can be expanded as a general technique for manycore scheduling.