Research Of Some Scheduling Problems For Asymmetric Multi-core Processors

Owing to the limit of chip integration scale, power consumption and cost, multi-coreprocessor has gradually become the mainstream of the market. Asymmetric multi-coreprocessor has been proposed as a more performance, power and area efficient alternative to itssymmetric counterpart, and will be the mainstream of computer architecture in the near future.The state of the art scheduling algorithms cannot exploit the asymmeitic multi-core processors,since they have originated from the single-core processors and only been reinforced for thesymmetric multi-processors. This dissertation investigates scheduling problems onasymmetric multi-core processors to improve performance, power efficiency and fairness.Specifically, this dissertation focuses on4important scheduling problems as follows:(1) To solve the problem of signle-threaded task scheduling in Operating Systems (OS) onasymmetric multi-core processors, this dissertation models and analyzes the problem,taking various factors into account. Moreover, this dissertation proposes a comprehensivescheduling algorithm, which adopts the scheduling policies of behavior matching,migration avoiding, and load balancin. The algorithm has two parts: an integratedworkload characterization, which proposes integrated behavior to measure the global andlocal behaviors of tasks comprehensively, and an integrated behavior-based schedulingalgorithm, which efficiently utilizes the asymmetric multi-core processors withoutfrequent task migration. This guarantees the load balance between cores. In addition, thealgorithm achieves universality with a flexible parameter adjustment mechanism. It is analgorithm to achieve universality as well as the first to handle the global and localbehaviors of tasks comprehensively. The evaluation on real platform demonstrates thatthe algorithm is universal for different conditions, and it always outperforms otherscheduling algorithms on asymmetric multi-core processors (by6%~22%).(2) To solve the problem of multi-threaded task scheduling in OS on asymmetric multi-coreprocessors, this dissertation models and analyzes the problem, taking various factors intoaccount. Moreover, this dissertation proposes an integrated scheduling algorithm, with three features:1) comprehensively considering synchronization characteristics ofmulti-threaded tasks, asymmetry and load of cores;2) integrating thread scheduling anddynamic voltage and frequency scaling (DVFS) in OS to improve energy efficiency;3)achieving universality with a flexible parameter adjustment mechanism. It is the firstalgorithm to exploit thread scheduling and DVFS on AMP simultaneously. Theevaluation on real platform demonstrates that the algorithm is universal for differentconditions and it always outperforms other scheduling algorithms on asymmetricmulti-core processors (by24%~50%).(3) To solve the problem of Virtual CPU (VCPU) fair scheduling on asymmetric multi-coreprocessors, this dissertation models and analyzes the problem, taking various factors intoaccount. Moreover, this dissertation proposes a composite scheduling algorithm, withthree features:1) comprehensively considering synchronization characteristics of VCPUs,asymmetry and load of cores;2) defining the concepts of utility factor, scaled factor andscaled resource to measure the load and resource comprehensively, in whichsynchronization characteristics of VCPUs and asymmetry of cores are taken into account;3) decomposing the run queues of cores to reduce overhead of scheduling. It is the firstalgorithm to exploit the synchronization characteristics of VCPUs on AMP. Theevaluation on real platform demonstrates that the algorithm achieves fair scheduling andit always outperforms other scheduling algorithms on asymmetric multi-core processors(by19%~48%).(4) To solve the problem of VCPU high energy efficient scheduling on asymmetricmulti-core processors, this dissertation proposes a Parallelism-aware Scheduler (PS),which integrates VCPU scheduling and DVFS. PS dynamically detects parallelism of thedomain with a non-invasive approach, then determines and executes co-scheduling ofVCPUs on asymmetric cores. With a novel delay co-scheduling algorithm, differentparallel domains are enabled to perform co-scheduling simultaneously without conflictsin PS. The evaluation on real platform demonstrates that the performance and energyefficiency improvement achieved by PS are significant, reaching up to26%and65% respectively. Furthermore, the overheads of PS are comparable to those of the nativescheduler, and lower than those of state-of-the-art asymmetry-aware hypervisorschedulers.