Last active
January 5, 2022 16:45
-
-
Save jerryc05/d2ec86a744b22268d8df61fb1c8cf7dd to your computer and use it in GitHub Desktop.
3c's Problem
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#!usr/bin/env python3 | |
from dataclasses import dataclass | |
from math import log2, floor | |
from typing import cast, Set | |
if __name__ == '__main__': | |
n_set_, n_blk_, n_sz_, cols = '# of total sets: ', '# of total blocks: ', 'block size in bytes: ', 60 | |
n_set = int(input(n_set_)) | |
n_blk = int(input(n_blk_)) | |
n_sz = int(input(n_sz_)) | |
n_way = n_blk // n_set | |
print() | |
print('-' * (cols//2)) | |
print(f'{n_set_}{n_set}') | |
print(f'{n_blk_}{n_blk}') | |
print(f'# of total ways: {n_way}') | |
print(f'{n_sz_}{n_sz}') | |
print(f'cache size in bytes: {n_blk*n_sz}') | |
print() | |
print('-' * cols) | |
@dataclass | |
class Data: | |
addr: int | |
inf: bool = False | |
fa: bool = False | |
sa: bool = False | |
addr_of_ev: 'int|None' = None | |
data: 'list[Data]' = [] | |
while ...: | |
inp = input(f'addr #{len(data)+1} (leave blank to start): ') | |
if not inp: break | |
data.append(Data(addr=int(inp, 0))) | |
print(f'addr #{len(data)}: {hex(data[-1].addr)}\n') | |
print() | |
# infinite | |
blk_i: 'Set[int]' = set() | |
for d in data: | |
tag = d.addr // n_sz | |
d.inf = tag in blk_i | |
blk_i.add(tag) | |
del blk_i | |
# f. a. | |
blk_f: 'list[int]' = [] | |
for d in data: | |
tag = d.addr // n_sz | |
if tag in blk_f: | |
d.fa = True | |
blk_f.remove(tag) | |
blk_f.append(tag) | |
else: | |
d.fa = False | |
blk_f.append(tag) | |
if len(blk_f) > n_blk: | |
del blk_f[0] | |
del blk_f | |
# s. a. | |
@dataclass | |
class LruData: | |
v: bool | |
lru: int | |
data: Data | |
sets: 'list[list[LruData]]' = [[LruData(False, 0, Data(0)) for _ in range(n_way)] for _ in range(n_set)] | |
for d in data: | |
d.sa = False | |
tag = d.addr // n_sz | |
set_i = tag % n_set | |
blks = sets[set_i] | |
done = False | |
for blk in blks: | |
if not blk.v: | |
for blk_ in blks: | |
if blk_.v: blk_.lru -= 1 | |
blk.v, blk.lru, blk.data, done = True, n_way - 1, d, True | |
break | |
elif tag == blk.data.addr // n_sz: | |
for blk_ in blks: | |
if blk_.lru > blk.lru: blk_.lru -= 1 | |
d.sa, blk.lru, blk.data, done = True, n_way - 1, d, True | |
break | |
if done: continue | |
blk = min(blks, key=lambda x: x.lru) | |
d.addr_of_ev = blk.data.addr | |
if (blk.lru != 0): raise RuntimeError(blk.lru) | |
for blk_ in blks: | |
if blk_.lru > blk.lru: blk_.lru -= 1 | |
blk.lru, blk.data = n_way - 1, d | |
print('-' * cols) | |
print() | |
max_addr = max(data, key=lambda x: x.addr).addr | |
max_addr_hexlen = max(4, len(hex(max_addr))) | |
max_addr_binlen = max(4, len(bin(max_addr))) | |
blk_bits, set_bits = floor(log2(n_sz)), floor(log2(n_set)) | |
tag_bits = max_addr_binlen - 2 - blk_bits - set_bits | |
tag_of_ev_label = 'Addr of Evicted' | |
print( | |
f'{"ADDR".center(max_addr_hexlen)} | {"ADDR in Bin".center(max_addr_binlen+3)} | INF | F A | S A | {"3Cs".center(10)} | {tag_of_ev_label.center(max_addr_binlen+3)}' | |
) | |
print(f'{"-"*max_addr_hexlen}-|-{"-"*(max_addr_binlen+3)}-|-----|-----|-----|-{"-"*10}-|-{"-"*(max_addr_binlen+3)}') | |
for d in data: | |
addr, inf, fa, sa, ev = d.addr, d.inf, d.fa, d.sa, d.addr_of_ev | |
addr_ = f'{addr:#0{max_addr_binlen}b}' | |
addr_ = f'0b \x1b[93m{addr_[2:2+tag_bits]} \x1b[95m{addr_[2+tag_bits:-blk_bits]} \x1b[96m{addr_[-blk_bits:]}\x1b[39m' | |
print(end=f'{addr:#0{max_addr_hexlen}x} | {addr_}') | |
for x in (inf, fa, sa): | |
print(end=f' | \x1b[{"92mH" if x else "91mM"}\x1b[39m ') | |
print(end=' | \x1b[') | |
if not inf: | |
print(end='94mCompulsory') | |
elif fa and not sa: | |
print(end='93m Conflict ') | |
elif not sa: | |
print(end='95m Capacity ') | |
else: | |
print(end=f'92m{"-"*10}') | |
if ev is None: | |
addr_ = "-" * (max_addr_binlen+3) | |
else: | |
addr_ = f'{ev:#0{max_addr_binlen}b}' | |
addr_ = f'0b \x1b[93m{addr_[2:2+tag_bits]} \x1b[95m{addr_[2+tag_bits:-blk_bits]} \x1b[96m{addr_[-blk_bits:]}\x1b[39m' | |
print(f'\x1b[39m | {addr_}') | |
print() | |
print() | |
print('-' * cols) | |
for i, set in enumerate(sets): | |
for j, blk in enumerate(set): | |
addr_ = f'{blk.data.addr:#0{max_addr_binlen}b}' | |
addr_ = f'0b \x1b[93m{addr_[2:2+tag_bits]} \x1b[95m{addr_[2+tag_bits:-blk_bits]} \x1b[96m{addr_[-blk_bits:]}\x1b[39m' | |
print(f'Set {i} Way {j} Addr: {addr_}') | |
print() | |
''' | |
2 | |
4 | |
16 | |
0xdd5 | |
0x1f07 | |
0x2ae | |
0x509 | |
0x2edf | |
0x1f0f | |
0x1f01 | |
0x48d7 | |
0xdda | |
0x380 | |
''' |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment