Optimal task allocation in real-time distributed systems
Başlık çevirisi mevcut değil.
- Tez No: 15745
- Danışmanlar: DOÇ.DR. OĞUZ TOSUN
- Tez Türü: Yüksek Lisans
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Dağıtık sistemler, Gerçek zamanlı sistemler, Distributed systems, Real time systems
- Yıl: 1991
- Dil: İngilizce
- Üniversite: Boğaziçi Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Belirtilmemiş.
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: Belirtilmemiş.
Özet
Ö21T Dağıtımlı (distributed) sistemlerin yaygın kullanımını önleyen ciddi sorunlardan birisi doyum etkisi nedeniyle iş çıkarma kapasitesindeki azalmadır. Görev dağıtımı, dağılımlı sistemlerde performansı arttırma konusundaki seçeneklerden birisidir, Bu tezde, gerçek zamanlı sistemlerde görev yanıt suresinin optimizasyonu amacıyla tasarlanmış bir statik, optimal dağıtım algoritması sunulmaktadır. Görev modülleri arasındaki haberleşme hacimlerinin kestirimi için bir model geliştirilerek, dağıtımın etkinliğini değerlendirmek amacıyla bir maliyet fonksiyonu önerilmektedir. Önerilen fonksiyon, görevlerin birden fazla defa çağırılmalarından doğan işlemci kuyruk gecikmelerini hesaba katmakta ve alıcı modüldeki haberleşme maliyetini olduğundan yüksek alarak, modüller arasındaki öncelik ilişkilerinin ortaya çıkardığı etkiyi kapatmaya çalışmaktadır. İki optimizasyon ölçütü önerilmiştir. Birincil olanı, yani minimaks ölçütü, en yüklü işlemcinin yanıt süresini en aza indirme üzerine kurulmuştur. Minimaks ölçütünün birden fazla çözüm verdiği durumlarda sistemin toplam yükünü en aza indirmeye dayanan ikincil ölçüt devreye sokulur. Daha sonra da, önerilen maliyet fonksiyonu ve optimizasyon ölçü tüyle, görev dağıtım problemi, Shen ve Tsai' nin [1] yaklaşımlarına dayanan durum-uzay arama problemi olarak yeniden formole edilir. Modüllerin işlemcilere verilmesi işlemi de, aramanın hızlandırılması için uygun buluşsal (heuristic) bilgilerin önerilmesinden sonra, yapay zeka uygulamalarında kullanılan A* algoritması kullanılarak çözülecek olan zayıf- homomorphic grafik eşleme problemine dönüştürülür. Modül verme işleminin sırasının üretilen grafik elemanlarının sayısı üzerindeki etkisi de formel olarak incelenmiş ve arama etkinliğini artıran, yaklaşık olarak optimal bir modül verme sırasını belirleme stratejisi geliştirilmiştir. Modüllerin çalışır hale gelmeleri için geçmesi gereken sürenin ozyenilemeyle (recursion) belirlendiği, öncelik ilişkilerinden doğan etkilerin açık olarak hesaba katıldığı ikinci bir maliyet fonksiyonu önerilmiş ve bu da benzeri bir yaklaşımla çözülmüştür.
Özet (Çeviri)
IV ABSTRACT Â serious problem that prevents widespread use of distributed systems is the degradation in throughput caused by the saturation effect. Task allocation is one of the alternatives for improving performance in distributed systems. * This thesis presents a static, optimal allocation algorithm designed for task response time optimization in real-time systems. A model for estimating the communication volumes among task modules is developed, and a cost function is proposed for evaluating the effectiveness of the allocation. The proposed cost function considers processor queueing delays resulting from multiple invocations of tasks, and tends to compensate for the effects of precedence relations among modules by overestimating the ^communication costs at the receiver module. Two optimization criteria are also proposed. Tha primary one, called the minimax criterion, is based on minimizing the turnaround time of the bottleneck processor. In cases where the minimax criterion yields multiple solutions, a second criterion based on minimizing the total load on the system is employed. With the proposed cost function and optimization criteria, the task allocation problem is then formulated as a state-space search problem based on the approach proposed by Shen and Tsai [1], Module assignment to processors is transformed into a weakiy-homomorphic graph matching problem, which is then solved by the A* Algorithm used in artificial intelligence applications after proper heuristic information for speeding up the search is suggested. The effect of module allocation order on the number of generated nodes is also formally investigated, and a near-optimal strategy is developed for determining an allocation order which improves search efficiency. A second cost function which explicitly considers the effect of precedence relations by recursively computing release times of modules is also proposed, and solved using a similar approach.
Benzer Tezler
- Esnek üretim sistemleri için bir etkin üretim denetleme modeli
An Effective supervisory control model for flexible manufacturing systems
BAHAR KORKUSUZ
Doktora
Türkçe
1989
Endüstri ve Endüstri Mühendisliğiİstanbul Teknik ÜniversitesiPROF.DR. GÖNÜL YENERSOY
- Düşük bir hızlarında konuşma kodlama ve uygulamaları
Low bit rate speech coding and applications
TARIK AŞKIN
Doktora
Türkçe
1999
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiPROF.DR. GÜNSEL DURUSOY
- Seri iş akışlı çizelgeleme için bulanık dal-sınır algoritması
Başlık çevirisi yok
İZZETTİN TEMİZ
Yüksek Lisans
Türkçe
1998
Endüstri ve Endüstri MühendisliğiGazi ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF. DR. YALÇIN EROL
- Proje yönetiminde kantitatif yöntemlerin uygulanması
The application of the quantitative methods in project management
ZİYA ULUKAN
- Ulaştırma sistemlerinin bütünleşik analizi
Integrated analysis of transportation systems
TEVFİK BAŞAL
Yüksek Lisans
Türkçe
1998
Ulaşımİstanbul Teknik Üniversitesiİnşaat Mühendisliği Ana Bilim Dalı
PROF. DR. GÜNGÖR EVREN