AlgKons

Tilbake til Øvinger og Nøtter.

Leking med parallell prosessering

Øvingen denne gang går ut på å leke med parallell prosessering. Vi gir kun en liten innføring og litt inspirasjon i Java, men dere står selvfølgelig fritt til å bruke hvilket språk dere vil. Som en første inspirasjon kan dere ta en titt på følgende klasse, laget av Rune Jensen: Mptest.

Dere kan få en artig utskrift ved å kjøre Mptest på en pc med flere prosessorer, f.eks. en stud/idi-server eller en multicoremaskin hvis dere har det selv. Det kan være lærerikt å sette seg inn i hva Mptest gjør.

Oppgave

Så skal vi lage noe selv. Et sentralt tema under forelesningene om parallelle algoritmer var pekerdobling og parallell prefiks. Vi skal nå implementere det siste. Vi har ingen synkron parallell maskin tilgjengelig, så vi må gjøre noen triks isteden. Vi tenker oss nå at hver tråd er en prosessor. Dere står egentlig fritt til hvordan dere vil lage noe som minner om en parallell prefix på dette grunnlaget, men under beskriver vi noen hint for en måte å gjøre det på. Husk at det finnes mange andre fremgangsmåter.

Vi kan simulere at noe skjer synkront ved å sørge for at alle trådene venter på hverandre på tidspunkter der de må være synkrone. Java 5.0 (eller hva dere vil kalle det) har fått inn endel nytt når det gjelder synkronisering. En av de nye tingene er en klasse som heter CyclicBarrier. Den kan dere lese litt om her: onjava.com, i tillegg til at det selvfølgelig står om den i APIen.

Med CyclicBarrier kan vi få alle trådene som kaller await til å vente til et spesifisert antall tråder har kalt await. Dermed kan vi egentlig få til en slags synkronisering. Et eksempel på dette er vist her: Barrier.java. Deres oppgave blir nå å prøve å finne ut når dere trenger synkronisering når dere lager en slags implementasjon av parallell prefix (dette kan være forskjellig avhengig av om dere vil gjøre ting i henhold til EREW eller CREW f.eks). Deretter skal dere prøve å implementere det. Prøv gjerne å teste litt tidsbruk også, som vist i Mptest.

Innlevering

Denne øvingen blir det ingen innlevering av.

Lykke til!

Simon og Truls