-
Notifications
You must be signed in to change notification settings - Fork 0
/
cache.py
189 lines (159 loc) · 6.51 KB
/
cache.py
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
# -*- coding: utf-8 -*-
"""Set Associative Cache 計算機結構_專題(一).ipynb
Automatically generated by Colaboratory.
Original file is located at
https://colab.research.google.com/drive/18OkXZfb-HKlQmyTQDkvU1XG1cAd7FPM1
"""
import math
class blocks:
def __init__(self):
self.valid = True # true -> empty ; false -> not empty
self.tag = -1
self.count = 0 # the greater the count is, the less the block is used since last time
self.address_in_decimal = -1
self.address = -1
class sets:
def __init__(self, SD_SetDegree):
self.blocks = [blocks() for i in range(SD_SetDegree)] # 在每個 set 中建立 SD_SetDegree 個 cache blcok
class cache:
def __init__(self, BS_BlockSize, CS_CacheSize, SD_SetDegree):
# Three inputs for __init__
# 1. 每個Cache Block的大小，單位為Byte,
# 2. Cache的大小，單位為KByte,
# 3. 一個set中的cache block個數
self.BS_BlockSize = BS_BlockSize
self.CS_CacheSize = CS_CacheSize
self.SD_SetDegree = SD_SetDegree
self.CBN_CacheBlockNumber = int((CS_CacheSize * 1024) / BS_BlockSize) # The number of "Cache Block"
print("\nThere are %d Cache Blocks" % (self.CBN_CacheBlockNumber))
self.SN_SetNumber = int(self.CBN_CacheBlockNumber / SD_SetDegree) # The number of set
self.sets = [sets(SD_SetDegree) for i in range(self.SN_SetNumber)] # 在 cache 中建立 SN_SetNumber 個 cache set
print(str(self.SD_SetDegree) + "-way associative cache, with " + str(self.SN_SetNumber) + " sets.")
self.hit_count = 0
self.miss_count = 0
def read_from_cache(self, address_in_decimal): # check data是否在cache中
block_address = math.floor(address_in_decimal / self.BS_BlockSize) # 將 decimal address 轉為 Block address
set_number = int(block_address % self.SN_SetNumber) # 計算所對應的 set
tag = math.floor(block_address / self.SN_SetNumber) # 計算所對應的 tag
#print("\nset: %d, tag: %d" % (set_number, tag))
if self.IsEmpty(set_number):
#print("Set %d is empty" % (set_number))
#print("Cache MISS")
self.miss_count += 1
self.sets[set_number].blocks[0].valid = False
self.sets[set_number].blocks[0].tag = tag
self.add_count(set_number)
else:
if not self.IsFull(set_number):
#print("Set %d is NOT FULL" % (set_number))
hit = False
for block in self.sets[set_number].blocks:
if not block.valid and block.tag == tag:
#print("Cache HIT")
hit = True
self.hit_count += 1
self.add_count(set_number)
block.count = 1
break
'''
elif not hit and block.valid: # 該判斷只適用在循序存取cache block，若block是在set中隨機存取則會有bug
self.miss_count += 1
block.valid = False
block.tag = tag
self.add_count(set_number)
break
'''
if not hit:
for block in self.sets[set_number].blocks:
if block.valid:
#print("Cache MISS")
self.miss_count += 1
block.valid = False
block.tag = tag
self.add_count(set_number)
break
else: # the set is full, replace the least recent used block, by LRU algorithm.
#print("Set %d is FULL" % (set_number))
self.LRU(set_number, tag)
#print("hit_count: %d, miss_count: %d" % (self.hit_count, self.miss_count))
#for block in self.sets[set_number].blocks:
#print("tag: %d" % block.tag)
def LRU(self, set_number, tag):
#print("the set is full")
hit = False
for block in self.sets[set_number].blocks:
if block.tag == tag: # cache hit, the wanted data is in cache, set count to 0
#print("Cache HIT")
hit = True
self.hit_count += 1
self.add_count(set_number)
block.count = 1
break
if not hit:
#print("Cache MISS")
self.miss_count += 1
max_count = 0 # the LRU block count，數字越大 -> 越久沒被使用
LRU_index = -1
for i in range(self.SD_SetDegree):
if self.sets[set_number].blocks[i].count > max_count:
max_count = self.sets[set_number].blocks[i].count
LRU_index = i
#print("***Tag: %d is kicked out***" % self.sets[set_number].blocks[LRU_index].tag)
self.sets[set_number].blocks[LRU_index].tag = tag
self.add_count(set_number)
self.sets[set_number].blocks[LRU_index].count = 1
def add_count(self, set_number):
for block in self.sets[set_number].blocks:
if not block.valid: block.count += 1
def IsEmpty(self, set_number):
for block in self.sets[set_number].blocks:
if block.valid == False:
return False
return True
def IsFull(self, set_number):
for block in self.sets[set_number].blocks:
if block.valid == True:
return False
return True
def print(self):
i = 0
j = 0
for set_ in self.sets:
print("set " + str(i) + ": ")
i += 1
for block in set_.blocks:
print("\tblock %d: valid: %s, tag: %d" % (j, block.valid, block.tag))
j += 1
j = 0
def __main__():
SD = [1, 2, 4, 8]
ff = open("result.txt", "w")
for SD_SetDegree in SD: # 一個set中的cache block個數
###########手動調整參數###########
BS_BlockSize = 16 # 每個Cache Block的大小，單位為Byte
CS_CacheSize = 1024 # Cache的大小，單位為KByte
#SD_SetDegree = 8 # 一個set中的cache block個數
###########手動調整參數###########
test = cache(BS_BlockSize, CS_CacheSize, SD_SetDegree)
f = open("trace.txt", "r")
address = f.readlines()
# 嘗試從 cache 讀取 trace.txt 中的所有 binary address
for i in range(len(address)):
address_in_decimal = int(address[i], 16) # 將十六進位轉換為十進位
#print("Address in decimal: %d" % (address_in_decimal))
test.read_from_cache(address_in_decimal)
#test.print()
print("The number of request: %d, Hit_count: %d" % (len(address), test.hit_count))
print("Miss rate: %f\n-" % (1.0 - (test.hit_count) / len(address)))
f.close()
input = "Block size = %d (Byte)\n" % (BS_BlockSize)
ff.write(input)
input = "Cache size = %dK (Byte)\n" % (CS_CacheSize)
ff.write(input)
input = "Set degree = %d\n" % (SD_SetDegree)
ff.write(input)
input = "Miss rate = %f\n\n" % (1 - (test.hit_count) / len(address))
ff.write(input)
ff.close()
if __name__ == "__main__":
__main__()