Real-Time Computing
For Human Computer Interfacing

November 4, 2002

Copyright* 1997-2002
Perry R. Cook, Princeton University




Jump to Expanded Lecture Notes
or Text Only Version of Expanded Lecture Notes

I. What's Real-Time? Some Definitions



Encyclopedia of Computer Science (VNR 1993) says:

    Computer Processing Modes and Times:

    Card Oriented Batch

    100-10000s

    Keyboard Oriented Batch

    1-100s

    Interactive Computing

    1-10s

    Online Inquiry and Transactions

    1-10s

    Message Switching

    0.1-10s

    Data Acquisition and Control

    0.01-10s






Ib. What's Real-Time? Continued

What do the Computer Companies Say?
  • SGI: Media Playback is Synchronizable
    to 1 Audio Sample

  • Windows: Graphics Display Looks Smooth,
    Audio Doesn't Click too Much
    Prerecorded Game Sounds Play Quickly

  • Apple, NeXT, Others: Still different definitions.

  • Computer Company Definitions Typically Say Little
    About Latency Guarantees!






Ic. What's Real-Time? Continued

What do the Controls/Robotics People Say?
  • Systems Function Under Time Constraints

  • Imposed by External Processes

  • Scheduling and Resource Allocation Guarantees

  • Synchronous, or Guaranteed Timings (Stability)




II. Controls Systems vs. Media Delivery

    Media Delivery:
    • Make it look/sound smooth, degrade gracefully
    • No clicks or pops in audio, no jerks in video.

    Control Systems:

    • Close a feedback loop with sensors and motors.
    • Guarantee STABILITY.

    HCI is Both:

    We're really interested in combining two areas. We want to get user input,
    process it in a timely fashion, and display something smoothly and convincingly
    (with small or controllable delay) in response. The human and computer make
    a complete feedback system. Many modern HCI applications are active
    feedback control systems, and thus stability can be a consideration.



III. Control Systems

  • A Classic Feedback Control System

    • Feedback allows system to control itself

    • Human sets desired state, but is not part of feedback

    • Must worry about stability of feedback systems

  • What are some systems where human is part of feedback?


IIIb. Control Systems

    Humans in the Feedback Loop:
    • Cars and things you steer

    • Musical Instruments (some, but not all)

      • Theremin
      • Brass
      • Bowed



IIIc. Control Systems

    Car:

    • Actuator: Steering system
    • Mechanical System: Car, Wheels, Tires

    Human:

    • Sensor: Visual Sensors (maybe more!)
    • Controller: Brain and Arms

A More General Picture of a Feedback Control System:



IIId. Some Feedback Control Systems with Humans

    Broom Balancing

    • Actuator: Hand
    • System: Physics of Broomstick
    • Sensor: Visual/Tactile/Kinesthetic
    • Controller: Human

    Video Game

    • Actuator: Hand/Joystick
    • System: Computer running game software
    • Sensor: Visual (auditory) System(s)
    • Controller: Human

    Theremin

    • Actuator: Hands
    • System: Theremin electronics
    • Sensor: Auditory
    • Controller: Human



IIIe. Diagram of Control System with Human

    Problems:
    • Latency

    • Overcompensation, stability (gain)

      • Feedback means possibility for instability
      • System Delay (VR Sickness)
      • Sampling and measurement errors

      • Human overcompensation
      • Variable Reaction time (attention, ...)
      • Resolution
      • Training



IV. Synchronous vs. Asynchronous Models
Polled vs. Interrupt Operation

  • Synchronous Real-Time
      Based on time-ordered external events.
      Processor responds instantaneously to events.
      (or time between events >> response time)

  • Asynchronous Real-Time
      Events at times indexed on the real numbers.
      System responds within specified bounds.
To accomplish: We can Poll, use Interrupts, or both.





V. Data and Processing Models


  • Queues and Scheduling:
    • FIFOs (fixed priority)
    • Priority-based


  • Interrupts:
    • Single Priority
    • Multi-Level
    • Nestable
    • Hardware vs. Software





Vb. Data and Processing Models Continued


  • Process/Device Communication:
    • Shared Memory
    • Messages
    • DMA
    • Multi-Bus/Ring/Star/Common Bus


  • Input/Output Buffers
    • Ping Pong
    • Single with Hi/Low Water


VI. Complexity!!!

Online: Scheduling, Interrupt Handling, Load Monitoring, ..
Development: Debugging, Optimization, Profiling, ..

=> Need for an Operating System

Some Real-Time Operating Systems

VxWorks

.

OS-9

.

VRTX

.

LynxOS

.

Chimera:

 MC680x0

RT Mach

80960, 80486, MIPS R3000

DSP/Media Processor Real-Time OS:

IBM MWave/OS

MWAVE DSP

AT&T VCOS

DSP3210

SPOX

TICX0, Motorola 56x, ADI 21x



VII. Multiple Processes

One Common Software Model:
  • Main Loop
    • Polls Non-Critical Inputs
    • (Maybe) Services Queue
    • Waits Around a Lot
  • Interrupt Service Routines (ISRs)
    • Respond Instantaneously
    • Typically Very Short

Queue Servicing Can Also Be Done on a Clocked ISR



VIIb. Multiple Processors

Why?
  • Segments and Isolates the Problems
  • Improves Response Times
  • Saves Cost
Why Not?
  • Can Increase Complexity and Indeterminacy
  • Can Degrade Response Times

Symmetric Processors (all the same type) or Not
May Share Memory or Not
May Run Synchronously or Not


VIII. DSP and DSPs

What's a DSP?

    • Processor good for DSP algorithms

      • Filters
      • FFT's
      • Matrix and Vector Math

    • Fast (Single Cycle) Multiplies +

    • Optimized Data Paths (2+ operands)

    • Address Generation Hardware:

      • Pointer Arithmetic
      • Modulo incrementing/decrementing
      • Bit Reversing
      • Increment/Decrement by N

    • I/O Support (A/D and D/A, Host Communication)


VIIIb. What are DSPs used for?

Applications:

    • Data Compression/Decompression
    • Telephony (MODEMS)
    • Audio Processing
    • Audio Synthesis
    • Speech Synthesis/Recognition
    • 3D Audio
    • 3D Graphics
Why?
    • More suitable
    • Frees up less suitable processors
    • $$$$$
    • Interactivity (latency, time)
Why Not?
    • Hard to develop for
    • Communications with other processors
    • Data flow
    • Synchronization

VIIIc. DSP -> Media Processors -> Media Extensions

Media Processors:
    • Combine Video, Audio, and more
    • Share memory between these types
    • Split ALU and data paths into smaller sub-units

      Media Data Types:
      • Video: 8 bit data, lots of it
      • Audio: 16+ bits, less of it
      • Compressed media: Varies

This leads also to "Media Extensions" on Hosts

  • Single cycle multiplies
  • Fixed Pt. Extensions
      Use existing floating point regs,
      but do parallel fixed point ops.
  • Examples: MMX, VIS, HP Media Extensions

VIIId. DSP Trends

Trends for General DSPs:

  • DMA, Local Memory Interfaces
    • Supports I/O
    • Supports Host Communication
    • Supports Data Transfer
  • Speeds go up some, but not as much as hosts
  • Multi Processor support (SHARC, C40)

Trends for Media Processors:

  • Multi function
  • Don't know yet

Trends for Host Based DSP:

    Media Extensions
Overall Need: Operating Systems?


IX. Microcontrollers

  • Microcontrollers Historically:
    • Small Words and Integer Math
    • Low Level Language
    • Hardware Interrupt Capabilities
    • Peripheral Devices for Inputs
    • Low Cost

  • Modern Microcontrollers:
    • Small Words (relatively) Integer Math (or not)
    • Higher Level Language Support
    • Peripheral Inputs Integrated
    • Low Cost

IXb. Microcontrollers Continued

  • Old: H8 (Minuteman missles), 68xx, 65xx, Zx, 80x

      • 8 bit data, 8 bit instruction, 2+K address
      • Clock Rate: 1-2 MHz
      • Language and Interface: Assembler via TTY
      • System cost: $100.00

  • New:

    • PIC Chip ($4-10.00)

    • BASIC Stamp = PIC + More
      • 16 bit data, high level instructions, 2K memory
      • Clock Rate: 4-20 MHz
      • Language and Interface: BASIC via PC Serial Port
      • System cost: $10-35.00

Simple Basic Stamp II Program Example


The KIM-1 microcomputer, 1977

Basic Stamp II SX, 1998





X. Micro/DSP/Host Real-time Processing Examples

  • Basic Stamp Programming Env.

  • Micro -> Micro+DSP via MIDI

  • Micro -> Host via MIDI


Some Web References:

Educational Research Groups and Projects:

U. Michigan Real-Time Computing Lab

Carnegie Melon Real-Time Groups


Commercial:

From Artesyn: Choosing an OS and Choosing a Processor

Resource List Compiled by E. Douglas Jensen


Some Non-Web References Made from Dead Trees:

"Real-time programming : neglected topics"
Caxton C. Foster.
Reading, Mass. : Addison-Wesley Pub. Co., c1981.

"Real-time software for control : program examples in C"
David M. Auslander, Cheng H. Tham.
Englewood Cliffs, N.J. : Prentice Hall, c1990.

"Real-time systems, Specification, Verification, and Analysis,"
Mathai Joseph, ed.
Englewood Cliffs, N.J. : Prentice Hall, 1996

"Introduction to Real-time Software Design,"
S.T. Allworth and R.N. Zobel
New York, Springer Verlag, 1989


* Permission to make digital or hard copies of part or all
of this work for personal or classroom use is granted with
or without fee provided that copies are not made or dis-
tributed for profit or commercial advantage and that copies
bear this notice and full citation on the first page. To copy
otherwise,to republish, to post on services, or to redistribute
to lists, requires specific permission and/or a fee.

Back to Princeton General Information Section