Back to Search
Start Over
One Way of Estimating Frequencies of Jumps in a Program.
- Source :
- Communications of the ACM; Jul1968, Vol. 11 Issue 7, p475-480, 6p, 5 Diagrams
- Publication Year :
- 1968
-
Abstract
- For the segmentation of a program it is useful to have a reasonable estimation of the values of S<subscript>ij</subscript>, where S<subscript>ij</subscript> is the mean value of the number of jumps from the ith instruction on to the ith instruction in the run time. In the cases where the S<subscript>ij</subscript>, are estimated directly, the structure of the whole program must be generally taken into account; therefore it is very difficult for the programmer and/or the translator to obtain a good estimation of the S<subscript>ij</subscript>. It is easier to estimate not S<subscript>ij</subscript>, but the quantities p<subscript>ij</subscript> = S<subscript>ij</subscript>·c<subscript>i</subscript>,/∑<subscript>j</subscript><superscript>N</superscript>=1 S<subscript>ij</subscript>, where c, is an arbitrary positive constant for each i. Although the p<subscript>ij</subscript> are, for each i, proportional to S<subscript>ij</subscript>, the estimation of p<subscript>ij</subscript> is easier, because we must estimate only the "probabilities" of events where instruction l<subscript>j</subscript>, is executed after instruction l<subscript>i</subscript>. This estimation can often be done without considering the structure of the whole program. In the first part of the paper, using the theory of the Markov chains, an algorithm for the computation of the S<subscript>ij</subscript> from the p , is found, and some ways of obtaining estimates of the p<subscript>ij</subscript> are given. In the second part a variant of this algorithm is derived, avoiding the necessity of computation involving large matrices. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 00010782
- Volume :
- 11
- Issue :
- 7
- Database :
- Complementary Index
- Journal :
- Communications of the ACM
- Publication Type :
- Periodical
- Accession number :
- 5263698
- Full Text :
- https://doi.org/10.1145/363397.363400