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

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

Hvis du jobber i utviklingsverdenen, 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 tar sikte på å 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 for langt, er det verdt å merke seg at selv om de ofte brukes om hverandre i dagligspråket, er de ikke synonyme. Samtidighet beskriver faktisk hvordan vi strukturerer og koordinerer oppgaver som sameksisterer , mens parallellisme refererer til å utføre flere av disse oppgavene samtidig på maskinvare som er i stand til å gjøre det. La oss herfra bryte det ned nøye 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 jobber som kjører i overlappende sekvenser. Dette kan skje på en enkelt CPU uten å faktisk utføre flere instruksjoner samtidig: systemet veksler mellom oppgaver (interleaving) slik at alle går videre , noe som reduserer ventetider og forbedrer brukeropplevelsen. Det er en tilnærming til programvaredesign og koordinering.

Parallelisme, derimot, er basert på ideen om splitt og hersk: vi deler opp et stort problem i delproblemer og behandler disse delene samtidig på flere dataenheter (kjerner, prosessorer eller noder). Her er det ekte parallell utførelse; derfor avhenger ytelsen sterkt av tilgjengelig maskinvare.

I praksis er begge 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 på utførelse . De 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 er denne samtidigheten vanligvis bare synlig på maskiner med én kjerne , takket være rask kontekstbytte; ekte samtidighet tilsvarer parallellisme og krever flere prosesseringsenheter.

Viktige forskjeller og maskinvarekrav

En praktisk forskjell ligger i systemkravene. Ekte parallellisme krever flere dataenheter: flere kjerner, prosessorer eller maskiner ; mens samtidighet kan implementeres på en enkelt kjerne ved å bytte oppgaver. Dette påvirker direkte maskinvarekostnadene.

Hovedformålet er også forskjellig: mens samtidighet reduserer opplevd latens og forbedrer et systems respons ved å administrere flere pågående oppgaver, søker parallellisme å øke hastigheten på 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 i et siste trinn. I samtidige oppgaver kan oppgaver være uavhengige og ikke avhenge av hverandre ; hver av dem utvikler seg i sitt eget tempo og vil fullføres 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 sameksisterende enheter og hvordan de kommuniserer, mens parallellisme handler om hvordan man utfører disse enhetene i harmoni for å oppnå bedre ytelse . Man kan ha samtidighet uten parallellisme (en enkelt kjerne som veksler mellom oppgaver) og parallellisme uten mye samtidighet (ren databehandling 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 ikke påvirker de andre ; hvis én er treg, bremser den ikke ned resten. Det er et typisk samtidighetsscenario: flere oppgaver sameksisterer og fremskrider, muligens vekslende CPU-bruk på samme kjerne.

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

En viktig observasjon i parallellisme er trinnet med sammenslåing av resultater. Etter at problemet er delt opp, må det være en kombinasjonsfase som integrerer de delvise svarene til en endelig løsning . Uten dette trinnet leverer ikke parallellisme et komplett produkt.

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

Maskinvare- og programvaremodeller: En oversikt

For å forstå mulighetene er det nyttig å se på landskapet til parallell maskinvare og programvaren som utnytter den. Når det gjelder maskinvare, finnes det forskjellige nivåer av parallellitet : fra flere kjerner på en enkelt prosessor til klynger av maskiner med distribuert minne. Flynns hierarki 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 adresseområde, mens flere tråder deler minne innenfor samme prosess . Å velge den ene eller den andre innebærer beslutninger om kommunikasjons-, isolasjons- og synkroniseringskostnader.

Driftsmessig er tråder lette og raske for deling av data, men de krever ekstrem forsiktighet med tanke på minneintegritet. Prosesser, derimot, 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 opplæringsprogram i samtidig og parallell programmering er vanligvis organisert i store blokker. Den første er Forstå motivasjoner og trender: hvorfor vi trenger parallell databehandling , hvilke ansvarsområder som letter design, og hvordan ytelse påvirker beslutninger.

Parallell maskinvare dekker modeller og hierarkier, inkludert Flynns taksonomi, GPU-er og flerkjerne-/NUMA-systemer. Den parallelle programvaremodulen tar for seg konseptene prosesser og tråder , deres API-er og hvordan man organiserer adresserom og delt eller distribuert minne.

Det andre fokuset er på å 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 samtidighet og kommunikasjon.

Dekomponeringsteknikker dekkes også: rekursive, datadrevne, utforskende, spekulative og andre. Uten riktig dekomponering kompenserer ikke parallellisme for overhead . Videre må oppgaver kartlegges til prosesser eller tråder, balansere belastningen og minimere interaksjon.

Denne aksen inkluderer de mest brukte parallelle programmeringsmodellene: dataparallelisme (samme operasjon på flere elementer), oppgavegrafer (eksplisitte avhengigheter) og arbeidspoolmønsteret ( et sett med jobber som tråder forbruker dynamisk). Disse modellene hjelper med å forstå distribusjon og synkronisering.

Den tredje delen fokuserer på å løse typiske synkroniserings- og koordinasjonsproblemer. Her studeres symbolske tilfeller, som produsent-forbruker-problemet, spisestedsfilosofene, røykerproblemet, barbershopproblemet, julenisseproblemet, vanndannelse og Modus Hall-problemet. Hver av dem illustrerer farer som sult, fastlåste forhold og raseforhold.

De følgende avsnittene fokuserer på å bygge samtidige programmer med delte ressurser (etter tråder) og bygge samtidige programmer med distribuerte ressurser (etter prosesser). Den første delen dekker grensesnitt som Pthreads og OpenMP , forklarer det vanlige adresserommet og lærer hvordan man sporer minne- og trådaktivitet.

Den andre delen tar for seg prosesssamtidighet med distribuert minne og API-er som MPI. Parallell input og output studeres , samt punkt-til-punkt og kollektiv kommunikasjon (broadcast, scatter, gather, all-reduce). Minne- og prosesssporing øves også.

Til slutt er det inkludert seksjoner om programvaretesting, evaluering og sammenligning. Testing dekker black-box- og white-box-teknikker tilpasset samtidighet og distribusjon. Evaluering dekker Amdahls lov, hastighetsøkningsmålinger, effektivitet og skalerbarhet , måling av veggtid og grafisk visualisering.

Dekomponeringsteknikker: hvordan man kan bryte ned problemet

Å velge hvordan man skal fordele arbeidet utgjør forskjellen mellom å oppnå og miste ytelse. Datadekomposisjon tilordner delsett av datasettet til forskjellige utførende parametre; det fungerer utmerket for homogene operasjoner som å bruke et filter på piksler eller iterere gjennom lister.

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

Spekulativ dekomponering kjører alternative baner eller antagelser parallelt, og aksepterer at noen beregninger vil være bortkastet hvis de ikke var nødvendige . Det er nyttig når vi forutsier at flere grener kan være gyldige, men ikke vet hvilken a priori.

Uansett hvilken teknikk som brukes, må koordineringskostnaden vurderes: hvis den er for høy, mister parallellitet sin effektivitet . Derfor er arbeidsgranularitet nøkkelen: oppgaver bør ikke være for små eller så store at de skaper ubalanse i arbeidsmengden.

Oppgavekartlegging og lastbalansering

Når arbeidsmengdefordelingen er bestemt, er neste trinn å tilordne oppgaver til prosesser eller tråder. Statisk kartlegging fordeler arbeidet på forhånd; det er enkelt og rimelig , men det kan bli ubalansert hvis oppgavene er uregelmessige. Dynamisk kartlegging (eller arbeidstyveri ) tillater justeringer underveis.

Lastbalansering har som mål å sikre at alle prosesservere er rimelig opptatt. Dette oppnås gjennom delte eller lokale køer med jobbtyveri. I tillegg er det nødvendig å redusere overhead for samhandling mellom oppgaver ved å minimere kommunikasjon og kritiske områder.

I distribuerte miljøer påvirker dataaffinitet og nettverkstopologi allokering. Å bringe data nærmere prosessoren unngår latens og flaskehalser . I delt minne bør falsk deling unngås, slik at mellombuffere fungerer i favør av, snarere enn mot, dataene.

Parallelle programmeringsmodeller

Dataparallalisme bruker den samme operasjonen på forskjellige elementer parallelt; det er ideelt for GPU-er og SIMD . Oppgavegrafen definerer noder med avhengigheter, noe som gjør det mulig for planleggere å utføre det som allerede er klart uten å bryte rekkefølgen.

Arbeidspoolmønsteret 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 videre i mellomtiden . Det brukes i pipelines, servere og søkemotorer.

Valg av modell påvirker ikke bare ytelsen: det bestemmer også hvor enkelt det er å resonnere om korrekthet og evnen til å introdusere eller unngå blokkering , aktive ventinger og kapplø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 dataintegriteten sikres. De vanligste verktøyene er Pthreads og OpenMP : førstnevnte tilbyr finjustert kontroll; sistnevnte gir overordnede direktiver integrert i kompilatoren.

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

Videre er det viktig å skille mellom reentrant- og ikke-reentrant-kode: reentrant-kode kan kjøres parallelt trygt hvis den ikke opprettholder global tilstand. Dette er et krav for å kunne snakke om trådsikker kode , som tåler samtidig kjøring uten å ødelegge data.

Samtidighet etter prosesser og distribuert minne

Når hver prosess har sitt eget minne, kommer biblioteker som MPI inn i bildet. Her deles ikke data: eksplisitte meldinger sendes . Dette øker robustheten mot feil i delt minne, på bekostning av mer kommunikasjonsarbeid.

MPI tilbyr punkt-til-punkt-kommunikasjon (send/motta) og kollektiv kommunikasjon (kringkasting, spredning, samling, alt-til-alle og reduksjon). Ved design er det viktig å forstå kravene til parallell I/O tydelig: et godt designet disktilgangsmønster kan være banebrytende for dataintensive arbeidsbelastninger.

Horisontal skalerbarhet er dens naturlige habitat: hvis problemet vokser, legger vi til flere noder. Nettverkslatens og kollektiv synkronisering krever imidlertid algoritmer som begrenser ventetider og favoriserer lokal beregning.

Synkronisering: vanlige mekanismer og feller

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

Opptatt venting har et dårlig rykte, og med rette: det opptar CPU-ressurser uten å utføre noe nyttig arbeid . Det er bare berettiget i scenarier med minimal ventetid og svært kort varighet. Generelt foretrekker vi å blokkere venting som frigjør CPU-en til arbeid blir tilgjengelig.

Typiske problemer inkluderer fastlåste tråder, fastlåste tråder (ingen gjør fremskritt selv om alle beveger seg), sult (noen tråder går aldri videre) og dårlig styrte prioriteringer. Å designe med streng rekkefølge i ressursanskaffelse og rimelige ventetider bidrar til å unngå disse.

Korrekthetstesting i samtidige programmer

Testing av samtidig programvare er ikke trivielt fordi feil kan være ikke-deterministiske. Likevel finnes det strategier. Black-box-testing validerer grensesnittet og observerbar oppførsel, mens white-box-testing tvinger frem spesifikke sammenflettede elementer for å avdekke kappløp og vranglåser.

Verktøy for å oppdage datarace, statisk analyse og modellsjekk er uvurderlige. I tillegg anbefales det å injisere feil (for eksempel ved å legge til tilfeldige små ventetider) for å øke sannsynligheten for å avdekke problematiske interleavinger under testing.

I distribuerte prosesser er kommunikasjonstesting og simulering av nettverkspartisjonering avgjørende. Og glem aldri å logge nøyaktig: gode hendelses- og tidsspor er uvurderlige når det gjelder feilsøking.

Ytelsesmålinger: hastighetsøkning, effektivitet og skalerbarhet

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

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

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

Praktiske krav og kostnader

I parallellisme dikterer maskinvare ytelsen: for å virkelig utføre flere oppgaver samtidig, trenger du flere kjerner eller maskiner. Dette medfører kostnader og driftsmessig kompleksitet. I samtidighet, derimot, kan du forbedre responsen på en enkelt kjerne , med mindre investering, hvis du designer den godt.

Ikke la deg lure: ikke all parallellisme akselererer fremdriften. Hvis kommunikasjon eller synkronisering dominerer, kan overbelastning oppheve fordelene . Derfor legger vi vekt 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. Serveringsfilosofer avslører fastlåste situasjoner og hvordan man kan bryte symmetrier for å unngå dem.

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

Ved å kombinere disse mønstrene med gode biblioteker (Pthreads, OpenMP, MPI) og solid testing forberedes du for virkelige applikasjoner: webtjenester med høy samtidighet, kjernepressende vitenskapelig databehandling og distribuerte datapipeliner.

Når alt dette brukes intelligent, blir resultatet raskere, mer skalerbar og brukervennlig programvare. Nøkkelen er å vite når samtidighet er passende, når parallellisme er nødvendig, og fremfor alt hvordan man får dem til å sameksistere uten konflikt i en godt designet arkitektur.

Når man ser på helhetsbildet, lar samtidighet deg utføre flere oppgaver samtidig og reagere raskt, selv med en enkelt kjerne gjennom svitsjering, mens parallellisme øker ytelsen ved å løse en enkelt oppgave samtidig på flere dataenheter. Med passende dekomponerings-, kartleggings-, synkroniserings- og testteknikker, og ved å stole på modeller som dataparallelisme, oppgavegrafer eller arbeidspool, er det mulig å designe systemer som håndterer mye arbeidsmengde og i tillegg kjører raskere uten å miste korrekthet.