Modeling time in computing - UCF Department of EECS

Modeling time in computing - UCF Department of EECS

MODELING TIME IN COMPUTING Benjamin Gamble What is Time? Can mean many different things to a computer Dynamic Equation Variable System State

2 Outline History Languages & Interpretations Dimensions of the Time Modeling Problem Discrete vs. Dense Finite or Bounded Time Models Linear vs. Branching Determinism vs. Nondeterminism

Time Advancement Problem Concurrency & Composition Analysis & Verification Issues 3 History of Time in Computing First implemented in computer hardware Then adapted for software and computational complexity

Parallel processing mandated a further investigation in timing issues Modern day real time systems 4 Outline History Languages & Interpretations

Dimensions of the Time Modeling Problem Discrete vs. Dense Finite or Bounded Time Models Linear vs. Branching Determinism vs. Nondeterminism Time Advancement Problem Concurrency & Composition Analysis & Verification Issues 5 Choosing the Right

Language 6 Two Main Classes of Languages Operational Well suited to describe the evolution of a system starting at some initial state Based on the key concept of state and transition

Modeled as evolving from a state to the next one when a certain event occurs 7 Operational Example A safe When the correct security code is entered, the safe opens If the safe remains open for 3 minutes, it automatically closes

8 Two Main Classes of Languages Descriptive Better suited for describing the properties that the system must satisfy Logic based formalisms Algebra based formalisms 9

Descriptive Example A safe The safe is open if and only if the correct security code has been entered no more than 3 minutes ago 10 Outline

History Languages & Interpretations Dimensions of the Time Modeling Problem Discrete vs. Dense Finite or Bounded Time Models Linear vs. Branching Determinism vs. Nondeterminism Time Advancement Problem Concurrency & Composition

Analysis & Verification Issues 11 Discrete vs. Dense Time Domains Discrete time means that there is a set of isolated points Dense time means that for every 2 points there is always a third point in between

12 Continuous vs. Non-Continuous Time Models 13 Continuous vs. Non-Continuous Time Models 14 Finite or Bounded Time Models

Many system models assume that the behaviors may proceed indefinitely into the future and maybe even the past This models time as an unbounded set Some system behaviors happen within a time window This will require a bounded time model 15

Bounded Time Model Example Braking a car We know that it requires, at most, a few seconds Testing an anti-lock braking system may include a time window of 0-60 seconds as a temporal domain 16

Hybrid Systems What is a hybrid system? Uses both discrete and dense time modeling When this may be used: Square wave form Continuous sampled at certain points Discrete steps with continuous

variables 17 Linear vs. Branching Time Models Linear interpreted over linear sequences of states 18 Linear vs. Branching Time Models

Branching interpreted over trees of states 19 Determinism vs. Nondeterminism Deterministic Whenever the future state of the system is uniquely determined by its current state and

input values Ex. A light switch Pressing the switch (input) while the light is in state off yields the unique possible state of light on 20 Determinism vs. Nondeterminism Nondeterministic Systems that can evolve to different future

states from the same present state and the same input by making arbitrary choices Ex. A resource arbiter Responds to 2 requests happening at the same time by choosing arbitrarily to whom to grant the resource first 21 Implicit vs. Explicit Time Reference

Explicit Time Reference Using math such as calculus to specify system behavior and its properties Implicit Time Reference Refers to a current time and orders events with respect to it 22

Time Advancement Problem This problem arises when the model of a timed system exhibits behaviors that do not progress past some instant Ex. Pushing a button Actual duration to push a button can be ignored and can be represented abstractly as a zero time event If these types of events are allowed then there could possibly be an infinite number of such transitions in a zero time interval

23 Solutions to the Time Advancement Problem Priori The syntax or the semantics of the formal notation is restricted beforehand, in order to guarantee that the model of any system described with it will be exempt from time advancement problems

24 Solutions to the Time Advancement Problem Posteriori Deals with time advancement issues after the system specification has been built It is then analyzed against a formal definition of time advancement in order to check that all of its actual behaviors do not incur into

the time advancement problem 25 Concurrency & Composition Composition also known as modularization Problems arise when analyzing synchronous subsystems

A classification of dealing with the composition of concurrent units can be spilt in two ways Synchronous vs. Asynchronous 26 Synchronous vs. Asynchronous Synchronous Occur at the same time or at instants of time that are related

Naturally paired with a discrete time domain Asynchronous Each activity can progress at a speed unrelated to others There is no need to know in which state each unit is at every instant 27 Outline

History Languages & Interpretations Dimensions of the Time Modeling Problem Discrete vs. Dense Finite or Bounded Time Models Linear vs. Branching Determinism vs. Nondeterminism Time Advancement Problem Concurrency & Composition

Analysis & Verification Issues 28 Expressiveness The possibility of characterizing extensive classes of properties A language is more expressive if it can be finely tuned into a set of behaviors

that satisfy certain properties For each language there exists properties that can only be expressed by them 29 Decidability & Complexity Decidability There is a trade-off between expressiveness

and decidability Complexity is used for decidable models Used to determine the effort required by an algorithm to decide whether a property holds Measured in the amount of memory or time required as a function of the input 30 Analysis & Verification Techniques

Exhaustive Enumeration Automated Exploration of graphs Syntactic Transformations Address the verification problem by logical deductions Specification and requirements are in descriptive form

31 Outline History Languages & Interpretations Dimensions of the Time Modeling Problem Discrete vs. Dense Finite or Bounded Time Models Linear vs. Branching

Determinism vs. Nondeterminism Time Advancement Problem Concurrency & Composition Analysis & Verification Issues 32 Questions? 33

Recently Viewed Presentations

  • Open Enrollment - Texas A&M University System

    Open Enrollment - Texas A&M University System

    Annual Enrollment. Health Care CoverageFor YouandYour Family. A&M Care Plan. ... Well on Target Portal. ... the doctor is a primary care doctor or a specialist. Primary care doctors are family practitioners, internists, OB/GYNs, and pediatricians and the $ 30.
  • Managing the Gemini Project Matt Mountain - Director

    Managing the Gemini Project Matt Mountain - Director

    Managing the Gemini Project Matt Mountain - Director ... Hughes, Sensis Corp (Optical Systems Engineer and Systems Engineer) Commercial Optical Industrial experience Phase Shift Technology (Manager of Optical Systems) With Gemini for nine years Systems Engineer in 1992 Acting Project...
  • UK Power Networks PowerPoint

    UK Power Networks PowerPoint

    Single point of Contact for Fault information. Single point of Contact for EHV Planned Outage Information. Automated reports are being worked on, manual process to setup and check all data. Proposing to test this month. Will be routine automated email...
  • Document No: GSC-21_006 Source: CCSA Contact: Li Li

    Document No: GSC-21_006 Source: CCSA Contact: Li Li

    Pg | Global Urbanization is speeding up . GDP Growth 2007-2025. 70% . ... Exploding electric vehicle market and soaring need for improved energy infrastructure are also grasped among the top drivers to the global smart cities market growth. ......
  • Ethical Issues in SLP

    Ethical Issues in SLP

    Ethical Dilemma Decision-Making Process. What is the ethical question? What do we know? What do we need to know? Who are the people involved? What are the possible actions? What evidence, legal and ethical guidance, and/or personal, social and professional...
  • English I Vocabulary

    English I Vocabulary

    Harangue A long and intense verbal attack. NOUN Synonym: a lecture, a scolding The teacher delivered a harangue so terrifying that the students didn't misbehave for the rest of the year. The boss launched into a vicious harangue when he...
  • John's Letters - Baptist Start

    John's Letters - Baptist Start

    The Letters of John Life Light First John 1:5-2:2 Page 1034 in Pew Bibles Love Confidence Born of God That you may know First John 1:5-10 Chapter 2 The Letters of John First John 2:1-2 Page 1034 in Pew Bibles...
  • Bias In The News - YRDSB

    Bias In The News - YRDSB

    YRDSB Other titles: Arial MS Pゴシック Georgia Wingdings 2 Wingdings Calibri Civic 1_Civic 2_Civic 3_Civic 4_Civic 5_Civic 6_Civic 7_Civic 8_Civic 9_Civic 10_Civic 11_Civic Bias In The News What is the goal of a reporter or a newspaper?