Next: Example: TCP Retransmission Up: No Title Previous: Introduction

Frequency Prediction using Markov Analysis

In the general case, the exact number of times a certain part in a program is executed can be determined once the probability of taking each branch in the program is known [Knu73]. This observation has lead to the idea of applying the Markov analysis technique to the flow graph of a program ([Ram65], [Tri82], [Wag94]).

A program flow graph consists of a set of nodes called basic blocks that are connected by arcs referred to as branches [Aho86]. When using Markov analysis, the flow graph of a program is mapped onto a finite Markov chain. Each basic block in the flow graph corresponds to a state of the Markov chain, and each branch corresponds to a transition of the Markov chain. The probability of taking a branch is then equivalent to the transition probability of the corresponding transition in the Markov chain.

Let be the number of basic blocks in the flow graph, and let be the probability that control passes from basic block to basic block . It can be shown [Tri82] that the number of times that each of the basic block is visited can be calculated by solving the following system of linear equations: where for i=j, and otherwise.
Wed Aug 9 15:22:05 MET DST 1995