##
This **preview** shows page *1-2-3-18-19-37-38-39*
out of 39 **pages**.

*View Full Document*

End of preview. Want to read all 39 pages?

Upload your study docs or become a GradeBuddy member to access this document.

View Full Document**Unformatted text preview:**

Block Diagrams for Modeling and DesignEdward A. Lee ProfessorUC Berkeley Dept. of EECSAbstractVisual depictions of electronic systems have always held a strong human appeal, making them extre...Domains where Block Diagrams are Common• Circuit schematics• Computer architecture• Dynamical systems• Control theory• Signal processing• CommunicationsBut the meaning of these diagrams can be quite different.Properties of Block Diagrams• Modular• Large designs are composed of smaller designs• Modules encapsulate specialized expertise• Hierarchical• Composite designs themselves become modules• Modules may be very complicated• Concurrent• Modules logically operate simultaneously• Implementations may be sequential or parallel or distributed• Abstract• The interaction of modules occurs within a “model of computation”• Many interesting and useful MoCs have emerged• Domain Specific• Expertise encapsulated in MoCs and libraries of modules.Blocks and Signals• Blocks represent activities• May have inputs and outputs, or not• May be implemented concurrently, or not• Are conceptually concurrent• Signals represent shared information• Shared variables• Functions of time• Sequences of tokens• Events in timeSpecifying Blocks• Denotationally:• A relation between signals (constraints on acceptable signals)• A function mapping input signals to output signalse.g.• Operationally:• Given observations of some signals, how do we change other signalse.g.SemanticsThe meaning of an interconnection of blocks (a system)• Denotational semantics:The set of properties that signals must have in a particular interconnection• Operational semantics:How to compute the signal values for a particular interconnectionDeterminacy• A behavior of a system is a set of signal values that obeys the semantics.• A system is determinate if knowing the inputs, there is at most one behavior.• A system is receptive if for all inputs there is at least one behavior.• A semantics is determinate if all systems are determinate.Nondeterminacy can be useful in modeling: a family of behaviors is described and analyzed compactly.However, nondeterminism is risky in design if it means that behavior is underspecified.Nondeterminacy can be viewed as a family of behaviors.Some Candidate Semantics1. Analog computers (differential equations)2. Discrete time (difference equations)3. Discrete-event systems4. Synchronous-reactive systems5. Process networks6. Dataflow7. Sequential processes that rendezvousBasic claim of this talk: each of these has its place.Essential Differences — Models of TimeKey Semantic Issues• Does a composition of blocks have a behavior? More than one behavior?• Typical hard case: Denotationally, the behavior here is a signal that is fixed point of f.• Can a simulation or analysis strategy find a behavior? All behaviors? A subset of behaviors sat...• The “strategy” is an operational semantics, and we need to know whether this semantics is the s...• Does a block diagram have the same semantics as a block?• This is sometimes called the “compositionality” property.Key Practical Issues• Can it be simulated?• Bounded memory• Bounded time for at least a partial solution• Simulation speed• Can it be implemented?• Bounded memory• Bounded time for at least a partial solution• Synthesis algorithms• How many ways can it be implemented?• Software vs. hardware• Parallel vs. sequential• Scheduling algorithms• Avoiding overspeficiation1. Analog ComputersExample: First-order differential equation:PropertiesSemantics:• blocks are relations between functions of time• fixed point is a set of functions of time satisfying these relationsStrengths:• Accurate model for many physical systems• Determinate under simple conditions (strict causality in feedback loops)• Established and mature (approximate) simulation techniquesWeaknesses:• Covers a narrow application domain• Tightly bound to an implementation• Relatively expensive to simulate• Difficult to implement in software2. Discrete Time ProcessingExample: Difference equation:PropertiesSemantics:• blocks are relations between functions of discrete time• fixed point is a set of functions of discrete time satisfying these relationsStrengths:• Useful model for many embedded signal processing systems• Determinate under simple conditions (strict causality in feedback loops)• Easy simulation (cycle-based)• Easy implementation (synchronous circuits or software)Weaknesses:• Covers a narrow application domain• Global synchrony may overspecify some systems3. Discrete-Event ModelsEvents occur at discrete points on a time line that is usually a continuum. The entities react to...Example application areas:• Communication networks• Queueing systems• Manufacturing systems• Hardware architectureExample: Hardware ArchitecturePropertiesSemantics:• Signals are sets of events placed in time (finite or infinite)• Blocks are relations between signals• Fixed point is a set of signalsStrengths:• Natural description of asynchronous digital hardware• Global synchronization• Determinate under simple conditions (strict causality in feedback loops)• Simulatable under simple conditions (delta causality in feedback loops)Weaknesses:• Expensive to implement in software• May over-specify and/or over-model systems (global time)Machinery for Studying Semantics of 1,2, and 3• The Cantor metric: , where is the glb of the times where and differ.• Metric space theorems provide conditions for the existence and uniqueness of fixed points.Example result: VHDL (a DE language) permits programs where a fixed point exists but no simulator...4. Synchronous/Reactive ModelsA discrete model of time progresses as a sequence of “ticks.” At a tick, the signals are defined ...Application areas:• Anything with elaborate control logic• User interfacesPropertiesSemantics:• Each tick represents a new fixed point computation• Convergence to fixed points (when possible) is finiteStrengths:• Good match for control-intensive systems• Tightly synchronized• Determinate in most cases (use constructive semantics)• Maps well to hardware and softwareWeaknesses:• Computation-intensive systems are overspecified• Modularity is compromised• Causality loops are possible (no fixed point or multiple fixed points)• Causality loops are hard to detect5. Process

View Full Document