Path: utzoo!attcan!uunet!samsung!sol.ctr.columbia.edu!src.honeywell.com!klemmer!vestal
From: vestal@SRC.Honeywell.COM (Steve Vestal)
Newsgroups: comp.arch
Subject: Re: Real Time/Cache
Message-ID: <1990Dec11.215313.20967@src.honeywell.com>
Date: 11 Dec 90 21:53:13 GMT
References: <11190@pt.cs.cmu.edu>
Sender: news@src.honeywell.com (News interface)
Organization: Honeywell Systems & Research Center
Lines: 37
In-Reply-To: lindsay@gandalf.cs.cmu.edu's message of 25 Nov 90 23:21:21 GMT
Nntp-Posting-Host: klemmer.src.honeywell.com


In article <11190@pt.cs.cmu.edu> lindsay@gandalf.cs.cmu.edu (Donald Lindsay) writes:

>> One of the interesting problems in real-time systems, is finding
>> the guaranteed-not-to-exceed execution time of a piece of code.

There are actually two distinct effects to be considered here: the impact of
caching due to preemption and the impact of caching due to data-dependent
memory access patterns within each task.

As far as preemption, assuming that worst-case time equals time with caches
disabled may be a bit pessimistic (not to mention possibly incorrect in some
pathalogical cases).  It may be possible to arrive at a worst-case context swap
time that includes cache effects, which in turn can be handled in some
scheduling models (e.g. rate monotonic scheduling).  The major problem here
is accurately determining what the worst-case context swap time will be.

The second problem is determining the worst-case execution time for a
(nonpreempted) task.  What is required is a determination of some "longest"
path through a task, which isn't as simple as finding the longest path through
some control flow graph when caches are present.  Basic block execution times
(arc lengths in the control flow graph) may depend on where control came from
and on the contents of variables/registers.  (I'm ignoring data-dependent
control flow, e.g. real-time Euclid.)

To say that the only execution time measure of interest in hard real-time
systems is a verifiable upper bound on execution time (ignore average
throughput, ignore measurements based on a few sample inputs) may be
excessive.  There are techniques to handle occasional "timing faults" in hard
real-time systems.  However, I would be interested to know of 1)
tools/techniques to determine reasonably tight worst-case execution
time bounds for specific processors, and 2) comparisons of processors based on
worst-case execution time bounds rather than average execution times.

Steve Vestal
Mail: Honeywell S&RC MN65-2100, 3660 Technology Drive, Minneapolis MN 55418 
Phone: (612) 782-7049                    Internet: vestal@src.honeywell.com