Optimal schedules for cycle-stealing in a network of workstations with a bag-of-tasks workload
| Autor: | A.L. Rosenberg |
|---|---|
| Rok vydání: | 2002 |
| Předmět: |
Schedule
Mathematical optimization Workstation Computer science Computation Distributed computing Embarrassingly parallel Cycle stealing Processor scheduling Workload law.invention Scheduling (computing) Computational Theory and Mathematics Hardware and Architecture law Signal Processing Probability distribution |
| Zdroj: | IEEE Transactions on Parallel and Distributed Systems. 13:179-191 |
| ISSN: | 1045-9219 |
| DOI: | 10.1109/71.983945 |
| Popis: | We refine the model underlying our prior work on scheduling bag-of-tasks ("embarrassingly parallel") workloads via cycle-stealing in networks of workstations (S.N. Bhatt et al., 1997; A.L. Rosenberg, 1999), obtaining a model wherein the scheduling guidelines of Rosenberg produce optimal schedules for every such cycle-stealing opportunity. We thereby render prescriptive the descriptive model of those sources. Although computing optimal schedules usually requires the use of general function-optimizing methods, we show how to compute optimal schedules efficiently for the broad class of opportunities whose durations come from a concave probability distribution. Even when no such efficient computation of an optimal schedule is available, our refined model often suggests a natural notion of approximately optimal schedule, which may be efficiently computable. We illustrate such efficient approximability via the important class of cycle-stealing opportunities whose durations come from a heavy-tailed distribution. Such opportunities do not admit any optimal schedule, nor even a natural notion of approximately optimal schedule, within the model of Bhatt and Rosenberg. Within our refined model, though, we derive computationally simple schedules for heavy-tailed opportunities, which can be "tuned" to accomplish an expected amount of work that is arbitrarily close to optimal. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|