Przyspieszenie (obliczenia równoległe)

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

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

Definicja[edytuj]

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

gdzie:

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 Sp = 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 T1 jest czasem wykonania najlepszego algorytmu sekwencyjnego, a relative speedup (przyspieszeniem względnym) kiedy T1 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:

.

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 maja parametr wydajności taki jak przy czym dąży on do zera przy wzroście liczby zastosowanych procesorów.

Przyspieszenie superliniowe (Super linear speedup)[edytuj]

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 ilość 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 ilość 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ż[edytuj]