Usability Study of GraphBLAS Through MulticoreMax-Flow

Abstract

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.

Graphs are one of the most general and flexible abstractions for computer science problem. However, as data sets grow, the need for more computing power grows with it. This implies there is a need to adopt graph algorithms to parallel multi-core machines. Since these algorithm generally exhibit a high degree of irregularity, the parallel algorithms needed can be extremely hard to write from scratch. There is therefore a growing effort to develop high-level abstractions in the form of frameworks and libraries to address this challenge.

Optimizing linear algebra operations has been a research topic for decades. The compact language of mathematics also produce lean, maintainable code. Using linear algebra as a high-level abstraction for graph operations is therefore very attractive.

In this work, we will explore the usability of the GraphBLAS framework, currently the leading standard for graph operations that uses linear algebra as an abstraction. We analyze the usability of GraphBLAS by using it to implement the Edmonds-Karp algorithm for s-t maximum-flow/minimum-cut. To our knowledge, this work represents the first published results of Max-Flow in GraphBLAS. The result of our novel implementation was an algorithm that achieved a speedup of up to ~11 over its own baseline, and is surprisingly compact and easy to reason about.

We also provide thorough discussions and examples of various ease-of-use aspects of GraphBLAS, through the lens of our max-flow implementation. We found that GraphBLAS delivers an interesting and useful perspective on graph algorithms. We show how the use of linear algebra allowed us to re-use knowledge and observations both from that field and graphs. Our work shows that many operations are \textit{easier} to express in linear algebra than otherwise, some harder, and some impossible, illustrating the abstraction and framework have some clear limitations. Directions for future work are also included.