Esercizio 26fattore di velocizzazione di una pipeline a 4 stadi con salti

Formula

A regime una pipeline a $k$ stadi completa un'istruzione per ciclo: lo speedup ideale rispetto a un'esecuzione non in pipeline è $k$. Ogni ciclo di stallo aggiunto in media per istruzione lo riduce:

$$S = \frac{k}{1 + \text{cicli di stallo per istruzione}}, \qquad \text{cicli di stallo per istruzione} = \sum_{\text{tipi di salto}} p_i \cdot s_i$$

dove $p_i$ è la frazione di istruzioni di quel tipo e $s_i$ il numero di cicli persi per ciascuna.

Cicli persi per tipo di salto

Senza alcun meccanismo, il prelievo continua in sequenza dopo il salto. Finché il salto non è risolto le istruzioni prelevate sono quelle sequenziali; se il salto è preso vanno scartate.

(Nel caso "non preso" il prelievo sequenziale era già corretto: nessuna perdita, anche se il salto è risolto tardi.)

Probabilità per tipo

Con $c$ = frazione di condizionati, $u$ = incondizionati, $q$ = frazione di condizionati presi:

• incondizionato: $u$;
• condizionato preso: $c \cdot q$;
• condizionato non preso: $c \cdot (1 - q)$.

$$\text{stalli} = u \cdot 1 + c\,q \cdot 2 + c\,(1 - q) \cdot 0 = u + 2\,c\,q.$$

Versione 2011-12

$c = 0{,}10$, $u = 0{,}03$, $q = 0{,}55$: condizionati presi $0{,}10 \cdot 0{,}55 = 0{,}055$.

$$\text{stalli} = 0{,}03 \cdot 1 + 0{,}055 \cdot 2 = 0{,}03 + 0{,}11 = 0{,}14, \qquad S = \frac{4}{1{,}14} = 3{,}508772\ldots$$

Risposta b.

Versione 2010-11

$c = 0{,}20$, $u = 0{,}03$, $q = 0{,}55$: condizionati presi $0{,}20 \cdot 0{,}55 = 0{,}11$.

$$\text{stalli} = 0{,}03 + 0{,}11 \cdot 2 = 0{,}25, \qquad S = \frac{4}{1{,}25} = 3{,}2.$$

$3{,}2$ non figura tra le opzioni ($3{,}23$ e $3{,}25$ sono vicine ma diverse): risposta e (nessuna delle precedenti).

Versione 2014-15

$c = 0{,}17$, $u = 0{,}01$, $q = 0{,}70$: condizionati presi $0{,}17 \cdot 0{,}70 = 0{,}119$, non presi $0{,}17 \cdot 0{,}30 = 0{,}051$.

$$\text{stalli} = 0{,}01 \cdot 1 + 0{,}119 \cdot 2 + 0{,}051 \cdot 0 = 0{,}01 + 0{,}238 = 0{,}248, \qquad S = \frac{4}{1{,}248} = 3{,}205128\ldots$$

(Lo stesso risultato della soluzione allegata al testo.)

Verifica

def speedup(k, cond, incond, presi, stallo_inc, stallo_cond_preso, stallo_cond_non_preso=0):
    stalli = incond * stallo_inc + cond * presi * stallo_cond_preso + cond * (1 - presi) * stallo_cond_non_preso
    return stalli, k / (1 + stalli)

for anno, (c, u, q) in {"2010-11": (0.20, 0.03, 0.55), "2011-12": (0.10, 0.03, 0.55), "2014-15": (0.17, 0.01, 0.70)}.items():
    stalli, s = speedup(4, c, u, q, 1, 2)
    print(anno, round(stalli, 4), round(s, 6))
# 2010-11 0.25 3.2
# 2011-12 0.14 3.508772
# 2014-15 0.248 3.205128

Errori comuni

• Contare 2 cicli persi per ogni salto (anche per quelli non presi) o 1 ciclo per i condizionati.
• Dimenticare che il salto incondizionato è risolto prima (stadio 2): costa 1 ciclo, non 2.
• Usare le percentuali dei salti presi come frazione di tutte le istruzioni invece che dei soli condizionati ($0{,}55$ è il 55% dei condizionati).
• Dare lo speedup come $k \cdot (1 - \text{stalli})$ invece di $k / (1 + \text{stalli})$.
• Scegliere l'opzione "più vicina" (3,23 per 3,2): conta il valore esatto.