Call Number | SEM-212 |
Collection Type | Indeks Artikel prosiding/Sem |
Title | Job Scheduling in Rings |
Author | Perry Fizzano, David Karger, Clifford Stein, Joel Wein; |
Publisher | 6th Annual ACM Symposium on Parallel Algorithms and Architecture |
Subject | |
Location |
Nomor Panggil | ID Koleksi | Status |
---|---|---|
SEM-212 | TERSEDIA |
We give distributed approximation algorithms for job scheduling in a ring architecture. In contrast to almost all other parallel scheduling models, the model we consider captures the influence of the underlying communications network by spec- ifying that task migration from one processor to another takes time proportional to the distance between those two processors in the network. As a result, our algorithms must balance both com- putational load and communication time. The algorithms are simple, require no global con- trol, and work in a variety of settings. All come with small constant-factor approximation guar- antees; the basic algorithm yields schedules of length at most 4.22 times optimal. We also give a lower bound on the performance of any dis- tributed algorithm and the results of simulation experiments, which give better results than our worst-case analysis.