The validity of a Markov model of the behaviour of programs

In light of the evidence presented, the modified model has been shown to be valid. However, as with any other validation using test cases, the results cannot be considered a truly formal or general proof of its correctness. However they provide grounds for future work attempting to apply the model, which leads to a series of proposals for future endeavours.

Rauscher [1] intended that modelling processors be made an integral part of optimizers in translator systems dynamically microprogrammable machines. This is slightly more difficult to achieve automatically with the modified model than with the original one, since DO blocks and termination code must be recognized by the processor, however it is still very feasible. This shows that one useful investigation would be to search for other easily recognizable structures which may be used to reduce the range of transition probabilities generated for the model, thus further improving its accuracy.

The modelling process takes a good deal of computing time, so that decreasing the number of sample probability sets generated could tremendously increase the efficiency of the model processor itself with respect to execution time of the optimizer. Further statistical tests should be devised to determine the number of samples necessary for an accurate result.

Finally, the model at a stage where techniques should be developed for using it in applications such as optimization by dynamic microprogramming (1], data flow analysis for debugging [21J, and storage allocation in operating systems using paging. For all of these applications, knowledge of the relative frequency of code blocks is not enough, other information must be attached to the states of the model before it may applied to the problem. When dealing with the optimization of execution me, the execution time of the code in each block is needed. For data flow analysis and storage allocation purposes, a table of the variables used in each block and their attributes is necessary.

All of this makes the author feel that there is still much work to be done with this Markov Model of Program Behaviour.