New User Special Price Expires in

Let's log you in.

Sign in with Facebook


Don't have a StudySoup account? Create one here!


Create a StudySoup account

Be part of our community, it's free to join!

Sign up with Facebook


Create your account
By creating an account you agree to StudySoup's terms and conditions and privacy policy

Already have a StudySoup account? Login here

ST Comp Mthds Electromagnetic

by: Roel Green

ST Comp Mthds Electromagnetic ECE 495

Roel Green
GPA 3.99


Almost Ready


These notes were just uploaded, and will be ready to view shortly.

Purchase these notes here, or revisit this page.

Either way, we'll remind you when they're ready :)

Preview These Notes for FREE

Get a free preview of these Notes, just enter your email below.

Unlock Preview
Unlock Preview

Preview these materials now for free

Why put in your email? Get access to more of this material and other relevant free materials for your school

View Preview

About this Document

Class Notes
25 ?




Popular in Course

Popular in Engineering Electrical & Compu

This 53 page Class Notes was uploaded by Roel Green on Wednesday September 23, 2015. The Class Notes belongs to ECE 495 at University of New Mexico taught by Staff in Fall. Since its upload, it has received 16 views. For similar materials see /class/212164/ece-495-university-of-new-mexico in Engineering Electrical & Compu at University of New Mexico.

Similar to ECE 495 at UNM

Popular in Engineering Electrical & Compu


Reviews for ST Comp Mthds Electromagnetic


Report this Material


What is Karma?


Karma is the currency of StudySoup.

You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 09/23/15
HWSW Codesign W FPGAs Embedded Systems ECE 495595 f0verview Slides from Embedded Systems Design F Vahid and T Givargis N Embedded computing systems de nition Computing systems embedded Within electronic deVices Hard to de ne nearly any computing system other than a desktop computer Billions of units produced yearly versus millions of desktop units Perhaps 50 per household and per automobile Characteristics of Embedded Systems Singlefunctioned Executes a single program repeatedly Tightlyconstrained Low cost low power small fast etc Reactive and realtime Continually reacts to changes in the system s environment Must compute certain results in realtime Without delay For example a car s cruise controller must monitor and react to speed and brake sensors J ECE UNM 1 2309 HW SW Codesign W FPGAs Embedded Systems ECE 495595 fEmbedded System Example A digital camera Chip CCD lens I I I Jim LII Cm N A v I Mem controller I IISA bus interfaceI I UART I LCD Ctrl A A A V i V Singlefunctioned tightlyconstrained 10W costpowersmall not realtime J ECE UNM 2 2309 HW SW Codesign w FPGAs Embedded Systems ECE 495595 ECE UNM 3 rEmbedded System Challenges N The design challenge for an engineer is to simultaneously optimize a set of possibly con icting design metrics A design metric is a measurable feature of a system s implementation NRE cost NonRecurring Engineering cost The onetime monetary cost of designing the system Unit cost the monetary cost of manufacturing each copy of the system excluding NRE cost Size the physical space required by the system eg bytes and gates Performance the execution time or throughput of the system Power the amount of power consumed by the system for battery lifecooling req Flexibility the ability to change the functionality of the system without incurring heavy NRE cost Timetoprototype the time needed to build a working version of the system Timetomarket the time required to develop a system to the point that it can be released and sold to customers Maintainability the ability to modify the system after its initial release by others Correctness safety etc J 2309 HWSW Codesign w FPGAs Embedded Systems ECE 495595 rEmbedded System Challenges N Improving one design metric one may worsen others TPower Size Performance lNRE cost Designers must be an expert with both software and hardware They must be comfortable with various technologies and moving between them in order to choose the best for a given application and constraints TimetoMarket Design Metric Market Window Period during which the product would have highest sales Challenge Growing system complexities driven by increased IC capacities requires designers to do more in less time J ECE UNM 4 2309 HWSW Codesign W FPGAs Embedded Systems ECE 495595 N rEmbedded System Design Metrics TimetoMarket Design Metric Simpli ed revenue model Product life 2W peak at W Peak revenue Peak revenue from delayed entry Market Area of triangle equals fall revenue Area difference is revenue loss Market rise I I I u t W Time e entry D 2W OH u K Delayed entry B Delays can be costly revenue lost 2 Ontime Delayed0ntime100 Ontime 12 2W W W2 assumes market rise is at 45 degree angle Delayed 12 W DWWD Percentage revenue loss 2 D3W D2W2100 Eg Lifetime 2W 2 52 Wks delay D 10 Wks gt 10326 102262 50 ECE UNM 5 2309 HWSW Codesign W FPGAs Embedded Systems ECE 495595 N rEmbedded System Design Metrics NRE and Unit Cost Metrics Unit cost the monetary cost of manufacturing each copy of the system exclud ing NRE cost NRE cost The onetime monetary cost of designing the system Total cost NRE cost unit cost numunits Perproduct cost total cost numunits NRE costnumunits unit cost Example NRE 2000 unit 2 100 For 10 units Total cost 2000 10100 3000 Perproduct cost 2000 10 100 2 300 Amortizing NRE cost over the units results in an additional 200 per unit When comparing technologies by costs the best option depends on quantity Technology A NRE2000 unit100 Technology B NRE30000 unit30 J ECE UNM 6 2309 HWSW Codesign W FPGAs Embedded Systems ECE 495595 rEmbedded System Design Metrics N NRE and Unit Cost Metrics g Low NRE U 3 Low unit cost a igtlt 9 40 3 Approach 9quot 0 39 39 39 39 39 39 39 perproduct cost 0 800 1600 2400 at high volumes Number of units volume So both perproduct cost and timetomarket must be considered to determine revenue impact Performance Metric 39 Clock frequency instructions per second Commonly used but most Widely abused measure For example for a digital camera example the user cares about how fast it processes images not about the clock speed or instructions per second ECE UNM 7 2309 HWSW Codesign w FPGAs Embedded Systems ECE 495595 rEmbedded System Design Metrics N Performance Metric The two main measures of performance are Latency response time Time between task start and end eg Camera can process images in 025 seconds 0 Throughput Tasks processed per second Note that throughput is NOT always the number of tasks latency because Ofpipelining Camera may be able to process 8 imagessec by capturing a new image while previous image is being stored Three Key Embedded System Technologies Technology de ned A manner of accomplishing a task especially using technical processes methods or knowledge J ECE UNM 8 2309 HWSW Codesign W FPGAs Embedded Systems ECE 495595 rEmbedded System Technologies N Three key technologies for embedded systems Processor technology IC technology Design technology Processor Technology Relates to the architecture of the computation engine used to implement the system s functionality The processor does not have to be programmable Other nonprogrammable digital systems can be considered processors as well Processors can be specialized for implementing a speci c function such as image processing or compression A system may be composed of a collection of specialized processors to opti mize design metrics for the application e g digital camera J ECE UNM 9 2309 HWSW Codesign W FPGAs Embedded Systems ECE 495595 rEmbedded System Technologies N Processor Technology General Purpose ApplicationSpeci c SinglePurpose Controller Datapath Controller Datapath Controller Datapath I I I Control Reg I Control Reg I Control I index I logic and le logic and le logic state regs I I state regs I I I I total I General 39 Custom 39 state Aw Aw regs I I I V I I I V I I I Program Data Program Data Data memory memory I memory memory I memory Assembly I Assembly I code for I code for I total 0 total 0 f0ri1t0 I forizlto I I I GeneralPurpose Processors Program memory and data path are generic can execute any program J ECE UNM 10 2309 HWSW Codesign W FPGAs Embedded Systems ECE 495595 rEmbedded System Technologies N Processor Technology GeneralPurpose Processors Data path typically has a large register le and one or more general purpose ALUs Embedded system designer does NOT need to be concerned With the design of the processor heshe simply installs a program into memory Bene ts timetomarket is low exibility is high unit cost can be low in small quantities NRE cost distributed over other customers and perfor mance high When using cutting edge technologies Drawbacks Unit cost can be high in large quantities custom processor can be designed With lower NRE costs performance can be low for certain apps and sizepower can be large because of unneeded features J ECE UNM 11 2309 HWSW Codesign W FPGAs Embedded Systems ECE 495595 rEmbedded System Technologies N Processor Technology SinglePurpose Processors Hardware designed to execute exactly one program using a custom digital circuit commonly referred to as coprocessor accelerator and peripheral From camera example all components except for microcontroller are sin gle purpose processors JPEG codec compresses and decompresses Video frames Features Circuit contains only components needed to execute a single pro gram and n0 program memory is required Bene ts Unit cost may be low in large quantities performance can be high sizepower can be small inverse of GPP Drawbacks Design time and NRE cost may be high exibility low and unit cost high for small quantities J ECE UNM 12 2309 HWSW Codesign w FPGAs Embedded Systems ECE 495595 rEmbedded System Technologies N Processor Technology Application Speci c Processors ASIPs are a programmable processor optimized for a particular class of applications compromise between GPP and singlepurpose processors Examples include microcontrollers and digitalsignal processors Microcontrollers are optimized for embedded control apps where monitor ing and setting of numerous singlebit control signals are common Datapath is optimized for application class by adding special functional units for common operations and eliminating infrequently used units Bene ts exibility can be high while achieving good performance power and size Drawbacks NRE costs can be high both in circuit and compiler design some inef ciency because of features to support reprogrammability J ECE UNM 13 2309 HWSW Codesign W FPGAs Embedded Systems ECE 495595 rEmbedded System Technologies N IC Technology The manner in which a digital gatelevel implementation is mapped onto a chip IC technology is independent of processor technology ie any type of proces sor can be mapped to any type of IC technology Single GPP ASIP purpose Flexibility Processor Maintainabil ity Power ef ciency 4 gt NRE cost Performance Timetoma Size volume PLD Semicustom Fullcustom A Chip is fabricated using a sequence processing steps With transistors fabri cated in the substrate and metal Wires above J ECE UNM 14 2309 HWSW Codesign W FPGAs Embedded Systems ECE 495595 rEmbedded System Technologies N IC Technology Full CustonWLSI In full custom design all layers of Chip fabrication are optimized Transistors are placed to minimize Wire lengths and are sized to optimize delay Characteristics Once a Chip layout is completed the mask speci cation is sent off to be fabri cated VLSI Chip design has a very large NRE cost and long turnaround times measured in months VLSI chip design yields excellent performance and small power and size Usually used only in highvolume or performance critical applications Our VLSI course describes this process in detail Very sophisticated tools eXist to enable layout and simulation J ECE UNM 15 2309 HW SW Codesign W FPGAs Embedded Systems ECE 495595 rEmbedded System Technologies IC Technology Semicustom ASIC gate array and standard cell N For ASIC the lower layers are fully or partially built leaving the upper layers to be customized for the application For gate array ASICs the masks for the transistor and gate levels are already built the Chip already consists of arrays of gates All that remains is to de ne the interconnections of the gates For standard cell ASICs a set of logiclevel cells e g NAND and NOR are hand designed Place and route tools automatically con gure the gates and interconnect to implement the design ASICs are the most popular IC technology ASICs provide good performance and size lower NRE cost Wrt full custom Drawback Still require weeks to months to manufacture ECE UNM 16 J 2309 HWSW Codesign w FPGAs Embedded Systems ECE 495595 rEmbedded System Technologies N IC Technology PLD For programmable logic devices all layers already exist PLDs can be partitioned into two categories simple and complex PLAs PALs and GALs are simple They are programmed by con guring AND andor OR gates CPLDs and FPGAs are complex and implement a more sophisticated con nection scheme between gates PLDs offer a low NRE cost are instantly available and are excellent for proto typing Drawbacks They are larger than ASICs have higher unit cost may consume more power and have lower performance J ECE UNM 17 2309 HWSW Codesign W FPGAs Embedded Systems ECE 495595 rEmbedded System Technologies N Design Technology Refers to the methods used to convert our concept of desired system functional ity into an implementation We must be able to implement the design quickly and the implementation must optimize design metrics A key objective of improving design technology is to enhance productivity of the designer to keep pace With Moores law The number of transistors on an IC doubles every 18 months System re ned through several abstraction levels Three approaches to improving the design process gggg ggcess for increased productivity Compilatiomsynthesis LibrariesP Testveri cation J ECE UNM 18 2309 HWSW Codesign W FPGAs Embedded Systems ECE 495595 rEmbedded System Technologies N Design Technology Compilatior Synthesis ECE UNM 19 Desired functionality is described in abstract manner and lowerlevel imple mentation details are automatically generated Removal of the details improves productivity by as much as an order of magnitude Logic synthesis converts Boolean expressions into a connection of logic gates netlist RTL synthesis converts FSM and register transfers into a datapath of RT com ponents and a controller of Boolean equations Behavioral synthesis converts a sequential program into FSMs and register transfers Compiler converts a sequential program to assembly code RTL System synthesis converts an abstract system spec into a set of sequential pro grams on general and singlepurpose processors J 2309 HWSW Codesign W FPGAs Embedded Systems ECE 495595 rEmbedded System Technologies N Design Technology Libraries1P ECE UNM 20 Libraries allow reuse of preeXisting implementations and therefore improve productivity IP cores are a good example Logic libraries consist of layouts of gates and cells RT library consists of layouts of registers MUXs decoders and functional units Behavioral library consists of compression components bus interfaces display controllers and GPUs Systemlevel library consists of complex systems solving particular problems suCh as an interconnection of processors with OS and programs to implement an ethernet protocol J 2309 HWSW Codesign W FPGAs Embedded Systems ECE 495595 N rEmbedded System Technologies Design Technology TestVeri cation Ensures that functionality is correct in an effort to avoid timeconsuming debugging and iterations from low abstractions to higher levels Simulation is the most common form of veri cation Simulation exists at every abstraction level from gatelevel to GPP simula tors that execute machine code to cosimulators that connect HDL and GPP simulators At the system level model simulators simulate the initial system spec using an abstract computation model independent of processor tech Also model checkers verify certain properties of the speci cation e g cer tain simultaneous conditions never occur or the system does not deadlock J ECE UNM 21 2309 HWSW Codesign w FPGAs Embedded Systems ECE 495595 rEmbedded System Technologies N Design Technology Standards also serve to improve productivity by de ning wellde ned methods and interfaces They eXist at the language synthesis and library levels Languages improve productivity by allowing designers to specify functionality with minimal effort Frameworks improve productivity by providing a software environment for the application of numerous tools and for version management 100000 10000 1000 Productivity 100 Transistors 10 designermonth 1 K 01 I 001 1981 1995 2010 K J ECE UNM 22 2309 HWSW Codesign W FPGAs Embedded Systems ECE 495595 rEmbedded System Technologies N The combination of compilatiOnsynthesis libraries P testveri cation standards languages and frameworks have increased productivity dramatically In 1981 a designer could produce about 100 transistors per month In 2002 a designer could produce about 5000 transistors per month However productivity has not kept pace With IC capacity 10000 100000 1000 10000 100 1000 10 100 1 10 01 1 001 z 01 0001 I 001 1981 1995 2010 f IC capacity Productivity Transistors per chip M Transistorsdesignermonth K ECE UNM 23 2309 HWSW Codesign W FPGAs Embedded Systems ECE 495595 rEmbedded System Technologies N GAP denotes the growing design productivity gap For example in 1981 a leadingedge Chip required about 100 designermonths to design 100 designermonths 100 transistorsdesignermonth 10000 transistors In 2002 a leadingedge Chip required about 30000 designer months 30000 designermonths 5000 transistorsdesignermonth 150000000 tran sistors So the design productivity gap increased the design of a Chip from 100 to 30000 Assuming a designer costs about 10000 per month the cost has risen from 1000000 to 300000000 Few products can afford this so most designs do not even come Close to using the potential Chip capacity J ECE UNM 24 2309 HWSW Codesign w FPGAs Embedded Systems ECE 495595 rEmbedded System Technologies N The situation is even worse however because this assumes that productivity is inde pendent of project team size Unfortunately adding designers to a project team actually decreases productivity This is true because the complexity of having more designers work together grows and this slows their individual productivity 60000 50000 40000 30000 20000 10000 43 4 Months to completion Team product1v1ty transistorsmonth AIndividual designer productivity I I Decreases as 0 10 20 30 40 more designers number of designers are added quotToo many cooksquot can actually lengthen completion time J ECE UNM 25 2309 HWSW Codesign w FPGAs Embedded Systems ECE 495595 G he Codesign Latter N The recent maturation of synthesis enables a uni ed View of hardware and software Sequential program code eg C VHDL ehavioral Synthes Compllers 908 60 s and 70 s e 5 er ans ers ssem 1115 c o s RTSynthesis ssemblers linkers 80 S and 90 S o c ua ons 50 S and 60 S RT ynthes1s ac me ms c on 80 s and 90 s 0 c a es Microprocessor lugnplementatlon VLSI ASIC or PLD program bits quotso twarequot Implementation quothardwarequot Choosing between hardware or software for a particular function is simply a tradeoff among various design metrics There is no difference between what hardware or software can implement J ECE UNM 26 2309 HW SW Codesign W FPGAs Models ECE 495595 ECE UNM l rModels and Architectures Slides from quotHardwareSoftware CoDesignquot text N System design is the process of implementing a desired functionality using a set of physical components The system can be treated as a collection of simpler subsystems together With a method or model to compose the subsystems to create the system functionality A model should possess certain qualities It should be formal so that it contains no ambiguity It should be complete so that it describes the entire system It should be comprehensible to the designers Who use it and easy to modify It should be natural enough to aid rather than impede the designer s understanding of the system Designers choose different models in different phases of the design process to emphasize speci c aspects of interest We refer to these as different levels of abstraction J 21909 ECE 495595 N HWSW Codesign w FPGAs Models rModels and Architectures The designer describes the functionality using a particular model and then trans forms the functionality into an architecture The architecture de nes the system implementation by specifying the number and types of components as well as the connections between them Therefore models describe how the system works and architectures describe how it will be manufactured implemented A design methodology is a set of design tasks that transform a model into an archi tecture It makes sense then to discuss the basic computational models used in system design FiniteState Machines FSMs They are extremely useful in describing control systems because states and state transitions naturally represent their temporal behaVior J 21909 K ECE UNM 2 HWSW Codesign W FPGAs Models ECE 495595 rFSMs An FSM model consists of a set of states a set of transitions between states a set of actions associated With these states and transitions An FSM can be de ned abstractly using the quintuple S I 0 f h S I and 0 represent the set of states the set of inputs and the set of outputs respec tively f and h represent the nextstate and output functions The nextstate function f is de ned as a mapping S X I gt S Here f assigns to every pair of state and input symbols another state symbol The output function It de nes the output values in the present state Statebased FSMs Mooretype are de ned using the mapping S gt 0 Inputbased FSM Mealytype are de ned using the mapping S X I gt 0 K J ECE UNM 3 21909 HWSW Codesign W FPGAs Models ECE 495595 rFSMs For Mealy FSMs the output symbol in each state is de ned by a pair of state and input symbols and is outputted While the state and input symbols persist Consider the Mealy FSM that describes an elevator controller for a building With 3 oors Here the set of inputs I r1 r2 r3 represent the oor requested The set of outputs 0 2 d2 d n u L12 represent the action to be taken by the ele vator eg d2 indicates down 2 floors J ECE UNM 4 21909 HW SW Codesign W FPGAs Models ECE 495595 ECE UNM 5 rFSMs In contrast the Moore statebased FSM is more complicated because the three out put values each need their own states many of the arcs are not shown DataFlow Graphs DFGs They are extremely useful in describing computational intensive systems because mathematical equations are naturally represented in a directed graph J 21909 HW SW Codesign w FPGAs Models ECE 495595 ECE UNM 6 rDataFlow Graphs N The nodes in the directed graph represent operations or functions and the arcs repre sent the order in which the nodes are executed The data ow model of computation is based on two principles Asynchrony all operations are executed when and only when the required oper ands are available Functionality all operations behave as functions which do not have any side effects This implies that any two enabled operations can be executed in either order or they can be executed concurrently Formally DFGs are described as a quintuple N A v v0 f with N n1n2 nM is the set ofnodes J 21909 HWSW Codesign W FPGAs Models ECE 495595 fDataFlow Graphs N A 611612 aL gN gtltN is the set of arcs between nodes V 121 v2 11 E V1gtlt V2gtlt VL represent the set of values associated With the arcs Where vi 6 Vi is the value at arc Ai V0 E V represents the initial values at the arcs f fniz aje 1nij gt Hake 0niVkniE N de nes the function performed by each node n l e N Where Inl and 0ni are the set of incoming and outgoing arcs for each node mi 6 N DFGs are great for representing computations but are not good at control 3 Itl 39t2 39t3 39t4 Popular in describing DSP components and systems J ECE UNM 7 21909 HWSW Codesign W FPGAs Models ECE 495595 FSMs with Datapath FSMDs Most real systems require both control and computation and therefore require fea tures from both FSM and DFG models Operations performed Within a DFG represent the datapath in an FSMD To convert DFGs one can divide time in equal time intervals or states and allo cate one or more states for each node in the DFG The elevator example is reduced to one state c oor r oorc oor 2 r oor output 2 r oor c oor start c oor 2 r ooroutput 2 0 Here we use a variable c 00r to represent state value of the FSM and rflaar to store the request values r1 r2 and r3 It should be noted that although FSMDs are good at representing both control and computationdominated systems they do not support concurrency and hierarchy Therefore they are not appropriate for modeling complex systems J ECE UNM 8 21909 HWSW Codesign W FPGAs Models ECE 495595 Hierarchical Concurrent FSMs HCFSM N HCFSMs consist of a set of states and a set of transitions like FSMs Unlike FSMs each state in a HCFSMs can be further decomposed into a set of sub states andor concurrent substates Concurrent substates execute in parallel and communicate through global vari ables Transitions in HCFSMs can be structured or unstructured Structured transitions occur between states at the same level of hierarchy While unstructured have no constraints Statecharts is a graphical language based on the HCFSM model It supports hierarchy concurrency and communication between concurrent states It uses unstructured transitions and a broadcast communication mechanism Where events emitted by any given state can be detected by all other states K J ECE UNM 9 21909 HWSW Codesign w FPGAs Models ECE 495595 Hierarchical Concurrent FSMs HCFSM N Rounded rectangles denote states at any level and encapsulation is used to express a hierarchical relation between states D 0 starting points E u represents concurrency Arrows denote the transitions between states each arrow being labeled with an event and optionally with a parenthesized condition andor action Here Y is decomposed into two concurrent states A and D A has two substates B and C If event a occurs while in state B A will transfer to state C but only if condition P holds at the time of occurrence If true action 0 will be performed J ECE UNM 10 21909 HWSW Codesign W FPGAs Models ECE 495595 Hierarchical Concurrent FSMs HCFSM N Although the HCFSM model is better suited to represent complex control systems it is not suitable for modeling complex data structures or complex activities Even when using an FSMD model in a HCFSMD only very simple actions e g assignments can be associated With its transitions or states Programming Languages Provide a heterogeneous model that can support data activity and control modeling There are two types imperative eg C and Pascal and declarative e g LISP and PROLOG Imperative languages use a controldriven model of execution in Which state ments are executed in sequential order Declarative languages execute through demanddriven or patterndriven com putation They don t specify order but focus on de ning the target of the computa tion through a set of functions or logic rules J ECE UNM 11 21909 HWSW Codesign W FPGAs Models ECE 495595 rProgramming Languages N For imperative languages a variety of data structures are provided for data modeling such as integers real arrays and structures Activities are modeled using statements functions and procedures the latter provid ing hierarchy The order of execution is controlled using control structures such as sequential composition branching ifthenelse case looping and subroutine calls An advantage of using an imperative programming language is that it is wellsuited to modeling computationdominated behavior Here the problem to be solved can be described using an algorithm e g sort a list of numbers stored in an array Although wellsuited to modeling data activity and the control mechanism of a sys tem they do not explicitly model the system s states This is a disadvantage When trying to model embedded systems K J ECE UNM 12 21909 HWSW Codesign W FPGAs Models ECE 495595 rProgramState Machines PSMs N Programstate machines are a heterogeneous model that integrate HCFSM and the programming language paradigms PSMs consist of a hierarchy of programstates in which each programstate repre sents a distinct model of computation At any given time only a subset of programstates Will be actively carrying out their computations Within the hierarchy the model consists of both composite and leaf programstates A composite programstate is one that can be further decomposed into either concurrent or sequential pro gram substates If they are concurrent all the programsubstates Will be active Whenever the programstate is active The computations of leaf programstates are described using programming lan guage statements K J ECE UNM 13 21909 HWSW Codesign W FPGAs Models ECE 495595 rProgramState Machines PSMs N There are two types of transition arcs Transitiononcompletion TOC arcs are traversed only When the source pro gramsubstate has completed its computation and the condition evaluates true Transitionimmediately TI arcs are traversed immediately Whenever the are con dition becomes true they do not wait for source programsubstate to complete V f N Y variable A arrayl20 of integer v starting Y state 5 D t variable i max integer Eiglrgg r gcy max O I I for i l to 20 do 0m lemon if Ai gt max then I 130m max Ai end if TOC arcs end for e3 J TI arcs AA K J K J ECE UNM 14 21909 HWSW Codesign W FPGAs Models ECE 495595 rProgramState Machines PSMs N States B C and D are leaf states States B and C would also have programming code associated With them Arcs labeled 6 and 63 are TOC arcs While are 62 is a TI arc When state B nishes AND condition 6 is true control Will transfer to state C If condition 62 is true While in state C control Will transfer to state B regardless of Whether C nishes or not Since PSMs can represent a system s states data and activities in a single model they are more suitable than HCFSMDs for modeling systems With complex datacontrol A PSM can also overcome the primary limitation of a programming language since it can model states explicitly A program can be Viewed as a PSM With only one leaf state containing code A HCFSMD can be Viewed as a PSM With all its leaf states containing NO code K J ECE UNM 15 21909 HWSW Codesign W FPGAs Models ECE 495595 rLanguages vs Models N A computational model describes desired system behavior While a language captures models A model can be captured in a variety of languages While a language can capture a variety of models State Seq Data Machine Program Flow C C Java A sequential program is a model a conceptual notion consisting of a set of program instructions for computing something and a notion of how to sequence those instr A sequential program can be captured in many different languages e g C Java A particular language can capture many different models other than sequential pro grams e g state machines and data ow Certain languages may be better than others at representing a particular model ECE UNM 16 21909 HWSW Codesign W FPGAs Models ECE 495595 fLanguages vs Models N For example C can be used to capture state machines but a language designed specif ically for this purpose may do a better job at representing the concept Consider an elevator controller UnitControl Un up down open 1 Control while l while req floor open 0 if req gt floor Request Resolver Up 1 Buttons else in elevator down 1 while req floor updown Up 2 down 2 0 buttons on Open 1 each oor delay 10 K J ECE UNM 17 21909 HWSW Codesign W FPGAs Models ECE 495595 rFinite State Machines with DataPath FSMD N Mooretype FSMD representation Note that every transition is implicitly ANDed With clk req gt oor timer lt 10 M d O t start M d O t 070 1 0 0011 req 2 oor 7 d 0 t req lt oor I 0 100 u 1s up d is down 39 req lt oor 0 is open tis timerstart For FSMDs we carry out the following List all possible states and declare all variables For each state list the possible transitions With associated conditions to other states For each state andor transition list the associated actions For each state ensure that exiting transition conditions are exclusive and complete K J ECE UNM 18 21909 HW SW Codesign w FPGAs Models ECE 495595 ECE UNM 19 rFinite State Machines with DataPath FSMD N For the last step we ensure that no two conditions are true simultaneously and that one condition is always true If the transitions leaving a state are not exclusive we have a nondeterministic state machine Which is more natural the sequential model or the FSMD for describing the elevator controller Many argue the FSMD is better because it naturally maps to controlbased sys tems FSMDs are designed to encourage the designer to think about all possible states of the system and all possible transitions based on possible input conditions Sequential programs are designed to transform data through a series of instructions that may be iterated and conditionally executed Note that it is NOT the graphical nature of state machines that make them more natu ral for computing in this case J 21909 HWSW Codesign W FPGAs Models ECE 495595 rFinite State Machines with DataPath FSMD N It can be captured textualy and still provide the same advantage In fact a textually description is more popular For example we can describe the graphical representation using a state table in Which we list each state as an entry in a table Alternatively you can use a structured language subset approach define IDLE 0 define GOINGUP 1 define GOINGDN 2 define DOOROPEN 3 void UnitControl int state IDLE while 1 switchstate IDLE up0 down0 open1 timerstart0 if req floor state IDLE if req gt floor state GOINGUP A ECE UNM 20 21909 HWSW Codesign W FPGAs Models ECE 495595 rFinite State Machines with DataPath FSMD N if req lt floor state GOINGDN break GOINGUP up1 down0 open0 timerstart0 if req gt floor state GOINGUP if req gt floor state DOOROPEN break GOINGDN up0 down1 open0 timerstart0 if req lt floor state GOINGDN if req lt floor state DOOROPEN break DOOROPEN up0 down0 open1 timerstart1 iftimer lt 10 state DOOROPEN if timer lt 10 state IDLE break Conversely the textual C description given earlier can be captured using a graphical sequential programming language such as a ow chart A ECE UNM 21 21909 HWSW Codesign W FPGAs Models ECE 495595 rHCFSMs HCFSM adds hierarchy and concurrency to FSMs which allows certain operations to be more concisely speci ed req 2 oor ud0 0l0 39 req lt oor re 39ud000l Adding a re input and an additional behavior ie go to the rst oor and open the door is cumbersome under the FSMD approach Exits from each state need to be added cluttering up the diagram K J ECE UNM 22 2 1909 HW SW Codesign W FPGAs Models ECE 495595 rHCFSMs The diagram is Cleaner using the HCFSM approach N f N f req gt oor NormalMode u d 0 1 0 O req gt oor 76170 O O 1 676 req 2 oor u d 0 O 1 O k j u d 0 O 1 0 FireMode FireGoingDn re u d 0 0 0 1 K J J ECE UNM 23 21909 HWSW Codesign w FPGAs Models ECE 495595 rHCFSMs Also concurrency can support both modules ElevatorController Sequential States UnitControl RequestResolver ORdecomposition r NormalMode Only one state active Concurrency ANDdecomposition Multiple states active The Statecharts language supports several extensions timeout mechanism shown above transition taken as soon as state has remained active for time equal to the timeout value history mechanism remembers last substate that an ORdecomposed state A was in before transitioning to another state B This model an interrupt mechanism where control returns to the substate that was exited K Note that HCFSM ONLY supports the transitionimmediately model J ECE UNM 24 21909 HWSW Codesign W FPGAs Models ECE 495595 rProgramState Machine Model PSM N PSMs extends state machines to allow sequential program code to de ne a state s actions including extensions for complex data types and variables PSMs also includes the hierarchy and concurrency extensions of HCFSMs PSMs are a merger of HCFSM and sequential program models F UnitControl ElevatorController int re NormaIMode CIRdecomposition q iieii m Open 2 l A JANDdecomysitzon RequestResolver I while req 2 I floor I Open 2 O FlreMode if req gt floor UPZO downzl I else up 1 Open20 down 2 1 whilefloor gt 1 while req I 111320 floor downzo up 2 down 2 O P39SM support transition open 2 l delayuo 0 completion and tran51t10n Immediately k V J J ECE UNM 25 21909 HWSW Codesign W FPGAs Models ECE 495595 N rModels and Languages Models shape the way we think about the system and therefore you should choose carefully For example a state machine model is more natural When the system must react to a variety of changing inputs like the elevator example The language should capture the model easily Ideally the language should contain constructs that capture features of the model e g bubbles for states etc Alternatively When a modellanguage match is not possible structured tech niques can be used to emulate the missing constructs K J ECE UNM 26 21909 HWSW Codesign W FPGAs Models ECE 495595 rModels and Languages N Choice of computational State Seq Data Concurrent modem is based on Machine Program Flow Processes Whether it allows the Pascal Implementation Implementation Implementation A B C K ECE UNM tional model used to describe the system 27 designer to describe the system Choice of languages is based on Whether it cap tures the computational modelss Choice of implementation is based on Whether it meets power size perfor mance and cost require ments The choice of a programming language is independent of the implementation The choice of language should be based on Whether it captures the computa J 21909


Buy Material

Are you sure you want to buy this material for

25 Karma

Buy Material

BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.


You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

Why people love StudySoup

Steve Martinelli UC Los Angeles

"There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

Jennifer McGill UCSF Med School

"Selling my MCAT study guides and notes has been a great source of side revenue while I'm in school. Some months I'm making over $500! Plus, it makes me happy knowing that I'm helping future med students with their MCAT."

Jim McGreen Ohio University

"Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

Parker Thompson 500 Startups

"It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

Become an Elite Notetaker and start selling your notes online!

Refund Policy


All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email


StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here:

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.