Aktualne modele równoległe do obliczeń

Lata osiemdziesiąte dały początek modelom obliczeń równoległych PRAM i BSP . Wygląda na to, że okres świetności obu modeli przypadał na przełom lat 80. i 90.

Czy obszary te są nadal aktywne w zakresie badań algorytmów równoległych? Czy istnieją nowsze, bardziej wyrafinowane modele do obliczeń równoległych? Czy ogólne modele są nadal w modzie, czy też badacze próbują specjalizować się w GPGPU lub obliczeniach opartych na chmurze?

Istnieje wiele modeli unoszących się wokół, ale niektóre z nich są najbardziej istotne:

1. Modele MUD i Mapreduce , które głównie dotyczą przechwytywania środowiska MapReduce, ale bardziej ogólnie mogą być postrzegane jako równolegle rozproszone modele obliczeniowe
2. Różne zaproponowane modele wielordzeniowe (ale w żadnym wypadku nie są jeszcze standardem)

W zeszłym miesiącu w DIMACS odbyły się warsztaty na ten temat: przejrzenie streszczeń da więcej wskazówek.

Z góry przepraszam za format bloga mojej odpowiedzi. Nie mogłem się powstrzymać od zrobienia krótkiego przeglądu świata obliczeń równoległych.

Modele programowania równoległego można podzielić na mniej więcej dwie kategorie: modele sterowania przepływem i modele przepływu danych.

Modele sterowania przepływem próbują sprawić, by równoległość działała w kontekście programu jawnej kontroli, w zasadzie każdego dzisiejszego programowalnego komputera. Podstawowym problemem, z którym należy się zmierzyć, jest to, że taka „architektura von Neumanna” nie została zaprojektowana do równoległego wykonywania, ale wydajne obliczenia sekwencyjne. Równoległość w takim kontekście uzyskuje się przez powielanie części podstawowych modułów (pamięć, sterowanie, arytmetyka).

Duplikowanie tylko arytmetyki daje instrukcje SIMD, wszystkie ALU współużytkują ten sam licznik programów (PC), a zatem zawsze wykonują tę samą operację równolegle, choć na różnych danych.

Duplikowanie ALU i komputera PC, ale utrzymanie sekwencera instrukcji wewnątrz jednostki sterującej, zapewnia wykonanie poza kolejnością (OoO), które zapewnia pewną równoległość potoku. W tej kategorii masz również bardzo długie słowo instrukcji (VLWI) i techniki przewidywania rozgałęzień. Rzadko jednak widzisz tę kategorię na poziomie oprogramowania.

Nieco dalej jest duplikowanie całego „rdzenia”, ale przy zachowaniu wspólnej pamięci, są to obecnie procesory wielordzeniowe, które zapewniają równoległość zadań (lub wątków). Udostępnianie pamięci w tym kontekście daje bardzo, bardzo trudne i subtelne problemy z współbieżnością . Obliczenia równoległe w bieżącym trybie wielordzeniowym dotyczą zatem całkowicie problemów z synchronizacją / współbieżnością, starannej równowagi wydajności (bez synchronizacji) i pożądanej semantyki (całkowicie zsynchronizowana, semantyka sekwencyjnego wykonywania). Przykładem tego jest PRAM lub bardziej popularny obecnie Cilk ofshoots, taki jak fork / join ( IntelTBB , Java.Utils.Concurrency). Modele CSP i Actor są modelami współbieżności, ale jak wspomniano powyżej, współbieżność i równoległość stają się rozmyte w środowisku pamięci wspólnej. Równoległość nb służy wydajności, a współbieżność pozwala zachować poprawną semantykę.

Powielanie pamięci daje ci albo komputery w sieci, które są zaprogramowane z MPI i jego podobnymi, albo po prostu dziwne architektury inne niż Von Neumann, takie jak procesory sieciowe na chipie (procesor w chmurze, Transputer, Tilera). Modele pamięci, takie jak UMA lub NUMA, starają się zachować iluzję pamięci współdzielonej i mogą istnieć na poziomie oprogramowania lub sprzętu. MPI utrzymuje równoległość na poziomie programu i komunikuje się tylko poprzez przekazywanie komunikatów. Przekazywanie wiadomości jest również używane na poziomie sprzętowym do komunikacji i współbieżności (Transputer).

Druga kategoria to modele przepływu danych . Zostały one zaprojektowane na początku ery komputerów jako sposób na zapisywanie i wykonywanie równoległych obliczeń, unikając projektu von Neumanna. Te przestały być modne (w przypadku przetwarzania równoległego) w latach 80. po tym, jak wydajność sekwencyjna wzrosła wykładniczo. Jednak wiele równoległych systemów programowania, takich jak Google MapReduce, Driada Microsoftu lub Współbieżne kolekcje Intela, są w rzeczywistości modelami obliczeniowymi przepływu danych. W pewnym momencie reprezentują obliczenia jako wykres i wykorzystują je do kierowania wykonaniem.

Określając części modeli, otrzymujesz różne kategorie i semantykę dla modelu przepływu danych. Co ograniczasz kształt wykresu do: DAG (CnC, Driada), drzewa (mapreduce), digraph? Czy istnieje ścisła semantyka synchronizacji ( Luster, programowanie reaktywne]? Czy nie zezwalasz na rekurencję, aby móc mieć harmonogram statyczny (StreaMIT), czy zapewniasz bardziej ekspresyjną moc dzięki dynamicznemu harmonogramowi (Intel CnC)? Czy istnieje ograniczenie liczby krawędzi przychodzących lub wychodzących? Czy semantyka wyzwalania umożliwia odpalenie węzła, gdy dostępny jest podzbiór danych przychodzących? Są krawędziami strumieni danych (przetwarzanie strumieniowe) lub pojedynczymi tokenami danych (statyczne / dynamiczne pojedyncze przypisanie). W przypadku powiązanych prac można rozpocząć od pracy badawczej nad przepływem danych osób takich jak Arvind, K. Kavi, j. Sharp, W. Ackerman, R. Jagannathan itp.

Edycja: Ze względu na kompletność. Powinienem zauważyć, że istnieją również modele napędzane równolegle do redukcji i wzorców . W przypadku strategii redukcji zasadniczo stosuje się redukcję wykresów i ciągów znaków. Haskell w zasadzie stosuje redukcję wykresów, co jest bardzo wydajną strategią w systemie sekwencyjnym pamięci wspólnej. Duplikaty redukcji ciągów działają, ale mają właściwość pamięci prywatnej, dzięki czemu lepiej nadają się do niejawnego zrównoleglenia. Modelami opartymi na wzorach są równoległe języki logiczne, takie jak współbieżne prologowanie. Model aktora jest również modelem opartym na wzorcach, ale z cechami pamięci prywatnej.

PS. Używam terminu „model” szeroko, obejmując abstrakcyjne maszyny zarówno do celów formalnych, jak i programistycznych.

W przypadku architektur przekazujących wiadomości, modelem dość podobnym do BSP, ale łatwiejszym w obsłudze i analizie wydajności zbliżonym do tego, co naprawdę dostajesz na prawdziwej maszynie, jest z pewnością CGM lub Coarse Grained Multicomputer. Został zaproponowany przez Franka Dehne, a znajdziesz wiele ciekawych prac prezentujących algorytmy opracowane w tym kontekście.

CGM pasuje do architektur gruboziarnistych, zakładając procesory p, każdy z pamięcią lokalną O (n / p) i wielkością wejściową n znacznie większą (o rząd wielkości od siebie) niż p, tj. P≪n. Dlatego model mapuje znacznie lepiej niż inne na obecnych architekturach; zostało szeroko zbadane. Model opiera się na następujących założeniach: (i) algorytmy wykonują tak zwane superpoki, które składają się z jednej fazy obliczeń lokalnych i jednej fazy komunikacji między procesorami z synchronizacją barier pośrednich, (ii) wszystkie procesory p mają dostęp do Pamięć lokalna O (n / p), (iii) w każdym superstepie procesor może wysyłać i odbierać co najwyżej elementy O (n / p) i (iv) sieć komunikacyjna między procesorami może być dowolna. W tym modelu algorytm jest oceniany na podstawie czasu obliczeń i liczby rund komunikacji. Chociaż model jest prosty, zapewnia jednak rozsądne przewidywanie faktycznych wyników algorytmów równoległych; w rzeczywistości algorytmy równoległe dla CGM mają zazwyczaj teoretyczną analizę złożoności bardzo zbliżoną do rzeczywistych czasów ustalonych eksperymentalnie podczas ich wdrażania i porównywania.

Parallel External Memory (PEM) to naturalne połączenie pamięci współdzielonej typu PRAM z modelem pamięci zewnętrznej. Koncentruje się na implikacjach prywatnych pamięci podręcznych.

Z tego, co wiem, modele BSP i LogP są obecnie używane do algorytmów rozproszonych. Również od czasu obliczeń na GPU PRAM jako znów stał się popularny, jednak w analizie należy uwzględnić hierarchie pamięci. Możesz sprawdzić model UPMH (hierarchia pamięci Uniform Parallel), który ładnie uzupełnia PRAM.

B. Alpern, L. Carter, E. Feig i T. Selker. Model obliczeń jednolitej hierarchii pamięci. Al Algorytmica, 12: 72–109, 1994. 10.1007 / BF01185206.

Bowen Alpern, Larry Carter i Jeanne Ferrante. Modelowanie komputerów równoległych jako hierarchii pamięci. In In Proc. Modele programowania dla komputerów masowo równoległych, strony 116–123. IEEE Computer Society Press, 1993.

Również w przypadku obliczeń na GPU pojawiła się propozycja teoretycznego modelu obliczeniowego; model K:

Gabriele Capannini, Fabrizio Silvestri i Ranieri Baraglia. Model K: nowy model obliczeniowy dla procesorów strumieniowych. W materiałach 12 Międzynarodowej Konferencji IEEE 2010 w sprawie wysokowydajnych obliczeń i komunikacji, HPCC '10, strony 239–246, Waszyngton, DC, USA, 2010. IEEE Computer Society.

Wreszcie widziałem automaty komórkowe (CA) modelowane jako równoległe komputery, osobiście uważam, że jest to bardzo interesujący temat badawczy. Kto wie, w przyszłości procesory zostaną stworzone w ten sposób, jak małe przestrzenie obliczeniowe. Nie mam na to solidnego odniesienia, możesz zajrzeć do sieci.

Czysto funkcjonalne programy umożliwiają równoległe wykonywanie niezależnych wyrażeń. Dlatego bym je liczył jako równoległe modele obliczeń.

Wolę podejście Bader-Jaja (patrz sekcja 2.1). Modelujesz złożoność jako problem przekazywania wiadomości. Dla każdej wysłanej wiadomości istnieje zarówno zmienna opóźnienie inicjowania komunikacji, jak i zmienna przepustowość.

$t$$u$$m$$p$$t$$u$$m$$p$

wymieniasz konkretnie przetwarzanie w chmurze. nastąpił w ciągu zaledwie kilku lat intensywnej innowacji w tej dziedzinie z Amazon Elastic Compute Cloud, na Google App Engine i różnych narzędzi i ich powiązanych przetwarzania „modeli” koncepcyjne równoległych.

specjalne narzędzia open source obejmują Google Mapreduce , Apache Hadoop i bazy danych NoSQL, które pojawiają się jako nowe, silne, szeroko dostosowane standardy algorytmu równoległego, „najlepsze praktyki” i „wzorce projektowe”. również memcacheD jest coraz częściej wykorzystywany jako rozproszona baza danych w pamięci. przykład tego jest używany na Facebooku opisany w niedawnym artykule [1].

[1] Wiele głównych magazynów kluczy i wartości Berezecki i in

pod innym kątem. wprawdzie niektórzy mogą to uznać za nieco niejasne lub marginesowe, ale istnieją pewne prace nad paralelizacją, w sposób ogólny, algorytmów probabilistycznych, które, jak się twierdzi, w pewien sposób nadają się do paralelizmu.

patrz np. Równoległe obliczenia probabilistyczne na klastrze stacji roboczych Radenski, Vann, Norris:

Algorytmy probabilistyczne są intensywnymi obliczeniowo przybliżonymi metodami rozwiązywania trudnych problemów. Algorytmy probabilistyczne są doskonałymi kandydatami do obliczeń klastrowych, ponieważ wymagają niewielkiej komunikacji i synchronizacji. Możliwe jest określenie wspólnej równoległej struktury sterowania jako ogólnego algorytmu dla probabilistycznych obliczeń klastrowych. Taki ogólny algorytm równoległy można skleić z algorytmami sekwencyjnymi specyficznymi dla domeny w celu uzyskania przybliżonych równoległych rozwiązań dla różnych trudnych problemów. W tym artykule proponujemy ogólny algorytm obliczeń probabilistycznych na klastrze stacji roboczych. Używamy tego ogólnego algorytmu, aby uzyskać określone algorytmy równoległe dla dwóch dyskretnych problemów optymalizacji: problemu plecaka i problemu sprzedawcy podróży.

w przypadku, gdy nie jest jasne, „wspólna równoległa struktura sterowania jako ogólny algorytm”, o której mowa wraz z obliczeniami probabilistycznymi i ogólną konwersją, jest „modelem”.

Można argumentować, że obliczenia probabilistyczne nie są obliczeniami stricte klasycznymi lub Turinga zakończone. więc zauważ, że jest trochę pracy w wiązaniu klasyki z obliczeniami probabilistycznymi, szczególnie w kontekście równoległym, np

Uzasadnienie dotyczące probabilistycznych programów równoległych autorstwa Rao:

Zastosowanie randomizacji w projektowaniu i analizie algorytmów obiecuje proste i wydajne algorytmy do trudnych problemów, z których niektóre mogą nie mieć deterministycznego rozwiązania. Ten wzrost prostoty, wydajności i możliwości rozwiązania powoduje kompromis tradycyjnego pojęcia absolutnej poprawności algorytmów dla pojęcia bardziej ilościowego: poprawności z prawdopodobieństwem między 0 a 1. Dodanie pojęcia równoległości do już nieintuicyjnego Idea randomizacji sprawia, że ​​rozumowanie o równoległych programach probabilistycznych jest tym bardziej krępujące i trudne. W tym artykule zajmujemy się problemem określania i wyprowadzania właściwości probabilistycznych programów równoległych, które zachowują się deterministycznie lub z prawdopodobieństwem 1.

oczywiście obliczenia QM są bardzo podobne do obliczeń probabilistycznych (miły refren, który podkreśla, że ​​jest to pogląd złożonego przez teoretyka teorii złożoności autorstwa Fortnowa ) i istnieje pewna wskazówka, że ​​podejścia te można by rozszerzyć, np. w pracy nad równoległą symulacją QM.

niektórzy uznają to za kontrowersyjne, a nawet zwolennicy tego punktu widzenia będą musieli przyznać się do tego na wczesnych etapach badań, ale w zasadzie obliczenia kwantowe wydają się mieć wiele powiązań z równoległością i obliczeniami równoległymi. referencje są teraz rozproszone, ale wyłaniający się temat może zobaczyć zdeterminowany badacz.

być może najlepszym połączeniem jest algorytm wyszukiwania Groversa, który ostatnio okazał się bardziej ogólny w tym sensie, że nadaje się do przyspieszenia większości problemów NP całkowitych w ogóle [5]. Wydaje się, że algorytm Grovers ma silną analogię / połączenie z równoległymi algorytmami wyszukiwania w bazie danych. najlepsze klasyczne algorytmy szeregowe nie mogą osiągnąć tej samej wydajności, ale co najmniej jeden organ twierdzi ostatnio, że podejścia QM do wyszukiwania w rzeczywistości nie przewyższają równoległych algorytmów klasycznych [1].

Kolejnymi dowodami są schematy, które wyraźnie przyglądają się równoległości w wyszukiwaniu kwantowym, np. [2]. zaproponowano również symulator kwantowy, który opiera się na przetwarzaniu równoległym / rozproszonym [3] [4], a ponieważ schemat dobrze pasuje i prowadzi do wydajnych i możliwych do symulacji symulacji (30 kubitów symulowanych w pozycji odniesienia [3]), ta konwersja z pewnością nie jest jedynie zbiegiem okoliczności i wskazuje na głębszy pomost między równoległymi obliczeniami klasycznymi a obliczeniami QM, ale prawdopodobnie dotychczas nie został odkryty.

[1] Czy wyszukiwanie kwantowe jest praktyczne? przez Viamontes i in

[2] Dokładne wyszukiwanie kwantowe za pomocą równoległych schematów jednolitej dyskryminacji Wu / Dian

[3] Symulator równoległy ogólnego zastosowania do obliczeń kwantowych , Niwa, Matsumoto, Imai.

[4] wydajne rozproszone obliczenia kwantowe autorstwa Beals i in. 2012

[5] Rozwiązywanie całkowitych problemów NP z wyszukiwaniem kwantowym przez Furer 2008