ELS Dunn 03-loc-xi-xviii-9780123849885 — 2011/1/8 — 11:12 — page xviii — #8 ELS Dunn 01-fm-i-iv-9780123849885 — 2011/1/8 — 12:46 — page i — #1 GPU Computing Gems Emerald Edition ELS Dunn 01-fm-i-iv-9780123849885 — 2011/1/8 — 12:46 — page ii — #2 Morgan Kaufmann’s Applications of GPU Computing Series Computing is quickly becoming the third pillar of scientific research, due in large part to the perfor- mance gains achieved through graphics processing units (GPUs), which have become ubiquitous in handhelds, laptops, desktops, and supercomputer clusters. Morgan Kaufmann’sApplications of GPU Computing series offers training, examples, and inspiration for researchers, engineers, students, and supercomputingprofessionalswhowanttoleveragethepowerofGPUsincorporatedintotheirsimu- lations or experiments. Each high-quality, peer-reviewed book is written by leading experts uniquely qualifiedtoprovideparallelcomputinginsightsandguidance. Each GPU Computing Gems volume offers a snapshot of the state of parallel computing across a carefullyselectedsubsetofindustrydomains,givingyouawindowintothelead-edgeresearchoccur- ring across the breadth of science, and the opportunity to observe others’ algorithm work that might applytoyourownprojects.Findoutmoreathttp://mkp.com/gpu-computing-gems. RecommendedParallelComputingTitles ProgrammingMassivelyParallelProcessors AHands-onApproach ByDavidB.KirkandWen-meiW.Hwu ISBN:9780123814722 GPUComputingGems:JadeEdition Editor-in-Chief:Wen-meiW.Hwu ISBN:9780123859631 ComingSummer2011 TheArtofMultiprocessorProgramming ByMauriceHerlihyandNirShavit ISBN:9780123705914 ELS Dunn 01-fm-i-iv-9780123849885 — 2011/1/8 — 12:46 — page iii — #3 GPU Computing Gems Emerald Edition Wen-mei W. Hwu AMSTERDAM•BOSTON•HEIDELBERG•LONDON NEWYORK•OXFORD•PARIS•SANDIEGO SANFRANCISCO•SINGAPORE•SYDNEY•TOKYO MorganKaufmannPublishersisanimprintofElsevier ELS Dunn 01-fm-i-iv-9780123849885 — 2011/1/8 — 12:46 — page iv — #4 AcquiringEditor:ToddGreen AssistantEditor:RobynDay ProjectManager:PaulGottehrer Designer:DennisSchaefer MorganKaufmannisanimprintofElsevier 30CorporateDrive,Suite400,Burlington,MA01803,USA (cid:13)c 2011NVIDIACorporationandWen-meiW.Hwu.PublishedbyElsevierInc.Allrightsreserved. Nopartofthispublicationmaybereproducedortransmittedinanyformorbyanymeans,electronicor mechanical,includingphotocopying,recording,oranyinformationstorageandretrievalsystem,without permissioninwritingfromthepublisher.Detailsonhowtoseekpermission,furtherinformationaboutthe Publisher’spermissionspoliciesandourarrangementswithorganizationssuchastheCopyrightClearanceCenter andtheCopyrightLicensingAgency,canbefoundatourwebsite:www.elsevier.com/permissions. ThisbookandtheindividualcontributionscontainedinitareprotectedundercopyrightbythePublisher(other thanasmaybenotedherein). Notices Knowledgeandbestpracticeinthisfieldareconstantlychanging.Asnewresearchandexperiencebroadenour understanding,changesinresearchmethodsorprofessionalpractices,maybecomenecessary.Practitionersand researchersmustalwaysrelyontheirownexperienceandknowledgeinevaluatingandusinganyinformationor methodsdescribedherein.Inusingsuchinformationormethodstheyshouldbemindfuloftheirownsafetyand thesafetyofothers,includingpartiesforwhomtheyhaveaprofessionalresponsibility. Tothefullestextentofthelaw,neitherthePublishernortheauthors,contributors,oreditors,assumeanyliability foranyinjuryand/ordamagetopersonsorpropertyasamatterofproductsliability,negligenceorotherwise,or fromanyuseoroperationofanymethods,products,instructions,orideascontainedinthematerialherein. LibraryofCongressCataloging-in-PublicationData GPUcomputinggems/editor,Wen-meiW.Hwu. p.cm. Includesbibliographicalreferences. ISBN978-0-12-384988-5 1.Graphicsprocessingunits–Programming.2.Imagingsystems.3.Computergraphics.4.Image processing–Digitaltechniques.I.Hwu,Wen-mei. T385.G68752011 006.6–dc22 2010047487 BritishLibraryCataloguing-in-PublicationData AcataloguerecordforthisbookisavailablefromtheBritishLibrary. ForinformationonallMKpublicationsvisitourwebsiteat www.mkp.com PrintedintheUnitedStatesofAmerica 11 12 13 14 15 11 10 9 8 7 6 5 4 3 2 1 ELS Dunn 02-toc-v-x-9780123849885 — 2011/1/8 — 16:49 — page v — #1 Contents Editors,Reviewers,andAuthors ....................................................................... xi Introduction.............................................................................................. xix Wen-meiW.Hwu SECTION 1 SCIENTIFIC SIMULATION RobertM.Farber CHAPTER 1 GPU-AcceleratedComputationandInteractiveDisplayofMolecular Orbitals.......................................................................... 5 JohnE.Stone,DavidJ.Hardy,JanSaam,KirbyL.Vandivort,KlausSchulten CHAPTER 2 Large-ScaleChemicalInformaticsonGPUs..................................... 19 ImranS.Haque,VijayS.Pande CHAPTER 3 DynamicalQuadratureGrids:ApplicationsinDensityFunctional Calculations..................................................................... 35 NathanLuehr,IvanUfimtsev,ToddMartinez CHAPTER 4 FastMolecularElectrostaticsAlgorithmsonGPUs.............................. 43 DavidJ.Hardy,JohnE.Stone,KirbyL.Vandivort,DavidGohara,ChristopherRodrigues, KlausSchulten CHAPTER 5 QuantumChemistry:PropagationofElectronicStructureonaGPU............. 59 JacekJakowski,StephanIrle,KeijiMorokuma CHAPTER 6 AnEfficientCUDAImplementationoftheTree-BasedBarnesHutn-Body Algorithm........................................................................ 75 MartinBurtscher,KeshavPingali CHAPTER 7 LeveragingtheUntappedComputationPowerofGPUs:FastSpectral SynthesisUsingTextureInterpolation........................................... 93 RichardTownsend,KarthikeyanSankaralingam,MatthewD.Sinclair CHAPTER 8 BlackHoleSimulationswithCUDA.............................................. 103 FrankHerrmann,JohnSilberholz,ManuelTiglio CHAPTER 9 TreecodeandFastMultipoleMethodforN-BodySimulationwithCUDA........ 113 RioYokota,LorenaA.Barba v ELS Dunn 02-toc-v-x-9780123849885 — 2011/1/8 — 16:49 — page vi — #2 vi Contents CHAPTER 10 Wavelet-BasedDensityFunctionalTheoryCalculationonMassively ParallelHybridArchitectures ................................................... 133 LuigiGenovese,MatthieuOspici,BriceVideau,ThierryDeutsch,Jean-Franc¸oisMe´haut SECTION 2 LIFE SCIENCES BertilSchmidt CHAPTER 11 AccurateScanningofSequenceDatabaseswiththeSmith-Waterman Algorithm........................................................................ 155 ŁukaszLigowski,WitoldR.Rudnicki,YongchaoLiu,BertilSchmidt CHAPTER 12 MassiveParallelComputingtoAccelerateGenome-Matching.................. 173 BenWeiss,MikeBailey CHAPTER 13 GPU-SupercomputerAccelerationofPatternMatching......................... 185 AliKhajeh-Saeed,J.BlairPerot CHAPTER 14 GPUAcceleratedRNAFoldingAlgorithm........................................ 199 GuillaumeRizk,DominiqueLavenier,SanjayRajopadhye CHAPTER 15 TemporalDataMiningforNeuroscience........................................ 211 Wu-chunFeng,YongCao,DebprakashPatnaik,NarenRamakrishnan SECTION 3 STATISTICAL MODELING MikeGiles CHAPTER 16 ParallelizationTechniquesforRandomNumberGenerators .................... 231 ThomasBradley,JacquesduToit,RobertTong,MikeGiles,PaulWoodhams CHAPTER 17 MonteCarloPhotonTransportontheGPU ...................................... 247 La´szlo´ Szirmay-Kalos,Bala´zsTo´th,Mila´nMagdics CHAPTER 18 High-PerformanceIteratedFunctionSystems................................... 263 ChristophSchied,JohannesHanika,HolgerDammertz,HendrikP.A.Lensch SECTION 4 EMERGING DATA-INTENSIVE APPLICATIONS VolodymyrKindratenko CHAPTER 19 Large-ScaleMachineLearning.................................................. 277 JerodJ.Weinman,AugustusLidaka,ShitanshuAggarwal ELS Dunn 02-toc-v-x-9780123849885 — 2011/1/8 — 16:49 — page vii — #3 Contents vii CHAPTER 20 MulticlassSupportVectorMachine............................................. 293 SergioHerrero-Lopez CHAPTER 21 Template-DrivenAgent-BasedModelingandSimulationwithCUDA............ 313 PaulRichmond,DanielaRomano CHAPTER 22 GPU-AcceleratedAntColonyOptimization ...................................... 325 RobinM.Weiss SECTION 5 ELECTRONIC DESIGN AUTOMATION SunilP.Khatri CHAPTER 23 High-PerformanceGate-LevelSimulationwithGP-GPUs........................ 343 DebapriyaChatterjee,AndrewDeOrio,ValeriaBertacco CHAPTER 24 GPU-BasedParallelComputingforFastCircuitOptimization ................... 365 YifangLiu,JiangHu SECTION 6 RAY TRACING AND RENDERING AustinRobison CHAPTER 25 LatticeBoltzmannLightingModels.............................................. 381 RobertGeist,JamesWestall CHAPTER 26 PathRegenerationforRandomWalks........................................... 401 JanNova´k,VlastimilHavran,CarstenDachsbacher CHAPTER 27 FromSparseMocaptoHighlyDetailedFacialAnimation....................... 413 BerndBickel,ManuelLang CHAPTER 28 AProgrammableGraphicsPipelineinCUDAforOrder-Independent Transparency.................................................................... 427 MengchengHuang,FangLiu,XuehuiLiu,EnhuaWu SECTION 7 COMPUTER VISION JamesFung CHAPTER 29 FastGraphCutsforComputerVision............................................ 439 P.J.Narayanan,VibhavVineet,TimoStich CHAPTER 30 VisualSaliencyModelonMulti-GPU............................................ 451 AnisRahman,DominiqueHouzet,DenisPellerin ELS Dunn 02-toc-v-x-9780123849885 — 2011/1/8 — 16:49 — page viii — #4 viii Contents CHAPTER 31 Real-TimeStereoonGPGPUUsingProgressiveMultiresolutionAdaptive Windows ........................................................................ 473 YongZhao,GabrielTaubin CHAPTER 32 Real-TimeSpeed-Limit-SignRecognitiononanEmbeddedSystem UsingaGPU..................................................................... 497 PinarMuyan-O¨zc¸elik,VladimirGlavtchev,JeffreyM.Ota,JohnD.Owens CHAPTER 33 HaarClassifiersforObjectDetectionwithCUDA................................ 517 AntonObukhov SECTION 8 VIDEO AND IMAGE PROCESSING TimoStich CHAPTER 34 ExperiencesonImageandVideoProcessingwithCUDAandOpenCL .......... 547 AlptekinTemizel,TugbaHalici,BerkerLogoglu,TugbaTaskayaTemizel, FatihOmruuzun,ErsinKaraman CHAPTER 35 ConnectedComponentLabelinginCUDA ....................................... 569 OndrˇejSˇt´ava,BedrˇichBenesˇ CHAPTER 36 ImageDe-Mosaicing ............................................................ 583 JoeStam,JamesFung SECTION 9 SIGNAL AND AUDIO PROCESSING JohnRoberts CHAPTER 37 EfficientAutomaticSpeechRecognitionontheGPU............................ 601 JikeChong,EkaterinaGonina,KurtKeutzer CHAPTER 38 ParallelLDPCDecoding......................................................... 619 GabrielFalcao,VitorSilva,LeonelSousa CHAPTER 39 Large-ScaleFastFourierTransform............................................. 629 YifengChen,XiangCui,HongMei SECTION 10 MEDICAL IMAGING LawrenceTarbox CHAPTER 40 GPUAccelerationofIterativeDigitalBreastTomosynthesis .................... 647 DanaSchaa,BenjaminBrown,ByunghyunJang,PerhaadMistry,RodrigoDominguez, DavidKaeli,RichardMoore,DanielB.Kopans ELS Dunn 02-toc-v-x-9780123849885 — 2011/1/8 — 16:49 — page ix — #5 Contents ix CHAPTER 41 ParallelizationofKatsevichCTImageReconstructionAlgorithm onGenericMulti-CoreProcessorsandGPGPU.................................. 659 AbderrahimBenquassmi,EricFontaine,Hsien-HsinS.Lee CHAPTER 42 3-DTomographicImageReconstructionfromRandomlyOrderedLines withCUDA....................................................................... 679 GuillemPratx,Jing-YuCui,SvenPrevrhal,CraigS.Levin CHAPTER 43 UsingGPUstoLearnEffectiveParameterSettingsforGPU-Accelerated IterativeCTReconstructionAlgorithms ......................................... 693 WeiXu,KlausMueller CHAPTER 44 UsingGPUstoAccelerateAdvancedMRIReconstructionwithField InhomogeneityCompensation................................................... 709 YueZhuo,Xiao-LongWu,JustinP.Haldar,ThibaultMarin,Wen-meiW.Hwu, Zhi-PeiLiang,BradleyP.Sutton CHAPTER 45 (cid:96)1Minimizationin(cid:96)1-SPIRiTCompressedSensingMRIReconstruction....... 723 MarkMurphy,MikiLustig CHAPTER 46 MedicalImageProcessingUsingGPU-AcceleratedITKImageFilters.......... 737 Won-KiJeong,HanspeterPfister,MassimilianoFatica CHAPTER 47 DeformableVolumetricRegistrationUsingB-Splines........................... 751 JamesShackelford,NagarajanKandasamy,GregorySharp CHAPTER 48 MultiscaleUnbiasedDiffeomorphicAtlasConstructiononMulti-GPUs......... 771 LinhHa,JensKru¨ger,SarangJoshi,Cla´udioT.Silva CHAPTER 49 GPU-AcceleratedBrainConnectivityReconstructionand VisualizationinLarge-ScaleElectronMicrographs............................. 793 Won-KiJeong,HanspeterPfister,JohannaBeyer,MarkusHadwiger CHAPTER 50 FastSimulationofRadiographicImagesUsingaMonteCarloX-Ray TransportAlgorithmImplementedinCUDA...................................... 813 AndreuBadal,AldoBadano Index.............................................................................................. 831