abstract recursive array layouts and fast parallel matrix multiplication

《abstract recursive array layouts and fast parallel matrix multiplication》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、RecursiveArrayLayoutsandFastParallelMatrixMultiplicationSiddharthaChatterjeeyAlvinR.LebeckzPraveenK.PatnalayMithunaThottethodizAbstractnelinlinearalgebraicalgorithms,andisenshrinedinthedgemmroutineintheBLAS3library[10].Thereisanintimaterelation-Matrixmultiplicationisanimportantkernelin

2、linearalgebraal-shipbetweenthelayoutofthearraysinmemoryandtheperfor-gorithms,andtheperformanceofbothserialandparallelimple-manceoftheroutine.Onmodernshared-memorymultiprocessorsmentationsishighlydependentonthememorysystembehavior.withmulti-levelmemoryhierarchies,thecolumn-majorlayoutas-

3、Unfortunately,duetofalsesharingandcachecon¯icts,traditionalsumedintheBLAS3librarycanresultinperformanceanomaliescolumn-majororrow-majorarraylayoutsincurhighvariabilityinasthematrixsizeisvaried.Theseanomaliesresultfromunfavor-memorysystemperformanceasmatrixsizevaries.Thispaperin-ableacce

4、sspatternsinthememoryhierarchythatcauseinterfer-vestigatestheuseofrecursivearraylayoutsforimprovingtheper-encemissesandfalsesharingandincreasememorysystemover-formanceofparallelrecursivematrixmultiplicationalgorithms.headsexperiencedbythecode.Inthispaper,weinvestigaterecur-Weextendprevi

5、ousworkbyFrensandWiseonrecursivema-sivearraylayoutsaccompaniedbyrecursivecontrolstructuresasatrixmultiplicationtoexamineseveralrecursivearraylayoutsandmeansofdeliveringhighandrobustperformanceforparalleldensethreerecursivealgorithms:standardmatrixmultiplication,andthelinearalgebra.morec

6、omplexalgorithmsofStrassenandWinograd.WeshowTheuseofquad-oroct-trees(or,inadualinterpretation,space-thatwhilerecursivearraylayoutssigni®cantlyoutperformtradi-®llingcurves)isknowninparallelcomputing[1,20,21,33,35,38]tionallayouts(reducingexecutiontimesbyafactorof1.2±2.5)forforimprovingbo

7、thloadbalanceandlocality.Thecomputationsthestandardalgorithm,theyofferlittleimprovementforStrassen'sthusparallelizedorrestructuredarereasonablycoarse-grained,thusandWinograd'salgorithms;weprovideanalgorithmicexplanationmakingtheoverheadsofmaintainingandaccessingthedatastruc-oft