From 39020cf5ae3030bc15035925a0c72eb44eea67b7 Mon Sep 17 00:00:00 2001 From: Jonathan Herman Date: Thu, 7 Feb 2013 11:21:23 -0500 Subject: Added gen_exps.py script. --- common.py | 26 +++++- config/config.py | 16 ++-- gen/__init__.py | 0 gen/dp.py | 33 +++++++ gen/generators.py | 257 +++++++++++++++++++++++++++++++++++++++++++++++++++ gen/rv.py | 86 +++++++++++++++++ gen_exps.py | 98 ++++++++++++++++++++ parse/ft.py | 4 +- parse/sched.py | 2 +- parse/tuple_table.py | 9 ++ parse_exps.py | 13 +-- run_exps.py | 1 + 12 files changed, 525 insertions(+), 20 deletions(-) create mode 100644 gen/__init__.py create mode 100644 gen/dp.py create mode 100644 gen/generators.py create mode 100644 gen/rv.py mode change 100644 => 100755 gen_exps.py diff --git a/common.py b/common.py index 0990cfe..ad3c418 100644 --- a/common.py +++ b/common.py @@ -1,9 +1,14 @@ +import os +import re +import subprocess import sys + from collections import defaultdict from textwrap import dedent def get_executable(prog, hint, optional=False): - import os + '''Search for @prog in system PATH. Print @hint if no binary is found.''' + def is_exe(fpath): return os.path.isfile(fpath) and os.access(fpath, os.X_OK) @@ -19,12 +24,29 @@ def get_executable(prog, hint, optional=False): if not optional: sys.stderr.write("Cannot find executable '%s' in PATH. This is a part " - "of '%s' which should be added to PATH to run." % + "of '%s' which should be added to PATH to run.\n" % (prog, hint)) sys.exit(1) else: return None +def get_config_option(option): + '''Search for @option in installed kernel config (if present). + Raise an IOError if the kernel config isn't found in /boot/.''' + uname = subprocess.check_output(["uname", "-r"])[-1] + fname = "/boot/config-%s" % uname + + if os.path.exists(fname): + config_regex = "^CONFIG_{}=(?P.*)$".format(option) + match = re.search(config_regex, open(fname, 'r').read()) + if not match: + return None + else: + return match.group("val") + + else: + raise IOError("No config file exists!") + def recordtype(typename, field_names, default=0): ''' Mutable namedtuple. Recipe from George Sakkis of MIT.''' field_names = tuple(map(str, field_names)) diff --git a/config/config.py b/config/config.py index 3282705..d463999 100644 --- a/config/config.py +++ b/config/config.py @@ -17,18 +17,20 @@ BINS = {'rtspin' : get_executable('rtspin', 'liblitmus'), FILES = {'ft_data' : 'ft.bin', 'linux_data' : 'trace.dat', 'sched_data' : 'st-{}.bin', - 'log_data' : 'trace.slog',} + 'log_data' : 'trace.slog'} '''Default parameter names in params.py.''' -PARAMS = {'sched' : 'scheduler', - 'dur' : 'duration', - 'kernel' : 'uname', - 'cycles' : 'cpu-frequency'} +# TODO: add check for config options +PARAMS = {'sched' : 'scheduler', # Scheduler used by run_exps + 'dur' : 'duration', # Duration of tests in run_exps + 'kernel' : 'uname', # Regex of required OS name in run_exps + 'cycles' : 'cpu-frequency', # Frequency run_exps was run with + 'tasks' : 'tasks' # Number of tasks + } -'''Default values for program parameters.''' +'''Default values for program options.''' DEFAULTS = {'params_file' : 'params.py', 'sched_file' : 'sched.py', - 'exps_file' : 'exps.py', 'duration' : 10, 'spin' : 'rtspin', 'cycles' : 2000} diff --git a/gen/__init__.py b/gen/__init__.py new file mode 100644 index 0000000..e69de29 diff --git a/gen/dp.py b/gen/dp.py new file mode 100644 index 0000000..0ac8cce --- /dev/null +++ b/gen/dp.py @@ -0,0 +1,33 @@ +from __future__ import division + +class DesignPointGenerator(object): + '''Iterates over all combinations of values specified in options. + Shamelessly stolen (and simplified) from bcw.''' + def __init__(self, options): + self.point_idx = 0 # Current point + self.options = options + self.total = 1 + for x in options.itervalues(): + self.total *= len(x) + + def __iter__(self): + return self + + def next(self): + while True: + if self.point_idx == self.total: + raise StopIteration + else: + point = {} + + divisor = 1 + for key in sorted(self.options.keys()): + size = len(self.options[key]) + + option_idx = int(self.point_idx / divisor) % size + point[key] = self.options[key][option_idx] + + divisor *= size + self.point_idx += 1 + + return point diff --git a/gen/generators.py b/gen/generators.py new file mode 100644 index 0000000..2fc77a7 --- /dev/null +++ b/gen/generators.py @@ -0,0 +1,257 @@ +from Cheetah.Template import Template +from collections import namedtuple +from common import get_config_option +from config.config import DEFAULTS +from gen.dp import DesignPointGenerator +from parse.tuple_table import ColMap + +import gen.rv as rv +import os +import random +import run.litmus_util as lu +import schedcat.generator.tasks as tasks +import shutil as sh + +NAMED_PERIODS = { + 'harmonic' : rv.uniform_choice([25, 50, 100, 200]), + 'uni-short' : rv.uniform_int( 3, 33), + 'uni-moderate' : rv.uniform_int(10, 100), + 'uni-long' : rv.uniform_int(50, 250), +} + +NAMED_UTILIZATIONS = { + 'uni-very-light': rv.uniform(0.0001, 0.001), + 'uni-light' : rv.uniform(0.001, 0.1), + 'uni-medium' : rv.uniform( 0.1, 0.4), + 'uni-heavy' : rv.uniform( 0.5, 0.9), + + 'exp-light' : rv.exponential(0, 1, 0.10), + 'exp-medium' : rv.exponential(0, 1, 0.25), + 'exp-heavy' : rv.exponential(0, 1, 0.50), + + 'bimo-light' : rv.multimodal([(rv.uniform(0.001, 0.5), 8), + (rv.uniform( 0.5, 0.9), 1)]), + 'bimo-medium' : rv.multimodal([(rv.uniform(0.001, 0.5), 6), + (rv.uniform( 0.5, 0.9), 3)]), + 'bimo-heavy' : rv.multimodal([(rv.uniform(0.001, 0.5), 4), + (rv.uniform( 0.5, 0.9), 5)]), +} + +# Cheetah templates for schedule files +TP_CLUSTER = "plugins/C-EDF/cluster{$level}" +TP_RM = """#if $release_master +release_master{1} +#end if""" +TP_TBASE = """#for $t in $task_set +{}$t.cost $t.period +#end for""" +TP_PART_TASK = TP_TBASE.format("-p $t.cpu ") +TP_GLOB_TASK = TP_TBASE.format("") + +GenOption = namedtuple('GenOption', ['name', 'types', 'default', 'help']) + +class BaseGenerator(object): + '''Creates sporadic task sets with the most common Litmus options.''' + def __init__(self, name, templates, options, params): + self.options = self.__make_options() + options + + self.__setup_params(params) + + self.params = params + self.template = "\n".join([TP_RM] + templates) + self.name = name + + def __make_options(self): + '''Return generic Litmus options.''' + + # Guess defaults using the properties of this computer + cpus = lu.num_cpus() + try: + config = get_config_option("RELEASE_MASTER") and True + except: + config = False + release_master = list(set([False, config])) + + list_types = [str, float, type([])] + + return [GenOption('cpus', int, [cpus], + 'Number of processors on target system.'), + GenOption('num_tasks', int, range(cpus, 5*cpus, cpus), + 'Number of tasks per experiment.'), + GenOption('utils', list_types + NAMED_UTILIZATIONS.keys(), + ['uni-medium'],'Task utilization distributions.'), + GenOption('periods', list_types + NAMED_PERIODS.keys(), + ['harmonic'], 'Task period distributions.'), + GenOption('release_master', [True,False], release_master, + 'Redirect release interrupts to a single CPU.'), + GenOption('duration', float, [30], 'Experiment duration.')] + + def __create_dist(self, name, value, named_dists): + '''Attempt to create a distribution representing the data in @value. + If @value is a string, use it as a key for @named_dists.''' + name = "%s distribution" % name + # A list of values + if type(value) == type([]): + map(lambda x : self.__check_value(name, x, [float, int]), value) + return rv.uniform_choice(value) + elif type(value) in [float, int]: + return lambda : value + elif value in named_dists: + return named_dists[value] + else: + raise ValueError("Invalid %s value: %s" % (name, value)) + + def __create_exp(self, exp_params, out_dir): + '''Create a single experiment with @exp_params in @out_dir.''' + pdist = self.__create_dist('period', + exp_params['periods'], + NAMED_PERIODS) + udist = self.__create_dist('utilization', + exp_params['utils'], + NAMED_UTILIZATIONS) + tg = tasks.TaskGenerator(period=pdist, util=udist) + + ts = [] + tries = 0 + while len(ts) != exp_params['num_tasks'] and tries < 5: + ts = tg.make_task_set(max_tasks = exp_params['num_tasks']) + tries += 1 + if len(ts) != exp_params['num_tasks']: + print("Failed to create task set with parameters: %s" % exp_params) + + self._customize(ts, exp_params) + + sched_file = out_dir + "/" + DEFAULTS['sched_file'] + with open(sched_file, 'wa') as f: + exp_params['task_set'] = ts + f.write(str(Template(self.template, searchList=[exp_params]))) + + del exp_params['task_set'] + exp_params_file = out_dir + "/" + DEFAULTS['params_file'] + with open(exp_params_file, 'wa') as f: + exp_params['scheduler'] = 'CEDF' + f.write(str(exp_params)) + + def __setup_params(self, params): + '''Set default parameter values and check that values are valid.''' + for option in self.options: + if option.name not in params: + params[option.name] = option.default + params[option.name] = self._check_value(option.name, + option.types, + params[option.name]) + return params + + + def _check_value(self, name, types, val): + '''Raise an exception if the value of type of @val is not specified + in @types. Returns a copy of @val with strings converted to raw + Python types, if possible.''' + if types == float: + types = [float, int] + if type(types) != type([]): + types = [types] + if type(val) != type([]): + val = [val] + + retval = [] + for v in val: + # Has to be a better way to find this + v = False if v in ['f', 'False', 'false', 'n', 'no'] else v + v = True if v in ['t', 'True', 'true', 'y', 'yes'] else v + + if type(v) not in types and v not in types: + # Try and convert v to one of the specified types + parsed = None + for t in types: + try: + parsed = t(v) + break + except: + pass + + if parsed: + retval += [parsed] + else: + raise TypeError("Invalid %s value: '%s'" % (name, v)) + else: + retval += [v] + return retval + + def _customize(self, taskset, exp_params): + '''Configure a generated taskset with extra parameters.''' + pass + + def create_exps(self, out_dir, force): + '''Create experiments for all possible combinations of params in + @out_dir. Overwrite existing files if @force is True.''' + col_map = ColMap() + + # Track changing values so only relevant parameters are included + # in directory names + for dp in DesignPointGenerator(self.params): + for k, v in dp.iteritems(): + col_map.try_add(k, v) + + for dp in DesignPointGenerator(self.params): + dir_leaf = "sched=%s_%s" % (self.name, col_map.get_encoding(dp)) + dir_path = "%s/%s" % (out_dir, dir_leaf.strip('_')) + + if os.path.exists(dir_path): + if force: + sh.rmtree(dir_path) + else: + print("Skipping existing experiment: '%s'" % dir_path) + continue + + os.mkdir(dir_path) + + self.__create_exp(dp, dir_path) + + def print_help(self): + s = str(Template("""Generator $name: + #for $o in $options + $o.name -- $o.help + \tDefault: $o.default + \tAllowed: $o.types + #end for""", searchList=vars(self))) + + # Has to be an easier way to print this out... + for line in s.split("\n"): + res = [] + i = 0 + for word in line.split(", "): + i+= len(word) + res += [word] + if i > 80: + print ", ".join(res[:-1]) + res = ["\t\t "+res[-1]] + i = line.index("'") + print ", ".join(res) + +class PartitionedGenerator(BaseGenerator): + def __init__(self, name, templates, options, params): + super(PartitionedGenerator, self).__init__(name, + templates + [TP_PART_TASK], options, params) + + def _customize(self, taskset, exp_params): + start = 1 if exp_params['release_master'] else 0 + # Random partition for now: could do a smart partitioning + for t in taskset: + t.cpu = random.randint(start, exp_params['cpus'] - 1) + +class PedfGenerator(PartitionedGenerator): + def __init__(self, params={}): + super(PedfGenerator, self).__init__("P-EDF", [], [], params) + +class CedfGenerator(PartitionedGenerator): + LEVEL_OPTION = GenOption('level', ['L2', 'L3', 'All'], ['L2'], + 'Cache clustering level.',) + + def __init__(self, params={}): + super(CedfGenerator, self).__init__("C-EDF", [TP_CLUSTER], + [CedfGenerator.LEVEL_OPTION], params) + +class GedfGenerator(BaseGenerator): + def __init__(self, params={}): + super(GedfGenerator, self).__init__("G-EDF", [TP_GLOB_TASK], [], params) diff --git a/gen/rv.py b/gen/rv.py new file mode 100644 index 0000000..e6f4d0f --- /dev/null +++ b/gen/rv.py @@ -0,0 +1,86 @@ +from __future__ import division +import random + +def uniform_int(minval, maxval): + "Create a function that draws ints uniformly from {minval, ..., maxval}" + def _draw(): + return random.randint(minval, maxval) + return _draw + +def uniform(minval, maxval): + "Create a function that draws floats uniformly from [minval, maxval]" + def _draw(): + return random.uniform(minval, maxval) + return _draw + +def bernoulli(p): + "Create a function that flips a weight coin with probability p" + def _draw(): + return random.random() < p + return _draw + +def uniform_choice(choices): + "Create a function that draws uniformly elements from choices" + selector = uniform_int(0, len(choices) - 1) + def _draw(): + return choices[selector()] + return _draw + +def truncate(minval, maxval): + def _limit(fun): + def _f(*args, **kargs): + val = fun(*args, **kargs) + return min(maxval, max(minval, val)) + return _f + return _limit + +def redraw(minval, maxval): + def _redraw(dist): + def _f(*args, **kargs): + in_range = False + while not in_range: + val = dist(*args, **kargs) + in_range = minval <= val <= maxval + return val + return _f + return _redraw + +def exponential(minval, maxval, mean, limiter=redraw): + """Create a function that draws floats from an exponential + distribution with expected value 'mean'. If a drawn value is less + than minval or greater than maxval, then either another value is + drawn (if limiter=redraw) or the drawn value is set to minval or + maxval (if limiter=truncate).""" + def _draw(): + return random.expovariate(1.0 / mean) + return limiter(minval, maxval)(_draw) + +def multimodal(weighted_distributions): + """Create a function that draws values from several distributions + with probability according to the given weights in a list of + (distribution, weight) pairs.""" + total_weight = sum([w for (d, w) in weighted_distributions]) + selector = uniform(0, total_weight) + def _draw(): + x = selector() + wsum = 0 + for (d, w) in weighted_distributions: + wsum += w + if wsum >= x: + return d() + assert False # should never drop off + return _draw + +def uniform_slack(min_slack_ratio, max_slack_ratio): + """Choose deadlines uniformly such that the slack + is within [cost + min_slack_ratio * (period - cost), + cost + max_slack_ratio * (period - cost)]. + + Setting max_slack_ratio = 1 implies constrained deadlines. + """ + def choose_deadline(cost, period): + slack = period - cost + earliest = slack * min_slack_ratio + latest = slack * max_slack_ratio + return cost + random.uniform(earliest, latest) + return choose_deadline diff --git a/gen_exps.py b/gen_exps.py old mode 100644 new mode 100755 index e69de29..e4e8187 --- a/gen_exps.py +++ b/gen_exps.py @@ -0,0 +1,98 @@ +#!/usr/bin/env python +from __future__ import print_function + +import os +import re +import shutil as sh + +from gen.generators import GedfGenerator,PedfGenerator,CedfGenerator +from optparse import OptionParser + +# There has to be a better way to do this... +GENERATORS = {'C-EDF':CedfGenerator, + 'P-EDF':PedfGenerator, + 'G-EDF':GedfGenerator} + +def parse_args(): + parser = OptionParser("usage: %prog [options] [files...] " + "[generators...] [param=val[,val]...]") + + parser.add_option('-o', '--out-dir', dest='out_dir', + help='directory for data output', + default=("%s/exps"%os.getcwd())) + parser.add_option('-f', '--force', action='store_true', default=False, + dest='force', help='overwrite existing data') + parser.add_option('-l', '--list-generators', dest='list_gens', + help='list allowed generators', action='store_true', + default=False) + parser.add_option('-d', '--describe-generators', metavar='generator[,..]', + dest='described', default=None, + help='describe parameters for generator(s)') + + return parser.parse_args() + +def load_file(fname): + with open(fname, 'r') as f: + data = f.read().strip() + try: + values = eval(data) + if 'generator' not in values: + raise ValueError() + generator = values['generator'] + del values['generator'] + return generator, values + except: + raise IOError("Invalid generation file: %s" % fname) + +def main(): + opts, args = parse_args() + + # Print generator information on the command line + if opts.list_gens: + print(", ".join(GENERATORS.keys())) + if opts.described != None: + for generator in opts.described.split(','): + if generator not in GENERATORS: + print("No generator '%s'" % generator) + else: + GENERATORS[generator]().print_help() + if opts.list_gens or opts.described: + return 0 + + params = filter(lambda x : re.match("\w+=\w+", x), args) + + # Ensure some generator is loaded + args = list(set(args) - set(params)) + #TODO: get every loaded plugin, try and use that generator + args = args or ['C-EDF', 'G-EDF', 'P-EDF'] + + # Split into files to load, named generators + files = filter(os.path.exists, args) + gen_list = list(set(args) - set(files)) + + # Parse all specified parameters to be applied to every experiment + global_params = dict(map(lambda x : tuple(x.split("=")), params)) + for k, v in global_params.iteritems(): + global_params[k] = v.split(',') + + exp_sets = map(load_file, files) + exp_sets += map(lambda x: (x, {}), gen_list) + + if opts.force and os.path.exists(opts.out_dir): + sh.rmtree(opts.out_dir) + if not os.path.exists(opts.out_dir): + os.mkdir(opts.out_dir) + + for gen_name, gen_params in exp_sets: + if gen_name not in GENERATORS: + raise ValueError("Invalid generator name: %s" % gen_name) + + print("Creating experiments using %s generator..." % gen_name) + + params = dict(gen_params.items() + global_params.items()) + generator = GENERATORS[gen_name](params) + + generator.create_exps(opts.out_dir, opts.force) + +if __name__ == '__main__': + main() diff --git a/parse/ft.py b/parse/ft.py index a6596b7..5293b00 100644 --- a/parse/ft.py +++ b/parse/ft.py @@ -47,12 +47,12 @@ def parse_overhead(result, overhead_bin, overhead, cycles, out_dir, err_file): def sort_ft(ft_file, err_file, out_dir): '''Create and return file with sorted overheads from @ft_file.''' - out_fname = "{}/{}".format(out_dir, FT_SORTED_NAME) + out_fname = "{}/{}".format("%s/%s" % (os.getcwd(), out_dir), FT_SORTED_NAME) # Sort happens in-place sh.copyfile(ft_file, out_fname) cmd = [conf.BINS['ftsort'], out_fname] - ret = subprocess.call(cmd, cwd=out_dir, stderr=err_file, stdout=err_file) + ret = subprocess.call(cmd, cwd="%s/%s" % (os.getcwd(), out_dir), stderr=err_file, stdout=err_file) if ret: raise Exception("Sort failed with command: %s" % " ".join(cmd)) diff --git a/parse/sched.py b/parse/sched.py index 512ac73..ba0df5e 100644 --- a/parse/sched.py +++ b/parse/sched.py @@ -146,7 +146,7 @@ def extract_sched_data(result, data_dir, work_dir): bin_files = conf.FILES['sched_data'].format(".*") output_file = "%s/out-st" % work_dir - bins = [f for f in os.listdir(data_dir) if re.match(bin_files, f)] + bins = ["%s/%s" % (data_dir,f) for f in os.listdir(data_dir) if re.match(bin_files, f)] if not len(bins): return diff --git a/parse/tuple_table.py b/parse/tuple_table.py index e5dc39b..86006d2 100644 --- a/parse/tuple_table.py +++ b/parse/tuple_table.py @@ -23,6 +23,15 @@ class ColMap(object): key += (kv[col],) return key + def get_encoding(self, kv): + def escape(val): + return str(val).replace("_", "-").replace("=", "-") + vals = [] + for key in self.col_list: + k, v = escape(key), escape(kv[key]) + vals += ["%s=%s" % (k, v)] + return "_".join(vals) + def __contains__(self, col): return col in self.rev_map diff --git a/parse_exps.py b/parse_exps.py index c8cd8b1..f7e1342 100755 --- a/parse_exps.py +++ b/parse_exps.py @@ -18,6 +18,8 @@ def parse_args(): # TODO: convert data-dir to proper option, clean 'dest' options parser = OptionParser("usage: %prog [options] [data_dir]...") + print("default to no params.py") + parser.add_option('-o', '--out', dest='out', help='file or directory for data output', default='parse-data') parser.add_option('-c', '--clean', action='store_true', default=False, @@ -41,19 +43,14 @@ def get_exp_params(data_dir, col_map): if not os.path.isfile: raise Exception("No param file '%s' exists!" % param_file) - # Ignore 'magic' parameters used by these scripts params = load_params(param_file) - for ignored in conf.PARAMS.itervalues(): - # With the exception of cycles which is used by overhead parsing - if ignored in params and ignored != conf.PARAMS['cycles']: - params.pop(ignored) # Store parameters in col_map, which will track which parameters change # across experiments for key, value in params.iteritems(): col_map.try_add(key, value) - # Cycles must be present + # Cycles must be present for feather-trace measurement parsing if conf.PARAMS['cycles'] not in params: params[conf.PARAMS['cycles']] = conf.DEFAULTS['cycles'] @@ -72,10 +69,10 @@ def load_exps(exp_dirs, col_map, clean): # Used to store error output and debugging info work_dir = data_dir + "/tmp" + if os.path.exists(work_dir) and clean: + sh.rmtree(work_dir) if not os.path.exists(work_dir): os.mkdir(work_dir) - elif clean: - sh.rmtree(work_dir) params = get_exp_params(data_dir, col_map) diff --git a/run_exps.py b/run_exps.py index cc348ec..8fd9ed2 100755 --- a/run_exps.py +++ b/run_exps.py @@ -117,6 +117,7 @@ def load_experiment(sched_file, scheduler, duration, param_file, out_dir): # Cycles is saved here for accurate overhead calculations later out_params = dict(params.items() + [(conf.PARAMS['sched'], scheduler), + (conf.PARAMS['tasks'], len(schedule['spin'])), (conf.PARAMS['dur'], duration), (conf.PARAMS['cycles'], lu.cpu_freq())]) with open("%s/%s" % (out_dir, conf.DEFAULTS['params_file']), 'w') as f: -- cgit v1.2.2