MINIPROSJEKT i fag. 45214 datamaskinarkitektur

(Obligatorisk øving, vårsemesteret 1996)


Innholdsfortegnelse


Innledning

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


Tidsplan - Vår 1996

Ø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


Generelle retningslinjer for arbeid og rapport

  1. Rapporten skal skrives på norsk eller engelsk. Rimelig bra språk og rimelig lite trykkfeil vil bli krevd.
  2. Det utførte arbeid kan om ønskelig overlappe med prosjektarbeid i andre fag eller av privat karakter, men det skal i så fall klart gjøres rede for i rapporten hvilke deler av arbeidet som er utført i dette miniprosjektet. Egen, separat, rapport i fag 45214 skal leveres uansett. Tilsvarende skal faglærer i det andre faget informeres om hvilke deler av arbeidet som er utført som miniprosjekt i fag 45214.
  3. Ved framstilling av måleresultater (under UNIX) kan programmet gnuplot (prøv man gnuplot) anbefales. Bruk av MATLAB kan også være aktuelt.
  4. Arbeider som du tror (ikke vær beskjeden!) DM-gruppen el. IDT kan ha nytte av i.f.m. framtidig undervisning ønskes levert også elektronisk (DOS el. UNIX). Det oppfordres også i å legge ut heler eller deler av arbeidet på internett. (Dette vil kunne hjelpe oss å profilere faget og gruppa).

Om forventet innhold i rapporten

  1. "Vanlig" beskrivelse av arbeidet, inkludert referanser. Se enkle generelle tips om rapportskriving.
  2. Hva har vi lært. En kort beskrivelse av hva en har lært (innenfor fagområdet datamaskinarkitektur og parallell prosessering) gjennom arbeidet med oppgaven.
  3. Kopling til pensum. En kort beskrivelse av hvordan arbeidet bygger på eller utdyper deler av pensum i faget, gjerne med detaljerte henvisninger til pensum
  4. Forslag til øvingsoppgave. En kort vurdering av om du synes ditt/deres arbeid kan benyttes (etter evt. videre bearbeiding) som øvingsoppgave i faget. datamaskinarkitektur, og evt. med skisse av hvordan dere tenker dere dette gjort.
  5. Miniprosjekt-evaluering. En kort vurdering av nytten ved å ha en øvingsoppgave av denne typen, og evt. forslag til forbedringer av opplegget. En kort vurdering av hvordan du (eller gruppen) oppfatter eget arbeid.

Tilbake til INNHOLDSFORTEGNELSE, miniprosjekt fag 45214


Oppgaveforslag - Vår 1997

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.

CRAY T3E (3 oppgaver)

Relevante pekere: er CRAY's hjemmeside og hjemmesiden for NTNU's superdatamaskiner

PDL

PDL(Performance Description Language) er et relativt nytt språk som brukes for å modellere hierarkisk systemer. Oppgaven går ut på å beskrive et enkelt system av eget valg og kjøre relevante ytelse analyser på systemet. Språket er lett å lære og intuitiv og et kort tutorial er tilgjengelig.

Maskinvare Ruter Modul (1/2 personer)

I en ruter, rutingalgoritmet bestemes hvilke av de mulig utgangene skal brukes å sende melding videre mot bestemelsested. En av de mulig ruting algoritmer heter 'dimension-order' ruting. Beskriv ruting algoritme i syntesesbar VHDL og vis korrekt oppførsel med bruk av simulatoren. Design kan være synkron eller asynkron. Hvis to personer tar ut oppgaven kan både synkron og asynkron implementeres og samenlignes.

ClustRa DBMS

Noen oppgaver innen ClustRa prosjektet er tilgjengelig. Ta gjerne kontakt direkt med Tore Sæter for videre informasjon.

Nettverk Traffikk

Analyse av ytelse i Multidatamaskiner kan ikke gjøres uten å ta hensyn til netverk traffikk. Nettverk traffikk oppstår på grunn av de kommunikasjon mønsterene i parallelle applikasjoner. Dessuten har det vært mye uenighet om hvor realistisk de forskjellige metodene er. Oppgaven går ut på å undersøke de mulige metodene og vise forståelse av de fordelene og ulempene med hver av dem.

SB-PRAM

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.

Bulk Synkrone Parallelle maskiner (BSP)

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.

Shared Memory Consistency Models

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).

PARAGON

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.

Hwang's pipenet

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...:-) )

Systoliske array

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.

DLX

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.

Multiprosessor DLX

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.

Superskalar DLX

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.

FPGA-baserte super-datamaskiner sammenlignet med CM-2-baserte super-datamaskiner

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.

Parallaxis-1

(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"

Parallaxis-2, (Rekonfigurerbar parallell-arkitektur)

(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.

Graham

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