Czy jest coś, co MUSI być zrobione na wielordzeniowym procesorze?

45

Zastanawiając się nad tym, jak przyjazny dla wielu wątków musi być nasz program, mój zespół zastanawiał się, czy nie da się nic zrobić na jednordzeniowym procesorze. Stwierdziłem, że przetwarzanie grafiki wymaga masowo równoległego przetwarzania, ale argumentują, że takie rzeczy jak DOOM zostały wykonane na jednordzeniowych procesorach bez GPU.

Czy jest coś, co należy zrobić na procesorze wielordzeniowym?

Załóżmy, że jest nieskończony czas na rozwój i działanie.

Ben Leggiero
źródło
8
Chociaż poniższe odpowiedzi wydają się być w większości „nie”, historycznie istnieją systemy, które dosłownie nie mogłyby działać bez koprocesora obsługującego niektóre zadania. Jednym silnym przykładem, jaki znam, jest Nintendo DS, który zawiera procesor ARM9 67 MHz i procesor ARM7 33 MHz (również używany do kompatybilności wstecznej podczas grania w gry GBA). W przypadku gier DS ARM7 obsługuje odtwarzanie dźwięku i komunikację Wi-Fi, ponieważ ARM9 nie może przetworzyć i narysować nic ważnego na ekranie, jednocześnie nadążając za bezpośrednim podawaniem dźwięku do układu dźwiękowego. Tak więc, jak @jmite stwierdza „pod jakimi ograniczeniami”, brak prędkości może wymagać wielu procesorów.
Slipp D. Thompson
10
W mojej pracy korzystamy z wielordzeniowych Xeonów i rozszerzeń Xenomai w czasie rzeczywistym dla Linuksa, aby przetwarzać audio z niskim opóźnieniem. Mamy trzyetapowy potok przetwarzania dźwięku, a każdy etap ma swój własny dedykowany rdzeń, który wykorzystuje ~ 70% cykli. Zadania nie wykonywane w czasie rzeczywistym mogą korzystać z czwartego rdzenia, a wszelkie pozostałe cykle pozostały w pierwszych trzech. Byłoby to możliwe tylko w przypadku jednordzeniowego procesora, jeśli ten jednordzeniowy rdzeń był ponad 3 razy szybszy niż rdzeń w obecnym czterordzeniowym procesorze; biorąc pod uwagę, że obecny procesor pracuje z częstotliwością 2 GHz, może to być trudne do osiągnięcia.
Jeremy Friesner,
19
Oprogramowanie procesora jednordzeniowego może emulować procesor wielordzeniowy. Różnica polega prawie na prędkości.
user253751
24
Jedną rzeczą, którą należy zrobić w systemie wielordzeniowym, jest testowanie oprogramowania wielowątkowego. Ponieważ niektóre defekty (prawie) nigdy nie wystąpią w systemie jednordzeniowym. Nie jestem jednak pewien, czy kwalifikuje się jako odpowiedź ...
nikie
13
@nikie Jednordzeniowy system może również emulować porządkowanie pamięci i przestarzałe pamięci podręczne - ale wyobrażam sobie, że byłoby to bardzo nieefektywne (jak 10 × spowolnienie)
Nayuki

Odpowiedzi:

47

Jeśli nie zależy Ci na czasie działania, cokolwiek możesz zrobić na maszynie wielordzeniowej, możesz to zrobić na maszynie jednordzeniowej. Maszyna wielordzeniowa to tylko sposób na przyspieszenie niektórych obliczeń.

TnTn

DW
źródło
3
Nie jestem do końca pewien, czy jest to absolutnie poprawne. Nie sądzę, aby błędy spójności pamięci były możliwe do wygenerowania na jednym rdzeniu (tak, można emulować system multicache na jednorożcu, ale taka pośrednictwo jest rodzajem oszustwa). (Być może jest to odpowiednik implementacji zamiany reg. Przez ruch operacji w VLIW, wykorzystując gwarantowany || ism?) Przypuszczam, że nawet na rdzeniu jednowątkowym nadal byłoby możliwe wyodrębnienie entropii z wielowątkowej zmienności taktowania, ale ilość entropia byłaby mniejsza na jednostkę czasu (co tak naprawdę jest tylko kwestią wydajności, podobnie jak inne różnice).
Paul A. Clayton
6
@ PaulA.Clayton Błędy spójności pamięci są zwykle niepożądane i dobrze napisane oprogramowanie nie powinno ich wykazywać. Jeśli jednak naprawdę tego chcesz, możesz emulować je na jednym procesorze. (Chociaż może to być powolne)
253751
4
nn
11
„Maszyna jednordzeniowa może emulować maszynę wielordzeniową za pomocą podziału czasu / podziału czasu”. I rzeczywiście zrobili to od zarania „nowoczesnego” systemu operacyjnego.
Lekkość ściga się z Monicą
1
@ PaulA.Clayton Myślę, że możesz mieć problemy z spójnością pamięci (takie jak przyrost nieatomowy), gdybyś miał dwa różne procesy, które modyfikowały tę samą pamięć współdzieloną. Potrzebujesz tylko wyprzedzającego wielozadaniowości. Oczywiście z tego właśnie powodu współczesne systemy operacyjne nie mają procesów współużytkujących tę samą zapisywalną pamięć, chyba że wyraźnie o to proszą.
Patrick M
58

Pytanie brzmi: pod jakimi ograniczeniami?

Z pewnością istnieją problemy, gdy zadamy pytanie „czy możemy rozwiązać ten problem na sprzęcie X w określonym czasie”, odpowiedź będzie przecząca.

Ale nie jest to odpowiedź „na przyszłość”: rzeczy, które w przeszłości nie mogły być wykonane wystarczająco szybko w jednym rdzeniu, prawdopodobnie mogą być teraz i nie możemy przewidzieć, do czego będzie zdolny przyszły sprzęt.

Jeśli chodzi o obliczalność, wiemy, że maszyna Turinga z pojedynczą taśmą jest w stanie wykonać wszystkie te same funkcje, co komputer jedno- lub wielordzeniowy, więc poza środowiskiem uruchomieniowym nie ma problemów, że komputer wielordzeniowy może rozwiązać pojedynczy rdzeń nie może.

Jeśli chodzi o coś takiego jak grafika, dosłownie wszystko, co jest na GPU, można zrobić na procesorze ... jeśli jesteś gotów czekać wystarczająco długo.

jmite
źródło
3
@JanDvorak Powiedziałbym, że GPU wcale tego nie robi;)
TomTom
15
Jeśli czas nie jest ograniczeniem, możesz wykonać wszystkie obliczenia ręcznie, długopisem i papierem.
matematyk
2
@mathreadler Tak, ponieważ mózg jest Turinga kompletny. Coś, co zmieniło się w długą debatę na temat wymiany stosów fizyki.
JBentley,
4
Właściwie @JanDvorak, generując VGA jest bardzo prosta i może być wykonana w oprogramowaniu na pokornego 16 MHz mikrokontroler, ponieważ projekt pokazuje: pyroelectro.com/tutorials/arduino_basic_vga
axello
3
@ matreadler To jest tak naprawdę bardziej skomplikowane pytanie, niż się wydaje. Krótka odpowiedź może brzmieć „tak”, ponieważ wyspecjalizowana maszyna może zbudować komputer bez konieczności wykonywania jakichkolwiek narzędzi. Dłuższą odpowiedzią może być „nie”, ponieważ zdolność do zbudowania maszyny Turinga może oznaczać, że ma się większą maszynę Turinga, która jest w stanie „inicjalizacji”, w którym konstruuje resztę maszyny stanu. Pełna odpowiedź jest jeszcze bardziej skomplikowana, ponieważ nigdy nie skonstruowaliśmy urządzenia Turing Complete. Opracowaliśmy abstrakcyjne pomysły na maszyny, które są ...
Cort Ammon
17

Jak wskazały inne odpowiedzi, jeden procesor zawsze może emulować wiele procesorów, skracając czas i odgrywając rolę każdego wirtualnego procesora. Ta emulacja z pewnością obliczy poprawne odpowiedzi.

W prawdziwym świecie czas wykonania może być ważny. Może to oznaczać różnicę między mierną liczbą klatek na sekundę a gwiezdnym doświadczeniem wizualnym. Lub różnica między zyskiem a stratą w handlu.

Jedna patologiczna sytuacja, w której multiprocesor jest znacznie szybszy niż uniprocesor, polega na tym, że przetwarzanie jest potokiem danych, przełączanie kontekstu jest drogie, a kod maszynowy dla każdego etapu potoku ledwo mieści się w pamięci podręcznej procesora.

Pozwól mi zilustrować za pomocą niektórych liczb. Załóżmy, że masz potok danych (renderowanie 3D itp.), Który ma 4 etapy przetwarzania, każdy etap ma 256 KiB kodu programu i wygodnie masz 4 procesory z 256 KiB pamięci podręcznej L2. Jeśli spróbujesz uruchomić to przetwarzanie na jednym procesorze, przełączanie między 4 zadaniami będzie kosztowne i wiąże się z dużymi brakami pamięci podręcznej. Z drugiej strony, jeśli uruchomisz go w systemie 4-rdzeniowym, obliczenia mogą potencjalnie być bardzo płynne, pominięcia pamięci podręcznej są minimalne, a przełączniki kontekstu nie istnieją. (Na marginesie, jest to związane z pojęciem przypinania niektórych aplikacji do niektórych rdzeni - np. Wykonywania operacji jądra systemu operacyjnego tylko w jednym rdzeniu lub obsługi protokołu TCP / IP itp.)

Nayuki
źródło
7

Znacznie trudniej jest opracować naprawdę nikczemne wyścigi danych za pomocą jednego procesora. Chodzi mi o to, że możesz przerwać szarpanie między słowami, jeśli przerwiesz pojedynczy procesor, ale czy potrafisz budować egzotyczne scenariusze, w których nie ma pojedynczego przeplatania wątków, co byś chciał?

Ok, może podstępne błędy nie liczą się jako poprawne użycie ulepszeń wielu kodów. Jak się okazuje, wiele rdzeni nie jest w stanie zrobić, tak jak pojedynczy rdzeń nie ma czasu. Powód jest prosty. Jeśli spróbujesz uniknąć tych złych wyścigów danych, musisz mieć punkty synchronizacji w kodzie. Jeśli modelujesz swój kod jako sieć obliczeń, w której dane wejściowe muszą być kompletne i zsynchronizowane przed obliczeniem i wygenerowaniem danych wyjściowych, łatwo zauważyć, że pojedynczy procesor może po prostu pracować wzdłuż sieci, obliczając następny dostępny blok pracy .

W rzeczywistości, jeśli potrafisz wykazać, że Twój algorytm może zostać rozwiązany przez maszynę Turinga (czyli praktycznie każdy algorytm, na którym nam zależy), można udowodnić, że algorytm może być wykonany nie tylko przez pojedynczy rdzeń procesora, ale w rzeczywistości automat państwowy z bardzo długim kawałkiem taśmy do pamięci!

SZACHY detektor wyścig rzeczywiście wykorzystuje to, aby znaleźć przypadki wyścigu. Obsługuje wszystko pojedynczo i systematycznie bada wszystkie możliwe przeploty między wątkami, próbując znaleźć przypadki, w których test kończy się niepowodzeniem z powodu przypadku wyścigu. SZACHY zależą od tego, że możesz uruchomić dowolną aplikację wielowątkową na jednym rdzeniu.

Przypadki, w których potrzebujesz wielordzeniowości, pojawiają się, gdy zaczynasz rozciągać ograniczenia sprzętu. Oczywistym jest, że masz ograniczenia czasowe. Niektóre problemy z ograniczeniami czasu rzeczywistego są niemożliwe do wykonania z jednym rdzeniem, ponieważ po prostu nie są w stanie wystarczająco szybko sterować zegarem z jednym rdzeniem. Jest powód, dla którego procesory wspięły się do 4 GHz, a następnie nieco się uspokoiły, woląc więcej rdzeni przy niższych prędkościach.

Bardziej egzotyczna wersja tego ograniczenia czasowego znajduje się w systemach czasu rzeczywistego. W niektórych trudnych systemach czasu rzeczywistego obsługa przerwań jest tak wymagająca, że ​​faktycznie trzeba wybrać procesor wielordzeniowy, który pozwala rozdzielić przerwania między rdzeniami lub napotkać ograniczenia czasowe.

Kolejny limit powstaje w przypadku magistrali danych. Rozważ Blue Gene / P jako przykład. JUGENE, szczególny superkomputer Blue Gene / P, ma 144 terabajty pamięci. Po prostu nie produkują komputerów z jednym procesorem, które mają dostęp do całej tej pamięci.

Cort Ammon
źródło
1
Re, po prostu nie robią komputerów z jednym procesorem, które mogą uzyskać dostęp do [tak dużej] pamięci. „Nie” to nie to samo, co „nie może”. Ty mógł zaprojektować i zbudować Jednoprocesorowy z 144 terabajtów lub więcej pamięci głównej. Jedynym powodem, dla którego ludzie tego nie robią, są zmniejszające się zwroty: Przyrostowa, praktyczna wartość dodawania większej ilości pamięci do konstrukcji jednoprocesorowej osiąga szczyt w pewnym momencie, a następnie spada wraz ze wzrostem wielkości pamięci, podczas gdy koszt przyrostowy pozostaje stały .
Solomon Slow
@jameslarge Właśnie dlatego to zdanie pojawiło się w części mojej odpowiedzi dotyczącej praktycznego sprzętu z prawdziwego życia i dlaczego nie pojawiło się w pierwszej 2/3 odpowiedzi, która omawiała teoretyczne możliwości.
Cort Ammon
„Nie” kontra „Nie mogę” ilustrują dwa systemy w mojej piwnicy. Gdybym mógł fizycznie dodać tyle pamięci do ich konfiguracji sprzętowych, ich procesory „mogłyby” uzyskać dostęp do każdego bajtu. Ale nie mogę, więc „nie mogą”. Możliwości procesorów przekraczają praktyczność.
user2338816,
Myślałem o takiej odpowiedzi. Wydaje się, że warunki wyścigu byłyby niemożliwe (lub zdarzyłyby się w 100% przypadków) w środowisku z jednym rdzeniem. Jeśli chodzi o praktyczne zastosowanie, teoretyzuję, że twórca oprogramowania mógłby zaprojektować unikalną formę ochrony przed kopiowaniem, kodując jakiś dziwny test warunków wyścigu, który zawsze przekazywałby określony sprzęt docelowy, ale zawodziłby na emulowanym sprzęcie uruchamianym przez pojedynczy rdzeń . W takim przypadku emulacja przez system wielordzeniowy prawdopodobnie przejdzie czasami, ale niewiarygodnie.
Dan Henderson
6

Jeśli chcesz obserwować proces działający na pojedynczym elemencie przetwarzania, nie zakłócając jego zachowania w czasie rzeczywistym (lub tak mało, jak to możliwe), np. W przypadku testów porównawczych lub rejestrowania aktywności, prawdopodobnie potrzebujesz osobnego zasobu przetwarzania.

Yves Daoust
źródło
Miły, zwięzły przykład czegoś, co wymagałoby precyzyjnej emulacji, gdyby nie wielu procesorów
Ben Leggiero,
Hej, czy to twoje konto? Czy chcesz to połączyć?
Zły
4

Inne odpowiedzi są zgodne z ograniczonym poglądem na paralelizm jako „współbieżność rozproszoną”. To daje kilka odpowiedzi: w czystym modelu obliczeniowym à la Turinga wiele rdzeni nie daje przewagi; jedyną korzyścią, jaką możesz uzyskać, jest wydajność.

Jest to jedna rzecz wielu jednostek przetwarzania (ropa) może zrobić, że jeden nie można, chociaż: wykonanie operacji równolegle , czyli w tym samym czasie .

Jest to bardzo przydatne, jeśli uruchamiasz wiele programów jednocześnie. To prawda, że ​​rzadko zdarza się, że absolutnie potrzebujesz czegoś więcej niż równoczesnego wykonywania, a większość zastosowań sprowadza się do zwiększenia wydajności. Ale jest ta różnica.

Powiedz, że musisz przetwarzać dane czujnika danych z wielu źródeł w czasie rzeczywistym. Cokolwiek to dokładnie oznacza w twojej aplikacji, jeden PU może obsługiwać tylko tyle strumieni wejściowych jednocześnie, bez naruszania limitu czasu odpowiedzi. Potrzebujesz więc wielu PU, gdy będziesz mieć zbyt wiele czujników dla bieżącej generacji PU.

k

kkk

Raphael
źródło
0

z CS pov, „wielordzeniowy” nie różni się tak bardzo w teorii, jak „przetwarzanie rozproszone”. podstawowa koncepcja to „niezależne elementy obliczeniowe (obliczające się równolegle”). więc nieco sformułowanie pytania („wielordzeniowy” nie jest tak naprawdę teoretyczną koncepcją w CS) prowadzi do innych możliwości. jak wskazano w innych odpowiedziach, programowanie sekwencyjne jest równoważne programowaniu równoległemu z pov CS. wraca to do definicji teoretycznego systemu obliczeniowego, a mianowicie maszyny Turinga. teoretyczna analiza wydajności CS jest ostatecznie pod kątem TM, w których tak naprawdę nie ma zastosowania rozróżnienie równoległe a sekwencyjne ( chociaż istnieje pewna zgrubna analogia z TM na wielu taśmach ).

ale biorąc pod uwagę to pytanie mniej abstrakcyjnie, przetwarzanie rozproszone jest rzeczywiście lepsze, a nawet prawie wymagane w przypadku niektórych problemów związanych z odpornością na uszkodzenia . w tym obszarze istnieje koncepcja, która ma zastosowanie, gdy / gdzie przyjmuje się, że niezależne elementy obliczeniowe mają pewien stopień zawodności (nie jest to tak naprawdę uniwersalne założenie we wszystkich kontekstach). Oto kilka przypadków, w których odporność na awarie jest zwiększona, a nawet wymaga niezależnych elementów obliczeniowych.

  • należy wziąć pod uwagę, że każdy procesor ma niezależną „[x]%” szansę niepowodzenia podczas obliczeń. można opracować system, w którym poprzez komunikację ogólna tolerancja na uszkodzenia systemu jest lepsza niż poszczególnych elementów. zostało to zastosowane wiele dziesięcioleci temu, np. w systemach promu kosmicznego. ostatnio istnieją podstawowe protokoły zaprojektowane do jego wykorzystania, np. Paxos, które rozwiązują tak zwany problem konsensusu . bardziej przyziemnym przykładem jest Google, który ma wiele zastrzeżonych algorytmów, które zasadniczo budują swój superkomputer (-y) z indywidualnie zawodnych elementów w połączeniu z algorytmami odpornymi na uszkodzenia.

  • Bitcoin obejmuje transakcje rozproszone w celu obliczenia księgi głównej, a to nie tylko ze względu na zwykłe problemy z przetwarzaniem obciążenia. algorytm jest starannie zaprojektowany, aby udaremnić uszkodzone węzły. w skrócie „rozwiązuje” / wdraża problem generałów bizantyjskich, który nie polega wyłącznie na maksymalizacji wydajności równoległej, obejmuje niezależne jednostki „sprawdzające” siebie nawzajem i „algorytmicznie / kryptograficznie / bezpiecznie” odrzucające nieprawidłowe obliczenia, nazywane swoistym „oszustwem” lub „ korupcja".

  • klasyczna analiza paralelizmu stwierdza, że ​​istnieje około 7 „podstawowych” typów wzorców problemów, które rozkładają się na poszczególne awarie wykonywania równoległego. patrz Krajobraz badań równoległych obliczeń: widok z Berkeley

  • istnieje tutaj pewien element otwartego pytania teoretycznego, który nie uwzględnia rozważań dotyczących wydajności w większości innych odpowiedzi. pytanie, czy są jakieś problemy, które są „z natury szybsze” równolegle niż sekwencyjnie, jest również z grubsza znane jako problem P = NC, gdzie NC jest uważany za klasę algorytmów „wydajnie zrównoleglalnych”, a P to algorytmy „wydajne [sekwencyjne] „

vzn
źródło
1
Uwielbiam tę odpowiedź! Wiele się nauczyłem z twoich przykładów: D
Ben Leggiero
+1 za odporność na uszkodzenia w środowiskach o krytycznym znaczeniu z promieniowaniem, -1 za brak ograniczeń i redundancję.
Cees Timmerman,