Porównanie algorytmów konstrukcyjnych statycznego harmonogramowania dla wybranych architektur wieloprocesorowych

• Autorzy: Banul, A. , Wala, K.

Warianty tytułu

EN

Comparison of static scheduling algorithms for selected multiprocessor architectures

• Języki publikacji: PL

Abstrakty

PL

Przedstawiono model formalny statycznego problemu harmonogramowania zależnych zadań obliczeniowych w systemach wieloprocesorowych. Opisano sześć algorytmów konstrukcyjnych harmonogramowania, a następnie, biorąc pod uwagę szereg ważnych kryteriów oceny jakości harmonogramów, zaprezentowano wyniki badań komputerowych ich efektywności dla wybranych homogenicznych architektur wieloprocesorowych.

EN

A formal model of static scheduling problem of dependent computational tasks in homogeneous multiprocessor system is presented. The dependent computational tasks are modeled by acyclic weighted task precedence degraph G = (V,E), where K is a task set, E describes the precede relation in set V and functions p: V —> R+, a: E —> R+ define the mean task execution and message transmission time, respectively. We give a description of six constructive scheduling algorithms for schedule calculation before application software execution by means of the algorithms of APN (Arbitrary Processors Network) class. Taking into account a number of important efficiency criterions, we picture the results of computational investigations of performance comparison of the scheduling algorithms for selected multiprocessor architectures. The computational results are discussed at the end of the paper.

Słowa kluczowe

PL

harmonogramowanie statyczne; homogeniczna architektura wieloprocesorowa

EN

static scheduling; homogeneous multiprocessor architecture

• Czasopismo: Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie
• Rocznik: 2009
• Tom: T. 13, z. 2
• Strony: 181-188
• Opis fizyczny: Bibliogr. 6 poz., rys., wykr.

Twórcy

autor

Banul, A.

• Wyższa Szkoła Biznesu w Dąbrowie Górniczej

autor

Wala, K.

• Wyższa Szkoła Biznesu w Dąbrowie Górniczej

Bibliografia

• [1] Banul A., Wala K., Harmonogramowanie statyczne zadań obliczeniowych w homogenicznym systemie wieloprocesorowym, Zeszyty Naukowe Politechniki Śląskiej, seria Automatyka 2008.
• [2] Banul A., Komputerowy system do badania efektywności przybliżonych algorytmów harmonogramowania zadań obliczeniowych w wieloprocesorowym systemie czasu rzeczywistego. Dyplomowa praca magisterska, promotor: K. Wala, Akademia Górniczo-Hutnicza, Kraków 2007.
• [3] Banul A., Wala K., Harmonogramowanie zadań obliczeniowych w wieloprocesorowym systemie czasu rzeczywistego. Automatyka (półrocznik AGH), t. 7, z. 3, 2003, 627-635.
• [4] Kim S.J., Brown J.C., A general approach to mapping of parallel computation upon multiprocessor architectures. International Conference on Parallel Processing, vol. 3, 1988, 1-8.
• [5] Sarkara V., Partitioning and scheduling parallel programs for executing on multiprocessors. The MIT Press, Cambridge, MA, 1989.
• [6] Kwok Y.K., Ahmad I., Static scheduling algorithms for allocating directed tasks graphs to multiprocessors. AMC Computing Surveys, vol. 31, No. 4, 1999, 406-71.