Multilevel heuristics for task assignment in distributed systems
Dağıtık sistemlerde çok düzeyli görev atama algoritmaları
- Tez No: 79320
- Danışmanlar: DOÇ. DR. CEVDET AYKANAT
- Tez Türü: Yüksek Lisans
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Task assignment, distributed systems, task clustering, multilevel task assignment methods, Kernighan-Lin Heuristic
- Yıl: 1998
- Dil: İngilizce
- Üniversite: İhsan Doğramacı Bilkent Üniversitesi
- Enstitü: Mühendislik ve Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar Bilimleri ve Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 68
Özet
Görev atama probleminin amacı bir dağıtık sistemdeki görevlerin işlemcilere yürütme ve iletişim giderlerinin toplamını en küçük yapacak biçimde atamaktır. Bu çalışmada, görevlerin iletişim zamanlarının yanı sıra yürütme zamanları arasındaki farkı da dikkate alan yeni bir topaklama yöntemi önerilmiştir. Bu topaklama yöntemi uygun atama yöntemleri ile birlikte her türlü görev atama problemine en iyiye yakın çözümler bulabilecek olan iki-evreli atama algo ritmaları oluşturmak için kullanılmıştır. Bunlara ek olarak, çizge/hiperçizge parçalamada kullanılan çok düzeyli çizenek görev atama problemine uyarlan mıştır. Çok düzeyli atama algoritmaları görevleri birleştirerek asıl problemi küçültür, en küçük problem için bir başlangıç ataması bulur, sonra bu ata mayı her düzeyde iyileştirerek asıl probleme doğru yansıtır. Bu çalışmada çok düzeyli atama algoritmaları için bir çok topaklama çizeneği önerilmiştir. Bütün önerilen algoritmalar iki güncel algoritma ile karşılaştırılmış ve başarımları bir deneysel çalışma ile değerlendirilmiştir. Deney sonuçları göstermiştir ki önerilen algoritmalar varolan iki algoritmadan da daha iyi çalışmaktadır. Anahtar kelimeler. Görev atama, dağıtık sistemler, görev topaklama, çok düzeyli görev atama yöntemleri, Kerninghan-Lin algoritması
Özet (Çeviri)
Task assignment problem deals with assigning tasks to processors in order to minimize the sum of execution and communication costs in a distributed sys tem. In this work, we propose a novel task clustering scheme which considers the differences between the execution times of tasks to be clustered as well as the communication costs between them. We use this clustering approach with proper assignment schemes to implement two-phase assignment algorithms which can be used to find suboptimal solutions to any task assignment prob lem. In addition, we adapt the multilevel scheme used in graph/hypergraph partitioning to the task assignment. Multilevel assignment algorithms reduce the size of the original problem by collapsing tasks, find an initial assignment on the smaller problem, and then projects it towards the original problem by successively refining the assignment at each level. We propose several clus tering schemes for multilevel assignment algorithms. The performance of all proposed algorithms are evaluated through an experimental study where the as signment qualities are compared with two up-to-date heuristics. Experimental results show that our algorithms substantially outperform both of the existing heuristics.
Benzer Tezler
- Independent task assignment for heterogeneous systems
Heterojen sistemler için bağımsız iş atama
ERTUĞRUL KARTAL TABAK
Doktora
İngilizce
2013
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİhsan Doğramacı Bilkent ÜniversitesiBilgisayar Mühendisliği Bölümü
PROF. DR. CEVDET AYKANAT
- The Implications of the use of Building Environmental Assessment Tools within the Building Practice in Turkey
Türkiye'de Yeşil Bina Sertifika Sistemlerinin Bina Tasarım ve Yapım Süreçlerine Etkisi
IŞIL RUHİ SİPAHİOĞLU
Doktora
İngilizce
2013
MimarlıkPolitecnico di MilanoYapı Bilgisi Ana Bilim Dalı
PROF. DR. NICCOLO ASTE
YRD. DOÇ. DR. LAVINIA CHIARA TABLIABUE
- Heuristic procedures for the lot sizing problem with assembly structures
Başlık çevirisi yok
ORHAN İRFANOĞLU
Yüksek Lisans
İngilizce
1990
Endüstri ve Endüstri MühendisliğiOrta Doğu Teknik ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DOÇ. DR. ÖMER KIRCA
- Design and analysis of lot sizing techniques for an mrp systems
Malzeme ihtiyaç planlama sisteminde kafile büyüklerini belirleyen tekniklerin analizi ve tasarımı
SEDAT ZENCİRCİ
Yüksek Lisans
İngilizce
1994
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolOrta Doğu Teknik ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DOÇ. DR. ADNAN YAZICI
- Algorithms for multi-level capacitated lot-sizing problem with set-up times
Başlık çevirisi yok
E.İFFET ŞAHİN
Yüksek Lisans
İngilizce
1989
Endüstri ve Endüstri MühendisliğiOrta Doğu Teknik ÜniversitesiDOÇ. DR. ÖMER KIRCA