Performance Analysis. Future Direction.

PerformanceStudyofaWholeGenomeComparisonToolonaHyper-ThreadingMultiprocessorJuandelCuvillo1,XinminTian2,GuangR.Gao1andMilindGirkar2(1)DepartmentofElectricalandComputerEngineering,UniversityofDelaware,DE19716Newark,USA(2)IntelCompilerLaboratory,SSG/EPG,IntelCorporation,3600JulietteLane,CA95052SantaClara,USAPresentedBy:RatnaSinghDepartmentofComputerScience,NCSUAgenda•UnderstandingGenomics.•BioinformaticsKeyApplications.•MotivationforATGC.•ATGC(AnotherToolforGenomeComparison).•ParallelComputationofSequenceAlignment.•PerformanceAnalysis.•FutureDirection.GeneticsGlossary•Genomics-studyofgenesandtheirfunction.•Genomicsequence/DNA(deoxyribonucleicacid)-moleculethatencodesgeneticinformation.-DNAisadouble-strandedmoleculeheldtogetherbyweakbondsbetweenbasepairsofnucleotides.-fournucleotidesinDNAcontainthebasesadenine(A),guanine(G),cytosine(C),andthymine(T).•Geneexpression-processbywhichagene'scodedinformationisconvertedintothestructurespresentandoperatinginthecell.•Bioinformatics-scienceofmanaging&analyzinggenomicresearchdatausingadvancedcomputingtechniques.BioinformaticsKeyApplications•databasesearch–Exponentialgrowthofbiologicalsequencedata.•multiplesequencecomparison–Twoconstraints:executiontime&memorybandwidth.MotivationforATGC•Needfor–fastersequencecomparisonalgorithms.–toolsforcomparativegenomics.•Parallelizationofsequencealignmentalgorithms.–reliableoutputandreasonablecost.ATGCAnotherToolforGenomeComparison•genomecomparison•sequenceanalysis•parallelcomputation•multithreadingSmith-WatermanAlgorithm•Insteadoflookingateachsequenceinitsentiretythiscomparessegmentsofallpossiblelengths(LOCALalignments)andchooseswhichevermaximizethesimilaritymeasure.•ForeverycellthealgorithmcalculatesALLpossiblepathsleadingtoit.Thesepathscanbeofanylengthandcancontaininsertionsanddeletions.Smith-WatermanAlgorithmParallelComputationofSequenceAlignment•ParallelizationofSmith-WatermanAlgorithmdecreasesexecutiontimealmostlinearly.•Parallelizationisachievedby–OpenMPpragmas.–rotatingbuffersforthreadcommunication.–Hyperthreadingmultiprocessors.•Benefits–Locks/criticalsectionsnotneeded.–Minimuminterthreadcommunication.Hyper-ThreadingTechnology(a)Hyper-threadingnon-capableprocessors(b)Hyper-threading-enabledprocessorsTraditionalandHT-capablemultiprocessorsystemsComputationofthesimilaritymatrixonaSMPsystemAbsolutespeedupformitochondrialgenomecomparisonsTable1.Workloadcharacteristicsforthehumanvs.mouseandhumanvs.Drosophilagenomecomparisonswithblockwidth1,000Conclusions•Meetstherequirementsforsmallandmediumsizegenomes.•Intelcompileryieldstoa3.3absolutespeeduponaquadprocessormachine.•high1stlevelcachemissrateof7-8%.•LogicalprocessorswithHTtechnologyenabledcannotachievefurtherimprovement.–high1stlevelcachemissrateof7-8%.–lackofmemorybandwidth.FutureWorkInvestigate•whyhyper-threadingdoesnotbringadditionalperformancegain.•overheadcausedby–loopwiththePAUSEinstruction,whichaccountsfor5%oftheexecutiontime.–fourload-storeoperationsthataccountformorethan90%oftheL2cachemisses.References•A.N.Arslanetal.Anewapproachtosequencecomparison:Normalizedsequencealignment.Bioinformatics,17(4):327–337,2001.•J.delCuvillo.Wholegenomecomparisonusingamultithreadedparallelimplementation.Master’sthesis,U.ofDelaware,Newark,Del.,Jul.2001.•A.L.Delcheretal.Alignmentofwholegenomes.NucleicAcidsRes.,27(11):2369–2376,1999.•D.T.Maretal.Hyper-threadingtechnologyarchitectureandmicroarchitecture.IntelTech.J.,6(1):4–15,Feb.2002.•W.S.Martinsetal.Wholegenomealignmentusingamultithreadedparallelimplementation.InProc.ofthe13thSymp.onComputerArchitectureandHighPerformanceComputing,Piren´opolis,Brazil,Sep.10–12,2001.•W.S.Martinsetal.Amultithreadedparallelimplementationofadynamicprogrammingalgorithmforsequencecomparison.InProc.ofthePaci.cSymp.OnBiocomputing,pages311–322,MaunaLani,Haw.,Jan.3–7,2001.•D.M.Tullsenetal.Simultaneousmultithreading:Maximizingon-chipparallelism.InProc.ofthe22ndAnn.Intl.Symp.onComputerArchitecture,pages392–403,SantaMargheritaLigure,Italy,Jun.1995.•M.S.Waterman.IntroductiontoComputationalBiology:Maps,Sequences,andGenomes.ChapmanandHall,1995.