Patent ID: 8615763

Claim:
A multiprocessor system employing a power management technique comprising: (a) a plurality of processors for executing a plurality of tasks in a task-set; and, (b) means for allocating the plurality of tasks among the plurality of processors operable to (a) associate a worst-case number of processor cycles C i needed for completion, a period T i , and a deadline D i for each task τ i of a plurality of tasks; (b) calculate a task density d i for each task τ i as follows d i = C i D i ; (c) store each task density d i in a first density array; (d) store each task τ i in non-increasing order of density in a second array; (e) select a processor M j having a minimum task density between d 1 and d n for each task τ i in the second array; (f) add the task τ i to a task allocation array TA j ; (g) perform a first response time test to identify if the selected processor M j can performance the added task τ i without violating its allotted time slot; (h) if the first response time test does not pass, select a processor M j having a next lowest task density between d 1 and d n for each task τ i in the second array and repeat until the first response time test passes; (i) determine a Sys-clock frequency F d i of M j as a minimum frequency enabling processor M j to complete its tasks before their respective deadlines; (j) calculate a harmonicity H i of each task τ i for processors M 1 , . . . , M n as follows H i = ⁢ ∑ j ⁢ { ( T i T j ) - ⌊ T j T j ⌋ } ⁢ ⁢ for ⁢ ⁢ T i < T j , k ≤ n , ⁢ and = ⁢ ∑ j ⁢ { ( T j T i ) - ⌊ T j T i ⌋ } ⁢ ⁢ for ⁢ ⁢ T j < T i ; (k) assign a highest harmonicity processor as M k ; (l) remove task τ i from task allocation array TA j and add task τ i to task allocation array TA k ; (m) perform a second response time test; (n) finding a next highest harmonicity processor if the second response time test fails; (o) repeating the steps (k) to (m) until the second response time test passes; (p) determine the Sys-clock frequency F H i of processor of M k as a minimum frequency enabling processor M k to complete its tasks before their respective deadlines; (q) test the Sys-clock frequency to see if the Sys-clock frequency is greater than F d i ; (r) update density d k and return TA 1 to TA m and return F 1 to F m if F H i is not greater than F d i ; and, (s) otherwise, if F H i is greater than F d i , remove task τ i from TA k and add task τ i to TA j and update density d j .