Research On The Scheduling Algorithm For The Chip Multi-Processors

As the IC fabrication technology evolving, the performance of single-core processor has been dramatically improved. For the further improvement on its performance, we are facing the problems of unmatched rate between processor and external memory, the instruction level parallelization and the huge energy consumption of the single-core processor. Chip Multi-processors(CMPs), as an effective solution to the above problems, receives widely attentions. CMPs, including Network-on-Chip(NoC), is famous for its high computing capacity, high parallel mechanism and low energy profile, which makes it a good candidate for applications like wireless communication, video/image processing, cloud computing and etc, and it is a research hotspot in the related field. Although much has studied researched during past a few years, lagging of research in some areas is still limiting the application of multicores. One of these areas is the task scheduling algorithm for multicore processors.Task scheduling is the process of allocating computing resource to tasks from both time and space dimensions. A good task scheduling algorithm is critical to improve the performance of multicore-processor-based system. This dissertation focuses on the task scheduling problem of multicore processor, and aims at the real-time task scheduling and the DAG task scheduling on multicores. The contribution of our work is as follow:1. In the research of real-time task scheduling on multicore processor, we simulate and compare the performance of three widely used scheduling heuristics: Genetic Algorithm(GA), Particle Swarm Optimization(PSO) and Simulated Annealing(SA). For the best performer, particle swarm optimization, we propose a load-balanced smallest position value algorithm and a hybrid PSO to further improve its performance. Simulation results show that our proposal has better workload balance as well as the overall performance comparing with the original one.2. In the research of DAG task scheduling on NoC, we propose an Energy-Efficient Scheduling algorithm for NoC-based MPSoC(EES-MPNoC). The scheduling algorithm adopts the schedule length as the primary goal. Under constraint of minimal makespan scheduling, it uses minimal hops scheduling and a computational slack time based DVS to optimize NoC energy and processor energy. The simulation results show that our algorithm, compared to the conventional LBL scheduling algorithm, produces 3% shorter makespan, and saves 13% more data routing energy of NoC on average.3. The schedule solution evaluation of real-time task scheduling on multicores is addressed, and the Data Envelopment Analysis(DEA) is introduced. Three common metrics are extracted from the real-time task scheduling problem, and are used to construct multi-input multi-output Decision Making Unit(DMU) model. Based on the DMU model, a schedule solution evaluation method using BCC super efficiency is discussed. Then the evaluation method is combined with genetic scheduling algorithm, and a DEA-GA is proposed. By comparing to other multi-objective scheduling algorithm in simulations, our proposal always produces more efficient schedule solutions.4. The DEA approach is then introduced to the DAG task scheduling problem on NoC. The corresponding DMU model is constructed, and FDH model is applied to evaluate the efficiency of schedule solutions. Then a FDH cross efficiency method is proposed based on the peer-appraisal process. Finally, combining with GA, we propose a CrossFDH-GA for the task scheduling problem on NoC. According to our simulation results, the proposed FDH cross efficiency effectively distinguishes the schedule solutions according to the balance of their metrics, and our CrosFDH always output more metric-balanced schedule than other global criterion GAs.