# Copyright 2011-2021 IBM Corporation
#
# Licensed under the Apache License, Version 2.0 (the "License");
# you may not use this file except in compliance with the License.
# You may obtain a copy of the License at
#
# http://www.apache.org/licenses/LICENSE-2.0
#
# Unless required by applicable law or agreed to in writing, software
# distributed under the License is distributed on an "AS IS" BASIS,
# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
# See the License for the specific language governing permissions and
# limitations under the License.
""":mod:`microprobe.model.memory` module
"""
# Futures
from __future__ import absolute_import, division, print_function
from typing import Dict, List, Tuple, Union
# Own modules
from microprobe.code.address import Address
from microprobe.code.var import VariableArray
from microprobe.exceptions import MicroprobeModelError
from microprobe.model import GenericModel
from microprobe.utils.distrib import shuffle, weighted_choice
from microprobe.utils.logger import get_logger
from microprobe.utils.typeguard_decorator import typeguard_testsuite
from microprobe.target.uarch.cache import SetAssociativeCache
# Constants
LOG = get_logger(__name__)
__all__ = ["EndlessLoopInstructionMemoryModel", "EndlessLoopDataMemoryModel"]
# Functions
# Classes
[docs]
@typeguard_testsuite
class EndlessLoopInstructionMemoryModel(GenericModel):
""" """
[docs]
def __init__(self,
name: str,
cache_hierarchy: List[SetAssociativeCache],
percentages: List[int],
minimum_chunks: Union[int, None] = None,
minimum_displacement: Union[int, None] = None):
"""
:param name:
:param cache_hierarchy:
:param percentages:
:param minimum_chunks: (Default value = None)
:param minimum_displacement: (Default value = None)
"""
super(EndlessLoopInstructionMemoryModel, self).__init__(
name, "Generic instruction memory model for endless loops")
self._cache_hierarchy = cache_hierarchy
self._percentages = percentages
assert len(cache_hierarchy) == len(percentages)
assert sum(percentages) == 100, \
"The memory access model is not complete"
cache_ant: Union[SetAssociativeCache, None] = None
displacements: List[int] = []
number_of_chunks: List[int] = []
for cache, ratio in zip(cache_hierarchy, percentages):
if cache_ant is None and ratio > 0:
displacements.append(0)
number_of_chunks.append(1)
elif ratio == 0:
displacements.append(0)
number_of_chunks.append(0)
elif ratio > 0:
assert cache_ant is not None
displacements.append(2**(cache_ant.bits_x_set + 1 +
cache_ant.bits_x_offset))
number_of_chunks.append(cache_ant.ways + 1)
assert cache.ways >= cache_ant.ways + 1, "Overflowing two " \
"levels at the same time? Not Implemented."
cache_ant = cache
if minimum_chunks is not None:
# print number_of_chunks
# print displacements
assert [x for x in number_of_chunks
if x >= 0][-1] < minimum_chunks, \
"Minimum chunks forced, but more chunks are needed."
number_of_chunks[[
x[0] for x in enumerate(number_of_chunks) if x[1] > 0
][-1]] = minimum_chunks
if minimum_displacement is not None:
for idx, displacement in enumerate(displacements):
if displacement < minimum_displacement:
displacements[idx] = minimum_displacement
iterations = [1] * len(number_of_chunks)
def get_percentages(iterations: List[int], number_chunks: List[int]):
"""
:param iterations:
:param number_chunks:
"""
total_count = sum(
[x * y for x, y in zip(iterations, number_chunks)])
return [((x * y) / total_count) * 100
for x, y in zip(iterations, number_chunks)]
def max_percentage_diff(percentages: List[float],
target_percentages: List[int]):
"""
:param percentages:
:param target_percentages:
"""
return max(
[abs(x - y) for x, y in zip(percentages, target_percentages)])
def min_percentage_idx(percentages: List[float],
target_percentages: List[int]):
"""
:param percentages:
:param target_percentages:
"""
min_value = min([(x - y)
for x, y in zip(percentages, target_percentages)])
return [
idx for idx, elem in enumerate(
zip(percentages, target_percentages))
if (elem[0] - elem[1]) == min_value
][0]
current_percentages = get_percentages(iterations, number_of_chunks)
while max_percentage_diff(current_percentages,
self._percentages) > 0.1:
iterations[min_percentage_idx(current_percentages,
self._percentages)] += 1
current_percentages = get_percentages(iterations, number_of_chunks)
descriptors = list(zip(number_of_chunks, displacements, iterations))
self._descriptors = descriptors
def __call__(self, bbl_size: int):
"""
:param bbl_size:
"""
# print self._descriptors
for elem in [
x[1] for x in self._descriptors[1:] if x[2] > 0 and x[0] > 0
]:
# print(elem, bbl_size)
if bbl_size > elem:
raise MicroprobeModelError(
f"Basic block size ('{bbl_size}') is too "
"large for the model")
return self._descriptors
[docs]
@typeguard_testsuite
class EndlessLoopDataMemoryModel(GenericModel):
""" """
[docs]
def __init__(self, name: str, cache_hierarchy: List[SetAssociativeCache],
percentages: List[int]):
"""
:param name:
:param cache_hierarchy:
:param percentages:
"""
super(EndlessLoopDataMemoryModel,
self).__init__(name, "Generic memory model for endless loops")
self._cache_hierarchy = cache_hierarchy
self._percentages = percentages
assert len(cache_hierarchy) == len(percentages)
items: List[Tuple[SetAssociativeCache, int]] = []
all_ratio = 0
accum = 100
mcomp_ants: List[SetAssociativeCache] = []
sets_dict: Dict[SetAssociativeCache, List[int]] = {}
for mcomp, ratio in zip(cache_hierarchy, percentages):
items.append((mcomp, ratio))
all_ratio += ratio
if accum == 0:
sets = []
elif len(mcomp_ants) == 0:
sets = mcomp.setsways()
lsets = len(sets)
sets = sets[0:int(lsets * ratio // accum)]
else:
sets = mcomp.setsways()
sets_length = len(sets)
setm = [1] * len(sets)
for mcomp_ant in mcomp_ants:
# sets = mcomp.setsways()
sets_ant = list(elem & ((1 << mcomp_ant.set_ways_bits) - 1)
for elem in sets)
# zipping = zip(sets, sets_ant)
# fset = frozenset(sets_dict[mcomp_ant])
# sets = [s1 for s1, s2 in zipping if s2 not in fset]
# print(len(sets))
if len(sets_dict[mcomp_ant]) > 0:
fset = frozenset(sets_dict[mcomp_ant])
idxes = (idx for idx in range(0, sets_length)
if setm[idx] != 0)
for idx in idxes:
# print(idx, sets_length)
# if setm[idx] == 0:
# continue
if sets_ant[idx] in fset: # sets_dict[mcomp_ant]:
# print(idx, sets_length)
setm[idx] = 0
# sets = mcomp.setsways()
sets = [s1 for s1, s2 in zip(sets, setm) if s2 != 0]
lsets = len(sets)
sets = sets[0:int(lsets * ratio // accum)]
sets_dict[mcomp] = sets
accum = accum - ratio
mcomp_ants.append(mcomp)
mcomp_ant_iter = None
for mcomp, ratio in zip(cache_hierarchy, percentages):
slist = [elem << mcomp.offset_bits for elem in sets_dict[mcomp]]
# TODO: strided parameter or random or pseudorandom (32k ranges)
# TODO: shuffle function too slow for pseudorandom
if mcomp_ant_iter is None:
mcomp_ant_iter = mcomp
if False:
slist = shuffle(slist, 32768)
elif False:
slist = shuffle(slist, -1)
elif False:
slist = shuffle(slist, mcomp_ant_iter.size)
if len(slist) > 0:
tlist: List[int] = []
tlist.append(slist[0])
tlist.append(slist[-1])
sets_dict[mcomp] = slist
mcomp_ant_iter = mcomp
self._sets = sets_dict
self._func = weighted_choice(dict(items))
self._state: Dict[SetAssociativeCache, Tuple[VariableArray, int, int,
int, List[int]]] = {}
assert all_ratio == 100, "The memory access model is not complete"
assert accum == 0, "Something wrong"
[docs]
def initialize_model(self):
""" """
mant = None
for elem in self._cache_hierarchy:
var = VariableArray(elem.name.replace(" ", "_"),
"char",
elem.size,
align=256 * 1024)
count = 0
max_value = 0
if mant is None:
module = len(self._sets[elem])
else:
module = min(
int(4 * (len(mant.setsways()) - len(self._sets[mant]))),
len(self._sets[elem]))
self._state[elem] = (var, count, max_value, module, [])
mant = elem
[docs]
def finalize_model(self):
""" """
actions: List[Tuple[VariableArray, int, int]] = []
cache_ant: Union[SetAssociativeCache, None] = None
for cache, ratio in zip(self._cache_hierarchy, self._percentages):
var, count, max_value, \
_dummy_module, _dummy_cca = self._state[cache]
# General checks
if count == 0 and ratio > 0:
raise MicroprobeModelError(
"Zero accesses generated to the"
f" cache level '{cache}' and '{ratio}' of all accesses"
" are required.")
if count > 0 and ratio == 0:
raise MicroprobeModelError(
f"{count} accesses generated to the"
f" cache level '{cache}' and not accesses"
" are required.")
if cache_ant is None or ratio == 0:
cache_ant = cache
continue
size = len(self._sets[cache])
real_size = len(cache_ant.setsways()) - len(self._sets[cache_ant])
incsize = max_value // cache_ant.size
if (max_value % cache_ant.size) > 0:
incsize += 1
incsize = cache_ant.size * incsize
guard = cache.size // incsize
LOG.debug(f"Level: {cache}")
LOG.debug(f" Accesses: {count}")
LOG.debug(f" Max.Value: {max_value}")
LOG.debug(f" Previous level size: {real_size}")
LOG.debug(f" Increment size: {incsize}")
LOG.debug(f" Iterations: {guard}")
if (guard * count) < (2 * real_size):
# Too few accesses that we can not overflow the previous
# cache level
raise MicroprobeModelError(
"Too few accesses to cache level"
" '%s' to overflow the previous cache level '%s'. "
"Consider increasing the number of accesses to this"
" level (more %% of accesses or larger benchmark size)."
" You need '%d' more accesses. Accesses: %s ;"
" Iterations: %s ; Size: %s " %
(cache, cache_ant,
((2 * real_size) -
(guard * count)) // guard, count, guard, real_size))
if count > size or count > (2 * real_size):
# No action required
continue
increment_size = cache.size // guard
actions.append((var, increment_size, guard))
return actions
def _check_integrity(self):
""" """
# Make sure we are accessing to different CC on each
# memory element
for elem1 in self._cache_hierarchy:
for elem2 in self._cache_hierarchy:
if elem1 == elem2:
continue
intr = set(self._state[elem1][4]).intersection(
(self._state[elem2][4]))
if len(intr) > 0:
LOG.debug(f"{elem1}, {self._state[elem1][4]}")
LOG.debug(f"{elem2}, {self._state[elem1][4]}")
LOG.critical("MEMORY MODEL NOT IMPLEMENTED CORRECTLY")
exit(-1)
def __call__(self, lengths: List[int]):
"""
:param lengths:
"""
mcomp = self._func()
var, count, max_value, module, cca = self._state[mcomp]
value = self._sets[mcomp][count % module]
count = count + 1
max_value = max(value, max_value)
cgc = mcomp.congruence_class(value)
self._check_integrity()
if cgc not in cca:
cca.append(cgc)
self._state[mcomp] = (var, count, max_value, module, cca)
return Address(base_address=var, displacement=value), max(lengths)