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)