Pipeline - en metode til at organisere beregninger, der bruges i moderne processorer og controllere for at øge deres ydeevne (øge antallet af instruktioner, der udføres pr. tidsenhed - drift af parallelisme på instruktionsniveau ), en teknologi, der bruges i udviklingen af computere og andre digitale elektroniske enheder.
Ideen er at udføre flere processorinstruktioner parallelt. Komplekse processorinstruktioner er repræsenteret som en sekvens af enklere trin. I stedet for at udføre instruktioner sekventielt (vente på slutningen af en instruktion for at fuldføre og gå videre til den næste), kan den næste instruktion udføres gennem flere stadier af udførelse af den første instruktion. Dette gør det muligt for processorens kontrolkæder at modtage instruktioner med hastigheden af det langsomste behandlingstrin, men på samme tid meget hurtigere end at udføre eksklusiv fuld behandling af hver instruktion fra start til slut.
Illustrationen til højre viser en simpel fem-niveau pipeline i RISC-processorer . Her:
Den lodrette akse er sekventielle uafhængige instruktioner, den vandrette akse er tid. Den grønne kolonne beskriver processorens tilstand på et tidspunkt, i den er den tidligste, øverste instruktion allerede i tilstanden til at skrive til registret, og den seneste, nederste instruktion er kun i færd med at læse.
Selve udtrykket "transportør" kom fra industrien, som bruger et lignende driftsprincip - materialet trækkes automatisk langs transportbåndet til arbejderen, som udfører de nødvendige handlinger med det, arbejderen, der følger ham, udfører sine funktioner på den resulterende arbejdsemne, gør det næste noget andet. Ved slutningen af pipelinen afslutter kæden af arbejdere således alle de tildelte opgaver og opretholder en høj produktionshastighed. For eksempel, hvis den langsomste operation tager et minut, vil hver del forlade samlebåndet på et minut. I processorer udføres arbejdernes rolle af funktionelle moduler, der er en del af processoren.
Den enkleste form for overlappende instruktionsudførelse i tid blev implementeret i Z3 -maskinen af Konrad Zuse i 1941 [2] .
Tube lille ETSVM " Ural " ( 1957 , USSR ) havde en to-trins transportør af operationer. [3]
Flertrinstransportører i den moderne opfattelse blev implementeret i Anatoly Ivanovich Kitovs M -100- maskine (1959, USSR) [ specificer ] [4] , UNIVAC LARC (1960, USA), IBM Stretch (1961, USA) [5] , Atlas (1962, Storbritannien) og BESM-6 (1967, USSR). I IBM Stretch-projektet blev begreberne "fetch" ( eng. Fetch ), "decoding" ( eng. Decode ) og "execution" ( eng. Execute ) foreslået, som så blev almindeligt anvendte.
Mange moderne processorer styres af en urgenerator. Processoren indeni består af logiske elementer og hukommelsesceller - flip- flops . Når signalet fra clockgeneratoren ankommer, får flip-flops deres nye værdi, og "logikken" tager lidt tid at afkode de nye værdier. Så kommer det næste signal fra clockgeneratoren, flip-flopsene får nye værdier og så videre. Ved at opdele sekvenserne af logiske elementer i kortere sekvenser og placere flip-flops mellem disse korte sekvenser, reduceres den tid, der kræves for logikken til at behandle signaler. I dette tilfælde kan varigheden af en processorcyklus reduceres tilsvarende.
For eksempel kan den enkleste pipeline af RISC-processorer repræsenteres af fem trin med sæt triggere mellem trin:
Situationer, kaldet pipeline-konflikter ( engelske hazards ), forhindrer udførelsen af den næste instruktion fra instruktionsstrømmen i den cyklus, der er beregnet til den. Kollisioner reducerer den reelle hastighed i pipeline-ydelsen og kan få rørledningen til at stoppe . Konfliktløsning kræver, at nogle instruktioner i pipelinen får lov til at fortsætte med at udføre, mens andre er forsinkede.
Der er tre klasser af konflikter [6] .
Strukturelle konflikter opstår på grund af ressourcekonflikter, når hardwaren ikke kan understøtte alle mulige kombinationer af samtidigt udførte instruktioner [7] . Hvis en kombination af instruktioner ikke kan understøttes, siges processoren at have en strukturel konflikt . Oftest opstår strukturelle konflikter, når en eller anden funktionel blok ikke er fuldt pipelinet. For eksempel deler nogle processorer en enkelt hukommelsespipeline til data og instruktioner. Som et resultat, når en instruktion indeholder en datahukommelsesadgang, er den i konflikt med en senere instruktion. For at løse denne konflikt, når der tilgås hukommelse til data, pauser pipelinen i én cyklus.
Som et alternativ til en sådan strukturel konflikt kunne udvikleren give separat instruktionshukommelsesadgang enten ved at opdele cachen i separate instruktionscaches og datacaches eller ved at bruge flere buffere kaldet instruktionsbuffere til at gemme instruktioner, men dette gøres ikke for for at undgå at øge omkostningerne ved blokken [8] .
Datakonflikter opstår, når en kommandos afhængighed af resultaterne af en tidligere viser sig, når kommandoer kombineres i en pipeline. Disse konflikter opstår, når pipelinen ændrer rækkefølgen af læse-/skriveadgange til operander, så den adskiller sig fra den rækkefølge, der findes for sekventielt udførte instruktioner i en processor uden en pipeline. Der er en datakonfliktløsningsmetode: videresendelse ( engelsk registervideresendelse ) (nogle gange kaldet bypass ) [9] . Desværre kan ikke alle potentielle datakonflikter håndteres ved hjælp af en bypass, i hvilket tilfælde pipelinen suspenderes, indtil konflikten er løst.
Kontrolkonflikter opstår ved udførelse af betingede overførsler og andre instruktioner, der ændrer værdien af programtælleren . Der er mange måder at håndtere et rørledningsstop forårsaget af kontroloverførselsforsinkelse, men dybe rørledninger har en tendens til at bruge aggressive værktøjer [10] såsom forudsigelse af kontroloverførsel .
Den pipelineløse arkitektur er meget mindre effektiv på grund af mindre belastning af processorens funktionelle moduler, mens et eller et lille antal moduler udfører deres funktion under instruktionsbehandling. Pipelinen eliminerer ikke fuldstændig tomgangstiden for moduler i processorer og reducerer ikke eksekveringstiden for hver specifik instruktion, men den tvinger processormodulerne til at arbejde parallelt på forskellige instruktioner og øger derved antallet af instruktioner, der udføres pr. tidsenhed , og dermed den overordnede ydeevne af programmer.
Processorer med en rørledning indeni er designet således, at behandlingen af instruktioner er opdelt i en sekvens af trin, forudsat samtidig behandling af flere instruktioner på forskellige stadier. Resultaterne af arbejdet i hvert af trinene overføres gennem hukommelsescellerne til næste trin, og så videre, indtil instruktionen udføres. En sådan organisering af processoren, med en lille stigning i den gennemsnitlige udførelsestid for hver instruktion, giver ikke desto mindre en betydelig stigning i ydeevne på grund af den høje frekvens af instruktionsfuldførelse.
Men ikke alle instruktioner er uafhængige. I den enkleste pipeline, hvor instruktionsbehandling er repræsenteret af fem trin, for at sikre fuld belastning, mens behandlingen af den første instruktion er afsluttet, skal der ideelt set behandles yderligere fire på hinanden følgende uafhængige instruktioner parallelt. Hvis sekvensen indeholder instruktioner, der er afhængige af dem, der aktuelt udføres, så suspenderer kontrollogikken for den enkleste pipeline flere indledende stadier af pipelinen, og placerer derved en tom instruktion ("boble") i pipelinen, nogle gange gentagne gange, indtil afhængigheden er løst. Der er en række tricks, såsom videresendelse, der i høj grad reducerer behovet for at sætte en del af pipelinen på pause i sådanne tilfælde. Afhængigheden mellem instruktioner, der behandles samtidigt af processoren, tillader imidlertid ikke at opnå en ydelsesforøgelsesmultipel af antallet af pipelinetrin sammenlignet med en pipelineløs processor.
Rørledningen hjælper ikke i alle tilfælde. Der er flere mulige ulemper. En instruktionspipeline kan kaldes "fuldt pipelinet", hvis den kan acceptere en ny instruktion hver maskincyklus . Ellers skal der tvinges forsinkelser ind i rørledningen, der gør rørledningen flad, samtidig med at dens ydeevne forringes.
Fordele:
Fejl:
Til højre er en generel pipeline med fire arbejdstrin:
Det øverste grå område er en liste over instruktioner, der skal udføres. Det nederste grå område er en liste over instruktioner, der allerede er blevet udført. Og det mellemste hvide område er selve rørledningen.
Udførelsen går således:
| Cyklus | Handlinger |
|---|---|
| 0 | Fire instruktioner afventer udførelse |
| en |
|
| 2 |
|
| 3 |
|
| fire |
|
| 5 |
|
| 6 |
|
| 7 |
|
| otte |
|
| 9 | Alle instruktioner er blevet fulgt |
For at løse pipelinekonflikter er processoren tvunget til at forsinke behandlingen af instruktionen ved at skabe en "boble" i pipelinen. Passagen af boblen gennem aktuatorerne er ikke ledsaget af noget nyttigt arbejde. I den anden cyklus er behandlingen af den lilla instruktion forsinket, og der er nu en boble i afkodningsstadiet i den tredje cyklus. Alle instruktioner "efter" den lilla instruktion er forsinket med en cyklus, mens instruktionerne "før" den lilla instruktion fortsætter med at blive udført.
Det er klart, at tilstedeværelsen af en boble i rørledningen giver en samlet udførelsestid på 8 cyklusser i stedet for 7 i udførelsesdiagrammet vist ovenfor.
Aktuatorerne skal udføre en handling på hver cyklus. Bobler er en måde at skabe en forsinkelse i behandlingen af en instruktion uden at stoppe rørledningen. Når de udføres, sker der ikke noget nyttigt arbejde i stadierne med at hente, afkode, udføre og skrive resultatet. De kan udtrykkes ved hjælp af NOP [11] [12] [13] assembler instruktionen .
Lad os sige, at en typisk instruktion til at tilføje to tal er СЛОЖИТЬ A, B, C. Denne instruktion tilføjer værdierne i hukommelsesplaceringerne A og B og placerer derefter resultatet i hukommelsesplaceringen C . I en pipelinet processor kan controlleren opdele denne operation i sekventielle opgaver af formularen
LOAD A , R1 LOAD B , R2 ADD R1 , R2 , R3 WRITE R3 , C load næste instruktionCeller R1 , R2 og R3 er processorregistre . _ Værdierne, der er gemt i hukommelsesplaceringer, som vi kalder A og B , indlæses (det vil sige kopieres) i disse registre, opsummeres derefter, og resultatet skrives til hukommelsesplacering C .
I dette eksempel består pipelinen af tre niveauer - indlæsning, udførelse og skrivning. Disse trin kaldes naturligvis niveauer eller pipeline-trin .
I en pipelineløs processor kan kun ét trin køre ad gangen, så en instruktion skal fuldføres fuldstændigt, før den næste instruktion overhovedet kan begynde. I en pipelinet processor kan alle disse trin udføres samtidigt på forskellige instruktioner. Så når den første instruktion er i udførelsestrinnet, vil den anden instruktion være i afkodningsstadiet, og den tredje instruktion vil være i læsestadiet.
Pipelinen reducerer ikke den tid, det tager at udføre en instruktion, men den øger mængden (antallet) af instruktioner, der kan udføres på samme tid, og reducerer dermed forsinkelsen mellem udførte instruktioner - øger den såkaldte. gennemstrømning . Jo flere lag en pipeline har, jo flere instruktioner kan udføres på samme tid, og jo mindre forsinkelse er der mellem afsluttede instruktioner. Hver mikroprocessor, der fremstilles i dag, bruger mindst en to-niveau pipeline.
Teoretisk tre-niveau pipeline:
| Trin | engelsk titel | Beskrivelse |
|---|---|---|
| Prøve | Hent | Læs instruktion fra hukommelsen |
| Udførelse | Udfør | Udfør instruktion |
| Indspilning | Skrive tilbage | Skriv resultatet til hukommelsen og/eller registre |
Pseudo-assembler-liste, der skal udføres:
LAST 40, A ; indlæs nummer 40 i A KOPI A , B ; kopi A til B ADD 20, B ; tilføj 20 til B SKRIV B , 0x0300 ; skriv B til hukommelsesplacering 0x0300Sådan vil det blive udført:
| Takt | Prøve | Udførelse | Indspilning | Forklaring |
|---|---|---|---|---|
| Foranstaltning 1 | HENT | LOAD-instruktionen læses fra hukommelsen. | ||
| Foranstaltning 2 | KOPI | HENT | LOAD-instruktionen udføres, COPY-instruktionen læses fra hukommelsen. | |
| Foranstaltning 3 | FOLDE | KOPI | HENT | LOAD-instruktionen er i skriveresultattrinnet, hvor dens resultat (det vil sige tallet 40 ) skrives til register A. Samtidig udføres COPY-instruktionen. Da den skal kopiere indholdet af register A ind i register B , skal den vente til slutningen af LOAD-instruktionen. |
| Foranstaltning 4 | OPTAGE | FOLDE | KOPI | SKRIV-instruktionen indlæses, mens COPY-instruktionen siger farvel til os, og ADD-instruktionen er ved at blive beregnet. |
Og så videre. Bemærk, at instruktioner nogle gange vil afhænge af resultatet af andre instruktioner (som vores COPY-instruktion, for eksempel). Når mere end én instruktion refererer til en specifik placering, enten ved at læse den (dvs. bruge den som en input-operand) eller skrive til den (det vil sige ved at bruge den som en output-operand), er udførelsen af instruktionerne ikke i den ordre, der oprindeligt var tiltænkt i det originale program. , kan forårsage en pipelinekonflikt , (som nævnt ovenfor). Der er flere gennemprøvede teknikker til enten at forhindre konflikter eller løse dem, hvis de opstår.
Mange ordninger inkluderer pipelines på 7, 10 eller endda 20 niveauer (som for eksempel i Pentium 4-processoren ). Sen Pentium 4-kerner med kodenavnet Prescott og Cedar Mill (og deres Pentium D- derivater) har en 31-niveau pipeline.
Xelerator X10q-processoren har en pipeline, der er over tusind trin lang [14] . Bagsiden af mønten i dette tilfælde er behovet for at nulstille hele pipelinen, hvis programflowet har ændret sig (for eksempel ved en betinget erklæring). Branch forudsigere forsøger at løse dette problem . Branch forudsigelse i sig selv kan kun gøre tingene værre, hvis forudsigelsen er lavet dårligt. I nogle applikationer, såsom supercomputing , er programmer specifikt skrevet til at bruge betingede udsagn så lidt som muligt, så meget lange pipelines vil have en meget positiv effekt på den samlede hastighed af beregninger, da lange pipelines er designet til at reducere CPI ( antal cyklusser til instruktionen ).
Hvis forgrening sker hele tiden, vil omarrangering af maskininstruktionerne hjælpe med at reducere hastighedstabet markant: de instruktioner, der sandsynligvis er nødvendige, er placeret i rørledningen. Denne metode er mere effektiv end at skulle nulstille rørledningen fuldstændigt hver gang. Programmer som gcov kan bruges til at bestemme, hvor ofte individuelle filialer faktisk udføres, ved hjælp af en teknik kendt som kodedækningsanalyse . Selvom en sådan analyse i praksis er den sidste foranstaltning i optimering.
Den høje gennemstrømning af pipelines fører til et fald i ydeevnen, hvis den eksekverbare kode indeholder mange betingede spring: processoren ved ikke, hvor den næste instruktion skal læses fra, og må derfor vente på, at den betingede springinstruktion slutter, hvilket efterlader en tom rørledning bagved. Når grenen er krydset, og det er kendt, hvor processoren skal springe hen til næste, skal den næste instruktion gå hele vejen gennem pipelinen, før resultatet er tilgængeligt, og processoren "virker" igen. I ekstreme tilfælde kan ydeevnen af en pipelinet processor teoretisk falde til den for en pipelineløs processor eller endda være værre på grund af det faktum, at kun ét niveau af pipelinen er optaget, og der er en lille forsinkelse mellem niveauerne.
Hvis processoren er udstyret med en pipeline, bliver koden læst fra hukommelsen ikke eksekveret med det samme, men placeret i en kø ( prefetch input queue ). Hvis koden indeholdt i hukommelsen ændres, vil koden i pipeline-køen forblive den samme. Instruktionerne i instruktionscachen ændres heller ikke . Det skal tages i betragtning, at dette problem kun er typisk for selvmodificerende programmer og pakkere af eksekverbare filer.
| Digitale processorteknologier | |||||||||
|---|---|---|---|---|---|---|---|---|---|
| Arkitektur | |||||||||
| Instruktionssæt arkitektur | |||||||||
| maskinord | |||||||||
| Parallelisme |
| ||||||||
| Implementeringer | |||||||||
| Komponenter | |||||||||
| Strømstyring | |||||||||