Trianglar är de mest grundläggande icke-triviala subgrafer. Triangeln räknar används i ett antal olika applikationer, inklusive sociala nätverk gruvdrift, it-säkerhet, och spam upptäckt. I allmänhet är triangelräkningsalgoritmer lätt att parallellisera, men när de genomförs i distribuerat, delat minne, deras prestanda är dålig på grund av hög kommunikation, obalans i arbetet, och svårigheten att utnyttja lokalitet som finns i delat minne. I den här artikeln diskuterar vi fyra olika (men relaterade) triangelräkningsalgoritmer och hur deras prestanda kan förbättras i distribuerad, delad minne genom att minska in-node belastning obalans, förbättra cacheutnyttjande, minimera nätverket overhead, och minimera algoritmiskt arbete. Vi generaliserar de fyra olika triangelräkningsalgoritmer i ett gemensamt ramverk och visar att för alla fyra algoritmer in-node belastning obalans kan minimeras samtidigt som caches genom att partitionera arbete i block av hörn, kan nätverket overhead minimeras genom aggregering av block av arbete, och algoritm arbete kan minskas genom partitionering vertex grannar efter grad. Vi utvärderar experimentellt de svaga och den starka skalprestandan hos de föreslagna algoritmerna med två typer av syntetiska grafingångar och tre verkliga grafingångar. Vi jämför också prestandan av våra implementationer med de distribuerade, delade triangelräkningsalgoritmer som finns i PowerGraph-GraphLab och visar att våra föreslagna algoritmer överträffar dessa algoritmer, både när det gäller rum och tid.
Kanewala m.fl. REF beskriver en distribuerad algoritm med delat minne till triangelräkning.
Distributed, Shared-Memory Parallel Triangle Counting
{'venue': "PASC '18", 'journal': None, 'mag_field_of_study': ['Computer Science']}