Vi presenterar blockalgoritmer och deras genomförande för parallellisering av subkubisk Gaussisk eliminering på delade minnesarkitekturer. I motsats till de klassiska kubikalgoritmerna i parallell numerisk linjär algebra fokuserar vi här på rekursiva algoritmer och grov kornparallalisering. I själva verket, sub-kubisk matris aritmetik kan endast uppnås genom rekursiva algoritmer vilket gör grova korn block algoritmer prestera mer effektivt än finkorniga. Detta arbete motiveras av utformningen och genomförandet av tät linjär algebra över ett ändligt fält, där snabb matris multiplikation används i stor utsträckning och där kostsamma modulära minskningar också förespråkar grov korn block sönderdelning. Vi bygger stegvis effektiva kärnor, för matris multiplikation först, sedan triangulär systemlösning, ovanpå vilken en rekursiv PLUQ nedbrytningsalgoritm byggs. Vi studerar parallelliseringen av dessa kärnor med hjälp av flera algoritmiska varianter: antingen iterativ eller rekursiv och med olika delningsstrategier. Experiment visar att rekursiva adaptiva metoder för matrismultiplikation, hybridrekursiva-iterativa metoder för triangulära system löser och kakelrekursiva versioner av PLUQ-dekomposition, tillsammans med olika policyer för datakartering, ger bästa prestanda på en 32 kärnor NUMA arkitektur. Sammantaget visar vi att overhead av modulära minskningar mer än kompenseras av de snabba linjära algebra algoritmer och att exakt tät linjär algebra matchar prestandan hos full rank referens numerisk programvara även i närvaro av rank brister.
REF presenterar undersökningar om parallellisering av sub-kubisk Gaussian eliminering på delade minne multicore arkitekturer.
Recursion based parallelization of exact dense linear algebra routines for Gaussian elimination
{'venue': 'Parallel Comput.', 'journal': 'Parallel Comput.', 'mag_field_of_study': ['Computer Science']}