ABSTRACT Title of dissertation HILL-CLIMBING SMT P

ABSTRACTTitleofdissertation:HILL-CLIMBINGSMTPROCESSORRESOURCEDISTRIBUTIONSeungryulChoi,DoctorofPhilosophy,2006Dissertationdirectedby:ProfessorDonaldYeungDepartmentofElectricalandComputerEngineeringThekeytohighperformanceinSMTprocessorsliesinoptimizingthesharedre-sourcesdistributionamongsimultaneouslyexecutingthreads.Existingresourcedistribu-tiontechniquesoptimizeperformanceonlyindirectly.Theyinferpotentialperformancebottlenecksbyobservingindicators,likeinstructionoccupancyorcachemisscount,andtakeactionstotrytoalleviatethem.Whilethecorrectiveactionsaredesignedtoimproveperformance,theiractualperformanceimpactisnotknownsinceendperformanceisnevermonitored.Consequently,opportunitiesforperformancegainsarelostwheneverthecor-rectiveactionsdonoteffectivelyaddresstheactualperformancebottlenecksoccurringintheSMTprocessorpipeline.Inthisdissertation,weproposeadifferentapproachtoSMTprocessorresourcedistributionthatoptimizesendperformancedirectly.Ourapproachobservestheimpactthatresourcedistributiondecisionshaveonperformanceatruntime,andfeedsthisin-formationbacktotheresourcedistributionmechanismstoimprovefuturedecisions.Bysuccessivelyapplyingandevaluatingdifferentresourcedistributions,ourapproachtriestolearnthebestdistributionovertime.Becauseweperformlearningon-line,learningtimeiscrucial.Wedevelopahill-climbingSMTprocessorresourcedistributiontechniquethatefficientlylearnsthebestresourcedistributionbyfollowingtheperformancegradientwithintheresourcedistributionspace.Thisdissertationmakesthreecontributionswithinthecontextoflearning-basedSMTprocessorresourcedistribution.First,wecharacterizeandquantifythetime-varyingperformancebehaviorofSMTprocessors.Thisanalysisprovidesunderstandingofthebehaviorandguidesthedesignofourhill-climbingalgorithm.Second,wepresentahill-climbingSMTprocessorresourcedistributiontechniquethatperformslearningon-line.Theperformanceevaluationofourapproachshowsa11.4%gainoverICOUNT,11.5%gainoverFLUSH,and2.8%gainoverDCRAacrossalargesetof63multiprogrammedwork-loads.Third,wecompareexistingresourcedistributiontechniquestoanideallearning-basedtechniquethatperformslearningoff-linetoshowthepotentialperformanceoftheexistingtechniques.Thislimitstudyidentifiestheperformancebottleneckoftheexist-ingtechniques,showingthattheperformanceofICOUNT,FLUSH,andDCRAis13.2%,13.5%,and6.6%,respectively,lowerthantheidealperformance.Ourhill-climbingbasedresourcedistribution,however,handlesmostofthebottlenecksoftheexistingtechniquesproperly,achieving4.1%lowerperformancethantheidealcase.HILL-CLIMBINGSMTPROCESSORRESOURCEDISTRIBUTIONbySeungryulChoiDissertationsubmittedtotheFacultyoftheGraduateSchooloftheUniversityofMaryland,CollegeParkinpartialfulfillmentoftherequirementsforthedegreeofDoctorofPhilosophy2006AdvisoryCommittee:ProfessorDonaldYeung,Chair/AdvisorProfessorChau-WenTsengProfessorAlanSussmanProfessorManojFranklinProfessorSungLeecCopyrightbySeungryulChoi2006ACKNOWLEDGMENTSItismyhonortoknowsomanygoodpeoplewhomademyPh.D.studyattheUniversityofMarylandenjoyable.Firstofall,Ireallythankmyadvisor,Dr.DonaldYeung.Henotonlyadvisedmyresearchbutalsowasarolemodelinmyacademiclife.Inaddition,thediscussionwithhiminspiredmeandmademetoaimathigherqualityintellectuallevel.Asaresult,mygraduatestudywasfunandameaningfulpartofmylife.Ispeciallythankmygrandmother,father,mother,andbrotherfortheirendlesslove.IwasabletofinishmylonggraduatestudyinMarylandbecauseoftheirenormoussupportandendlessprayerstoGodforme.Mycousinsandcousin-in-laws,Wonsun,Sam,Moonsun,Andrew,andTaewook,alwaysremindmeofthemeaningofthefamily.IreallyappreciatetheirhelpsinceIfirstcametotheUSA.DuringmystayinMaryland,Iwassoluckytohavemanygoodpeoplearoundme.IthankmyofficematesintheUniversityofMarylandfortheirhelpanddiscussion,andforsharingideas:Dongkeun,Gautham,Deepak,Hameed,Sumit,Wanli,Xuanhua,Priyanka,Aamer,Sada,Zahran,Anashua,Vinod,Aneesh,Jayanth,Brinda,Renju,Barath,Sumesh,David,Kursad,Mike,Ohm,Sean,andalltheotherfriendsinSCA-Lab.IwouldliketoacknowledgetheKoreanfriendsandtheirfamiliesinMaryland:Junesong,Jungmin,Kwangoon,Dongin,Eenjun,Hyunsang,Hwansoo,Kyungdong,Sungjoon,Kyongil,Jae-jung,Sangwook,Hyunmo,Pyonguk,Bongwon,Changha,Jihwang,Yooah,Seungjoon,Kyungnam,Beomseok,Jinwook,Minho,Bongshin,Jaeyong,Jaeyoon,Sungwook,Bo-iihyung,Hyunook,Woochul,Joonhyuk,Seungjong,Jusub,Dongik,Soobum,andmanyothers.IalsoappreciatethemembersofmyPh.D.defensecommittee:Dr.ManojFranklin,Dr.Chau-WenTseng,Dr.AlanSussman,andDr.SungLee.Inaddition,IwanttothankDaniel,Timoteo,Joseph,Jennifer,Kwanghoon,Wooyoung,Jaehwa,Jin-hyuk,Ilchul,Woochang,andTJfortheirreligioussupportandprayersforme.IapologizetothoseIhaveinadvertentlyleftout.Mostimportantly,IwouldliketothankmylovelyJiyoun,Andy,andClaire.AndyandClairehavebeenthesourceofhappinessinmyfamily.Jiyounhasalwaysbeenthebestfriend,agreatsupporter,atrustfuladvisoraswellasasweetwife.Lastly,IsincerelythankGodforhisendlessloveandcare.iiiTABLEOFCONTENTSListofFiguresvii1Introduction11.1Motivation....................................11.1.1SimultaneousMultithreadingProcessors................11.1.2Feedback-bas