Harmonogramowanie zadań obliczeniowych w wieloprocesorowym systemie równoległym

• Autorzy: Wala K.

Warianty tytułu

EN

Scheduling of the computational tasks in the parallel multiprocessor system

• Języki publikacji: PL

Abstrakty

PL

W pracy przedstawiono model sieciowy NP-trudnego zagadnienia harmonogramowania zadań obliczeniowych w systemie wieloprocesorowym, przy czym założono, że procesory mogą być niejednorodne. Zbiór zadań i warunki poprzedzania w zbiorze zadań są opisane za pomocą ważonego acyklicznego digrafu. Następnie zaproponowano uogólnienie algorytmów konstrukcyjnych Sakara'y oraz Kima i Browne'a, właśnie, dla procesorów niejednorodnych. Przedstawiono wyniki obliczeń dla jednego przykładu, ilustrując efektywność zaproponowanych algorytmów konstrukcyjnych.

EN

The network model of NP-hard scheduling problem of the computational tasks in multiprocessor system is given where the processors can be heterogeneous. The task set and precedence relation in the task set are described by use of the weighted acyclic digraph. Further, a generalization of the Sakara as well as Kim and Browne constructive algorithms just for the heterogeneous processors is given. At last, the computational results, to illustrate the efficiency of the proposed algorithms, for one example are presented.

Słowa kluczowe

EN

scheduling; parallel multiprocessor system; parallel system; computational tasks

• Wydawca: Wydawnictwa AGH
• Czasopismo: Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie
• Rocznik: 2003
• Tom: T. 7, z. 1-2
• Strony: 301--308
• Opis fizyczny: Bibliogr. 7 poz., rys., wykr., tab.

Twórcy

autor

Wala K.

• Katedra Automatyki, Akademia Górniczo-Hutnicza w Krakowie

Bibliografia

• [1] Banul A.: Komputerowy program do harmonogramowania procesów obliczeniowych w systemach równoległych. Bielko-Biała, Wyższa Szkoła Informatyki i Zarządzania 2002 (dyplomowa praca inżynierska, promotor K. Wala)
• [2] Gerasoulis A., Yang T.: A comparison of clustering DAGs on multiprocessors. New Brunswick, Department of Computer Science, Rutgers University 1996
• [3] Homel T, Wala K.: Metaheurystyka tabu w optymalizacji wielorzędowego rozmieszczenia maszyn. Gliwice, ZN Politechniki Śląskiej, Automatyka, z. 139, 2002, 85-96
• [4] Kim S J., Browne J.C.: A general approach to mapping of parallel computation upon multiprocessor architectures. International Conference on Parallel Processing, vol. 3, 1988, 1-8
• [5] Sakara V.: Partitioning and scheduling parallel programs for executing on multiprocessors. The MIT Press 1989
• [6] Wala K., Werewka J.: Allocation of computational Processes in a Multiprocessor system. Archiwum Automatyki i Telemechaniki, z. 1-2, t. 34, 1989, 197-215
• [7] Yu-Kwong Kwok, Ishfaq Ahmad: Static scheduling algorithms for allocating directed tasks graphs to multiprocessors. AMC Computing Surveys, vol. 31, No. 4, 1999