Szeregowanie zadań periodycznych w heterogenicznych systemach wieloprocesorowych

• Autorzy: Gajer, M.

Warianty tytułu

EN

The periodic task scheduling in heterogeneous multiprocessor systems

• Języki publikacji: PL

Abstrakty

PL

W artykule zamieszczono propozycję zastosowania techniki obliczeniowej opartej na algorytmach ewolucyjnych celem optymalizacji procesu aloka­cji zadań periodycznych w heterogenicznych systemach wieloprocesorowych. Rozważono przypadek szeregowania zbioru zadań periodycznych, wywłaszczałnych i niezależnych, które szeregowane są z wykorzystaniem algorytmu Rate Monotonic Scheduling. W przypadku rozważanych heterogenicznych systemów wieloprocesorowych każdy z procesorów odznacza się nieco innym poziomem mocy obliczeniowej. W związku z powyższym celem algorytmu ewolucyjnego było odnalezienie takich schematów przydziału zadań do poszczególnych procesorów, aby w ramach każdego z nich spełniony był warunek wystarczający na szeregowaIność przydzielonego do niego zbioru zadań z wykorzystaniem algorytmu Rate Monotonic Scheduling.

EN

In the paper we propose the implementation of a computational technique based on evolutionary algorithms for the purpose of optimizing the process of the periodic task allocation in heterogeneous multiprocessor systems. In the article we discuss the case of scheduling a set of periodic, pre-emptive and independent tasks that are scheduled with the use of the Rate Monotonic Scheduling algorithm. In the case of heterogeneous multiprocessor systems the computational power of each processor is slightly different. The aim of the evolutionary algorithm was to find such task allocation schemes for each of the processors so that the sufficient condition for the set of the scheduled tasks was fulfilled. The periodic tasks were scheduled with the use of the Rate Monotonic Scheduling algorithm.

Słowa kluczowe

PL

teoria alokacji i szeregowania zadań; systemy wieloprocesorowe; algorytmy ewolucyjne

EN

tasks allocation and scheduling theory; multiprocessor systems; evolutionary algorithms

• Czasopismo: Elektronika : konstrukcje, technologie, zastosowania
• Rocznik: 2012
• Tom: Vol. 53, nr 4
• Strony: 47-51
• Opis fizyczny: Bibliogr. 20 poz., tab., wykr.

Twórcy

autor

Gajer, M.

• AGH Akademia Górniczo-Hutnicza, Katedra Automatyki, Kraków

Bibliografia

• [1] Shin K. G., Ramanathan R: Real-time computing: A new discipline of computer science and engineering. Proceedings of the IEEE, vol. 82, 1994, ss. 6-24.
• [2] Hsueh W., Lin K. J.: Scheduling real-time systems with end-to-end timing constraints using the distributed pinwheel model. IEEE Transactions on Computers, vol. 50, 2001, ss. 51-67.
• [3] Lala J. H., Harper R. E.: Architectural principles for safety-critical real-time applications, Proceedings of the IEEE, vol. 82, 1994, ss. 25-41.
• [4] Szmuc T., Motet G.: Specyfikacja i projektowanie oprogramowania czasu rzeczywistego, Wydawnictwa CCATIE, Kraków 1998.
• [5] Suri N., Hugue M. M., Walter C. J.: Synchronization issues in realtime systems. Proceedings of the IEEE, vol. 82, 1994, ss. 41-53.
• [6] Stoyenko T., Baker P.: Real-time schedulability analyzable mechanisms in Ada9X. Proceedings of the IEEE, vol. 82, 1994, ss. 95-107.
• [7] Ramamrithan K., Stankovic J. A.: Scheduling algorithms and operating systems support for real-time systems. Proceedings of the IEEE, vol. 82, 1994, ss. 55-67.
• [8] Sha L., Rajkumar R., Sathaye S. S.: Generalized rate-monotonic scheduling theory: A framework for developing real-time systems. Proceedings of the IEEE, vol. 82, 1994, ss. 68-82.
• [9] Tannenbaum A.: Rozproszone systemy operacyjne, WNT, Warszawa, 1996.
• [10] Coulouris G., Dollimore J., Kindberg T.: Systemy rozproszone - podstawy i projektowanie, WNT, Warszawa, 1998.
• [11] Goldberg D. E.: Algorytmy genetyczne i ich zastosowania, Wydawnictwa Naukowo-Techniczne, Warszawa 1996.
• [12] Arabas J.: Wykłady z algorytmów ewolucyjnych, Wydawnictwa Naukowo-Techniczne, Warszawa 2004.
• [13] Rutkowska D.: Inteligentne systemy obliczeniowe i sztuczna inteligencja. [W] Biocybernetyka i inżynieria biomedyczna 2000, pod redakcją Macieja Nałęcza, Tom 6 - Sieci neuronowe, ss. 765-784.
• [14] Michalewicz Z.: Algorytmy genetyczne + struktury danych = programy ewolucyjne. Wydawnictwa Naukowo-Techniczne, Warszawa 2003.
• [15] Rutkowska D., Piliński M., Rutkowski L.: Sieci neuronowe, algorytmy genetyczne i systemy rozmyte. Wydawnictwo Naukowe PWN, Warszawa - Łódź 1997.
• [16] Gras R., Devaurs D., Wozniak A., Aspinall A.: An individual-based evolving predator-prey ecosystem simulation using a fuzzy cognitive map as the behavior model. Artificial Life, vol. 15, 2009, ss. 423-463.
• [17] Bullinaria J. A.: Lifetime learning as a factor in life history evolution. Artificial Life, vol. 15, 2009, ss. 389-409.
• [18] Stanley K. O., A'Ambrosio D. B., Gauci J.: Ahypercube-based encoding for evolving large-scale neural networks. Artificial Life, vol. 15, 2009, ss. 185-212.
• [19] Ampatzis C., Tuci E., Trianni V., Christensen A. L., Dorigo M.: Evolving self-assembly in autonomous homogeneous robots: Experiments with two physical robots. Artificial Life, vol. 15, 2009, ss. 465-484.
• [20] Paenke I., Kawecki T. J., Sendhoff B.: The influence of learning on evolution: A mathematical framework. Artificial Life, vol. 15, 2009, ss. 227-245.