\documentstyle[a4,oving,block]{article-n}
\begin{document}

{\Large \bf L\o sningsforslag til \O ving 6:}

\Oppgave{% Gammel 3.3,   3.7, s. 231 i Hwang

\begin{enumerate}
 \item Minimum-tid (dvs.\ tid dersom dataavhengigheter ikke eksisterer)
       $= k+(M-1)$.

       Forventet forsinkelse pr.\ instruksjon gitt at dataavhengighet
       virkelig eksisterer $= \sum _{n=1}^{L} p_{n}\tau_{n} $.

       Forventet forsinkelse pr.\ instruksjon n\aa r det ikke forutsettes
       noe om hvorvidt den aktuelle instruksjon har dataavhengighet til
       forgjengere $= p_{d}\sum _{n=1}^{L} p_{n}\tau_{n} $.

       Forventet total forsinkelse $= Mp_{d}\sum _{n=1}^{L} p_{n}\tau_{n} $.

       Forventet utf\o relsestid for de $M$ instruksjonene:
       \[ T = \mbox{minimum-tid} + \mbox{total forsinkelse} \]
       \[ = k + (M-1) + Mp_{d} \sum_{n=1}^{L}p_{n}\tau_{n}
       = k + (M-1) + Mp_{d}(k\sum_{n=1}^{k}p_{n} - \sum_{n=1}^{k}np_{n}) \mbox{.}\]
       N\aa\ er
       \[ \sum_{n=1}^{k}p_{n} = \sum_{n=1}^{k}\frac{1}{L} = \frac{k}{L} \]
       og
       \[ \sum_{n=1}^{k}np_{n} = \sum_{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} \mbox{\hspace{1em} .} } \]

 \item 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}} \]
       \[ \Downarrow \]
       \[ \underline{P} = \lim_{M\rightarrow \infty} \frac{M}{T}
            = \underline{\frac{1}{1+p_{d}k\frac{k-1}{2L}}}
          \]
\end{enumerate}
}


\Oppgave{

Vi skal sammenligne hastighets\o 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\aa ndet (Eng.: superpipelined) prosessor av grad n
vil syklustiden for samlebaandet v\ae re $\frac{1}{n}$ av base syklus
til den skalare prosessoren.

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

\[T(1,n) = k + \frac{1}{n}(N-1)(basesykluser)\]

Dermed vil maskimal hastighets\o 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\o kningen $S(1,n) \rightarrow n$, n\aa r antall instruksjoner,
$N \rightarrow \infty$. 

Superskaler:

For en ``super''-skaler prosessor, som henter m instruksjoner samtidig, vil
ideel utf\o relsestid v\ae re:

\[T(m,1) = k + \frac{N - m}{m} (basesykluser)\]

hvor k er tiden som trengs for \aa  utf\o re de f\o rste m instruksjonene
gjennom samleb\aa ndet, og $\frac{N-m}{m}$ er tiden for de N-m gjenst\aa
ende instruksjonene, hvor m utf\o res pr. syklus.

Den ideelle hastighets\o 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\o kningen $S(m,1) \rightarrow m$, n\aa r antall instruksjoner, $N
\rightarrow \infty$.

Superpipeline og superskalar:

For en ``super''-skalar, ``super''-samleb\aa ndet prosessor f\aa 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\o kningen $S(m,n) \rightarrow m x n$, n\aa r antall
instruksjoner, $N \rightarrow \infty$

En skalar prosessor p\aa  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\aa r $(m,n) = (2,6)$.

Noe upresist kan vi derfor p\aa st\aa  at DEC's Alpha prosessor er $m x n = 2
x 6 = 12$ ganger raskere enn en prosessor p\aa  25 Mhz.

}


\end{document}

























