* Worst Case Execution Time Tool? @ 2001-12-04 22:51 StationSteve 2001-12-05 0:10 ` Ted Dennison 2001-12-05 10:00 ` Rod Chapman 0 siblings, 2 replies; 13+ messages in thread From: StationSteve @ 2001-12-04 22:51 UTC (permalink / raw) Are there any tools that quantitatively determine the worst case execution time (WCET) of an Ada83 program or subprogram? Execution platform is Intel 80386SX bare machine. I think I'm looking for something similar to SPARK Examiner's WCET analysis, but for Ada83. Thanks in advance for any help... ^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: Worst Case Execution Time Tool? 2001-12-04 22:51 Worst Case Execution Time Tool? StationSteve @ 2001-12-05 0:10 ` Ted Dennison 2001-12-05 17:28 ` Stuart Palin 2001-12-05 10:00 ` Rod Chapman 1 sibling, 1 reply; 13+ messages in thread From: Ted Dennison @ 2001-12-05 0:10 UTC (permalink / raw) In article <3C0D536C.2E059EE8@computer.org>, StationSteve says... > >Are there any tools that quantitatively determine the worst case >execution time (WCET) of an Ada83 program or subprogram? Execution >platform is Intel 80386SX bare machine. I think I'm looking for >something similar to SPARK Examiner's WCET analysis, but for Ada83. Wouldn't such a tool also be able to solve the Halting Problem? ( http://foldoc.doc.ic.ac.uk/foldoc/foldoc.cgi?query=halting+problem ) --- T.E.D. homepage - http://www.telepath.com/dennison/Ted/TED.html No trees were killed in the sending of this message. However a large number of electrons were terribly inconvenienced. ^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: Worst Case Execution Time Tool? 2001-12-05 0:10 ` Ted Dennison @ 2001-12-05 17:28 ` Stuart Palin 2001-12-05 18:33 ` Ted Dennison 0 siblings, 1 reply; 13+ messages in thread From: Stuart Palin @ 2001-12-05 17:28 UTC (permalink / raw) Ted Dennison wrote: > In article <3C0D536C.2E059EE8@computer.org>, StationSteve says... > >Are there any tools that quantitatively determine the worst case > >execution time (WCET) of an Ada83 program or subprogram? > Wouldn't such a tool also be able to solve the Halting Problem? ( > http://foldoc.doc.ic.ac.uk/foldoc/foldoc.cgi?query=halting+problem ) <simple answer> No! </simple answer> If a WCET tool was developed on general terms with the intention of dealing with all forms of program, then it is most likely that if a non-terminating program was submitted for analysis the analysis itself would not halt. In more practical terms, this type of tool will typically constrain the types of program that it will analyze. Typically this might prohibit recursion and demand upper limits for loops to be statically determinable (either from the code or from annotations). Such rarified problems as the Halting Problem are hardly a consideration. -- Stuart Palin Principal Software Engineer BAE SYSTEMS Avionics Ltd, Rochester G-NET 791 3364 mailto:stuart.palin@baesystems.com ^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: Worst Case Execution Time Tool? 2001-12-05 17:28 ` Stuart Palin @ 2001-12-05 18:33 ` Ted Dennison 2001-12-06 14:05 ` StationSteve 0 siblings, 1 reply; 13+ messages in thread From: Ted Dennison @ 2001-12-05 18:33 UTC (permalink / raw) In article <3C0E5927.5657963A@baesystems.com>, Stuart Palin says... >In more practical terms, this type of tool will typically constrain the >types of program that it will analyze. Typically this might prohibit >recursion and demand upper limits for loops to be statically >determinable (either from the code or from annotations). Such rarified >problems as the Halting Problem are hardly a consideration. Ah. So we aren't looking for something that can handle any old program (which it still seems to be would be reducable to the Halting Problem), but rather one that can handle programs that fit certian restrictions. --- T.E.D. homepage - http://www.telepath.com/dennison/Ted/TED.html No trees were killed in the sending of this message. However a large number of electrons were terribly inconvenienced. ^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: Worst Case Execution Time Tool? 2001-12-05 18:33 ` Ted Dennison @ 2001-12-06 14:05 ` StationSteve 2001-12-06 16:40 ` Ted Dennison 0 siblings, 1 reply; 13+ messages in thread From: StationSteve @ 2001-12-06 14:05 UTC (permalink / raw) Of course. Er, I mean sorry, I guess I should have said that I was looking for a *practical* tool that could *productively* address a *real world* problem! ;-) Steve S. Ted Dennison wrote: > In article <3C0E5927.5657963A@baesystems.com>, Stuart Palin says... > >In more practical terms, this type of tool will typically constrain the > >types of program that it will analyze. Typically this might prohibit > >recursion and demand upper limits for loops to be statically > >determinable (either from the code or from annotations). Such rarified > >problems as the Halting Problem are hardly a consideration. > > Ah. So we aren't looking for something that can handle any old program (which it > still seems to be would be reducable to the Halting Problem), but rather one > that can handle programs that fit certian restrictions. > > --- > T.E.D. homepage - http://www.telepath.com/dennison/Ted/TED.html > > No trees were killed in the sending of this message. > However a large number of electrons were terribly inconvenienced. ^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: Worst Case Execution Time Tool? 2001-12-06 14:05 ` StationSteve @ 2001-12-06 16:40 ` Ted Dennison 2001-12-06 21:27 ` StationSteve 0 siblings, 1 reply; 13+ messages in thread From: Ted Dennison @ 2001-12-06 16:40 UTC (permalink / raw) In article <3C0F7B36.52960668@computer.org>, StationSteve says... > >Of course. Er, I mean sorry, I guess I should have said that I was looking >for a *practical* tool that could *productively* address a *real world* >problem! ;-) > >Ted Dennison wrote: >> Ah. So we aren't looking for something that can handle any old program >> (which it still seems to be would be reducable to the Halting Problem), but >> rather one that can handle programs that fit certian restrictions. :-) For that to be accurate though, you'd have to be able to say that all programs that don't fit within the restrictions are not "real world" programs for some reason. That could be the case I suppose. However, I'd bet quite a few "real world" programs wouldn't meet all the restrictions in any such existing tool. Certianly "No recursion" and "no loops with a dynamicly determined amount of iterations" (which is what Stuart said) would take out a great deal of the "real world" code I have seen. For instance, just about anything that handles terminated I/O would be out. A lot of dynamic data structure code would be out too. I could easily see where a hard realtime app might want to measure the worst-case execution time of a list traversal (eg: the scheduler's list of scheduled tasks). It'd be a pretty darn smart tool if it could handle that, no matter how the list is implemented. --- T.E.D. homepage - http://www.telepath.com/dennison/Ted/TED.html No trees were killed in the sending of this message. However a large number of electrons were terribly inconvenienced. ^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: Worst Case Execution Time Tool? 2001-12-06 16:40 ` Ted Dennison @ 2001-12-06 21:27 ` StationSteve 2001-12-06 22:44 ` Ted Dennison 0 siblings, 1 reply; 13+ messages in thread From: StationSteve @ 2001-12-06 21:27 UTC (permalink / raw) Ok, do you have time to educate me a little bit? Why would a tool have to be "pretty darn smart" to measure the worst-case execution time of a list traversal? What's the big driver in making such a thing hard to do? How hard are we talking? Ph.D/New Theory Required hard or Grad Student Thesis hard or Kappa-Key undergrad hard or Lock-the-new-hire-in-the-lab-just-get-it-done hard? Ted Dennison wrote: > In article <3C0F7B36.52960668@computer.org>, StationSteve says... > > > >Of course. Er, I mean sorry, I guess I should have said that I was looking > >for a *practical* tool that could *productively* address a *real world* > >problem! ;-) > > > >Ted Dennison wrote: > >> Ah. So we aren't looking for something that can handle any old program > >> (which it still seems to be would be reducable to the Halting Problem), but > >> rather one that can handle programs that fit certian restrictions. > > :-) > > For that to be accurate though, you'd have to be able to say that all programs > that don't fit within the restrictions are not "real world" programs for some > reason. That could be the case I suppose. However, I'd bet quite a few "real > world" programs wouldn't meet all the restrictions in any such existing tool. > Certianly "No recursion" and "no loops with a dynamicly determined amount of > iterations" (which is what Stuart said) would take out a great deal of the "real > world" code I have seen. > > For instance, just about anything that handles terminated I/O would be out. A > lot of dynamic data structure code would be out too. I could easily see where a > hard realtime app might want to measure the worst-case execution time of a list > traversal (eg: the scheduler's list of scheduled tasks). It'd be a pretty darn > smart tool if it could handle that, no matter how the list is implemented. > > --- > T.E.D. homepage - http://www.telepath.com/dennison/Ted/TED.html > > No trees were killed in the sending of this message. > However a large number of electrons were terribly inconvenienced. ^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: Worst Case Execution Time Tool? 2001-12-06 21:27 ` StationSteve @ 2001-12-06 22:44 ` Ted Dennison 2001-12-07 1:00 ` annonymous 0 siblings, 1 reply; 13+ messages in thread From: Ted Dennison @ 2001-12-06 22:44 UTC (permalink / raw) In article <3C0FE2DE.4BD905B9@computer.org>, StationSteve says... > >Ok, do you have time to educate me a little bit? >Why would a tool have to be "pretty darn smart" to measure the worst-case >execution time of a list traversal? What's the big driver in making such a >thing hard to do? Well, if its a dynamicly allocated list, then theoreticly the "worst case" would be the amount of time it takes to iterate through n/j items, where n is the amount of free memory you have after your program loads and j is the amount of bytes per list item. :-) In most cases there is a smaller "worst case" available, but you have to know a fair bit about the system to know what it is. For my real-time scheduler example, it could be that the list is implemented in an array with a hard limit of 40 items, and it wouldn't be too horribly dificult for a code analyzer to figure that out (although not trivial). On the other hand, it could be that the limit is the number of items listed in a configuration file that is read in at runtime. There's no possible way a tool could figure that out, because it isn't really set at all. --- T.E.D. homepage - http://www.telepath.com/dennison/Ted/TED.html No trees were killed in the sending of this message. However a large number of electrons were terribly inconvenienced. ^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: Worst Case Execution Time Tool? 2001-12-06 22:44 ` Ted Dennison @ 2001-12-07 1:00 ` annonymous 0 siblings, 0 replies; 13+ messages in thread From: annonymous @ 2001-12-07 1:00 UTC (permalink / raw) Ted writes: > In most cases there is a smaller "worst case" available, but you have to know a > fair bit about the system to know what it is. For my real-time scheduler > example, it could be that the list is implemented in an array with a hard limit > of 40 items, and it wouldn't be too horribly dificult for a code analyzer to > figure that out (although not trivial). On the other hand, it could be that the > limit is the number of items listed in a configuration file that is read in at > runtime. There's no possible way a tool could figure that out, because it isn't > really set at all. There are many cases where it may be necessary to supply guidance to the timing tools in the form of annotations. As long as the tool can identify these or they are easy to spot by huge variations between measured and theoretical times it is usually not difficult for the systems engineer to supply the constraints needed to do WCET analysis. The tool needs to be able to accept this information information in the some form that can be correlated with the program (usually specialized comments). -Tom ^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: Worst Case Execution Time Tool? 2001-12-04 22:51 Worst Case Execution Time Tool? StationSteve 2001-12-05 0:10 ` Ted Dennison @ 2001-12-05 10:00 ` Rod Chapman 2001-12-05 14:54 ` StationSteve 1 sibling, 1 reply; 13+ messages in thread From: Rod Chapman @ 2001-12-05 10:00 UTC (permalink / raw) StationSteve <Steven.Suchting@computer.org> wrote in message news:<3C0D536C.2E059EE8@computer.org>... > Are there any tools that quantitatively determine the worst case > execution time (WCET) of an Ada83 program or subprogram? Execution > platform is Intel 80386SX bare machine. I think I'm looking for > something similar to SPARK Examiner's WCET analysis, but for Ada83. > > Thanks in advance for any help... Now here's a blast from the past... :-) I developed the SPATS toolset as part of my DPhil work - it was a static WCET tool for SPARK targetting 68020. It was very much a "research prototype" (i.e. total hack) and so never saw the light of day. York Software Engineering Ltd then went on to develop a tool called STAMP that incorporated some of the ideas from SPATS. As far as I know, STAMP remains the only commercially available static WCET tool. It has been ported to analyse 68020 and PPC 603e object code - no 386SX I'm afraid... There is no "offical" SPARK WCET tool, or (currently) any support for it in the Examiner, other than the inherent analysability of the language in the first place. We have the annotations and analysis all worked out, but the funding (either internal or external) to make it a reality has never materialized - it's just not a priority for our customers I'm afraid. - Rod ^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: Worst Case Execution Time Tool? 2001-12-05 10:00 ` Rod Chapman @ 2001-12-05 14:54 ` StationSteve 2001-12-05 15:31 ` Jeffrey L. Susanj 2001-12-05 17:32 ` Stuart Palin 0 siblings, 2 replies; 13+ messages in thread From: StationSteve @ 2001-12-05 14:54 UTC (permalink / raw) Oh, I guess I read the SPARK-Examiner web page wrong: http://www.sparkada.com/examiner.html I thought because the following words were on the SPARK-Examiner page, that Examiner could actually DO WCET analysis of a SPARK program: The Examiner checks conformance of a SPARK source text to the rules of SPARK by performing the following analyses. ... other bullets here ... Worst-Case Execution Time Analysis The static analysis of program execution time requires analysis of program source text, object code, and user-supplied annotations. The latter supply information that cannot be determined automatically, such as a bound on the number of iterations made by each looping statement. By combining the control-flow graph for each subprogram, the program's call-tree, and the worst-case execution time for each object code fragment, the worst-case execution time (WCET) of a subprogram can be determined. Such analysis has several uses: - Potential timing problems can be found earlier than usual, and thus can be corrected more cheaply and effectively. - Watchdog timers can be set to monitor and control the execution of time-critical code. The program path that leads to WCET can be identified and tested with confidence. ... Guess the marketing guys got tricky again, eh? ;-) So how (or do?) people typically PROVE that their program will actually meet their deadlines? If somebody does a rate monotonic design, they have to assume the execution time of task. How does one determine the true execution time so that the design can be shown to be correct? Thanks again... Rod Chapman wrote: > StationSteve <Steven.Suchting@computer.org> wrote in message news:<3C0D536C.2E059EE8@computer.org>... > > Are there any tools that quantitatively determine the worst case > > execution time (WCET) of an Ada83 program or subprogram? Execution > > platform is Intel 80386SX bare machine. I think I'm looking for > > something similar to SPARK Examiner's WCET analysis, but for Ada83. > > > > Thanks in advance for any help... > > Now here's a blast from the past... :-) > > I developed the SPATS toolset as part of my DPhil work - it was a > static WCET tool for SPARK targetting 68020. It was very much a > "research prototype" (i.e. total hack) and so never saw the light > of day. > > York Software Engineering Ltd then went on to develop a tool > called STAMP that incorporated some of the ideas from SPATS. As far > as I know, STAMP remains the only commercially available static WCET tool. > It has been ported to analyse 68020 and PPC 603e object code - no > 386SX I'm afraid... > > There is no "offical" SPARK WCET tool, or (currently) any support > for it in the Examiner, other than the inherent analysability of the > language in the first place. We have the annotations and analysis > all worked out, but the funding (either internal or external) to > make it a reality has never materialized - it's just not a priority > for our customers I'm afraid. > > - Rod ^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: Worst Case Execution Time Tool? 2001-12-05 14:54 ` StationSteve @ 2001-12-05 15:31 ` Jeffrey L. Susanj 2001-12-05 17:32 ` Stuart Palin 1 sibling, 0 replies; 13+ messages in thread From: Jeffrey L. Susanj @ 2001-12-05 15:31 UTC (permalink / raw) What we have always done is select a scenario that looks like it would produce the worst case time and run the software on the bench. The executive can capture the time the frame ends. Not very elegant and not very rigorous but it gives us a warm fuzzy feeling. Jeff S. "StationSteve" <Steven.Suchting@computer.org> wrote in message news:3C0E3535.58437022@computer.org... > ... > > Guess the marketing guys got tricky again, eh? ;-) > > So how (or do?) people typically PROVE that their program will actually meet their deadlines? If > somebody does a rate monotonic design, they have to assume the execution time of task. How does one > determine the true execution time so that the design can be shown to be correct? > > Thanks again... > > Rod Chapman wrote: > ^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: Worst Case Execution Time Tool? 2001-12-05 14:54 ` StationSteve 2001-12-05 15:31 ` Jeffrey L. Susanj @ 2001-12-05 17:32 ` Stuart Palin 1 sibling, 0 replies; 13+ messages in thread From: Stuart Palin @ 2001-12-05 17:32 UTC (permalink / raw) StationSteve wrote: <snip> > So how (or do?) people typically PROVE that their program will actually meet their deadlines? If > somebody does a rate monotonic design, they have to assume the execution time of task. How does one > determine the true execution time so that the design can be shown to be correct? On several projects we have used [in-house] WCET tools, our most recent being for a MC68020/MC68882 target with code generated by the XD-Ada compiler. Unfortunately this does not help you (not a commercially available tool and not '386). -- Stuart Palin Principal Software Engineer BAE SYSTEMS Avionics Ltd, Rochester G-NET 791 3364 mailto:stuart.palin@baesystems.com ^ permalink raw reply [flat|nested] 13+ messages in thread
end of thread, other threads:[~2001-12-07 1:00 UTC | newest] Thread overview: 13+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2001-12-04 22:51 Worst Case Execution Time Tool? StationSteve 2001-12-05 0:10 ` Ted Dennison 2001-12-05 17:28 ` Stuart Palin 2001-12-05 18:33 ` Ted Dennison 2001-12-06 14:05 ` StationSteve 2001-12-06 16:40 ` Ted Dennison 2001-12-06 21:27 ` StationSteve 2001-12-06 22:44 ` Ted Dennison 2001-12-07 1:00 ` annonymous 2001-12-05 10:00 ` Rod Chapman 2001-12-05 14:54 ` StationSteve 2001-12-05 15:31 ` Jeffrey L. Susanj 2001-12-05 17:32 ` Stuart Palin
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox