-
Notifications
You must be signed in to change notification settings - Fork 0
/
Cachesim.m
140 lines (123 loc) · 4.41 KB
/
Cachesim.m
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
function worst=Cachesim(N, alpha, chunks, C)
%% Input Parameters
n = 10000;
pop = zipf_rand(n,alpha,n);
pop = sort(pop,'descend');
% sizes = unidrnd(7,1,n);
sizes = ones(1,n) * chunks;
biggest = max(sizes);
totpop = sum(pop);
lambda = 1;
font_size = 24;
line_width = 3;
marker_size = 15;
%% Solve for tc
disp('Solving for root')
func = @(t) timeapproxgLRU(t,n,pop,sizes)-C;
options = optimset('TolX', 10^(-16));
tc = fzero(func,0,options)
%% Define Hit rate Function
hitrate = @(pop,k) expcdf(tc,1/pop).^k- expcdf(tc,1/pop).^(k+1);
%% Generate interarrrival times and file selections
fileselect = randsample(1:n, N, true, pop/totpop);
%% Complete Simulation
disp('Entering Simulation')
cache = zeros(1,C);
newcache = zeros(1,C);
numin = zeros(1,n);
hits = zeros(1,N);
for i = 1:N
chosen = fileselect(i);
if numin(chosen) > 0
ind = cache == chosen;
newcache(1:numin(chosen)) = cache(ind);
newcache(numin(chosen)+1:end) = cache(~ind);
cache = newcache;
end
if numin(chosen) < sizes(chosen)
if cache(end) ~= 0
numin(cache(end)) = numin(cache(end)) - 1;
end
cache(2:end) = cache(1:end-1);
cache(1) = fileselect(i);
hits(i) = numin(chosen);
numin(chosen) = numin(chosen)+1;
else
hits(i) = numin(chosen);
end
if mod(i,100000) == 0
disp(i/N)
end
end
worst = 0
hold off
selected = fileselect == 1;
tbl = tabulate(hits(selected));
hitest = hitrate(pop(1),0:sizes(1)-1);
plot(0:sizes(1),[hitest 1-sum(hitest)], 'b-','LineWidth',line_width);
xlabel('Number of file chunks')
ylabel('Probability of finding in cache')
ylim([0 1])
hold on
plot(tbl(:,1),tbl(:,3)/100,'b*','MarkerSize',marker_size)
hold on
set(gca,'fontsize',font_size)
padded = zeros(length(hitest)+1,1);
padded(1:length(tbl(:,3))) = transpose(tbl(:,3)/100);
worst_temp = max(abs(transpose([hitest 1-sum(hitest)]) - padded))
worst = max(worst, worst_temp)
% tbl = tabulate(hits(10));
% selected = fileselect == 10;
% tbl = tabulate(hits(selected));
% hitest = hitrate(pop(10),0:sizes(10)-1);
%
% plot(0:sizes(10),[hitest 1-sum(hitest)], 'k--','LineWidth',1.5);
% xlabel('Number of file chunks')
% ylabel('Probability of finding in cache')
% ylim([0 1])
% hold on
% plot(tbl(:,1),tbl(:,3)/100,'k+','LineWidth',1.5)
% hold on
% set(gca,'fontsize',font_size)
% padded = zeros(length(hitest)+1,1);
% padded(1:length(tbl(:,3))) = transpose(tbl(:,3)/100);
% worst_temp = max(abs(transpose([hitest 1-sum(hitest)]) - padded));
% worst = max(worst, worst_temp);
%
fileselect = fileselect(C+1:end);
hits = hits(C+1:end);
selected = fileselect == 100;
tbl = tabulate(hits(selected));
hitest = hitrate(pop(100),0:sizes(100)-1);
%
plot(0:sizes(100),[hitest 1-sum(hitest)], 'r:','LineWidth',line_width);
xlabel('Number of file chunks')
ylabel('Probability of finding in cache')
ylim([0 1])
hold on
plot(tbl(:,1),tbl(:,3)/100,'ro','MarkerSize',marker_size)
hold on
set(gca,'fontsize',font_size)
padded = zeros(length(hitest)+1,1);
padded(1:length(tbl(:,3))) = transpose(tbl(:,3)/100);
worst_temp = max(abs(transpose([hitest 1-sum(hitest)]) - padded));
worst = max(worst, worst_temp);
selected = fileselect == 1000;
tbl = tabulate(hits(selected));
hitest = hitrate(pop(1000),0:sizes(1000)-1);
plot(0:sizes(1000),[hitest 1-sum(hitest)], 'm-.','LineWidth',line_width);
xlabel('Number of file chunks')
ylabel('Probability of finding in cache')
ylim([0 1])
hold on
plot(tbl(:,1),tbl(:,3)/100,'mx','MarkerSize',marker_size)
set(gca,'fontsize',font_size)
filename = strcat('cachesim_N_',string(N),'_n_',string(n),'_alpha_', ...
string(alpha),'_C_',string(C),'_chunks_',string(chunks),'.png');
fig = gcf;
print(fig,'-dpng',filename{1})
padded = zeros(length(hitest)+1,1);
padded(1:length(tbl(:,3))) = transpose(tbl(:,3)/100);
worst_temp = max(abs(transpose([hitest 1-sum(hitest)]) - padded));
worst = max(worst, worst_temp);
end