INF1010 - V?r 2012


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:

  1. Parallellitet: Hvilke operasjoner kan g? i parallell og hvilke kan ikke g? i parallell i programmet ditt (Amdahls lov)??
  2. 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. 澳门葡京手机版app下载.

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