Istruzioni di programmazione - Instruction scheduling

In informatica , pianificazione delle istruzioni è un ottimizzazione del compilatore utilizzato per migliorare a livello di istruzioni di parallelismo , che migliora le prestazioni su macchine con tubazioni di istruzioni . Più semplicemente, si cerca di fare quanto segue senza modificare il significato del codice:

  • Evitare bancarelle gasdotto riorganizzando l'ordine delle istruzioni.
  • Evitare operazioni illegali o semanticamente ambiguo (in genere compresi problemi di tempistica di istruzioni gasdotti sottili o le risorse non interbloccate).

I banchi conduttura possono essere causati da ostacoli strutturali (limite risorsa processore), pericoli di dati (uscita di un'istruzione necessaria un'altra istruzione) e rischi di controllo (ramificazione).

rischi dati

Pianificazione delle istruzioni è in genere fatto in un unico blocco di base . Al fine di determinare se riordinando le istruzioni del blocco in un certo modo conserva il comportamento di quel blocco, abbiamo bisogno del concetto di dipendenza dei dati . Ci sono tre tipi di dipendenze, che capita anche di essere i tre pericoli di dati :

  1. Leggere dopo Write (RAW o "True"): Istruzione 1 scrive un valore utilizzato in seguito da istruzioni 2. Istruzioni 1 deve venire prima, o di istruzioni 2 leggerà il vecchio valore invece del nuovo.
  2. Scrivi dopo Leggi (guerra o "anti"): Istruzione 1 legge una posizione che è in seguito sovrascritto da istruzioni 2. Istruzioni 1 deve venire prima, o leggerà il nuovo valore al posto del vecchio.
  3. Scrivi dopo Write (WAW o "Uscita"): Due istruzioni sia scrivere la stessa posizione. Essi devono avvenire nel loro ordine originale.

Tecnicamente, c'è un quarto tipo, lettura dopo lettura (RAR o "Input"): Entrambe le istruzioni lette nella stessa posizione. dipendenza ingresso non vincola l'ordine di esecuzione di due istruzioni, ma è utile in sostituzione scalare di elementi array.

Per essere sicuri di rispettare i tre tipi di dipendenze, viene costruito un grafico di dipendenza, che è un grafo orientato dove ciascun vertice è un'istruzione e c'è un bordo da I 1 a I 2 se 1 deve venire prima 2 a causa di un dipendenza. Se dipendenze loop effettuato sono lasciati fuori, il grafico dipendenza è un grafo orientato aciclico . Quindi, qualsiasi ordinamento topologico di questo grafico è un programma un'istruzione valida. I bordi del grafo sono generalmente etichettati con la latenza della dipendenza. Questo è il numero di cicli di clock che deve trascorrere prima che la conduttura può procedere con l'istruzione di destinazione senza stallo.

algoritmi

L'algoritmo più semplice per trovare un ordinamento topologico è usato frequentemente ed è conosciuta come la lista di programmazione . Concettualmente, seleziona ripetutamente una fonte del grafico di dipendenza, aggiunge alla pianificazione istruzione corrente e rimuove dal grafico. Ciò può causare altri vertici come fonti, che poi anche da considerare per la pianificazione. L'algoritmo termina se il grafico è vuoto.

Per arrivare a un buon programma, bancarelle devono essere prevenute. Questo è determinato dalla scelta della prossima istruzione per essere programmato. Un certo numero di euristiche sono di uso comune:

  • Le risorse del processore utilizzati dalle istruzioni già programmati vengono registrati. Se un candidato utilizza una risorsa che è occupato, la sua priorità scenderà.
  • Se un candidato è prevista più vicina ai suoi predecessori rispetto alla latenza associata sua priorità cadrà.
  • Se un candidato si trova sul percorso critico del grafico, la sua priorità aumenterà. Questo euristica fornisce una qualche forma di look-ahead in un processo decisionale altrimenti locale.
  • Se la scelta di un candidato creerà molte nuove fonti, la sua priorità salirà. Questa euristica tende a generare una maggiore libertà per lo scheduler.

L'ordine delle fasi di schedulazione delle istruzioni

Pianificazione delle istruzioni può essere effettuata prima o dopo l'allocazione registro o sia prima che dopo. Il vantaggio di farlo prima di allocazione dei registri è che questo si traduce in massima parallelismo. Lo svantaggio di farlo prima assegnazione di registri è che questo può comportare registro allocatore necessità di utilizzare un numero di registri superiori a quelle disponibili. Questo farà sì che il codice fuoriuscita / riporto da introdurre che ridurrà le prestazioni della sezione di codice in questione.

Se l'architettura sia pianificata ha sequenze di istruzioni che offrono combinazioni potenzialmente illegali (a causa di una mancanza di interblocchi istruzione) le istruzioni devono essere previsti dopo l'allocazione registro. Questo secondo passaggio di pianificazione migliorerà anche il posizionamento del codice di fuoriuscita / riempimento.

Se la programmazione avviene solo dopo la ripartizione registro allora ci saranno falsi dipendenze introdotte dalla allocazione dei registri che limiterà la quantità di movimento istruzione possibile dallo scheduler.

Tipi di pianificazione delle istruzioni

Ci sono diversi tipi di pianificazione delle istruzioni:

  1. Locale ( base blocco ) la programmazione : istruzioni non possono muoversi attraverso i confini dei blocchi di base.
  2. La pianificazione globale : istruzioni possono muoversi attraverso i confini dei blocchi di base.
  3. Modulo programmazione : un algoritmo per generare pipelining software , che è un modo per aumentare il livello di istruzione parallelismo interleaving diverse iterazioni di un inner ciclo .
  4. Scheduling Traccia : il primo approccio pratico per la pianificazione globale, la pianificazione traccia cerca di ottimizzare il percorso del flusso di controllo che viene eseguita più spesso.
  5. Scheduling Superblocco : una forma semplificata di scheduling traccia che non tenta di unire percorsi di flusso di controllo in tracce "ingressi laterali". Invece, il codice può essere implementato da più di un programma, semplificando enormemente il generatore di codice.

Guarda anche

Riferimenti

ulteriore lettura

  • Fisher, Joseph A. (1981). "Trace Scheduling: Una tecnica per Globale Microcode compattazione" . IEEE Transactions on Computers . 30 (7): 478-490.( Scheduling Trace )
  • Nicolau, Alexandru; Fisher, Joseph A. (1984). "Misurare il parallelismo Disponibile per Very Long Instruction Word Architectures". IEEE Transactions on Computers . 33 (11).( Scheduling percolazione )
  • Bernstein, David; Rodeh, Michael (giugno 1991). "Pianificazione istruzione globale per le macchine superscalare". Proceedings of the ACM, SIGPLAN '91 Conferenza sul Design linguaggio di programmazione e attuazione .( Scheduling Globale )