I detta dokument föreslås ett nytt algoritmiskt paradigm -k-nivå asynkron (KLA) - som överbryggar nivåsynkrona och asynkrona paradigm för bearbetning av grafer. KLA-paradigmet gör att asynkroninnivån i parallella grafalgoritmer kan varieras parametiskt från ingen (nivåsynkron) till full (asynkron). Motiveringen är att förbättra genomförandetiderna genom en lämplig avvägning mellan användning av färre, men dyrare globala synkroniseringar, som i nivåsynkrona algoritmer, och mer, men billigare lokala synkroniseringar (och kanske även redundant arbete), som i asynkrona algoritmer. Vi visar hur vanliga mönster i grafalgoritmer kan uttryckas i KLA pardigm och tillhandahåller tekniker för att bestämma k, antalet asynkrona steg tillåtna mellan globala synkroniseringar. Resultat av en implementering av KLA i stapl Graph Library visar utmärkt skalbarhet på upp till 96K kärnor och förbättringar av 10x eller mer över nivåsynkrona och asynkrona versioner för grafalgoritmer som bredd-första sökning, PageRank, k-core nedbrytning och andra på vissa klasser av verkliga grafer.
KLA grafbehandlingssystem har en traversal algoritm som växlar adaptivt mellan PBFS (nivåsynkron) och PDFS (asynkron) traversals för att accelerera vissa grafalgoritmer, såsom PageRank och k-core nedbrytning REF.
KLA: a new algorithmic paradigm for parallel graph computations
{'venue': "PACT '14", 'journal': None, 'mag_field_of_study': ['Computer Science']}