Okienkowo-stosowy algorytm alokacji zadań dla multikomputerów zorientowanych siatkowo

Abstract

Prezentowane zagadnienie dotyczy problemu optymalizacji algorytmu przydzielania zadań dla systemów zorientowanych siatkowo. Porównano dwa algorytmy: FS (przegląd zupełny) oraz stworzony przez nas WSBA (okienkowo-stosowy algorytm alokacji zadań). Algorytm WSBA został celowo zaprojektowany tak by statyczny efekt jego działania był identyczny jak w przypadku zastosowania FS, przy jednoczesnym znacznym skróceniu czasu wykonania, zmniejszeniu złożoności i uniezależnieniu od kształtu siatki.
Autorzy: Michał KUBIAK, Tomasz LARKOWSKI, Leszek KOSZAŁKA

1. WPROWADZENIE

Systemy wieloprocesorowe bazujące na siatkowym układzie jednostek wykonawczych znajdują swoje zastosowanie wszędzie tam gdzie jest konieczna duża moc obliczeniowa. Efektywny przydział zadań do siatki staje się sprawą kluczową w momencie, gdy chcemy obniżyć koszty konstrukcji systemu przy zachowaniu tej samej mocy przerobowej. Efektywniejszy algorytm pozwala na pełniejsze wykorzystanie dostępnych procesorów, przez co ten sam ciąg zadań może zostać przetworzony na mniejszej liczbie jednostek wykonawczych.

Znaczenie samego zagadnienie ostatnimi czasy wzrosło, ponieważ pojawiło się zapotrzebowanie na efektywny dostęp do dzielonej pamięci w systemach wieloprocesorowych. Pamięć taka charakteryzuje się strukturą regularną, modularną, skalowalnością, względną łatwością konstrukcji, co powoduje, że jest ona doskonałym adresatem algorytmów siatkowych. Dlatego też architektura zorientowana siatkowo jest zagadnieniem mającym duże perspektywy, szczególnie dla przyszłych generacji superkomputerów. Już teraz powstało kilka prototypów oraz systemów komercyjnych skonstruowanych na bazie topologii dwu- i trójwymiarowej siatki. Najbardziej znane to: Intel Touchstone Delta [1], Intel Paragon XP/S [2], Tera Computer System [3], Cray T-3D system [4], Fujitsu AP-100 [5], Parsytec GC [6], PASM [7], i Sanyo Edden/Cyberflow system [5]. W literaturze można również znaleźć wiele propozycji algorytmów alokujących zadania do tego rodzaju siatek: [8],[9],[10],[11],[12],[13] i [14].

W naszych badaniach skoncentrowaliśmy się na opracowaniu algorytmu, który w sposób efektywny zarządza przydziałem zadań do niezajętych jednostek wykonawczych, przyjmując domyślną obsługę nadchodzących zdarzeń w systemie FCFS (First Come First Serve ).

Celem naszych eksperymentów było zbadanie efektywności działania nowego, stworzonego przez nas algorytmu WSBA (Window-Stack Based Allocation Algorithm), względem pewnego punktu odniesienia, za który przyjęliśmy dobrze znany algorytm FS (Full Search).