\documentstyle[a4,oving,block]{article-n}
\begin{document}
\HodeLosn{2}
\Oppgave{% Gammel 5.2,  Hwang&Briggs: 5.9, s. 391

\begin{enumerate}
 \item $N$ innganger kan permuteres p\aa\ $N!$ forskjellige m\aa ter.

 \item Omega-nettet har $n$ trinn, hver med $N/2 = 2^{n-1}$ celler
       (svitsje-bokser); totalt har nettet alts\aa\ $n\cdot 2^{n-1}$ celler.

       Siden det her kun er snakk om permutasjoner (ikke kringkasting), benyttes
       to tilstander (parallell og kryss) i hver celle. Det samlede antall
       tilstander for nettet blir da $2^{\# celler} = 2^{n\cdot 2^{n-1}} =
       N^{N/2}$, og dette blir da antallet forskjellige permutasjoner som
       kan utf\o res.

       $N = 8 \Rightarrow \mbox{\# permutasjoner} = 8^{4}
       \Rightarrow \mbox{prosentandelen} = 8^{4}/8! = 10.16\%$.

 \item Skriver
       \[ \begin{array}{lclcl}
       T & = & (t_{n-1}t_{n-2}\cdots t_{1}t_{0})_{2} & , & \\
       S & = & (s_{n-1}s_{n-2}\cdots s_{1}s_{0})_{2} & , & \mbox{og} \\
       D & = & (d_{n-1}d_{n-2}\cdots d_{1}d_{0})_{2} & ; &
                                                t_{i} = s_{i} \oplus d_{i} \; .
       \end{array} \]
       Rutingen foreg\aa r da slik: P\aa\ det $i$'te trinnet settes svitsje-cellen
       til parallellforbindelse dersom $t_{i}=0$, og til kryssforbindelse
       dersom $t_{i}=1$.

       Fordeler ved \aa\ benytte $T$ istedet for $D$ er blant annet:
       \begin{itemize}
        \item Enkel ruting : Svitsje-cellenes funksjon angis eksplisitt av
              ett eneste bit i rutingsmerket.
        \item Mottakeren kan identifisere senderen ved $S = D \oplus T$
       \end{itemize}

 \item Betrakt tilfellet at informasjon skal kringkastes fra PE$_{s}$, med
       adresse $S = (s_{n-1}s_{-2}\cdots s_{1}s_{0})_{2}$, til $2^{h}$
       destinasjoner. Adressene til disse destinasjons-PE'ene avviker fra
       hverandre i $h$ bit, de resterende er like. La {$\cal D$} v\ae re mengden
       av de $h$ bitnummer ($0 \ldots n-1$) som angir hvilke bit som er
       forskjellige i de $h$ destinasjonsadressene. Rutingalgoritmen blir da,
       for trinn $i$:
       \begin{center}
        \begin{tabbing}
          aaa \= aaa \= aaa \= \kill
          {\bf if} $i \in {\cal D}$ \\
          {\bf then} \\
          \> {\bf if} $s_{i}=0$ \\
          \> {\bf then} \\
          \> \> Kringkast fra den \o vre inngangen til begge utganger \\
          \> {\bf else} \\
          \> \> Kringkast fra den nedre inngangen til begge utganger \\
          {\bf else} \\
          \> F\o lg regelen fra c) for denne cella
        \end{tabbing}
       \end{center}
\end{enumerate}
}

\newpage
\Oppgave{

\begin{enumerate}


\item 
For {\aa} konstruere et nettverk for en 64-node multidatamaskin, kan
vi bruke:

\begin{itemize}

\item En 3D-torus med 4 noder langs hver dimensjon.  De relevante
parametrene blir: $d = 3 \lfloor r/2 \rfloor = 6, D = 3 \lfloor r/2
\rfloor = 6$, og $l = 3N = 192$.  Dermed blir $d \times D \times l =
6912$.

\item En 6-dimensjonell hyperkube.  De relevante parametrene blir: $d
= n = 6,  D = n = 6$, og $l = n \times N/2 = 6 \times 64/2 = 192$.  Vi
har dermed $d \times D \times l = 6912$.

\item En CCC med dimensjon $k = 4$.  De relevante parametrene blir: $d
= 3, D = 2k - 1 + \lfloor k/2 \rfloor = 2 \times 4 - 1 + \lfloor 4/2 
\rfloor = 9$, og $l = 3N/2 = 96$.  Dermed blir $d \times D \times l =
2592$. 

\end{itemize}

Resultatene er listet opp i tabellen under:
\begin{table}[htb]
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|} \hline 

Nettverk	& $d$	& $D$	& $l$	& $(d \times D \times l)^{-1}$
& Rank \\ \hline \hline
Torus	& 6 & 6 & 192 & 1/6912 & 2 \\ \hline
6-kube	& 6 & 6 & 192 & 1/6912 & 2 \\ \hline
CCC	& 3 & 9 & 96 & 1/2592 & 1 \\ \hline
\end{tabular}
\end{center}
\end{table}

Hvis kvaliteten til et nettverk skal m{\aa}les ved ${(d \times D
\times l)}^{-1}$, er CCC-nettverket bedre enn 3D-torus og 6-kuben.  En
3D-torus og 6-kube vil ha samme kvalitet.

\item 

\begin{itemize}

\item

3D-torus og hyperkuben har de samme nettverks-parametrene:   Vi har
$\sum_{i=1}^{D} = \frac{(1 + 6) \times 6}{2} = 21$.  $P(i)$ er
sannsynligheten for informasjonsutveksling mellom noder ved en avstand
$i$.  Vi har s{\aa}ledes:
\[ P(1) = \frac{6}{21}, P(2) = \frac{5}{21}, P(3) = \frac{4}{21}, P(4)
= \frac{3}{21}, P(5) = \frac{2}{21}, P(6) = \frac{1}{21}. \]

$\alpha$ blir da:
\[ 1 \times \frac{6}{21} + 2 \times \frac{5}{21} + 3 \times
\frac{4}{21} + 4 \times \frac{3}{21} + 5 \times \frac{2}{21} + 6
\times \frac{1}{21} = \frac{56}{21} = \frac{8}{3}.\]

\item 

For CCC har vi $\sum_{i=1}^{D} = \frac{(1 + 9) \times 9}{2} = 45$.
$P(i)$ blir dermed:

\[ P(1) = \frac{9}{45}, P(2) = \frac{8}{45}, P(3) = \frac{7}{45}, P(4)
= \frac{6}{45}, P(5) = \frac{5}{45}, P(6) = \frac{4}{45}. \]
\[ P(7) = \frac{3}{45}, P(8) = \frac{2}{45}, P(9) = \frac{1}{45}.\]

$\alpha$ blir her: 

\[ 1 \times \frac{9}{45} + 2 \times \frac{8}{45} + 3 \times
\frac{7}{45} + 4 \times \frac{6}{45} + 5 \times \frac{5}{45} + 6
\times \frac{4}{45} + 7 \times \frac{3}{45} + 8 \times \frac{2}{45} +
9 \times \frac{1}{45} =  \frac{165}{45}.\]

Resultatene er listet opp i tabellen under:

\end{itemize}

\begin{table}[htb]
\begin{center}
\begin{tabular}{|c|c|c|} \hline 
Nettverk	& Gj.sn internode avstand & Rank \\ \hline \hline
Torus	& $\frac{8}{3} = 2.67$ & 1 \\ \hline
6-kube	& $\frac{8}{3} = 2.67$ & 1 \\ \hline
CCC	& $\frac{165}{45} = 3.67$ & 2 \\ \hline
\end{tabular}
\end{center}
\end{table}

Konklusjonen her blir at $\alpha$ til 4-CCC nettverket er st{\o}rre en
det til 6-hyperkuben og 3D-torus.  6-hyperkuben og 3D-torus har samme
$\alpha$-verdi.  Likheten mellom 6-hyperkuben og 3D-torus er
sl{\aa}ende:  Faktisk har det blitt vist [Wang89] at n{\aa}r $k = 4$
(som her), vil en $k$-n{\ae}r $n$-kube v{\ae}re eksakt tilsvarende en
$2n$-dimensjonell bin{\ae}r hyperkube.

\end{enumerate}
}

\end{document}
