É«É«À²

Väitöskirjan nimi: Massively Parallel Algorithms for Sparse Graphs

³Õä¾±³Ù³Ù±ð±ô¾±Âáä: Rustam Latypov
³Õ²¹²õ³Ù²¹±¹Ã¤¾±³Ù³ÙäÂáä: professori Artur Czumaj, University of Warwick, Yhdistynyt kuningaskunta
Kustos: professori Jara Uitto, Aalto-yliopiston perustieteiden korkeakoulu 

Sosiaalinen media, karttapalvelut ja biologiset molekyyliverkostot ovat esimerkkejä massiivisista verkoista, joissa miljardit solmut kytkeytyvät toisiinsa. Tällaisten verkkojen analysoiminen on yksi nykypäivän tietotekniikan keskeisistä haasteista. Yksittäinen tietokone ei pysty käsittelemään näin suuria tietomääriä riittävän nopeasti. Tämän vuoksi työ jaetaan tuhansille koneille, jotka ratkaisevat ongelmaa yhdessä rinnakkain. Globaalin datamäärän kasvaessa tehokkaat rinnakkaisalgoritmit ovat yhä keskeisemmässä roolissa digitaalisen elämän ylläpidon kannalta.

Tämä väitöskirja tarkastelee rinnakkaisjärjestelmien tehokkuutta perustavanlaatuisten verkko-ongelmien ratkaisemisessa. Tutkimuksen kohteena ovat tasaisen harvat verkot, joissa yhteyksiä on vähän solmujen määrään nähden. Nämä verkot ovat osoittautuneet erityisen hankaliksi rinnakkaislaskennan kannalta, vaikka ne ensisilmäyksellä vaikuttavatkin yksinkertaisilta.

Väitöskirja ratkaisee useita avoimia ongelmia ja parantaa alan aiempia huipputuloksia. Työssä kehitetään uusia algoritmeja klassisiin ongelmiin kuten yhtenäisyys, verkon väritys ja maksimaalinen riippumaton joukko. Algoritmit ovat todistetusti nopeimmat mahdolliset ja suunniteltu käyttämään muistia mahdollisimman säästeliäästi, käytännössä vain sen verran kuin itse verkon tallentamiseen tarvitaan. Tulokset osoittavat, että ongelmia voidaan ratkaista vaikeissakin verkoissa tehokkaasti rinnakkain, kun taustalla ovat oikeanlaiset algoritmiset tekniikat.

Avainsanat: Massiivisen rinnakkaislaskennan malli, tasaisen harvat verkot, yhtenäisyys, verkon väritys, maksimaalinen pariutus, maksimaalinen riippumaton joukko

Yhteystiedot:  

Linkki väitöskirjan sähköiseen esittelykappaleeseen (esillä 7 päivää ennen väitöstä): .