A PTAS for assigning sporadic tasks on two-type heterogeneous multiprocessors
Ref: HURRAY-TR-120903 Publication Date: 4 to 7, Dec, 2012
A PTAS for assigning sporadic tasks on two-type heterogeneous multiprocessors
Ref: HURRAY-TR-120903 Publication Date: 4 to 7, Dec, 2012Abstract:
Consider the problem of determining a task-to-processor assignment for a given collection of implicit-deadline sporadic tasks upon a multiprocessor platform in which there are two distinct kinds of processors. We propose a polynomial-time approximation scheme (PTAS) for this problem. It offers the following guarantee: for a given task set and a given platform, if there exists a feasible task-to-processor assignment, then given an input parameter, e, our PTAS succeeds, in polynomial time, in finding such a feasible task-to-processor assignment on a platform in which each processor is 1+3e times faster. In the simulations, our PTAS outperforms prior state-of-the-art PTAS and also for the vast majority of task sets, it requires significantly smaller processor speedup than (its upper bound of) 1+3e for successfully determining a feasible task-to-processor assignment.
Gurulingesh Raravi
Vincent NélisDocument:
View
Download33rd IEEE Real-Time Systems Symposium (RTSS 2012), IEEE, pp 117-126.
San Juan, Puerto Rico.
DOI:10.1109/RTSS.2012.64.
Record Date: 10, Sep, 2012