Usability Study of GraphBLAS Through MulticoreMax-Flow

Grafer er blant de mest generelle og fleksible abstraksjonene i datavitenskap. Men, etter hvert som størrelsen på datasett vokser trenger vi stadig mer datakraft for å behandle dem, som betyr at vi må ta ibruk grafalgoritmer som kan dra nytte av paralle flerkjernemaskiner. Dette kan være en stor utfordring, da grafalgoritmer ofte har stor grad av irregularitet, som gjør det vanskelig å konstruere slike algoritmer fra bunnen av. Det har derfor blitt utvilket mange bibliotek og rammeverk for å gjøre denne prossessen enklere. I flere tiår har forskere optimalisert operasjoner for lineær algebra. På grunn av det ekspressive og komptakte språket fra matematikk, kan programmer skrevet som en serie av linear algebra-operasjoner gi kode som er lettere å lese og vedlikeholde. Lineær algebra er derfor en veldig attraktiv abstraksjon å ta ibruk for utrykke grafoperasjoner. I dette arbeidet skal vi utforske brukbarheten til rammeverket GraphBLAS, den ledende standarden for grafopereasjoner utrykt som lineær algebra. Vi analyserer brukbarheten til GraphBLAS ved å implementere Edmonds-Karps algoritme for s-t maksimal flyt/minimalt kutt. Så vidt oss bekjent er dette arbeidet det første publiserte resultatet av maks-flyt implementert i GraphBLAS. Vår implementasjon ga et program som oppnådde opptil ~11 økt hastighet over egen grunnlinje. Vi inkluderer også en grundig diskusjon med eksempler for å presentere ulike brukervennlighetsaspekter ved GraphBLAS, med utgangspunkt i vår egen maks-flyt-implementasjon. Våre funn indikerer at GraphBLAS gir en interessant og nyttig måte å se på grafalgoritmer, og vi observerte at å bruke lineær algebra som astraksjon gjorde at vi kunne ta ibruk kunnskap og verktøy både fra dette feltet og grafteori. Vi viser at mange operasjoner på grafer faktisk er enklere å utrykke i lineær algebra, men også at noen er vanskelige og andre igjen umulige. Dette illustrerer at abstraksjonen og rammeverket har noen klare begrensninger. Vi beskriver også mulige retninger for fremtidig arbeid