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

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.

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ń.

$T$$n$$\sim Tn$

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.

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.)

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.

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.

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$

$k$$k$$k$

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] „