Abstrakt. Detta papper tar upp problemet med endimensionell uppdelning av strukturellt osymmetrisk kvadrat och rektangulära glesa matriser för parallella matris-vektor och matris-transposevector multiplier. Målet är att minimera kommunikationskostnaderna samtidigt som balansen på beräkningsbelastningen för processorer bibehålls. De flesta av de befintliga partitionering modellerna endast överväga den totala meddelandevolymen i hopp om att minimera denna kommunikation kostnad metrisk är sannolikt att minska andra mått. Den totala meddelandelatensen (starttid) kan dock vara viktigare än den totala meddelandevolymen. Dessutom är den maximala meddelandevolym och latens som hanteras av en enda processor också viktiga mått. Vi föreslår en strategi i två faser som omfattar alla dessa fyra mått på kommunikationskostnader. Målet i den första fasen är att minimera den totala meddelandevolymen samtidigt som beräkningsbelastningsbalansen bibehålls. Målet i den andra fasen är att inkapsla de återstående tre måtten på kommunikationskostnader. Vi föreslår kommunikationshypergraf- och partitioneringsmodeller för den andra fasen. Vi presenterar sedan flera metoder för att partitionera kommunikationshypergrafer. Experiment på ett brett spektrum av testmatriser visar att det föreslagna tillvägagångssättet ger mycket effektiva partitioneringsresultat. En parallell implementering på en PC-kluster verifierar att de teoretiska förbättringar som visas genom partitionering resultat håller i praktiken. Nyckelord. matrisfördelning, strukturellt osymmetrisk matris, rektangulär matris, iterativ metod, matris-vektorn multiplicera, parallell beräkning, meddelandevolym, meddelande latens, kommunikations hypergraph, hypergraph partitionering AMS ämnesklassificeringar. 05C50, 05C65, 65F10, 65F50, 65Y05 DOI. 10.1137/S1064827502410463 1. Inledning. Upprepade matris-vektorn och matris-transpose-vektorn multiplies som involverar samma stora, glesa, strukturellt osymmetrisk kvadrat eller rektangulär matris är kärnan operationer i olika iterativa algoritmer. Till exempel, iterativa metoder såsom konjugatgradient normala ekvationsfel och restmetoder (CGNE och CGNR) [15, 34] och standard kvasiminimala restmetoden (QMR) [14], som används för att lösa osymmetriska linjära system, kräver beräkningar av formen y = Ax och w = A T z i varje iteration, där A är en osymmetrisk kvadratkoefficient matris. De minst kvadrater (LSQR) metod [31], som används för att lösa de minst kvadrater problem, och Lanczos metod [15], som används för att beräkna singular värde nedbrytning, kräver frekventa beräkningar av formen y = Ax och w = A T z, där A är en rektangulär matris. Iterativa metoder som används för att lösa de normala ekvationer som uppstår i inre punktmetoder för linjär programmering kräver upprepade beräkningar av formen y = AD 2 A T z, där A är en rektangulär begränsningsmatris och D är en diagonal matris. Snarare än att bilda koefficientmatris AD 2 A T, som kan vara ganska tät, ovanstående beräkning utförs som w = A T z, x = D 2 w, och y = Ax. Surrogatrestriktionsmetoden [29, 30, 39, 40], som används för att lösa det linjära genomförbarhetsproblemet, kräver frikopplade matris-vektor och matris-transpose-vektor multiplier som omfattar samma rektangulära matris.
Uçar och Aykanat REF diskuterar hur man kan minska det totala antalet meddelanden och uppnå balans på den maximala volymen meddelanden som skickas av en processor som ett hypergraf partitioneringsproblem i den andra fasen.
Encapsulating multiple communication-cost metrics in partitioning sparse rectangular matrices for parallel matrix-vector multiplies
{'venue': 'SIAM Journal on Scientific Computing', 'journal': None, 'mag_field_of_study': ['Computer Science']}