Title :
Real-Time Scheduling of Parallel Tasks on Fewest Processors
Author :
Lee, Wan Yeon ; Ko, Young Woong
Author_Institution :
Hallym University, Chunchon 200-702, South Korea
Abstract :
A polynomial-time scheduling algorithm is proposed for the real-time parallel tasks on multiprocessors. The algorithm always finds a feasible schedule using the fewest processors. The tasks have the properties of linear speedup, flexible preemption, bounded parallelism, arbitrary arrivals and sequential deadlines with the order of Last Come First Service(LCFS). The time complexity of the algorithm is (M2 ?? N2) for M tasks and N processors, in the worst case.
Keywords :
Aerospace simulation; Bandwidth; Geographic Information Systems; Multiprocessing systems; Optimal scheduling; Parallel processing; Polynomials; Processor scheduling; Real time systems; Scheduling algorithm;
Conference_Titel :
Hybrid Information Technology, 2006. ICHIT '06. International Conference on
Conference_Location :
Cheju Island
Print_ISBN :
0-7695-2674-8
DOI :
10.1109/ICHIT.2006.253662
