Scalable resource allocation for multi-processor QoS optimization

We present scalable QoS optimization algorithms for allocating resources to tasks in a multi-processor environment. Given a set of tasks, each of which is capable of running at one of several different QoS levels, the algorithms can select a QoS operating point, the number of replicas for fault-tolerance and the processors on which to run the replicas so as to maximize overall system QoS. The algorithms are extensions of Q-RAM (QoS-based Resource Allocation Model) [5] and fix two deficiencies with the basic algorithm. The first is that the existing algorithm is weak in making resource trade-off decisions such as to which processor to map a task. The second was that it was not scalable to very large numbers of resources such as in a large multi-processor system. In this paper we present two new algorithms which significantly enhance the ability of Q-RAM to make resource tradeoff decisions. We also introduce a hierarchical decomposition scheme which enables QoS optimization to be performed on problems with thousands of resources and thousands of tasks.