Pipeline - en metod för att organisera beräkningar som används i moderna processorer och styrenheter för att öka deras prestanda (öka antalet instruktioner som exekveras per tidsenhet - drift av parallellism på instruktionsnivå ), en teknik som används vid utveckling av datorer och andra digitala elektroniska apparater.
Tanken är att utföra flera processorinstruktioner parallellt. Komplexa processorinstruktioner representeras som en sekvens av enklare steg. Istället för att exekvera instruktioner sekventiellt (vänta på att slutet av en instruktion ska slutföras och gå vidare till nästa), kan nästa instruktion exekveras genom flera stadier av exekvering av den första instruktionen. Detta gör att processorns kontrollkedjor kan ta emot instruktioner med hastigheten för det långsammaste bearbetningsstadiet, men samtidigt mycket snabbare än att utföra exklusiv fullständig bearbetning av varje instruktion från början till slut.
Illustrationen till höger visar en enkel fem-nivå pipeline i RISC-processorer . Här:
Den vertikala axeln är sekventiella oberoende instruktioner, den horisontella axeln är tid. Den gröna kolumnen beskriver tillståndet för processorn vid en tidpunkt, i den är den tidigaste, övre instruktionen redan i tillståndet att skriva till registret, och den senaste, lägre instruktionen är endast under läsning.
Själva termen "transportör" kom från industrin, som använder en liknande funktionsprincip - materialet dras automatiskt längs transportbandet till arbetaren, som utför de nödvändiga åtgärderna med det, arbetaren som följer honom utför sina funktioner på den resulterande arbetsstycket gör nästa något annat. Så vid slutet av pipelinen slutför kedjan av arbetare alla tilldelade uppgifter och upprätthåller en hög produktionstakt. Till exempel, om den långsammaste operationen tar en minut, kommer varje del att lämna löpande bandet på en minut. I processorer utförs arbetarnas roll av funktionella moduler som är en del av processorn.
Den enklaste formen av överlappande instruktionsexekvering i tid implementerades i Z3 -maskinen av Konrad Zuse 1941 [2] .
Rör liten ETSVM " Ural " ( 1957 , USSR ) hade en tvåstegs transportör av operationer. [3]
Flerstegstransportörer i modern uppfattning implementerades i Anatoly Ivanovich Kitovs M - 100- maskin (1959, USSR) [ specificera ] [4] , UNIVAC LARC (1960, USA), IBM Stretch (1961, USA) [5] , Atlas (1962, Storbritannien) och BESM-6 (1967, USSR). I IBM Stretch-projektet föreslogs termerna "fetch" ( eng. Fetch ), "decoding" ( eng. Decode ) och "execution" ( eng. Execute ), som sedan blev vanligt förekommande.
Många moderna processorer styrs av en klockgenerator. Processorn inuti består av logiska element och minnesceller - flip- flops . När signalen från klockgeneratorn anländer tar flip-flopsna sitt nya värde och "logiken" tar lite tid att avkoda de nya värdena. Sedan kommer nästa signal från klockgeneratorn, vipporna tar nya värden och så vidare. Genom att bryta upp sekvenserna av logiska element i kortare sekvenser och placera vippor mellan dessa korta sekvenser, reduceras den tid som krävs för att logiken ska behandla signaler. I detta fall kan varaktigheten av en processorcykel reduceras i enlighet därmed.
Till exempel kan den enklaste pipelinen av RISC-processorer representeras av fem steg med uppsättningar triggers mellan stegen:
Situationer, kallade pipeline conflicts ( engelska hazards ), förhindrar exekvering av nästa instruktion från instruktionsströmmen i den cykel som är avsedd för den. Kollisioner minskar den verkliga hastigheten i pipelineprestanda och kan få pipelinen att stanna . Konfliktlösning kräver att vissa instruktioner i pipelinen tillåts fortsätta att utföras medan andra är försenade.
Det finns tre klasser av konflikter [6] .
Strukturella konflikter uppstår på grund av resurskonflikter, när hårdvaran inte kan stödja alla möjliga kombinationer av samtidigt exekverade instruktioner [7] . Om någon kombination av instruktioner inte kan stödjas, sägs processorn ha en strukturell konflikt . Oftast uppstår strukturella konflikter när något funktionellt block inte är fullt utvecklat. Till exempel delar vissa processorer en enda minnespipeline för data och instruktioner. Som ett resultat, när en instruktion innehåller en dataminnesåtkomst, kommer den i konflikt med en senare instruktion. För att lösa denna konflikt vid åtkomst till minne för data pausar pipelinen i en cykel.
Som ett alternativ till en sådan strukturell konflikt kan utvecklaren tillhandahålla separat åtkomst till instruktionsminnet antingen genom att dela upp cachen i separata instruktionscacher och datacache, eller genom att använda flera buffertar som kallas instruktionsbuffertar för att lagra instruktioner, men detta görs inte för att för att undvika att kostnaden för blocket ökar [ 8] .
Datakonflikter uppstår när ett kommandos beroende av resultatet från ett tidigare dyker upp när kommandon kombineras i en pipeline. Dessa konflikter uppstår när pipelinen ändrar ordningen för läs-/skrivåtkomster till operander så att den skiljer sig från den ordning som finns för sekventiellt exekverade instruktioner i en processor utan pipeline. Det finns en datakonfliktlösningsmetod: vidarebefordran ( engelsk register forwarding ) (kallas ibland bypass ) [9] . Tyvärr kan inte alla potentiella datakonflikter hanteras med en bypass, i vilket fall pipelinen avbryts tills konflikten är löst.
Kontrollkonflikter uppstår vid exekvering av villkorliga överföringar och andra instruktioner som ändrar värdet på programräknaren . Det finns många sätt att hantera ett pipelinestopp orsakat av kontrollöverföringsfördröjning, men djupa pipelines tenderar att använda aggressiva verktyg [10] såsom kontrollöverföringsförutsägelse .
Den pipelinelösa arkitekturen är mycket mindre effektiv på grund av mindre belastning av processorns funktionsmoduler medan en eller ett litet antal moduler utför sin funktion under instruktionsbearbetning. Pipelinen eliminerar inte helt vilotiden för moduler i processorer och minskar inte exekveringstiden för varje specifik instruktion, men den tvingar processormodulerna att arbeta parallellt med olika instruktioner, vilket ökar antalet instruktioner som exekveras per tidsenhet , och därmed programmets övergripande prestanda.
Processorer med en pipeline inuti är utformade så att behandlingen av instruktioner är uppdelad i en sekvens av steg, förutsatt att flera instruktioner behandlas samtidigt i olika steg. Resultaten av arbetet i vart och ett av stegen överförs genom minnescellerna till nästa steg, och så vidare tills instruktionen exekveras. En sådan organisation av processorn, med en liten ökning av den genomsnittliga exekveringstiden för varje instruktion, ger inte desto mindre en signifikant ökning av prestanda på grund av den höga frekvensen av instruktionsfullbordande.
Alla instruktioner är dock inte oberoende. I den enklaste pipelinen, där instruktionsbearbetningen representeras av fem steg, för att säkerställa full laddning, medan bearbetningen av den första instruktionen är slutförd, bör i idealfallet ytterligare fyra på varandra följande oberoende instruktioner behandlas parallellt. Om sekvensen innehåller instruktioner som är beroende av de som för närvarande exekveras, avbryter kontrolllogiken för den enklaste pipelinen flera initiala steg i pipelinen, och placerar därigenom en tom instruktion ("bubbla") i pipelinen, ibland upprepade gånger, tills beroendet är löst. Det finns ett antal knep, såsom vidarebefordran, som kraftigt minskar behovet av att pausa en del av pipelinen i sådana fall. Beroendet mellan instruktioner som behandlas samtidigt av processorn tillåter emellertid inte att uppnå en prestandaökningsmultipel av antalet pipelinesteg i jämförelse med en pipelinelös processor.
Rörledningen hjälper inte i alla fall. Det finns flera möjliga nackdelar. En instruktionspipeline kan kallas "fullständig pipelined" om den kan acceptera en ny instruktion varje maskincykel . Annars måste förseningar tvingas in i rörledningen som plattar ut rörledningen samtidigt som den försämrar dess prestanda.
Fördelar:
Brister:
Till höger finns en allmän pipeline med fyra arbetssteg:
Det övre grå området är en lista över instruktioner som ska utföras. Det nedre grå området är en lista över instruktioner som redan har utförts. Och det vita mittområdet är själva rörledningen.
Utförandet går till så här:
| Cykel | Åtgärder |
|---|---|
| 0 | Fyra instruktioner väntar på att verkställas |
| ett |
|
| 2 |
|
| 3 |
|
| fyra |
|
| 5 |
|
| 6 |
|
| 7 |
|
| åtta |
|
| 9 | Alla instruktioner har följts |
För att lösa pipelinekonflikter tvingas processorn att fördröja behandlingen av instruktionen genom att skapa en "bubbla" i pipelinen. Bubblans passage genom ställdonen åtföljs inte av något användbart arbete. I den andra cykeln fördröjs behandlingen av den lila instruktionen, och det finns nu en bubbla i avkodningssteget i den tredje cykeln. Alla instruktioner "efter" den lila instruktionen fördröjs med en cykel, medan instruktionerna "före" den lila instruktionen fortsätter att utföras.
Uppenbarligen ger närvaron av en bubbla i pipelinen en total exekveringstid på 8 cykler istället för 7 i exekveringsdiagrammet som visas ovan.
Ställdonen måste utföra någon åtgärd på varje cykel. Bubblor är ett sätt att skapa en fördröjning i behandlingen av en instruktion utan att stoppa pipelinen. När de exekveras sker inget användbart arbete i stadierna av hämtning, avkodning, exekvering och skrivning av resultatet. De kan uttryckas med NOP [11] [12] [13] assemblerinstruktionen .
Låt oss säga att en typisk instruktion för att lägga till två tal är СЛОЖИТЬ A, B, C. Denna instruktion lägger till värdena i minnesplatserna A och B och placerar sedan resultatet i minnesplats C . I en pipelined processor kan styrenheten dela upp denna operation i sekventiella uppgifter av formuläret
LADDA A , R1 LADDA B , R2 LÄGG TILL R1 , R2 , R3 SKRIV R3 , C ladda nästa instruktionCellerna R1 , R2 och R3 är processorregister . _ Värdena som är lagrade i minnesplatser, som vi kallar A och B , laddas (det vill säga kopieras) till dessa register, summeras sedan och resultatet skrivs till minnesplats C .
I det här exemplet består pipelinen av tre nivåer - laddning, exekvering och skrivning. Dessa steg kallas uppenbarligen nivåer eller pipeline-steg .
I en pipelinelös processor kan bara ett steg köras åt gången, så en instruktion måste slutföras helt innan nästa instruktion ens kan börja. I en pipelined processor kan alla dessa steg utföras samtidigt på olika instruktioner. Så när den första instruktionen är i exekveringssteget, kommer den andra instruktionen att vara i avkodningssteget och den tredje instruktionen kommer att vara i lässteget.
Pipelinen minskar inte tiden det tar att exekvera en instruktion, men den ökar mängden (antalet) instruktioner som kan exekveras samtidigt, och minskar därmed fördröjningen mellan exekverade instruktioner - ökar den sk. genomströmning . Ju fler lager en pipeline har, desto fler instruktioner kan utföras samtidigt och desto mindre fördröjning mellan slutförda instruktioner. Varje mikroprocessor som tillverkas idag använder minst en två-nivå pipeline.
Teoretisk pipeline med tre nivåer:
| Steg | engelsk titel | Beskrivning |
|---|---|---|
| Prov | Hämta | Läs instruktioner från minnet |
| Avrättning | Kör | Utför instruktion |
| Inspelning | Skriv tillbaka | Skriv resultat till minnet och/eller register |
Pseudo-assembler-listning som ska köras:
LAST 40, A ; ladda nummer 40 i A KOPIA A , B ; kopia A till B ADD 20, B ; lägg till 20 till B SKRIV B , 0x0300 ; skriv B till minnesplats 0x0300Hur det kommer att utföras:
| Takt | Prov | Avrättning | Inspelning | Förklaring |
|---|---|---|---|---|
| Åtgärd 1 | LADDA NER | LOAD-instruktionen läses från minnet. | ||
| Åtgärd 2 | KOPIERA | LADDA NER | LOAD-instruktionen exekveras, COPY-instruktionen läses från minnet. | |
| Åtgärd 3 | VIKA IHOP | KOPIERA | LADDA NER | LOAD-instruktionen är i skrivresultatsteget, där dess resultat (det vill säga talet 40 ) skrivs till register A. Samtidigt exekveras COPY-instruktionen. Eftersom den måste kopiera innehållet i register A till register B , måste den vänta till slutet av LOAD-instruktionen. |
| Åtgärd 4 | SPELA IN | VIKA IHOP | KOPIERA | WRITE-instruktionen laddas, medan COPY-instruktionen säger adjö till oss, och ADD-instruktionen beräknas för närvarande. |
Och så vidare. Observera att instruktioner ibland beror på resultatet av andra instruktioner (som vår COPY-instruktion, till exempel). När mer än en instruktion hänvisar till en specifik plats, antingen genom att läsa den (det vill säga använda den som en ingångsoperand) eller genom att skriva till den (det vill säga använda den som en utgångsoperand), utförs inte instruktionerna i ordningen som ursprungligen var avsedd i det ursprungliga programmet. , kan orsaka en pipeline-konflikt , (som nämnts ovan). Det finns flera beprövade tekniker för att antingen förhindra konflikter eller åtgärda dem om de uppstår.
Många system inkluderar pipelines med 7, 10 eller till och med 20 nivåer (som till exempel i Pentium 4-processorn ). Sen Pentium 4-kärnor med kodnamnet Prescott och Cedar Mill (och deras Pentium D- derivat) har en 31-nivå pipeline.
Xelerator X10q-processorn har en pipeline som är över tusen steg lång [14] . Baksidan av myntet i det här fallet är behovet av att återställa hela pipelinen om programflödet har ändrats (till exempel genom ett villkorligt uttalande). Branch prediktorer försöker lösa detta problem . Branch förutsägelse i sig kan bara göra saken värre om förutsägelsen görs dåligt. I vissa applikationer, såsom supercomputing , är program specifikt skrivna för att använda villkorade uttalanden så lite som möjligt, så mycket långa pipelines kommer att ha en mycket positiv effekt på den totala hastigheten för beräkningar, eftersom långa pipelines är utformade för att minska CPI ( antal cykler) till instruktionen ).
Om förgrening sker hela tiden, kommer en omarrangering av maskininstruktionerna att bidra till att avsevärt minska hastighetsförlusten: de instruktioner som sannolikt behövs placeras i pipelinen. Denna metod är mer effektiv än att behöva återställa pipelinen helt varje gång. Program som gcov kan användas för att bestämma hur ofta enskilda grenar faktiskt exekveras, med hjälp av en teknik som kallas kodtäckningsanalys . Även om i praktiken är en sådan analys den sista åtgärden i optimering.
Den höga genomströmningen av pipelines leder till en minskning av prestanda om den körbara koden innehåller många villkorliga hopp: processorn vet inte var den ska läsa nästa instruktion från och måste därför vänta på att den villkorliga hoppinstruktionen ska sluta, vilket lämnar en tom rörledning bakom den. När grenen har passerats och det är känt var processorn behöver hoppa till nästa, måste nästa instruktion gå hela vägen genom pipelinen innan resultatet är tillgängligt och processorn "fungerar" igen. I ett extremt fall kan prestandan för en pipelined processor teoretiskt sett sjunka till den för en pipelinelös processor, eller till och med vara sämre på grund av det faktum att endast en nivå av pipeline är upptagen och det finns en liten fördröjning mellan nivåerna.
Om processorn är utrustad med en pipeline exekveras inte koden som läses från minnet omedelbart, utan placeras i en kö ( prefetch input queue ). Om koden som finns i minnet ändras kommer koden som finns i pipelinekön att förbli densamma. Instruktionerna i instruktionscachen kommer inte heller att ändras . Det bör beaktas att detta problem endast är typiskt för självmodifierande program och packare av körbara filer.
| Digital Processor Technologies | |||||||||
|---|---|---|---|---|---|---|---|---|---|
| Arkitektur | |||||||||
| Instruktionsuppsättning arkitektur | |||||||||
| maskinord | |||||||||
| Parallellism |
| ||||||||
| Genomföranden | |||||||||
| Komponenter | |||||||||
| Energihantering | |||||||||