Generelt
Som en obligatorisk del av faget 45214 skal studentene utføre en større øvingsoppgave som må være godkjent for å kunne ta eksamen i faget. Oppgavens omfang er i utgangspunktet gitt av studieplanen som beskriver 2Øs + 2D i vårsemesteret. Den ene av fordypningstimene regnes med i arbeidet på øvingsoppgaven. Dette gir 3 timer pr. uke. 13 uker i semesteret gir da ca. 40 timer. Øvingen er basert på stor grad av valgfrihet fordi dette av erfaring ofte gir god motivasjon. Studentene kan derfor velge oppgave selv både m.h.p. innhold og angrepsmåte, dog med den forutsetning at de generelle retningslinjer som er skissert i dette notatet følges. For sen innlevering, avskrift ("kok"), eller slett arbeid vil ikke bli akseptert. En øving som vurderes til ikke-bestått vil bli krevd forbedret og levert inn på nytt før eksamen.
Hensikt
Mange temaer innenfor datamaskinarkitektur kan best belyses med forsøk eller detaljerte studier. Ofte oppnår vi også en bedre og mer varig forståelse ved forsøk eller rett og slett bare ved å skrive om et tema. Mange mener også at det er ønskelig å trene studentene i selvstendighet, kreativitet og kvalitetsbevisthet. Miniprosjektet er også ment å tilby en mulighet for å "lukte på" problemstillinger som kan være aktuelle som diplomoppgave.
Tilbake til INNHOLDSFORTEGNELSE, miniprosjekt fag 45214
Øvingen kan utføres alene eller i selvvalgt gruppe på 2-3 studenter.
21/2: Valg av oppgave klart og varslet til vit.ass. i faget (Pauline Haddow)
14/3: Kort statusrapport og disposisjon av rapport leveres til Pauline på papir for godkjenning, evt. tilbakemelding
18/4: Endelig rapport leveres. Obligatorisk muntlig presentasjon, antakelig i øvingstimen denne dagen eller senere i samme uke. Presentasjonen kan gjøres kort og enkel. (Ca. 5-10 min pr. person). Faglærer og vit.ass. vil være til stede og ta presentasjonen med i vurderingen av om arbeidet blir godkjent.
25/4: Beskjed på mail om øving er godkjent eller ikke.
Mai, Juni el Aug.: Korte skriftlige kommentarer
Tilbake til INNHOLDSFORTEGNELSE, miniprosjekt fag 45214
Tilbake til INNHOLDSFORTEGNELSE, miniprosjekt fag 45214
Dette er en liste av forslag på oppgaver dere kan jobbe med. Betrakt dette som ideer, ikke som ferdige oppgaver. Oppgavene kan være ufullstendige og av varierende vanskelighet og omfang. Noe av hensikten med miniprosjektet er å få trening i å gjøre fornuftige antakelser der det er nødvendig, avgrense problemet, samt å dokumentere arbeidet. Kom gjerne med helt selvstendige forslag på oppgaver, evt. nye "vinklinger" på forslagene under. Ta kontakt med vit.ass. hvis du er usikker på om din oppgave eller vinkling virker fornuftig, kanskje kan hun eller faglærer svare.
Relevante pekere: er CRAY's hjemmeside og hjemmesiden for NTNU's superdatamaskiner
Ved Universitetet i Saarbrucken er det utviklet en PRAM maskin. Dette er interessant fordi det er det første seriøse forsøk på å bygge en maskin som tilbyr programmereren å bruke PRAM modellen. PRAM modellen er den mest brukte i teoretisk arbeide med parallelle algoritmer, men har generelt vært regnet som "umulig" å bygge med dagens teknologi.
Ta utgangspunkt i SB-PRAM prosjektet.
Sett deg inn i de forsøk du kan finne på å bygge datamaskiner for bulk synkrone beregninger og beskriv et sammendrag av disse. Lag helst også forslag (skisser) for hvordan du synes en BSP-maskin bør være. Du kan starte med å titte på Lasse's BSP hjemmeside.
Med utgangspunkt i artikkelen til S.V. Adve and K. Gharachorloo; Shared Memory Consistency Models: A Tutorial, (Rice University ECE Technical Report 9512 and Western Research Laboratory Research Report 95/7 September 1995).(postscript) skriv et 5-8 siders godt sammendrag (på norsk el. engelsk) som kan brukes som pensum i faget som supplement eller tillegg til læreboka kap. 5.4. (Gjerne også utkast på innhold til forelesning-foiler om temaet).
Oppgaven baserer seg på generell eksperimentering med denne maskinen, hvor målsettingen er å lære seg om maskinens arkitektur, konstruksjon og sammenheng med ytelse. Beskriv spesielle trekk ved arkitekturen, og finn ut om mulig hvordan disse påvirker ytelsen for ulike typer av beregninger. Studer f.eks. mulige teknikker for synkronisering.
Hva skjedde med dette prosjektet. Ble det fulgt opp?. Brukt i produkter i dag?. To muligheter for å finne ut av dette er WWW-søking (prøv f.eks. LYCOS eller MetaCrawler eller Alta Vista) og Science Citatation Index (Hovedbiblioteket). Prøv også BIBSYS. (MEN, å vise at dere kan søke etter og finne info via WWW er ikke nok. Det antar vi at dere kan...:-) )
Det var mye medvind for dette begrepet på 80-tallet, men hvordan gikk det med konseptet? Har man skiftet til nyere ord på de samme ideene?, ... eller brukes dette mye i prototyper og produkter ?, ... eller var ikke konseptet så vellykket likevel? Se oppgaven "Hwang's pipenet" m.h.p. tips om søking.
Vi har hentet inn en C kompilator som produserer såkalt DLX assembler kode. Denne koden kan kjøres på en simulator som heter DLXsim. DLX er en "gjennomsnitts" RISC prosessor introdusert av Hennessy og Patterson. dlxsim og dlxcc ligger under /home/villrips/b/dam/45214/dlx/bin. Prøv å bruke simulatoren for å prøve ut effekten av hopp-instruksjoner på prosessor-ytelse.
En simulator for en multiprosessor variant av DLX er lagt ut på. "~dam/45214/dlx/dlxmsim". Oppgaven kan gå ut på utprøving av denne. Prøv å illustrere noen av de multiprosessor-problemstillinger som omtales i pensum ved bruk av simulatoren.
En simulator for en superskalar variant av DLX er lagt ut på. "~dam/45214/dlx/superdlx". Oppgaven kan gå ut på utprøving av denne. Prøv å illustrere effekten av superskalaritet ifm. prosessor-ytelse.
Ta utgangspunkt i artikkelen "The CM-2X: A Hybrid CM-2 / Xilinx Prototype", Steven A. Cuccaro, Craig F. Reese, fra IEEE Workshop on FPGAs for Custom Computing Machines, April 5-7, 1993, Napa, California. I tillegg kan artikler om Splash II og Quickturn og andre FPGA-baserte datamaskiner studeres. Målet med oppgaven er å komme med noen tanker/betraktninger om hvordan FPGA-baserte datamaskiner kan konstrueres.
(Egnet for 2 studenter) Vi har hentet inn systemet Parallaxis som er egnet for utprøving av parallelle algoritmer på parallelle maskiner med ulike konfigurasjoner av og sammenkoplinger av prosessorer. Løsning av et problem ved å implementere en eller flere parallelle algoritmer vil ikke kunne bli godkjent i dette faget. Imidlertid vil vi i denne og neste oppgave foreslå hvordan systemet kan brukes til å lære om datamaskinarkitektur. Vi skal studere utførelse av parallel prefix (Se [HB84] side 331) på ulike prosessor-topologier. Realiser denne algoritmen på følgende arkitekturer;
1) Et lineært array av prosessorer, der PE(i) har en kommunikasjonskanal til PE(i+1)
2) Et Illiac-nettverk
3) En hyperkube
Mål og plot tidsforbruket på hver av disse tre arkitekturene for n = 16, 64, 256 og 1024. I hvert tilfelle antar vi at antall prosessorer er lik n. Verktøyet ligger på "~dam/45214/parallaxis"
(Egnet for 2-3 studenter, vanskelig oppgave) Se bakgrunnsinformasjon som beskrevet ovenfor. Her skal vi bruke Parallaxis for å vurdere nytten av rekonfigurerbar maskinvare i.f.m. parallell prefix. Som en ser av beskrivelsen kan en parallell prefix beregning på 8 elementer deles inn i 3 faser, der en bruker ulike kommunikasjonslinjer i hver fase. Vi skal beregne parallell prefix av 512 elementer på 512 prosessorer. Videre antar vi et system der vi i hver fase bare tillater å ha kommunikasjonslinjer som blir benyttet minst en gang i fasen. Dette innebærer at en i fase en bare kan ha kommunikasjonslinjer fra PE(i) til PE(i+1). Videre antar vi at kommunikasjons-nettverket mellom prosessorene er realisert med FPGA eller tilsvarende teknologi som kan rekonfigureres i løpet av x = 1000 Parallaxis-instruksjoner. I noen faser kan det da være raskere å benytte "videresending" v.hj.a. kommunikasjonslinjene brukt i forrige fase, istedetfor å innlede fasen ved å omkonfigurere til et skreddersydd nettverk. Ved implementasjon og målinger, finn ut i hvilke faser en bør omkonfigurere for å gjøre beregningen hurtigst mulig. Prøv å uttrykke dette matematisk som funksjon av x.
R. L. Grahams såkalte multiprosessor anomalier trekkes ofte fram da de bl.a. illustrerer "at ting ikke er så enkelt som en tror". Gi en god beskrivelse av disse, og legg vekt på hvilke antakelser som ligger til grunn for observasjonene.
Lykke til !
IDT, NTNU 13 februar 1997
Tore Sæter, faglærer,
Pauline Haddow, vit.ass,
45214 datamaskinarkitektur.
Tilbake til INNHOLDSFORTEGNELSE, miniprosjekt fag 45214
Tilbake til hjemmeside for 45214