Salta al contenuto
Note per Studenti Esercizio 19 · speedup di una pipeline con salti

Esercizio 19speedup di una pipeline con salti

In questa pagina 6

Testo (svolto in aula, lezione dell'11 gennaio 2017). In uno scenario di esecuzione di software applicativi il 15% delle istruzioni sono di salto condizionato, l'1% di salto incondizionato, e il 60% dei salti condizionati ha la condizione soddisfatta (salto preso). Si consideri la pipeline MIPS a 5 stadi, in cui l'indirizzo di destinazione è disponibile dopo la fase EX e i salti condizionati sono risolti durante la fase EX. Si assuma che non ci siano altre cause di stallo e che si predica di non saltare in caso di salto condizionato. Calcolare quanto sarebbe più veloce, a regime, la pipeline senza gli stalli introdotti dai salti.

Formula data: lo speedup di una pipeline a kk stadi a regime è

Sk=k1+frazione di cicli di stalloS_k = \frac{k}{1 + \text{frazione di cicli di stallo}}

Senza stalli

Con frazione di stallo nulla S5=5S_5 = 5: a regime una pipeline a 5 stadi completa un'istruzione per ciclo (vedi PipelineIdea della catena di montaggio; pipeline a 5 stadi IF, ID, EX, MEM, WB; tempo di ciclo, tempo per n istruzioni in una pipeline a k stadi e speedup con esempi svolti; registri di pipeline; scrittura e lettura dei registri nello stesso ciclo; limiti (stadi sbilanciati, hazard).Pipeline →).

Cicli di stallo per tipo di salto

Il salto entra in IF al ciclo 1, ID al 2, EX al 3; solo alla fine di EX si conoscono destinazione e condizione, quindi il prelievo dell'istruzione giusta parte al ciclo 4. Nel frattempo sono state prelevate le 2 istruzioni successive al salto.

  • Salto incondizionato: le 2 istruzioni prelevate vanno scartate → 2 cicli di stallo.
  • Condizionato preso: stessa situazione → 2 cicli.
  • Condizionato non preso: la previsione "non saltare" era giusta, le istruzioni prelevate sono quelle da eseguire → 0 cicli.

Probabilità

  • incondizionato: 0,010{,}01;
  • condizionato preso: 0,15⋅0,60=0,090{,}15 \cdot 0{,}60 = 0{,}09;
  • condizionato non preso: 0,15⋅0,40=0,060{,}15 \cdot 0{,}40 = 0{,}06.

Frazione di cicli di stallo

Ogni tipo pesa con il suo numero di cicli:

0,01⋅2+0,09⋅2+0,06⋅0=0,02+0,18=0,20{,}01 \cdot 2 + 0{,}09 \cdot 2 + 0{,}06 \cdot 0 = 0{,}02 + 0{,}18 = 0{,}2

Speedup

S5=51+0,2=51,2≈4,17S_5 = \frac{5}{1 + 0{,}2} = \frac{5}{1{,}2} \approx 4{,}17

La pipeline senza stalli da salto sarebbe 5/4,17=1,25/4{,}17 = 1{,}2 volte più veloce, cioè il 20% in più.

Osservazione

Il risultato dipende dalle ipotesi del testo. Se la pipeline si mettesse in stallo appena decodificato un salto condizionato (senza prevedere "non preso"), anche i salti non presi costerebbero cicli. Vedi Hazard nella pipelineHazard strutturali, sui dati e sul controllo; dipendenze RAW, WAR e WAW; stalli e bolle con diagrammi; data forwarding (bypass) e caso load-use; riordino delle istruzioni da parte del compilatore e dell'hardware; costo dei salti.Hazard nella pipeline → e Branch predictionTecniche per gli hazard sul controllo: stallo, flussi multipli, prelievo anticipato del bersaglio, loop buffer, salto ritardato; predizione statica e dinamica con bit di storia, predittore a 1 e a 2 bit con esempio su un ciclo, tabella dei bersagli (BTB); costo di una predizione errata.Branch prediction →.

Versione ripasso

Testo (svolto in aula, lezione dell'11 gennaio 2017). In uno scenario di esecuzione di software applicativi il 15% delle istruzioni sono di salto condizionato, l'1% di salto incondizionato, e il 60% dei salti condizionati ha la condizione soddisfatta (salto preso). Si consideri la pipeline MIPS a 5 stadi, in cui l'indirizzo di destinazione è disponibile dopo la fase EX e i salti condizionati sono risolti durante la fase EX. Si assuma che non ci siano altre cause di stallo e che si predica di non saltare in caso di salto condizionato. Calcolare quanto sarebbe più veloce, a regime, la pipeline senza gli stalli introdotti dai salti.

Formula data: lo speedup di una pipeline a kk stadi a regime è

Sk=k1+frazione di cicli di stalloS_k = \frac{k}{1 + \text{frazione di cicli di stallo}}

Metodo: si pesano i cicli di stallo di ogni tipo di salto con la sua probabilità (PipelineIdea della catena di montaggio; pipeline a 5 stadi IF, ID, EX, MEM, WB; tempo di ciclo, tempo per n istruzioni in una pipeline a k stadi e speedup con esempi svolti; registri di pipeline; scrittura e lettura dei registri nello stesso ciclo; limiti (stadi sbilanciati, hazard).Pipeline →, Hazard nella pipelineHazard strutturali, sui dati e sul controllo; dipendenze RAW, WAR e WAW; stalli e bolle con diagrammi; data forwarding (bypass) e caso load-use; riordino delle istruzioni da parte del compilatore e dell'hardware; costo dei salti.Hazard nella pipeline →, Branch predictionTecniche per gli hazard sul controllo: stallo, flussi multipli, prelievo anticipato del bersaglio, loop buffer, salto ritardato; predizione statica e dinamica con bit di storia, predittore a 1 e a 2 bit con esempio su un ciclo, tabella dei bersagli (BTB); costo di una predizione errata.Branch prediction →).

  1. Senza stalli S5=5S_5 = 5.
  2. Destinazione e condizione sono note alla fine di EX: le 2 istruzioni prelevate dopo il salto vanno scartate. Incondizionato: 2 cicli; condizionato preso: 2 cicli; non preso (previsione giusta): 0.
  3. Probabilità: incondizionato 0,010{,}01; preso 0,15⋅0,60=0,090{,}15 \cdot 0{,}60 = 0{,}09; non preso 0,15⋅0,40=0,060{,}15 \cdot 0{,}40 = 0{,}06.
  4. Stalli per istruzione: 0,01⋅2+0,09⋅2+0,06⋅0=0,20{,}01 \cdot 2 + 0{,}09 \cdot 2 + 0{,}06 \cdot 0 = 0{,}2.
  5. S5=5/(1+0,2)=5/1,2≈4,17S_5 = 5/(1 + 0{,}2) = 5/1{,}2 \approx 4{,}17.

Senza stalli da salto la pipeline sarebbe 1,21{,}2 volte più veloce (20% in più). Il risultato dipende dall'ipotesi "non preso".

Esercizi su questo argomento

Lezioni in cui compare

Teoria collegata