Predicazione (architettura del computer) - Predication (computer architecture)

Da non confondere con la previsione del ramo .

In informatica , predicazione è una architettura caratteristica che fornisce un'alternativa al trasferimento condizionale di controllo , attuato da istruzioni macchina come la condizionale ramo , condizionale chiamata , condizionale di ritorno , e le tabelle di filiale . La predicazione funziona eseguendo istruzioni da entrambi i percorsi del ramo e consentendo solo a tali istruzioni dal percorso preso di modificare lo stato dell'architettura. Le istruzioni del percorso preso possono modificare lo stato architetturale perché sono state associate ( predicate ) con un predicato , un valore booleano utilizzato dall'istruzione per controllare se l'istruzione può modificare o meno lo stato architetturale.

In parole povere: se il bit Register Condition è impostato, l'istruzione viene eseguita; se il bit è chiaro, non lo è. Poiché il contenuto di Condition Register è dinamico, l'esecuzione dell'istruzione predicata è altrettanto dinamica, cioè (condizionatamente) determinata in fase di runtime.

I processori Vector , alcuni SIMD ISA (come AVX2 e AVX-512 ]) e le GPU in generale fanno un uso massiccio della predicazione, applicando un bit di una maschera condizionale Vector agli elementi corrispondenti nei registri Vector in elaborazione, mentre la predicazione scalare in scalare i set di istruzioni richiedono solo un bit del predicato. Il punto in cui le maschere dei predicati diventano particolarmente potenti nell'elaborazione dei vettori è se una serie di codici di condizione , uno per ogni elemento del vettore, può essere restituita alle maschere dei predicati che vengono poi applicate alle successive istruzioni del vettore.

Panoramica

La maggior parte dei programmi per computer contiene codice condizionale , che verrà eseguito solo in condizioni specifiche a seconda di fattori che non possono essere determinati in anticipo, ad esempio in base all'input dell'utente. Poiché la maggior parte dei processori semplicemente eseguire la successiva istruzione in una sequenza, la soluzione tradizionale è quella di inserire ramo istruzioni che permettono ad un programma di ramo condizionale ad una sezione differente di codice, modificando così il passo successivo nella sequenza. Ciò è stato sufficiente fino a quando i progettisti hanno iniziato a migliorare le prestazioni implementando il pipelining delle istruzioni , un metodo che viene rallentato dai rami. Per una descrizione più approfondita dei problemi sorti e una soluzione popolare, vedere il predittore di ramo .

Fortunatamente, uno dei modelli di codice più comuni che normalmente si basa sulla ramificazione ha una soluzione più elegante. Considera il seguente pseudocodice : 

if condition
    {dosomething}
else
    {dosomethingelse};

Su un sistema che utilizza la ramificazione condizionale, questo potrebbe tradursi in istruzioni macchina simili a: 

branch-if-condition to label1
dosomethingelse
branch-to label2
label1:
dosomething
label2:
...

Con la predicazione, tutti i possibili percorsi di diramazione sono codificati in linea, ma alcune istruzioni vengono eseguite mentre altre no. L'idea di base è che ogni istruzione è associata a un predicato (la parola qui usata in modo simile al suo utilizzo nella logica dei predicati ) e che l'istruzione verrà eseguita solo se il predicato è vero. Il codice macchina per l'esempio precedente che utilizza la predicazione potrebbe essere simile a questo: 

(condition) dosomething
(not condition) dosomethingelse

Oltre all'eliminazione dei rami, è necessario meno codice in totale, a condizione che l'architettura fornisca istruzioni prestabilite. Sebbene ciò non garantisca un'esecuzione più rapida in generale, lo sarà se i blocchi di codice di " fai qualcosa" e " fai qualcosa " sono sufficientemente brevi.

La forma più semplice di predicazione è la predicazione parziale , in cui l'architettura ha istruzioni di spostamento condizionale o di selezione condizionale . Le istruzioni di spostamento condizionale scrivono il contenuto di un registro su un altro solo se il valore del predicato è vero, mentre le istruzioni di selezione condizionale scelgono quale dei due registri ha il contenuto scritto su un terzo in base al valore del predicato. Una forma più generalizzata e capace è la predicazione completa . La predicazione completa ha una serie di registri dei predicati per l'archiviazione dei predicati (che consente l'eliminazione simultanea di più rami nidificati o sequenziali) e la maggior parte delle istruzioni nell'architettura ha un campo di identificazione del registro per specificare quale registro del predicato fornisce il predicato.

Vantaggi

Lo scopo principale della predicazione è evitare salti su sezioni molto piccole del codice del programma, aumentando l'efficacia dell'esecuzione in pipeline ed evitando problemi con la cache . Ha anche una serie di vantaggi più sottili:

  • Le funzioni che vengono tradizionalmente calcolate utilizzando semplici operazioni aritmetiche e bit per bit possono essere più veloci da calcolare utilizzando istruzioni predicate.
  • Le istruzioni predicate con predicati diversi possono essere mescolate tra loro e con codice incondizionato, consentendo una migliore pianificazione delle istruzioni e quindi prestazioni ancora migliori.
  • L'eliminazione di istruzioni di diramazione non necessarie può rendere più rapida l'esecuzione delle diramazioni necessarie, come quelle che costituiscono i loop, riducendo il carico sui meccanismi di previsione delle diramazioni .
  • Eliminazione del costo di una previsione errata di un ramo che può essere elevato su architetture profondamente pipeline.
  • I set di istruzioni che dispongono di codici condizione completi generati dalle istruzioni possono ridurre ulteriormente la dimensione del codice utilizzando direttamente i registri di condizione in o come predicazione.

Svantaggi

Lo svantaggio principale di Predication è l'aumento dello spazio di codifica. Nelle implementazioni tipiche, ogni istruzione riserva un campo di bit per il predicato specificando in quali condizioni quell'istruzione dovrebbe avere effetto. Quando la memoria disponibile è limitata, come sui dispositivi embedded , questo costo di spazio può essere proibitivo. Tuttavia, alcune architetture come Thumb-2 sono in grado di evitare questo problema (vedi sotto). Altri svantaggi sono i seguenti:

  • La predicazione complica l'hardware aggiungendo livelli di logica ai percorsi critici e potenzialmente riduce la velocità di clock.
  • Un blocco predicato include cicli per tutte le operazioni, quindi i percorsi più brevi potrebbero richiedere più tempo ed essere penalizzati.
  • La predicazione di solito non è speculata e causa una catena di dipendenze più lunga. Per i dati ordinati ciò si traduce in una perdita di prestazioni rispetto a un ramo prevedibile.

La predicazione è più efficace quando i percorsi sono bilanciati o quando il percorso più lungo è il più frequentemente eseguito, ma determinare tale percorso è molto difficile in fase di compilazione, anche in presenza di informazioni di profilazione .

Storia

Le istruzioni predicate erano popolari nei progetti di computer europei degli anni '50, tra cui il Mailüfterl (1955), lo Zuse Z22 (1955), lo ZEBRA (1958) e l' Electrologica X1 (1958). Il progetto IBM ACS-1 del 1967 allocava un bit "salta" nei suoi formati di istruzione e il processore flessibile CDC nel 1976 allocava tre bit di esecuzione condizionale nei suoi formati di microistruzione.

Hewlett-Packard s' PA-RISC architettura (1986) ha avuto una funzione chiamata nullità , che ha permesso la maggior parte delle istruzioni per essere basata dall'istruzione precedente. L' architettura POWER di IBM (1990) prevedeva istruzioni di spostamento condizionali. Il successore di POWER, PowerPC (1993), lasciò cadere queste istruzioni. Digital Equipment Corporation 's Alpha architettura (1992) inoltre ha caratterizzato istruzioni di movimento condizionali. MIPS ha ottenuto istruzioni di movimento condizionale nel 1994 con la versione MIPS IV; e SPARC è stato esteso nella versione 9 (1994) con istruzioni di spostamento condizionale sia per i registri interi che per quelli a virgola mobile.

Nell'architettura Hewlett-Packard / Intel IA-64 , la maggior parte delle istruzioni è basata. I predicati sono memorizzati in 64 registri di predicati per scopi speciali ; e uno dei registri predicato è sempre vero in modo che i unpredicated istruzioni sono semplicemente le istruzioni predicate con il valore true. L'uso della predicazione è essenziale nell'implementazione del software pipelining di IA-64 perché evita la necessità di scrivere codice separato per prologhi ed epiloghi.

Nell'architettura x86 , una famiglia di istruzioni di spostamento condizionale ( CMOVe FCMOV) è stata aggiunta all'architettura dal processore Intel Pentium Pro (1995). Le CMOVistruzioni hanno copiato il contenuto del registro sorgente nel registro di destinazione a seconda di un predicato fornito dal valore del registro flag.

Nell'architettura ARM , il set di istruzioni originale a 32 bit fornisce una funzionalità chiamata esecuzione condizionale che consente di predicare la maggior parte delle istruzioni da uno dei 13 predicati basati su una combinazione dei quattro codici di condizione impostati dall'istruzione precedente. Il set di istruzioni Thumb di ARM (1994) ha abbandonato l'esecuzione condizionale per ridurre la dimensione delle istruzioni in modo che potessero adattarsi a 16 bit, ma il suo successore, Thumb-2 (2003) ha superato questo problema utilizzando un'istruzione speciale che non ha altro effetto se non quello di fornire predicati per le seguenti quattro istruzioni. Il set di istruzioni a 64 bit introdotto in ARMv8-A (2011) ha sostituito l'esecuzione condizionale con istruzioni di selezione condizionale.

SIMD, SIMT e predizione vettoriale

Alcuni set di istruzioni SIMD , come AVX2, hanno la capacità di utilizzare una maschera logica per caricare/salvare valori in memoria in modo condizionale, una forma parallela dello spostamento condizionale e possono anche applicare singoli bit di maschera a singole unità aritmetiche che eseguono un'operazione parallela. La tecnica è nota come "elaborazione associativa" nella tassonomia di Flynn .

Questa forma di predicazione viene utilizzata anche nei processori Vector e nel calcolo GPU con una singola istruzione e più thread . Tutte le tecniche, i vantaggi e gli svantaggi della predicazione scalare singola si applicano altrettanto bene al caso di elaborazione parallela.

Guarda anche

Riferimenti

Ulteriori letture