Instruktionsschemaläggning

Inom datavetenskap är instruktionsschemaläggning en kompilatoroptimering som används för att förbättra parallellism på instruktionsnivå, vilket förbättrar prestandan på maskiner med instruktionspipelines . Enkelt uttryckt försöker den göra följande utan att ändra innebörden av koden:

  • Undvik rörledningsstopp genom att ändra ordningen på instruktionerna.
  • Undvik olagliga eller semantiskt tvetydiga operationer (som vanligtvis involverar subtila tidsproblem med instruktionspipeline eller olåsta resurser).

Rörledningsstopp kan orsakas av strukturella faror (processorresursgräns), datarisker (utmatning av en instruktion som behövs av en annan instruktion) och kontrollrisker (förgrening).

Datarisker

Instruktionsschemaläggning görs vanligtvis på ett enda grundblock . För att avgöra om omorganisering av blockets instruktioner på ett visst sätt bevarar beteendet för det blocket, behöver vi konceptet med ett databeroende . Det finns tre typer av beroenden, som också råkar vara de tre datariskerna :

  1. Läs efter skriv (RAW eller "True"): Instruktion 1 skriver ett värde som används senare av Instruktion 2. Instruktion 1 måste komma först, annars läser Instruktion 2 det gamla värdet istället för det nya.
  2. Skriv efter läsning (WAR eller "Anti"): Instruktion 1 läser en plats som senare skrivs över av Instruktion 2. Instruktion 1 måste komma först, annars kommer den att läsa det nya värdet istället för det gamla.
  3. Skriv efter skriv (WAW eller "Output"): Två instruktioner skriver båda på samma plats. De måste förekomma i sin ursprungliga ordning.

Tekniskt sett finns det en fjärde typ, Read after Read (RAR eller "Input"): Båda instruktionerna läses på samma plats. Indataberoende begränsar inte exekveringsordningen för två satser, men det är användbart vid skalärt ersättning av arrayelement.

För att se till att vi respekterar de tre typerna av beroenden konstruerar vi en beroendegraf, som är en riktad graf där varje vertex är en instruktion och det finns en kant från I 1 till I 2 om I 1 måste komma före I 2 på grund av en beroende. Om loopburna beroenden utelämnas är beroendegrafen en riktad acyklisk graf . Då är vilken topologisk sort som helst av denna graf ett giltigt instruktionsschema. Kanterna på grafen är vanligtvis märkta med beroendets latens . Detta är antalet klockcykler som behöver förflyta innan pipelinen kan fortsätta med målinstruktionen utan att stanna.

Algoritmer

Den enklaste algoritmen för att hitta en topologisk sortering används ofta och kallas listschemaläggning . Konceptuellt väljer den upprepade gånger en källa till beroendediagrammet, lägger till den i det aktuella instruktionsschemat och tar bort den från grafen. Detta kan göra att andra hörn blir källor, som då också kommer att beaktas för schemaläggning. Algoritmen avslutas om grafen är tom.

För att komma fram till ett bra schema bör stånd förhindras. Detta bestäms av valet av nästa instruktion som ska schemaläggas. Ett antal heuristiker är vanliga:

  • Processorresurserna som används av de redan schemalagda instruktionerna registreras. Om en kandidat använder en resurs som är upptagen kommer dess prioritet att minska.
  • Om en kandidat schemaläggs närmare sina föregångare än den associerade latensen, kommer dess prioritet att sjunka.
  • Om en kandidat ligger på den kritiska vägen för grafen kommer dess prioritet att öka. Denna heuristik ger någon form av blick framåt i en annars lokal beslutsprocess.
  • Om valet av en kandidat skapar många nya källor, kommer dess prioritet att öka. Denna heuristik tenderar att generera mer frihet för schemaläggaren.

Fasordning

Instruktionsschemaläggning kan göras antingen före eller efter registertilldelning eller både före och efter den. Fördelen med att göra det före registertilldelning är att detta resulterar i maximal parallellitet. Nackdelen med att göra det innan registertilldelning är att detta kan resultera i att registerfördelaren behöver använda ett antal register som överstiger de tillgängliga. Detta kommer att leda till att spill/fyllningskod introduceras, vilket kommer att minska prestandan för kodavsnittet i fråga.

Om arkitekturen som schemaläggs har instruktionssekvenser som har potentiellt olagliga kombinationer (på grund av brist på instruktionsspärrar), måste instruktionerna schemaläggas efter registertilldelning. Detta andra schemaläggningspass kommer också att förbättra placeringen av spill/fyllningskoden.

Om schemaläggning endast görs efter registerallokering, kommer det att finnas falska beroenden som introduceras av registerallokeringen som kommer att begränsa mängden instruktionsrörelse som är möjlig av schemaläggaren.

Typer

Det finns flera typer av instruktionsschemaläggning:

  1. Lokal ( grundblock ) schemaläggning : instruktioner kan inte flyttas över grundläggande blockgränser.
  2. Global schemaläggning : instruktioner kan röra sig över grundläggande blockgränser.
  3. Modulo scheduling : en algoritm för att generera mjukvarupipelining , vilket är ett sätt att öka instruktionsnivåparallellismen genom att interfoliera olika iterationer av en inre loop .
  4. Spårningsschemaläggning : det första praktiska tillvägagångssättet för global schemaläggning, spårningsschemaläggning försöker optimera kontrollflödesvägen som exekveras oftast.
  5. Superblock-schemaläggning : en förenklad form av spårschemaläggning som inte försöker slå samman styrflödesvägar vid spårnings "sidoingångar". Istället kan kod implementeras av mer än ett schema, vilket avsevärt förenklar kodgeneratorn.

Exempel på kompilatorer

GNU Compiler Collection är en kompilator som är känd för att utföra instruktionsschemaläggning, genom att använda flaggorna -march (både instruktionsuppsättning och schemaläggning) eller -mtune (endast schemaläggning). Den använder beskrivningar av instruktionslanser och vilka instruktioner som kan köras parallellt (eller motsvarande, vilken "port" varje använder) för varje mikroarkitektur för att utföra uppgiften. Den här funktionen är tillgänglig för nästan alla arkitekturer som GCC stöder.

Fram till version 12.0.0 kunde instruktionsschemaläggningen i LLVM /Clang endast acceptera en -march (kallad mål-cpu på LLVM-språk) för både instruktionsuppsättning och schemaläggning. Version 12 lägger till stöd för -mtune ( tune-cpu ) endast för x86.

Informationskällor om latens och portanvändning inkluderar:

LLVM:s llvm-exeges bör vara användbar på alla maskiner, speciellt för att samla information om icke-x86.

Se även

Vidare läsning

Hämtad från " https://en.wikipedia.org/w/index.php?title=Instruction_scheduling&oldid=1139902718 "