๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

[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


[ACM Press the eighteenth annual ACM sym
โœ Bunde, David P. ๐Ÿ“‚ Article ๐Ÿ“… 2006 ๐Ÿ› ACM Press ๐ŸŒ English โš– 166 KB

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

[ACM Press the sixteenth annual ACM symp
โœ Andreev, Konstantin; Rรคcke, Harald ๐Ÿ“‚ Article ๐Ÿ“… 2004 ๐Ÿ› ACM Press ๐ŸŒ English โš– 127 KB

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

[ACM Press the sixteenth annual ACM symp
โœ Andreev, Konstantin; Rรคcke, Harald ๐Ÿ“‚ Article ๐Ÿ“… 2004 ๐Ÿ› ACM Press ๐ŸŒ English โš– 127 KB

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

[ACM Press the fourteenth annual ACM sym
โœ Alstrup, Stephen; Gavoille, Cyril; Kaplan, Haim; Rauhe, Theis ๐Ÿ“‚ Article ๐Ÿ“… 2002 ๐Ÿ› ACM Press ๐ŸŒ English โš– 183 KB

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