Skalbara parallella datorer är nödvändiga för att bearbeta storskaliga (power-law) grafer. Distributionen av data över processer blir viktig på distribuerade minnesdatorer med tusentals kärnor. Det har visat sig att tvådimensionella layouter (kantdelning) kan ha betydande fördelar jämfört med traditionella endimensionella layouter. Den enkla 2D-blockdistributionen använder dock inte grafens struktur, och mer avancerade 2D-partitioneringsmetoder är för dyra för stora grafer. Vi föreslår en ny tvådimensionell partitioneringsalgoritm som kombinerar grafpartitionering med 2D-blockfördelning. Den beräknade kostnaden för algoritmen är i huvudsak samma som 1D-grafpartitionering. Vi studerar prestandan hos sparse matris-vektorn multiplikation (SpMV) för skalfria grafer från webben och sociala nätverk med hjälp av flera olika partitionerare och både 1D och 2D datalayouter. Vi visar att SpMV körtiden minskas genom att utnyttja grafens struktur. Tvärtemot vad folk tror, observerar vi att nuvarande graf- och hypergrafpartitionerare ofta ger relativt bra partitioner på skalfria grafer. Vi visar att vår nya 2D-partitioneringsmetod konsekvent överträffar de andra metoder som beaktas, för både SpMV och en eigensolver, på matriser med upp till 1,6 miljarder nonzeros med upp till 16 384 kärnor.
Erik G. Boman m.fl. REF studerar ett specialfall och föreslår en grafpartitionalgoritm för skalbara matrisberäkningar på storskaliga grafer för att minska körtiden med 2D-grafpartitionering.
Scalable matrix computations on large scale-free graphs using 2D graph partitioning
{'venue': "SC '13", 'journal': None, 'mag_field_of_study': ['Computer Science']}