Szeregowanie zadań periodycznych w heterogenicznych systemach wieloprocesorowych

Dyskusja wyników

W wyniku realizacji algorytmu ewolucyjnego otrzymano następujące wartości stopni wykorzystania poszczególnych procesorów wchodzących w skład badanego sytemu heterogenicznego:

1. procesor nr 1 – 0,673;
2. procesor nr 2 – 0,654;
3. procesor nr 3 – 0,691;
4. procesor nr 4 – 0,678;
5. procesor nr 5 – 0,674.

Rys. 1. Ilustracja sposobu dochodzenia do stabilnego rozwiązania w przypadku procesora nr 1:

Rys. 2. Ilustracja sposobu dochodzenia do stabilnego rozwiązania w przypadku procesora nr 2:

Rys. 3. Ilustracja sposobu dochodzenia do stabilnego rozwiązania w przypadku procesora nr 3:

Rys. 4. Ilustracja sposobu dochodzenia do stabilnego rozwiązania w przypadku procesora nr 4:

Rys. 5. Ilustracja sposobu dochodzenia do stabilnego rozwiązania w przypadku procesora nr 5:

Jak widać, w przypadku każdego z rozważanych procesorów spełniony jest warunek wystarczający na szeregowalność przydzielonego do niego podzbioru zadań, zadany nierównością (2), ponieważ stopień wykorzystania tych procesorów nie przekracza wartości 0,693. Ponadto wartym zwrócenia uwagi jest fakt w miarę równomiernego obciążenia wszystkich procesorów, ponieważ ich stopnie wykorzystania mają bardzo zbliżone wartości.

Dodatkowo za pomocą wykresów przedstawionych na rys. 1–5 zilustrowano sposób dochodzenia algorytmu ewolucyjnego do stabilnych rozwiązań końcowych. Jak wynika z wykresów zamieszczonych na rys. 1–5, stabilne rozwiązania uzyskiwane są po upływie już kilkudziesięciu pokoleń algorytmu ewolucyjnego, w związku z czym jego zbieżność jest bardzo szybka.

Ponadto analizując wykresy zamieszczone na rys. 1–5, wyróżnić można dwa odmienne sposoby dochodzenia algorytmu ewolucyjnego do stabilnych rozwiązań. W przypadku pierwszego z nich, który charakterystyczny jest dla procesorów nr 1 i 4, stopień wykorzystania procesora zmienia się w sposób monotoniczny, dochodząc asymptotycznie do wartości końcowej. W przypadku procesora nr 1 jego stopień wykorzystania narasta od wartości początkowej, równej 0,518, do wartości końcowej, równej 0,673. Z kolei w przypadku procesora nr 4 jego stopień wykorzystania maleje, począwszy od wartości początkowej, równej 0,932, do wartości końcowej, równej 0,678. Natomiast w przypadku wykresów odnoszących się do procesorów nr 2, 3 i 5 zaobserwować można charakterystyczne oscylacje, podczas których wartość stopnia wykorzystania tych procesorów gwałtownie wzrasta w początkowej fazie realizacji algorytmu ewolucyjnego, by następnie asymptotycznie zmaleć do stabilnej wartości końcowej. 

Reasumując zawarte w artykule rozważania, należy stwierdzić, że technika obliczeniowa oparta na zastosowaniu algorytmów ewolucyjnych może zostać z powodzeniem użyta w celu realizacji zagadnienia optymalizacji rozdziału zadań periodycznych w heterogenicznych systemach wieloprocesorowych. W rozważanym wypadku zastosowanie algorytmu ewolucyjnego prowadzi do odnalezienia takich schematów alokacji zadań periodycznych, w przypadku których dla każdego z procesorów spełniony jest warunek wystarczający na szeregowalność przydzielonego do niego podzbioru zadań. Dodatkowo algorytm ewolucyjny gwarantuje taki przydział zadań, który odznacza się zrównoważeniem stopnia obciążenia wszystkich procesorów systemu heterogenicznego.

Literatura

[1] Shin K. G., Ramanathan P.: 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.: A hypercube-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.