C, C++, and AssemblyLanguages for Embedded SystemsProf. Stephen A. EdwardsSummer 2004NCTU, TaiwanWhat are Embedded Systems?Computers masquerading as non-computers.Casio Nokia 7110 SonyCamera Browser Playstation 2Watch PhonePhilips PhilipsDVD Player TiVo RecorderEmbedded System ChallengesDiffers from general-purposecomputing:Real-time ConstraintsPower ConstraintsExotic HardwareConcurrencyControl-dominated systemsSignal-processingUser InterfacesLaws of PhysicsThe Role of LanguagesLanguage shapes how you solve aproblem.Java, C, C++ and their ilk designedfor general-purpose systemsprogramming.Do not address timing,concurrency.Domain-specific languages muchmore concise.Problem must fit the language.SyllabusSoftware languages: Assembly, C, and C++Concurrency in Java and Real-Time Operating SystemsDataflow Languages (SDF)Hardware Languages (Verilog)SystemCSyntax, Semantics, and ModelMarionette ModelYou have control through thesyntax of the languageThe semantics of the languageconnect the syntax to the modelYou ultimately affect a modelSyntaxFormally:Language: infinite set of strings from an alphabetLanguage AlphabetDNA A T G CStudent Transcripts w1007-02 w1009-01 w4995-02English aardvard abacus abalone ...Verilog always module . . .Computation ModelWhat the string ultimately affectsA language may have more than oneLanguage ModelDNA Proteins suspended in waterStudent Transcripts Your knowledgeThe admiration of othersEnglish Natural Language UnderstandingVerilog Discrete Event SimulatorNetlist of gates and flip-flopsSemanticsHow to interpret strings in the modelAlso not necessarily uniqueLanguage SemanticsDNA [[AGA ]]= Arginine[[TAG ]]= STOPStudent Transcripts [[w1007-02 ]]= JavaEnglish [[Look out! ]]= Somebody’s warning meVerilog [[always @posedge clk ]]= Flip-flopDefining SyntaxGenerally done with a grammarRecursively-defined rules for constructing valid sentences“Backus-Naur Form”expr ::literal|| expr + expr|| expr ∗ exprNot a focus of this class: I’m assuming you’ve had acompilers class.Operational SemanticsDescribes the effect a program has on an abstractmachineTypical instruction observes and then advances machinestateClose to implementation, fairly easy to use to create the“obvious” implementationOften includes too many details, can be hard to show thata particular implementation conformsSpecification and ModelingHow do you want to use the program?Specification langauges say “build thisplease.”Modeling languages allow you todescribe something that does or willexistDistinction a function of the model andthe language’s semanticsSpecification Versus ModelingC is a specification language•Semantics very operational•Clear how the language is to be translated intoassembly languageVerilog is a modeling language•Semantics suggestive of a simulation procedure•Good for building a model that captures digitalhardware behavior (delays, unknown values)•Not as good for specification: how do you buildsomething with a specific delay?ConcurrencyWhy bother?Harder model to programReal world is concurrentGood architecture: one concurrently-running processcontrols each independent system componentE.g., process for the right brake, process for the left brake,process for a brake pedalApproaches to ConcurrencyShared memory / Every man for himself•Adopted by Java, other software languages•Everything’s shared, nothing synchronized by default•Synchronization through locks/monitors/semaphores•Most flexible, easy to get wrongSynchronous•Global clock regulates passage of time•Robust in the presence of timing uncertainty•Good for hardware; but has synchronization overheadCommunicationand ConcurrencyIdea: Let processes run asynchronouslyOnly force them to synchronize when they communicateC. A. R. Hoare’s Communicating Sequential Processes•Rendezvous-style communication•Processes that wish to communicate both wait untilthe other is ready to send/receiveKahn Process Networks (later in the course)•Communicate through channels•Reader waits for data; writer never waitsNondeterminismDoes a program mean exactly one thing?Example from C:a = 0;printf("%d %d %d", ++a, ++a, ++a);Argument evaluation order is undefinedProgram behavior subject to the whim of the compilerAre you sure your program does what you think?Nondeterministicis not RandomDeterministic: 1 + 1 = 2 alwaysRandom: 1 + 1 = 2 50% of thetime, 3 otherwiseNondeterministic:1 + 1 = 2 or 3, but I’mnot tellingNondeterministic behavior can look deterministic, random,or something worse.Murphy’s law of nondeterminism: Somethingnondeterministic will choose the worst possible outcomeat the worst possible time.Nondeterminism is AwfulMuch harder to be sure your specification or model iscorrectTrue nondeterminstic language difficult to simulateShould produce “any of these results”Must maintain all possible outcomes, which growsexponentiallyIdiosyncrasies of a particular implementation of anondeterministic language often become the de factostandardExample from VerilogConcurrent procedure execution order undefinedalways @(posedge clk) $write( a )always @(posedge clk) $write( b )First simulator moved procedures between twopush-down stacks, producinga b b a a b b a a b b a a b aLater simulators had to match this now-expected behavior.Nondeterminism is GreatTrue nondeterministic specification often exponentiallysmaller than deterministic counterpartImplicit “all possible states” representationE.g., nondeterministic finite automata for matching regularexpressionsIf system itself is truly nondeterministic, shouldn’t itsmodel also be?Can be used to expose design errorsMore flexible: only there if you want to use itCorrectness remains more elusiveCommunicationMemory•Value written to location•Value stays until written again•Value can be read many times•No synchronizationFIFO Buffer•Value written to buffer•Value held until read•Values read in written orderCommunicationWires•May or may not have explicit write operation•Value immediately seen by all readers•More like a system of equations than a sequence ofoperationsHierarchyMost languages can create pieces and assemble themAdvantage: Information hiding•User does not know details of a piece•Easier to change implementation of piece withoutbreaking whole system•Easier to get small piece right•Facilitates abstraction: easier to understand the wholeAdvantage: Reuse•Pieces less specific; can be used againE.g., Functions in C, Classes in Java,
View Full Document