Różnica między wykonywaniem „równoległym” i „równoległym”?

107

Jaka jest różnica między warunkami współbieżnych i równoległego wykonywania? Nigdy nie byłem w stanie zrozumieć tego rozróżnienia.

Tag definiuje współbieżność jako sposób uruchamiania dwóch procesów jednocześnie, ale myślałem, że równoległość jest dokładnie taka sama, tj. Osobne wątki lub procesy, które potencjalnie mogą być uruchomione na osobnych procesorach.

Ponadto, jeśli weźmiemy pod uwagę coś w rodzaju asynchronicznego we / wy, to czy mamy do czynienia z współbieżnością lub równoległością?

blz
źródło
27
W skrócie - jednocześnie: wiele różnych operacji dzieje się jednocześnie. równolegle: ta sama operacja podzielona na małe kawałki dzieje się jednocześnie.
Oded
3
@Oded, rozumiem, co oznaczają te słowa, ale mam problem z rozwikłaniem implikacji. Czy masz konkretny przykład?
blz
7
@Odeded, tak naprawdę nie zgadzam się z tobą, nigdzie w ich definicjach (ogólnych lub stosowanych do programowania) pojęcia „współbieżne” i „równoległe” nie wspominają nic o liczbie lub „rozmiarze” operacji.
Shivan Dragon,
2
@Oded, kiedy powiedziałeś „małe kawałki”.
Avner Shahar-Kashtan
2
@Oded: Tak, ale wydaje się, że jest to przyczyną nieporozumień między tobą a ShivanDragon.
Avner Shahar-Kashtan

Odpowiedzi:

97

Współbieżność i równoległość to dwa powiązane, ale odrębne pojęcia.

Współbieżność oznacza zasadniczo, że zarówno zadanie A, jak i zadanie B muszą się zdarzyć niezależnie od siebie, a A zaczyna działać, a następnie B rozpoczyna się przed zakończeniem A.

Istnieją różne sposoby osiągnięcia współbieżności. Jednym z nich jest równoległość - posiadanie wielu procesorów pracujących nad różnymi zadaniami jednocześnie. Ale to nie jedyny sposób. Innym jest przełączanie zadań, które działa w ten sposób: Zadanie A działa do pewnego momentu, a następnie procesor na nim zatrzymany i przełącza się na zadanie B, działa przez chwilę, a następnie przełącza się z powrotem na zadanie A. przedziały czasowe są wystarczająco małe, może się wydawać użytkownikowi, że obie rzeczy są uruchamiane równolegle, nawet jeśli faktycznie są przetwarzane szeregowo przez wielozadaniowy procesor.

Mason Wheeler
źródło
4
W przypadku B działa asynchroniczne we / wy, nie?
blz
6
@blz: Zgadza się. Tak działa również zapobiegawcza wielozadaniowość. Główną różnicą jest to, że w asynchronicznym we / wy program decyduje się poświęcić swój czas i nakazać procesorowi przetworzenie czegoś innego, podczas gdy w zapobiegawczej wielozadaniowości, jeśli działający wątek nie poddaje się procesora po wystarczająco długim czasie, system operacyjny uprzedza to.
Mason Wheeler,
1
Najlepsze wytłumaczenie bez
Konrad
@MasonWheeler: Jeśli mamy tylko 1 procesor, możemy mieć tylko współbieżność, bez równoległości. Dobrze? Równoległość może być osiągnięta przez więcej niż 1 procesor. Dobrze? A jeśli jest to słuszne i jeśli mamy tylko 1 procesor, to strumienie z Java 8 nie są przydatne.
Anish Mittal
1
Dokładnie o pierwszych kilku punktach. Co do ostatniego, czy paralelizm jest jedyną korzyścią płynącą ze strumieni? Nie jestem programistą Java, ale mam wrażenie, że Strumienie Java są w przybliżeniu równoważne LINQ, a to daje realne korzyści w ekspresji i łatwości programowania.
Mason Wheeler
37

Te dwie koncepcje są powiązane, ale różne.

Współbieżność oznacza, że ​​dwa lub więcej obliczeń odbywa się w tym samym przedziale czasowym i zwykle istnieje między nimi pewna zależność.

Równoległość oznacza, że ​​dwa lub więcej obliczeń odbywa się jednocześnie.

Mówiąc śmiało, współbieżność opisuje problem (dwie rzeczy muszą się wydarzyć razem), podczas gdy równoległość opisuje rozwiązanie (dwa rdzenie procesora są używane do wykonywania dwóch rzeczy jednocześnie).

Równoległość jest jednym ze sposobów implementacji współbieżności, ale nie tylko. Innym popularnym rozwiązaniem jest przetwarzanie z przeplotem (inaczej coroutines): dzielenie obu zadań na etapy atomowe i przełączanie się między nimi.

Zdecydowanie najbardziej znanym przykładem nierównoległej współbieżności jest sposób działania JavaScript: istnieje tylko jeden wątek i każde asynchroniczne wywołanie zwrotne musi poczekać, aż poprzednia część kodu zakończy działanie. To ważne, aby wiedzieć, ponieważ gwarantuje, że każda pisana funkcja jest atomowa - żadne wywołanie zwrotne nie może jej przerwać, dopóki nie zwróci. Ale oznacza to również, że „zajęte pętle” nie będą działać - nie można ustawić limitu czasu, a następnie zapętlać, dopóki nie zostanie uruchomiony, ponieważ pętla uniemożliwi wykonanie wywołania limitu czasu.

tdammers
źródło
8
Mówisz tak Concurrency means that two or more calculations happen within the same time frame, and there is usually some sort of dependency between them.Ale użytkownik, który napisał tę zaakceptowaną odpowiedź, mówi Concurrency means, essentially, that task A and task B both need to happen independently of each other. Jaki jest zatem wniosek?
nbro 13.03.15
czy możesz wyjaśnić, dlaczego model JavaScript jest zgodny? Zgodnie z definicją współbieżności dwa lub więcej obliczeń powinno odbywać się w tym samym przedziale czasowym. Ale w JavaScript obliczenia są porządkowane sekwencyjnie za pomocą jednej kolejki.
damluar 21.04.16
4
Przez „w tym samym przedziale czasowym” niekoniecznie mam na myśli „jednocześnie”, po prostu ogólne ramy czasowe, w których występują. Można to osiągnąć równolegle (np. Dwa rdzenie procesora, z których każdy wykonuje jedno z zadań), ale można to również osiągnąć poprzez całkowitą serializację wykonania (najpierw wykonaj zadanie 1, zapamiętaj wynik, następnie wykonaj zadanie 2, a następnie zgłoś oba) lub przez pocięcie na kawałki i przeplatanie kawałków. To drugie robi JS.
tdammers
9

Wierzę, że ta odpowiedź jest bardziej poprawna niż istniejące odpowiedzi i ich edytowanie zmieniłoby ich istotę. Próbowałem linkować do różnych źródeł lub stron wikipedii, aby inni mogli potwierdzić poprawność.


Współbieżność: właściwość systemu, która umożliwia wykonywanie zadań programu, algorytmu lub problemu poza kolejnością lub w częściowej kolejności bez wpływu na końcowy wynik 1 2 .

Prostym tego przykładem są kolejne dodatki:

0 + 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 = 45

Ze względu na przemienną właściwość dodawania kolejność tych elementów można zmienić bez wpływu na poprawność; następujący układ da tę samą odpowiedź:

(1 + 9) + (2 + 8) + (3 + 7) + (4 + 6) + 5 + 0 = 45

Tutaj pogrupowałem liczby w pary, które sumują się do 10, dzięki czemu łatwiej jest mi znaleźć prawidłową odpowiedź w mojej głowie.

Obliczenia równoległe: rodzaj obliczeń, w którym wiele obliczeń lub wykonywanie procesów jest przeprowadzanych jednocześnie 3 4 . Zatem obliczenia równoległe wykorzystują właściwość współbieżności do wykonywania wielu jednostek programu, algorytmu lub problemu jednocześnie.

Kontynuując przykład kolejnych dodań, możemy wykonywać różne części sumy równolegle:

Execution unit 1:  0 + 1 + 2 + 3 + 4 = 10
Execution unit 2:  5 + 6 + 7 + 8 + 9 = 35

Następnie na koniec sumujemy wyniki każdego pracownika, aby uzyskać 10 + 35 = 45.

Ponownie, ta równoległość była możliwa tylko dlatego, że kolejne dodania mają właściwość współbieżności.

Współbieżność może być jednak wykorzystywana nie tylko przez równoległość. Rozważ pierwszeństwo w systemie z jednym rdzeniem: przez pewien czas system może robić postępy w wielu uruchomionych procesach, nie kończąc żadnego z nich. Rzeczywiście, twój przykład asynchronicznych operacji we / wy jest częstym przykładem współbieżności, która nie wymaga równoległości.


Zamieszanie

Powyższe jest stosunkowo proste. Podejrzewam, że ludzie się mylą, ponieważ definicje słownika niekoniecznie pasują do tego, co opisano powyżej:

  • Współbieżne: występujące lub występujące jednocześnie lub obok siebie 5 .
  • Współbieżność: fakt, że dwa lub więcej zdarzeń lub okoliczności dzieje się lub istnieje w tym samym czasie Od wyszukiwania w Google: „zdefiniuj: współbieżność” .

Słownik definiuje „współbieżność” jako fakt występowania, podczas gdy definicja w języku obliczeniowym jest utajoną właściwością programu, właściwości lub systemu. Choć powiązane te rzeczy nie są takie same.


Osobiste rekomendacje

Zalecam użycie terminu „równoległy”, gdy jednoczesne wykonanie jest zapewnione lub oczekiwane, i użycie terminu „współbieżnego”, gdy nie jest pewne lub nieistotne, czy zostanie zastosowane jednoczesne wykonanie.

Dlatego opisałbym symulowanie silnika odrzutowego na wielu rdzeniach jako równoległy.

Makefiles opisałbym jako przykład współbieżności. Pliki makefile określają zależności każdego celu. Gdy cele zależą od innych celów, powoduje to częściowe uporządkowanie. Gdy relacje i przepisy są kompleksowo i poprawnie zdefiniowane, ustanawia to właściwość współbieżności: istnieje częściowa kolejność, dzięki której kolejność niektórych zadań może zostać zmieniona bez wpływu na wynik. Ponownie, tę współbieżność można wykorzystać do budowania wielu reguł jednocześnie, ale współbieżność jest własnością Makefile, niezależnie od tego, czy stosuje się równoległość, czy nie.

Levi Morrison
źródło
6

Współbieżne wykonywanie jest uogólnioną formą wykonywania równoległego. Na przykład program równoległy można również nazwać równoczesnym, ale odwrotność nie jest prawdą.

  1. Możliwe jest jednoczesne wykonywanie na jednym procesorze (wiele wątków, zarządzanych przez program planujący)
  2. Wykonanie równoległe nie jest możliwe na jednym procesorze, ale na wielu procesorach. (Jeden proces na procesor)

Szczegółowe informacje można znaleźć w niniejszym dokumencie badawczym Koncepcje programowania współbieżnego


źródło
1
„Równoległe wykonywanie nie jest możliwe na jednym procesorze, ale na wielu procesorach” - inne niż oczywiście tam, gdzie istnieją równoległe ścieżki wykonania w procesorze, np. Systemy wykorzystujące równoległość poziomu instrukcji (inaczej architektury „superskalarnej”, np. Procesory Intel od Pentium, ARM Cortex i większość innych wysokiej klasy procesorów) oraz Single Instruction Multiple Data, znane również jako architektury równoległe do danych (np. MMX / SSE / etc). Nie wspominając o egzotycznych rozwiązaniach, takich jak procesory przepływu danych i tak dalej.
Jules
3

Przetwarzanie równoległe jest podzbiorem przetwarzania równoległego.

Współbieżne przetwarzanie opisuje dwa zadania występujące asynchronicznie, co oznacza, że ​​kolejność wykonywania zadań nie jest z góry określona. Dwa wątki mogą działać jednocześnie na tym samym rdzeniu procesora poprzez przeplatanie instrukcji wykonywalnych. Na przykład wątek 1 działa przez 10 ms, wątek 2 działa przez 10 ms itp.

Przetwarzanie równoległe jest rodzajem przetwarzania równoległego, w którym jednocześnie wykonuje się więcej niż jeden zestaw instrukcji. Może to być wiele systemów pracujących nad wspólnym problemem, jak w przypadku przetwarzania rozproszonego, lub wiele rdzeni w tym samym systemie.

ConditionRacer
źródło
0

Oświadczenie tdammera zbliża się wielkimi krokami, reszta jest poza tym istotna. On mówi:

„Śmiało mówiąc, współbieżność opisuje problem (dwie rzeczy muszą się wydarzyć razem), podczas gdy równoległość opisuje rozwiązanie (dwa rdzenie procesora są używane do wykonywania dwóch rzeczy jednocześnie”

Przeanalizujmy tylko słowa.

Obecne oznacza dzieje się teraz, rzeczywiste, istotne w tym momencie. Con oznacza przeciw, przeciwstawia się, nie zrównuje się z.

Równoległe oznacza w tym samym kierunku, bez przekraczania, bez wzajemnego przeszkadzania.

Zatem współbieżność oznacza konkurowanie o ten sam zasób. Równoległość nie. Procesy równoległe mogą korzystać z tego samego zasobu, ale nie jest to uważane za problem, nie jest to problem. W przypadku współbieżności należy rozwiązać ten problem.

Martin Maat
źródło
„Prąd oznacza, że ​​dzieje się teraz, rzeczywisty, istotny w tym momencie. Con oznacza przeciw, przeciwstawia się, nie dostosowuje się”. - wymagany cytat. Mocno wątpię w oba te stwierdzenia. Chociaż „prąd” może mieć znaczenie wspomniane tutaj w języku angielskim, nie jest to znaczenie użyte w słowie „współbieżne”
Hulk
1
Myślę, że tłumaczenie współbieżnego z łaciny to „biegać razem”. Przedrostek „con” często oznacza razem , ponieważ w spisku (oddychać razem) konsekwencja (wyniki razem lub następujące po sobie) kończy się (blisko siebie) itp. Jest to denerwujący aspekt języka, że ​​coś może mieć przeciwne znaczenia, sankcja jest moim ulubionym przykładem .
@no comprende W tym przypadku (współbieżne) znaczenie wspólnego działania wydaje się lepiej dopasowane. Ponieważ nie ma pro-prądu ... W języku niderlandzkim współbieżny to rzeczownik oznaczający konkurenta. Courant jest powszechny, porusza się wokół ciebie. To także gazeta. Coś, co jest teraz aktywne. „Rekening courant” to konto bieżące. Wydaje mi się, że współbieżność oznacza flet con (!). Walka o ten sam zasób. Działa w tej samej przestrzeni. Może ze względu na holenderskie znaczenie (konkurent).
Martin Maat
Zastanawiam się, co powiedziałby Dijkstra?
-1

Oczywiście, terminy są używane w różny sposób w różnych kulturach.

Moje rozumienie jest następujące:

Równoległość to sposób na przyspieszenie przetwarzania. Niezależnie od tego, czy wykonujesz mnożenie macierzy na jednym rdzeniu, na wielu rdzeniach, a nawet w GPU, wynik jest taki sam (w przeciwnym razie Twój program jest zepsuty). Nie dodaje nowych funkcji do niektórych programów, po prostu szybkość.

Podczas gdy współbieżność dotyczy rzeczy, których nie można zrobić sekwencyjnie. Na przykład wyświetlanie 3 różnych stron internetowych jednocześnie 3 klientom w oczekiwaniu na następne żądanie. (Chociaż można to do pewnego stopnia symulować poprzez przeplatanie, tak jak miało to miejsce w dawnych czasach). Zauważ, że zachowanie współbieżnych programów nie jest deterministyczne. Na przykład nie jest jasne, który z 3 klientów zostanie obsłużony jako pierwszy. Możesz uruchomić całkiem sporo testów i uzyskać inny wynik za każdym razem, gdy zamówienie zostanie zakończone. System wykonawczy powinien gwarantować, że a) wszyscy klienci będą obsługiwani oraz b) w rozsądnym czasie.

Zwykle koń roboczy obliczeń równoległych nie jest świadomy, ani nie dba o równoległość. Podczas gdy współbieżne zadania często jawnie wykorzystują komunikację międzyprocesową lub między wątkową - taką jak kolejki blokujące, mechanizmy synchronizacji i blokowania.

Ingo
źródło
-1

Moim zdaniem z punktu widzenia programowania aplikacji nie ma różnicy między tymi dwoma pojęciami, a posiadanie dwóch słów jest mylące ze względu na zamieszanie. Myślę, że przeplatanie wątków zostało wprowadzone w celu symulacji przetwarzania wielordzeniowego w czasach, gdy wielordzeniowy nie był możliwy. Dlaczego mamy słowo na ten przestarzały sposób myślenia?

Mason Wheeler i Penguin udzielili tej samej odpowiedzi. Jeden rdzeń z przełączaniem zadań i / lub wielordzeniem jest równoczesny, ściśle wielordzeniowy = równoległy.

Uważam, że te dwa terminy należy połączyć w jedno i staram się unikać wyrażenia „współbieżne”. Myślę, że na poziomie programowania systemu operacyjnego rozróżnienie jest ważne, ale z perspektywy programisty aplikacji nie ma to większego znaczenia. Napisałem mapReduce, Spark, MPI, cuda, openCL i wielowątkowy c ++ i nigdy nie musiałem się zatrzymywać i myśleć, czy zadanie działa z przeplatanymi wątkami czy z wieloma rdzeniami.

Na przykład, kiedy piszę wielowątkową wersję c ++, czasami nie jestem pewien, ile rdzeni otrzymam, chociaż istnieją sposoby na stawianie wymagań co do liczby rdzeni, jak opisano tutaj https://stackoverflow.com/questions/2166425/ how-to-structure-ac-application-to-use-a-multicore-processor . W iskrze po prostu wykonuję mapowanie i ograniczam operacje i nie mam pojęcia, w jaki sposób JVM obsługuje je na poziomie sprzętowym. Myślę, że na GPUkażdy wątek jest przypisany do własnego prostego procesora, ale zawsze synchronizuję wątki tam, gdzie może wystąpić problem. W MPI komunikacja między maszynami jest wyraźnie określona, ​​ale możemy przeplatać funkcje działające na wielu komputerach na jednym rdzeniu i łączyć wyniki za pomocą odpowiedniej funkcji jednowątkowej. A co, jeśli użyjemy MPI do koordynowania wielu maszyn z jednym rdzeniem, każdy z wielowątkowością? Jaką to robi różnicę? Nie powiedziałbym nic. Nazwij to wszystko „równoległym” i skończ z tym.

Julian Cienfuegos
źródło
2
To rozróżnienie jest nadal aktualne do dziś. Możesz mieć paralelizm tylko do liczby rdzeni procesora, jaką posiada Twój sprzęt, jednak wiele programów ma setki jednoczesnych obliczeń wykonywanych jednocześnie, znacznie więcej niż liczba rdzeni sprzętu. Niezrozumienie tego rozróżnienia może doprowadzić programistów do niezrozumienia, dlaczego ich programy równoległe działają wolniej niż wersja z jednym wątkiem (lub niewielka liczba wątków).
Lie Ryan,