INF1010 - Obligatorisk oppgave 4, vår 2012
Versjon 1.0
Oppgavebeskrivelse
Du skal lage et program som sorterer ord ved hjelp av flere tråder. Programmet skal ta imot tre parametre på kommandolinjen: et heltall som angir antall tråder som skal brukes til sortering, og filnavn til en innfil og en utfil. Eksempel på kommandolinje:
$ java Sort 128 names.txt out.txt
I dette eksemplet skal programmet bruke 128 tråder, lese inn ord fra filen "names.txt", og skrive resultatet ut til filen "out.txt". Første parameter i kommandolinjen kaller vi «antTråder» («threadCnt») og angir antall tråder som skal brukes til sorteringen. Første linje i innfilen er et heltall, som vi kaller «antOrd» («wordCnt») og angir hvor mange ord det er totalt i resten av filen. Resten av filen inneholder ordene som skal sorteres, adskilt med et eller flere linjeskift.
Programmet skal lese ordene inn i en tabell (array). Hver tråd skal sortere N= «antOrd»/«antTråder» ord (+/- 1). Les først alle ordene inn i en tabell i minnet og starter deretter alle trådene. På denne måten vil du kunne se at flere tråder sorterer raskere enn en (eller noen få). Du skal selv programmere (og skjønne alle detaljer i) den sorteringsalgoritmen du velger. Lag gjerne en enkel algoritme med en grei invariant. Beskriv invarianten du bruker som en (eller flere) kommentarer i programmet ditt.
Når minst to tråder er ferdig med å sortere sine deler av de innleste ordene skal en tråd (du kan velge om det skal være en ny tråd eller en av trådene som allerede kjører) flette sammen de ferdig sorterte delene to og to, osv. inntil alle ord fra innfilen er ferdig sortert. Lag så mange tråder at flettingene skjer i parallell og dermed hurtig hvis maskinen har nok prosessorer. (Legg merke til at det nå er langt færre enn «antTråder» tråder som jobber med å flette).
Du skal også levere en tekstfil der du skriver et lite og uformelt argument om:
- Parallellitet: Hvilke operasjoner kan gå i parallell og hvilke kan ikke gå i parallell i programmet ditt (Amdahls lov)?
- Kjøretiden programmet ditt bruker på sorteringen i forhold til «antOrd» og «antTråder», f.eks. ca. hvor mye øker sorterings-kjøretiden (eller antall operasjoner som utføres) når «antOrd» dobler seg. Stor O-notasjon er ikke pensum og trenger derfor ikke tas med; et lite anslag ved dobling av dataene (og dobling av antall prosessorer) er nok.
Programmet skal virke med «antTråder» mellom 1 og 1000 (og gjerne flere), og skal kunne sortere de to datafilen vist nedenfor. Hvis antall ord i innfilen ikke stemmer med heltallet på første linje skal programmet stoppe med en fornuftig feilmelding. Før programmet skriver det sorterte resultatet på utfilen skal alle ord ligge i en tabell (array), og programmet skal sjekke at denne tabellen har riktig lengde («antOrd») og at det ikke ligger en null-peker som siste element.
Datafiler
Du kan bruke disse filene til testing. Ikke ta dem med i innleveringen din:
names.txt 5163 ord, 40 KB Fra census.gov
sowpods.txt 267751 ord, 2905 KB Fra isc.ro
Innlevering
Siste frist for å levere obligen er ONSDAG 16. mai kl. 14.00. Denne gangen er innleveringsfristen mer absolutt enn tidligere fordi det er lite tid til retting og tilbakemelding før eksamen. Det blir svært begrenset anledning til å levere revidert utgave etter fristen. Ta kontakt med retteren din på forhånd hvis du tror at programmet du leverer kanskje ikke blir godkjent.
På samme måte som i de andre obligatoriske oppgavene så er det lov å snakke med andre studenter om hvordan dere skal løse oppgaven, men du skal likevel skrive ditt eget program, du skal selv taste inn alle tegn i programmet og du skal skjønne alle deler av det. Hvis du ikke kan gjøre rede for alle deler av programmet vil besvarelsen ikke bli godkjent. Husk å nevne evt. samarbeid.
Obligen skal leveres som en .zip eller .tgz-fil som inneholder .java-filene dine og en tekstfil kalt "TIL_RETTER.txt" der du svarer på spørsmålene om kjøretid og parallelitet nevnt ovenfor, og skriver litt info til retter om besvarelsen din, bl.a. om evt. mangler i besvarelsen eller andre spørsmål du har. Hvis alt fungerer skriver du det. Ord-filer og .class-filer skal IKKE være med i leveringen. Hovedprogrammet skal hete Sort.java og det skal gå an å kjøre det som vist i eksemplet ovenfor. Kontakt retteren din på forhånd hvis du vil gjøre det på en annen måte (og gjør det bare på en annen måte hvis du har fått skriftelig godkjenning på epost).