Viikko 10 - Rinnakkaisuus ja yhtäaikaisuus

Johdanto

Tällä harjoituskerralla tutustutaan kahteen, toisistaan lähes täysin erilliseen, käsitteeseen, rinnakkaisuuteen yhtäaikaisuuteen. Rinnakkaisuus on ollut pitkään tärkeä funktio-ohjelmoinnin kehittämisen motivaattori ja aluksi toivottiinkin, että sivuvaikutuksettomat funktio-ohjelmat voitaisiin automaattisesti rinnakkaistaa. Tämä osoittautui saavuttomattomaksi unelmaksi, mutta siitä huolimatta funktio-ohjelmointi näyttää kyntenstä erityisesti nykyisessä moniprosessoriympäristössä — on selvää, että tehokas rinnakkaistus vaatii ohjelmoijalta suurta työtä ja aivan erityisesti tiukkaa kuria sivuvaikutusten kanssa, mikä tekee funktiokielistä erityisen soveliaita rinnakkaisohjelmointiin.

Yhtäaikaisuus puolestaan tuntuu keskittyvän samalla tavalla sivuvaikutusten hallintaan ja suurin työ monisäikeisessä ohjelmassa onkin pitää huoli siitä, että ohjelman globaali tila pysyy konsistenttina. Mikäli kielessä olevat muuttujat ovat vähäisiä lukumäärältään ja sopivasti rajattuja käy ilmi, että on olemassa tehokkaita työkaluja, joilla yhtäaikaisia ohjelmia voidaan kirjoittaa ilman hankalia lukkoja ja semaforirakenteita.

Näiden harjoitusten tekemistä auttaa erityisesti Simon Marlowin erinomainen rinnakkaisuustutoriaali.

Käsitteet

1. Mitä eroa on yhtäaikaisella (concurrent) laskennalla ja rinnakkaisella (parallel) laskennalla?
2. Mitä tarkoitetaan deterministisellä ja epädeterministisellä ohjelmalla
3. Mitä sanoo Ahmdalin laki?

Yhtäaikaisuus ja Transaktiomuisti

Lue ensin Real World Haskell, kappale 28

Rinnakkainen jono

Tavallisen rajapinnan sijaan rinnakkaiset ohjelmat kommunikoivat usein käyttäen jonoja. Sen sijaan, että yhdestä säikeestä kutsutaan tiettyä toiminnallisuutta, laitetaankin pyyntö jonoon, odottamaan, että asiaa hoitava säie käsittelee sen. Tätä varten tarvitaan tietysti turvallinen rinnakkainen jonorakenne, jota voidaan purkaa toisesta päästä samalla kun sitä täytetään toisesta.

1. Toteuta jono käyttäen MVar abstraktiota. Käytä seuraavaa rajapintaa:

newJono   :: IO ( Jono a)
writeJono :: Jono a -> a -> IO ()
readJono  :: Jono a -> IO a

(Ts. Toteuta itse, äläkä käytä valmista Chan tyyppiä)

2. Toteuta jono käyttään transaktiomuistia. Käytä seuraavaa rajapintaa:

newTJono :: STM (TJono a)
writeTJono :: TJono a -> a -> STM ()
readTJono :: TJono a -> STM a 

(Ts. Toteuta itse, äläkä käytä valmista TChan tyyppiä)

3. Testaa käyttäen quickcheckiä. Käytä Quickcheck.Monadic modulia. Monadisen koodin testaamisen ideaan pääsee kiinni alkuperäisen artikkelin kautta.

Pikaviestipalvelu

Tässä tehtävässä toteutetaan yksinkertainen pikaviestiohjelma. Ohjelma kuuntelee yhteyksiä annettuun porttiin ja ottaa yhteyden annettuihin ip osoitteisiin. Tämän jälkeen ohjelma lukee mitä komentoriville kirjoitetaan ja lähettää sen kaikille kumppaneilleen samanaikaisesti. Ohjelman tulee myös tulostaa ja tallettaa saapuvia viestejä tiedostoon.

1. Toteuta prosessi, joka odottaa yhteyksiä ja laukaisee jokaiselle yhteydelle oman säikeensä.
2. Toteuta prosessi, joka lukee tekstiä ja laittaa sitä rivi kerrallaan jonoon.
3. Toteuta prosessi, joka tulostaa tekstiä jonosta.
4. Toteuta prosessi, joka tallentaa tekstiä jonosta tiedostoon.
5. Yhdistä prosessit jonojen avulla.

Vinkkejä: 1, 2

Rinnakkaisuus

Tässä tehtävässä on tarkoitus leikkimielisesti kokeilla rinnakkaisuutta. Mikäli onnistun vakuuttamaan yli-insinöörimme siitä, että kurssilaiset tarvitsevat pääsyn laskentapalvelimelle, tee seuraavat tehtävät 64 ytimen paasikivi.jyu.fi koneessa. (Huomaa, että siellä ghc on asennettu hakemistoon /usr/local/ghc). Muussa tapauksessa, toteuta virtuaalikoneella tai läppärillä ja käytä mielikuvitusta.

Katso myös How to think about parallel programming, not!.

Suorakaiteiden paluu

Tässä tehtävässä käytetään parin edellisen harjoituksen tuloksia. Tarkoituksena on tehdä ohjelma, joka mahdollisimman nopeasti parsii laskee edelisten demojen suorakaidelausekkeita.

Voit myös vaihtaa aihetta, jos haluat rinnakkaistaa jonkun muun ohjelman.

1. Tee ohjelma, joka yhdistää kaksi edellistä harjoitusta ja laskee tiedostossa annetut yhdiste/leikkaus lausekkeet.
2. Käytä Eval-monadia ja rinnakkaista ohjelmasi.
3. Käytä Parallel Strategy lähestymistä ja rinnakkaista ohjelmasi.

4. Käytä Par-monadia ja rinnakkaista ohjelmasi

5. Arvioi tuloksiasi Simon Marlowin rinnakkaistutoriaalin näkökulmasta. Saitko hyötyä rinnakkaisuudesta? Miten voisit parantaa tilannetta?