Przyspieszenie (obliczenia równoległe)

Przyspieszenie (Speedup) – miara przyrostu wydajności wykonywanego zadania, przy wykonywaniu go jako obliczenie równoległe.

Definicja

Przyspieszenie jest definiowane jako iloraz czasu wykonywania zadania w obliczeniach sekwencyjnych i równoległych, co można wyrazić wzorem:

$S_{p}={\frac {T_{1}}{T_{p}}},$

gdzie:

$p$ – liczba procesorów,

$T_{1}$ – czas wykonania algorytmu sekwencyjnego,

$T_{p}$ – czas wykonania algorytmu równoległego przy użyciu $p$ procesorów.

Przyspieszenie liniowe (Linear speedup lub ideal speedup) jest uzyskiwane, kiedy przyspieszenie jest równe liczbie procesorów w obliczeniach równoległych, co wyraża wzór $S_{p}=p.$ Jeżeli algorytm ma liniowe przyspieszenie, wówczas podwojenie liczby procesorów powoduje dwukrotne zwiększenie szybkości obliczeń. Jest to sytuacja idealna i oznacza bardzo dobrą skalowalność.

Przyspieszenie nazywane jest absolute speedup (przyspieszeniem absolutnym), jeżeli $T_{1}$ jest czasem wykonania najlepszego algorytmu sekwencyjnego, a relative speedup (przyspieszeniem względnym), kiedy $T_{1}$ jest czasem wykonania tego samego algorytmu równoległego na jednym procesorze. Przyspieszenie względne jest zazwyczaj stosowane, jeżeli typ wymaganego przyspieszenia nie został określony. Dzieje się tak, ponieważ typ ten nie wymaga implementacji algorytmu sekwencyjnego.

Wydajność (efficiency) jest miarą zdefiniowaną jako:

$E_{p}={\frac {S_{p}}{p}}={\frac {T_{1}}{pT_{p}}}.$

Jest to wartość zazwyczaj mieszcząca się między 0 i 1, przewidująca, jak dobrze wykorzystana jest moc obliczeniowa procesorów przy rozwiązywaniu problemu w porównaniu do czasu, jaki został zmarnowany na komunikację i synchronizację. Algorytmy przyspieszenia liniowego i te wykonujące się na jednym procesorze mają parametr wydajności równy 1, podczas gdy wiele algorytmów kłopotliwych w równoległej implementacji ma parametr wydajności taki jak ${\frac {1}{\log p}},$ przy czym dąży on do zera przy wzroście liczby zastosowanych procesorów.

Przyspieszenie superliniowe (Super linear speedup)

Zdarza się w programowaniu równoległym, że występuje przyspieszenie większe niż $p$ przy zastosowaniu $p$ procesorów, co nazywane jest przyspieszeniem superliniowym. Przyspieszenie superliniowe zdarza się rzadko i sprawia wiele trudności początkującym, którzy są przekonani, że teoretycznie maksymalna wartość przyspieszenia nie powinna być większa niż $p,$ czyli liczba zastosowanych procesorów.

Jednym z możliwych powodów zaistnienia przyspieszenia superliniowego jest efekt pamięci cache, który jest rezultatem odmiennej hierarchii pamięci współczesnych komputerów: w programowaniu równoległym rolę odgrywa nie tylko liczba procesorów, ale także ilość skumulowanej pamięci podręcznej (accumulated cache) z pozostałych procesorów. Przy większej ilości skumulowanej pamięci podręcznej, więcej lub nawet całość głównej części danych może zostać wczytana do pamięci podręcznej co powoduje, że czas dostępu do pamięci spada dramatycznie, co prowadzi do jeszcze większego wzrostu przyspieszenia jako dodatkowego względem aktualnego wyniku obliczeń.

Przyspieszenie superliniowe może pojawić się także w sytuacji zastosowania algorytmu z nawrotami równolegle: jeden wątek może skrócić wyczerpujące przeszukiwanie w pewnej gałęzi rozwiązań, podczas gdy inny wątek mógłby podjąć to przeszukiwanie w innych okolicznościach.

Zobacz też

• miara Karpa-Flatta
• prawo Amdahla
• prawo Brooksa
• prawo Gustafsona
• skalowalność