Tài liệu Advanced Hierarchical Event-Stream Model pdf

Advanced Hierarchical Event-Stream Model

Karsten Albers, Frank Bodmann and Frank Slomka

Embedded Systems / Real-Time Systems, Ulm University

{name.surname}@uni-ulm.de

Abstract—Analyzing future distributed real-time systems, au￾tomotive and avionic systems, is requiring compositional hard

real-time analysis techniques. Well known established techniques

as SymTA/S and the real-time calculus are candidates solving

the mentioned problem. However both techniques use quite

simple event models. SymTA/S is based on discrete events the

real-time calculus on continuous functions. Such simple models

has been choosen because of the computational complexity of

the considered mathematical operations required for real-time

analysis. Advances in approximation techniques are allowing the

consideration of more expressive descriptions of events. In this

paper such a new expressive event model and its analysis algo￾rithm are described. It integrates the models of both techniques.

It is also possible in this module to integrate an approximative

real-time analysis into the event model. This allows to propagate

the approximation through the analysis of a distributed system

leading to a much more efficient analysis.

1. MOTIVATION

The module-based design processes make it possible to

handle the complexity in software and hardware design. Sys￾tems are build using a set of closed modules. These modules

can be designed and developed separately. Modules have only

designated interfaces and connections to other modules of their

set. The purpose of modularisation is to split the challenging

job of designing the whole system into multiple smaller jobs,

allowing the reuse of modules in different designs or to include

IP components of third-party vendors.

Every module-based design concept requires a well defined

interface-concept for connecting the modules. Developing real￾time systems requires for this interface-concept to cover also

the real-time aspects of the modules. A concept for the real￾time analysis is required to handle the modules separatly and

allows a propagation of the real-time analysis results through

the system. It is necessary to propagate the results of the real￾time analysis of the different modules in an abstract way. The

global analysis is build by connecting the local analyses of the

single modules. Therefore it is essiential to have an expressive

and efficient interface describing the influence in timing of

one module to the next module. One aspect of this interface

is the timing description of events which are produced by one

module to trigger the next following module. Another aspect

is the computation capacity that remains for lower priority

modules left over by the higher priority ones.

Consider for example a network packet processor as shown

in figure 1. The single packages are processed by chains

of tasks τ which can be located on different processing

elements P. The processing elements P can be processors,

dedicated hardware or the communication network. The events

Θ triggering the different tasks are equal to the packages

4 10

Θ 11

Θ12

P

2

τ

4

sp2

τ

5

S5

S4

s

p3

τ 7

τ 8

6 S

S7

S8

P

3

τ

6

Θ 8

Θ 9

Θ 7

sp3

Θ 1

Θ 2

Θ 3

τ

P

1

S

S

S

τ

τ

1

2

3

1

2

3

Θ

Θ

Θ 6

5

Θ

Figure 1. Network processor example

flowing through the network. Each processing unit P uses a

fixed-priority scheduling and the task τ on each unit are sorted

by their priority level. Each task τ has, as available capacity,

the capacity S! left over by the tasks τ with a higher priority

located on the same processing unit.

The purpose of this paper is to provide an efficient and flex￾ible approach for the real-time analysis of such a modularized

system. Therefore is a powerful and sufficient event model for

describing the different time interfaces for the different aspects

is necessary.

2. RELATED WORK

The most advanced approach for the real-time analysis of

such a modulare network is the real-time calculus by Thiele

et al. [4], [13]. It is based on the network calculus approach

defined by Cruz [5] and Parekh and Gallager [9].

The event pattern is modeled by an sub-additive upper

and super-additive lower arrival curve αu

f(Δt) and αl

f(Δt)

delivering for every Δt the maximum number of events or

the minimum, respectivly. The service curves βu

r (Δt) and

βl

r(Δt) model the upper and lower bound of the computational

requirements which can be handled by the resource during

Δt. The real-time calculus provides equations to calculate the

outgoing arrival and service curves out of the incoming curves

of a task. To evaluate the modification equations independently

from each other, a good finit description for the curves is

needed. The complexity of the equations depends directly on

the complexity of this description. In [8] and [4] an approxima￾tion with a fixed degree of exactness for the arrival and service

curves was proposed in which each curve is described by three

straight line segments. One segment describes the initial offset

or arrival time, one an initial burst and one the long time rate.

Euromicro Conference on Real-Time Systems

1068-3070/08 $25.00 © 2008 IEEE

DOI 10.1109/ECRTS.2008.19

211