Efficient Primitives and Algorithms for Many-core architectures

《Efficient Primitives and Algorithms for Many-core architectures》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、EfficientPrimitivesandAlgorithmsforMany-corearchitecturesBySHUBHABRATASENGUPTAB.Sc.(IndianInstituteofTechnology,Kharagpur)1996M.Sc.(IndianInstituteofTechnology,Kharagpur)1998M.S(UniversityofCalifornia,Davis)2007DISSERTATIONSubmittedinpartialsatisfactionofthereq

2、uirementsforthedegreeofDOCTOROFPHILOSOPHYinComputerScienceintheOFFICEOFGRADUATESTUDIESoftheUNIVERSITYOFCALIFORNIADAVISApproved:JohnOwens,ChairBerndHamannKenJoyCommitteeinCharge2010-i-Copyrightc2010byShubhabrataSenguptaAllrightsreserved.Tomygrandparents...-ii-C

3、ONTENTSListofFigures......................................viListofTables......................................viiiAbstract.........................................ixAcknowledgments....................................x1Introduction11.1Thepresentandthefutureofpa

4、rallelism.....................21.2Whychoosemany-coreprocessorsasacomputingdevice............31.3TheevolutionoftheGPU.............................51.4Theevolutionofprogrammingmodels......................91.5AlgorithmicchallengesforGPUs.........................1

5、12Thescanprimitives142.1Introduction....................................142.2Scan:analgorithmicprimitiveforefficientdata-parallelcomputation......162.2.1Scan....................................162.2.2Segmentedscan..............................172.3Designofaneffi

6、cientscanalgorithm.......................192.3.1Hierarchyofthescanalgorithm.....................192.3.2Intra-warpscanalgorithm........................202.3.3Intra-blockscanalgorithm........................212.3.4Globalscanalgorithm..........................222

7、.4Designofanefficientsegmentedscanalgorithm.................232.4.1Operatortransformation.........................232.4.2Directintra-warpsegmentedscan....................242.4.3Blockandglobalsegmentedscanalgorithms..............282.5Algorithmiccomplexity.......

8、.......................292.6Somealternatedesignsforscanalgorithms....................312.6.1Savingbandwidthbyperformingareduction..............312.6.2Eliminatingrecursionbyperformi