Calcolo Prestazioni Andrea Gasparetto

(1)

Tutorato di architettura degli elaboratori

Calcolo Prestazioni

Andrea Gasparetto – andrea.gasparetto@unive.it

Formulario

T = durata del ciclo di clock in secondi = 1 / F F = numero di cicli di clock al secondo (herzt) = 1 / T Perf

x

= 1 / Exe_Time

x

= performance della macchina x Speedup = Perf

x

/ Perf

y

= Exe_Time

y

/ Exe_Time

x

#cicli = numero di cicli di clock per eseguire un programma = IC * CPI CPI = numero medio di cicli per istruzione

IC = instruction count, numero istruzioni di un programma

Exe_Timex = tempo di esecuzione (CPU) di un programma su una certa macchina = #cicli * T = #cicli / F = IC

* CPI * T = IC * CPI / F

MIPS = milioni di istruzioni per secondo = IC / (Exe_Time * 10

⁶

) = IC / ((IC * CPI / F) * 10

⁶

) = F / CPI * 10

⁶

Esercizio 1

Si considerino due diverse implementazioni, M1 ed M2, dello stesso set di istruzioni, partizionato in tre classi A, B, C:

Classe M1: CPI M2: CPI Utilizzo C1 Utilizzo C2 Utilizzo C3

A 4 2 30% 30% 50%

B 6 4 50% 20% 30%

C 8 3 20% 50% 20%

 M1 ha una frequenza di clock pari a 400 MHz

 M2 ha una frequenza di clock pari a 200 Mhz

 C1 è un compilatore sviluppato dai produttori di M1

 C2 è un compilatore sviluppato dai produttori di M2

 C3 è un compilatore sviluppato da un terzo costruttore.

Si supponga che il codice prodotto dai tre compilatori per uno stesso programma preveda un ugual numero di istruzioni eseguite (IC), ma una diversa distribuzione nelle varie classi come riportato in tabella.

1. Usando C1 su M1 e M2, di quanto M1 è più veloce di M2?

Con il compilatore C1:

CPI

M1

= 4 ∙ 0.3 + 6 ∙ 0.5 + 8 ∙ 0.2 = 1.2 + 3 + 1.6 = 5.8

CPI

M2

= 2 ∙ 0.3 + 4 ∙ 0.5 + 3 ∙ 0.2 = 0.6 + 2 + 0.6 = 3.2

Ricordando che Exe_Time = IC ∙ CPI / F

(2)

Speedup = Perf

M1

/ Perf

M2

= Exe_Time

M2

/ Exe_Time

M1

=

= ((IC ∙ 3.2) / (200 ∙ 10

⁶

)) ∙ ((400 ∙ 10

⁶

) / (IC ∙ 5.8)) = 1.10

2. Usando C2 su M1 e M2, di quanto M2 è più veloce di M1?

Con il compilatore C2:

CPI

M1

= 4 ∙ 0.3 + 6 ∙ 0.2 + 8 ∙ 0.5 = 1.2 + 1.2 + 4 = 6.4 CPI

M2

= 2 ∙ 0.3 + 4 ∙ 0.2 + 3 ∙ 0.5 = 0.6 + 0.8 + 1.5 = 2.9 Ricordando che Exe_Time = IC ∙ CPI / F

Speedup = Perf

M2

/ Perf

M1

= Exe_Time

M1

/ Exe_Time

M2

=

= ((IC ∙ 6.4) / (400 ∙ 10

⁶

)) ∙ ((200 ∙ 10

⁶

) / (IC ∙ 2.9)) = 6.4 / 5.8 = 1.10 3. Se si acquista M1, quale dei tre compilatori conviene usare?

4. Se si acquista M2, quale dei tre compilatori conviene usare?

5. Quale macchina è il miglior acquisto, supponendo che tutti gli altri criteri siano identici, compreso il prezzo?

Utilizzando il compilatore C3:

CPI

M1

= 4 ∙ 0.5 + 6 ∙ 0.3 + 8 ∙ 0.2 = 2 + 1.8 + 1.6 = 5.4 CPI

M2

= 2 ∙ 0.5 + 4 ∙ 0.3 + 3 ∙ 0.2 = 1 + 1.2 + 0.6 = 2.8

I due CPI sono minori rispetto ai casi precedenti. Quindi C3 conviene sia per M1 che per M2 Speedup = Perf

M1

/ Perf

M2

= ((2.8 ∙ IC) / (200 ∙ 10

⁶

)) ∙ ((400 ∙ 10

⁶

) / (5.4 ∙ IC)) = 1.04

Cioè M1 è la macchina da acquistare.

Esercizio 2

Considerare due macchine M1 (a 300 MHz) ed M2 (a 450 Mhz) con le seguenti caratteristiche (rispetto a compilatori prefissati):

Classe M1 : CPI Distrib.

A 1 40%

B 2 30%

C 3 20%

D 4 10%

Sapendo che, per uno stesso programma, in media il codice prodotto per M2 prevede il doppio di istruzioni rispetto a quello prodotto per M1, stabilire:

1. Quale macchina è migliore?

IC

M2

= 2 ∙ IC

M1

CPI

M1

= 1 ∙ 0.4 + 2 ∙ 0.3 + 3 ∙ 0.2 + 4 ∙ 0.1 = 2 CPI

M2

= 1 ∙ 0.4 + 2 ∙ 0.6 = 1.6

Classe M2 : CPI Distrib.

A 1 40%

B 2 60%

(3)

Speedup = Perf

M2

/Perf

M1

= Exe_Time

M1

/ Exe_Time

M2

=

= (IC

M1

∙ CPI

M1

/ F

M1

) ∙ (F

M2

/ (IC

M2

∙ CPI

M2

)) =

= (IC

M1

∙ 2 /(300∙10

⁶

)) ∙ (450∙10

⁶

/ (2 ∙ IC

M1

∙ 1.6)) = 0.9375 La macchina M1 è migliore.

2. Se si usa un nuovo compilatore su M2 che riduce di 1/3 il numero delle operazioni di tipo B, cosa succede alle prestazioni?

CPI

M*

= (1 ∙ 0.4 + 2 ∙ 2/3 ∙ 0.6) / (0.4 + 2/3 ∙ 0.6) = 1.2/0.8 = 1.5 ATTENZIONE: abbiamo normalizzato rispetto ai nuovi pesi!

IC

M*

= (0.4 + 2/3 ∙ 0.6) ∙ IC

M2

= 0.8 ∙ (2 ∙ IC

M1

) = 1.6 ∙ IC

M1

Speedup = Exe_Time

M1

/ Exe_Time

M∙

=

= (IC

M1

∙ 2 / (300 ∙ 10

⁶

)) ∙ (450 ∙10

⁶

/ (1.5 ∙ IC

M1

∙ 1.6)) = 1.25

Esercizio 3

Considerare due macchine M1 (a 3 GHz) ed M2 (a 1.5 GHz). La seguente tabella illustra le classi di istruzioni macchina, i relativi CPI medi e la distribuzione di probabilità delle istruzioni nei programmi considerati.

Macchina M1 Classe CPI Distr.

A 1 40%

B 2 30%

C 3 20%

D 4 10%

Supponendo di sapere che il codice prodotto, compilando lo stesso programma per le due piattaforme, ha identiche prestazioni sia per M1 che per M2, calcolare in che rapporto devono stare i numeri di istruzioni prodotte per i due programmi (ovvero, IC

M1

e IC

M2

) perché ciò si verifichi.

Calcoliamo il CPI medio per M1 e M2:

CPI

M1

= 0.4 ∙ 1 + 0.3 ∙ 2 + 0.2 ∙ 3 + 0.1 ∙ 4 = 2.0 CPI

M2

= 0.6 ∙ 1 + 0.4 ∙ 2 = 1.4

I due tempi di esecuzione si possono ora esprimere come:

Exe_Time

M1

= (CPI

M1

∙ IC

M1

) / Freq

M1

= (2.0 ∙ IC

M1

) / (3.0 ∙ 10

⁹

) = IC

M1

∙ 0.66 ∙ 10

^-9

s. = 0.66 ∙ IC

M1

ns.

Exe_Time

M2

= (CPI

M2

∙ IC

M2

) / Freq

M2

= (1.4 ∙ IC

M2

) / (1.5 ∙ 10

⁹

) = IC

M2

∙ 0.93 ∙ 10

^-9

s. = 0.93 ∙ IC

M2

ns.

Poiché Exe_Time

M1

= Exe_Time

M2

, risulta che deve valere:

0.66 ∙ IC

M1

= 0.93 ∙ IC

M2

==> 0.66 / 0.66 ∙ IC

M1

= 0.93 / 0.66 ∙ IC

M2

==> IC

M1

= 1.41 ∙ IC

M2

Questo significa che il compilatore per M1 genera un eseguibile 1.41 volte più lungo (41% di istruzioni in più rispetto all'eseguibile per M2)

Macchina M2 Classe ICP Distr.

A 1 60%

B 2 40%

(4)

Esercizio 4

Per una certa architettura e per un certo compilatore A, i CPI medi per le varie classi di istruzioni sono i seguenti:

CPI

l/s

= 2 CPI

fp

= 3 CPI

aritm

= 1 CPI

b/j

= 1.8

Il codice macchina prodotto da A contiene istruzioni delle varie classi, che appaiono con le seguenti percentuali:

Perc

l/s

= 30% Perc

fp

= 10%

Perc

aritm

= 40% Perc

b/j

= 20%

Impiegando un nuovo compilatore, B, i CPI medi rimangono invariati, ma l'instruction count (IC) aumenta del 30%, mentre le percentuali delle varie classi di istruzioni diventano:

Perc

l/s

= 20% Perc

fp

= 10%

Perc

aritm

= 60% Perc

b/j

= 10%

Calcolare quale dei due codici prodotti risulta avere il minor tempo di esecuzione e il relativo speedup.

CPI

A

= 2 ∙ 0.3 + 1 ∙ 0.4 + 3 ∙ 0.1 + 1.8 ∙ 0.2 = 1.66 CPI

B

= 2 ∙ 0.2 + 1 ∙ 0.6 + 3 ∙ 0.1 + 1.8 ∙ 0.1 = 1.48

Inoltre, sappiamo che IC

B

= IC

A

+ 0.30 ∙ IC

A

= (1 + 0.30) ∙ IC

A

= 1.30 IC

A

I tempi di esecuzione nei due casi sono:

Exe_Time

A

= IC

A

∙ CPI

A

∙ T = T ∙ (IC

A

∙ 1.66)

Exe_Time

B

= IC

B

∙ CPI

B

∙ T = T ∙ (1.30 ∙ IC

A

∙ 1.48) = T (IC

A

∙ 1.92) Dove T è la durata del ciclo di clock.

Il codice generato dal compilatore A risulta avere un Exe_Time minore quindi è più veloce, da cui:

Speedup = Perf

A

/ Perf

B

= Exe_Time

B

/ Exe_Time

A

= 1.92 / 1.66 = 1.16

Esercizio 5

Un computer a 1 GHz, nell’eseguire un certo programma, ha una prestazione ideale di 500 MIPS. Calcolare il CPI medio ideale.

Poiché il processore è a 1 GHz, e 1/2 G (500 M) sono le istruzioni eseguite in un secondo, allora abbiamo che per ogni istruzione impieghiamo in media 2 cicli (CPI=2).

Più formalmente:

𝑇 _𝑒𝑥𝑒 = #𝑐𝑖𝑐𝑙𝑖

𝐹𝑟𝑒𝑞 = 𝐼𝐶 ∗ 𝐶𝑃𝐼

𝐹

(5)

𝑀𝐼𝑃𝑆 = 𝐼𝐶

𝑇 _𝑒𝑥𝑒 ∗ 10 ⁶ = 𝐼𝐶 ∗ 𝐹

𝐼𝐶 ∗ 𝐶𝑃𝐼 ∗ 10 ⁶ = 𝐹 𝐶𝑃𝐼 ∗ 10 ⁶

Sostituendo abbiamo che 500 = 1G ∙ 10

⁻⁶

/ CPI, e quindi: CPI = ¹⁰ ₅₀₀

³

= 2.

Esercizio 6

Considerare l’esecuzione di un programma P su di una data CPU.

1. Calcolare il CPI ideale, considerando che il CPI medio delle load/store sarebbe 4.5, il CPI medio delle altre istruzioni sarebbe 2, mentre la percentuale di load/store è del 40%.

CPI

ideale

= 0.4 ∙ CPI

load

+ 0.6 ∙ CPI

altro

= (0.4 ∙ 4.5) + (0.6 ∙ 2) = 3.

2. Calcolare i tempi ideali per eseguire P considerando che IC = 200 Milioni, mentre la frequenza della CPU è di 500 MHz.

Se la CPU è a 500 MHz, allora T = 1 / (500 M) s. = 2 ∙ 1/G s. = 2 ns. Il tempo di esecuzione ideale è quindi

CPI

ideale