For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
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
Publication Date: 2009/04/01
Online ISSN: 1745-1361
Print ISSN: 0916-8532
Type of Manuscript: LETTER
Category: Algorithm Theory
scheduling algorithm, real-time task, parallel task, multicore,
Full Text: PDF>>
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.