Samtidig og parallell programmering: Definisjon, praksis og målinger

Formarse » Gratis online kurs » Samtidig og parallell programmering: Definisjon, praksis og målinger

Hvis du er involvert i utvikling, har du sannsynligvis hørt om samtidighet og parallellisme, men det er ikke alltid klart hvor den ene slutter og den andre begynner. Kort sagt, Begge teknikkene søker å utnytte systemressursene bedre, selv om de forfølger litt forskjellige mål og implementeres med forskjellige verktøy og kriterier.

Før vi går inn på det, er det verdt å merke seg at selv om de ofte brukes som synonymer i dagligspråket, er de ikke det. Faktisk, Samtidighet beskriver hvordan vi strukturerer og koordinerer oppgaver som sameksisterer, mens parallellisme refererer til å kjøre flere av disse oppgavene samtidig på kompatibel maskinvare. La oss herfra bryte det ned sakte og med klare eksempler.

Tydelig definisjon av samtidighet og parallellisme

Når vi snakker om samtidighet, refererer vi til et systems evne til å håndtere flere oppgaver som overlapper hverandre. Dette kan skje på en enkelt CPU uten at flere instruksjoner faktisk utføres samtidig: Systemet veksler mellom oppgaver (interleaving) slik at all fremdrift, noe som reduserer ventetider og forbedrer brukeropplevelsen. Det er en tilnærming til programvaredesign og koordinering.

Parallalismen er på sin side basert på ideen om splitt og hersk: Vi deler opp et stort problem i delproblemer og behandler disse delene samtidig. på tvers av flere dataenheter (kjerner, prosessorer eller noder). Dette er ekte parallell utførelse; derfor avhenger ytelsen i stor grad av tilgjengelig maskinvare.

I praksis er de to konseptene beslektet: samtidighet beskriver orkestrering av oppgaver, mens parallellisme beskriver samtidig utførelse. Det er derfor det noen ganger sies at Samtidighet fokuserer på programvaredesign og parallellisme i utførelsenDe er to sider av samme sak, men ikke utskiftbare.

En viktig avklaring: du vil noen ganger se definisjoner som likestiller samtidighet med behandling av mer enn én prosess om gangen. I virkeligheten, Denne samtidigheten er vanligvis tydelig på maskiner med én kjerne., takket være raske kontekstbytter; ekte samtidighet tilsvarer parallellisme og krever flere prosesseringsenheter.

Viktige forskjeller og maskinvarekrav

En praktisk forskjell ligger i systemkravene. For å oppnå ekte parallellisme kreves det flere dataenheter: flere kjerner, prosessorer eller maskiner; på den annen side kan samtidighet implementeres på en enkelt kjerne ved å alternere oppgaver. Dette påvirker direkte maskinvarekostnadene.

Hovedformålet er også forskjellig: mens samtidigheten reduserer opplevd latens og forbedrer responstiden av et system ved å administrere flere pågående oppgaver, søker parallellisme å øke den totale utførelsestiden for en jobb ved å dele den og utføre den samtidig.

En annen veldig nyttig forskjell: parallelt er deloppgaver vanligvis nært beslektet, og resultatene deres kombineres til et siste trinn. I samtidighet, Oppgaver kan være uavhengige og ikke avhengige av hverandre; hver av dem går frem i sitt eget tempo og vil fullføre når det er forfalt, uten nødvendigvis å synkronisere med de andre.

Til slutt, for designformål sier vi ofte at samtidighet handler om hvordan vi strukturerer programmet i enheter som sameksisterer og hvordan de kommuniserer, mens parallellisme handler om hvordan kjøre disse enhetene sammen for å oppnå bedre ytelseDu kan ha samtidighet uten parallellisme (en enkelt kjerne som veksler mellom oppgaver) og parallellisme uten mye samtidighet (en ren beregning av data delt og utført parallelt).

Hverdagseksempler for å unngå forvirring

Tenk deg en app for nedlasting av musikk. Brukeren velger flere sanger, og appen lar dem laste dem ned «samtidig». Hovedideen her er at Hver nedlasting er uavhengig og påvirker ikke de andre.Hvis én er treg, bremser den ikke de andre. Dette er et typisk samtidighetsscenario: flere oppgaver sameksisterer og beveger seg fremover, muligens alternerende CPU-er på samme kjerne.

Tenk deg nå en nettside for flysammenligning. Vi mottar brukerens kriterier (datoer, destinasjon, antall mellomlandinger) og starter samtidige søk etter flere flyselskaper. I dette tilfellet, alle søk bidrar til ett enkelt sluttresultat: finn det beste tilbudet. Vi må vente til alle er ferdige, samle resultatene og kombinere dem. Dette er en klassisk parallellismestrategi basert på å dele arbeidet og synkronisere til slutt.

En viktig observasjon i parallellisme er trinnet med resultatsammenføyning. Etter at problemet er partisjonert, må det være et kombinasjonstrinn som integrere delvise svar i en endelig løsningUten det trinnet leverer ikke parallellisme et komplett produkt.

I den virkelige verden eksisterer begge mønstrene ofte samtidig. For eksempel kan et nettsted håndtere mange brukerforespørsler samtidig, og innenfor hver enkelt, kjøre parallelle rutiner som utnytter flere kjerner for å få fart på intensive beregninger.

Maskinvare- og programvaremodeller: En oversikt

For å forstå mulighetene er det verdt å se på landskapet til parallell maskinvare og programvaren som utnytter den. Når det gjelder maskinvare, Det finnes forskjellige nivåer av parallellismeFra flere kjerner i én prosessor til klynger av maskiner med distribuert minne. Flynn-hierarkiet klassifiserer arkitekturer i kategorier som SISD, SIMD, MISD og MIMD.

På programvaresiden beveger vi oss mellom prosesser og tråder. En prosess har sitt eget adresserom, mens flere tråder deler minne i samme prosessÅ velge den ene eller den andre innebærer avgjørelser om kommunikasjons-, isolasjons- og synkroniseringskostnader.

Driftsmessig er tråder lette og raske til å dele data, men de krever ekstrem forsiktighet med tanke på minneintegritet. Prosesser, derimot, De tilbyr isolasjon og forhindrer visse typer korrupsjon, i bytte mot dyrere kommunikasjon og større ressursforbruk.

Mål, akser og fordeling av grunnleggende innhold

Et solid treningsprogram i parallell og samtidig programmering er vanligvis organisert i store deler. Den første er Forståelse av motivasjoner og trender: Hvorfor vi trenger parallell databehandling, hvilke ansvarsdelinger som letter design og hvordan ytelse påvirker beslutninger.

I parallell maskinvare studeres modeller og hierarkier, inkludert Flynns taksonomi, GPU-er og flerkjerne-/numa-systemer. Parallell programvare-blokken tar for seg konseptet med prosess og tråd, API-ene og hvordan man organiserer adresserommet og delt eller distribuert minne.

Den andre aksen dreier seg om å designe samtidige og distribuerte løsninger. Dette innebærer å forstå hva som skiller parallelle algoritmer fra serielle, og hvordan vi analyserer rom og tid i nærvær av oppmøte og kommunikasjon.

Dekomponeringsteknikker dekkes også: rekursive, datadrevne, utforskende, spekulative og andre. Uten en god dekomponering, parallellisme kompenserer ikke for overbelastningI tillegg må oppgaver tilordnes prosesser eller tråder, for å balansere belastningen og minimere interaksjon.

De mest brukte parallelle programmodellene faller inn under denne aksen: dataparallelisme (samme operasjon på flere elementer), oppgavegraf (eksplisitte avhengigheter) og mønsteret arbeidspool (sett med jobber som tråder dynamisk forbruker). Disse modellene hjelp med å resonnere rundt distribusjon og timing.

Den tredje blokken fokuserer på å løse typiske synkroniserings- og koordinasjonsproblemer. Her studeres emblematiske tilfeller, som produsent-forbruker, kommensale filosofer, røykerproblemet, barbersalongen, julenissens problem, vanndannelse og det såkalte Modus Hall-problemet. Hver av dem illustrerer farer som sult, fastlåste forhold og raseforhold.

De følgende blokkene fokuserer på å bygge samtidige programmer med delte ressurser (etter tråder) og bygge samtidige programmer med distribuerte ressurser (etter prosesser). I den første jobber du med grensesnitt som Pthreads og OpenMP, det felles adresserommet forstås, og du lærer å spore minne- og trådaktivitet.

Den andre tar for seg samtidighet i prosesser med distribuert minne og API-er som MPI. Den studerer parallell inngang og utgang, samt punkt-til-punkt og kollektiv kommunikasjon (kringkasting, spredning, samling, all-reduksjon). Minne- og prosesskanning øves også.

Til slutt finnes det seksjoner om programvaretesting, evaluering og sammenligning. Testing dekker black-box- og white-box-teknikker tilpasset samtidighet og distribusjon. Evaluering dekker Amdahls lov, hastighetsøkning, effektivitet og skalerbarhetsmålinger, måling av veggtid og visualisering med grafikk.

Dekomponeringsteknikker: hvordan man kan bryte ned problemet

Å velge hvordan man skal fordele arbeidsmengden utgjør forskjellen på om man oppnår eller mister ytelse. Datadekomposisjon tilordner delsett av datasettet til forskjellige utførende enheter; gjør underverker i homogene operasjoner hvordan man bruker et filter på piksler eller itererer gjennom lister.

Rekursiv dekomponering opptrer i splitt og hersk: problemet er fragmentert i mindre delproblemer opp til en terskel; parallell mergesort eller quicksort er klassiske eksemplerUtforskende dekomponering tilordner forskjellige søkegrener eller scenarier til forskjellige tråder eller noder.

Spekulativ dekomponering går alternative veier eller antagelser parallelt, og aksepterer at noen Beregninger er bortkastet hvis de ikke var nødvendigeDet er nyttig når vi forutsier at flere grener kan være gyldige, men vi vet ikke hvilken a priori.

Uansett teknikk må du tenke på koordineringskostnaden: hvis den er for høy, parallellisme mister effektivitetDerfor er arbeidsgranularitet nøkkelen: oppgaver som verken er for små eller så store at de ubalanserer arbeidsmengden.

Oppgavekartlegging og lastbalansering

Når nedbrytningen er bestemt, er det på tide å tilordne oppgaver til prosesser eller tråder. Statisk kartlegging fordeler arbeidet på forhånd; Det er enkelt og billig, men det kan bli ubalansert hvis oppgavene er uregelmessige. Dynamisk kartlegging (eller arbeid å stjele) tillater justering underveis.

Lastbalansering har som mål å sikre at alle utførende aktører har rimelig mye å gjøre. Dette oppnås ved å bruke delte eller lokale køer med arbeidstyveri. I tillegg, redusere interaksjonsoverbelastning mellom oppgaver, noe som minimerer kommunikasjon og kritiske områder.

I distribuerte miljøer påvirker dataaffinitet og nettverkstopologi allokering. Å bringe data nærmere de som behandler dem unngår forsinkelser og flaskehalserI delt minne er det lurt å unngå falsk deling, slik at mellombufferne fungerer i din favør, ikke mot deg.

Parallelle programmeringsmodeller

Dataparallalisme bruker den samme operasjonen på forskjellige elementer parallelt; Den er ideell for GPU-er og SIMDOppgavegrafen definerer noder med avhengigheter, slik at planleggere kan utføre det som allerede er klart uten å bryte rekkefølgen.

Mønsteret arbeidspool Den grupperer jobber i en kø; flere arbeidere bruker dem og produserer resultater. Styrken ligger i tilpasningsevnen: Hvis én oppgave tar lengre tid, går andre fremoverDen brukes i pipelines, servere og søkemotorer.

Valg av modell påvirker ikke bare ytelsen: det avgjør også hvor enkelt det er å resonnere om korrekthet og nøyaktighet. muligheten for å introdusere eller unngå blokkeringer, aktive ventetider og løpsforhold.

Trådbasert samtidighet og delt minne

I delt minne har flere tråder tilgang til samme adresserom. Dette tillater at data sendes via referanse uten kopiering, men krever at integriteten sikres. De vanligste verktøyene er Pthreads og OpenMPDen første tilbyr finjustert kontroll; den andre, direktiver på høyt nivå som er innebygd i kompilatoren.

Utfordringen er å skrive kode fri for kappløpsbetingelser. Vi må beskytte kritiske regioner med mutexer eller lese-skrive-låser, bruke betingelsesvariabler for å koordinere, og stole på barrierer og reduksjonsoperasjoner når det er passende.

Videre er det nødvendig å skille mellom reentrant- og ikke-reentrant-kode: reentrant-kode kan kjøres parallelt uten risiko hvis den ikke opprettholder global tilstand. Dette er et krav for å snakke ordentlig om trådsikker kode, som tåler samtidig utførelse uten å ødelegge data.

Samtidighet etter prosesser og distribuert minne

Når hver prosess har sitt eget minne, kommer biblioteker som MPI inn i bildet. Data deles ikke her: eksplisitte meldinger sendesDette øker robustheten mot feil i delt minne, på bekostning av økt kommunikasjonsoverhead.

MPI tilbyr både punkt-til-punkt (send/motta) og kollektiv (kringkasting, spredning, samling, alt-til-alle, reduksjon) kommunikasjon. Ved design er det viktig å være tydelig på kravene til parallell I/O: Et godt disktilgangsmønster kan være banebrytende ved intensive databelastninger.

Horisontal skalerbarhet er dens naturlige terreng: hvis problemet vokser, legger vi til flere noder. Nettverkslatens og kollektiv synkronisering krever imidlertid algoritmer som begrense ventetider og favorisere lokal databehandling.

Synkronisering: vanlige mekanismer og feller

For å koordinere tråder eller prosesser bruker vi synkroniseringsprimitiver. I delt minne er de klassiske mutex, semaforer, lese-skrive-låser og betingelsesvariabler. På et høyere nivå bruker vi barrierer og reduksjoner for globale møtepunkter.

Travel venting har et dårlig rykte, og med god grunn: Den bruker opp CPU-en uten å gjøre noe nyttig arbeid.Det er bare berettiget i scenarier med minimal ventetid og svært kort varighet. Vi foretrekker generelt å blokkere ventetider som frigjør CPU-en til det er arbeid som må gjøres.

Typiske problemer inkluderer fastlåste tråder, fastlåste tråder (ingen gjør fremskritt selv om alle beveger seg), sult (noen tråder gjør aldri fremskritt) og dårlig styrte prioriteringer. Design med total orden i ressursanskaffelse og rimelige ventetider bidrar til å unngå dem.

Korrekthetstesting i samtidige programmer

Testing av samtidig programvare er ikke trivielt fordi feil kan være ikke-deterministiske. Det finnes imidlertid strategier. Black-box-testing validerer grensesnittet og observerbar oppførsel; hvite bokser tvinger betong mellomlegg å avsløre løp og blokkeringer.

Verktøy for deteksjon av datakappløp, statisk analyse og modellsjekk er gode allierte. I tillegg er det tilrådelig å injisere feil (f.eks. legge til tilfeldig små ventetider) i øke sannsynligheten for å avdekke problematiske sammenflettede deler under prøvene.

I distribuerte prosesser er kommunikasjonstesting og simulering av nettverkspartisjoner avgjørende. Og glem aldri å registrere nøyaktig: god sporing av arrangementer og tid Det er rent gull når det gjelder raffinering.

Ytelsesmålinger: hastighetsøkning, effektivitet og skalerbarhet

For å objektivt evaluere bruker vi standardmålinger. Hastighetsøkning måler hvor mye et parallelt program akselererer sammenlignet med et serieprogram. Effektivitet normaliserer denne hastighetsøkningen med antall ressurser, noe som indikerer hvor stor andel av kapasiteten bruker vi.

Amdahls lov minner oss om at den ikke-parallelliserbare seksjonen begrenser den maksimale hastighetsøkningen: selv om du legger til uendelige ressurser, den sekvensielle delen setter et takParallelt tilbyr Gustafsons lov et annet perspektiv når problemets størrelse vokser med ressursene.

Skalerbarhet beskriver hvordan ytelsen endres med økende data og ressurser. Vi skiller mellom sterk skalerbarhet (løst problem, flere ressurser) og svak skalerbarhet (problemet vokser etter hvert som ressursene øker). Begge De krever grundig måling av veggtid (veggklokke) og presenter resultatene i tydelige grafer.

Praktiske krav og kostnader

I parallellisme er det maskinvaren som gjelder: for å kjøre flere oppgaver samtidig kreves det flere kjerner eller maskiner. Dette medfører kostnader og driftsmessig kompleksitet. I samtidighet derimot, du kan forbedre responsiviteten på en enkelt kjerne, med mindre investering, hvis du designer godt.

Ikke la deg lure: ikke all parallellisme akselererer. Hvis kommunikasjon eller synkronisering dominerer, Overbelastning kan spise opp fordeleneDerfor insisterer vi så sterkt på dekomponering, kartlegging og valg av riktig modell for hvert problem.

Klassiske casestudier og mønstre

Kanoniske øvelser finnes av en grunn: de lærer bort koordinasjonsmønstre og fallgruvene man bør unngå. Produsent-forbruker illustrerer køer, signaler og mottrykk. Kommensale filosofer avslører fastlåste situasjoner og hvordan bryt symmetrier for å unngå dem.

Problemene med røykere, frisøren og julenissen tvinger oss til å tenke på forskrifter, varsler og rettferdighet. Å danne vann lærer oss atomkombinasjoner og barrierer å justere enheter. Modus Hall (i sin klassiske formulering) er en annen unnskyldning for å praktisere disse mekanismene.

Å kombinere disse mønstrene med gode biblioteker (Pthreads, OpenMP, MPI) og solid testing forbereder deg på det virkelige liv: webtjenester med høy samtidighet, vitenskapelig databehandling som klemmer kjernene og distribuerte datarørledninger.

Når alt dette brukes klokt, blir resultatet raskere, mer skalerbar og brukervennlig programvare. Nøkkelen er å vite når samtidighet er best for deg, når parallellisme er best for deg, og fremfor alt hvordan du bruker det. få dem til å leve sammen uten å tråkke hverandre på tærne i en gjennomtenkt arkitektur.

Når man ser på det store bildet, lar samtidighet deg utføre flere oppgaver samtidig og reagere raskere, selv med en enkelt kjerne gjennom alternering, mens parallellisme øker ytelsen ved å løse en enkelt oppgave samtidig på flere dataenheter; med passende dekomponerings-, kartleggings-, synkroniserings- og testteknikker, og støttet av modeller som dataparallellisme, oppgavegrafer eller arbeidspooling. Det er mulig å designe systemer som håndterer mye belastning og som også kjører raskere. uten å miste korrektheten.