| Due to the limitations of the chip manufacturing process, the increasing ofprocessor frequency has encountered the physical bottleneck, multiprocessortechnology is considered to be an effective way to maintain the growth inperformance of the on-chip system. Heterogeneous multi-processor system on chip(MPSoC) owns the versatility and flexibility, has caused the common concern ofindustry and academia, and has been widely used in area s such as mobilecommunication, embedded multimedia and so on. For the heterogeneous MPSoC, itsperformance depends on the efficient task scheduling algorithm. An effectivescheduling algorithm can alleviate the problems of high energy consumption, hightemperature, high-cost which are brought by the increasing number of processors,and extend the applications of heterogeneous MPSoC. The optimal scheduling ofheterogeneous MPSoC under a variety of constraints has been proven to be NP-hardproblem. Thus, taking account of the various kinds of application req uirements ofheterogeneous MPSoC, seeking for the optimal scheduling policy for differentoptimization goals has become the focus and hot research of today’s multi-processortechnology.As the development of reconfigurable technology and the MPSoC, one kin d ofheterogeneous MPSoC which contains the reconfigurable resources has appeared.This kind of MPSoC combines the flexibility of MPSoC and the efficiency ofreconfigurable resources, and provides more alternatives for system design andapplication. For the heterogeneous MPSoC which contains reconfigurable resources,task scheduling also needs to partition the software and hardware, which increasesthe complexity of task scheduling further. Considering the heterogeneous MPSoCwhich owns the reconfigurable function, in order to take full use of thereconfigurable resources, address the energy consumption and temperature problemof the heterogeneous MPSoC, we have carried out the research of hardware/softwarepartitioning algorithm, energy-saving scheduling algorithm, and temperature-awarescheduling algorithm respectively. The specific work of the paper is as follows:(1) According to the characteristics of the hardware/software bi-partition, takingthe algorithm of the0/1knapsack problem as a reference, a h ardware/softwarepartitioning algorithm was proposed based on the global optimization features if simulated annealing algorithm which combined the greedy algorithm and thesimulated annealing algorithm. After analyzing the system structure ofhardware/software bi-partitioning, this method reduced the hardware/softwarepartitioning problem to the0/1knapsack problem, and used the greedy algorithm todo the initial rapid partition; then designed a new acceptance criteria to calculate theprobability of acceptance according to the new position of the solution inperturbation model. Based on pre-partitioning results of the greedy algorithm, usedthe improved simulated annealing algorithm to search the global optimal solution.The proposed algorithm combines the efficiency of greedy algorithm and the globaloptimization ability of simulated annealing algorithm, and avoided the difficulty inthe initial partition of simulated annealing algorithm, and expected to have a bettereffect in the quality of the partition and running time of the algorithm. Thesimulation results show the effectiveness of the proposed algorithm.(2) The energy consumption of heterogeneous MPSoC is becoming higher as thenumber of processors increases. Considering the efficient search capab ilities ofgenetic algorithm, using the dynamic voltage scaling techniques, we proposed a newenergy-efficient scheduling algorithm. Firstly, the algorithm improved the selectionoperator and population update mechanism of genetic firstly, which enhance th ediversity of the population. Secondly, using the improved genetic algorithm todetermine the priorities of the task, and then, determined the task execution order bylist scheduling method. Finally, according to the relationship between energy andtime of tasks, we designed a new method to calculate the scaling priority of the task,which is used in energy-efficient scheduling. The proposed algorithm is of theefficient search capabilities of genetic algorithms, and recover the defect that beingeasy to fall into local optimal solution as well. And it scales down the high-energytask, is expected to achieve better system energy.(3) The growth of energy density in heterogeneous MPSoC causes the increase oftemperature. Considering the relationship among the drain power, supply voltage andtemperature, taking the minimizing of system peak temperature as the optimizationtarget, a new temperature-aware scheduling algorithm is proposed. The rising oftemperatures will shorten the life cycle of the processor, and affect the systemperformance and comfort at the same time. Considering the temperature problemwhich hinders the application of heterogeneous MPSoC, we took account of thedrain power of the processor and established a temperature model based on therelationship between temperature and supply voltage. We used the mission-critical path algorithm to schedule at first, calculated the operating temperature of task bythe temperature model, and used the dynamic voltage scaling techniques to optimizethe peak temperature of system by iterative operation. As the temperature model inthis thesis is more practical, and we optimized the task with a peak temperaturedirectly, the system peak temperature is expected to be efficiently reduced.(4) Applications and researches were done on related embedded systems aboutthe proposed task scheduling algorithms. In the project that the development of thekey device based on―Mathematical Separation‖for three-dimensional fluorescencespectrometer from the Research Conditions Innovation Program of Hunan Province,the hardware/software division algorithm is applied and researched. The kernel ofthe component is the―Mathematical Separation‖algorithm, which involves a largenumber of high-dimensional matrix operations and requires works to solve theproblem of complicated computing in embedded applications. After analyzing thecomputational characteristics of the problem, a way of general processor andreconfigurable resource combined was chosen to design the system. Then theproposed hardware/software division scheme was applied to divide the tasks toobtain better performance. The application and research of energy-saving schedulingalgorithm were carried out in―Mobile Learning Platform‖, a sub-project in―ChineseOnline Education Platform‖from the National Development and ReformCommission. Power consumption is the biggest concern on embedded mobileplatforms. PXA255, a platform which has good power management, was decided tobe used to accomplish the system design. The dynamic voltage scaling technique wasimplemented. Based on that, using the proposed energy-saving scheme, the researchof the energy-saving scheduling algorithm was done on the AVS decoding task. Theresults proved the effectiveness of the proposed algorithm. |
PDF Full Text Request