Analysis of computational systems: Discrete Markov analysis of computer programs

ABSTRACT

A PROGRAM with a number of subroutines can be represented by a flow diagram; Figure 1. The nodes represent the subroutines and the directed branches indicate the allowed transitions between them. Given a program consisting of n subroutines R₁, R₂ .....R_n, two matrices are also assumed to be known, viz., an n × 1 matrix of execution times of each subroutine and a n × n matrix P, such that its ij-th element P_ij is the branching probability that the program will branch to subroutine j from subroutine i. We shall assume P_ij's are statistically independent so that the model of the computer program is that of a discrete Markov process. The expected time to complete a program is then a summation of all possible statistically weighted paths that begin at an initial or starting subroutine and end at the terminal subroutine.

References

1. 1.Mason, S. J., "Further Properties of Flow Graphs," Proc. IRE; July, 1956.
2. 2.Ramamoorthy, C. V., "Representation and Analysis of Discrete Systems by Generating Functions of Astract Graphs," IEEE International Convention Record; 1965.
3. 3.Howard, R. A., "Dynamic Programming and Markov Processes," Wiley; 1960.
4. 4.Feller, W., "An Introduction to Probability Theory and Its Applications," Wiley; 1957.
5. 5.Karp, R., Ph.D. Thesis, Harvard University; 1959.
6. 6.Ramamoorthy, C. V., Ph.D. Thesis, Harvard University; May, 1964.

Index Terms

• Mathematics of computing

  • Discrete mathematics

    • Combinatorics

      • Generating functions

  • Probability and statistics

    • Probabilistic representations

      • Markov networks

    • Stochastic processes

      • Markov processes

• Theory of computation

  • Semantics and reasoning

    • Program reasoning

      • Program analysis

    • Program semantics

  • Theory and algorithms for application domains

    • Machine learning theory

      • Markov decision processes