Automatisk parallellisering , også automatisk parallellisering , autoparallellisering eller parallellisering , refererer til å gjøre sekvensiell kode flertrådet eller vektorisert (eller begge deler) for å bruke flere prosessorer samtidig i en delt minne multiprosessor ( SMP ) maskin. Nytten med automatisk parallellisering er å frigjøre programmerere fra den kjedelige og feilutsatte prosessen med manuell parallellisering. Selv om kvaliteten på parallell automatisering har forbedret seg de siste tiårene, er en fullstendig automatisk parallellisering av sekvensielle programmer av en kompilator fortsatt en stor utfordring, siden det krever kompleks beregningsanalyse og ukjente faktorer (som rekkevidden av datainndata) under kompilering . [ 1 ]
Programmeringskontrollstrukturene som autoparallellisering fokuserer på er løkker , siden det meste av programmets utførelsestid generelt foregår inne i en løkke. En parallell kompilator forsøker å partisjonere en løkke slik at dens iterasjoner kan utføres på separate mikroprosessorer samtidig.
Kompilatoren utfører normalt to analyseringssykluser før en parallellisering for å bestemme følgende:
I det første trinnet utfører kompilatoren en avhengighetsanalyse av løkken for å bestemme om hver iterasjon av løkken kan utføres uavhengig av de andre. Dataavhengighet kan noen ganger håndteres ved meldingsoverføring , synkronisering av delt minne eller en annen metode for kommunikasjon mellom prosessorer, men kan øke overhead.
Det andre trinnet prøver å rettferdiggjøre parallelliseringsinnsatsen, ved å sammenligne den teoretiske utførelsestiden til den parallelliserte koden med utførelsestiden til den sekvensielle koden. Selv om det virker kontraproduktivt, har ikke kode alltid fordel av parallell kjøring. Den ekstra arbeidsbelastningen som kan være forbundet med bruk av flere prosessorer kan oppheve den mulige økningen i hastigheten på utførelse av parallell kode.
Fortran -koden nedenfor kan autoparallelleres av en kompilator fordi hver iterasjon er uavhengig av de andre, og det endelige resultatet av vektoren zvil være korrekt uavhengig av utførelsesrekkefølgen til iterasjonene.
do i = 1 , n z ( i ) = x ( i ) + y ( i ) enddoPå den annen side kan følgende kode ikke autoparallelleres, fordi verdien av z(i)avhenger av resultatet av forrige iterasjon, z(i-1).
do i = 2 , n z ( i ) = z ( i - 1 ) * 2 enddoDette betyr ikke at det ikke kan parallelliseres. Faktisk tilsvarer det
do i = 2 , n z ( i ) = z ( 1 ) * 2 ** ( i - 1 ) enddoNåværende parallellkompilatorer er imidlertid ikke i stand til å oppnå disse parallelliseringene automatisk, og det er tvilsomt om denne koden kan dra nytte av parallellisering.
Automatisk parallellisering av kompilatorer eller verktøy er veldig komplisert på grunn av følgende årsaker:
På grunn av vanskelighetene som ligger i full automatisk parallellisering, er det flere enklere tilnærminger for å oppnå et parallellprogram av høyere kvalitet, for eksempel:
De fleste forskere på kompilatorer for automatisk parallellisering foretrekker Fortran -programmer , [ nødvendig referanse ] fordi Fortran tilbyr bedre aliasing - garantier enn andre språk som C. Typiske eksempler er: