Abstract-Medan framgångsrika implementationer har redan skrivits för ensidiga transformationer (t.ex. QR, LU och Cholesky factorizations) på multicore arkitektur, få hög prestanda för tvåsidiga minskningar (t.ex., Hessenberg, tridiagonal och bidiagonal minskningar) är fortfarande ett öppet och svårt forskningsproblem på grund av dyra minnesbundna operationer som sker under panelen factorization. Klyftan i processorns hastighet fortsätter att vidgas, vilket har förvärrat problemet ytterligare. Detta dokument fokuserar på ett effektivt genomförande av tridiagonal reduktion, vilket är det första algoritmiska steget mot att beräkna den spektrala nedbrytningen av en tät symmetrisk matris. Den ursprungliga matrisen översätts till en kakellayout, dvs. en högpresterande datarepresentation, vilket avsevärt förbättrar datalokaliseringen. Efter en tvåstegsmetod omvandlas kakelmatrisen sedan till tridiagonal bandform med hjälp av beräkna intensiva kärnor. Bandet form reduceras ytterligare till den nödvändiga tridiagonal form med hjälp av en vänster-liknande bulge jakt teknik för att minska minnestrafik och minnes strid. Ett beroendeöversättningsskikt associerat med ett dynamiskt körtidssystem möjliggör schemaläggning och överlappande uppgifter som genereras från båda stadierna. Den erhållna kakel tridiagonal minskning betydligt överträffar state-of-theart numeriska bibliotek (10X mot multitrådade LAPACK med optimerad MKL BLAS och 2.5X mot den kommersiella numeriska programvaran Intel MKL) från medelstora till stora matrisstorlekar.
REF fann förbättrad prestanda med en vänstervänd variant.
Two-Stage Tridiagonal Reduction for Dense Symmetric Matrices Using Tile Algorithms on Multicore Architectures
{'venue': '2011 IEEE International Parallel & Distributed Processing Symposium', 'journal': '2011 IEEE International Parallel & Distributed Processing Symposium', 'mag_field_of_study': ['Computer Science']}