Download Bound-T User Manual - Bound
Transcript
Nonrectangular loops In some nested loops, the number of repetitions of the inner loop is not constant but depends on the iteration number of the outer loop. For example, here is an Ada loop that traverses the “lower triangle” of a 100 × 100 matrix M: for I in 1 .. 100 loop for J in 1 .. I loop Note the upper bound! Traverse (M(I,J)); end loop; end loop; The outer loop repeats 100 times. The inner loop repeats I times where I is the counter for the outer loop. On the first iteration of the outer loop (I = 1) the inner loop repeats once; on the last iteration of the outer loop (I = 100) the inner loop repeats 100 times. At present, it is not possible assert such a variable bound for the inner loop, nor can BoundT deduce such a variable bound automatically. As a workaround, you can assert an “average” bound on the inner loop such that the total number of repetitions of the inner loop is correct, or close. In this example, when the outer loop is finished the inner loop has been repeated a total of 100 × (100 + 1) / 2 = 5050 times. Thus, the average number of repetitions of the inner loop for each repetition of the outer loop is 5050 / 100 = 50.5. The closest possible assertion is 51 repetitions: loop that is in (loop) repeats 51 times; end loop; This assertion corresponds to a total of 51 × 100 = 5100 repetitions of the inner loop, an overestimation of 50 repetitions compared to the true number of 5050 repetitions. In this example you can remove this overestimation because the inner loop always calls the subprogram Traverse and you can assert the total number of times this call occurs as follows: call to "Traverse" repeats 5050 times; end call; This assertion makes BoundT compute a WCET bound that corresponds to exactly 5050 repetitions of the inner loop. (However, you also have to make the loop assertion unless BoundT bounded the loop automatically.) The next section shows more examples of executioncount assertions for calls. 5.4 Assertions on the Execution Count of Calls Why? An executioncount assertion for a call defines the number of times the call is executed in each execution of the caller. The form of the assertion is “repeats N times” where N is a number or a range of numbers. It is never necessary to assert the execution count of calls, because BoundT can determine a finite WCET bound without such assertions as long as all loops are bounded (automatically or by assertions). However, executioncount assertions on calls can often improve (sharpen) the WCET bound. Without such assertions, the WCET bound may include an unrealistically (infeasibly) large number of some calls, or even some calls that should not be included at all because they represent a scenario that you want to exclude from the analysis. 44 Writing Assertions BoundT User Manual