Który model obliczeń jest „najlepszy”?

41

W 1937 r. Turing opisał maszynę Turinga. Od tego czasu opisano wiele modeli obliczeń, próbując znaleźć model, który jest jak prawdziwy komputer, ale wciąż wystarczająco prosty do projektowania i analizy algorytmów.

W rezultacie mamy kilkanaście algorytmów dla np. Problemu SORT dla różnych modeli obliczeń. Niestety nie możemy nawet mieć pewności, że implementacja algorytmu z czasem wykonania O (n) w słowie RAM z dozwolonymi operacjami wektora bitowego będzie działać szybciej niż implementacja algorytmu z czasem wykonania O (n⋅logn) w słowo RAM (mówię oczywiście tylko o „dobrych” implementacjach).

Chcę więc zrozumieć, który z istniejących modeli jest „najlepszy” do projektowania algorytmów i szukam aktualnej i szczegółowej ankiety na temat modeli obliczeniowych, która daje zalety i wady modeli oraz ich bliskość z rzeczywistością.

Tatiana Starikovskaya
źródło
1
Wpis opublikowany na stronie MathOverflow ( mathoverflow.net/questions/44558/… ), chociaż tutaj przekierowano.
Dave Clarke
@Tatiana, Dobre pytanie, co rozumiesz przez „najlepszy”? Czy masz na myśli model o teoretycznym czasie działania zbliżonym do „rzeczywistego” czasu działania?
Mohammad Al-Turkistany
8
Jeśli chcesz dokładnie modelować „rzeczywiste” czasy działania, wydaje się, że może być ważne dokładne modelowanie pamięci podręcznych. W szczególności współczesne obliczenia mają wiele warstw buforowania (procesor, pamięć RAM, dysk itp.), Przy czym niektóre warstwy są wolniejsze od innych; nie jest wykluczone, że „rzeczywisty” czas działania algorytmu zależy od liczby braków pamięci podręcznej. Anegdotycznie słyszałem, że jednym z powodów, dla których metody barierowe w programowaniu liniowym działają tak dobrze pomimo ich słabych teoretycznych gwarancji, jest to, że często są one dość wydajne dla pamięci podręcznej.
mhum,
4
O ile mogę powiedzieć, jak mhum mówi, największe rozbieżności przewidywanych czasów działania w słowie model pamięci RAM i rzeczywiste czasy działania generalnie powstają z powodu pobierania danych ... nieprawidłowe zmienne znajdują się w pamięci podręcznej, a czas pobierania spowalnia ogromnie z tego powodu. Podjęto wiele prób modelowania tego za pomocą teoretycznego modelu pamięci hierarchicznej i nie sądzę, aby któraś z tych prób była bardzo udana, ponieważ modele są zbyt skomplikowane, aby łatwo z nimi pracować.
Peter Shor,
2
Jeśli masz algorytm, który Twoim zdaniem może być przydatny w praktyce, i chcesz, aby był rzeczywiście używany, najlepszą rzeczą, jaką możesz zrobić, aby go wdrożyć, lub poprosić kogoś innego o jego wdrożenie (nawet jeśli nie jest dobry wystarczająca implementacja, aby można ją było włączyć do praktycznego oprogramowania) Studium przypadku w tym, spójrz na historię algorytmu kompresji danych LZW. W rzeczywistości prawdopodobnie nie ma sensu zastanawiać się, w jaki sposób buforowanie wpływa na algorytm, chyba że ludzie są zainteresowani jego implementacją; w przeciwnym razie nikt nie zwróci uwagi na twoje wyniki.
Peter Shor,

Odpowiedzi:

30

Zawsze uważałem standardowy model Word RAM za „najlepszy” w twoim znaczeniu. Każdy, kto nauczył się programować w języku takim jak C (lub dowolne luźne odpowiedniki, takie jak Java itp.), Ma na myśli dokładnie ten model, gdy myśli o komputerze.

Oczywiście czasami potrzebujesz uogólnień w zależności od reżimów, w których pracujesz. Należy pamiętać o modelu pamięci zewnętrznej. Dotyczy to nie tylko pracy z dyskami, ale także zrozumienia (zmuszania do dbania o) pamięci podręcznej. Oczywiście potraktowanie go zbyt poważnie może również prowadzić do bezsensownych wyników, ponieważ czysty model pamięci zewnętrznej nie liczy się z obliczeniami. Kolejnym uogólnieniem Word RAM jest paralelizm, ale w tej chwili wszyscy jesteśmy trochę zdezorientowani :)

Algorytm z czasem działania z pewnością będzie działał szybciej niż jeden z czasem działania . Jest matematycznym faktem, że ten pierwszy jest szybszy dla dużych :) Rozmiar twojego problemu może po prostu nie być wystarczająco duży, aby to miało znaczenie. Ponieważ przywołujesz sortowanie, zapewniam cię, że bardzo trudno będzie pokonać sortowanie radix za pomocą algorytmu porównawczego dla rozsądnego .O ( n lg n ) n nO(n)O(nlgn)nn

Ostatnia uwaga na temat algorytmów i „rzeczywistości”: zawsze miej na uwadze to, co próbujesz osiągnąć. Pracując w algorytmach, staramy się rozwiązać najtrudniejsze problemy (np. SAT na 50 zmiennych lub sortowanie miliarda liczb). Jeśli próbujesz posortować 200 liczb lub rozwiązać SAT na 20 zmiennych, nie potrzebujesz żadnego wymyślnego algorytmu. Dlatego większość algorytmów w rzeczywistości jest dość trywialna. Nie oznacza to nic złego w badaniach algorytmicznych - akurat jesteśmy zainteresowani tym niezwykłym 1/1000 prawdziwych problemów, które są trudne ...

Mihai
źródło
Dziękuję za odpowiedź. Chcę zrozumieć, które uogólnienia warto dodać do pamięci RAM. Czy możemy opisać model, który będzie zawierał wszystkie te sztuczki, takie jak operacje na wektorach bitowych, równoległość, pamięci podręczne i nadal będą proste?
Tatiana Starikovskaya
10

Nie ma jednego całkowicie zadowalającego modelu obliczeniowego, w którym ze smutkiem analizowano by algorytmy, nawet w tym, co można by uznać za tradycyjne ustawienie. Zakłada się, że wszystkie dane są łatwo dostępne, a przestrzeń robocza jest skutecznie nieograniczona.

Maszyna Turinga z wieloma taśmami jest z pewnością dobrze teoretycznie sprecyzowana, a wiele algorytmów zaprojektowano i przeanalizowano w tym modelu na przestrzeni lat. Jednak dla niektórych nie jest wystarczająco ściśle związany z tym, jak działają prawdziwe komputery, aby naprawdę był dobrym modelem do zastosowania w XXI wieku. Z drugiej strony model słowo-RAM stał się popularny i wydaje się dokładniej uchwycić pracę współczesnych komputerów (operacje na słowach nie bitów, stały dostęp do lokalizacji pamięci w czasie). Są jednak aspekty, które nie są idealne. Na przykład nie ma jednego słowa modelu pamięci RAM. Trzeba najpierw określić, które operacje na słowach mają być dozwolone w stałym czasie. Jest na to wiele opcji bez jednej akceptowanej odpowiedzi. Druga, rozmiar słowa w jest zwykle zwiększany wraz z rozmiarem wejściowym (co najmniej tak szybkim jak log (n)), aby umożliwić adresowanie dowolnego elementu w pamięci za pomocą stałej liczby słów. Oznacza to, że trzeba sobie wyobrazić nieskończoną klasę maszyn, na których działa twój algorytm, lub nawet gorzej, że maszyna zmienia się, gdy podajesz jej więcej danych. To niepokojąca myśl dla najczystszych przynajmniej wśród moich studentów. Wreszcie, otrzymujesz nieco zaskakujące wyniki dotyczące złożoności dzięki modelowi słowo-RAM, który może nie zgadzać się z tymi, których uczy się jako uczeń. Na przykład, mnożenie dwóch liczb n-bitowych to czas O (n) w tym modelu, a po prostu odczytanie ciągu n-bitowego jest nagle podliniową operacją czasową. Oznacza to, że trzeba sobie wyobrazić nieskończoną klasę maszyn, na których działa twój algorytm, lub nawet gorzej, że maszyna zmienia się, gdy podajesz jej więcej danych. To niepokojąca myśl dla najczystszych przynajmniej wśród moich studentów. Wreszcie, otrzymujesz nieco zaskakujące wyniki dotyczące złożoności dzięki modelowi słowo-RAM, który może nie zgadzać się z tymi, których uczy się jako uczeń. Na przykład, mnożenie dwóch liczb n-bitowych to czas O (n) w tym modelu, a po prostu odczytanie ciągu n-bitowego jest nagle podliniową operacją czasową. Oznacza to, że trzeba sobie wyobrazić nieskończoną klasę maszyn, na których działa twój algorytm, lub nawet gorzej, że maszyna zmienia się, gdy podajesz jej więcej danych. To niepokojąca myśl dla najczystszych przynajmniej wśród moich studentów. Wreszcie, otrzymujesz nieco zaskakujące wyniki dotyczące złożoności dzięki modelowi słowo-RAM, który może nie zgadzać się z tymi, których uczy się jako uczeń. Na przykład, mnożenie dwóch liczb n-bitowych to czas O (n) w tym modelu, a po prostu odczytanie ciągu n-bitowego jest nagle podliniową operacją czasową.

Powiedziawszy to wszystko, jeśli chcesz tylko wiedzieć, czy Twój algorytm będzie działał szybko, najprawdopodobniej zrobi to :-)

Raphael
źródło
2
Myślę, że jeśli unikasz operacji arytmetycznych bitowych lub modelowania słów, próbując uniknąć problemu „maszyna rośnie wraz z rozmiarem wejściowym”, ale nadal używasz jednolitej pamięci RAM lub maszyny wskazującej, to po prostu oszukujesz siebie: te inne modele mają ten sam problem. Jak indeksują swoje dane wejściowe? Odpowiedź brzmi: w prawdziwych komputerach brakuje pamięci, ale mimo to wygodniej jest zaprojektować dla nich algorytmy, zakładając, że są one pamięcią RAM (a może nawet lepiej jest użyć modelu uwzględniającego koszty hierarchii pamięci), niż zakładając, że są DFA.
David Eppstein,
4
Model RAM, o którym dyskutuje Knuth, kosztuje na przykład czas na wyszukanie adresu za pomocą bitów w i podobnie czas na dodanie dwóch liczb w bitów (w ten sposób dostaje Theta (n log n) za czas pomnożenia dwóch n -bitowe liczby w modelu RAM bez operacji na słowach o stałym czasie). Interesujące jest to, jak zmieniły się najczęściej akceptowane modele w ciągu ostatnich 20 lat i ile modeli już nigdy nie jest omawianych.
Raphael,
8

Modele to tylko modele. Nie posunąłbym się za daleko; mówią coś o niektórych aspektach twoich algorytmów, ale nie całą prawdę.

Sugerowałbym, abyś po prostu użył standardowego modelu słowa RAM do analizy i zaimplementował algorytm i zobaczył, jak dobrze sobie radzi w praktyce.

(Właściwie samo wdrożenie algorytmu bez jego uruchamiania mówi ci już o nim wiele ... Po pierwsze, jest to możliwe do wdrożenia.)

Jukka Suomela
źródło
3
Mam dwa zastrzeżenia. Po pierwsze, niewielu teoretyków implementuje algorytmy, a jednak musimy je jakoś porównać. Po drugie, chcę zrozumieć, jakie funkcje komputera możemy dodać do modelu, nie tracąc jego prostoty.
Tatiana Starikovskaya
11
Zaproponowane przez Davida Johnsona rozwiązanie polega na tym, aby więcej osób wdrożyło algorytmy - zaczął rozwiązywać ALENEX i wyzwania DIMACS. Mam z tym również trochę doświadczenia. Wraz z Kenem Clarksonem opracowałem randomizowany algorytm wypukłego kadłuba, który naszym zdaniem będzie sprawdzał się w praktyce. Clarkson zlecił wdrożenie letniego studenta w Bell Labs. W oparciu o obietnicę tej implementacji pomysły zostały opracowane w programie qhull (napisanym w Centrum Geometrii), ale z pewnymi przyspieszeniami heurystycznymi, co oznacza, że ​​algorytm nie ma już teoretycznej gwarancji szybkiego działania.
Peter Shor,
5

Jeśli Twoim zadaniem obliczeniowym jest bardziej przenoszenie danych niż wykonywanie operacji (arytmetycznych) (zestawy danych są ogromne, więc nawet nie mieszczą się w głównej pamięci), to model I / O (wprowadzony przez Aggarwal i Vitter w 1988 r. ) może być bardzo dokładne. W przypadku takich zadań, jak permutacja dużej liczby elementów w pamięci głównej, pomocne może być użycie algorytmów optymalnych dla operacji wejścia / wyjścia (w ostrożnej implementacji).

W przypadku nowoczesnych komputerów wielordzeniowych równoległy wariant wprowadzony przez Arge, Goodricha, Nelsona i Sitchinavę w 2008 r. Może być dokładnym modelem.

Riko Jacob
źródło
5

Jeśli masz na myśli „najlepszy” model obliczeniowy, który uczyni twoje życie bardziej skomplikowanym, możesz użyć 2-stanowej, 3-symbolowej uniwersalnej maszyny Turinga Wolfram.

Wady : brak oprócz wrażenia, że ​​kroczy się cienką linią między rozumem a szaleństwem;

Wady : tony ...

:-D (tylko żart, w zasadzie zgadzam się z poprzednimi odpowiedziami ...)

Marzio De Biasi
źródło
1

Bardziej teoretyczna uwaga: artykuł Ostateczne modele teoretyczne nanokomputerów dowodzą , że odwracalny model siatki 3D jest optymalnym fizycznym modelem obliczeń, w tym sensie, że żaden inny model fizyczny nie mógłby być asymptotycznie szybszy. Omówiono kwestie fizyczne, takie jak prędkość światła, zasada Landauera i granica Bekensteina .

Cytat z streszczenia:

Stwierdzamy, że przy użyciu obecnej technologii odwracalna maszyna zawierająca zaledwie kilkaset warstw obwodów mogłaby przewyższyć każdą istniejącą maszynę, a odwracalny komputer oparty na nanotechnologii musiałby mieć zaledwie kilka mikronów średnicy, aby przewyższyć każdą możliwą nieodwracalną technologię.

Twierdzimy, że silikonowa implementacja odwracalnej siatki 3D może być dziś cenna dla przyspieszenia niektórych obliczeń naukowych i inżynieryjnych, i proponujemy, aby model ten stał się przedmiotem przyszłych badań w teorii algorytmów równoległych dla szerokiego zakresu problemów.

użytkownik76284
źródło