a) Utled en formel for den hastighetsøkning, S(k,n), en kan oppnå ved å prosessere en vektor på n elementer i en trinn-prosessor (Eng. pipeline) med k trinn sammenliknet med prosessering på en vanlig prosessor der hvert element må prosesseres ved k delberegninger som hver tar 1 tidsenhet (og som må utføres etterhverandre). Trinn-prosessoren består av k segmenter som hver tar 1 tidsenhet.
Hvordan varierer hastighetsøkningen som funksjon av n?
b) Tegn nettverket "3-cube-connected-cycles", og tegn og forklar hvordan et "k-cube-connected-cycles" (k-CCC) nettverk konstrueres ved å ta utgangspunkt i en k-dimensjonal hyperkube med 2k noder. Uttrykk antall noder i et slikt k-CCC nettverk som funksjon av k.
c) Hva mener vi med diameteren i et nettverk, og hva er diameteren i en hyperkube og i en "k-cube-connected-cycles" (k-CCC)?
d) En annen viktig parameter for et nettverk er node-grad (også kalt valens). Anta at du bruker et nettverk for sammenkopling av prosessorer i en multiprosessor. Hvordan bør parameteren node-grad utvikle seg som funksjon av antall prosessorer for å oppnå god skalerbarhet, og hvilken gode egenskap har k-CCC i denne sammenheng?
e) Anta et simuleringsprogram der den underliggende modellen er et to-dimensjonalt (2D) rutenett med et stort antall punkter, og at en "ideell" parallellisering kunne ha vært et punkt lagret i hver prosessor på en parallell-maskin der prosessorene er knyttet sammen med et 2D nettverk. I praksis vil et antall punkter være lagret i en prosessor da en ikke har nok fysiske prosessorer tilgjengelig, eller fordi en av andre årsaker ønsker å begrense antall fysiske prosessorer som benyttes. Ved kjøringen av et slikt simuleringsprogram er det ønskelig at en oppnår en rimelig balanse mellom utnyttelsen av maskinens beregningskapasitet (i hver prosessor) og maskinens kommunikasjons-kapasitet (mellom prosessorene). Forklar begrepene problem-granularitet og maskin-granularitet, og hvordan maskin-granulariteten påvirker hvor finkornet vi kan parallellisere et slikt problem (her et simuleringsprogram).
a) Forklar hovedprinsippet i teknikken "wormhole routing" for meldingsutveksling, og hvordan denne metoden skiller seg fra såkalt "store and forward" ruting. Tegn gjerne en figur. Hvilke fordeler har "wormhole routing"?
b) Forklar kort hva som menes med E-kube ruting. Ta utgangspunkt i følgende eksempel: Vi har en "6-ary 3-cube" (dvs. 3D-rutenett med 6 noder i bredden i hver dimensjon), der en nodes adresse angis som (X,Y,Z) der X, Y, Z hver er et heltall i området 0..5. Nodene har en enveis-forbindelse til nabo-noden foran (+1) og bak (-1) langs hver dimensjon. Vi har ingen såkalte "wrap-around" forbindelser. Anta at vi skal sende en melding fra node (1, 5, 2) til (5, 1, 4). Beskriv hvilken vei denne meldingen vil gå, og beskriv denne rutings-strategien for et vilkårlig avsender/mottaker par.
c) Diskuter evt. fordeler og ulemper ved E-kube ruting. To stikkord er vranglås og fordeling av meldingstrafikk på nettverket.
d) E-kube ruting er en enkel rutingsstrategi. Forklar hvordan en pakke med fordel kan bygges opp for at logikken for å utføre E-kube ruting i hver enkelt node kan gjøres enkel og rask. Forklar denne logikken, gjerne v.hj.a. pseudokode og/eller en figur.
a) CM-5 fra Thinking Machines Corp. har tre sentrale nettverk. Forklar meget kort hoved-funksjonen til hver av disse. Det er tilstrekkelig å gi nettverkenes rette navn. Ved utførelse av parallelle beregninger på maskinen utfører to av nettverkene en sentral rolle. Det ene nettverket er realisert som et komplett binært tre, mens det andre er et såkalt "fat-tree". Forklar hvorfor dette er et logisk valg sett i lys av hovedfunksjonen til de to nettverkene.
b) Forklar hovedprinsippet bak strukturen "fat-tree" (tegn gjerne en figur). (2 varianter er presentert i læreboka, og en eksakt definisjon kreves ikke). Nevn to fordeler en slik struktur kan ha for sammenkopling av prosessorer i en parallell datamaskin framfor et binær-tre.
c) DASH (Directory Architecture for Shared Memory) er en såkalt hurtigbuffer-koherent NUMA multiprosessor. Tegn en skisse av arkitekturen og forklar ved å henvise til moduler/enheter i arkitekturen følgende aspekter: 1) Hva som ligger i begrepet NUMA og hvordan arkitekturen "i rimelig grad" er skalerbar m.h.p. antall prosessorer. 2) Hvordan arkitekturen realiserer hurtigbuffer-koherens på en skalerbar måte.
d) Gjør en begrunnet vurdering av om du ville ha valgt en CM-2 maskin eller en CM-5 maskin hvis du skulle anskaffe en av disse maskinene for bare å kjøre følgende applikasjon; Bildebehandling der bildene finnes i tre formater, med henholdsvis 1, 8 og 16 bit pr. bilde-element (piksel). Vurder bare maskinenes arkitektur, ikke faktiske ytelser, pris, eller alder siden lanseringstidspunkt.
a) Forklar kort forskjellen på begrepene arkitektur og implementasjon. Hvilke egenskaper tilhører arkitekturen, og hvilke tilhører implementasjonen av en prosessor.
b) I utformingen av Alpha-arkitekturen har en valgt løsninger som innebærer at instruksjonene i stor grad blir uavhengige av hverandre. Hvorfor kan dette gi bedre ytelse?
c) Beskriv kort flest mulige av de valg som er benyttet i Alpha arkitekturen for å oppnå slik uavhengighet mellom instruksjonene?
d) Forklar kort hva som ligger i begrepet "multithreading", og hvordan dette kan brukes til å skjule langsomme aksesser til lageret (Eng. latency hiding)
a) To sentrale hoved-teknikker for å opprettholde koherente hurtigbuffere i en multiprosessor er buss-snusing (Eng. bus-snooping) og katalog-metoden (Eng. directory based protocols). Videre kan katalog-metoden deles inn i komplette kataloger, begrensete kataloger, og lenkete kataloger. Forklar kort forskjellen mellom disse tre, samt eventuelle fordeler/ulemper ved hver av disse variantene av katalog-metoden.
b) SCI, Scalable Coherent Interface, er en standard som inneholder en mekanisme for å opprettholde koherente hurtigbuffere i massivt parallelle systemer. Forklar denne mekanismen, og vektlegg spesielt hvordan en oppnår skalerbarhet.
a) Forklar kort hva som er den vesentligste forskjellen mellom en statisk og en dynamisk dataflytmaskin. Nevn minst to egenskaper i et dataflytprogram som kan oppnås på en dynamisk dataflytmaskin, men som er vanskelig eller tungvindt å realisere på en statisk dataflytmaskin.
b) I forbindelse med Valiant's BSP modell snakker en om begrepet parallell slakk. Forklar dette begrepet, og beskriv hvordan graden av parallell slakk i et program påvirker muligheten for effektiv utførelse av programmet på en BSP-basert maskin.
Du er ansatt som systemarkitekt i firmaet Lasse & Bjørnars Lynraske Regne-Maskiner (LB-z-RM) som utvikler komplette systemløsninger til noen meget sjeldne kunder. Firmaet skal nå utvikle en maskin for behandling av sort-hvitt bilder i sann tid. Hvert bilde inneholder 512 x 512 punkter, og er representert med 1 bit pr. piksel. Det ankommer 60 bilder i sekundet som skal prosesseres i samme hastighet. Kompetansen og ressursene i firmaet er begrenset slik at du må sette sammen en maskin ved å velge eksakt en delløsning fra hver av de 4 listene nedenfor. Velg delløsninger slik at du mener du får en god totalløsning. Begrunn ditt valg så godt som mulig, og beskriv evt. manglende delløsninger for å oppnå en god begrunnelse. Valg fra listen uten begrunnelse gir ingen poeng. Beskriv også hvordan du vil løse IO-problemet på din maskin.
Prosessorer: 1) 16 k "bit-slice" prosessorer realisert i VLSI 2) 64 mikroprosessorer av typen Alpha el.l. 3) 1 stk. CRAY Y-MP Lagerstruktur: 1) Ett stort felles lager, aksessert via felles buss 2) Små men hurtige lokale bit-adresserbare lagere i hver prosessor 3) Cache, hovedlager og disk knyttet til hver prosessor Sammenkopling av prosessorene: 1) SCI 2) Hyperkube 3) Blitzen X-net 4) Alle-til-alle krysskopling "Operasjonsmodus" for prosessorene: 1) MIMD 2) SIMD 3) "load-and-go bus-shuffling" 4) BSP