[comp.realtime] Execution timing analysis

steve@titan.tsd.arlut.utexas.edu (Steve Glicker) (04/11/91)

I am looking for a means to analyze the execution timing of a
realtime, distributed, system composed of multitasking processors.
We're interested in measuring minimum, maximum, and average
times between events on different processors as well as
the execution time of tasks on individual processors.  I'd
like to hear of good and bad experiences in conducting these
measurements as well as information, tools, and techniques which
have proven to be useful.  If there is interest I'd be glad
to post the results.

Steve Glicker
Applied Research Laboratories
The University of Texas at Austin
(steve@titan.tsd.arlut.utexas.edu)
--
Steve Glicker
Applied Research Laboratories
The University of Texas at Austin
(steve@titan.tsd.arlut.utexas.edu)

steve@titan.tsd.arlut.utexas.edu (Steve Glicker) (04/17/91)

A short time ago I posted an inquiry on execution timing to comp.realtime
and comp.lang.ada.  Here are the results.

- - - - - - - - -

I would suggest the following papers for a start:

 IPS-2: The Second Generation of Parallel Program Measurement System.
   Miller et al.
IEEE Transactions on Parallel and Dist. Systems. Vol 1 No. 2.
April 1990.

A Noninterference Monitoring and Replay Mechanism for Real-Time Software...
TSAI et. al.
IEEE Trans. of Software Engineering. Vol 16. No. 8. August 1990.

 ----

I am working in this area.  

Ben Abbott
Vanderbilt

- - - - - - - - -

We've been looking at several areas relating to real-time timing analysis
of systems, including multi-pocessors

We have an instrumentation system that lets you give abstract specifications
of events, data to be collected at events, and analysis and displays to be
generated.  These specifications are automatically processed into a form that
the system uses to do the monitoring, collection, analysis and display.

We have been developing and applying analytic models.  Model parameters are
mesured piece-wise, the analytic models are used to predict actual values, and
selected actual values are compared with easily measured observed values to
validate the analytic model (which can then be used to estimate not so easily
observed values).

Linear benchmarking is a statistical software benchmarking technique for
sequential code fragments that gives confidence intervals and some indication
of execution time variability.

There are several projects at other places that have built tools that do a flow
analysis of sequencial code fragments, attempt to identify shortest and longest
paths, and then use tables to estimate execution times along those paths.

If you're interested in any specific topic, I can email you specific
references.

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

- - - - - - - - -

[I responded to Steve, but I don't have my response.  Nevertheless, his reply follows,]

- - - - - - - - -

In article mumble mumble steve@titan.tsd.arlut.utexas.edu (Steve Glicker) writes:

>We have an instrumentation system that lets you give abstract specifications
SG> Is this a commerical system or is it based on a commerical system (such as

It is a system we developed in-house.  It is software-based (the runtime
system is automatically tweaked), and there is a small amount of overhead
imposed (typically 1-5% as I recall).  For more information on this, talk to
Devesh Bhatt, bhatt@src.honeywell.com.

>We have been developing and applying analytic models.  Model parameters are
SG> We've been thinking about doing this in a simplistic/ad hoc way.  Are these

What we have been doing is sort of the reverse of what performance modeling
people often do.  We identify a formal model first, then deliberately
structure the system along those lines.  That way, we have high apriori
confidence in the accuracy of the models (to the degree that real-time
properties might in some sense be considered formally verified by the model).
For one example of this approach, see "On The Accuracy of Predicting Rate
Monotonic Scheduling Performance," Tri-Ada '90.

>Linear benchmarking is a statistical software benchmarking technique for
SG> I am not sure of what you mean by this.  I'd appreciate a reference on it.

It's an overly complicated software benchmarking technique, essentially a
generalization of the dual-loop benchmarking approach.  See "Linear
Benchmarks," Ada Letters, November/December 1990.

>There are several projects at other places that have built tools that do a
SG> I am aware of some of the work done by A. Mok, U. of Texas at Austin, and

Also, Real-Time Euclid at the University of Toronto.  This is described in one
of the Real-Time System Symposium proceedings (around 87, I think).

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

- - - - - - - - -

per your posting on the net, you are probably familiar with
statistical-histogram based analyzers that implicitly
record min, max, average and so forth.  these are available
from a variety of test/measurement mfrs that are in the so
called logic analyzer or microprocessor development tools trade.

ignoring the marketing angle for a second, tektronix recently
introduced a new tool for hardware oriented timing that measures
event-by-event timing variations.  you use any oscilloscope and
get a real-time display of time-interval vs. time...such as the
time between task executions.  of course you need to find a test
point or signal in your circuit that runs at the desired time-interval.

if you are interested, i can fax or u.s mail you an application note that
describes this new technique.  

stan

- - - - - - - - -

[Stan did FAX me this information.  He is at stans%tekig7.map.tek.com@RELAY.CS.NET]

- - - - - - - - -

The best place to begin looking for the information you wish to find is the Ada Real Time Environments Working Group (ARTEWG).  You should be able to get a tracer
on current players if you take a look in Ada Letters, any recent issue; they have an organization list and special interest group POC's.

If that is not enough, you might send a direct inquiry to SEI.

I know some folks who have done some excellent work in this area, but it is not generally available, due to proprietary agreements.


regards,

-- Bud Hammons

****************************************************************************
* Bud Hammons            Internet:   hammons@csl.dl.nec.com                *
* NEC America Inc.       CompuServe: 71160,3220                            *
* 1525 Walnut Hill Lane  voice:      (214)518-3488     CCSL S/W Dev.Lab.   *
* Irving, Texas 75038    FAX:        (214)518-3990     S/W Eng. Group      *
****************************************************************************

- - - - - - - - -

%T Calculating The Maximum Execution Time Of Real-Time Programs
%A P. Puschner
%A C. Koza
%J Real-Time Systems
%V 1
%N 2
%D Sept 1989
%P 159-176
%K RTS

%T Application of Real-Time Monitoring to Scheduling Tasks with Random Execution Times
%A D. Haban
%A K. Shin
%R TR-89-028
%I International Computer Science Institute, Berkeley, California
%D May 1989

%T Analysis of the Execution Time of Real-Time Tasks
%A M. H. Woodbury
%J Proceedings IEEE Real-Time Systems Symposium
%D December 2-4, 1986
%C Fairmont Hotel, New Orleans, Louisiana
%P 89-96

%T A Source-Level Tool for Predicting Deterministic Execution Times of Programs
%A C. Y. Park
%A A. C. Shaw
%R #89-09-12
%I Department of Computer Science and Engineering, University of Washington,
Seattle
%D September 1989

%T A Priori Execution Time Analysis for Parallel Processes
%A W. A. Halang
%J Proceedings IEEE Euromicro 1989
%D June 1989
%P 62, 65

%T Determining Average Program Execution Times and Their Variance
%A V. Sarkar
%J ACM SIGPLAN Notices (Proceedings of SIGPLAN '89 Conference on Programming
Language Design and Implementation)
%V 24
%N 7
%D July 1989
%P 298-312

Puschner and Vrchoticky have produced a PDCS report "On the Feasibility
of Response Time Predictions - An experimental evaluation". They can be
found at alex@vmars.tuwien.ac.at (Austria) and peter@vmars.tuwien.ac.at

Hope this helps
Ken

--
Ken Tindell             UUCP:     ..!mcsun!ukc!minster!ken
Computer Science Dept.  Internet: ken%minster.york.ac.uk@nsfnet-relay.ac.uk
York University,        Tel.:     +44-904-433244
YO1 5DD
UK                      
--
"The Gulf War won't be like a Rambo film; it will be long, bloody and terrible"

- - - - - - - - -

I appreciate all of the responses.  We are in the process of wrapping up
some initial work here on determining minimum and maximum execution times
as well, so I'll list our work.  The primary motivation for
the posting was to find out how execution timing measurments were being
made and what information was typically considered useful.  We are
in the _initial_ stage of designing a non-intrusive system to record and
analyze execution time activity, so I was trying to find out something
about what is currently being done.

Glicker, S. and F. Hosch (1991). "Toward Automating the Execution Timing
	Analysis of Ada Tasks in Event-driven, Realtime Systems," Applied
	Research Laboratories Technical Report No. 91-4, (ARL-TR-91-4),
	Applied Research Laboratories, The University of Texas at Austin.

This TR describes an approach for determing worst-case execution paths
(minimum and maximum execution times) in Ada tasks.  Contact Betty Korts
at (512) 835-3595 for a copy.

Glicker, S. and F. Hosch (1991). Data Dependent Execution Timing in
	Hardware and Software for Realtime Systems," (Accepted for
	Publication), ACM/IEEE ICSE Workshop on Software/Hardware CoDesign,
	Austin, Texas (May).

This paper describes data-dependencies in hardware and software which
effect execution timing.  It is based on the TR listed above, but is
much more limited in scope.  I am told that the workshop papers will
not be included in the ICSE proceedings so I am not sure about their
availability.  If your interested in their availability contact David
Franke (franke@mcc.com) or Martin Purvis (purvis@mcc.com) at MCC.  As
for our paper, I'd be glad to forward copies when the final version is
complete.


Here is another reference on non-instrusive monitoring,

Tsai, J.P., K. Fang, J. Chen (1990). "A Noninvasive Architecture to Monitor
	Real-Time Distributed Systems," Computer, 23(3), 11-23.


And Al Mok (here at UT) has done work on calculating execution times
as well as on the design of real-time systems.

Mok, A. K. (1985). "SARTOR - A Design Environment for Real-Time Systems,"
	Proc. of the 9th COMPSAC, 174-181.

Thanks again.
--
Steve Glicker
Applied Research Laboratories
The University of Texas at Austin
(steve@titan.tsd.arlut.utexas.edu)