Composing State Machines for System Analysis and Design
Explore the principles of function composition in systems analysis, focusing on state machines and their interconnected nature. Learn about synchronous/reactive systems, composition aspects, and the usefulness of synchrony in physical and software systems.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
CSE314: SYSTEMS ANALYSIS Lecture 04: Composing State Machines Dr. Ahmed Mahmoud, --/10/2020
Introduction to Composition Interesting systems are usually designed by composing simpler components. Systems are functions. So, their composition is function composition. State machines are not given directly as functions that map input sequences into output sequences. State machines are given procedurally, where the update function defines how to progress from one state to the next. In this lecture, we study how to define a new state machine that describes a composition of multiple state machines. Interconnected state machines means that outputs of one state machine may be the inputs to another. CSE314: SYSTEMS ANALYSIS --/10/2020 2
Aspects of Composition I/O I/O timing relationships connections CSE314: SYSTEMS ANALYSIS --/10/2020 3
Synchrony (1) Each state machine in the composition reacts simultaneously and instantaneously. i.e., a reaction of the composite machine consists of a set of simultaneous reactions of each of the component machines. A system that reacts only in response to external stimulus is said to be reactive. Because our compositions are synchronous, they are often called synchronous/reactive systems. Instantaneous Reactions does not take time. Simultaneous Inputs and output occur at the same moment without delay !!! Creates subtleties: Feedback composition when the input of a state machine is connected to its own output!! CSE314: SYSTEMS ANALYSIS --/10/2020 4
Synchrony (2) Very useful model of the behavior of physical systems. Example: Digital circuits are almost always designed using this model. Circuit elements are viewed as taking no time to calculate their outputs given their inputs, and time overall is viewed as progressing in a sequence of discrete time steps according to ticks of a clock. However, the time that it takes for a circuit element to produce an output cannot ultimately be ignored, but the model is useful because for most circuit elements in a complex design, this time can be ignored. Only the time delay of the circuit elements along a critical path affects the overall performance of the circuit. Synchrony has come to be used in software as well. Concurrent software modules interact according to the synchronous model. Languages built on this principle are called synchronous languages. They are used primarily in real-time embedded system design (ATOM, Lustre, LabVIEW). CSE314: SYSTEMS ANALYSIS --/10/2020 5
Side-by-side Composition (1) A single state machine representing the synchronous operation of the two component state machines. The two state machines do not interact with one another. It is useful for combination with other types of composition. CSE314: SYSTEMS ANALYSIS --/10/2020 6
Side-by-side Composition (2) CSE314: SYSTEMS ANALYSIS --/10/2020 7
Side-by-side Composition Example (1) CSE314: SYSTEMS ANALYSIS --/10/2020 8
Side-by-side Composition Example (2) CSE314: SYSTEMS ANALYSIS --/10/2020 9
Cascade Composition (1) Cascade or series composition is where the output of one is the input of the other. The component machines react together, synchronously, as one state machine. CSE314: SYSTEMS ANALYSIS --/10/2020 10
Cascade Composition (2) CSE314: SYSTEMS ANALYSIS --/10/2020 11
Cascade Composition Example (1) CSE314: SYSTEMS ANALYSIS --/10/2020 12
Cascade Composition Example (2) CSE314: SYSTEMS ANALYSIS --/10/2020 13
Product-form Inputs and Outputs Some input values are selected by one part of the environment, while other input values are simultaneously selected by another part. Also, some output values are sent to one part of the environment, while other output values are simultaneously sent to another part. CSE314: SYSTEMS ANALYSIS --/10/2020 14
Product-form I/O Example CSE314: SYSTEMS ANALYSIS --/10/2020 15
General Feedforward Composition Composition of state machines that combines features of both the cascade composition and the side-by-side composition. Forking: To send a value to multiple destinations such as the bottom port of machine A goes both to the output of the composite machine and to the top port of machine B. CSE314: SYSTEMS ANALYSIS --/10/2020 16
Feedforward Example (1) CSE314: SYSTEMS ANALYSIS --/10/2020 17
Feedforward Example (2) CSE314: SYSTEMS ANALYSIS --/10/2020 18
Hierarchical Composition Given a collection of interconnected state machines, there are several ways to hierarchically compose them. we could first compose machines A and B to get, say, machine D, and then compose D with C. Alternatively, we could first compose B and C to get, say, machine E, and then compose E and A. These two procedures result in different but bisimilar state machine models (each simulates the other). --/10/2020 CSE314: SYSTEMS ANALYSIS 19
