Wat is Out Of Order Execution?

Computers zijn complexe machines waarvan geen enkel onderdeel complexer is dan de CPU. Op basisniveau lijkt het erop dat de CPU relatief eenvoudig moet zijn. Er is een reeks opdrachten voor nodig, verwerkt ze en voert vervolgens de gegevens uit. Dit lijkt echter weinig op de werkelijke werking van moderne CPU's.

Subscalair naar superscalair

Vroege CPU's waren precies zoals je zou verwachten. Ze namen de instructies afzonderlijk op, in de volgorde waarin ze ze kregen, verwerkten ze tot ze voltooid waren en gingen toen verder met de volgende instructie. CPU's van dit type waren subscalair en konden minder dan één instructie per klokcyclus voltooien. CPU-ontwerpers stelden vast dat er veel verschillende fasen waren bij het voltooien van een instructie. Elk van deze fasen vereiste verschillende hardware. Dit betekende dat bij het uitvoeren van een enkele instructie door de hele reeks tegelijk, sommige delen van de hardware inactief waren. In elke soort processor is inactieve hardware nutteloze hardware.

Om deze inactieve hardware te gebruiken, werden CPU-ontwerpen bijgewerkt om een ​​pijplijnbenadering te gebruiken. Hierdoor werd de hardware voor elke fase verder gescheiden, maar konden ze allemaal tegelijkertijd worden gebruikt door een reeks instructies. Hoewel het nog steeds een paar cycli duurde voordat elke instructie door de pijplijn ging, was de totale doorvoer één instructie per cyclus. Dit maakte CPU's scalair.

Om meer te kunnen doen, moesten processors superscalair worden gemaakt. Om dit te bereiken zijn meerdere parallelle pijpleidingen geïmplementeerd.

Pipelines gevoed houden met data

Het belangrijkste prestatieprobleem met computers is meestal geheugenlatentie. Veel instructies werken op gegevens, en dus moeten er gegevens beschikbaar zijn om de instructie uit te voeren. De vraag is, wat doe je als je op die gegevens moet wachten omdat ze niet onmiddellijk beschikbaar zijn? Traditioneel was het antwoord gewoon stoppen en wachten tot het beschikbaar kwam. Hierdoor blijft de hele pijplijn leeg, mogelijk voor honderden CPU-cycli. Het wordt nog erger wanneer twee instructies in parallelle pijplijnen moeten wachten op geheugen, omdat de eerste zelfs het verzoek om de gegevens van de tweede zal tegenhouden. Hoewel CPU-cachegeheugen dit probleem kan verhelpen, kan het het nog steeds niet oplossen. Er was een nieuw paradigma nodig om het op te lossen. Die paradigmaverschuiving was Out Of Order Execution of OOO.

De eerste fase van een pijplijn is het decoderen van de instructie. Dit betekent uitzoeken wat er moet gebeuren en controleren of de gegevens die nodig zijn voor de operatie beschikbaar zijn. In een OOO CPU worden gedecodeerde instructies toegevoegd aan een wachtrij. Ze worden pas uit de wachtrij gehaald en daadwerkelijk verwerkt als de gegevens die ze nodig hebben beschikbaar zijn. Cruciaal is dat het niet uitmaakt in welke volgorde de instructies aan de wachtrij zijn toegevoegd. Als een vroege instructie wacht op gegevens, kan een recentere instructie doorgaan als deze klaar is voor gebruik. OOO-processors kunnen de instructies die ze moeten verwerken opnieuw ordenen op basis van de wachtrij met komende instructies en welke daarvan klaar zijn voor uitvoering.

Kritieke afhankelijkheden

Dit proces veronderstelt twee dingen. Allereerst dat het mogelijk is om op betrouwbare wijze echte afhankelijkheden te identificeren en af ​​te handelen. Ten tweede dat u valse afhankelijkheden betrouwbaar kunt afhandelen en identificeren. Wat is het verschil? Welnu, een echte afhankelijkheid is een afhankelijkheid die helemaal niet kan worden beperkt in een OOO-systeem. Het gemakkelijkste voorbeeld is het lezen-na-schrijven. Als je een instructie hebt die wat gegevens moet schrijven en een andere die die gegevens moet lezen, is er geen manier om die instructies opnieuw te ordenen. Ze moeten worden ingevuld in de volgorde waarin ze zijn gepresenteerd, anders krijg je onzingegevens.

Een valse afhankelijkheid is er een die kan worden verborgen met een andere slimme truc. Laten we het voorbeeld van schrijven-na-lezen nemen. Op het eerste gezicht zou je kunnen denken dat je gegevens niet kunt overschrijven voordat je ze hebt gelezen. De zaken liggen echter niet zo eenvoudig. Wat als u een andere plaats heeft waar u de nieuwe gegevens kunt schrijven, en dan kunt u de nieuwe en oude gegevens gewoon verwisselen zodra de oude gegevens zijn gelezen? Dit is het proces van het hernoemen van registers en het is essentieel voor OOO-verwerking.

Doorgaans definieert een instructieset een bepaald aantal architecturale registers die in het systeem worden gebruikt. Je kunt letterlijk niemand anders aanspreken. Maar wat als u overprovisioning registreert? Je kunt ze gewoon grotendeels verbergen, ze gebruiken om gegevens op te slaan die nog niet verwerkt hadden moeten worden, en dan gewoon de labels van de verborgen en architectonische registers verwisselen als de tijdlijn weer klopt. Op elk moment zijn er precies de juiste hoeveelheid architectonische registers, ze zijn alleen niet noodzakelijkerwijs altijd op dezelfde plaats. Een real-world analogie zou hot-desking zijn.

Conclusie

Out Of Order-uitvoering is een verwerkingsparadigma waarbij instructies dynamisch opnieuw kunnen worden gerangschikt tijdens uitvoering door de CPU. Dit gebeurt op basis van de vroegst uitgegeven instructies waarover gegevens beschikbaar zijn. Dit betekent dat instructies die in de pijplijn worden geladen altijd klaar zijn om te worden uitgevoerd en dat er geen vertragingen zijn tijdens het wachten op gegevens. Het is natuurlijk nodig om een ​​wachtrij te hebben die lang genoeg is om niet vol te raken met instructies die op gegevens wachten, maar dat is een uitdaging bij de implementatie. OOO-uitvoering is afhankelijk van het hernoemen van registers om valse afhankelijkheden te verbergen. Zelfs als deze instructies in de verkeerde volgorde worden uitgevoerd, worden de registers zodanig hernoemd dat dit feit voor de rest van de computer verborgen blijft.