Kolejność ma znaczenie

Z artykułu Wojciecha Śmietanki wypływa ważny morał: przystosowanie algorytmu do działania na maszynie równoległej wymaga często zupełnie innego spojrzenia na dany problem. Okazuje się jednak, że nawet w przypadku architektury jednoprocesorowej optymalizacja algorytmu może wymagać od nas całkiem pomysłowych przeróbek. W tym artykule podamy dwa przykłady, w których kluczową okaże się kolejność, w jakiej wykonujemy operacje.

Za pierwszy przykład niech posłuży wspomniany już algorytm mnożenia macierzy. Można go zapisać, na przykład, tak:

display-math

Z uwagi na przemienność dodawania nie ma znaczenia, w jakiej kolejności wykonamy powyższe pętle. Ważne jest tylko to, aby ostatni wiersz został wykonany dla wszystkich trójek $\text{[math]}$ Okazuje się, że to, iż pętle występują w kolejności $\text{[math]}$ (zamiast, wydawać by się mogło, bardziej naturalnej kolejności $\text{[math]}$ ), ma kluczowe znaczenie. Na moim komputerze ten program dla $\text{[math]}$ wykonuje się 2,1 s, natomiast program „naturalny” aż 8,2 s – prawie cztery razy wolniej! Wiąże się to z tym, że w powyższym programie wszystkie macierze są przeglądane wierszami, co dobrze wpływa na wykorzystanie pamięci podręcznej procesora.

Często, aby umożliwić wykonywanie operacji w lepszej kolejności, konieczne jest głębsze przebudowanie algorytmu. Za przykład posłuży nam tu wyznaczanie liczb pierwszych za pomocą sita Eratostenesa.

display-math

Zauważmy, że dla każdej nowo znalezionej liczby pierwszej $\text{[math]}$ przeglądamy prawie całą tablicę $\text{[math]}$ by wykreślić wielokrotności $\text{[math]}$ To powoduje, że nieefektywnie korzystamy z pamięci podręcznej procesora. Spróbujmy zatem tak przepisać powyższy algorytm, by zwiększyć lokalność odwołań do pamięci.

Zauważmy, że liczba pierwsza $\text{[math]}$ zostanie użyta do wykreślania tylko, gdy $\text{[math]}$ Na początek wykonajmy więc powyższy kod dla początkowego kawałka tablicy $\text{[math]}$ przy okazji zapamiętując w tablicy $\text{[math]}$ napotkane liczby pierwsze, a w tablicy $\text{[math]}$ ich najmniejsze wielokrotności większe niż $\text{[math]}$ Resztę tablicy podzielmy na bloki długości $\text{[math]}$ i przeglądajmy te bloki kolejno, za każdym razem wykreślając (dla wszystkich $\text{[math]}$ ) znajdujące się w tym bloku wielokrotności liczby $\text{[math]}$ odpowiednio uaktualniając w $\text{[math]}$ najmniejszą niewykorzystaną jeszcze wielokrotność $\text{[math]}$ Poniższy pseudokod realizuje ten nowy algorytm:

display-math

Jeśli przyjmiemy $\text{[math]}$ to pierwszy kod działa na moim komputerze 4,2 s. Pamięć podręczna w moim procesorze ma rozmiar 32 kB, zatem możemy przyjąć $\text{[math]}$ Wtedy drugi program działa w czasie 1,3 s, co daje ponadtrzykrotne przyspieszenie, mimo iż liczba operacji wykonywanych w pseudokodzie wzrosła!

Można, oczywiście, dalej optymalizować nasz algorytm, np. wyrzucić z tablicy $\text{[math]}$ liczby parzyste i użyć tablicy bitowej. Można również przyjąć jako rozmiar bloku wielokrotność iloczynu małych liczb pierwszych i zauważyć, że wtedy wielokrotności tych liczb w każdym bloku są położone tak samo.