Czy algorytmy zależą od architektury komputera?

Czytałem gdzieś (zapomniałem, która to książka), że algorytmy są niezależne od architektur komputerowych. Niektórzy nawet twierdzą, że algorytmy są obliczeniami (maszyny?)?

Z drugiej strony książki o programowaniu równoległym zawierają rozdziały na temat algorytmów równoległych. Wygląda na to, że algorytmy równoległe zależą od architektur równoległych?

Chyba brakuje mi dużych zdjęć? Dzięki.

Algorytmy to seria kroków podjętych w celu rozwiązania określonego problemu. Przepis na rozwiązanie problemu, jeśli chcesz. „Programy” oczywiście robią to samo; używamy „algorytmu”, aby zasugerować „ogólne” lub „ogólnie obowiązujące” przepisy, które są niezależne od konkretnych konstrukcji maszyn, języków programowania itp.

Algorytmy mają być ogólne, ale nadal mogą zależeć od niektórych obecnych funkcji. Na przykład „algorytmy współbieżne” mogą zależeć od tego, czy masz jakiś mechanizm jednoczesnego działania różnych programów. „Algorytmy rozproszone” mogą zależeć od tego, czy masz więcej niż jeden system we współpracującej grupie, oraz sieć lub inny schemat komunikacji między nimi. Podobnie „algorytmy równoległe” to często te zaprojektowane do działania, gdy masz wiele jednostek przetwarzających - potencjalnie wiele, wiele jednostek przetwarzających oraz rodzaj urządzeń komunikacyjnych, które są powszechne, gdy masz duże tablice jednostek przetwarzających. Możesz być w stanie uruchomić „algorytm równoległy”, nawet jeśli masz tylko jeden komputer lub jeden procesor - ale nie jest to szczególnie interesujące, ponieważ inżynierowie ruchu nie są

Algorytmy są niezależne od architektury komputera. Jest tak, ponieważ algorytmy definiują szereg procesów, które rozwiązują problem. Niezależnie od architektury algorytmy sortowania zawsze będą sortować. Nie renderowałby nagle rysunków 3D na niektórych architekturach.

Jeśli się nad tym zastanowić, to w rzeczywistości jest to intuicyjne. Google Chrome (który jest jedynie zbiorem algorytmów) to przeglądarka internetowa po skompilowaniu dla dowolnej architektury. W niektórych architekturach nie stałby się nagle sterownikiem urządzenia.

Ale szybkość działania algorytmów zależy od architektury. Niektóre algorytmy działają szybciej niż inne w zależności od architektury.

Jeśli się nad tym zastanowić, jest to również intuicyjne. Biorąc pod uwagę algorytm, projektant sprzętu zawsze może zaprojektować architekturę, która przyspieszy ten algorytm. To jeden z powodów, dla których istnieją takie przyspieszone karty graficzne 3D i akceleratory wydobywania bitcoinów.

Kiedy ludzie mówią o algorytmach równoległych, mówią o rodzinie algorytmów, które mogą działać szybciej na architekturach równoległych. Istnieje wiele algorytmów, które nie są ulepszane przez równoległe architektury. Identyfikacja nowych algorytmów dla tego samego problemu, które działają dobrze równolegle, jest aktywnym obszarem badań.

Ale te algorytmy nadal robią to samo. Architektury nie zmieniają tego, co robią.

„Wygląda na to, że algorytmy równoległe zależą od architektur równoległych?”

Moim zdaniem odpowiedź brzmi: nie. Ogólne Dostaję tylko właściwości

• równoległość
• rozmiar słowa (niejawne limity zasobów)

myśląc o architekturze sprzętu.

Odnosząc się do równoległości, możesz mieć dowolny algorytm równoległy obliczany wsadowo i dowolny równoległy łuk do pracy szeregowej, więc algorytm nie zależy od tego. Rozmiar słowa może być problemem dla stabilności numerycznej, ale nie dla samego algorytmu. Ograniczenia zasobów, takie jak 64-bitowe, mogą opisywać tylko 2 ^ 64 różne liczby mogą stanowić problem, ale w każdym razie elementy są ograniczone.

Oczywiście mogą istnieć pewne algorytmy, które zależą od niektórych rozszerzonych zestawów instrukcji, ale przynajmniej wszystko można opisać za pomocą podstawowej matematyki.

Na przykład przy obliczeniach kwantowych niektóre wartości Big-O mogą się zmienić i powiedziałbym to

„algorytmy są niezależne od architektur komputerowych”

nie jest już prawdą.

Algorytmy nie zależą od architektury komputera, jednak wydajność uruchamiania dowolnego konkretnego algorytmu zależy od architektury. Dowolne maszyny Turing Complete mogą emulować inne maszyny Turing Complete, chociaż niektóre maszyny byłyby lepsze w jednym przypadku niż inne.

Rozumiemy, że algorytmy współbieżne rozumiemy przez to, że algorytm działa dobrze lub może korzystać z współbieżności w maszynie, być może dlatego, że wymaga mniejszego blokowania, które w przeciwnym razie byłyby wymagane przez algorytmy, które nie zostałyby specjalnie zaprojektowane dla współbieżnej maszyny, a może dlatego, że Algorytm wykorzystuje dzielenie i podbijanie skutecznie, aby wykorzystać pełną moc maszyny. Uruchomienie algorytmu na niebieżnej maszynie byłoby nadal możliwe, ale może nie być tak wydajne lub może wymagać dodatkowego blokowania, aby działało poprawnie.

Istnieją również algorytmy, które zostały zaprojektowane tak, aby wykorzystać dziwactwo konkretnej architektury, takie jak algorytmy przyjazne dla pamięci podręcznej, które optymalizują buforowanie. Algorytmy te mogą być mniej wydajne w komputerach, które nie buforują tak, jak zakłada algorytm.

Teoretycznie algorytmy są całkowicie niezależne od architektury. Zawsze możesz emulować architekturę równoległą w systemie z pojedynczym wydaniem. Możesz argumentować na temat algorytmów bez architektury. Książka Knutha wykorzystuje fikcyjną architekturę.

W praktyce istnieją algorytmy, które próbują osiągnąć lepszy czas działania dla tej samej złożoności „O” poprzez optymalizację użycia sprzętu pamięci podręcznej i operacji podstawowych synchronizacji.

Tak i nie. Zależy to od ograniczeń, które chcesz spełnić, i warunków koniecznych do uruchomienia twojego algorytmu.

Idealnie, algorytm to abstrakcyjny przepis, który definiuje krok po kroku, jak coś zrobić. Algorytmy zdefiniowano w taki sposób w celu zapewnienia odtwarzalności, a następnie automatyzacji. Algorytmy wywodzą się z obliczeń lambda, dzięki czemu można łatwo zrozumieć, dlaczego zostały wykonane w taki sposób. Ta definicja jest zwykła, ale współczesne algorytmy mogą być niesekwencyjne (nie krok po kroku, jak algorytmy współbieżne lub logiczne, takie jak te wykorzystujące unifikację), nieliniowe (algorytmy stochastyczne) lub po prostu dziwne (kwantowe algorytmy), ale przekażę to.

Idealnie więc algorytm powinien być tak abstrakcyjny, jak to możliwe, bez księgowania jakiegokolwiek sprzętu.

Ale, jak w przypadku każdego systemu, musisz zdefiniować niektóre aksjomaty , nie tylko w celu uzyskania spójnego systemu, ale także w celu uzyskania czasu. Na przykład większość algorytmów zakłada, przynajmniej domyślnie, że są one zdefiniowane na maszynie Von-Neumann. Gdyby tak nie było, musieliby jednoznacznie zdefiniować każdą część systemu, na której mają być uruchomione (ponieważ jest to wymagane do odtworzenia przepisu, jest to rodzaj warunku wstępnego). Ponadto często algorytmy opierają się na popularnych poleceniach, takich jak write (), bez ich pełnego zdefiniowania.

Innym powodem, dla którego algorytmy nie są tak abstrakcyjne w stosunku do architektury sprzętowej, jest konieczność spełnienia pewnych ograniczeń .

Załóżmy, że pracujesz na systemach wbudowanych, więc prawdopodobnie nie możesz polegać na takiej samej ilości zasobów, jaką masz na stacjach roboczych. Jednym z najbardziej powściągliwych zasobów jest prawdopodobnie pamięć. Jednak większość algorytmów ma tendencję do optymalizacji złożoności czasowej (szybkości wykonywania na procesorze), a nie złożoności pamięci (ilość pamięci niezbędnej do pracy na danych). Dla tych systemów opracowano algorytmy zoptymalizowane pod kątem pamięci, w których algorytmy niezoptymalizowane pod kątem pamięci po prostu zawiodłyby lub działałyby znacznie wolniej. W rzeczywistości systemy wbudowane nie są jedynym celem algorytmów efektywnych pod względem pamięci: na przykład istnieją algorytmy nieobsługujące pamięci podręcznej, które dostosowują swoje przetwarzanie do efektywnego wykorzystania pamięci podręcznej procesora. Kolejny przykład: niektóre algorytmy uczenia maszynowego dla dużych zbiorów danych są dostosowanenauka przyrostowa lub przetwarzanie poza rdzeniem w celu przetwarzania ogromnej ilości danych znacznie większych niż pamięć dostępna na dowolnym komputerze itp.

Istnieją również algorytmy, które nie optymalizują określonej części komputera, ale standard zależny od architektury sprzętowej. Na przykład dane liczbowe wymagające precyzji są przechowywane w liczbach zmiennoprzecinkowych lub podwójnych, które z natury są ograniczone ze względu na ograniczenia sprzętowe. Problem polega na tym, że złożone obliczenia mogą prowadzić do zaokrąglania, a im więcej obliczeń wykonasz na zaokrąglonych liczbach, tym bardziej będziesz odpływał. Nazywa się to katastrofalną ingerencją . Niektóre aplikacje wymagają krytycznej precyzji, nawet kosztem najgorszej złożoności. Dla tego typu aplikacji opracowano algorytmy optymalizujące ich obliczenia w celu zmniejszenia lub usunięcia katastrofalnych zakłóceń.

Zatem projektowanie algorytmu może być również kompromisem między abstrakcją a ograniczeniami.

Na koniec możemy powiedzieć, że algorytm jest tak abstrakcyjny, jak jego cel i jak wymaga tego jego warunek wstępny (architektura) . Im bardziej konkretny cel ma algorytm, tym bardziej prawdopodobnie będzie on polegał na architekturze sprzętowej.

Niektóre powiązane słowa kluczowe, które mogą Cię zainteresować:

• Lokalizacja odniesienia
• Optymalizacja pętli
• Optymalizacja gniazda pętli
• Skalowalna lokalizacja

Nie należy mylić algorytmu ogólnie z algorytmami matematycznymi lub obliczeniowymi. Jeśli chodzi o algorytmy obliczeniowe, tak, są one niezależne od architektury maszyny.

Definicja algorytmu z Wikipedii:

W matematyce i informatyce algorytm jest samodzielnym zestawem operacji, które należy wykonać krok po kroku. Istnieją algorytmy, które wykonują obliczenia , przetwarzanie danych i automatyczne wnioskowanie.

Ta definicja jest używana w odniesieniu do niektórych zamkniętych zadań obliczeniowych lub przetwarzania danych. Innymi słowy, obliczenia, które można abstrakcyjnie uruchomić na maszynie Turinga . Jednak ostatnio w matematyce istnieje pojęcie o nazwie Obliczanie interaktywne, które obejmuje komunikację wejścia / wyjścia ze światem zewnętrznym podczas obliczeń.

W ogólnej definicji algorytm to tylko przepis (sekwencja instrukcji). Myślę, że nie możesz wymyślić algorytmu bez znajomości zestawu instrukcji lub operacji, których możesz użyć; Operacje matematyczne dotyczą obliczeń, a następnie algorytm obejmujący etap o nazwie „ rozgrzanie piekarnika ” nie jest algorytmem matematycznym, ale można go przekazać szefowi kuchni, ponieważ on wie, jak go wykonać.

Następnie możesz stworzyć maszynę, która potrafi X, Y, Z .... każdy z nich może być użyty w twoim algorytmie jako instrukcja. Ale jeśli chodzi o obliczenia zamknięte (w rzeczywistości, nieinteraktywne deterministyczne cyfrowe obliczenia małokrokowe), można udowodnić, że twoja maszyna jest odpowiednikiem maszyny Turinga . Ale jeśli celujesz w inny rodzaj obliczeń (kontynuuje wartości lub obliczenia interaktywne [jednak nie jestem pewien, czy to naprawdę inny rodzaj obliczeń]) lub nawet zadania bez obliczeń, możesz pomyśleć o maszynach, które mogą je wykonywać.

To pytanie i odpowiedź jest również interesujące, aby uzyskać szersze spojrzenie na algorytmy.

Ogólnie rzecz biorąc, algorytmy są opracowane dla określonych problemów przy minimalizacji pewnej miary „kosztu”. Historycznie wiele algorytmów zaprojektowano przy założeniu, że względne koszty wspólnych operacji byłyby względnie podobne na wielu architekturach, a zatem niektóre typowe maszyny działałyby jeden algorytm działałby lepiej niż inny, a na większości typowych maszyn poprzedni algorytm działałby najgorsze, bądź tylko nieznacznie gorszy od tego drugiego. Z biegiem czasu takie założenie nie działa tak dobrze, jak kiedyś.

Na przykład kiedyś było tak, że liczba razy, gdy program potrzebował odczytać rzeczy z pamięci, był uważany za ważniejszy niż lokalizacja rzeczy do odczytania. Czytanie rzeczy znajdujących się blisko siebie w pamięci było nieco tańsze niż czytanie rzeczy, które były daleko od siebie, ale nie były oburzające. Ponieważ szybkość głównego procesora wzrosła z szybkością znacznie przewyższającą prędkość pamięci, znaczenie sekwencji dostępu znacznie wzrosło. Możliwe jest wykonanie jednego programu dziesięciokrotnie większej liczby instrukcji niż inne, a mimo to szybsze działanie, jeśli 95% pobrań pamięci poprzedniego programu generuje trafienia w pamięci podręcznej L1, a większość pobrań pamięci tego drugiego programu generuje pomyłki w pamięci podręcznej.

Ponadto niektóre rodzaje algorytmów współbieżności przyjmują różne założenia dotyczące tego, kiedy dane zapisane w pamięci przez jeden rdzeń procesora będą „widoczne” przez inne rdzenie. Wiele procesorów ma różne sposoby odczytu i zapisu pamięci, przy różnych kosztach i gwarancjach widoczności. Niektóre algorytmy będą działać bardzo dobrze na architekturach, które mogą spełnić wymagania dotyczące widoczności „za darmo”, ale słabo na innych, w których instrukcje niezbędne do uzyskania tych gwarancji są drogie. Rzeczywiście, na niektórych architekturach można zagwarantować, że pewne algorytmy związane z współbieżnością będą działać tylko poprzez ograniczenie wykonania do pojedynczego współdzielonego czasowo rdzenia procesora (co oczywiście pokonałoby sens używania algorytmu współbieżnego).

W wielu odpowiedziach brakuje faktu, że algorytm można zdefiniować w kategoriach, które są albo abstrakcyjne, albo w bezpośrednim, dosłownym stosunku do architektury. Algorytm musi być jednoznaczny, ale jest jeszcze miejsce, aby był mniej lub bardziej szczegółowy.

Algorytm konwertujący ciąg znaków na wielkie litery można łatwo opisać w pseudokodzie niezależnym od architektury. Ale jednocześnie nic nie stoi na przeszkodzie, abyś opisał algorytm konwertujący ciąg znaków na wielkie litery, szczególnie w architekturze x86. Wystarczy zadanie domowe do złożenia w zespole x86. (Nadal możesz to zrobić w pseudokodzie - po prostu pseudokod odnoszący się do tej architektury!) Sam fakt, że problem dotyczy konkretnie architektury x86, nie oznacza, że ​​nie masz już algorytmu do jego rozwiązania.

Zależy to od problemu, który algorytm ma rozwiązać. Algorytm jest niezależny od architektury, jeśli rozwiązany przez niego problem jest niezależny od architektury (i przy założeniu, że nie zostanie to rozwiązane przez sposób opisania lub złożenia algorytmu). Problem może mieć charakter teoretyczny, tablicowy lub może dotyczyć bardzo specyficznej architektury. W tym drugim przypadku algorytm z kolei byłby ograniczony do pracy z tą architekturą.

Algorytmy to sekwencja kroków. Nie zależą od tego, co je wykonuje (lub nie wykonuje).

Jednak złożoność czas algorytmu może zależeć od tego, co się je wykonuje. Dlatego szczegółowa analiza algorytmu wymaga „modelu obliczeń”, takiego jak maszyna o dostępie swobodnym .
To, czy pamięć jest dostępna losowo, z pewnością wpływa na czas działania algorytmu, a większość algorytmów zakłada, że ​​tak jest, podczas gdy w rzeczywistości większość architektur nie spełnia tego warunku.

Różnią się w zależności od kontekstu problemów. Algorytm to zbiór kroków do rozwiązania problemu. Kontekst tego problemu może być teoretycznie dowolny. Dlatego algorytm rozwiązania problemu może zależeć od dosłownie wszystkiego, co możemy sobie wyobrazić we wszechświecie. Pozwól mi wyjaśnić na przykładzie. Powiedzmy, że masz zadanie:

Skonstruuj algorytm, który rozłoży obciążenia na wiele rdzeni, gdy będzie dostępny rdzeń wielordzeniowy.

Czy możesz sobie teraz wyobrazić, że Twój algorytm będzie zależny od architektury, czy nie? Oczywiście, że tak .