A Study On A Class Of Online Scheduling Algorithms In Heterogeneous Many-Core Chip

With the rapid development of semiconductor technology,Chip Multi-Processor(CMP)has become a development trend of high-performance microprocessor.The increasing scale of multi-core processors would make dynamic heterogeneity problems brought by unforeseen variable factors such as errors and hardware abrasions in the manufacturing process more conspicuous with each passing day.Unforeseen failures would make each processor core on the chip change during use.They would be different from the predesigned ones on the computing performance,power dissipation and other key parameters.If the scheduling algorithm ignores this difference,big losses on the processor chip?s performance and energy consumption will be caused.In view of the unpredictable dynamic heterogeneous CMP scheduling problems,this paper will carry out the research and improve the existing local search scheduling algorithm.In this paper,the main research work is as follows:First,the simulation platform of the scheduling algorithm with scalability is constructed.The platform is interconnected with multiple single core simulators and can statistically analyze for the performance and energy consumption of each single core simulator.This paper has altered every core configuration and simulated the processor?s degradation caused by hard errors.This platform has the following advantages:(1)Speed scheduling algorithm simulating.(2)Be able to simulate unpredicted heterogeneity CMP.(3)Capable of simulating a large scale on-chip multicore processor.Second,although local search scheduling algorithm has effectively improved the effectiveness of time and energy,it also has used plenty of thread switching and sampling in the process of scheduling decision-making.This paper holds the opinion that a program would not have great changes on computing performance and energy consumption in a more fine-grained execution phase.The scheduling"preference"of a thread in"exchange pair"is basically fixed.The tabu search-based unpredicted scheduling algorithm(TSU)can avoid the occurrence of repeated sampling and reduce the migration frequency and sampling frequency of a thread by using a tabu table.The experimental results have indicated that tabu search scheduling algorithm has had average 33.6%of thread migration and 27.8%of the sampling time less than the local search scheduling algorithm by the cost of more 0.5%ED~2.Further considering that local search scheduling algorithm uses pairwise exchange of random threads to explore the neighborhood,this paper believes that some"thread pairs"have little impact onED~2 after being exchanged,so these threads are unworthy of being exchanged preferentially.This paper has put forward the calculation method of the influence of"thread pair".The"thread pair"with greater influence would have largerED~2 after being exchanged.The impact-based semi-online scheduling algorithm(IBS)can improve the convergence speed of the scheduling algorithm by preferentially exchanging those"thread pairs"with greater influences.Experimental results show that impact-based semi-online scheduling algorithm get optimal assignment in shorter time than local search scheduling algorithm.Experimental results show that on 25 power management interval,IBS scheduling algorithm average decreased by 2.49%ED~2 than local search scheduling algorithm;in 8 core CMP,when the number of power management interval is less than 70,ED~2 of IBS scheduling algorithm is always lower than the local search algorithm's.