A reference string sampling method with dynamically changing parameters

Wittneben proposed a technique which determines the structural characteristics of a program's memory referencing behavior based only on a sampling of the complete reference string. This method controls the cost of the measurement by adjusting the sampling rate while simultaneously attempting to determine accurately the referencing behavior as reflected in its working set measurements. Wittneben's method is controlled by parameters with statically determined values. The aim of this paper is to present a modified sampling method in which sampling parameters are updated dynamically according to the actual program referencing behavior. The updating process is controlled by the phase-transition structure of a program. Furthermore, working set measurements of the program are based on modified principles which take into account the most probable sources of errors made during the sampling process. Experiments conducted with synthetic and real reference strings seem to demonstrate the superiority of the modified method in comparison with the technique originally formulated by Wittneben.     

Characterizing and reproducing working set size dynamics

A characterization of program referencing dynamics based on the temporal behavior of memory demand (as represented by the working set size of a program for a given window size) is proposed. A deterministic generative model which produces a references string having a given dynamic characterization is then presented, and its practical implementation is discussed. An experimental study of the accuracy and the viability of such a model is performed, together with a theoretical and empirical investigation of the feasibility of constructing a synthetic program which produces an approximation to that artificial string, thereby exhibiting the given dynamic behavior. The results for working-set-like environments with window sizes larger than or equal to that used in the generation of the artificial string are satisfactory, but those for other types of memory policies reveal that improvements to the string generation algorithm or different characterizations are needed.     

Strategy independent program restructuring using the critical reference principle

This paper defines and analyzes two new strategy independent program restructuring algorithms. The more effective of these two algorithms combines the critical reference principle used in strategy dependent algorithms with the bounded locality interval mechanism. Limited, though encouraging, results are presented which show that this new algorithm can be at least as effective as the Critical LRU algorithm, even when the memory management policy is LRU itself, and can also be at least as effective as Critical Working Set, even when the memory management policy is the working set policy. This new algorithm combines the benefits of strategy independent restructuring with the performance improvements previously possible only with a strategy dependent method.     

Efficient calculation of the space-time performance of the working set

The performance of working set memory management is often used as a benchmark against which other algorithms are compared. Efficient algorithms which can generate exact performance curves for the mean working set size and fault rate have appeared in the literature. These algorithms exploit the fact that the curve of fault rate or mean resident set size versus the working set parameter value may be computed by gathering various statistics during one pass across the reference string and then by substituting those statistics into relatively simple formulae.

This paper develops an efficient technique for the determination of the exact space time product versus parameter value curve. The usual simulation approach to compute a space-time performance curve exhibits worst case time complexity of O(nn²) where p is the number of pages referenced by the program and n is the total number of memory references generated by the program. The one-pass technique presented here requires O(pn) time. Given that n may be quite large in practice (10⁷ references is not unusual), this reduction in complexity is necessary for the practical determination of space-time performance of the working set.     

An analytical study of strategy-oriented restructuring algorithms

Considerable experimental evidence has been accumulated showing that the performance of programs in virtual memory environments can be significantly improved by restructuring the programs, i.e., by modifying their block-to-page or block-to-segment mapping. This evidence also points out that the so-called strategy-oriented algorithms, which base their decisions on the knowledge of the memory management strategy under which the program will run, are more efficient than those algorithms which do not take this strategy into account.We present here some theoretical arguments to explain why strategy-oriented algorithms perform better than other program restructuring algorithms and determine the conditions under with these algorithms are optimum. In particular, we prove that the algorithms oriented towards the working set or sampled working set policy are optimum when applied to programs having no more than two blocks per page, and that, when this restriction is removed, they minimize both upper and lower bounds of the performance index they consider as the figure of merit to be reduced. We also prove that the restructuring algorithms aimed at reducing the page fault rate of programs to be run under such policies as LRU, Global LRU and PFF (the Page Fault Frequency policy) minimize an upper bound of the page fault rate, and we extend some of our results to some non-strategy-oriented algorithms. Throughout the paper, the only assumption about program behavior is that it can be accurately modeled as a stationary discrete-state stochastic process.     

Improving page prefetching with prior knowledge

Prefetching is a technique applied to memory management policies in which pages are brought into memory before they are actually needed. In this study, prior knowledge of program behavior obtained through trace data is used to parameterize a variation of the working set memory management policy supporting demand page prefetching using one page lookahead. Two new algorithms supporting double page prefetching are proposed. A comparative analysis of them is made.Evaluation of the techniques through trace driven simulation shows that, in general, they are very effective in reducing the page fault rate and in some cases the space time product. As expected, memory occupancy increases, but usually by small amounts. The results are encouraging for their ability to improve performance for a variety of programs which exhibit some form of locality (spatial and/or temporal).