Detta papper analyserar prestanda och skalbarhet av en iteration av den förkonditionerade Conjugate Gradient Algoritm på parallella arkitekturer med en mängd olika sammankopplingsnät, såsom mesh, hyperkub, och CM-5 T M † parallelldator. Det visas att för block-tridiagonala matriser som härrör från tvådimensionella finita differens rutnät dominerar kommunikationen overhead på grund av vektor inre produkter kommunikations omkostnaderna för resten av beräkningen på ett stort antal processorer. Men med en lämplig kartläggning, den parallella formuleringen av en PCG iteration är mycket skalbar för sådana matriser på en maskin som CM-5 vars snabba kontrollnätverk praktiskt taget eliminerar overheads på grund av inre produktberäkning. Användningen av den trunkerade Ofullständiga Cholesky (IC) förkonditioneringen kan leda till ytterligare förbättring av skalbarheten på CM-5 med en konstant faktor. Som ett resultat, en parallell formulering av PCG-algoritm med IC förkonditionering kan köras snabbare än det med en enkel diagonal förkonditionering även om den senare körs snabbare i en seriell implementation. För matriser som är resultatet av tredimensionella ändliga differens rutnät, är skalbarheten ganska bra på en hyperkub eller CM-5, men inte lika bra på en 2-D mesh arkitektur. Vid slumpmässiga ostrukturerade glesa matriser med ett konstant antal icke-noll element i varje rad, är den parallella formuleringen av PCG iteration oskalbar på något meddelande passerar parallell arkitektur, om inte vissa beställning tillämpas på glesa matrisen. Det parallella systemet kan göras skalbart antingen om icke-nollelementen i N × N-matrisen kan begränsas i ett band vars bredd är O(N y ) för alla y < 1, eller om antalet icke-nollelement per rad ökar som N x för alla x > 0. Skalbarheten ökar när antalet icke-nollelement per rad ökas och/eller bredden på bandet som innehåller dessa element minskas. För ostrukturerade glesa matriser är skalbarheten asymptotiskt densamma för alla arkitekturer. Många av dessa analysresultat verifieras experimentellt på CM-5 parallelldatorn.
En grundlig prestanda- och skalbarhetsanalys av parallell CG ges i REF på en mängd parallella arkitekturer.
Performance and Scalability of Preconditioned Conjugate Gradient Methods on Parallel Computers
{'venue': 'Department of Computer Science, University of Minnesota', 'journal': None, 'mag_field_of_study': ['Computer Science']}