Czy algorytmy są oceniane na podstawie wielkiej notacji, na którą ma wpływ paralelizm? - algorytm, przetwarzanie równoległe, big-o

Właśnie przeczytałem artykuł o przełomiemnożenie macierzy; algorytm O (n ^ 2,373). Ale myślę, że mnożenie macierzy może być równoległe. Jeśli więc kiedykolwiek zaczniemy produkować procesory o tysięcznych rdzeniach, czy stanie się to nieistotne? Jak zmieniłyby się rzeczy?

Odpowiedzi:

Jeśli obliczenia kwantowe pojawią się pewnego dnia w praktyce, to tak, złożoność algorytmów ulegnie zmianie.

W międzyczasie, równolegle do algorytmu, zustalona liczba procesorów, justs dzieli swój czas pracy proporcjonalnie (i to, w najlepszym przypadku, gdy nie ma zależności między zadaniami wykonywanymi na każdym procesorze). Oznacza to, że dzielenie środowiska wykonawczego przez stałą, a więc złożoność pozostaje taka sama.

Równoległe wykonanie nie zmienia podstawzłożoność konkretnego algorytmu - w najlepszym razie „poświęcasz czas na określony rozmiar i dzieli przez liczbę rdzeni. Może to skrócić czas dla danego rozmiaru o stały współczynnik, ale nie ma wpływu na złożoność algorytmu.

Jednocześnie równoległe wykonanie czasami się zmienia który algorytm (y), których chcesz użyć do konkretnych zadań. Niektóre algorytmy, które działają dobrze w kodzie seryjnym, po prostu nie dzielą się bardzo dobrze na zadania równoległe złożoność może być szybszy w przypadku problemów praktycznych, ponieważ działają równolegle lepiej.

Dla bardzo dużej liczby rdzenizłożoność samego obliczenia może stać się drugorzędna w stosunku do zwykłego uzyskania niezbędnych danych do / ze wszystkich rdzeni w celu wykonania obliczeń. większość obliczeń big-O nie uwzględnia tych efektów przy obliczaniu szeregowym, ale może stać się dość ważna dla obliczeń równoległych, zwłaszcza dla niektórych modeli maszyn równoległych, które nie zapewniają jednolitego dostępu do wszystkich węzłów.

Przez Prawo Amdahla, dla tego samego rozmiaru problemu, równoległość dojdzie do punktumalejący powrót wraz ze wzrostem liczby rdzeni (teoretycznie). W rzeczywistości, z pewnego stopnia równoległości, obciążenie związane z równoległością faktycznie zmniejszy wydajność programu.

Jednak przez Prawo Gustafsona, wzrost liczby rdzeni faktycznie pomagawraz ze wzrostem rozmiaru problemu. Taka jest motywacja do obliczeń klastrowych. Ponieważ mamy większą moc obliczeniową, możemy rozwiązać problem na większą skalę lub większą precyzję dzięki równoległości.

Algorytmy, których się uczymy, mogą być lub nie byćparalelizowalny. Czasami trzeba użyć osobnego algorytmu, aby wydajnie wykonywać to samo zadanie równolegle. Tak czy inaczej, notacja Big-O musi zostać ponownie przeanalizowana, aby przypadek równoległy uwzględnił wpływ równoległości na złożoność czasową algorytmu.