Library Automation and Digital Archive
LONTAR
Fakultas Ilmu Komputer
Universitas Indonesia

Pencarian Sederhana

Find Similar Add to Favorite

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
Lokasi : Perpustakaan Fakultas Ilmu Komputer
Nomor Panggil ID Koleksi Status
SEM-212 TERSEDIA
Tidak ada review pada koleksi ini: 55458
ABSTRACT

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.