pp_prednaska_8_navrh Flashcards Preview

PARALELPR > pp_prednaska_8_navrh > Flashcards

Flashcards in pp_prednaska_8_navrh Deck (16):
1

Stupeň súbežnosti (Concurrency)

Počet naraz vykonateľných úloh – stupeň súbežnosti
! Počet naraz vykonateľných úloh sa v priebehu programu
mení
! Maximálny stupeň súbežnosti – max. počet úloh, kt. sú
naraz vykonateľné v ľubovoľnom čase počas behu
programu
! Priemerný stupeň súbežnosti – zohľadnenie času,
priemerný počet naraz vykonateľných úloh
! Stupeň súbežnosti rastie so zmenšujúcou sa zrnitosťou

2

Procesy a mapovanie úloh na procesy

Vo všeobecnosti počet úloh je vyšší ako počet
výpočtových spracovateľských elementov – procesov
! Paralelný algoritmus musí riešiť mapovanie úloh na
procesy

Vhodné mapovanie úloh na procesy – kritické pre výkon
paralelného algoritmu
! Mapovanie je určené grafom závislosti aj grafom
interakcie
! Grafy závislosti môžu pomôcť pri rovnomernom
rozložení práce medzi procesy v každom čase
(minimálne čakanie a optimálne zaťaženie)
! Grafy interakcie môžu pomôcť pri minimalizácií interakcií
medzi procesmi (minimálna komunikácia)



Vhodné mapovanie musí minimalizovať čas paralelného
vykonania programu:
" Mapovanie nezávislých úloh na rôzne procesy
" Priradenie úloh na kritickej ceste procesom hneď ako je to možné
" Minimalizácia interakcie medzi procesmi mapovaním úloh s
hustou komunikáciou na rovnaký proces
! Často protichodné ciele, napr. všetky úlohy na jediný
proces zredukuje interakciu, ale žiadne zrýchlenie sa
nedosiahne

3

Procesy vs. procesory

Zvyčajne nie je možné priame mapovanie úloh na procesory
" Úlohy na procesy a OS mapuje procesy na procesory
" Proces – voľné pomenovanie súboru úloh a k nim prislúchajúcich
údajov

4

Pravidlo „vlastník počíta“
!

Pravidlo vlastník počíta (Owner Computes) – proces
priradený k nejakému údaju je zodpovedný za všetky
výpočty spojené s údajom.
! Dekompozícia na základe vstupných údajov – všetky
výpočty nad vstupnými údajmi sú vykonávané procesom,
ktorému prislúchajú vstupné údaje.
! Dekompozícia na základe výstupných údajov – výstup je
vypočítaný procesom, ktorému prislúchajú výstupné
údaje.

5

Metódy mapovania úloh na procesy
!

Po dekomponovaní problému na súbežné úlohy je
potrebné úlohy namapovať na procesy vykonateľné na
paralelnej platforme
! Mapovanie musí minimalizovať réžiu (overhead), hlavne
" Komunikačná réžia
" Réžia súvisiaca s nečinnosťou procesorov
! Minimalizácia réžie – často protichodné ciele
! Napr. triviálna minimalizácia komunikácie mapovaním
celého problému na jeden procesor spôsobí veľkú réžiu
súvisiacu s nečinnosťou ostatných dostupných
procesorov

6

Metódy mapovania na minimalizáciu
nečinnosti

Mapovanie musí súčasne minimalizovať nečinnosť a
zároveň zabezpečiť vyvážené zaťaženie procesorov
! Čisté vyvažovanie záťaže nemusí minimalizovať
nečinnosť.


Metódy mapovania môžu byť statické alebo dynamické:
" Statické mapovanie
" Úlohy „vopred“ mapované na procesy
" Potrebný dobrý odhad veľkosti úloh
! Problém mapovania môže byť NP úplný
" Dynamické mapovanie
" Úlohy mapované na procesy „za behu“
" Napr. z dôvodu že sú generované „za behu“ alebo ich veľkosť nie
je dopredu známa
! Ostatné faktory determinujúce výber metódy
" Veľkosť údajov asociovaných s úlohou
" Charakter problémovej domény

7

Schémy statického mapovania

Mapovanie založené na dátovej dekompozícií
! Mapovanie založené na dekomponovaní grafu
! Hybridné mapovanie

8

Blokovo cyklická dekompozícia

Variácia mapovania pri blokovo cyklickej dekompozície
môže byť použitá na odľahčenie nerovnomernosti
zaťaženia procesorov a ich lepšie využitie
! Rozdelenie poľa dát počet blokov >> počet procesorov
! Bloky sú priradené procesorom jeden po druhom (Round
Robin) tak, že každý proces obdrží niekoľko
nesusediacich blokov

9

Dátová dekompozícia založená na
rozdelení grafu

Riedke matice – bloková dekompozícia je náročná
! Násobenie riedkej matice vektorom
! Graf matice je užitočným indikátorom množstva práce
(počet uzlov) a komunikácie (stupeň vrcholov)
! Rovnomerné rozdelenie grafu medzi procesy vzhľadom
na počet uzlov, pričom sa minimalizuje počet hrán medzi
partíciami grafu

10

Mapovanie založené na dekompozícií
na úlohy

Rozdelenie daného grafu závislostí medzi úlohami na
procesy
! Určenie optimálneho mapovania pre všeobecný graf
závislostí je NP-úplný problém
! Existujú kvalitné heuristiky pre štruktúrované grafy

11

Hierarchické mapovanie

Jediné mapovanie môže byť neadekvátne pre niektoré
úlohy
! Napr. mapovanie úloh binárneho stromu (alg. „quicksort“)
na veľký počet procesorov nie je možné
! Mapovanie na základe dekompozície na úlohy na hornej
úrovni môže byť kombinované s dátovou dekompozíciou
na každej úrovni

12

Schémy dynamického mapovania

Dynamické mapovanie niekedy nazývané tiež
dynamické vyrovnávanie záťaže, nakoľko vyrovnávanie
záťaže je hlavnou motiváciou pre dynamické mapovanie
! Schémy dynamického mapovania môžu byť
centralizované alebo decentralizované

13

Centralizované dynamické mapovanie

Procesy sú označené ako riadiaci proces a podriadené
procesy („Master“ a „Slaves“)
! Ak proces nemá prácu, vyžiada si ju od riadiaceho
procesu
! S rastúcim počtom procesov komunikácia s riadiacim
procesom môže byť úzkym hrdlom
! Proces si môže „vyzdvihnúť“ skupinu úloh (chunk) –
Chunk Sheduling
! Príliš veľké skupiny – nerovnováha
! Viaceré schémy – postupné zmenšovanie veľkosti
skupiny

14

Distribuované dynamické mapovanie

Každý proces môže posielať alebo prijímať prácu od
iných procesov
! Zmierňuje to úzke hrdlo súvisiace s centralizovanou
schémou dynamického mapovania
! Štyri kritické otázky:
" Ako sú odosielateľ a prijímateľ spárované
" Kto iniciuje presun práce
" Ako veľa práce je prenesenej
" Kedy je presun odštartovaný
! Závisí od doménovej oblasti

15

Minimalizácia réžie súvisiacej s
inetarakciami medzi úlohami

Maximalizácia dátovej lokálnosti
" Znovupoužitie údajov, reštrukturalizácia výpočtu tak, aby údaje
mohli byť znovu použité v kratšom časovom okne
! Minimalizácia objemu prenášaných údajov
" S každým presunutým slovom je spojená réžia a tak je potrebné
minimalizovať objem prenášaných údajov
! Minimalizácia frekvencie interakcií
" S inicializáciou každej interakcie je spojená réžia
" Je potrebné zoskupovať viaceré interakcie do jednej
! Minimalizácia súťaženia a úzkych hrdiel
" Použitie decentralizovaných metód
" Replikácia údajov, kde je to potrebné

Prelínanie výpočtov a interakcií, zakrývanie latencie:
" Používanie neblokujúcej komunikácie
" Viacvláknovosť
" Skoré načítavanie
! Replikácia údajov alebo výpočtov
! Používanie skupinovej komunikácie (nie bod – bod
komunikácie)
! Prelínanie interakcií s inými interakciami

16

Modely paralelných algoritmov

Model algoritmu
" Spôsob štruktúrovania paralelného algoritmu výberom metódy
dekompozície a mapovania a aplikáciu vhodnej stratégie na
minimalizáciu interakci
! Dátovo paralelný model
" Úlohy sú staticky mapované na procesy a každá úloha vykonáva
podobné výpočty nad rôznymi údajmi
! Model grafu úloh
" Počnúc grafom závislosti medzi úlohami vzťahy medzi úlohami
sú využité na podporu lokálnosti a redukciu réžie spojenej s
interakciou


Model „nadriadený – podriadení“
" Jeden alebo viac procesov generujú prácu a alokujú ju na
podriadené procesy, statická alebo dynamická alokácia
! Prúdová linka / producenti - konzumenti
" Prúd údajov je prenášaný postupnosťou procesov, každý vykoná
nad údajmi danú úlohu
! Hybridné modely
" Kompozícia viacerých modelov aplikovaných hierarchicky
" Viaceré modely aplikované sekvenčne počas rôznych fáz
paralelného algoritmu