Løsningsforslag til Øving 6:

\underline{Oppgave 1:}

a) Minimum-tid (dvs. tid dersom dataavhengigheter ikke eksisterer) = k + (M − 1).

Forventet forsinkelse pr. instruksjon gitt at dataavhengighet virkelig eksisterer = ∑_{n=1}^{L} p_{n}τ_{n}.

Forventet forsinkelse pr. instruksjon når det ikke forutsettes noe om hvorvidt den aktuelle instruksjon har dataavhengighet til forgjengere = p_{d} ∑_{n=1}^{L} p_{n}τ_{n}.

Forventet total forsinkelse = Mp_{d} ∑_{n=1}^{L} p_{n}τ_{n}.

Forventet utførelsestid for de M instruksjonene:

T = minimum-tid + total forsinkelse

= k + (M − 1) + Mp_{d} ∑_{n=1}^{L} p_{n}τ_{n} = k + (M − 1) + Mp_{d}(k ∑_{n=1}^{k} p_{n} − ∑_{n=1}^{k} np_{n}).

Nå er

∑_{n=1}^{k} p_{n} = ∑_{n=1}^{k} \frac{1}{L} = \frac{k}{L}

og

∑_{n=1}^{k} np_{n} = ∑_{n=1}^{k} \frac{n}{L} = \frac{k(k + 1)}{2L}

slik at

\underline{T} = k + (M − 1) + Mp_{d}(\frac{k^{2}}{L} − \frac{k(k + 1)}{2L}) = \underline{k + M − 1 + Mp_{d}k \frac{k − 1}{2L} .}

b) Ytelsen:

\frac{M}{T} = \frac{M}{k + M − 1 + Mp_{d}k \frac{k−1}{2L}}

= \frac{1}{1 + \frac{k−1}{M} + p_{d}k \frac{k−1}{2L}}

⇓

\underline{P} = lim_{M→∞} \frac{M}{T} = \underline{\frac{1}{1 + p_{d}k \frac{k−1}{2L}}}

\underline{Oppgave 2:}

Vi skal sammenligne hastighetsøkningen for en superpipeline, en superskalar og en superpipeline og superskalar maskin med en skalar maskin med T (1, 1) = k + N − 1.

Superpipeline: For en “super”-samlebåndet (Eng.: superpipelined) prosessor av grad n vil syklustiden for samlebaandet være \frac{1}{n} av base syklus til den skalare prosessoren.

Minimum tid som trengs for åutføre N instruksjoner for en super-samlebåndet maskin av grad n med k steg i samlebåndet vil bli:

T (1, n) = k + \frac{1}{n}(N − 1)(basesykluser)

Dermed vil maskimal hastighetsøkning bli:

S(1, n) = \frac{T (1, 1)}{T (1, n)} = \frac{k + N − 1}{k + (N − 1)/n} = \frac{n(k + N − 1)}{nk + N − 1}

Hastighetsøkningen S(1, n) → n, når antall instruksjoner, N → ∞. Superskaler: For en “super”-skaler prosessor, som henter m instruksjoner samtidig, vil ideel utførelsestid være:

T (m, 1) = k + \frac{N − m}{m}(basesykluser)

hvor k er tiden som trengs for åutføre de første m instruksjonene gjennom samlebåndet, og \frac{N−m}{m} er tiden for de N-m gjenstående instruksjonene, hvor m utføres pr. syklus. Den ideelle hastighetsøkningen for dette tilfellet vil bli:

S(m, 1) = \frac{T (1, 1)}{T (m, 1)} = \frac{k + N − 1}{N/m + k − 1} = \frac{m(k + N − 1)}{N + m(k − 1)}

Hastighetsøkningen S(m, 1) → m, når antall instruksjoner, N → ∞. Superpipeline og superskalar: For en “super”-skalar, “super”-samlebåndet prosessor får vi:

T (m, n) = k + \frac{T (1, 1)}{T (m, n)} = \frac{k + N − 1}{k + (N − 1)/(mn)} = \frac{mn(k + N − 1)}{mnk + N − m}

Hastighetsøkningen S(m, n) → mxn, når antall instruksjoner, N → ∞ En skalar prosessor på25 Mhz, henter 1 instruksjon pr. syklus, og har (m, n) = (1, 1). DEC’s Alpha prosessor DEC 21064-A, 150 MHZ, henter maskimalt to instruksjoner pr. syklus. Den har en syklustid som er 150Mhz/25MHz = 6 ganger det skalare tilfellet, og får (m, n) = (2, 6). Noe upresist kan vi derfor påståat DEC’s Alpha prosessor er mxn = 2x6 = 12 ganger raskere enn en prosessor på25 Mhz.