System-Level Design and

Real-Time System Modeling

 Design Methodologies

Waterfall model

Start with Specification

System Level design

Hardware and Software design and development performed independently

Integration and Test

Does OK for smaller and simple systems

Integration disaster when used for large and complex systems

Hardware and Software Co-Design

Start with Specifications and requirements analysis

Hardware and Software concurrent design

Accelerates design and development process

Hardware is designed and upgraded with software in mind

Software is designed and upgraded for the hardware

Function/Architecture Co-Design

Hardware-Software Co-design does not address system-level design

Hardware-Software Co-design concentrates on hardware and software interaction and not system

Uses top-down synthesis of system

Simulation and verification

Usually a hardware platform is available

Platform-Based Design

Came about as result of:

Increasing system complexity

Lengthier development time

To counter lengthier development time, reuse and higher levels of abstraction is necessary

One of the most important components of any system design is system platform

Platform consists of hardware infrastructure and software components

System Resources:

Processors (i.e. Servers, CPUs)

Resources

Reusable (read/write from/to shared memory, memory resources, are typically the bottleneck in many real-time systems)

Consumable (queue/network/bus messages)

System-level tasks

Task (job or process) mapping

Process scheduling

Scheduler is a module that allocates processors and resources to jobs/tasks

Communications

Application Modeling

Dataflow model

Process is a sequence of computations

Process start (Runs/executes) when all of it’s inputs (data and control) and resources are available

After the process finishes executing, it produces its output values and relinquishes the processor

Dataflow process networks are also known as process graphs

But how would we model control communication?

Conditional Process Graph (CPG) allows modeling of data flow as well as control flow and is also suitable for modeling timing

Conditional Process Graph (CPG)

Source node (first process) and Sink node (last process)

These nodes have no execution time and require no resources

Ordinary process nodes

Will be assigned or mapped to processors

Mutually exclusive sets

Simple Graph nodes

Conditional Graph nodes

Conditional node

Disjunction nodes

Conjunction nodes

Process is activated (can run or execute) after all of it’s inputs are available

An exception is conjunction processes

Conjunction processes are activated after one of it’s inputs is available

Process must output before termination

Processing execution environment and scheduling scheme

Preemptive

A higher priority process can (not shall) interrupt execution of a lower priority during it’s execution

A lower priority process can block a higher priority process (priority ceiling protocol and priority inheritance protocol)

Non-preemptive

A process can not be interrupted during it’s execution

Process Execution time

Communication time

For hard real-time systems, worst case time estimate is used on graph for execution and communication times

For soft real time systems, average response time can be used

Here is an example of a Conditional Process Graph:

Release time ri, and absolute deadline di, mark the feasible interval

(ri,di]

Jittered release time

Fixedtasks

Sporadic tasks

Execution time

Time it takes a job to execute alone when it has all of the resources it requires

Maximum and minimum execution times for each real-time process is determined through statistical measurement and analysis

Often for hard real-time processes, maximum execution time is used for modeling the system and in order to determine whether each job can complete its execution before its deadline

Could lead to underutilized system resources if there are wide variations between maximum execution time and average execution time of jobs

If execution time suffers from wide variations in a system, how accurate is deterministic modeling of the system?

In hard real-time systems, and safety critical systems, variations in job execution timesare kept to a minimum

The need to have relatively deterministic execution times places restrictions on system implementations

For example, dynamic structures (such as classes with virtual methods) lead to variable execution times and memory usage and are avoided

Another example is non-deterministic garbage collection

Preemptive sporadic jobs

Determinism allows designer to use deterministic modeling, which allows:

Verification and Validation of the system to be simplified

Deterministic modeling with maximum execution times will allow hard real-time jobs to meet their deadlines

One approach is to allocate the under utilized CPU time to soft real-time jobs

Most frequently used performance measure for jobs that have soft real-time deadlines is the average response time as oppose to maximum response time

Periodic task model

Period Pi of a periodic task Ti is the minimum length of all time intervals between release times ri of consecutive periodic tasks

Execution time is the maximum execution time of all the periodic jobs

Phase, is the release time of the first job in each task is called phase of the task

For periodic tasks, a job is one of many jobs of in a periodic task

An aperiodic task has jobs with soft real-time deadlines or no deadlines at all

Late response time is tolerable but not desired

Sporadic tasks have jobs with hard real-time deadlines but are released at random times

Must insure that their deadlines are always met, minimizing response time is not is secondary

Precedence and Task Graphs

Data dependency

And/Or precedence

Conditional branches

Pipeline

Laxity

Scheduler and schedules

Feasible schedule

Every job completes by its deadline

Optimal scheduling

The algorithm always produces a feasible schedule given a set of jobs has feasible schedules

If an optimal algorithm fails to find a feasible schedule, we can conclude that the given set of jobs can not feasibly be scheduled by any algorithm

For most soft real-time systems, it is acceptable to complete some tasks late or not at all

Performance measure for soft real-time systems could use missed deadline rate or lost job rate

1