Oppgave 1
Du blir spurt om å konstruere et nettverk for en multi-datamaskin
med 64 noder, og skal studere disse nettverks-arkitekturene nærmere:
3D-torus,6-dimensjonell hyperkube, og CCC
(cube-connected-cycles) med minimal diameter.
a)
La d være node-graden (node degree), D nettverks-diameteren, og
l det totale antall linker i nettverket. Anta at kvaliteten på
nettverket kan måles ved
1 / (d x D x l).
Ranger de
tre forskjellige arkitekturene med tanke på dette
kvalitets-målet.
b)
Den gjennomsnittlige avstanden mellom to noder, alpha er
definert som det gjennomsnittlige antall linker langs den korteste
veien en melding må reise fra en node til en annen. Gjennomsnittet
beregnes for alle (avsender, mottaker) par. Ranger de tre
arkitekturene basert på deres alpha-verdi, når du antar at
sannsynligheten for at en node vil sende en melding til alle andre
noder med avstand i er:
(D - i + 1 ) / sum(k = 1..D)
hvor D er nettverks-diameteren.
Oppgave 2
Betrakt et Omega-nett med N innganger, (N = en potens of 2) hvor hver svitsje-celle er
individuelt styrt.
Oppgave c) og d) er en smule vanskelig. Mer informasjon kan finnes i
[Hwang93], s. 341-343.
a)
Generelt: Hvor mange permutasjoner (en til en og på -
avbildning) kan defineres over N innganger?
b)
Hvor mange permutasjons-funksjoner kan utføres av Omega-nettet?
Hvor stor prosentandel av det teoretisk mulige antall blir dette når N=8?
c)
For et vilkårlig kilde(S)-destinasjons(D)-par kan veien gjennom
nettet unikt bestemmes av destinasjons-adressen D. Istedet for å bruke D,
velger vi benytte T = (S xor D) som rutings-merke. Vis hvordan T
alene kan brukes til å bestemme veivalget. Prøv å finne noen fordeler ved å
benytte T som rutings-merke.
d)
Omega-nettet er i stand til å foreta kringkasting (en til
mange - avbildning). Finn en enkel rutingsalgoritme som foretar en
slik kringkasting for det tilfellet at antallet destinasjonsnoder er en
potens av 2 og at disse adressene avviker fra hverandre i de h minst
signifikante bit. Angi hvilken gruppe PE'er det kringkastes til.
Pauline Haddow(pauline@idt.unit.no)
Last modified: Fri Oct 13 12:04:49 1995