-
Notifications
You must be signed in to change notification settings - Fork 3
/
README.txt
745 lines (663 loc) · 16 KB
/
README.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
All the swapfile sizes in the simulation are 3000
tracefiles :
/u/csc369h/winter/pub/a2-traces/tr-simpleloop.ref
/u/csc369h/winter/pub/a2-traces/tr-blocked.ref
/u/csc369h/winter/pub/a2-traces/tr-matmul.ref
traceprogs/tr-linkedlisttrace.ref
rand
--------------------------------------------------
tr-simpleloop
--------------------------------------------------
m = 50
Hit count: 7600
Miss count: 2968
Clean evictions: 236
Dirty evictions: 2682
Total references : 10568
Hit rate: 71.9152
Miss rate: 28.0848
m = 100
Hit count: 7823
Miss count: 2745
Clean evictions: 49
Dirty evictions: 2596
Total references : 10568
Hit rate: 74.0254
Miss rate: 25.9746
m = 150
Hit count: 7853
Miss count: 2715
Clean evictions: 14
Dirty evictions: 2551
Total references : 10568
Hit rate: 74.3092
Miss rate: 25.6908
m = 200
Hit count: 7865
Miss count: 2703
Clean evictions: 18
Dirty evictions: 2485
Total references : 10568
Hit rate: 74.4228
Miss rate: 25.5772
--------------------------------------------------
tr-blocked
--------------------------------------------------
m = 50
Hit count: 2516731
Miss count: 8293
Clean evictions: 6890
Dirty evictions: 1353
Total references : 2525024
Hit rate: 99.6716
Miss rate: 0.3284
m = 100
Hit count: 2519796
Miss count: 5228
Clean evictions: 3964
Dirty evictions: 1164
Total references : 2525024
Hit rate: 99.7930
Miss rate: 0.2070
m = 150
Hit count: 2520591
Miss count: 4433
Clean evictions: 3160
Dirty evictions: 1123
Total references : 2525024
Hit rate: 99.8244
Miss rate: 0.1756
m = 200
Hit count: 2521210
Miss count: 3814
Clean evictions: 2507
Dirty evictions: 1107
Total references : 2525024
Hit rate: 99.8490
Miss rate: 0.1510
--------------------------------------------------
tr-matmul
--------------------------------------------------
m = 50
Hit count: 1973240
Miss count: 994912
Clean evictions: 956138
Dirty evictions: 38724
Total references : 2968152
Hit rate: 66.4804
Miss rate: 33.5196
m = 100
Hit count: 2644847
Miss count: 323305
Clean evictions: 315834
Dirty evictions: 7371
Total references : 2968152
Hit rate: 89.1075
Miss rate: 10.8925
m = 150
Hit count: 2872249
Miss count: 95903
Clean evictions: 93453
Dirty evictions: 2300
Total references : 2968152
Hit rate: 96.7689
Miss rate: 3.2311
m = 200
Hit count: 2911955
Miss count: 56197
Clean evictions: 54368
Dirty evictions: 1629
Total references : 2968152
Hit rate: 98.1067
Miss rate: 1.8933
--------------------------------------------------
tr-linkedlisttrace
--------------------------------------------------
m = 50
Hit count: 15760
Miss count: 336
Clean evictions: 149
Dirty evictions: 137
Total references : 16096
Hit rate: 97.9125
Miss rate: 2.0875
m = 100
Hit count: 15941
Miss count: 155
Clean evictions: 4
Dirty evictions: 51
Total references : 16096
Hit rate: 99.0370
Miss rate: 0.9630
m = 150
Hit count: 15963
Miss count: 133
Clean evictions: 0
Dirty evictions: 0
Total references : 16096
Hit rate: 99.1737
Miss rate: 0.8263
m = 200
Hit count: 15963
Miss count: 133
Clean evictions: 0
Dirty evictions: 0
Total references : 16096
Hit rate: 99.1737
Miss rate: 0.8263
==================================================
fifo
--------------------------------------------------
tr-simpleloop
--------------------------------------------------
m = 50
Hit count: 7602
Miss count: 2966
Clean evictions: 224
Dirty evictions: 2692
Total references : 10568
Hit rate: 71.9341
Miss rate: 28.0659
m = 100
Hit count: 7820
Miss count: 2748
Clean evictions: 43
Dirty evictions: 2605
Total references : 10568
Hit rate: 73.9970
Miss rate: 26.0030
m = 150
Hit count: 7859
Miss count: 2709
Clean evictions: 16
Dirty evictions: 2543
Total references : 10568
Hit rate: 74.3660
Miss rate: 25.6340
m = 200
Hit count: 7867
Miss count: 2701
Clean evictions: 12
Dirty evictions: 2489
Total references : 10568
Hit rate: 74.4417
Miss rate: 25.5583
--------------------------------------------------
tr-blocked
--------------------------------------------------
m = 50
Hit count: 2518574
Miss count: 6450
Clean evictions: 5201
Dirty evictions: 1199
Total references : 2525024
Hit rate: 99.7446
Miss rate: 0.2554
m = 100
Hit count: 2520689
Miss count: 4335
Clean evictions: 3121
Dirty evictions: 1114
Total references : 2525024
Hit rate: 99.8283
Miss rate: 0.1717
m = 150
Hit count: 2520785
Miss count: 4239
Clean evictions: 2979
Dirty evictions: 1110
Total references : 2525024
Hit rate: 99.8321
Miss rate: 0.1679
m = 200
Hit count: 2521847
Miss count: 3177
Clean evictions: 1893
Dirty evictions: 1084
Total references : 2525024
Hit rate: 99.8742
Miss rate: 0.1258
--------------------------------------------------
tr-matmul
--------------------------------------------------
m = 50
Hit count: 1840885
Miss count: 1127267
Clean evictions: 1083469
Dirty evictions: 43748
Total references : 2968152
Hit rate: 62.0213
Miss rate: 37.9787
m = 100
Hit count: 1884606
Miss count: 1083546
Clean evictions: 1061660
Dirty evictions: 21786
Total references : 2968152
Hit rate: 63.4943
Miss rate: 36.5057
m = 150
Hit count: 2933748
Miss count: 34404
Clean evictions: 32957
Dirty evictions: 1297
Total references : 2968152
Hit rate: 98.8409
Miss rate: 1.1591
m = 200
Hit count: 2934270
Miss count: 33882
Clean evictions: 32441
Dirty evictions: 1241
Total references : 2968152
Hit rate: 98.8585
Miss rate: 1.1415
--------------------------------------------------
tr-linkedlisttrace
--------------------------------------------------
m = 50
Hit count: 15766
Miss count: 330
Clean evictions: 137
Dirty evictions: 143
Total references : 16096
Hit rate: 97.9498
Miss rate: 2.0502
m = 100
Hit count: 15934
Miss count: 162
Clean evictions: 0
Dirty evictions: 62
Total references : 16096
Hit rate: 98.9935
Miss rate: 1.0065
m = 150
Hit count: 15963
Miss count: 133
Clean evictions: 0
Dirty evictions: 0
Total references : 16096
Hit rate: 99.1737
Miss rate: 0.8263
m = 200
Hit count: 15963
Miss count: 133
Clean evictions: 0
Dirty evictions: 0
Total references : 16096
Hit rate: 99.1737
Miss rate: 0.8263
==================================================
lru
--------------------------------------------------
tr-simpleloop
--------------------------------------------------
m = 50
Hit count: 7793
Miss count: 2775
Clean evictions: 93
Dirty evictions: 2632
Total references : 10568
Hit rate: 73.7415
Miss rate: 26.2585
m = 100
Hit count: 7891
Miss count: 2677
Clean evictions: 0
Dirty evictions: 2577
Total references : 10568
Hit rate: 74.6688
Miss rate: 25.3312
m = 150
Hit count: 7893
Miss count: 2675
Clean evictions: 0
Dirty evictions: 2525
Total references : 10568
Hit rate: 74.6877
Miss rate: 25.3123
m = 200
Hit count: 7893
Miss count: 2675
Clean evictions: 0
Dirty evictions: 2475
Total references : 10568
Hit rate: 74.6877
Miss rate: 25.3123
--------------------------------------------------
tr-blocked
--------------------------------------------------
m = 50
Hit count: 2519846
Miss count: 5178
Clean evictions: 4029
Dirty evictions: 1099
Total references : 2525024
Hit rate: 99.7949
Miss rate: 0.2051
m = 100
Hit count: 2521215
Miss count: 3809
Clean evictions: 2631
Dirty evictions: 1078
Total references : 2525024
Hit rate: 99.8491
Miss rate: 0.1509
m = 150
Hit count: 2521223
Miss count: 3801
Clean evictions: 2595
Dirty evictions: 1056
Total references : 2525024
Hit rate: 99.8495
Miss rate: 0.1505
m = 200
Hit count: 2521331
Miss count: 3693
Clean evictions: 2437
Dirty evictions: 1056
Total references : 2525024
Hit rate: 99.8537
Miss rate: 0.1463
--------------------------------------------------
tr-matmul
--------------------------------------------------
m = 50
Hit count: 1926933
Miss count: 1041219
Clean evictions: 1040073
Dirty evictions: 1096
Total references : 2968152
Hit rate: 64.9203
Miss rate: 35.0797
m = 100
Hit count: 1961708
Miss count: 1006444
Clean evictions: 1005269
Dirty evictions: 1075
Total references : 2968152
Hit rate: 66.0919
Miss rate: 33.9081
m = 150
Hit count: 2935275
Miss count: 32877
Clean evictions: 31654
Dirty evictions: 1073
Total references : 2968152
Hit rate: 98.8923
Miss rate: 1.1077
m = 200
Hit count: 2935286
Miss count: 32866
Clean evictions: 31593
Dirty evictions: 1073
Total references : 2968152
Hit rate: 98.8927
Miss rate: 1.1073
--------------------------------------------------
tr-linkedlisttrace
--------------------------------------------------
m = 50
Hit count: 15865
Miss count: 231
Clean evictions: 56
Dirty evictions: 125
Total references : 16096
Hit rate: 98.5649
Miss rate: 1.4351
m = 100
Hit count: 15958
Miss count: 138
Clean evictions: 0
Dirty evictions: 38
Total references : 16096
Hit rate: 99.1426
Miss rate: 0.8574
m = 150
Hit count: 15963
Miss count: 133
Clean evictions: 0
Dirty evictions: 0
Total references : 16096
Hit rate: 99.1737
Miss rate: 0.8263
m = 200
Hit count: 15963
Miss count: 133
Clean evictions: 0
Dirty evictions: 0
Total references : 16096
Hit rate: 99.1737
Miss rate: 0.8263
==================================================
clock
--------------------------------------------------
tr-simpleloop
--------------------------------------------------
m = 50
Hit count: 7780
Miss count: 2788
Clean evictions: 106
Dirty evictions: 2632
Total references : 10568
Hit rate: 73.6185
Miss rate: 26.3815
m = 100
Hit count: 7890
Miss count: 2678
Clean evictions: 1
Dirty evictions: 2577
Total references : 10568
Hit rate: 74.6593
Miss rate: 25.3407
m = 150
Hit count: 7893
Miss count: 2675
Clean evictions: 0
Dirty evictions: 2525
Total references : 10568
Hit rate: 74.6877
Miss rate: 25.3123
m = 200
Hit count: 7892
Miss count: 2676
Clean evictions: 0
Dirty evictions: 2476
Total references : 10568
Hit rate: 74.6783
Miss rate: 25.3217
--------------------------------------------------
tr-blocked
--------------------------------------------------
m = 50
Hit count: 2519259
Miss count: 5765
Clean evictions: 4609
Dirty evictions: 1106
Total references : 2525024
Hit rate: 99.7717
Miss rate: 0.2283
m = 100
Hit count: 2520852
Miss count: 4172
Clean evictions: 2994
Dirty evictions: 1078
Total references : 2525024
Hit rate: 99.8348
Miss rate: 0.1652
m = 150
Hit count: 2521218
Miss count: 3806
Clean evictions: 2599
Dirty evictions: 1057
Total references : 2525024
Hit rate: 99.8493
Miss rate: 0.1507
m = 200
Hit count: 2521803
Miss count: 3221
Clean evictions: 1964
Dirty evictions: 1057
Total references : 2525024
Hit rate: 99.8724
Miss rate: 0.1276
--------------------------------------------------
tr-matmul
--------------------------------------------------
m = 50
Hit count: 1926923
Miss count: 1041229
Clean evictions: 1040084
Dirty evictions: 1095
Total references : 2968152
Hit rate: 64.9200
Miss rate: 35.0800
m = 100
Hit count: 1966370
Miss count: 1001782
Clean evictions: 1000607
Dirty evictions: 1075
Total references : 2968152
Hit rate: 66.2490
Miss rate: 33.7510
m = 150
Hit count: 2933499
Miss count: 34653
Clean evictions: 33428
Dirty evictions: 1075
Total references : 2968152
Hit rate: 98.8325
Miss rate: 1.1675
m = 200
Hit count: 2935273
Miss count: 32879
Clean evictions: 31606
Dirty evictions: 1073
Total references : 2968152
Hit rate: 98.8923
Miss rate: 1.1077
--------------------------------------------------
tr-linkedlisttrace
--------------------------------------------------
m = 50
Hit count: 15855
Miss count: 241
Clean evictions: 68
Dirty evictions: 123
Total references : 16096
Hit rate: 98.5027
Miss rate: 1.4973
m = 100
Hit count: 15955
Miss count: 141
Clean evictions: 0
Dirty evictions: 41
Total references : 16096
Hit rate: 99.1240
Miss rate: 0.8760
m = 150
Hit count: 15963
Miss count: 133
Clean evictions: 0
Dirty evictions: 0
Total references : 16096
Hit rate: 99.1737
Miss rate: 0.8263
m = 200
Hit count: 15963
Miss count: 133
Clean evictions: 0
Dirty evictions: 0
Total references : 16096
Hit rate: 99.1737
Miss rate: 0.8263
==================================================
opt
--------------------------------------------------
tr-simpleloop
--------------------------------------------------
m = 50
Hit count: 7793
Miss count: 2775
Clean evictions: 94
Dirty evictions: 2631
Total references : 10568
Hit rate: 73.7415
Miss rate: 26.2585
m = 100
Hit count: 7892
Miss count: 2676
Clean evictions: 0
Dirty evictions: 2576
Total references : 10568
Hit rate: 74.6783
Miss rate: 25.3217
m = 150
Hit count: 7894
Miss count: 2674
Clean evictions: 0
Dirty evictions: 2524
Total references : 10568
Hit rate: 74.6972
Miss rate: 25.3028
m = 200
Hit count: 7894
Miss count: 2674
Clean evictions: 0
Dirty evictions: 2474
Total references : 10568
Hit rate: 74.6972
Miss rate: 25.3028
--------------------------------------------------
tr-blocked
--------------------------------------------------
m = 50
Hit count: 2519828
Miss count: 5196
Clean evictions: 4047
Dirty evictions: 1099
Total references : 2525024
Hit rate: 99.7942
Miss rate: 0.2058
--------------------------------------------------
tr-matmul
--------------------------------------------------
--------------------------------------------------
tr-linkedlisttrace
--------------------------------------------------
m = 50
Hit count: 15866
Miss count: 230
Clean evictions: 56
Dirty evictions: 124
Total references : 16096
Hit rate: 98.5711
Miss rate: 1.4289
m = 100
Hit count: 15958
Miss count: 138
Clean evictions: 0
Dirty evictions: 38
Total references : 16096
Hit rate: 99.1426
Miss rate: 0.8574
m = 150
Hit count: 15963
Miss count: 133
Clean evictions: 0
Dirty evictions: 0
Total references : 16096
Hit rate: 99.1737
Miss rate: 0.8263
m = 200
Hit count: 15963
Miss count: 133
Clean evictions: 0
Dirty evictions: 0
Total references : 16096
Hit rate: 99.1737
Miss rate: 0.8263
algorithms comparison:
From the results obtained, we can get some conclusions with respect to memory size and algorithm. For individual algorithm on different memory sizes, most algorithms show the trend that with the increment of the memory sizes, the hit rate is increasing and clean/dirty evictions are decreasing. This is understandable, since larger memory size helps capture more memory hits, thus reducing the times of evictions. rand, due to the fact that it doesn't pick up an appropriate candidate to swap, doesn't show this trend apparently. LRU, although known to have Belady's anomaly, doesn't show this feature distinctively in the simulation. For the 4th trace tr-linkedlisttrace, eviction becomes 0 when memory size is large enough. In terms of comparison of different algorithms in general, for the small files such as tr-simpleloop, most algorithms are finally stablized at 74.*%; while for large files like tr-matmul and tr-block, opt and clock algorithms both give relatively better performance on hit rates than other algorithms.
LRU algorithm:
For files of tr-simpleloop, tr-block and tr-linkedlisttrace, the hit rates are quite similar with respect to different memory sizes, while for tr-matmul, the hit rates increase from 63% to 98% when memory size changes from 100 to 150. Even though Belady's anomaly is not obvious in the simulation, we can still find the increased memory size doesn't certainly cause the better hit rates and eviction performance.