From f659a11e1c888b01cce64fee5ae064a67aa4d777 Mon Sep 17 00:00:00 2001 From: Jonathan Herman Date: Fri, 5 Apr 2013 14:24:33 -0400 Subject: Added ColorMcGenerator. --- gen/__init__.py | 3 + gen/color.py | 102 +++++++++++++++++++++++++ gen/generator.py | 35 +++++---- gen/mc_generators.py | 206 ++++++++++++++++++++++++++++++++++++++++++++++----- 4 files changed, 316 insertions(+), 30 deletions(-) create mode 100644 gen/color.py (limited to 'gen') diff --git a/gen/__init__.py b/gen/__init__.py index 8c60b46..803bb37 100644 --- a/gen/__init__.py +++ b/gen/__init__.py @@ -1,6 +1,9 @@ import generator as gen import edf_generators as edf +import mc_generators as mc gen.register_generator("G-EDF", edf.GedfGenerator) gen.register_generator("P-EDF", edf.PedfGenerator) gen.register_generator("C-EDF", edf.CedfGenerator) +gen.register_generator("MC", mc.McGenerator) +gen.register_generator("Color-MC", mc.ColorMcGenerator) diff --git a/gen/color.py b/gen/color.py new file mode 100644 index 0000000..8184b8b --- /dev/null +++ b/gen/color.py @@ -0,0 +1,102 @@ +import os +import re + +from collections import namedtuple,defaultdict +from math import ceil +from random import randint + +class ColorScheme(object): + def __init__(self, colors, ways): + self.colors = colors + self.ways = ways + + def color(self, tasks, wss): + '''Assign a color->replicas dict to each task in tasks.''' + raise NotImplementedError + +class BlockColorScheme(ColorScheme): + def __init__(self, colors, ways, way_first): + super(BlockColorScheme, self).__init__(colors, ways) + self.way_first = way_first + + def color(self, tasks, pages_needed): + '''Pages are assigned in blocks, either maximizing the number of ways + or maximizing the number of colors used.''' + cpus = defaultdict(list) + for t in tasks: + cpus[t.cpu].append(t) + + if self.way_first: + # Way first means maximize ways + pages_per_color = min(self.ways, pages_needed) + colors_per_task = int(ceil(pages_needed/pages_per_color)) + else: + # Color first means maximize colors + colors_per_task = min(self.colors, pages_needed) + pages_per_color = int(ceil(pages_needed/colors_per_task)) + + curr_color = 0 + for cpu, tasks in cpus.iteritems(): + # All tasks on a CPU have the same coloring scheme + cpu_colors = defaultdict(int) + for _ in xrange(colors_per_task): + curr_color = (curr_color + 1) % self.colors + cpu_colors[curr_color] = pages_per_color + + for t in tasks: + t.colors = cpu_colors + +class RandomColorScheme(ColorScheme): + def color(self, tasks, pages_needed): + '''Pages are placed randomly in the cache''' + if pages_needed >= self.ways * self.colors: + raise Exception("Too many pages: %d > %d * %d" % + (pages_needed, self.ways, self.colors)) + + for t in tasks: + t.colors = defaultdict(int) + + for _ in xrange(pages_needed): + # Find the next color with available ways + while True: + next_color = randint(0, self.colors - 1) + if t.colors[next_color] != self.ways: + break + + t.colors[next_color] += 1; + +class EvilColorScheme(ColorScheme): + def color(self, tasks, pages_needed): + '''All tasks' working sets are placed at the front of the cache''' + colors = defaultdict(int) + color = 0 + + while pages_needed > 0: + colors[color] = min(self.ways, pages_needed) + pages_needed -= colors[color] + + color += 1 + + for t in tasks: + t.colors = colors + + +INFO_FIELDS = ['cache', 'line', 'page', 'ways', 'sets', 'colors'] +INFO_PROC = '/proc/sys/litmus/color/cache_info' + +# Build parsing regex +FIELD_REGEX = r"(?:.*?{0}.*?(?P<{0}>\d+).*?)" +INFO_REGEX = "|".join([FIELD_REGEX.format(field) for field in INFO_FIELDS]) +INFO_REGEX = r"(?:{})*".format(INFO_REGEX) + +# To fill up this +CacheInfo = namedtuple('CacheInfo', INFO_FIELDS) + +def get_cache_info(): + if os.path.exists(INFO_PROC): + with open(INFO_PROC, 'r') as f: + data = f.read() + values = re.search(INFO_REGEX, data, re.M|re.I|re.S).groupdict() + return CacheInfo(**values) + else: + return None diff --git a/gen/generator.py b/gen/generator.py index f35a22b..1205490 100644 --- a/gen/generator.py +++ b/gen/generator.py @@ -51,38 +51,44 @@ class Generator(object): This class also performs checks of parameter values and prints out help. All subclasses must implement _create_exp. ''' - def __init__(self, scheduler, templates, options, params): + def __init__(self, name, templates, options, params): + self.__make_defaults(params) + self.options = self.__make_options(params) + options self.__setup_params(params) self.params = params self.template = "\n".join([TP_RM] + templates) - self.scheduler = scheduler - - def __make_options(self, params): - '''Return generic Litmus options.''' + self.scheduler = name - # Guess defaults using the properties of this computer + def __make_defaults(self, params): + '''Guess defaults using the properties of this computer''' if 'cpus' in params: - cpus = min(map(int, params['cpus'])) + self.cpus = min(map(int, params['cpus'])) else: - cpus = num_cpus() + self.cpus = num_cpus() try: config = get_config_option("RELEASE_MASTER") and True except: config = False - release_master = list(set([False, config])) + self.release_master = list(set([False, config])) - return [GenOption('tasks', int, range(cpus, 5*cpus, cpus), - 'Number of tasks per experiment.'), - GenOption('cpus', int, [cpus], + def __make_options(self, params): + '''Return generic Litmus options.''' + return [GenOption('num_tasks', int, + range(self.cpus, 5*self.cpus, self.cpus), + 'Number of tasks per experiment.'), + GenOption('cpus', int, [self.cpus], 'Number of processors on target system.'), - GenOption('release_master', [True,False], release_master, + GenOption('release_master', [True,False], self.release_master, 'Redirect release interrupts to a single CPU.'), GenOption('duration', float, [30], 'Experiment duration.')] + def _num_cpus(self): + return self.cpus + @staticmethod def _dist_option(name, default, distribution, help): return GenOption(name, [str, float, type([])] + distribution.keys(), @@ -119,6 +125,9 @@ class Generator(object): max_util) return ts + def _out_dir(self): + return self.out_dir + def _write_schedule(self, params): '''Write schedule file using current template for @params.''' sched_file = self.out_dir + "/" + DEFAULTS['sched_file'] diff --git a/gen/mc_generators.py b/gen/mc_generators.py index d6d8d90..bbb1ab9 100644 --- a/gen/mc_generators.py +++ b/gen/mc_generators.py @@ -1,5 +1,6 @@ import gen.rv as rv +from color import get_cache_info,CacheInfo,BlockColorScheme,RandomColorScheme,EvilColorScheme from common import try_get_config_option from gen.generator import GenOption,Generator,NAMED_UTILIZATIONS,NAMED_PERIODS @@ -16,11 +17,11 @@ TP_BASE = """#for $t in $lvl{0} TP_LVLA = """#if $lvla /proc/litmus/plugins/MC-CE/ce_file{ #for $t in $lvla -$t.cpu, $t.id, $t.budget +$t.cpu, $t.lvla_id, $t.budget #end for } #end if -""" + TP_BASE.format("a", "-i $t.id -p $t.cpu ") +""" + TP_BASE.format("a", "-i $t.lvla_id -p $t.cpu ") TP_LVLB = TP_BASE.format("b", "-p $t.cpu ") TP_LVLC = TP_BASE.format("c", "") TP_LVLD = """#if $be @@ -46,10 +47,12 @@ MC_OPT = 'PLUGIN_MC' LEVELS = 3 class McGenerator(Generator): - def __init__(self, params = {}): - super(McGenerator, self).__init__("MC", - [TP_LVLA, TP_LVLB, TP_LVLC, TP_LVLD], - self.__make_options(), + def __init__(self, name="MC", + templates=[TP_LVLA, TP_LVLB, TP_LVLC, TP_LVLD], + options=[], params={}): + super(McGenerator, self).__init__(name, + templates, + self.__make_options() + options, params) def __make_options(self): @@ -92,34 +95,46 @@ class McGenerator(Generator): 'Level-C task utilizations (at level C).'), Generator._dist_option('shares', ['fair'], NAMED_SHARES, - 'Distribution of actual utilizations.')] + 'Distribution of runtime utilizations.')] def __partition_worst_fit(self, params, ts): + cpus = int(params['cpus']) + if params['release_master']: + # No level B on the release master + cpus -= 1 + # Partition using worst-fit for most even distribution - utils = [0]*int(params['cpus']) - tasks = [0]*int(params['cpus']) + utils = [0]*cpus + tasks = [0]*cpus for t in ts: t.cpu = utils.index(min(utils)) - t.id = tasks[t.cpu] + t.lvla_id = tasks[t.cpu] utils[t.cpu] += t.utilization() tasks[t.cpu] += 1 + # Increment by one so release master has no tasks + t.cpu += 1 + def __adjust(self, params, level): # Adjust for levels which aren't used - ldiff = LEVELS - params['levels'] - shares = self.shares[ldiff:] - level -= ldiff + num = params['levels'] + shares = list(self.shares) + if num < 4: + shares.pop() + if num < 3: + shares.pop(0) + level -= 1 return shares, level def __get_max_util(self, params, level): shares, level = self.__adjust(params, level) - return float(shares[level]) / sum(shares[:level]) * params['cpus'] + return float(shares[level]) / sum(shares[:level+1]) * params['cpus'] def __get_scale(self, params, level): shares, level = self.__adjust(params, level) - return float(shares[level]) / sum(shares) + return float(sum(shares[:level+1])) / sum(shares) def __create_lvla_sched(self, params): if params['levels'] < 3: @@ -148,11 +163,13 @@ class McGenerator(Generator): utils = self._create_dist('utilization', params['b_utils'], NAMED_UTILIZATIONS) - # Level-A is present, b must be harmonic with lvla hyperperiod + if params['levels'] > 2: + # Level-A is present, b must be harmonic with lvla hyperperiod plist = [params['a_hyperperiod']*2**x for x in xrange(0, 4)] periods = rv.uniform_choice(plist) else: + # Level b can have whatever periods it wants periods = self._create_dist('period', params['b_periods'], NAMED_PERIODS) max_util = self.__get_max_util(params, 1) @@ -171,6 +188,9 @@ class McGenerator(Generator): return self._create_taskset(params, periods, utils, max_util) + def _customize(self, task_system, params): + pass + def _create_exp(self, params): # Ugly way of doing it self.shares = self._create_dist('shares', params['shares'], @@ -193,13 +213,165 @@ class McGenerator(Generator): scales = [] for index, level in enumerate('abc'): - scales += [('scale%s' % level, self.__get_scale(params, index))] + if tasks['lvl%s'%level]: + scales += [('scale%s' % level, self.__get_scale(params, index))] schedule_variables = params.items() + tasks.items() + scales param_variables = params.items() + [('config-options',conf_options)] + self._customize(tasks, params) + self._write_schedule(dict(schedule_variables)) self._write_params(dict(param_variables)) # Ugly del(self.shares) + + +# Types are base, locking, preemptive +# This sets up the scheduler to create each +TP_TYPE = """#if $type != 'unmanaged' +/proc/sys/litmus/color/lock_cache{1} +#else +/proc/sys/litmus/color/lock_cache{0} +#end if +#if $type == 'scheduling' +/proc/sys/litmus/color/preempt_cache{1} +#else +/proc/sys/litmus/color/preempt_cache{0} +#end if""" + +# Use special spin for color tasks +TP_COLOR_BASE = """colorspin -y $t.id -x $t.colorcsv """ + +TP_COLOR_B = TP_BASE.format("b", TP_COLOR_BASE + "-p $t.cpu ") +TP_COLOR_C = TP_BASE.format("c", TP_COLOR_BASE) + +# Not even sure job splitting is still possible +TP_CHUNK = """#if $chunk_size > 0 +/proc/sys/litmus/color/chunk_size{$chunk_size} +#end if""" + +COLOR_TYPES = ['scheduling', 'locking', 'unmanaged'] + +class ColorMcGenerator(McGenerator): + def __init__(self, params = {}): + super(ColorMcGenerator, self).__init__("COLOR-MC", + templates=[TP_TYPE, TP_CHUNK, TP_COLOR_B, TP_COLOR_C], + options=self.__make_options(), + params=self.__extend_params(params)) + + def __extend_params(self, params): + '''Add in fixed mixed-criticality parameters.''' + params['levels'] = 2 + params['be'] = False + params['redirect'] = True + params['release_master'] = True + params['timer_merging'] = False + params['slack_stealing'] = False + + # Set these just so they aren't displayed to the user + params['d_nice'] = False + params['d_fifo'] = False + params['a_hyperperiod'] = 0 + params['a_utils'] = 'bimo-light' + + return params + + def __make_system_info(self): + info = get_cache_info() + + if not info: + # Pick something semi-reasonable. these will work (wastefully) on + # many machines. The plugin will pidgeon hole pages into these + # specific areas, so even if the cache which runs this code has + # more ways and/or colors than these, it will run as though these + # are its parameters. This is sufficient for most testing + ways = 8 + colors = 8 + page = 4096 + line = 64 + + cache = ways * colors * page + sets = cache / (line * ways) + + info = CacheInfo(cache, line=line, page=page, + ways=ways, sets=sets, colors=colors) + + self.system = info + + def __make_options(self): + self.__make_system_info() + + return [GenOption('type', COLOR_TYPES, COLOR_TYPES, + 'Cache management type.'), + GenOption('chunk_size', float, [0], 'Chunk size.'), + GenOption('ways', int, [self.system.ways], 'Ways (associativity).'), + GenOption('colors', int, [self.system.colors], + 'System colors (cache size / ways).'), + GenOption('page_size', int, [self.system.page], + 'System page size.'), + GenOption('wss', [float, int], [.5], + 'Task working set sizes. Can be expressed as a fraction ' + + 'of the cache.'), + GenOption('align_unmanaged', [True, False], [True], + 'Place all working sets of unmanaged task systems in '+ + 'the same location, for maximum interference.')] + + + def __get_wss_pages(self, params): + '''Return the number of pages in a single task's working set.''' + cache_pages = params['ways'] * params['colors'] + + wss = params['wss'] + if type(wss) == float and wss <= 1.0: + # Can express wss as fraction of total cache + pages = int(wss*cache_pages) + else: + if wss < params['page_size']: + raise Exception(('Cannot have working set (%d) smaller than ' + 'a page (%d).') % (wss, params['page_size'])) + + pages = wss / params['page_size'] + + if pages > cache_pages: + raise Exception('WSS (%d) larger than the cache!' % (wss)) + + return pages + + + def __make_csv(self, task): + '''Write task.colors into a csv file, stored as task.colorcsv.''' + fname = 'colors%d.csv' % task.id + task.colorcsv = fname + + with open(self._out_dir() + "/" + fname, 'w') as f: + for color, replicas in task.colors.iteritems(): + f.write("%d, %d\n" % (color, replicas)) + + def _customize(self, task_system, params): + '''Add coloring properties to the mixed-criticality task system.''' + # Every task needs a unique id for coloring and wss walk order + all_tasks = [] + for level, tasks in task_system.iteritems(): + all_tasks += tasks + for i, task in enumerate(all_tasks): + task.id = i + + c = params['colors'] + w = params['ways'] + + if params['type'] == 'unmanaged': + hrt_colorer = EvilColorScheme(c, w) + srt_colorer = hrt_colorer + else: + srt_colorer = RandomColorScheme(c, w) + hrt_colorer = BlockColorScheme(c, w, way_first=True) + + pages_needed = self.__get_wss_pages(params) + + hrt_colorer.color(task_system['lvlb'], pages_needed) + srt_colorer.color(task_system['lvlc'], pages_needed) + + for t in all_tasks: + self.__make_csv(t) -- cgit v1.2.2