ABSTRACT MOHAN, SIBIN. Exploiting Hardware/Software Interactions for Analyzing Embedded Systems. (Underthedirection ofAssociate ProfessorFrankMueller). Embeddedsystemsareoftensubjecttoreal-timetimingconstraints. Suchsystemsrequire determinism to ensure that task deadlines are met. The knowledge of the bounds on worst-case executiontimes(WCET)oftasksisacriticalpieceofinformationrequiredtoachievethisobjective. One limiting factor in designing real-time systems is the class of processors that may be used. Contemporary processors with their advanced architectural features, such as out-of-order execution, branch prediction, speculation, and prefetching, cannot be statically analyzed to obtain WCETsfortasksastheyintroducenon-determinismintotaskexecution,whichcanonlyberesolved atrun-time. Suchmicro-processors aretunedtoreduceaverage-caseexecutiontimesattheexpense of predictability. Hence, they do not find use in hard real-time systems. On the other hand, static timing analysis derives bounds on WCETs but requires that bounds on loop iterations be known statically, i.e., at compile time. This limits the class of applications that maybe analyzed by static timinganalysisand,hence,usedinareal-timesystem. Finally,manyembeddedsystemshavecom- municationand/orsynchronization constructsandneedtofunctiononawidespectrumofhardware devices ranging from small microcontrollers to modern multi-core architectures. Hence, any sin- gle analysis technique (be it static or dynamic) will not suffice in gauging the true nature of such systems. This thesis contributes novel techniques that use combinations of analysis methods and constantinteractionsbetweenthemtotacklecomplexitiesinmodernembeddedsystems. Tobemore specific,thisthesis (I)introduces ofanewparadigm thatproposes minorenhancements tomodern processor architec- tures, which, oninteraction withsoftware modules, isable toobtain tight, accurate timinganalysis resultsformodernprocessors; (II) it shows how the constraint concerning statically bound loops may be relaxed and applied to makedynamicdecisions atrun-timetoachievepowersavings; (III)itrepresents thetemporalbehavior ofdistributed real-timeapplications ascoloredgraphscou- pledwithgraphreductions/transformations thatattempttocaptureinherent“meaning” intheappli- cation. To the best of my knowledge, these methods that utilize interactions between different sourcesofinformation toanalyze modernembeddedsystemsareafirstoftheirkind. ExploitingHardware/Software InteractionsforAnalyzingEmbeddedSystems by Sibin Mohan A dissertationsubmittedto theGraduateFaculty of NorthCarolinaStateUniversity inpartialfullfillmentofthe requirementsfortheDegreeof DoctorofPhilosophy ComputerScience Raleigh, NorthCarolina 2008 APPROVED BY: Dr. AlexDean Dr. PurushIyer Dr. FrankMueller Dr. TaoXie ChairofAdvisoryCommittee ii DEDICATION toammumma,mom,dadandrads iii BIOGRAPHY SibinMohanwasbornonMarch20,1979toMrs. T.Shobhana andMr. B.M.C.Kumar inKozhikode(Kerala,India),buthaslivedmostlyinthelovelycitythatisBangalore. Hecompleted hisschooling attheFrankAnthony PublicSchool(FAPS),Bangalore. Hereceived hisBachelor of Engineering (B.E.)undergraduate degreeinComputerScienceandEngineering fromPESInstitute of Technology which is a part of Bangalore University, India. He then worked at Hewlett-Packard IndiaSoftwareOperations, Bangalore, asaSoftwareEngineerforoneyear. Sibin joined the graduate program in the Dept. of Computer Science at North Carolina StateUniversityinFall2002wherehehasbeensince,workingwithDr. FrankMueller. Heobtained his Masters degree in Computer Science in Fall 2004. Sibin is the recipient of the “Preparing the Professoriate” fellowship from the Graduate School at North Carolina State University. Since Fall 2004hehasbeenpursuinghisPh.D.inComputerScienceatNorthCarolinaStateUniversity,mainly intheSystemsarea. iv ACKNOWLEDGMENTS This dissertation is the culmination of many years of work, all of which have been ex- tremelyrewarding. Ihavebeenabletoreachthisgoallargelyduetothebelief,supportandwisdom imparted by many people I have had the honour of interacting with over the years. While I try to acknowledge everysingleoneofthem,Irealizethatbeingonlyhuman,Imightmissafewnames. ToDr. Frank Mueller, myadvisor, Ioffer sincere thanks and appreciation for having the patience to shepherd me through the journey that was this Ph.D. As the ancient Chinese proverb states, “a journey of a thousand miles begins with asingle step.” Irealize that this Ph.D., that first important step, would nothave been possible without hisinsight, advice, critique and support. His counsel on research methodology, teaching, presentation skills, writing skills, etc. have all been instrumentalinshapingmeasaresearcher. Hismanagementstyle,dedicationtowardsresearchand attention to detail is something that I can only hope to emulate. He has also guided and actively assisted methrough thelongprocessofsearching forfuturecareeropportunities. Some of the best courses I took during my time at NC State was courtesy of Dr. Matt Stallmann. Hiscourseschallenged andexcitedmeatthesametimeandoftenmademeseethefield ofComputerScienceinanewlight. Hewasalsograciousenoughtomentormethroughtheprocess ofnavigating mywaythroughmyfirstcomprehensive teaching assignment. Comments and questions raised by Dr. Alex Dean, Dr. Purush Iyer and Dr. Tao Xie helped me focus on important issues and avoid pitfalls during the course of my research. I would liketothankthemforbeingapartofmydissertation committeeandguidance provided thus. Dr. PurushIyer,Dr. PengNing,Dr. NagizaSamatovaandDr. TaoXietooktimeofftheir busy schedules to examine and provide valuable feedback on my job application materials. I am thankful for their feedback and the knowledge that they imparted during the whole process. I am alsogratefultoDr. BeckyRuftyforhervaluableadviceonthisandrelatedtopics. Iwouldalsolike tothankDr. DavidWhalleyandDr. JohnRegehrforwritingreference lettersforme. I would also like to thank Dr. Eric Rotenberg as many of the ideas in this dissertation would not have come up if not for the deep understanding of computer architecture he instilled in meviahiscourses. Iwouldalsoliketothankhimformakinghisarchitecture simulator andtoolset available for use in my research. Aravind Anantaraman and Vimal Reddy were always willing to help me to understand and solve problems related to the simulator framework and for that I am grateful. Graduateschoolcanneverbecompleteorpleasantwithouttheadministrationthatsilently v moves the great machinery in the background. Dr. David Thuente as the Director of Graduate Programs has been very helpful in directing me through the administrative details that go along with being a student. I would also like to thank the Computer Science staff members, Margery Page,CarolAllen,GinnyKingandSusanPeaslee,tonamebutafew. NotadaygoesbythatIdon’tremember,orfeelgratefultowards,Mr. Vijayan. Histeach- ings on C++, programming paradigms, operating systems, etc. coupled with quick philosophical insights often drew parallels with slices of real life. I attempt to emulate his remarkable teaching styleeverytimeIstepinfrontofaclassroomfullofstudents. IwouldalsoliketothankDr. Krishna RaoandMr. JoyeJosephwhoseteaching hadaprofound effectonme. Johannes Helander took a chance on a graduate student he met at a conference and has beenamentorandfriendeversince. Thatwasthestartofagreatopportunityforme;anopportunity to work on some really exciting research ideas. Conversations with him range over a diversity of topics, from cutting-edge research ideas to varieties of beer, all of which ensures that every time I talktohimIcomebackhavinglearnedsomething new. Jaydeep,Nirmit,Yifan,Kaustubh,Kiran,Anita,Harini,Anubhav,Nik,Ravi,Chao,Arun, Vivek,Raghuveer andHeshan haveallbeen greatlab-mates overtheyears. Interactions withthem resulted in my learning a great deal and often made me look forward to coming in to work every day. I would also like to thank my various room-mates (Salil, Ajit, Rahul, Ishdeep, Sharath) who havehadtoputupwithmeandmycooking overtheyears! No person is complete without his friends and I consider myself lucky to have some amazing people asclose friends. Nisha, whose thought processes resemble mineinuncanny ways, provides amirror tothe inner workings ofmymind. Iconsider myselflucky tohaveher alongside as one of my closest friends, right from our childhood days. Ayush, Biju, Chatt, Cherry, David, RameshandPalaniensuredthatschoolandeverything elsethatfollowedwasmemorable. Meeting and/ortalking tothemisstillsomething Ieagerly lookforwardto. Cohan,alwayshastheabilityto surpriseme,albeitinapleasantway. Heisbrimmingwithideasthathelovestoshare,isextremely helpful and is one of the nicest, smartest and best read people I have come across. Mrin, Sudheer, Chinmoyee and their family ensured that I never missed home and were always ready to welcome me into their family moments. Hema, a very dear friend, was the first person to take the effort to instruct me on the meaning of my own name. She is a terrific companion for attending concerts, reminiscing about bygone days, you name it. Folks that I met while working in various voluntary organizations oncampushavealsohelpedmeachieveawell-rounded outlook onlife. To Cup-A-Joe, without which I might have graduated sooner, albeit a little poorer as a vi human being. Discussions, debates, encouragement, queries, plans, dreams, all originating from a close circle of friends that used to meet there often helped ground me on some very basic realities in everyday life and provided a valuable sounding board for my thoughts and ideas. Salil, Sarat, Meeta,DC,SK,Milind,Ajit,NikandSallyhave,overtheyears,beeninstrumentalinensuringthat Ikeepmysanityintactandhelpedpassmanyafternoons andeveningsinanenjoyable manner. Iwouldalso like tothank Dr. Appaji Gowdaforbeing, literally, alife-saver. Iwould not beheretoday,doingwhatIam,withouthim. Myfamily. Atsomepointortheother,Ihavebeentherecipientoflove,guidanceandaid from every one who is a part of it. Toname but a few, Bindu, Vasu and their family, Deepa, Sashi andtheirfamily,Shyju,Sreekala,Rajuandtheirfamilieshaveallbeenmostsupportive throughthe variousupsanddownsinmylife. DineshwasthebrotherthatIneverhad,andthenlost. ToRupa,herparentsUshaandK.S.Venkatagiri,andManu,Ihavetheutmostlove,respect andadmiration. Theywelcomedmeintotheirfamilyandtreatmeasoneoftheirown. If I have the confidence to move forward in life, it is due to the unwavering support and dedication ofmyparents. Theyarethebackbone tomyflesh. Theirtrust,confidence andlovehave always been showered upon me. They believed in me when the chips were down and helped me stand up again. They completely back every decision I make, no matter how risky. They always tried tomakemylife better whilemakingsacrifices intheir own. Ihope thattheycantruly believe thattheireffortsandlabourhavebeenfruitful. My grandmother, Padmavathy Amma, was one of the most important people in my life. She raised me from when I was born, catered to my every whim, and instilled in me values that constitute the core of what I am today. She molded my belief system, my thinking abilities, my interactionswithotherpeople,andeveninstilledcultureandethicsinme. Ihopethatsheiswatching overmeandwillbehappywithwhatIhaveachievedsofar. If my grandmother nurtured me during the early part of my life, then my wife, Radha, is the person that seems to have taken over the mantle to back me the rest of the way. She is the mostcaring,lovingandthoughtfulpersonthatIhaveevermet. Icannotbethankfulenoughthatshe agreed to be my wife. My fondest memory at NC State has been meeting her and getting married to her. Time spent with her is simply put, joyous. I can have an intelligent conversation with her onanytopic under thesun. Hersuperb ability toplaythepart ofthedevil’s advocate onanytopic, technical or not, has helped meunderstand, rethink and shape manyof mydecisions and beliefs. I am glad that she has infinite patience that allows her to put up with my idiosyncrasies. She is the musetomyflightsoffancyandinspiration fortheideasthatmakeittotherealworld. vii TABLE OFCONTENTS LISTOFTABLES.................................................................... xi LISTOFFIGURES .................................................................. xii 1 Introduction ...................................................................... 1 1.1 Real-TimeSystems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Worst-CaseExecutionTime(WCET) . . . . . . . . . . . . . . . . . . . . . . . . 2 1.3 TimingAnalysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.4 TacklingtheComplexityofContemporary Processors . . . . . . . . . . . . . . . . 4 1.4.1 CheckerMode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.5 RelaxingConstraints onEmbeddedSoftware . . . . . . . . . . . . . . . . . . . . 5 1.5.1 ParaScale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.6 AnalysisofDistributed EmbeddedSystems . . . . . . . . . . . . . . . . . . . . . 7 1.7 Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.8 Hypothesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2 CheckerMode –TacklingtheComplexityofModernProcessors...................... 9 2.1 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.2 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.2.1 Plausibility oftheapproach . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.2.2 Processor VendorLimitations . . . . . . . . . . . . . . . . . . . . . . . . 11 2.2.3 Assumptions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.2.4 Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.3 CheckerMode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.3.1 Processor Enhancements . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.3.2 SoftwareOverview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.3.3 Driver/Analysis Controller andTuning. . . . . . . . . . . . . . . . . . . . 16 2.3.4 FalsePathIdentification andHandling . . . . . . . . . . . . . . . . . . . . 17 2.3.5 LoopAnalysisOverhead . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.3.6 InputDependencies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.3.7 AnalysisOverhead . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2.4 Experimental Framework . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2.5 Results. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 2.5.1 C-LabBenchmarkResults . . . . . . . . . . . . . . . . . . . . . . . . . . 21 2.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 viii 3 MergingStateandPreserving TimingAnomaliesinPipelinesofHigh-EndProcessors 24 3.1 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 3.2 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 3.3 Snapshots . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 3.4 AnalysisModel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 3.5 Snapshot CaptureusingPipelineDrain-Retire(DR)Technique . . . . . . . . . . . 27 3.6 Capturing StructuralandDataDependencies usingReservation Stations . . . . . . 28 3.6.1 Structural Dependencies . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 3.6.2 DataDependencies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 3.7 Snapshot Usage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 3.8 Merging PipelineSnapshots . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 3.8.1 Merging TwoSnapshots . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 3.8.2 Incorrect MergeTechnique . . . . . . . . . . . . . . . . . . . . . . . . . . 35 3.8.3 Merging ReservationStations . . . . . . . . . . . . . . . . . . . . . . . . 36 3.8.4 MergeforMorethanTwoSnapshots . . . . . . . . . . . . . . . . . . . . . 37 3.9 ProofofCorrectness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 3.10 Merging RegisterFiles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 3.11 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 3.12 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 4 FixedPointLoopAnalysisforHigh-EndEmbeddedProcessors...................... 48 4.1 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 4.2 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 4.3 Reduction ofAnalysisOverheadforLoops . . . . . . . . . . . . . . . . . . . . . 49 4.3.1 FixedPointTimingandOut-of-order Execution . . . . . . . . . . . . . . . 49 4.3.2 FixedpointPipelineStateAnalysisusingReservation Stations . . . . . . . 52 4.4 Experimental Framework . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 4.5 TimeDimensionAnalysisResults . . . . . . . . . . . . . . . . . . . . . . . . . . 56 4.5.1 PartialAnalysisofLoops . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 4.5.2 CLabBenchmarks: SRTbenchmark . . . . . . . . . . . . . . . . . . . . . 57 4.5.3 Composinglongerbenchmark pathsusingloopWCECbounds . . . . . . . 61 4.5.4 OtherCLabBenchmarkresults . . . . . . . . . . . . . . . . . . . . . . . . 63 4.6 PipelineStateAnalysisResults . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 4.7 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 5 ParametricTimingAnalysisandItsApplicationtoDynamicVoltageScaling......... 66 5.1 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 5.2 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 5.3 NumericTimingAnalysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 5.4 ParametricTimingAnalysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 5.5 CreationandTimingAnalysisofFunctionsthatevaluateParametricExpressions . 77 5.6 UsingParametricExpressions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 5.7 Framework . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 5.8 Experiments andResults . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84 5.8.1 OverallAnalysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87 ix 5.8.2 Leakage/Static Power . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88 5.8.3 WCET/PETRatio,Utilization ChangesandOtherTrends. . . . . . . . . . 90 5.8.4 Comparison ofParaScale-GwithStaticDVSandLookahead . . . . . . . . 92 5.8.5 Overheads . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94 5.9 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95 6 TemporalAnalysisforAdaptingConcurrentApplicationstoEmbeddedSystems..... 96 6.1 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96 6.2 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97 6.2.1 AwarenessofHardwareCapabilities . . . . . . . . . . . . . . . . . . . . . 97 6.2.2 Model-based Development . . . . . . . . . . . . . . . . . . . . . . . . . . 98 6.2.3 LimitationsofAnalysisTechniques . . . . . . . . . . . . . . . . . . . . . 99 6.2.4 Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99 6.3 SavingMemorythroughSequential Execution . . . . . . . . . . . . . . . . . . . . 101 6.3.1 Futures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102 6.4 TheTimingGraph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103 6.4.1 Representation oftheTimingGraph . . . . . . . . . . . . . . . . . . . . . 103 6.4.2 GraphInvariants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105 6.5 Information SourcesandGraphCreation . . . . . . . . . . . . . . . . . . . . . . . 106 6.5.1 Information Gathering Techniques . . . . . . . . . . . . . . . . . . . . . . 106 6.5.2 GraphCreation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108 6.6 TimingGraphTransformations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109 6.6.1 Assumptions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110 6.6.2 GraphPruningandReduction . . . . . . . . . . . . . . . . . . . . . . . . 110 6.7 OutcomeofTimingGraphTransformations . . . . . . . . . . . . . . . . . . . . . 114 6.7.1 FuturesandProgramModifications . . . . . . . . . . . . . . . . . . . . . 116 6.7.2 FalseParallelismandHotSpots . . . . . . . . . . . . . . . . . . . . . . . 117 6.8 Experimental Framework . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118 6.9 Results. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120 6.9.1 GraphResults . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120 6.9.2 TemporalTimingAnalyzerResults . . . . . . . . . . . . . . . . . . . . . 121 6.10 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122 7 RelatedWork.....................................................................124 7.1 WCETRequirements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124 7.2 StaticTimingAnalysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125 7.3 DynamicandStochastic TimingAnalysis . . . . . . . . . . . . . . . . . . . . . . 127 7.4 TimingAnomalies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127 7.5 CheckerMode RelatedWork(HybridTechniques) . . . . . . . . . . . . . . . . . 129 7.6 ParaScaleRelatedWork. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131 7.7 TemporalTimingAnalysisRelatedWork . . . . . . . . . . . . . . . . . . . . . . 133
Description: