Wikipédia

„Párhuzamos számítástechnika” változatai közötti eltérés

Laptörténet interaktív böngészése
[ellenőrzött változat][ellenőrzött változat]
← Régebbi szerkesztésÚjabb szerkesztés →
Tartalom törölve Tartalom hozzáadva
VizuálisWikiszöveges
aNincs szerkesztési összefoglaló
aNincs szerkesztési összefoglaló
29. sor:
[[Fájl:AmdahlsLaw.svg|jobbra|bélyegkép|300x300px|[[Amdahl-törvény|Amdahl törvényének]] grafikus ábrázolása. A program párhuzamosítástól való felgyorsítását korlátozza az, hogy a program mekkora részét lehet párhuzamosítani. Például ha a program 90%-a párhuzamosítható, akkor az elméleti maximális sebesség a párhuzamos számítás használatával tízszeres lesz, függetlenül attól, hogy hány processzort használunk.]]
 
[[Fájl:Optimizing-different-parts.svg|bélyegkép|300x300px|Tegyük fel, hogy egy feladatnak két független része van: ''A'' és ''B''. A ''B'' rész a teljes számítás idejének körülbelül 25%-át veszi igénybe. Nagyon kemény munkával előfordulhat, hogy ez a rész ötször gyorsabb lesz, de ez csak kicsit csökkenti a teljes számításhoz szükséges időt. Ezzel szemben lehet, kevesebb munkát kell elvégezni, hogy az ''A'' rész kétszer gyorsabb legyen. Ez sokkal gyorsabbá teszi a számítást, mint a ''B'' rész optimalizálása, annak ellenére, hogy a ''B'' rész gyorsulása aránylag nagyobb (ötszörös a kétszeressel szemben).]]
 
Optimális esetben a párhuzamosítástól való [[Gyorsulás (számítástechnika)|gyorsulás]] lineáris lenne – a feldolgozóelemek számának megkétszerezésével a futási időt a felére, második alkalommal történő megkétszerezésére pedig ismét a felére kellene csökkenteni. Azonban nagyon kevés párhuzamos algoritmus éri el az optimális gyorsulást. Legtöbbjüknél csaknem lineáris sebességnövekedés tapasztalható kisszámú feldolgozóelem esetében, amely állandó értékké válik nagyszámú feldolgozóelem esetén.
47. sor:
[[Fájl:Gustafson.png|jobbra|bélyegkép|300x300px|[[Gustafson-törvény|Gustafson törvényének]] grafikus ábrázolása]]
 
Amdahl törvénye csak azokra az esetekre vonatkozik, amikor a probléma nagysága rögzítve van. A gyakorlatban, mivel egyre több számítási erőforrás válik elérhetővé, hajlamosak nagyobb problémákhoz (nagyobb adatkészletekhez) szokni, és a párhuzamosítható részben eltöltött idő gyakran sokkal gyorsabban növekszik, mint a benne rejlő sorozatmunka.<ref>{{cite book |title=Structured Parallel Programming: Patterns for Efficient Computation |year=2013 |publisher=Elsevier |pages=61 |author1=Michael McCool |author2=James Reinders |author3=Arch Robison}}</ref> Ebben az esetben [[Gustafson-törvény|Gustafson törvénye]] kevésbé pesszimista, és reálisabb értékelést ad a párhuzamos teljesítményről:<ref>{{cite journal |last=Gustafson |first=John L. |title=Reevaluating Amdahl's law |journal=Communications of the ACM |date=May 1988 |volume=31 |issue=5 |pages=532–533 |doi=10.1145/42411.42415 |url=http://www.scl.ameslab.gov/Publications/Gus/AmdahlsLaw/Amdahls.html |url-status=dead |archiveurl=https://web.archive.org/web/20070927040654/http://www.scl.ameslab.gov/Publications/Gus/AmdahlsLaw/Amdahls.html |archivedate=2007-09-27 |citeseerx=10.1.1.509.6892 |s2cid=33937392}}</ref>
 
: <math>S_\text{latency}(s) = 1 - p + sp.</math>
55. sor:
=== Függőségek ===
 
Az [[adatfüggőség]]ek megértése alapvető fontosságú a [[párhuzamos algoritmus]]ok megvalósításában. Egyik program sem futhat gyorsabban, mint a függő számítások leghosszabb lánca (úgynevezett [[Kritikusút-módszer|kritikus út]]), mivel a számításokat, amelyek függnek a lánc előzetes számításától, sorrendben kell végrehajtani. A legtöbb algoritmus azonban nem csupán egy hosszú függő számítási láncból áll; általában vannak lehetőségek független számítások párhuzamos végrehajtására.
 
Legyen <math>P_i</math> és <math>P_j</math> két programszegmens. Bernstein feltételei<ref>{{cite journal |last=Bernstein |first=A. J. |title=Analysis of Programs for Parallel Processing |journal=IEEE Transactions on Electronic Computers |date=1 October 1966 |volume=EC-15 |issue=5 |pages=757–763 |doi=10.1109/PGEC.1966.264565}}</ref> leírják, mikor a kettő független és párhuzamosan végrehajtható. <math>P_i</math> számára legyen <math>I_i</math> az összes bemeneti és <math>O_i</math> a kimeneti változó, és ugyanígy a <math>P_j</math> esetében. <math>P_i</math> és <math>P_j</math> függetlenek, ha teljesülnek a következők:
140. sor:
A párhuzamos programozási nyelveknek és a párhuzamos számítógépeknek rendelkezniük kell [[konzisztenciamodell]]el (más néven memóriamodellel). A konzisztenciamodell meghatározza a [[Memória (számítástechnika)|számítógépes memóriában]] végrehajtott műveleteket és az eredmények előállításának szabályait.
 
Az egyik első konzisztenciamodell [[Leslie Lamport]] [[szekvenciális konzisztencia]]modellje volt. A szekvenciális konzisztencia egy párhuzamos program olyan tulajdonsága, hogy annak párhuzamos végrehajtása ugyanazokat az eredményeket adja, mint a szekvenciális végrehajtása. Pontosabban, egy program szekvenciálisan konzisztens, ha „bármely végrehajtás eredménye megegyezik, amennyiben az összes processzor műveletei tetszőleges sorrendben kerülnek végrehajtásra, és az egyes processzorok műveletei ebben a sorrendben jelennek meg a program által meghatározott sorrendben”.<ref>{{cite journal |last=Lamport |first=Leslie |title=How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs |journal=IEEE Transactions on Computers |date=1 September 1979 |volume=C-28 |issue=9 |pages=690–691 |doi=10.1109/TC.1979.1675439 |s2cid=5679366}}</ref>
 
A [[tranzakciós memória]] a konzisztenciamodell általános típusa. A tranzakciós memória kölcsönveszi az [[adatbázis]]-elméletből az [[Atomic commit|atomi tranzakciók]] fogalmát, és alkalmazza azokat a memóriaelérésekre.
160. sor:
=== Bitszintű párhuzamosság ===
 
A [[VLSI]] ''(Very Large Scale Integration)'' számítógépes chipgyártási technológiának az 1970-es években történő megjelenéséig, mintegy 1986-ig, a számítógép-architektúra felgyorsítását a [[Szó (számítástechnika)|számítógépes szó]] méretének megduplázása vezette – az az információmennyiség, amelyet a processzor ciklusonként módosíthat.<ref>{{cite book |last=Singh |first=David Culler; J.P. |title=Parallel computer architecture |edition=[Nachdr.] |year=1997 |publisher=Morgan Kaufmann Publ. |location=San Francisco |isbn=978-1-55860-343-1 |page=15}}</ref> A szóméret növelése csökkenti a processzor által végrehajtott műveletek számát olyan változók módosításakor, amelyek mérete meghaladja a szó hosszát. Például ha egy [[8 bites architektúra|8 bites]] processzornak két [[16 bites architektúra|16 bites]] [[Egész számok|egész számot]] kell összeadnia, akkor a processzornak először hozzá kell adnia 8 alacsonyabb rendű bitet minden egyes egészből a szokásos összeadási utasítás felhasználásával, majd hozzá kell adnia 8 magasabb rendű bitet egy add-with-carry utasítás segítségével és a [[átvitelbit]]et az alacsonyabb rendű összeadásból; így egy 8 bites processzornak két utasításra van szüksége egyetlen művelet végrehajtásához, amire egy 16 bites processzor egyetlen utasítással is képes lenne.
 
A [[4 bites architektúra|4 bites]] mikroprocesszorokról történelmileg 8, 16, majd 32 bites mikroprocesszorokra váltottak. Ez a tendencia általánosságban véget ért a 32 bites processzorok bevezetésével, amely két évtizede az általános célú számítástechnika szabványa. Csak a 2000-es évek elején, az [[x86-64]]-es architektúrák megjelenésével váltak a [[64 bites architektúra|64 bites]] processzorok köznapivá.
190. sor:
=== Memória és kommunikáció ===
 
A párhuzamos számítógép főmemóriája vagy [[Közös memóriahasználat|közös memória]] (az összes feldolgozóelem között megosztva egyetlen [[címtér]]ben), vagy [[Elosztott memóriahasználat|elosztott memória]] (amelyben minden feldolgozóelemnek megvan a saját helyi címtere).'''<ref name="PH713">Patterson and Hennessy, p.&nbsp;713.</ref>''' Az elosztott memória arra a tényre utal, hogy a memória logikailag van elosztva, de gyakran azt jelenti, hogy fizikailag is eloszlik. Az [[osztott közös memória]] és a [[memóriavirtualizáció]] kombinálja a két megközelítést, ahol a feldolgozóelemnek saját helyi memóriája van, és a memóriahoz nem helyi processzorok férhetnek hozzá. A helyi memória elérése általában gyorsabb, mint a nem helyi memória elérése. A [[szuperszámítógép]]eken az osztott közös memóriaterület a programozási modell segítségével, például [[osztott globális címtér]] használatával valósítható meg. Ez a modell lehetővé teszi az egyik számítási csomóponton lévő folyamatok számára, hogy átlátható módon hozzáférjenek egy másik számítási csomópont távoli memóriájához. Az összes számítási csomópont nagy sebességű összeköttetésen keresztül, például az [[InfiniBand]] segítségével egy külső közösmemória-rendszerhez is csatlakozik. Ezt a külső közösmemória-rendszert [[burst puffer]]nek nevezik, amely általában [[nem felejtő memória]] tömbjeiből épül fel, fizikailag elosztva több bemeneti/kimeneti csomópont között.
 
[[Fájl:Numa.svg|jobbra|bélyegkép|400x400px|A [[Non-uniform memory access|nem egységes memória-hozzáférésű]] (NUMA) architektúra logikai nézete. Az egyik könyvtárban lévő processzorok kevesebb késleltetéssel férhetnek hozzá a könyvtár memóriájához, mint a másik könyvtár memóriájához.]]
 
Azokat a számítógép-architektúrákat, amelyekben a főmemória minden eleméhez azonos [[Memóriakésleltetés|késleltetéssel]] és [[sávszélesség]]gel lehet hozzáférni, [[Uniform memory access|egységes memória-hozzáférésű]] (UMA) rendszereknek nevezzük. Általában ezt csak egy [[Közös memóriahasználat|közösmemória]]-rendszerrel lehet elérni, amelyben a memória fizikailag nincs elosztva. Azt a rendszert, amely nem rendelkezik ezzel a tulajdonsággal, [[Non-uniform memory access|nem egységes memória-hozzáférésű]] (NUMA) architektúrának nevezik. Az elosztottmemória-rendszerek nem egységes memória-hozzáféréssel rendelkeznek.
 
A számítógépes rendszerek [[gyorsítótár]]akat használnak – a processzor közelében található kis és gyors memóriákat, amelyek ideiglenes memóriaértékeket tárolnak (fizikai és logikai értelemben is egyaránt közel vannak). A párhuzamos számítógépes rendszereknek nehézségeik vannak olyan gyorsítótárakkal, amelyek ugyanazt az értéket egynél több helyen tárolhatják, a program helytelen végrehajtásának lehetőségével. Ezeknek a számítógépeknek [[Gyorsítótár-koherencia|gyorsítótárkoherencia]]-rendszerre van szükségük, amely nyomon követi a gyorsítótárazott értékeket, és stratégiailag megtisztítja azokat, garantálva ezzel a program helyes végrehajtását. A [[Bus snooping|buszfigyelés]] az egyik leggyakoribb módszer annak nyomon követésére, hogy mely értékekhez férnek hozzá (és ezért meg kell tisztítani). Nagy teljesítményű gyorsítótárkoherencia-rendszerek tervezése nagyon nehéz probléma a számítógép-architektúrában. Ennek eredményeként a közös memória számítógép-architektúrái nem olyan nagy léptékűek, mint az elosztottmemória-rendszerek.<ref name="PH713" />
 
A processzor–processzor és a processzor–memória kommunikációt sokféle módon megvalósíthatjuk a hardverben, többek között közös (multiportált vagy [[Multiplexelés|multiplexelt]]) memória, [[Crossbar switch|keresztkapcsoló]], megosztott [[Busz (informatika)|busz]] vagy összekapcsolt hálózat révén számos [[Hálózati topológia|topológiával]], beleértve a [[Csillagtopológia|csillagot]], [[Gyűrűtopológia|gyűrűt]], [[Fa (gráfelmélet)|fát]], [[Hiperkockagráf|hiperkockát]], kövér hiperkockát (egy csomóponton egynél több processzort tartalmazó hiperkocka) vagy [[Mesh networking|n dimenziós hálót]].
236. sor:
[[Fájl:BlueGeneL_cabinet.jpg|jobbra|bélyegkép|Egy szekrény az [[IBM]] [[IBM Blue Gene|Blue Gene/L]] tömegesen párhuzamos [[szuperszámítógép]]éből]]
 
A tömegesen párhuzamos processzor (MPP) egyetlen számítógép sok hálózati processzorral. Az MPP-k ugyanolyan tulajdonságokkal rendelkeznek mint a fürtök, de speciális összekapcsolási hálózatokkal rendelkeznek (míg a fürtök kereskedelmi forgalomban kapható hardvert használnak a hálózathoz). Az MPP-k általában nagyobbak is mint a fürtök, jellemzően „sokkal több”, mint 100 processzor.<ref>Hennessy and Patterson, p.&nbsp;537.</ref> Egy MPP-ben „minden processzor tartalmazza a saját memóriáját, valamint az operációs rendszer és az alkalmazás másolatát. Minden alrendszer nagysebességű összeköttetésen keresztül kommunikál a többiekkel.”<ref>[https://www.pcmag.com/encyclopedia_term/0,,t=mpp&i=47310,00.asp MPP Definition.] ''PC Magazine''. Retrieved on November 7, 2007.</ref>
 
A TOP500 rangsor szerint 2009 júniusában a világon az ötödik leggyorsabb [[szuperszámítógép]] az [[IBM]] [[IBM Blue Gene|Blue Gene/L]] volt, mely egy MPP.
274. sor:
Számos [[alkalmazásspecifikus integrált áramkör]]i (ASIC) megközelítést dolgoztak ki a párhuzamos alkalmazások kezelésére.<ref>Maslennikov, Oleg (2002). [[doi:10.1007/3-540-48086-2_30|„Systematic Generation of Executing Programs for Processor Elements in Parallel ASIC or FPGA-Based Systems and Their Transformation into VHDL-Descriptions of Processor Element Control Units”]] ''Lecture Notes in Computer Science'', '''2328/2002:''' p.&nbsp;272.</ref><ref>{{cite journal |last=Shimokawa |first=Y. |author2=Fuwa, Y. |author3=Aramaki, N. |title=A parallel ASIC VLSI neurocomputer for a large number of neurons and billion connections per second speed |journal=International Joint Conference on Neural Networks |date=18–21 November 1991 |volume=3 |pages=2162–2167 |doi=10.1109/IJCNN.1991.170708 |isbn=978-0-7803-0227-3 |s2cid=61094111}}</ref><ref>{{cite journal |last=Acken |first=Kevin P. |author2=Irwin, Mary Jane |author3=Owens, Robert M. |title=A Parallel ASIC Architecture for Efficient Fractal Image Coding |journal=The Journal of VLSI Signal Processing |date=July 1998 |volume=19 |issue=2 |pages=97–113 |doi=10.1023/A:1008005616596 |s2cid=2976028}}</ref>
 
Mivel az ASIC (definíció szerint) egy adott alkalmazásra jellemző, ezért teljes mértékben optimalizálható az adott alkalmazás számára. Ennek eredményeként egy adott alkalmazás esetén az ASIC általában jobb, mint egy általános célú számítógép. Az ASIC-eket azonban [[Fotolitográfia|UV fotolitográfia]] hozza létre. Ehhez a folyamathoz maszkkészlet szükséges, amely rendkívül költséges lehet. Egy maszkkészlet több mint egymillió dollárba kerülhet.<ref>Kahng, Andrew B. (June 21, 2004) [http://www.future-fab.com/documents.asp?grID=353&d_ID=2596 Scoping the Problem of DFM in the Semiconductor Industry] {{webarchive |url=https://web.archive.org/web/20080131221732/http://www.future-fab.com/documents.asp?grID=353&d_ID=2596 |date=2008-01-31}} University of California, San Diego. „A gyártás jövőbeli tervezésének (DFM) csökkentenie kell a tervezési költséget [nem megtérülő költség], és közvetlenül foglalkoznia kell a gyártás – a maszkkészlet és a szondakártya – költségeivel [nem megtérülő költségek], amely jóval meghaladja az egymillió dollárt 90 nm esetén és jelentős gátat szab a félvezető-alapú innovációnak.”</ref> (Minél kisebbek a chiphez szükséges tranzisztorok, annál drágább lesz a maszk.) Eközben az általános célú számítástechnika teljesítményének növekedése az idő múlásával (ahogyan azt [[Moore-törvény|Moore törvénye]] leírja) hajlamos arra, hogy ezeket az előnyöket csak egy vagy két chipgeneráció alatt törölje el.<ref name="DAmour" /> A magas kezdeti költség és a Moore törvénye által vezérelt általános célú számítástechnika túllépésének tendenciája az ASIC-eket a legtöbb párhuzamos számítástechnikai alkalmazás számára megvalósíthatatlanná tette. Néhányat azonban építettek. Példa erre a PFLOPS [[RIKEN MDGRAPE-3]] gépe, amely egyedi ASIC-eket használ [[molekuláris dinamika]]i szimulációhoz.
 
===== Vektorprocesszorok =====
308. sor:
== Algoritmikus módszerek ==
 
Ahogy a párhuzamos számítógépek egyre nagyobbá és gyorsabbá válnak, most már képesek vagyunk megoldani azokat a problémákat, amelyek futása korábban túl sokáig tartott. Az olyan változatos területek, mint a [[bioinformatika]] ([[fehérjehajtogatás]] és [[szekvenciaelemzés]]) és a közgazdaságtan (a [[pénzügyi matematika]] szempontjából) kihasználták a párhuzamos számítástechnika lehetőségeit. A párhuzamos számítástechnikai alkalmazások általános problémái a következők:<ref>Asanovic, Krste, et al. (December 18, 2006). [http://www.eecs.berkeley.edu/Pubs/TechRpts/2006/EECS-2006-183.pdf „The Landscape of Parallel Computing Research: A View from Berkeley”] (PDF). University of California, Berkeley. Technical Report No. UCB/EECS-2006-183. See table on pages 17–19.</ref>
 
* sűrű [[lineáris algebra]],
343. sor:
A SIMD párhuzamos számítógépek az 1970-es évekre vezethetők vissza. A korai SIMD számítógépek mögött a motiváció az volt, hogy a processzor [[vezérlőegység]]ének [[Terjedési késés|kapukésését]] több utasítás felett csökkentsék.'''<ref>Patterson and Hennessy, p.&nbsp;749.</ref>''' 1964-ben Slotnick javaslatot tett egy tömegesen párhuzamos számítógép felépítésére a [[Lawrence Livermore National Laboratory|Lawrence Livermore Nemzeti Laboratórium]] számára.'''<ref name="G_Wilson" />''' Tervezését az [[Az Amerikai Egyesült Államok Légiereje|amerikai légierő]] támogatta, amely a legkorábbi SIMD párhuzamos számítástechnikai erőfeszítés volt, [[ILLIAC IV]] néven.'''<ref name="G_Wilson" />''' A tervezés kulcsa egy meglehetősen nagy párhuzamosság volt, akár 256 processzorral, amely lehetővé tette a gép számára, hogy nagy adatkészleteken dolgozzon, amit később [[Vektorprocesszor|vektorfeldolgozásnak]] neveznek. Az ILLIAC IV-et azonban „a szuperszámítógépek leghírhedtebbikének” nevezték, mivel a projekt csak egynegyede fejeződött be, de 11 évig tartott, és az eredeti becslés majdnem négyszeresébe került.'''<ref name="infamous">Patterson and Hennessy, pp.&nbsp;749–50: „Noha az ILLIAC IV sikeresen alkalmazta a későbbi projektekben hasznos technológiákat, az ILLIAC IV számítógépes hibaként jelent meg. A költségek az 1966-ban becsült 8 millió dollárról 1972-re 31 millió dollárra növekedtek, annak ellenére, hogy a tervezett gép mindössze egynegyedét építették meg. Ez talán a szuperszámítógépek leghírhedtebbike volt. A projekt 1965-ben indult, és első valódi alkalmazását 1976-ban futatta.”</ref>''' Amikor 1976-ban végre készen állt az első valódi alkalmazás futtatására, azt a meglévő kereskedelmi szuperszámítógépek, mint például a [[Cray-1]], felülmúlták.
 
== Biológiai agy, mint tömegesen párhuzamos számítógép ==
 
Az 1970-es években, az [[MIT Computer Science and Artificial Intelligence Laboratory|MIT Számítástudományi és Mesterséges Intelligencia Laboratóriumban]] [[Marvin Minsky]] és [[Seymour Papert]] fejlődésnek indította a ''[[Society of Mind]]'' elméletet, amely a biológiai agyat, mint [[Tömegesen párhuzamos feldolgozás|tömegesen párhuzamos számítógép]] látja. Minsky 1986-ban publikálta a ''The Society of Mind'' című könyvét, amely azt állítja, hogy „az elme sok kis ágensből áll, amelyek önmagukban értelmetlenek”.<ref>{{cite book |last=Minsky |first=Marvin |title=The Society of Mind |url=https://archive.org/details/societyofmind00marv/page/17 |date=1986 |publisher=Simon & Schuster |location=New York |isbn=978-0-671-60740-1 |pages=[https://archive.org/details/societyofmind00marv/page/17 17]}}</ref> Az elmélet megkísérli megmagyarázni, hogy amit intelligenciának nevezünk, miként lehet nem intelligens részek kölcsönhatásának a terméke. Minsky elmondja, hogy az elmélettel kapcsolatos ötletek legnagyobb forrása az a munkája volt, hogy megpróbált olyan gépet létrehozni, amely robotkar, videókamera és számítógép segítségével építkezik építőkockákból.<ref>{{cite book |last=Minsky |first=Marvin |title=The Society of Mind |url=https://archive.org/details/societyofmind00marv/page/29 |date=1986 |publisher=Simon & Schuster |location=New York |isbn=978-0-671-60740-1 |pages=[https://archive.org/details/societyofmind00marv/page/29 29]}}</ref>
 
Hasonló modelleket (amelyek ugyancsak a biológiai agyat tömegesen párhuzamos számítógépnek tekintik, azaz az agy független vagy részben független ágensekből áll) írnak le:
A lap eredeti címe: „https://hu.wikipedia.org/wiki/Párhuzamos_számítástechnika”