[ACM Press the eighteenth annual ACM symposium - Cambridge, Massachusetts, USA (2006.07.30-2006.08.02)] Proceedings of the eighteenth annual ACM symposium on Parallelism in algorithms and architectures - SPAA '06 - Reconfigurable resource scheduling
โ Scribed by Plaxton, C. Greg; Sun, Yu; Tiwari, Mitul; Vin, Harrick
- Book ID
- 120838282
- Publisher
- ACM Press
- Year
- 2006
- Tongue
- English
- Weight
- 242 KB
- Edition
- 2006
- Category
- Article
- ISBN-13
- 9781595934529
No coin nor oath required. For personal study only.
โฆ Synopsis
We consider a class of scheduling problems that we refer to as reconfigurable resource scheduling. This class of problems is motivated by emerging applications that involve dynamically allocating a large number of shared resources to a variety of services. We design efficient online algorithms for certain problems in this class. Our goal is to obtain constant competitive online algorithms where the online algorithm is given a constant factor advantage in terms of the number of resources. The main problem considered in this paper is as follows. The input is a sequence of requests, each of which is a set of unit jobs. Each job has a category, and needs to be processed within a fixed delay bound from its arrival, or else it is dropped and we incur a category-specific drop cost. A job of a given category can only be executed on a resource configured for that category. A resource can be reconfigured at any time at a fixed reconfiguration cost. Our main result is a constant competitive online algorithm for this problem, which is obtained by the following layered approach. First, we reduce our main problem to the special case in which all jobs arrive at integral multiples of the delay bound. Second, we reduce the latter problem to the special case of unit delay. Third, we reduce the unit-delay problem to a caching problem that we refer to as file caching with remote reads. Our solution to this caching problem generalizes certain existing work in the area of file caching.
๐ SIMILAR VOLUMES
We consider offline scheduling algorithms that incorporate speed scaling to address the bicriteria problem of minimizing energy consumption and a scheduling metric. For makespan, we give linear-time algorithms to compute all non-dominated solutions for the general uniprocessor problem and for the mu
Sponsored By Acm Sigact, Acm Sigarch, And Organized In Cooperation With The European Association For Theoretical Computer Science & Intel Corporation. Includes Bibliographical References And Author Index. Also Issued Online With Additional Title: Proceedings Of The Sixteenth Annual Acm Symposium On
In this paper we consider the problem of (k, ฮฝ)-balanced graph partitioning -dividing the vertices of a graph into k almost equal size components (each of size less than ฮฝ โข n k ) so that the capacity of edges between different components is minimized. This problem is a natural generalization of sev
Sponsored By Acm Sigact [and] Acm Sigarch In Cooperation With Eatcs. Acm Order Number: 417020--t.p. Verso. Includes Bibliographical References And Author Index. Also Available On The World Wide Web Via Acm Digital Library With Title: Proceedings Of The Fourteenth Annual Acm Symposium On Parallel Alg