Model paralelního programování - Parallel programming model

v výpočetní, a model paralelního programování je abstrakce z paralelní počítač architektura, se kterou je vhodné vyjádřit algoritmy a jejich složení v programy. Hodnotu programovacího modelu lze posoudit podle jeho všeobecnost: jak dobře lze vyjádřit řadu různých problémů pro různé architektury a jejich výkon: jak efektivně mohou kompilované programy vykonávat.[1] Implementace modelu paralelního programování může mít formu a knihovna vyvolané z sekvenční jazyk, jako rozšíření stávajícího jazyka nebo jako zcela nový jazyk.

Konsenzus ohledně konkrétního programovacího modelu je důležitý, protože vede k tomu, že se různé paralelní počítače vytvářejí s podporou modelu, čímž se usnadňuje přenosnost softwaru. V tomto smyslu se programovací modely označují jako přemostění mezi hardwarem a softwarem.[2]

Klasifikace modelů paralelního programování

Klasifikace modelů paralelního programování lze obecně rozdělit do dvou oblastí: procesní interakce a dekompozice problému.[3][4][5]

Procesní interakce

Interakce procesů souvisí s mechanismy, kterými jsou paralelní procesy schopné navzájem komunikovat. Nejběžnějšími formami interakce jsou sdílená paměť a předávání zpráv, ale interakce může být také implicitní (pro programátora neviditelná).

Sdílená paměť

Hlavní článek: Sdílená paměť (komunikace mezi procesy)

Sdílená paměť je účinným prostředkem předávání dat mezi procesy. V modelu sdílené paměti sdílejí paralelní procesy globální adresní prostor, který asynchronně čtou a zapisují. Asynchronní souběžný přístup může vést k podmínky závodu a mechanismy jako zámky, semafory a monitory lze se jim vyhnout. Konvenční vícejádrové procesory přímo podporuje sdílenou paměť, kterou mnoho paralelních programovacích jazyků a knihoven, jako je Cilk, OpenMP a Navlékání stavebních bloků, jsou určeny k využití.

Předávání zpráv

Hlavní článek: Předávání zpráv

V modelu předávání zpráv si paralelní procesy vyměňují data prostřednictvím předávání zpráv jeden druhému. Tato komunikace může být asynchronní, kde lze odeslat zprávu dříve, než je připraven příjemce, nebo synchronní, kde musí být připraven příjemce. The Komunikace postupných procesů (CSP) formalizace předávání zpráv využívá synchronní komunikační kanály k propojení procesů a vedlo k důležitým jazykům, jako je Occam, Předpeklí a Jít. Naproti tomu herec model používá asynchronní předávání zpráv a používá se při navrhování jazyků jako D, Scala a SALSA.

Implicitní interakce

Hlavní článek: Implicitní paralelismus

V implicitním modelu není programátorovi viditelná žádná interakce procesu a místo toho za jeho provedení odpovídá kompilátor a / nebo běhový modul. Dva příklady implicitního paralelismu jsou s jazyky specifické pro doménu kde je předepsána souběžnost v rámci operací na vysoké úrovni, a s funkční programovací jazyky protože absence vedlejší efekty umožňuje paralelní provádění nezávislých funkcí.[6] Tento druh paralelismu je však obtížné zvládnout[7] a funkční jazyky jako Souběžný Haskell a Souběžné ML poskytují funkce pro správu paralelismu explicitně a správně.

Rozklad problému

Paralelní program se skládá ze současně prováděných procesů. Problémový rozklad souvisí se způsobem, jakým jsou formulovány základní procesy.[8][9]

Paralelnost úkolů

Hlavní článek: Paralelnost úkolů

Model paralelního úkolu se zaměřuje na procesy nebo vlákna provádění. Tyto procesy se často budou chovat odlišně, což zdůrazňuje potřebu komunikace. Paralelismus úkolů je přirozený způsob vyjádření komunikace předávající zprávy. v Flynnova taxonomie, paralelnost úkolů je obvykle klasifikována jako MIMD /MPMD nebo MISD.

Datový paralelismus

Hlavní článek: Datový paralelismus

Datově paralelní model se zaměřuje na provádění operací na datové sadě, obvykle na pravidelně strukturovaném poli. Sada úkolů bude fungovat na těchto datech, ale nezávisle na disjunktních oddílech. v Flynnova taxonomie, datový paralelismus je obvykle klasifikován jako MIMD /SPMD nebo SIMD.

Implicitní paralelismus

Hlavní článek: Implicitní paralelismus

Stejně jako u implicitní interakce procesů implicitní model paralelismu neodhalí nic programátorovi, protože je zodpovědný kompilátor, runtime nebo hardware. Například v kompilátorech automatická paralelizace je proces převodu sekvenčního kódu na paralelní kód a v počítačové architektuře, superskalární provedení je mechanismus, kterým paralelismus na úrovni instrukcí je využíván k paralelnímu provádění operací.

Terminologie

Modely paralelního programování úzce souvisí s modely výpočtu. Model paralelního výpočtu je abstrakce používá se k analýze nákladů na výpočetní procesy, ale nemusí to nutně být praktické, protože je lze efektivně implementovat do hardwaru a / nebo softwaru. Naproti tomu programovací model konkrétně implikuje praktické úvahy o implementaci hardwaru a softwaru.[10]

Paralelní programovací jazyk může být založen na jednom nebo na kombinaci programovacích modelů. Například, Vysoce výkonný Fortran je založen na interakcích sdílené paměti a datově paralelním rozkladu problémů a Jít poskytuje mechanismus pro interakci sdílené paměti a předávání zpráv.

Příklad modelů paralelního programování

názevTřída interakceTřída rozkladuUkázkové implementace
Herecký modelAsynchronní předávání zprávÚkolD, Erlang, Scala, SALSA
Hromadné synchronní paralelníSdílená paměťÚkolApache Giraph, Apache Hama, BSPlib
Komunikace postupných procesůSynchronní předávání zprávÚkolAda, Occam, VerilogCSP, Jít
ObvodyPředávání zprávÚkolVerilog, VHDL
Datový tokPředávání zprávÚkolLesk, TensorFlow, Apache Flink
FunkčníPředávání zprávÚkolSouběžný Haskell, Souběžné ML
Stroj LogPSynchronní předávání zprávNespecifikovánoŽádný
Paralelní stroj s náhodným přístupemSdílená paměťDataCilk, CUDA, OpenMP, Navlékání stavebních bloků, XMTC

Viz také

Reference

  1. ^ Skillicorn, David B., „Modely pro praktický paralelní výpočet“, International Journal of Parallel Programming, 20.2 133–158 (1991), https://www.ida.liu.se/~chrke55/papers/modelsurvey.pdf
  2. ^ Leslie G. Valiant, „Překlenovací model pro paralelní výpočet“, Komunikace ACM, svazek 33, číslo 8, srpen 1990, strany 103–111.
  3. ^ John E. Savage, Models of Computation: Exploring the Power of Computing, 2008, kapitola 7 (Parallel Computation), http://cs.brown.edu/~jes/book/ Archivováno 2016-11-05 na Wayback Machine
  4. ^ Ian Foster, Navrhování a budování paralelních programů, 1995, Oddíl 1.3, „Model paralelního programování“, http://www.mcs.anl.gov/~itf/dbpp/text/node9.html
  5. ^ Blaise Barney, Úvod do paralelních výpočtů, „Modely“, 2015, Lawrence Livermore National Laboratory,https://computing.llnl.gov/tutorials/parallel_comp/#Models
  6. ^ Hammond, Kevine. Paralelní funkční programování: Úvod. In International Symposium on Parallel Symbolic Computation, str. 46. ​​1994.
  7. ^ McBurney, D. L. a M. Ronan Sleep. „Transputerové experimenty s architekturou ZAPP.“ PARLE Parallel Architectures and Languages ​​Europe. Springer Berlin Heidelberg, 1987.
  8. ^ Ian Foster, Navrhování a budování paralelních programů, 1995, Oddíl 2.2, „Rozdělení disku“, http://www.mcs.anl.gov/~itf/dbpp/text/node16.html
  9. ^ Blaise Barney, Introduction to Parallel Computing, "Partitioning", 2015, Lawrence Livermore National Laboratory, https://computing.llnl.gov/tutorials/parallel_comp/#DesignPartitioning
  10. ^ Skillicorn, David B. a Domenico Talia, Modely a jazyky pro paralelní výpočet, ACM Computing Surveys, 30.2 123–169 (1998), https://www.cs.utexas.edu/users/browne/CS392Cf2000/papers/ModelsOfParallelComputation-Skillicorn.pdf

Další čtení

  • Blaise Barney, Úvod do paralelního výpočtu, Lawrence Livermore National Laboratory
  • Murray I. Cole., Algoritmické kostry: Strukturované řízení paralelních výpočtů (PDF), University of Glasgow
  • J. Darlinton; M. Ghanem; H. W. To (1993), "Strukturované paralelní programování", V programovacích modelech pro masivně paralelní počítače. IEEE Computer Society Press: 160–169, doi:10.1109 / PMMP.1993.315543, ISBN  0-8186-4900-3, S2CID  15265646
  • Ian Foster, Navrhování a budování paralelních programů, Argonne National Laboratory