"Parallisme als manier van parallelle gegevensverwerking"
Kotovsk 2010
Invoering
De snelle ontwikkeling van de wetenschap en de penetratie van het menselijk denken in alle nieuwe gebieden, samen met de oplossing van eerder gestelde problemen, genereert voortdurend een stroom van vragen en stelt nieuwe, meestal complexere taken. In de dagen van de eerste computers leek het erop dat een 100-voudige toename van hun snelheid de meeste problemen zou oplossen, maar de gigaflop-prestaties van moderne supercomputers zijn voor veel wetenschappers duidelijk onvoldoende. Elektro- en hydrodynamica, seismische verkenning en weersvoorspelling, modellering van chemische verbindingen, onderzoek naar virtual reality - dit is geen volledige lijst van wetenschapsgebieden waarvan de onderzoekers elke gelegenheid aangrijpen om de uitvoering van hun programma's te versnellen.
De meest veelbelovende en dynamische richting om de snelheid van het oplossen van toegepaste problemen te vergroten, is de wijdverbreide introductie van parallellisme-ideeën in de werking van computersystemen. Tot op heden zijn honderden verschillende computers ontworpen en getest, waarbij gebruik wordt gemaakt van een of ander type parallelle gegevensverwerking in hun architectuur. In de wetenschappelijke literatuur en technische documentatie vindt u meer dan een dozijn verschillende namen die alleen de algemene principes van de werking van parallelle machines kenmerken: vector-pipeline, massaal parallel, computers met een breed commandowoord, systolische arrays, hypercubes, speciale processors en multiprocessors, hiërarchische en clustercomputers, dataflow, matrixcomputers en vele andere. Als voor de volledigheid gegevens worden toegevoegd over belangrijke parameters zoals bijvoorbeeld geheugenorganisatie, topologie van communicatie tussen processors, synchronisatie van de werking van individuele apparaten of de manier waarop rekenkundige bewerkingen worden uitgevoerd, dan zal het aantal verschillende architecturen toenemen volledig grenzeloos.
Pogingen om de hele reeks architecturen te systematiseren begonnen nadat M. Flynn eind jaren 60 de eerste versie van de classificatie van computersystemen had gepubliceerd en gaan tot op de dag van vandaag door. Classificatie is erg belangrijk voor een beter begrip van het bestudeerde vakgebied, maar het vinden van een succesvolle classificatie kan een aantal belangrijke gevolgen hebben.
De hoofdvraag van de classificatie - wat eraan ten grondslag ligt, kan op verschillende manieren worden opgelost, afhankelijk van voor wie deze classificatie wordt gemaakt en om op te lossen op welk probleem deze is gericht. Zo maakt de veelgebruikte indeling van computers in personal computers, werkstations, minicomputers, grote mainframes, minisupercomputers en supercomputers het misschien mogelijk om de kosten van een computer ruwweg te schatten. Het brengt de gebruiker echter niet dichter bij het begrip van wat er van hem wordt verlangd om een programma te schrijven dat op de grens van de prestaties van een parallelle computer werkt, d.w.z. waarvoor hij besloot het te gebruiken.
De classificatie moet helpen om te begrijpen wat elke architectuur is, hoe ze met elkaar verbonden zijn, waarmee rekening moet worden gehouden om echt effectieve programma's te schrijven, of op welke klasse van architecturen moet worden gericht om de vereiste klasse van problemen op te lossen. Tegelijkertijd zou een succesvolle classificatie mogelijke manieren kunnen suggereren om computers te verbeteren, en in die zin zou het voldoende zinvol moeten zijn. Het is moeilijk te rekenen op het vinden van niet-triviale "witte vlekken", bijvoorbeeld in de classificatie op kosten, maar nadenken over de mogelijke taxonomie in termen van eenvoud en maakbaarheid van programmering kan uiterst nuttig zijn bij het bepalen van de richting van het zoeken naar nieuwe architecturen.
1. Parallelle computersystemen
Parallelle computersystemen zijn zowel fysieke computersystemen als softwaresystemen die op de een of andere manier parallelle gegevensverwerking op veel computerknooppunten implementeren.
Het idee van parallelle berekeningen is gebaseerd op het feit dat de meeste problemen kunnen worden onderverdeeld in een reeks kleinere problemen die tegelijkertijd kunnen worden opgelost. Parallel computing vereist meestal coördinatie. Parallel computergebruik is er in verschillende vormen: parallellisme op bitniveau, parallellisme op instructieniveau, gegevensparallellisme, taakparallellisme. Parallel computing wordt al vele jaren gebruikt, voornamelijk in high-performance computing, maar de laatste tijd is er een toenemende belangstelling voor vanwege het bestaan van fysieke beperkingen op de groei van processorkloksnelheden. Parallel computing is het dominante paradigma geworden in computerarchitectuur, voornamelijk in de vorm van multi-coreprocessors.
Het schrijven van programma's voor parallelle systemen is moeilijker dan voor sequentiële, aangezien resourceconflicten een nieuwe klasse van potentiële softwarefouten (bugs) vertegenwoordigt, waarvan racecondities de meest voorkomende zijn. Interactie en synchronisatie tussen processen vormen een grote barrière voor het bereiken van hoge prestaties in parallelle systemen. De laatste jaren is er ook aandacht voor de kwestie van het elektriciteitsverbruik door parallelle computers. De aard van de toename in programmasnelheid als gevolg van parallellisatie wordt verklaard door de wet van Amdahl.
Als de berekening geen cyclische (repetitieve) acties toepast, dan zullen N rekenmodules het werk nooit N keer sneller voltooien dan één enkele rekenmodule.
Als u bijvoorbeeld snel een array wilt sorteren op een machine met twee processors, kunt u de array in tweeën splitsen en elke helft op een aparte processor sorteren. Het sorteren van elke helft kan een andere tijd in beslag nemen, dus synchronisatie is noodzakelijk.
2. Gelijktijdigheidstypen
2.1 Parallellisme op bitniveau
Deze vorm van parallellisme is gebaseerd op het vergroten van het machinewoord. Het vergroten van de grootte van het machinewoord vermindert het aantal bewerkingen dat de processor nodig heeft om acties uit te voeren op variabelen waarvan de grootte groter is dan de grootte van het machinewoord. Bijvoorbeeld: op een 8-bits processor moet u twee 16-bits gehele getallen toevoegen. Om dit te doen, moet u eerst de onderste 8 bits van de getallen toevoegen, vervolgens de bovenste 8 bits toevoegen en de carry-vlagwaarde toevoegen aan het resultaat van hun toevoeging. Er zijn in totaal 3 instructies. Met een 16-bits processor kunt u deze bewerking met één instructie uitvoeren.
Historisch gezien werden 4-bits microprocessors vervangen door 8-bits, waarna 16-bits en 32-bits verschenen. 32-bits processors zijn al lang de standaard in het dagelijkse computergebruik. Met de komst van x86-64-technologie werden 64-bits processors voor deze doeleinden gebruikt.
2.2 Parallellisme op instructieniveau
Een computerprogramma is in wezen een stroom instructies die door een processor wordt uitgevoerd. Maar u kunt de volgorde van deze instructies wijzigen, ze in groepen verdelen die parallel worden uitgevoerd, zonder het resultaat van het hele programma te veranderen. Deze techniek staat bekend als parallellisme op instructieniveau. Vooruitgang in de ontwikkeling van parallellisme op instructieniveau in computerarchitectuur vond plaats van het midden van de jaren tachtig tot het midden van de jaren negentig.
Moderne processors hebben een meertraps instructiepijplijn. Elke fase van de pijplijn komt overeen met een bepaalde actie die door de processor in deze instructie in deze fase wordt uitgevoerd. Een processor met N pijplijntrappen kan tegelijkertijd tot N verschillende instructies op verschillende niveaus van volledigheid hebben. Een klassiek voorbeeld van een pijplijnprocessor is een RISC-processor met 5 fasen: haal een instructie uit het geheugen (IF), decodeer een instructie (ID), voer een instructie uit (EX), toegangsgeheugen (MEM), schrijf het resultaat naar registers ( WB) ... De Pentium 4-processor heeft een pijplijn met 35 fasen.
Sommige processors hebben, naast het gebruik van pijplijnen, de mogelijkheid om meerdere instructies tegelijkertijd uit te voeren, wat extra parallellisme op instructieniveau oplevert. Het is mogelijk om deze methode te implementeren met behulp van superscalariteit, wanneer instructies kunnen worden gegroepeerd voor parallelle uitvoering (als ze geen gegevensafhankelijkheden hebben). Implementaties met expliciet parallellisme op instructieniveau zijn ook mogelijk: VLIW en EPIC.
2.3 Gegevensparallellisme
De hoofdgedachte van de aanpak op basis van dataparallellisme is dat er direct één bewerking wordt uitgevoerd op alle elementen van de data-array. Verschillende fragmenten van zo'n array worden verwerkt op een vectorprocessor of op verschillende processors van een parallelle machine. Het programma verdeelt de gegevens tussen de processors. In dit geval wordt vectorisatie of parallellisatie meestal al uitgevoerd in de compilatiefase - vertaling van de broncode van het programma in machine-instructies. De rol van de programmeur komt in dit geval meestal neer op het specificeren van instellingen voor vector- of parallelle optimalisatie aan de compiler, richtlijnen voor parallelle compilatie en het gebruik van gespecialiseerde talen voor parallelle berekeningen.
2.4 Parallellisme van taken (multithreading)
De programmeerstijl die is gebaseerd op parallellisme van taken houdt in dat een rekentaak is verdeeld in verschillende relatief onafhankelijke subtaken en dat elke processor wordt geladen met zijn eigen subtaak.
2.5 Gedistribueerde besturingssystemen
Een gedistribueerd besturingssysteem, door het dynamisch en automatisch verdelen van werk over verschillende machines in het systeem voor verwerking, zorgt ervoor dat een set netwerkmachines fungeert als een virtuele uniprocessor. De gebruiker van een gedistribueerd besturingssysteem heeft in het algemeen geen informatie over de machine waarop zijn werk wordt uitgevoerd.
Een gedistribueerd besturingssysteem bestaat als een enkel besturingssysteem over een computersysteem. Elke computer in een netwerk met een gedistribueerd besturingssysteem voert een deel van de functies van dit wereldwijde besturingssysteem uit. Een gedistribueerd besturingssysteem verenigt alle computers op een netwerk in die zin dat ze nauw met elkaar samenwerken om alle bronnen van een computernetwerk efficiënt te gebruiken.
Parallel en pijplijnen
Bij parallelle gegevensverwerking is het idee van gelijktijdige uitvoering van verschillende acties belichaamd, zoals: transportband en parallellisme.
Parallelle verwerking
Wanneer het apparaat één bewerking per tijdseenheid uitvoert, kunnen we zeggen dat het apparaat duizend bewerkingen zal uitvoeren in duizend eenheden. Als we aannemen dat er vijf onafhankelijke apparaten tegelijkertijd werken, dan kan zo'n systeem van apparaten dezelfde duizend bewerkingen uitvoeren in tweehonderd tijdseenheden. Naar analogie zal een systeem van N apparaten hetzelfde werk uitvoeren in 1000 / N tijdseenheden. Dit geldt ook in het echte leven, bijvoorbeeld:
een moestuin kan door één soldaat in 10 uur worden opgegraven, en een gezelschap van soldaten van 50 mensen met dezelfde capaciteiten, terwijl ze tegelijkertijd werken, zal het in 12 minuten opgraven - het principe van parallellisme in actie.
A.A. Samarskiy, die begin jaren 50 berekeningen uitvoerde voor het simuleren van nucleaire explosies, was een pionier in de parallelle verwerking van datastromen. Samarsky berekende de evolutie van de explosiegolf op een interessante manier - hij zette enkele tientallen mensen met rekenmachines aan tafels, dwong hen om gegevens eenvoudig in woorden naar elkaar over te dragen en zette de nodige getallen op de optelmachines. We kunnen zeggen dat het is
en er was het eerste parallelle systeem. Ondanks dat de berekeningen van de waterstofbom vakkundig zijn uitgevoerd, was de nauwkeurigheid vrij laag, omdat het gebruikte raster weinig knooppunten had en de rekentijd te lang was.Transportband verwerking:
Om twee reële getallen toe te voegen die in drijvende-kommavorm worden weergegeven, is het nodig om een groot aantal kleine bewerkingen uit te voeren - bestellingen vergelijken, bestellingen uitlijnen, mantisse toevoegen, normaliseren, enz. Al deze "micro-operaties" voor elk paar argumenten, de processors van de eerste computers werden achter elkaar uitgevoerd, totdat ze het eindresultaat bereikten, en pas toen werd het volgende paar verwerkt
voorwaarden.De essentie van pipelining is om de afzonderlijke fasen van een algemene operatie te onderscheiden. Elke fase, die zijn werk had voltooid, zou het resultaat naar de volgende verzenden, terwijl tegelijkertijd een nieuw deel van de gegevens werd ontvangen. Het combineren van eerder verspreide bewerkingen heeft zeker een positief effect op de verwerkingssnelheid. Een operatie kan bijvoorbeeld worden onderverdeeld in vijf micro-operaties, die elk in één tijdseenheid worden uitgevoerd.
Als er één ondeelbaar serieel apparaat is, dan verwerkt het 100 paren argumenten in 500 eenheden. Als elke micro-operatie wordt opgesplitst in een afzonderlijke fase (of fase) van een transportinrichting, dan zal de vijfde tijdseenheid in een andere fase van verwerking van zo'n apparaat de eerste vijf paren argumenten bevatten, en de hele set van honderd paren worden verwerkt in 104 (5 + 99) tijdseenheden - versnelling in vergelijking met een sequentieel apparaat is bijna vijf keer (in termen van het aantal fasen van de transportband).Het lijkt erop dat pijplijnverwerking met succes kan worden vervangen door conventioneel parallellisme; het is voldoende om het hoofdapparaat zo vaak te dupliceren als het aantal pijplijntrappen zou moeten worden toegewezen. Inderdaad, 5 apparaten verwerken 100 paar argumenten in 100 tijdseenheden, wat sneller is dan de looptijd van een transportapparaat. Als het aantal apparaten vervijfvoudigd wordt, zullen het volume van de apparatuur en de kosten ervan aanzienlijk toenemen. Denk bijvoorbeeld aan een situatie waarin een transportband wordt verwijderd bij een autofabriek, terwijl het tempo van de autoproductie moet worden gehandhaafd en er dus duizend teams nodig zijn, die elk een auto van begin tot eind kunnen assembleren, nadat ze honderden verschillende operaties, en in een vrij korte tijd.
De kosten van de auto zullen enorm zijn. Daarom was er een pijplijnverwerking.
Moderne parallelle systemen
Momenteel zijn er vier richtingen in de ontwikkeling van high-performance computing.
Vector transportband computers
De eigenaardigheden van dergelijke machines zitten in de set van vectorinstructies en functionele transportinrichtingen. In tegenstelling tot de traditionele benadering, kunnen vectorteams werken op volledige arrays van onafhankelijke gegevens, wat betekent dat het mogelijk wordt om de beschikbare pijplijnen efficiënt te laden, d.w.z. een commando van de vorm A = B + C kan niet de toevoeging van twee getallen betekenen, maar twee arrays. Een typische vertegenwoordiger van deze richting is de CRAY-familie van vectortransportbandcomputers.
Massaal parallelle computers met gedistribueerd geheugen.
De constructie van computers van deze klasse onderscheidt zich door een eenvoudig idee: elke seriële microprocessor is uitgerust met zijn eigen lokale geheugen en vervolgens verbonden door middel van een communicatiemedium. Deze architectuur heeft veel voordelen: om de prestaties te verhogen, volstaat het om het aantal processors te vergroten; de optimale configuratie is eenvoudig te selecteren als de benodigde rekenkracht bekend is.
Er is echter een belangrijk nadeel dat opweegt tegen veel van de voordelen. In deze computers is de communicatie tussen processors veel langzamer dan de lokale gegevensverwerking door de processors zelf. In dit opzicht is het erg moeilijk om een effectief programma voor dergelijke computers te schrijven; soms is het gewoon onmogelijk voor sommige algoritmen. Voorbeelden van dergelijke computers: Intel Paragon, IBM SP1, Parsytec, tot op zekere hoogte IBM SP2 en CRAY T3D/T3E, al is de invloed van dit nadeel bij deze computers veel minder. Ook netwerken van computers, die steeds vaker worden gezien als een redelijk goedkoop alternatief voor extreem dure computers, kunnen tot dezelfde klasse worden gerekend.
Parallelle computers met gedeeld geheugen
Al het RAM-geheugen van deze computers wordt gedeeld door verschillende identieke processors. De problemen van de vorige klasse zijn opgelost, maar er zijn nieuwe toegevoegd - om technische redenen is het onmogelijk om een groot aantal processors te maken die toegang zouden hebben tot gedeeld geheugen. Voorbeelden van deze richting zijn veel multiprocessor SMP computers of bijvoorbeeld individuele nodes van HP Exemplar en Sun StarFire computers.
Gecombineerde systemen
De laatste richting is eerder niet onafhankelijk, maar gewoon een combinatie van de vorige drie. Laten we een rekenknooppunt vormen van verschillende processors (traditioneel of vector-pipelined) en een gemeenschappelijk geheugen voor hen. Als er een gebrek aan rekenkracht is, kun je meerdere nodes combineren met snelle verbindingen. Deze architectuur wordt geclusterd genoemd. Sun StarFire, NEC SX-5, CRAY SV1, HP Exemplar, de nieuwste IBM SP2 en andere zijn op dit principe gebouwd.
Deze richting is momenteel de meest veelbelovende voor het ontwerpen van computers met recordprestaties.
Gelijktijdigheidsniveaus
Afhankelijk van het niveau waarop parallelliteit moet worden gewaarborgd, worden bepaalde methoden en implementatiemiddelen gebruikt. Er zijn de volgende niveaus van parallellisme.
Micro niveau... De uitvoering van een instructie is opgedeeld in fasen en de fasen van verschillende aangrenzende instructies kunnen worden overlapt door pipelining. Het is mogelijk om dit niveau te bereiken in een vliegtuig met één processor.
Draadniveau... Taken worden opgesplitst in brokken die parallel kunnen lopen (threads). Dit niveau wordt bereikt op parallelle vliegtuigen.
Teamniveau... Meerdere instructies worden parallel uitgevoerd, meerdere pijplijnen worden tegelijk in de processor geplaatst. Typisch voor superscalaire processors.
Quest-niveau... Onafhankelijke taken worden gelijktijdig uitgevoerd op verschillende processors, er is praktisch geen interactie met elkaar. Het niveau is typisch voor multiprocessor- en multicomputervliegtuigen.
Het concept van gelijktijdigheidsniveau is nauw verwant aan het concept van granulariteit. Granulariteit is een maatstaf voor de verhouding tussen de hoeveelheid berekeningen die in een parallelle taak worden uitgevoerd en de hoeveelheid communicatie (voor berichten). De korreligheid varieert van fijn tot grof. De wet van Amdahl richt zich op grof graan
parallellisme.Grofkorrelig parallellisme betekent dat elke parallelle berekening voldoende onafhankelijk is van de andere; bovendien vereisen individuele berekeningen relatief weinig uitwisseling van informatie onderling. De eenheden van parallellisatie zijn grote en onafhankelijke programma's met duizenden instructies. Het besturingssysteem biedt dit niveau van parallellisme.
Voor een efficiënte parallelle uitvoering is het noodzakelijk om een evenwicht te vinden tussen de mate van granulariteit van het programma en de hoeveelheid communicatievertraging die optreedt tussen verschillende granules. Fijnmazige programmasplitsing is het meest geschikt voor minimale communicatielatentie. In dit geval is dataparallellisme aan het werk. Als de communicatielatentie groot is, is het beter om een grofkorrelige programmapartitionering te gebruiken.
Literatuur
- Badenko V.L. High-performance computergebruik. Zelfstudie. - SPb.: Uitgeverij van Polytechnic. Universiteit, 2010 .-- 180 p.
- Barsky AB Parallelle informatietechnologieën: leerboek / A.B. Barsky.-M.: Internet Universiteit voor Informatietechnologie; BINOMIAAL. Knowledge Laboratory, 2007.-503 p.: ill., Tab.- (reeks "Fundamentals of Information Technologies") - p.20-28, p.56-58.
- VV Korneev Computersystemen.-M.: Helios APB, 2004.-512s., Ill.- p. 34-46
- Latsis AO Parallelle gegevensverwerking. M.: Academie, 2010 .-- 336 d.
- Tsilker B.Ya., Orlov SA Organisatie van computers en systemen. Leerboek voor universiteiten. - SPb .: Peter, 2004 .-- 668 d.
Berichten
Berichten
4 gangen, 1 en 2 stromen, 7e semester
hoorcolleges (34 uur), toets
Afdeling verantwoordelijk voor de cursus: ASVK
Programma compiler: Corresponderend lid RAS, doctor in de Phys.-Math. V.V. Voevodin,
docenten: Corresponderend lid RAS, doctor in de Phys.-Math. Wetenschappen Voevodin Vl.V.
annotatie
De cursus behandelt algemene kwesties van het organiseren van parallel computing. De kenmerken van architecturen van moderne parallelle computersystemen worden overwogen, de belangrijkste methoden en paradigma's van programmeren in parallelle omgevingen worden bestudeerd.Voor de 1e en 2e stroming worden benaderingen voor de coördinatie van de kenmerken van de architectuur van parallelle systemen en de structuur van algoritmen, vraagstukken van de analysetheorie van de structuur van programma's en algoritmen, modellen in parallel computing besproken.
Programma
1. Grote taken en supercomputers. Parallelle en gepijplijnde gegevensverwerking. Parallellisme en pipelining in de architectuur van moderne krachtige computers. Scalaire en vectoropdrachten. Scalaire, pijplijn- en vectorapparaten. Geheugenhiërarchie in computers als middel om de snelheid van het uitvoeren van programma's, de plaats van berekeningen en de plaats van gegevensgebruik te verhogen. De wet van Amdahl en de gevolgen ervan, superlineaire versnelling.2. De belangrijkste klassen van moderne parallelle computersystemen. Computers met gedeeld geheugen, voorbeelden, redenen voor prestatievermindering in echte programma's. SMP, NUMA, ccNUMA-architecturen. Schakelende processors en geheugenmodules, bus, matrixcommutator, omega-netwerk. Vectorpijplijncomputersystemen, voorbeelden, redenen voor prestatievermindering. Computers met gedistribueerd geheugen, voorbeelden, redenen voor prestatievermindering. Topologie van communicatie tussen processors: ster, rooster, driedimensionale torus, binaire hyperkubus, hun eigenschappen. Computerclusters, voorbeelden, latentie en bandbreedte van verschillende communicatietechnologieën. Parallellisme-architecturen voor machine-instructie, VLIW, superscalar.
3. Technologieën van parallel programmeren. Traditionele sequentiële talen en parallelliserende compilers, problemen. Speciale opmerkingen en richtlijnen voor de compiler, uitbreidingen van bestaande talen. Speciale talen voor parallel programmeren. Programmeren met behulp van bibliotheken en berichteninterfaces. Parallelle onderwerpbibliotheken, gespecialiseerde pakketten en softwaresystemen op hoog niveau. Parallelle programmeertechnologieën MPI, OpenMP, Linda.
4. Prestaties van parallelle computersystemen. De veelzijdigheid en specialisatie van computers, de prestaties van speciale processors. De wet van Moore. Methoden voor het evalueren van prestaties. Introductie van een enkele numerieke parameter, Mflops, MIPS. Piek en echte prestaties van computers. Linpack-benchmark en varianten. Sets van complementaire testprogramma's, STREAM en NPB.
5. Grafische modellen van programma's. Controlegrafiek en programma-informatiegrafiek. Informatieve en operationele geschiedenis van de uitvoering van het programma. Algoritmegrafiek als een compacte parametrische vorm van presentatie van informatiegeschiedenis. Informatieonafhankelijkheid van operaties en de mogelijkheid van parallelle uitvoering ervan. De lengte van het kritieke pad van de grafiek van het algoritme als maat voor de mate van parallellisme. Eindig en massaal parallellisme, coördinaat en gekanteld parallellisme. Gelijkwaardige programmatransformaties, elementaire lustransformaties.
6. Heterogene gedistribueerde computersystemen. Metacomputers en metacomputing, bestaande metacomputerprojecten. Onderscheidende eigenschappen van metacomputers. Het concept van GRID, basiscomponenten en diensten, bestaande projecten van GRID-segmenten, het concept van een virtuele organisatie.
Literatuur
1. Voevodin VV, Voevodin Vl.V. Parallel computergebruik. - SPb .: BHV Petersburg, 2002 .-- 608 d.2. Korolev LN De architectuur van de processors van elektronische computers. - M.: Ed. Faculteit CMC, Staatsuniversiteit van Moskou, 2003.
3. VV Korneev. Parallelle computersystemen. - M.: Uitgeverij "Kennis", 1999. - 320s.
4. Materialen van het informatie- en analytische centrum over parallel computing Parallel.ru.
aanvullende literatuur
1. Antonov A.S. Parallel programmeren met behulp van technologieMPI: een studiegids. - M.: Uitgeverij van de Staatsuniversiteit van Moskou, 2004 .-- 71 p.
Verhoogde computerprestaties, waardoor?
Waarom tellen supercomputers zo snel? Er kunnen verschillende antwoorden zijn, waarvan er twee een duidelijk voordeel hebben: de ontwikkeling van de elementbasis en het gebruik van nieuwe oplossingen in de architectuur van computers.
Laten we proberen erachter te komen welke van deze factoren bepalend blijkt te zijn voor het behalen van recordprestaties. Laten we eens kijken naar de bekende historische feiten. Op een van de eerste computers ter wereld - EDSAC, die in 1949 in Cambridge verscheen en een cyclustijd had van 2 microseconden (2 * 10-6 seconden), was het mogelijk om 2 * n rekenkundige bewerkingen uit te voeren in 18 * n milliseconden , dat wil zeggen, gemiddeld 100 rekenkundige bewerkingen per seconde. Laten we een vergelijking maken met één rekenknooppunt van de moderne supercomputer Hewlett-Packard V2600: de cyclustijd is ongeveer 1,8 nanoseconden (1,8 * 10-9 seconden), en de piekprestaties zijn ongeveer 77 miljard rekenkundige bewerkingen per seconde.
Dus wat gebeurt er? In een halve eeuw zijn de computerprestaties met meer dan zevenhonderd miljoen een keer. Tegelijkertijd is de snelheidswinst die gepaard gaat met een afname van de cyclustijd van 2 microseconden naar 1,8 nanoseconden slechts ongeveer 1000 keer. Waar kwam de rest vandaan? Het antwoord ligt voor de hand: het gebruik van nieuwe oplossingen in computerarchitectuur. De belangrijkste plaats onder hen wordt ingenomen door het principe van parallelle gegevensverwerking, dat het idee van gelijktijdige (parallelle) uitvoering van verschillende acties belichaamt.
Parallelle gegevensverwerking, die het idee belichaamt van gelijktijdige uitvoering van verschillende acties, heeft twee varianten: pipelining en eigenlijk parallellisme. Beide soorten parallelle verwerking zijn intuïtief, dus hier volgen slechts enkele uitleg.
Parallelle verwerking... Als een bepaald apparaat één bewerking per tijdseenheid uitvoert, dan zal het duizend bewerkingen uitvoeren in duizend eenheden. Als we aannemen dat er vijf dezelfde onafhankelijke apparaten zijn die tegelijkertijd kunnen werken, dan kan een systeem van vijf apparaten dezelfde duizend bewerkingen uitvoeren, niet in duizend, maar in tweehonderd tijdseenheden. Evenzo zal een systeem van N apparaten hetzelfde werk uitvoeren in 1000 / N tijdseenheden. Vergelijkbare analogieën zijn te vinden in het leven: als een soldaat in 10 uur een moestuin opgraaft, dan zal een bedrijf van vijftig soldaten met dezelfde capaciteiten, gelijktijdig werkend, hetzelfde werk in 12 minuten aan - het principe van parallellisme in actie !
Trouwens, de pionier in de parallelle verwerking van datastromen was academicus A.A. Samarskiy, die begin jaren 50 de berekeningen uitvoerde die nodig waren om nucleaire explosies te simuleren. Samarsky loste dit probleem op door enkele tientallen jonge dames met rekenmachines aan tafels te laten zitten. De jongedames gaven elkaar eenvoudig in woorden gegevens door en zetten de benodigde getallen op de rekenmachines. Zo werd in het bijzonder de evolutie van de explosiegolf berekend. Er was veel werk, de jonge dames waren moe en Alexander Andreevich liep tussen hen in en moedigde hen aan. Dit, zou je kunnen zeggen, was het eerste parallelle systeem. Hoewel de berekeningen van de waterstofbom vakkundig zijn uitgevoerd, was de nauwkeurigheid erg laag, omdat er weinig knooppunten in het raster werden gebruikt en de teltijd te lang was.
Transportband verwerking:... Wat is er nodig om twee drijvende-kommagetallen toe te voegen? Een heleboel kleine operaties zoals het vergelijken van orders, het uitlijnen van orders, het toevoegen van mantissen, normalisatie, etc. De processors van de eerste computers voerden al deze "microbewerkingen" voor elk paar argumenten één voor één uit, één voor één, totdat ze het uiteindelijke resultaat bereikten, en pas daarna gingen ze verder met het verwerken van het volgende paar termen.
Het idee van pipelining is om de afzonderlijke fasen van een algemene bewerking te onderscheiden, en elke fase, die zijn werk heeft voltooid, zou het resultaat naar de volgende overbrengen, terwijl tegelijkertijd een nieuw deel van de invoergegevens wordt geaccepteerd. We krijgen een duidelijke winst in verwerkingssnelheid door de combinatie van eerder gespreide bewerkingen in de tijd. Stel dat een operatie kan worden onderverdeeld in vijf micro-operaties, die elk in één tijdseenheid worden uitgevoerd. Als er één ondeelbaar serieel apparaat is, dan zal het 100 paren argumenten in 500 eenheden verwerken. Als elke micro-operatie wordt opgesplitst in een afzonderlijke fase (of, met andere woorden, een fase) van een transportinrichting, dan worden in de vijfde tijdseenheid in een andere fase van verwerking van een dergelijke inrichting de eerste vijf paar argumenten zal worden gevonden en de hele set van honderd paren zal worden verwerkt in 5 + 99 = 104 tijdseenheden - versnelling in vergelijking met een sequentieel apparaat met bijna vijf keer (in termen van het aantal fasen van de transportband).
Het lijkt erop dat pipelining met succes kan worden vervangen door conventioneel parallellisme, waarvoor het hoofdapparaat zo vaak kan worden gedupliceerd als het aantal pijplijntrappen zou moeten worden toegewezen. Inderdaad, de vijf apparaten in het vorige voorbeeld zullen 100 paar argumenten verwerken in 100 tijdseenheden, wat sneller is dan de looptijd van het transportapparaat! Wat is er? Het antwoord is simpel: door het aantal apparaten vijf keer te vergroten, verhogen we zowel het volume van de apparatuur als de kosten ervan aanzienlijk. Stel je voor dat de autofabriek besloot de transportband te verwijderen, terwijl het tempo van de autoproductie gehandhaafd bleef. Als er eerder duizend auto's tegelijkertijd op de lopende band waren, moet je, naar analogie met het vorige voorbeeld, duizend teams rekruteren, die elk (1) in staat zijn om een auto van begin tot eind volledig te monteren , honderden verschillende soorten bewerkingen uitvoeren, en (2) het doen in dezelfde tijd dat de auto eerder op de transportband stond. Heb je je de kosten van zo'n auto ingebeeld? Nee? Ik ben het ermee eens, het is moeilijk, behalve dat Lamborghini in me opkomt, maar daarom is pijplijnverwerking ontstaan ...
