Matematiker øger domænedbrydningsmetoden til asynkron parallel computing

En matematiker fra RUDN-universitetet og hans kolleger fra Frankrig og Ungarn udviklede en algoritme til parallel computing, som gør det muligt at løse anvendte problemer, såsom i elektrodynamik eller hydrodynamik. Gevinsten i tid er op til 50 %. Resultaterne er offentliggjort i Journal of Computational and Applied Mathematics .

Parallelle beregningsmetoder bruges ofte til at behandle praktiske problemer i fysik, ingeniørarbejde, biologi, og andre felter. Det involverer flere processorer samlet i et net for samtidig at løse et enkelt problem - hver har sin egen lille del. Måden at fordele arbejdet mellem processorerne og få dem til at kommunikere med hinanden er et valg baseret på de særlige forhold ved et bestemt problem. En mulig metode er domænedbrydning. Studiedomænet er opdelt i separate dele - underdomæner - alt efter antallet af processorer. Når det tal er meget højt, især i heterogene high-performance computing (HPC) miljøer, asynkrone processer udgør en værdifuld ingrediens. Som regel, Schwarz metoder anvendes, hvor underdomænerne overlapper hinanden. Dette giver nøjagtige resultater, men fungerer ikke godt, når overlapning ikke er ligetil. Matematikeren og hans kolleger fra Frankrig og Ungarn foreslog en ny algoritme, der gør den asynkrone dekomponering lettere i mange strukturelle tilfælde – underdomænerne overlapper ikke hinanden; resultatet forbliver nøjagtigt med mindre tid, der kræves til beregning.

"Indtil nu, næsten alle undersøgelser af asynkrone iterationer inden for domænedbrydningsrammer målrettede metoder af den parallelle Schwarz-type. En første, og sål, forsøg på at håndtere primal ikke-overlappende nedbrydning resulterede i samtidig iteration på underdomænerne og på grænsefladen mellem dem. Det betyder, at beregningsskemaet er defineret på hele det globale domæne, "Guillaume Gbikpi-Benissan, Ingeniørakademi ved RUDN Universitet.

Matematikerne foreslog en algoritme baseret på Gauss-Seidel-metoden. Essensen af ​​innovationen er, at beregningsalgoritmen ikke køres samtidigt på hele domænet, men skiftevis på underdomænerne og grænserne mellem dem. Som resultat, værdierne opnået under hver iteration inden for subdomænet kan umiddelbart bruges til beregninger på grænsen uden ekstra omkostninger.

Matematikere testede den nye algoritme på Poisson-ligningen og det lineære elasticitetsproblem. Den første bruges, for eksempel, at beskrive det elektrostatiske felt, den anden bruges i hydrodynamik, at beskrive væskers bevægelse. Den nye metode var hurtigere end den oprindelige for begge ligninger. En gevinst på op til 50 % blev faktisk opnået – med 720 underdomæner, beregningen af ​​Poisson-ligningen tog 84 sekunder, mens den oprindelige algoritme brugte 170 sekunder. I øvrigt, antallet af synkrone alternerende iterationer falder med en stigning i antallet af underdomæner.

"Det er en ganske interessant adfærd, som kan forklares med det faktum, at forholdet mellem alternering stiger, efterhånden som subdomænernes størrelser reduceres, og der dukker flere grænseflader op. Dette arbejde tilskynder derfor til yderligere muligheder og lover nye undersøgelser af det asynkrone computerparadigme, " afslutter Gbikpi-Benissan.