Towards Effective Generation of Synthetic Memory References Via Markovian Models

Trace-driven simulation is a popular technique useful in many applications, as for example analysis of memory hierarchies or internet subsystems, and to evaluate the performance of computer systems. Normally, traces should be gathered from really working systems. However, real traces require enormous memory space and time. An alternative is to generate Synthetic traces using suitable algorithms. In this paper we describe an algorithm for the synthetic generation of memory references which behave as those generated by given running programs. Our approach is based on a novel Machine Learning algorithm we called Hierarchical Hidden/non Hidden Markov Model (HHnHMM). Short chunks of memory references from a running program are classified as Sequential, Periodic, Random, Jump or Other. Such execution classes are used to train an HHnHMM for that program. Trained HHnHMM are used as stochastic generators of memory reference addresses. In this way we can generate in real time memory reference streams of any length, wich mimic the behaviour of given programs without the need to store anything. It is worth noting that our approach can be extended to other applications, for example network or data storage systems. In this paper we address only the generation of synthetic memory references generated by instruction fetches. Experimental results and a case study conclude this paper.