Matriisikertolaskun kustannusmalli hajautetun ja jaetun muistin rinnakkaistietokoneille

Abstract

Merkittävä rinnakkaisohjelman suorituskykyyn vaikuttava tekijä on laskennan ja viestinnän välinen tasapaino. Tutkielmassa kehitettiin rinnakkaisalgoritmi ja sitä vastaava kustannusmalli matriisikertolaskulle C = AB, missä A, B ja C ovat n × n-matriiseja. Algoritmi ja kustannusmalli kehitettiin sekä hajautetun että jaetun muistin rinnakkaistietokoneille. Kustannusmalli esitettiin kustannusfunktiona.

Tutkielmassa sovellettiin konstruktiivista tutkimusotetta. Ensin perehdyttiin rinnakkaistietokoneisiin, rinnakkaislaskennan teoreettisiin malleihin, kahteen rinnakkaislaskennan ohjelmointiympäristöön sekä matriisikertolaskun rinnakkaistamiseen. Sen jälkeen laadittiin yksinkertaisiin oletuksiin perustuva algoritmi ja sitä vastaava kustannusfunktio sekä jaetulle että hajautetulle muistille. Algoritmit myös toteutettiin ja niitä suoritettiin CSC:n Puhti-supertietokoneessa. Suoritusaikoja mittaamalla määritettiin kustannusfunktioiden parametrit ja saatiin tietoa funktioiden tarkkuudesta.

Kumpikin kustannusmalli osoittautui tyydyttävän tarkaksi, kun n ≤ 512. Mallien avulla voidaan karkeasti arvioida rinnakkaistamisesta saatavaa hyötyä. Tarkkaan suoritusaikojen ennustamiseen mallit eivät kuitenkaan sovi. Ne eivät myöskään huomioi nykyaikaisten rinnakkaistietokoneiden hierarkkista rakennetta. Siksi on syytä olettaa, että suurempia rinnakkaislaskentaympäristöjä varten tarvitaan yksityiskohtaisempi malli.