Processor-Minimum Scheduling of Real-Time Parallel Tasks

Wan Yeon LEE  Kyungwoo LEE  Kyong Hoon KIM  Young Woong KO  

IEICE TRANSACTIONS on Information and Systems   Vol.E92-D   No.4   pp.723-726
Publication Date: 2009/04/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.E92.D.723
Print ISSN: 0916-8532
Type of Manuscript: LETTER
Category: Algorithm Theory
scheduling algorithm,  real-time task,  parallel task,  multicore,  

Full Text: PDF>>
Buy this Article

We propose a polynomial-time algorithm for the scheduling of real-time parallel tasks on multicore processors. The proposed algorithm always finds a feasible schedule using the minimum number of processing cores, where tasks have properties of linear speedup, flexible preemption, arbitrary deadlines and arrivals, and parallelism bound. The time complexity of the proposed algorithm is O(M3log N) for M tasks and N processors in the worst case.