Approximation algorithms for task allocation with QoS and energy considerations

We consider general problems of allocating tasks to processors where each task is associated with a set of service classes. A service class is a tuple: the first element represents the resource utilization and the second element the quality of service associated with that resource utilization. Before allocating a task to a processor, we need to assign it to a service class. We consider some elementary problems that arise from this setting. What is the minimum number of processors needed if we also need to attain a minimum aggregate QoS level? Given a fixed set of processors, what is the maximum attainable aggregate QoS? Such questions apply to the partitioned scheduling of real-time tasks on multiprocessors and to other resource allocation problems. The basic questions are NP-Hard, and we present polynomial time approximation algorithms for certain special, but practical, cases. We make interesting use of maximum flows in a bipartite graph while developing the polynomial time approximation schemes. We then integrate energy expenditure to the model above and address the problem of partitioning a set of independent, periodic, real-time tasks over a fixed set of heterogeneous processors while minimizing the energy consumption of the computing platform subject to a guaranteed quality of service requirement. This problem is NP-Hard and we present a fully polynomial time approximation scheme for this problem. The main contribution of our work is in tackling the problem in a completely discrete, and possibly arbitrarily structured, setting. In other words, each processor has a discrete set of speed choices. Each task has a computation time that is dependent on the processor that is chosen to execute the task and on the speed at which that processor is operated. Further, the energy consumption of the system is dependent on the decisions regarding task allocation and speed settings.Applied Science, Faculty ofElectrical and Computer Engineering, Department ofGraduat