Oparte na zadaniach biblioteki równoległe z pamięcią współdzieloną w Scientific Computing

10

W ostatnich latach pojawiło się kilka projektów bibliotek / oprogramowania, które oferują jakąś formę równoległego zarządzania pamięcią współużytkowaną opartą na danych ogólnych.

Główną ideą jest to, że zamiast pisać kod z jawnym wątkiem, programiści implementują swoje algorytmy jako zadania współzależne, które są następnie dynamicznie planowane przez oprogramowanie pośredniczące ogólnego przeznaczenia na maszynie z pamięcią współużytkowaną.

Przykładami takich bibliotek są:

  • QUARK : Pierwotnie zaprojektowany dla biblioteki algebry liniowej równoległej MAGMA , wydaje się być również używany do równoległej szybkiej metody wielobiegunowej .

  • Cilk : Pierwotnie projekt oparty na MIT, teraz obsługiwany przez Intel, wdrożony jako rozszerzenia języka / kompilatora do C, używany w oprogramowaniu komputerowym szachów Cilkchess i eksperymentalnie w FFTW .

  • Superskalarny SMP : Opracowany w Barcelona Supercomputing Center, pod wieloma względami podobny do Cilk, w oparciu o #pragmarozszerzenia.

  • StarPU : Podobne oparte na bibliotece „kodeki”, które można kompilować i planować na kilku różnych architekturach, w tym na GPU.

  • Zadania OpenMP: Od wersji 3.0 OpenMP wprowadził „zadania”, które można planować asynchronicznie (patrz rozdział 2.7 specyfikacji).

  • Elementy składowe wątków Intela : Używa klas C ++ do tworzenia i uruchamiania zadań asynchronicznych, patrz sekcja 11 samouczka.

  • OpenCL : obsługuje równoległość zadaniową na wielu rdzeniach.

Chociaż istnieje wiele literatury opisującej wewnętrzne działanie tych bibliotek / rozszerzeń języka i ich zastosowania do konkretnych problemów, natknąłem się na bardzo niewiele przykładów ich zastosowania w praktyce w naukowych aplikacjach komputerowych.

Oto pytanie: czy ktoś wie o naukowych kodach obliczeniowych wykorzystujących którąkolwiek z tych bibliotek / rozszerzeń językowych lub podobnych, do równoległości pamięci wspólnej?

Pedro
źródło
Czy szukasz paralelizmu zadaniowego? Czy istnieje powód, dla którego opuściłeś OpenCL i Intel TBB? Muszę przyznać, że nie mogę powiedzieć dokładnie, czego tu szukasz.
Aron Ahmadia,
1
@AronAhmadia: Niewiedza, głównie ... :) Dodałem TBB i OpenCL do listy, ale pytanie pozostaje takie samo: czy te, tj. Ich komponenty zadaniowe, zostały użyte w jakimkolwiek znaczącym oprogramowaniu dla nauki przetwarzanie danych?
Pedro
Co sądzimy o przekształceniu tego pytania i jego odpowiedzi w wiki społeczności w porównaniu z próbą rozszerzenia go?
Aron Ahmadia
@AronAhmadia: Trochę się martwię, że jeśli opuszczę format pytania, szybko przerodzi się to w długie dyskusje na temat zalet / wad programowania opartego na zadaniach i / lub pamięci wspólnej. Byłbym jednak za tym, aby zmienić go po otrzymaniu kilku odpowiedzi.
Pedro
Tytuł nie jest odpowiedni. To pytanie dotyczy równoległości zadań, a nie pamięci współdzielonej.
Jeff

Odpowiedzi:

8

deal.II korzysta z wątków w całej bibliotece i ogólnie jesteśmy z tego całkiem zadowoleni. Przyjrzeliśmy się kilku alternatywom, w szczególności OpenMP, ponieważ wydaje się, że wszyscy używają go do prostszych kodów, ale ich brakuje. W szczególności OpenMP ma tę ogromną wadę, że jego model zadań nie pozwala uzyskać uchwytu dla uruchomionego zadania, w związku z czym trudno jest uzyskać dostęp do stanu zadania (np. Czekać na jego zakończenie) lub zwrócić wartości funkcje uruchamiane na osobnym zadaniu. OpenMP jest przede wszystkim dobry do zrównoleglania najbardziej wewnętrznych pętli, ale wydajność równoległą zyskuje się przez równoległe równoległe, najbardziej złożone pętle, a OpenMP nie jest do tego narzędziem, podczas gdy TBB są do tego całkiem dobre.

Wolfgang Bangerth
źródło
Dzięki za zwrócenie na to uwagi, nie patrzyłem na ofertę. II! Czy jest jakaś publikacja lub dokumentacja, w której szczegółowo opisano wykorzystanie TBB przez deal.II?
Pedro
Brak publikacji, ale może to pomóc: dealii.org/developer/doxygen/deal.II/group__threads.html
Wolfgang Bangerth
4

Moim zdaniem systemy te okazały się względnie nieudane głównie z następujących powodów.

  • Naiwna perspektywa, w której obliczenia równoległe dotyczą bardziej równoległego obliczania (np. Klap), niż ujawnianie lokalizacji pamięci i usuwanie punktów synchronizacji. Chociaż niektóre problemy, takie jak algorytmy gęstej macierzy, są nadal ograniczone przez FP, to pojawia się tylko po starannym rozważeniu podsystemu pamięci i większość jąder obliczeniowych (szczególnie w świecie PDE) jest bardziej wrażliwa na pamięć. Kolejki robocze mają tendencję do wymiany lokalizacji pamięci w celu uzyskania lepszego naiwnego wyważenia klap i większej liczby operacji w pamięci atomowej (z powodu synchronizacji w kolejce).
  • Poleganie na nadmiernym rozkładzie w celu dynamicznego równoważenia obciążenia kosztem silnej skalowalności. Zasadniczo zadania mają nakładające się zależności danych (wartości duchów). Gdy rozmiar wnętrza kurczy się, stosunek ducha do wnętrza rośnie. Nawet jeśli nie oznacza to zbędnej pracy, oznacza to zwiększony ruch pamięci. Znaczące redukcje wymagań dotyczących przepustowości pamięci można uzyskać dzięki podejściom takim jak kooperacyjne pobieranie wstępne, dzięki któremu wiele wątków współużytkuje pamięć podręczną L1 lub L2 przez wstępne pobieranie oprogramowania dla swojego sąsiada (co pośrednio utrzymuje grupę wątków w przybliżeniu spójną). Jest to dokładnie odwrotność nadmiernego rozkładu.
  • Nieprzewidywalna wydajność, głównie z powodu powyższych problemów związanych z pamięcią.
  • Brak komponentów przyjaznych dla biblioteki. Można to prawie podsumować jako brak analogu, MPI_Commktóry umożliwia różnym bibliotekom wykonywanie bogatych operacji bez kolizji, a także przekazywanie kontekstu między bibliotekami i odzyskiwanie niezbędnych atrybutów. Abstrakcja zapewniana przez „komunikator” jest ważna dla kompozycji biblioteki, niezależnie od tego, czy używana jest pamięć współdzielona czy rozproszona.
Jed Brown
źródło
Być może źle rozumiem twoją odpowiedź, ale pierwszy punkt jest dokładnie przeciwny do tego, co Buttari, Kurzak, Dongarra i inni pokazali za pomocą MAGMA, opartej na zadaniach biblioteki współdzielonej pamięci dla gęstej algebry liniowej ... Ponadto, w twoim drugim punkcie odnosisz się do nakładających się danych, tj. wartości widm i stosunku powierzchni do objętości, ale są one zaprzeczeniem schematów dekompozycji domen pamięci rozproszonej. Sam pracuję z takimi metodami dla kodów opartych na cząsteczkach i uzyskuję znacznie lepszą wydajność niż równoległe implementacje oparte na MPI.
Pedro
W każdym razie pytanie było inne ... Czy znasz jakieś naukowe projekty oprogramowania komputerowego wykorzystujące te podejścia?
Pedro
1. Istnieje kilka projektów wykorzystujących te systemy, ale nie sądzę, aby podejście to można uznać za „udane”. 2. Zależności nadal pokrywają się w pamięci współdzielonej. Spójrz, w jaki sposób tcmalloc lub jądro Linuksa czyni wątki bardziej niezależnymi, aby uniknąć wąskich gardeł, takich jak synchronizacja za pomocą atomów. Współdzielona przestrzeń adresowa nie oznacza, że ​​powinieneś działać tak, jakbyś miał jednolitą pamięć lub że uważałeś atomy za niedrogie.
Jed Brown,
3. Nie wiem, jakie „uczciwe porównanie” zamierzasz przytoczyć, ale PLASMA otrzymuje tylko około 25% szczytowego FPU (np. Slajd 5 hpcgarage.org/cscads2012/Luszczek-UTK-PowerTools.pdf ), który byłby niepoprawnie źle dla tej samej operacji w pamięci rozproszonej, gdzie można oczekiwać co najmniej 70% wartości szczytowej. Gęsta algebra liniowa jest przypadkiem związanym z FPU, który konkretnie wymieniłem jako możliwy wyjątek, ale pomimo ogromnych rozmiarów matrycy, PLASMA jest oczywiście daleki od bycia związanym z FPU.
Jed Brown
Pedro, większość fizyki ma komponent dalekiego zasięgu, więc cząsteczki są połączone z aktualizacją, która podlega powyższemu efektowi powierzchni do rozpuszczenia (PPPM, cząstka wiru itp.)
Matt Knepley