Vad är Out Of Order Execution?

Datorer är komplexa maskiner med ingen del mer komplex än processorn. På en grundläggande översiktsnivå verkar det som att CPU:n borde vara relativt enkel. Det tar en serie kommandon, bearbetar dem och matar sedan ut data. Detta påminner dock inte mycket om hur moderna processorer fungerar.

Sub-skalär till super-skalär

Tidiga processorer var precis som du förväntade dig. De tog instruktioner individuellt, i den ordning de fick dem, bearbetade dem tills de var klara och gick sedan vidare till nästa instruktion. CPU:er av denna typ var sub-skalära och kunde slutföra mindre än en instruktion per klockcykel. CPU-designers identifierade att det fanns många olika steg för att slutföra en instruktion. Var och en av dessa steg krävde olika hårdvara. Detta innebar att när man körde en enskild instruktion genom hela sekvensen åt gången, var vissa delar av hårdvaran inaktiva. I vilken typ av processor som helst är inaktiv hårdvara värdelös hårdvara.

För att använda denna lediga hårdvara uppdaterades CPU-designerna för att använda en pipeline-metod. Detta ytterligare separerade hårdvaran för varje steg men gjorde det möjligt för dem alla att användas samtidigt av en serie instruktioner. Även om det fortfarande tog några cykler för varje instruktion att gå igenom pipelinen, var den totala genomströmningen en instruktion per cykel. Detta gjorde processorerna skalära.

För att kunna göra mer behövde processorer göras superskalära. För att uppnå detta implementerades flera parallella pipelines.

Att hålla pipelines matade med data

Det huvudsakliga prestandaproblemet med datorer är vanligtvis minneslatens. Många instruktioner verkar på data, och så att data måste vara tillgängliga för att instruktionen ska kunna utföras. Frågan är, vad gör du om du behöver vänta på den informationen eftersom den inte är tillgänglig direkt? Traditionellt var svaret bara att stanna och vänta på att det skulle bli tillgängligt. Detta lämnar hela pipelinen tom, potentiellt i hundratals CPU-cykler. Saker och ting blir ännu värre när två instruktioner i parallella pipelines behöver vänta på minne, eftersom den första kommer att hålla upp även begäran om den andras data. Även om CPU-cacheminne kan hjälpa till att lösa det här problemet, kan det fortfarande inte fixa det. Ett nytt paradigm behövdes för att lösa det. Det paradigmskiftet var Out Of Order Execution eller OOO.

Det första steget i en pipeline är att avkoda instruktionen. Det innebär att ta reda på vad som behöver göras och att verifiera att den data som behövs för operationen är tillgänglig. I en OOO CPU läggs avkodade instruktioner till i en kö. De tas bara bort från kön och bearbetas faktiskt när den data de behöver finns tillgänglig. Kritiskt sett spelar det ingen roll vilken ordning instruktionerna lades till i kön. Om en tidig instruktion väntar på data, kan en nyare instruktion hoppa framåt om den är redo att gå. OOO-processorer kan ordna om instruktionerna de ska behandla baserat på kön av kommande instruktioner och vilka av dem som är redo för exekvering.

Kritiska beroenden

Denna process förutsätter två saker. Först och främst att det är möjligt att på ett tillförlitligt sätt identifiera och hantera verkliga beroenden. För det andra att du på ett tillförlitligt sätt kan hantera och identifiera falska beroenden. Vad är skillnaden? Tja, ett verkligt beroende är ett beroende som inte alls kan mildras i ett OOO-system. Det enklaste exemplet är läs-efter-skrivning. Om du har en instruktion som är tänkt att skriva vissa data och en annan som sedan ska läsa den datan, finns det inget sätt att kunna ändra ordningen på dessa instruktioner. De måste fyllas i i den ordning som de presenterades, annars får du nonsensdata.

Ett falskt beroende är ett som kan döljas med ett annat smart trick. Låt oss ta exemplet med att skriva-efter-läsa. Vid första anblicken kanske du tror att du inte kan skriva över data innan du har läst den. Saker och ting är dock inte så enkelt. Vad händer om du har en annan plats där du kan skriva den nya datan, och sedan kan du bara byta den nya och gamla informationen när den gamla informationen har lästs? Detta är processen för att byta namn på register och det är avgörande för OOO-behandling.

Vanligtvis definierar en instruktionsuppsättning ett visst antal arkitektoniska register som används i systemet. Du kan bokstavligen inte tilltala någon annan. Men vad händer om du gör överprovisionsregister? Du kan bara gömma dem för det mesta, använda dem för att lagra data som inte borde ha bearbetats ännu, och sedan helt enkelt byta ut etiketterna för de dolda och arkitektoniska registren när tidslinjen är korrekt igen. När som helst finns det exakt rätt mängd arkitektoniska register, de är bara inte nödvändigtvis alltid på samma plats. En analogi från verkligheten skulle vara hot-deking.

Slutsats

Out Of Order exekvering är ett bearbetningsparadigm där instruktioner dynamiskt kan ordnas om vid körning av CPU:n. Detta görs utifrån de tidigast utfärdade instruktioner som har data tillgänglig. Detta innebär att instruktioner som laddas in i pipelinen alltid är redo att exekveras och det finns inga förseningar i väntan på data. Naturligtvis är det nödvändigt att ha en tillräckligt lång kö så att den inte fylls med instruktioner som väntar på data, men det är en implementeringsutmaning. OOO-körning förlitar sig på registerbyte för att dölja falska beroenden. Även om dessa instruktioner faktiskt exekveras i oordning, döps registren om på ett sådant sätt att detta faktum döljs från resten av datorn.