Research For The Low-power Scheduling Algorithm Based On Heterogeneous Multi-core System

As the computing power of heterogeneous multi-core processors increasessignificantly, energy consumption has also become a performance bottleneckrestricting its development and application promotion. The low-power designtechniques closer to the top, the higher the level of abstraction, the greater the impacton power consumption. So the research of real-time low-power scheduling algorithmfor heterogeneous multi-core processor systems has got extensive attention fromresearchers at home and abroad.Heterogeneous multi-core low-power scheduling problem is a typicalNP(non-polynomial) hard problem. Existing algorithms to solve the problem mostlyuse a two-stage heuristic strategies: First, tasks are assigned to each processing unitby a partitioning strategy. And then, the task’s execution order and voltage ofprocessing unit are determined by low-power task scheduling policy. However, thesealgorithms mostly ignored the time complexity of the algorithm and the task-relatedcharacteristics’s impact on the low-power technology energy saving. Therefore, in thelight of the characteristics of heterogeneous multi-core processor system model, basedon the strong golbal optimization capability of chemical reactions optimizationalgorithm, combined with effective control of sheduling length of key tasks, taskpower consumption and time properties’ impact on low-power energy-savingtechnology, we propose a high energy-saving efficient and a fast convergentheterogeneous multi-core low-power scheduling algorithm. The main work are asfollows:First, we design a task portioning algorithm based on chemical reactionoptimization, CROTM(Chemical Reaction Optimization for Task Mapping). CRO is ameta-heuristic algorithm by simulating chemical reactions in molecular motion. Thecore of CRO is four elementary reactions: On-wall Ineffective Collision,Decomposition, Inter-molecular Ineffective Collision and Synthesis. Inter-molecularIneffective Collision and On-wall Ineffective Collision can search the local optimalvalue effectively. In order to prevent search stagnation in local optimal value,Synthesis and Decomposition can effectively expand the search field, and thus getcloser to the global optimum value. CROTM takes full advantage of CRO andbroadens the search space effectively, so it significantly improves the possibility ofgetting the global optimum. In the stage of algorithm’s low-power operation, since the existing strategieshave high time complexity and ignore task-related characteristics’s impact on thelow-power technology energy saving, by the analysis on the basis of existingalgorithms, combined with the current popular dynamic voltage scaling technology,based on the feature that the scheduling length can be effectively controlled by keytasks, this paper proposes an algorithm considering the task power consumption andtime properties’s impact on low-power energy-saving effect at the same time. Fist,scheduling tasks by the priority which determined by the key task, thereby reducingthe scheduling length to extend the relaxation time, increasing the potential of thesystem to reduce the power consumption. Then according to the relationship betweenenergy consumption and time characteristics of tasks, we design a new method tocalculate the scaling priority of the task. To optimize the system energy consumptionin each iteration, repeatedly selectting task which has the best energy-saving effect tovoltage regulate under the condition of meeting the deadline and dependencies.In order to verify the above algorithms, the paper programs the algorithms usingthe TGFF tool and C++program description language and does some comparativeanalysis of the algorithm runtime and energy saving rate. The experimental resultshows that task partitioning strategy proposed in this paper effectively expands thesolution space and provides more extensive task allocation scheme for the followinglow power scheduling. Low-power scheduling strategy proposed in this paper reducesenergy consumption significantly and time complexity effectively at the same time.