The Framework for Study of Caching Algorithm Efficiency. © Thanh Hung Ngo Mosab Bassam Y. Al Zgool Don State Technical University Don State Technical University nthungla@yahoo.com mosab2000@yahoo.com PhD supervisor: Michael V. Grankov Abstract. is the development of mathematical model, describing the information system. In this paper we offer several models of In this paper we offer several models of reference reference sequences (traces of references) using sequences using Markov chains [5]. Besides, we offer Markov chains for testing of the replacement the scheme of the program stand, where these models policies in caching systems. These models have been realized, and the result of the experiments, enable the generations of traces with the which have been carried out with its help. repeated subsequences of references, which are of great interest for study of forecasting 2 Models of reference sequences methods in caching systems. Furthermore, we offer the scheme of the program stand, where 2.1 Model with One Markov Chain (MOMC) these models have been realized, and result of the experiments, which have been carried out The model is widely used for modeling of different with its help. queuing systems, including caching system. MOMC is Index terms: program stand, model of reference π specified by the triple (S , A , ) , where: 1. S = {s 1 , s 2 , … , s N } - the set of N objects in sequences, Markov chains, traces with repeated subsequences. the system. Objects may be the papers in paper caching systems or the objects in the object caching systems; 1 Introduction { } 2. A = a ij - the object transition probabilities. The value of element aij of matrix equals to the The most popular method to study the replacement policies in caching systems is its testing by the program probability of event, when the system, having accessed simulating caching system. In this approach different the object s i , accesses the object s j . If mark the traces are given to the input of the program and the object having been accessed at the moment t as qt , cache-hit rate is registered as the result provided cache- system. The more the value of this rate is, the more then: efficient the investigated policy performs. ( ) a ij = P q t +1 = s j | q t = s i , Specific characters of the functioning of the N information system often render a big influence upon a ij ≥ 0 , ∑ a ij = 1, 1 ≤ i , j ≤ N ; behavior of the reference sequences. So testing the j =1 policy, have been specially designed for a certain 3. π = (π 1 , π 2 , … , π N ) - the initial object information system, requires the traces, reflecting distribution. specifics of the system. There are two ways of achieving The generation of traces by MOMC follows the the reference sequences: by means of logging the algorithm: 1. Input S , A , π . accesses being executed in the system for a long-lasting time (e.g. collecting reference sequences) [1, 2] and by means of trace generating programs [3, 4]. The traces 2. Input the count of references L (length of trace). having been achieved using the first method more really 3. Initialize value for the variable O , which is the reflect the specifics of the system, but their achievement string logging the references to the object, as an empty requires a significant computing and material resources. string. The achievement of traces using program-generator is 4. Initialize value for the variable t , which is the faster and cheaper. The main problem of the last method current count of references: t = 1. 5. Choose the initial object qt from the set S according to the initial object distribution π . Proceedings of the Spring Young Researcher's Colloquium On Database and Information Systems SYRCoDIS, St.-Petersburg, Russia, 2008 6. WHILE t ≤ L 7. Let qt = s k , append s k to the string O : (2, 3, 1, 2, 2, 3, 1, 4, 3, 1, 4, 2, 4, 1, 4). O = O + sk . i\j 1 2 3 4 8. Choose the next object according to the matrix 1 0.043 0.043 0.043 0.871 of object transition probabilities A and the current 2 0.043 0.043 0.871 0.043 object s k . 3 0.871 0.043 0.043 0.043 9. Increase the value of the current count of 4 0.043 0.871 0.043 0.043 references t by one: Table 2: matrix of cyclic transitions with random t = t +1 . “noise”. 10. END-WHILE. Because of one’s simplicity the MOMC is not able 11. Save the achieved reference string O as the to describe the functioning principles of the real desired trace. systems. To specify the more complicated mechanisms Special occasions of implementing MOMC. Let’s it is used the hidden Markov model. consider the following realizations of MOMC: 1 1. a ij = , ∀i, j : 1 ≤ i , j ≤ N . 2.2 Model with Hidden Markov Chain (MHMC) N MHMC is specified by the quintuple (S , V , A , B , π ) , In this case we achieve the model describing the where: system where the accesses to the objects obey the uniform law. 1. S = {s1 , s 2 , … , sU } - the set from U users of 2. The absolute cyclic traces (ACT). the information system; Generation of the ACT is made by picking up the matrix of transition probabilities as in table 1. { } 2. A = a ij - the user transition probabilities. If mark the user, which has got access to the system at the i\j 1 2 3 4 moment t , by qt , then: 1 0 0 0 1 2 0 0 1 0 ( a ij = P q t +1 = s j | q t = s i ), 3 1 0 0 0 U 4 0 1 0 0 a ij ≥ 0 , ∑ a = 1, 1 ≤ i , j ≤ U ; j =1 ij Table 1: matrix of cyclic transitions. 3. V = {v 1 , v 2 , … , v N } - the set from N objects A fragment of ACT, achieved by using the matrix of the system; in table 1, looks like: …, 2, 3, 1, 4, 2, 3, 1, 4, …. The ACT is of interest to study the anomalies { } 4. B = b ij - probabilities of choosing object for such as Belady’s anomaly. the users. The i -th row is the object choice probability 3. The cyclic traces with random “noise” (CTRN). distribution for the i -th user. The value of element bij Replacements of one or more unit element (the equals to the probability of event, when the current user element with value equaling to 1) of matrix in q t = s i chooses the object v j . If mark this object as ot , table 1 by the value e −λx , and zero elements in then: the corresponding rows by the value (( ) ) 1 − e − λx / (N − 1) result in inclusion of a random ( b ij = P o t = v j | q t = s i ), N ln(N ) bij ≥ 0 , ∑ b = 1, 1 ≤ i ≤ U , 1 ≤ j ≤ N ; “noise” in cyclic traces ( 0 ≤ x ≤ and ij λ j =1 0 < λ ). When x = 0 , we achieve the ACT as in 5. π = (π 1 , π 2 , … , π N ) - the initial user occasion 2. Increasing the value of x , the distribution. indeterminacy in behavior of traces increase. The generation of traces by MHMC follows the ln (N ) algorithm: When x = 1. Input S , V , A , B , π . , we achieve the traces, in λ which references to the objects obey the uniform 2. Input the count of references L (length of trace). law (as in occasion 1). Thus the first and the 3. Initialize value for the variable O , which is the second occasions are just the special cases of the string logging the references to the object, as an empty third occasion. string. For example we have brought into the matrix in 4. Initialize value for the variable t , which is the table 1 the noise with the following parameters current count of references: t = 1 . (λ = 7, x = 0.0198) and have generated traces 5. Choose the initial user qt from the set S with its help. The matrix of transition according to the initial user distribution π . probabilities now looks like in table 2. Some of 6. WHILE t ≤ L generated traces are as follow: 7. Let qt = s k . (1, 4, 2, 3, 4, 2, 3, 4, 4, 2, 3, 1, 4, 2, 4); 8. Choose the current object ot according to the π k ( = π 1k , π 2k , … , π kN ) - the initial object matrix B and the current user s k . distribution for the k -th user. 1 ≤ k ≤ U . 9. Let ot = vl , append vl to the string O : The generation of traces by MHMC follows the O = O + vl . algorithm: 10. Choose the next user according to the matrix of 1. Input: S , V , AS , A 1 , A 2 , … , A U , and user transition probabilities A and the current user s k . π , π , π , …, π . S 1 2 U 11. Increase the value of the current count of 2. Input the count of references L (length of trace). references t by one: t = t + 1 . 3. Initialize value for the variable O , which is the 12. END-WHILE. string logging the references to the object, as an empty 13. Save the achieved reference string O as the string. desired trace. 4. Initialize value for the variable l , which is the The second model more naturally reflects the current count of references: l = 1 . relationship between the elements of the information 5. Initialize value for the variable t , which is the system: each user accesses to the objects due to his logic (his distribution law). count of the user turns: t = 1 . Both of the described models have disadvantages. 6. Choose the initial user qt from the set S The first one is not taken into account the presence of according to the initial user distribution π S . the users, and the second one is not able to model the 7. WHILE l ≤ L cyclic traces. For elimination of these restrictions we offer the two-level model of Markov chains. 8. Let qt = s k . 9. Initialize value for the variable r , which is 2.3 Two-Level Model of Markov Chains (TLMMC) the session count of references for the current user: r = 1 . TLMMC is specified by the six 10. Choose the initial object o r according to the (S , V , A S , AV , π , π ) , where: S V distribution π k . 1. S = {s 1 , s 2 , … , s U } - the set from U users of 11. Generate the number z , which is the count of references will be made by the current the information system; user. 2. V = {v 1 , v 2 , … , v N } - the set from N objects 12. WHILE (l ≤ L ) and (r ≤ z ) of the system; Let o r = v m , append v m to reference { } 13. 3. A S = a ij - the user transition probabilities. If string: O = O + v m . mark the user, which has got access to the system at the 14. Increase the value of l by one: moment t , by qt , then: l = l +1. ( a ij = P q t +1 = s j | q t = s i ), 15. Choose the next object o r +1 according U to the matrix A k and the current a ij ≥ 0 , ∑ a = 1, 1 ≤ i , j ≤ U ; j =1 ij object o r . ( 4. AV = A , A , … , A U - matrix of object 1 2 ) 16. Increase the value of r by one: r = r +1. transition probabilities for the users, where: { } 17. END-WHILE A k = a ijk - matrix of object transition 18. Choose the next user qt +1 according to probabilities for the k -th user. Value of the element a kij matrix AS and the current user qt = s k . 19. Increase the value of t by one: t = t + 1 . equals to the probability of event, when the k -th user, 20. END-WHILE. having chosen the i -th object, chooses the j -th object. 21. Save the achieved reference string O as the If mark the object, being chosen by the k -th user at his desired trace. r -th choice, as o r , then Let’s consider an example illustrating the usage of ( a ijk = P o r +1 = v j | ((o r = v i ) ∧ (q t = s k )) , ) TLMMC. Set value for the parameters of TLMMC as below: S = {1, 2}; V = {1, 2 , 3 , 4}; π = (0 .5 , 0 .5 ); N a ijk ≥ 0 , ∑ a ijk = 1, 1 ≤ i , j ≤ N , 1 ≤ k ≤ U ; S j =1 π = (0 .5 , 0 .5, 0 .5 , 0 .5 ); π = (0 .5, 0 .5 , 0 .5 , 0 .5 ); 1 5. π S = (π1 , π 2 , … , π U ) - the initial user 2 distribution; 6. π V = 1 (π π π ) , 2 , … , U - the initial object distributions for the users, where: ⎛0 0 0 1⎞ ⎛ .5 .5 ⎞ ⎜ ⎟ AS = ⎜⎜ ⎟⎟ ; ⎛ 0. 5 0 .5 ⎞ ⎜0 0 1 0⎟ ⎝ .5 .5 ⎠ AS = ⎜⎜ ⎟⎟; A = ⎜ 1 ; ⎝ 0.5 0.5 ⎠ 1 0 0 0⎟ Matrix A1 is specified as matrix of cyclic traces ⎜ ⎟ ⎜0 1 0 0 ⎟⎠ with a random “noise” (looks like the matrix in tab. 2). ⎝ When x = 0 the absolute cyclic trace, being generated ⎛ 0.25 0.25 0.25 0.25 ⎞ ⎜ ⎟ according to this matrix, looks like: ⎜ 0.25 0.25 0.25 0.25 ⎟ A =⎜ 2 ⎛1,2,3,4 ,87 ,35,7 ,99,9 ,76 ,13,12 ,11,14,15,34 ,78, ⎞ 0.25 0.25 0.25 0.25 ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ 0.25 0.25 0.25 0.25 ⎟ ⎜ 30 ,74 ,20 ,29 ,5,23,64 ,80 ,100 ,79,28,21,53,6,26 ,⎟ ⎝ ⎠ ⎜ 33,32 ,44 ,17 ,81,65,51,73,41,42 ,43,31,48,46 , ⎟ One of the traces achieved with help of the model ⎜ ⎟ looks like: 4, 2, 3, 1, 3, 1, 4, 2, 4, 2, 3, 1, 1, 2, 2, 3, 1, 4, ⎜ 47 ,22,49,45,96 ,52 ,18,54 ,55,94,19 ,60,90 ,25, ⎟ 1, 1, 2, 3, 1, 4, 2, 1, 4, 2. In this trace the absolute cyclic ⎜ ⎟ ⎜ 92 ,62 ,16 ,24 ,40 ,63,67 ,68,69 ,75,71,72 ,56,61, ⎟ trace (…, 1, 4, 2, 3, 1, 4, 2, 3, …) has been distorted and ⎜ 70,10 ,77 ,86 ,38,58,37 ,82 ,83,84,27 ,36 ,50,88, ⎟ fragmented into subsequences due to the random turns ⎜⎜ ⎟⎟ of the users and the random number of references ⎝ 89 ,59 ,57 ,91,93,39 ,95,85,97 ,98,8,66 ⎠ having been made in their turns. These distortions create Matrix A 2 determines for the second user the more difficulties for the methods identifying the equiprobable transition from an object to any objects, subsequences in the references sequence. So the model including the transition to it self, i.e. TLMMC is of great interest to investigate the prediction methods in caching system [6, 7]. a ij = 1 / 100, ∀i , j : 1 ≤ i , j ≤ 100 . 2 As magnitude of the “noise” coefficient it has been 3 The scheme of program stand used three values: x = 0 ; x = 0.1054 and x = 4.6052 . In all cases λ = 1 . When x = 0 , in generated traces The program stand has been written in programming present the repeated subsequences. This fact has environment Delphi 7. It has following components (fig. negatively influenced upon performance of Random and 1): LRU, but not for LFU. In this case it is registered the 1. Trace - generator. slight advantage of Random over LRU and significant Generate traces by the one of different models. advantage of LFU over the rest. Increasing the 2. Realization block of replacement policies. magnitude of x , the indeterminacy in generation of the 3. Cache simulator. Simulate the performance of cache-system with the traces rapidly increases. This change positively chosen policy and chosen traces model. influences upon performance of Random and LRU, and 4. Analysis block equalizes the performance of all policies. Analyze the result of performance of cache-system. Figure 1: The components of the program stand. 4 Experiments Functioning of the program stand has been illustrated by benchmark analysis of performance of different replacement policies: Random, LRU and LFU. The result of the experiment is showed in fig. 2. Figure 2: Experiment result. In the investigation it has been used the model TLMMC with the following parameters: 5 Conclusions S = {1, 2 }; V = {1, 2 , … , 100 }; π S = (. 5 , . 5 ); The result of the demonstration experiment shows π = (.01 , .01 , … , .01 ); π = (.01 , .01 , … , .01 ); 1 2 urgency and relevance of the offered traces models and also program stand for study of different replacement policies. The TLMMC presents a great interest to study the forecasting method in cache-system. The traces Software, 2000. ISPASS. IEEE International generated by this model were applied to testing the Symposium on Volume, Issue, 2000. decomposition method of the relations in database [4] Germán Galeano Gil, Juan A. Gómez Pulido, and systems with the criteria of increasing the cache-hit rate Juan M. Sánchez Pérez. Tool for the Analysis and [8]. Herein, when the magnitude of x reaches its Memory-Trace Generation of DOS Executable maximum value, the experimental cache-hit rate Files. // Microprocessors and Microsystems, completely agrees with the corresponding rate Volume 22, Issue 7, 25 January 1999, Pages 389- theoretically has been achieved in that paper. 393. [5] Lawrence R. Rabiner. A tutorial on Hidden Markov References Models and selected applications in speech recognition. // Proceedings of the IEEE, VOL. 77, [1] Min Xu, Vyacheslav Malyugin, Jeffrey Sheldon, NO. 2, Feb 1989. Ganesh Venkitachalam, Boris Weissman. ReTrace: [6] Fei Guo and Yan Solihin. A Prediction Model for Collecting Execution Trace with Virtual Machine Alternative Cache Replacement Policies. // Deterministic Replay. // Third Annual Workshop http://www.ece.ncsu.edu on Modeling, Benchmarking and Simulation, held [7] Thomas M. Kroeger, Darrell D. E. Long. Predicting in conjunction with the 34th Annual International File System Actions from Prior Events. // Symposium on Computer Architecture, June 2007. Proceedings of the USENIX 1996 Annual http://www.xhfamily.com/x/files/MoBS07_replay_i Technical Conference, pages 319-328, January trace.pdf 1996. [2] Hervé Touati, Alan Jay Smith. Reducing and http://citeseer.ist.psu.edu/kroeger96predicting.html Manipulating Complex Trace Data. // Software - [8] Thanh Hung Ngo, Michael V. Grankov. New Practice and Experience. Vol. 21, June 1991, 639– Object Function for Vertical Partitioning in 655. Database System. // the present colloquium. [3] Eeckhout L., De Bosschere K., Neefs H. Performance analysis through synthetic trace generation. // Performance Analysis of Systems and