Zastosowanie prawa Amdahla

Prawo Amdahla mówi o tym, jak bardzo można przyspieszyć wykonywanie procedury obliczeniowej dzięki zastosowaniu obliczeń równoległych, na przykład na klastrze albo dzięki wykorzystaniu procesora wielordzeniowego.

Najprościej jest wyjaśnić sprawę na przykładzie. Wyobraźmy sobie, że mamy do wykonania zadanie, które w sumie wymaga 100 godzin pracy pojedynczego procesora. Z tych 100 godzin 5 nie może zostać zrównoleglonych – to obliczenia złożone z ogromnej liczby kroków o takim charakterze, że trzeba je wykonywać po kolei i że rozpocząć kolejny krok można tylko po zakończeniu wszystkich poprzednich. Pozostałe 95 godzin to obliczenia potencjalnie nadające się do rozdzielenia na wiele procesorów i wykonywania jednocześnie.

Prawo Amdahla orzeka, że stosując nawet dowolnie zaawansowane techniki obliczeń równoległych, klastry złożone z tysięcy procesorów, nie wiem jak szybkie sieci przesyłu danych,  nie osiągniemy więcej niż 20-krotne przyspieszenie obliczenia naszego zadania. (Zaraz mi się przypomniało Tuwima „Lecz choćby przyszło tysiąc atletów/ I każdy zjadłby tysiąc kotletów,/ I każdy nie wiem jak się wytężał,/ To nie udźwigną, taki to ciężar.”)

Rzecz cała opiera się na banalnej obserwacji, że tych kluczowych 5 godzin obliczeń „krok po kroku” (naukowo mówiąc, sekwencyjnych) nie da się pominąć ani przyspieszyć, więc całość będzie trwać co najmniej 5 godzin, to jest co najmniej 1/20 tych wyjściowych 100 godzin.

Nowatorskie zastosowanie prawa Amdahla znalazł Urząd Zamówień Publicznych. W swoim oficjalnym dokumencie „UDZIELANIE ZAMÓWIEŃ PUBLICZNYCH NA DOSTAWĘ ZESTAWÓW KOMPUTEROWYCH. REKOMENDACJE” z roku 2010 napisał

„zgodnie z prawem Amdahla, przyspieszenie wykonania obliczeń poprzez
ich zrównoleglenie ma swoje granice. Gdyby w przyszłości któryś z producentów procesorów stwierdził, że dalsze zwiększanie liczby rdzeni w procesorach przeznaczonych dla zwykłych użytkowników nie zwiększa wydajności zestawu, wówczas specyfikacje wskazujące wymaganą liczbę rdzeni mogą naruszać zasady wolnej konkurencji poprzez wskazywanie na produkty jednego producenta […]”

Następnie na podstawie tej argumentacji zabronił przy rozpisywaniu zamówień publicznych na dostawę komputerów wpisywania do specyfikacji liczby rdzeni i wątków obsługiwanych przez procesor kupowanej maszyny. Zderzyłem się z tym problemem zamawiając komputer ze świeżo mi przyznanego grantu.

Powołanie się na Amdahla jest wykrętem, są liczne przykłady powszechnie spotykanych zadań obliczeniowych, w których część sekwencyjna stanowi całkowicie zaniedbywaną część całości. Są to na przykład wyliczenia zapytań w relacyjnych bazach danych. W ich wypadku im więcej rdzeni i wątków tym szybciej, a ograniczenia związane z prawem Amdahla są niezauważalne przy aktualnie dostępnych na rynku procesorach (i nieprędko dadzą się zauważyć).
No ale cóż, prawo stanowione to nie matematyka, obalenie argumentacji Urzędu nie powoduje, że można zignorować jego nakazy i zakazy.

Jerzy Tyszkiewicz

Na zdjęciu – J. M. Szancer, „Lokomotywa”, Julian Tuwim, 1954 (fot. 50 Watts, formerly A Journey Round My, Flickr, CC BY 2.0)

P.S. Lektura „Rekomendacji” w ogóle jest ciekawa,  w różnych dziwnych zakazach Urzędu widać ślady technik stosowanych dawniej przez jednostki zmuszone do kupowania komputerów w trybie zamówień publicznych, które starały się jak mogły, aby kupić sprzęt sensownej jakości, a nie najtańsze składaki.