mirror of
https://github.com/andreas-abel/nanoBench.git
synced 2025-07-21 07:01:04 +02:00
411 lines
13 KiB
Python
Executable File
411 lines
13 KiB
Python
Executable File
import random
|
|
|
|
from itertools import count
|
|
from numpy import median
|
|
from cacheLib import *
|
|
|
|
import logging
|
|
log = logging.getLogger(__name__)
|
|
|
|
|
|
def rindex(lst, value):
|
|
return len(lst) - lst[::-1].index(value) - 1
|
|
|
|
|
|
class ReplPolicySim(object):
|
|
def __init__(self, assoc):
|
|
self.assoc = assoc
|
|
self.blocks = [None] * assoc
|
|
|
|
def acc(self, block):
|
|
raise NotImplementedError()
|
|
|
|
def flush(self, block):
|
|
if block in self.blocks:
|
|
self.blocks[self.blocks.index(block)] = None
|
|
|
|
|
|
class FIFOSim(ReplPolicySim):
|
|
def __init__(self, assoc):
|
|
super(FIFOSim, self).__init__(assoc)
|
|
|
|
def acc(self, block):
|
|
hit = block in self.blocks
|
|
if not hit:
|
|
self.blocks = [block] + self.blocks[0:self.assoc-1]
|
|
return hit
|
|
|
|
|
|
class LRUSim(ReplPolicySim):
|
|
def __init__(self, assoc):
|
|
super(LRUSim, self).__init__(assoc)
|
|
|
|
def acc(self, block):
|
|
hit = block in self.blocks
|
|
self.blocks = [block] + [b for b in self.blocks if b!=block][0:self.assoc-1]
|
|
return hit
|
|
|
|
|
|
class PLRUSim(ReplPolicySim):
|
|
def __init__(self, assoc, linearInit=False, randLeaf=False, randRoot=False):
|
|
super(PLRUSim, self).__init__(assoc)
|
|
self.linearInit = linearInit
|
|
self.randLeaf = randLeaf
|
|
self.randRoot = randRoot
|
|
self.bits = [[0 for _ in range(0, 2**(level))] for level in range(0, int(math.ceil(math.log(assoc,2))))]
|
|
|
|
def acc(self, block):
|
|
hit = block in self.blocks
|
|
if hit:
|
|
self.updateIndexBits(self.blocks.index(block))
|
|
else:
|
|
if self.linearInit and None in self.blocks:
|
|
idx = self.blocks.index(None)
|
|
else:
|
|
idx = self.getIndexForBits()
|
|
self.blocks[idx] = block
|
|
self.updateIndexBits(idx)
|
|
return hit
|
|
|
|
def getIndexForBits(self, level=0, idx = 0):
|
|
if level == len(self.bits) - 1:
|
|
ret = 2*idx
|
|
if self.randLeaf:
|
|
ret += random.randint(0,1)
|
|
else:
|
|
ret += self.bits[level][idx]
|
|
return min(self.assoc - 1, ret)
|
|
elif level == 0 and self.randRoot:
|
|
return self.getIndexForBits(level + 2, random.randint(0,2))
|
|
else:
|
|
return self.getIndexForBits(level + 1, 2*idx + self.bits[level][idx])
|
|
|
|
def updateIndexBits(self, accIndex):
|
|
lastIdx = accIndex
|
|
for level in reversed(range(0, len(self.bits))):
|
|
curIdx = lastIdx//2
|
|
self.bits[level][curIdx] = 1 - (lastIdx % 2)
|
|
lastIdx = curIdx
|
|
|
|
|
|
class PLRUlSim(PLRUSim):
|
|
def __init__(self, assoc):
|
|
super(PLRUlSim, self).__init__(assoc, linearInit=True)
|
|
|
|
|
|
class PLRURandSim(PLRUSim):
|
|
def __init__(self, assoc):
|
|
super(PLRURandSim, self).__init__(assoc, randLeaf=True)
|
|
|
|
class RandPLRUSim(PLRUSim):
|
|
def __init__(self, assoc):
|
|
super(RandPLRUSim, self).__init__(assoc, randRoot=True)
|
|
|
|
|
|
AllRandPLRUVariants = {
|
|
'RandPLRU': RandPLRUSim,
|
|
'PLRURand': PLRURandSim,
|
|
}
|
|
|
|
class LRU_PLRU4Sim(ReplPolicySim):
|
|
def __init__(self, assoc):
|
|
self.PLRUs = [PLRUSim(4, linearInit=True) for _ in range(0, assoc//4)]
|
|
self.PLRUOrdered = list(self.PLRUs) # from MRU to LRU
|
|
|
|
def acc(self, block):
|
|
hit = False
|
|
curPLRU = self.PLRUOrdered[-1]
|
|
for plru in self.PLRUs:
|
|
if block in plru.blocks:
|
|
curPLRU = plru
|
|
hit = True
|
|
break
|
|
else:
|
|
for plru in self.PLRUs:
|
|
if None in plru.blocks:
|
|
curPLRU = plru
|
|
break
|
|
curPLRU.acc(block)
|
|
self.PLRUOrdered = [curPLRU] + [plru for plru in self.PLRUOrdered if plru!=curPLRU]
|
|
return hit
|
|
|
|
def flush(self, block):
|
|
for plru in self.PLRUs:
|
|
if block in plru.blocks:
|
|
plru.flush(block)
|
|
|
|
|
|
class QLRUSim(ReplPolicySim):
|
|
def __init__(self, assoc, hitFunc, missFunc, replIdxFunc, updFunc, updOnMissOnly=False):
|
|
super(QLRUSim, self).__init__(assoc)
|
|
self.hitFunc = hitFunc
|
|
self.missFunc = missFunc
|
|
self.replIdxFunc = replIdxFunc
|
|
self.updFunc = updFunc
|
|
self.updOnMissOnly = updOnMissOnly
|
|
self.bits = [3] * assoc
|
|
|
|
def acc(self, block):
|
|
hit = block in self.blocks
|
|
|
|
if hit:
|
|
index = self.blocks.index(block)
|
|
self.bits[index] = self.hitFunc(self.bits[index])
|
|
else:
|
|
if self.updOnMissOnly:
|
|
self.bits = self.updFunc(self.bits, -1)
|
|
|
|
index = self.replIdxFunc(self.bits, self.blocks)
|
|
self.blocks[index] = block
|
|
self.bits[index] = self.missFunc()
|
|
|
|
if not self.updOnMissOnly:
|
|
self.bits = self.updFunc(self.bits, index)
|
|
|
|
return hit
|
|
|
|
QLRUHitFuncs = {
|
|
'H21': lambda x: {3:2, 2:1, 1:0, 0:0}[x],
|
|
'H20': lambda x: {3:2, 2:0, 1:0, 0:0}[x],
|
|
'H11': lambda x: {3:1, 2:1, 1:0, 0:0}[x],
|
|
'H10': lambda x: {3:1, 2:0, 1:0, 0:0}[x],
|
|
'H00': lambda x: {3:0, 2:0, 1:0, 0:0}[x],
|
|
}
|
|
|
|
QLRUMissFuncs = {
|
|
'M0': lambda: 0,
|
|
'M1': lambda: 1,
|
|
'M2': lambda: 2,
|
|
'M3': lambda: 3,
|
|
}
|
|
|
|
QLRUMissRandFuncs = {
|
|
'MR32': lambda: (2 if random.randint(0,15) == 0 else 3),
|
|
'MR31': lambda: (1 if random.randint(0,15) == 0 else 3),
|
|
'MR30': lambda: (0 if random.randint(0,15) == 0 else 3),
|
|
'MR21': lambda: (1 if random.randint(0,15) == 0 else 2),
|
|
'MR20': lambda: (0 if random.randint(0,15) == 0 else 2),
|
|
'MR10': lambda: (0 if random.randint(0,15) == 0 else 1),
|
|
}
|
|
|
|
QLRUReplIdxFuncs = {
|
|
'R0': lambda bits, blocks: blocks.index(None) if None in blocks else bits.index(3), #CFL L3
|
|
'R1': lambda bits, blocks: blocks.index(None) if None in blocks else (bits.index(3) if 3 in bits else 0), #IVB
|
|
'R2': lambda bits, blocks: rindex(blocks, None) if None in blocks else bits.index(3), # CFL L2
|
|
}
|
|
|
|
QLRUUpdFuncs = {
|
|
'U0': lambda bits, replIdx: [b + (3 - max(bits)) for b in bits], #CFL L3
|
|
'U1': lambda bits, replIdx: [(b + (3 - max(bits[:replIdx]+bits[replIdx+1:])) if i != replIdx else b) for i, b in enumerate(bits)], #CFL L2
|
|
'U2': lambda bits, replIdx: [b+1 for b in bits] if not 3 in bits else bits, # IVB
|
|
'U3': lambda bits, replIdx: [((b+1) if i != replIdx else b) for i, b in enumerate(bits)] if not 3 in bits else bits,
|
|
}
|
|
|
|
# all deterministic QLRU variants
|
|
AllDetQLRUVariants = {
|
|
'QLRU_' + hf[0] + '_' + mf[0] + '_' + rf[0] + '_' + uf[0] + ('_UMO' if umo else ''):
|
|
type('QLRU_' + hf[0] + '_' + mf[0] + '_' + rf[0] + '_' + uf[0] + ('_UMO' if umo else ''), (QLRUSim,),
|
|
{'__init__': lambda self, assoc, hfl=hf[1], mfl=mf[1], rfl=rf[1], ufl=uf[1], umol=umo: QLRUSim.__init__(self, assoc, hfl, mfl, rfl, ufl, umol)})
|
|
for hf in QLRUHitFuncs.items()
|
|
for mf in QLRUMissFuncs.items()
|
|
for rf in QLRUReplIdxFuncs.items()
|
|
for uf in QLRUUpdFuncs.items()
|
|
for umo in [False, True]
|
|
if not (rf[0] in ['R0', 'R2'] and uf[0] in ['U2', 'U3'])
|
|
}
|
|
|
|
# all randomized QLRU variants
|
|
AllRandQLRUVariants = {
|
|
'QLRU_' + hf[0] + '_' + mf[0] + '_' + rf[0] + '_' + uf[0] + ('_UMO' if umo else ''):
|
|
type('QLRU_' + hf[0] + '_' + mf[0] + '_' + rf[0] + '_' + uf[0] + ('_UMO' if umo else ''), (QLRUSim,),
|
|
{'__init__': lambda self, assoc, hfl=hf[1], mfl=mf[1], rfl=rf[1], ufl=uf[1], umol=umo: QLRUSim.__init__(self, assoc, hfl, mfl, rfl, ufl, umol)})
|
|
for hf in QLRUHitFuncs.items()
|
|
for mf in QLRUMissRandFuncs.items()
|
|
for rf in QLRUReplIdxFuncs.items()
|
|
for uf in QLRUUpdFuncs.items()
|
|
for umo in [False, True]
|
|
if not (rf[0] in ['R0', 'R2'] and uf[0] in ['U2', 'U3'])
|
|
}
|
|
|
|
|
|
class MRUSim(ReplPolicySim):
|
|
def __init__(self, assoc, updIfNotFull=True):
|
|
super(MRUSim, self).__init__(assoc)
|
|
self.bits = [1] * assoc
|
|
self.updIfNotFull = updIfNotFull
|
|
|
|
def acc(self, block):
|
|
hit = block in self.blocks
|
|
full = not (None in self.blocks)
|
|
if hit:
|
|
index = self.blocks.index(block)
|
|
else:
|
|
if not full:
|
|
index = self.blocks.index(None)
|
|
else:
|
|
index = self.bits.index(1)
|
|
self.blocks[index] = block
|
|
|
|
if (full or self.updIfNotFull):
|
|
self.bits[index] = 0
|
|
|
|
if not 1 in self.bits:
|
|
self.bits = [(1 if bi!=index else 0) for bi, _ in enumerate(self.bits)]
|
|
|
|
return hit
|
|
|
|
|
|
class MRUNSim(MRUSim):
|
|
def __init__(self, assoc):
|
|
super(MRUNSim, self).__init__(assoc, False)
|
|
|
|
|
|
# according to ISCA'10 paper
|
|
class NRUSim(ReplPolicySim):
|
|
def __init__(self, assoc):
|
|
super(NRUSim, self).__init__(assoc)
|
|
self.bits = [1] * assoc
|
|
|
|
def acc(self, block):
|
|
hit = block in self.blocks
|
|
if hit:
|
|
index = self.blocks.index(block)
|
|
self.bits[index] = 0
|
|
else:
|
|
while not 1 in self.bits:
|
|
self.bits = [1] * self.assoc
|
|
index = self.bits.index(1)
|
|
self.blocks[index] = block
|
|
self.bits[index] = 0
|
|
return hit
|
|
|
|
|
|
CommonPolicies = {
|
|
'FIFO': FIFOSim,
|
|
'LRU': LRUSim,
|
|
'PLRU': PLRUSim,
|
|
'PLRUl': PLRUlSim,
|
|
'LRU_PLRU4': LRU_PLRU4Sim,
|
|
'MRU': MRUSim, # NHM
|
|
'MRU_N': MRUNSim, # SNB
|
|
'NRU': NRUSim,
|
|
'QLRU_H11_M1_R0_U0': AllDetQLRUVariants['QLRU_H11_M1_R0_U0'], # CFL L3
|
|
'QLRU_H21_M1_R0_U0_UMO': AllDetQLRUVariants['QLRU_H21_M2_R0_U0_UMO'], # https://arxiv.org/pdf/1904.06278.pdf paper
|
|
'QLRU_H11_M1_R1_U2': AllDetQLRUVariants['QLRU_H11_M1_R1_U2'], # IVB
|
|
'QLRU_H00_M1_R2_U1': AllDetQLRUVariants['QLRU_H00_M1_R2_U1'], # CFL L2
|
|
'QLRU_H00_M1_R0_U1': AllDetQLRUVariants['QLRU_H00_M1_R0_U1'], # CNL L2
|
|
'SRRIP': AllDetQLRUVariants['QLRU_H00_M2_R0_U0_UMO'],
|
|
}
|
|
|
|
AllDetPolicies = dict(list(CommonPolicies.items()) + list(AllDetQLRUVariants.items()))
|
|
AllRandPolicies = dict(list(AllRandQLRUVariants.items()) + list(AllRandPLRUVariants.items()))
|
|
AllPolicies = dict(list(AllDetPolicies.items()) + list(AllRandPolicies.items()))
|
|
|
|
|
|
def parseCacheSetsStrSim(cacheSetsStr):
|
|
if cacheSetsStr is None:
|
|
raise ValueError('no cache sets specified')
|
|
|
|
cacheSetList = []
|
|
for s in cacheSetsStr.split(','):
|
|
if '-' in s:
|
|
first, last = s.split('-')[:2]
|
|
cacheSetList += list(range(int(first), int(last)+1))
|
|
else:
|
|
cacheSetList.append(int(s))
|
|
|
|
return cacheSetList
|
|
|
|
|
|
def getHits(seq, policySimClass, assoc, cacheSetStr):
|
|
cacheSetList = parseCacheSetsStrSim(cacheSetStr)
|
|
allUsedSets = getAllUsedCacheSets(cacheSetList, seq)
|
|
policySims = {s: policySimClass(assoc) for s in allUsedSets}
|
|
|
|
hits = 0
|
|
for blockStr in seq.split():
|
|
blockName = getBlockName(blockStr)
|
|
if blockName == '<wbinvd>':
|
|
policySims = {s: policySimClass(assoc) for s in allUsedSets}
|
|
continue
|
|
|
|
overrideSet = getBlockSet(blockStr)
|
|
sets = [overrideSet] if overrideSet is not None else cacheSetList
|
|
|
|
for s in sets:
|
|
if '!' in blockStr:
|
|
policySims[s].flush(blockName)
|
|
else:
|
|
hit = policySims[s].acc(blockName)
|
|
if '?' in blockStr:
|
|
hits += int(hit)
|
|
return hits
|
|
|
|
|
|
def getAges(blocks, seq, policySimClass, assoc):
|
|
ages = {}
|
|
for block in blocks:
|
|
for i in count(0):
|
|
curSeq = seq + ' ' + ' '.join('N' + str(n) for n in range(0,i)) + ' ' + block + '?'
|
|
if getHits(curSeq, policySimClass, assoc, '0') == 0:
|
|
ages[block] = i
|
|
break
|
|
return ages
|
|
|
|
|
|
def getGraph(blocks, seq, policySimClass, assoc, maxAge, nSets=1, nRep=1, agg="med"):
|
|
traces = []
|
|
for block in blocks:
|
|
trace = []
|
|
for i in range(0, maxAge):
|
|
curSeq = seq + ' ' + ' '.join('N' + str(n) for n in range(0,i)) + ' ' + block + '?'
|
|
hits = [getHits(curSeq, policySimClass, assoc, '0-'+str(nSets-1)) for _ in range(0, nRep)]
|
|
if agg == "med":
|
|
aggValue = median(hits)
|
|
elif agg == "min":
|
|
aggValue = min(hits)
|
|
else:
|
|
aggValue = float(sum(hits))/nRep
|
|
trace.append(aggValue)
|
|
traces.append((block, trace))
|
|
return traces
|
|
|
|
|
|
def getPermutations(policySimClass, assoc):
|
|
# initial ages
|
|
initBlocks = ['I' + str(i) for i in range(0, assoc)]
|
|
seq = ' '.join(initBlocks)
|
|
|
|
initAges = getAges(initBlocks, seq, policySimClass, assoc)
|
|
|
|
accSeqStr = 'Access sequence: <wbinvd> ' + seq
|
|
print(accSeqStr)
|
|
print('Ages: {' + ', '.join(b + ': ' + str(initAges[b]) for b in initBlocks) + '}')
|
|
|
|
blocks = ['B' + str(i) for i in range(0, assoc)]
|
|
baseSeq = ' '.join(initBlocks + blocks)
|
|
|
|
ages = getAges(blocks, baseSeq, policySimClass, assoc)
|
|
|
|
accSeqStr = 'Access sequence: <wbinvd> ' + baseSeq
|
|
print(accSeqStr)
|
|
print('Ages: {' + ', '.join(b + ': ' + str(ages[b]) for b in blocks) + '}')
|
|
|
|
blocksSortedByAge = [a[0] for a in sorted(ages.items(), key=lambda x: -x[1])] # most recent block first
|
|
|
|
for permI, permBlock in enumerate(blocksSortedByAge):
|
|
seq = baseSeq + ' ' + permBlock
|
|
permAges = getAges(blocks, seq, policySimClass, assoc)
|
|
|
|
accSeqStr = 'Access sequence: <wbinvd> ' + seq
|
|
|
|
perm = [-1] * assoc
|
|
for bi, b in enumerate(blocksSortedByAge):
|
|
permAge = permAges[b]
|
|
if permAge < 1 or permAge > assoc:
|
|
break
|
|
perm[assoc-permAge] = bi
|
|
|
|
print(u'\u03A0_' + str(permI) + ' = ' + str(tuple(perm)))
|
|
|