Vi undersöker hur grafpartitionering negativt påverkar grafanalysernas prestanda. Vi visar att grafpartitionering framkallar extra arbete under graf traversal och att grafpartitioner har markant annorlunda konnektivitet än den ursprungliga grafen. Följaktligen ökar antalet partitioner når en topp efter vilken overheads snabbt dominerar prestandavinster. Dessutom visar vi att heuristiska för att balansera CPU belastning mellan grafpartitioner genom att balansera antalet kanter är olämpligt för en rad grafanalyser. Men även när det är lämpligt är det inte optimalt på grund av de sociala nätverkens snedvridna gradfördelning. Baserat på dessa observationer föreslår vi GraphGrind, ett nytt grafanalyssystem som tar upp de begränsningar som uppstår vid grafpartitionering. Vi föreslår dessutom en NUMA-medveten utökning till Cilk programmeringsspråket och få en skala-fri men ändå NUMA-medveten parallellprogrammeringsmiljö som stöder NUMA-medveten schemaläggning i GraphGrind. Vi visar att GraphGrind överträffar toppmoderna grafanalyssystem för delat minne inklusive Ligra, Polymer och Galois.
GraphGrind Ref analyserar effekten av grafpartitionering på grafens bearbetningsprestanda, och finner att grafpartitionering orsakar extra graf traversal kostnad och belastningsobalans.
GraphGrind: addressing load imbalance of graph partitioning
{'venue': "ICS '17", 'journal': None, 'mag_field_of_study': ['Computer Science']}