Optimal task allocation in real-time distributed systems

Abstract

Ö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.

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.