diff options
Diffstat (limited to 'bestflags')
-rw-r--r-- | bestflags/iterative_elimination.py | 178 | ||||
-rw-r--r-- | bestflags/testing_batch.py | 153 |
2 files changed, 323 insertions, 8 deletions
diff --git a/bestflags/iterative_elimination.py b/bestflags/iterative_elimination.py new file mode 100644 index 00000000..618917e2 --- /dev/null +++ b/bestflags/iterative_elimination.py @@ -0,0 +1,178 @@ +# Copyright (c) 2013 The Chromium OS Authors. All rights reserved. +# Use of this source code is governed by a BSD-style license that can be +# found in the LICENSE file. + +"""Iterative flags elimination. + +Part of the Chrome build flags optimization. + +This module implements the flag iterative elimination algorithm (IE) adopted +from the paper +Z. Pan et al. Fast and Effective Orchestration of Compiler Optimizations for +Automatic Performance Tuning. + +IE begins with the base line that turns on all the optimizations flags and +setting the numeric flags to their highest values. IE turns off the one boolean +flag or lower the value of a numeric flag with the most negative effect from the +baseline. This process repeats with all remaining flags, until none of them +causes performance degradation. The complexity of IE is O(n^2). + +For example, -fstrict-aliasing and -ftree-vectorize. The base line is +b=[-fstrict-aliasing, -ftree-vectorize]. The two tasks in the first iteration +are t0=[-fstrict-aliasing] and t1=[-ftree-vectorize]. The algorithm compares b +with t0 and t1, respectively, and see whether setting the numeric flag with a +lower value or removing the boolean flag -fstrict-aliasing produce a better +fitness value. +""" + +__author__ = 'yuhenglong@google.com (Yuheng Long)' + +import flags +from generation import Generation +import task + + +def _DecreaseFlag(flags_dict, spec): + """Decrease the value of the flag that has the specification spec. + + If the flag that contains the spec is a boolean flag, it is eliminated. + Otherwise the flag is a numeric flag, its value will be reduced by one. + + Args: + flags_dict: The dictionary containing the original flags whose neighbors are + to be explored. + spec: The spec in the flags_dict is to be changed. + + Returns: + Dictionary of neighbor flag that is only different from the original + dictionary by the spec. + """ + + # The specification must be held by one of the flags. + assert spec in flags_dict + + # The results this method returns. + results = flags_dict.copy() + + # This method searches for a pattern [start-end] in the spec. If the spec + # contains this pattern, it is a numeric flag. Otherwise it is a boolean flag. + # For example, -finline-limit=[1-1000] is a numeric flag and -falign-jumps is + # a boolean flag. + numeric_flag_match = flags.Search(spec) + + if numeric_flag_match: + # numeric flag + val = results[spec].GetValue() + + # If the value of the flag is the lower boundary of the specification, this + # flag will be turned off. Because it already contains the lowest value and + # can not be decreased any more. + if val == int(numeric_flag_match.group('start')): + # Turn off the flag. A flag is turned off if it is not presented in the + # flags_dict. + del results[spec] + else: + results[spec] = flags.Flag(spec, val - 1) + else: + # Turn off the flag. A flag is turned off if it is not presented in the + # flags_dict. + del results[spec] + + return results + + +class IterativeEliminationGeneration(Generation): + """The negative flag iterative elimination algorithm.""" + + def __init__(self, exe_set, parent_task): + """Set up the base line parent task. + + The parent task is the base line against which the new tasks are compared. + The new tasks are only different from the base line from one flag f by + either turning this flag f off, or lower the flag value by 1. + If a new task is better than the base line, one flag is identified that + gives degradation. The flag that give the worst degradation will be removed + or lower the value by 1 in the base in each iteration. + + Args: + exe_set: A set of tasks to be run. Each one only differs from the + parent_task by one flag. + parent_task: The base line task, against which the new tasks in exe_set + are compared. + """ + + Generation.__init__(self, exe_set, None) + self._parent_task = parent_task + + def IsImproved(self): + """Whether any new task has improvement upon the parent task.""" + + parent = self._parent_task + # Whether there is any new task that has improvement over the parent base + # line task. + for curr in [curr for curr in self.Pool() if curr != parent]: + if curr.IsImproved(parent): + return True + + return False + + def Next(self, cache): + """Find out the flag that gives the worst degradation. + + Found out the flag that gives the worst degradation. Turn that flag off from + the base line and use the new base line for the new generation. + + Args: + cache: A set of tasks that have been generated before. + + Returns: + A set of new generations. + """ + parent_task = self._parent_task + + # Find out the task that gives the worst degradation. + worst_task = parent_task + + for curr in [curr for curr in self.Pool() if curr != parent_task]: + # The method IsImproved, which is supposed to be called before, ensures + # that there is at least a task that improves upon the parent_task. + if curr.IsImproved(worst_task): + worst_task = curr + + assert worst_task != parent_task + + # The flags_set of the worst task. + work_flags_set = worst_task.GetFlags().GetFlags() + + results = set([]) + + # If the flags_set contains no flag, i.e., all the flags have been + # eliminated, the algorithm stops. + if not work_flags_set: + return [] + + # Turn of the remaining flags one by one for the next generation. + for spec in work_flags_set: + flag_set = flags.FlagSet(_DecreaseFlag(work_flags_set, spec).values()) + new_task = task.Task(flag_set) + if new_task not in cache: + results.add(new_task) + + return [IterativeEliminationGeneration(results, worst_task)] + + +class IterativeEliminationFirstGeneration(IterativeEliminationGeneration): + """The first iteration of the iterative elimination algorithm. + + The first iteration also evaluates the base line task. The base line tasks in + the subsequent iterations have been evaluated. Therefore, + IterativeEliminationGeneration does not include the base line task in the + execution set. + """ + + def IsImproved(self): + # Find out the base line task in the execution set. + parent = next(task for task in self.Pool() if task == self._parent_task) + self._parent_task = parent + + return IterativeEliminationGeneration.IsImproved(self) diff --git a/bestflags/testing_batch.py b/bestflags/testing_batch.py index 97ea450a..7bfda09b 100644 --- a/bestflags/testing_batch.py +++ b/bestflags/testing_batch.py @@ -6,7 +6,8 @@ Part of the Chrome build flags optimization. -Test the variations of the hill climbing algorithms. +Test the best branching hill climbing algorithms, genetic algorithm and +iterative elimination algorithm. """ __author__ = 'yuhenglong@google.com (Yuheng Long)' @@ -22,6 +23,7 @@ from flags import FlagSet from genetic_algorithm import GAGeneration from genetic_algorithm import GATask from hill_climb_best_neighbor import HillClimbingBestBranch +from iterative_elimination import IterativeEliminationFirstGeneration import pipeline_process from steering import Steering from task import BUILD_STAGE @@ -133,6 +135,102 @@ def GenerateRandomGATasks(specs, num_tasks, num_trials): return tasks +def _GenerateInitialFlags(specs, spec): + """Generate the flag_set of a task in the flag elimination algorithm. + + Set the value of all the flags to the largest value, except for the flag that + contains spec. + + For example, if the specs are [-finline-limit=[1-1000], -fstrict-aliasing] and + the spec is -finline-limit=[1-1000], then the result is + [-finline-limit=[1-1000]:-finline-limit=998, + -fstrict-aliasing:-fstrict-aliasing] + + Args: + specs: an array of specifications from which the result flag_set is created. + The flag_set contains one and only one flag that contain the specification + spec. + spec: The flag containing this spec should have a value that is smaller than + the highest value the flag can have. + + Returns: + An array of flags, each of which contains one spec in specs. All the values + of the flags are the largest values in specs, expect the one that contains + spec. + """ + + flag_set = [] + for other_spec in specs: + numeric_flag_match = flags.Search(other_spec) + # Found the spec in the array specs. + if other_spec == spec: + # Numeric flag will have a value that is smaller than the largest value + # and Boolean flag will be deleted. + if numeric_flag_match: + end = int(numeric_flag_match.group('end')) + flag_set.append(flags.Flag(other_spec, end - 2)) + + continue + + # other_spec != spec + if numeric_flag_match: + # numeric flag + end = int(numeric_flag_match.group('end')) + flag_set.append(flags.Flag(other_spec, end - 1)) + continue + + # boolean flag + flag_set.append(flags.Flag(other_spec)) + + return flag_set + + +def _GenerateAllIterativeEliminationTasks(specs): + """Generate the initial tasks for the negative flag elimination algorithm. + + Generate the base line task that turns on all the boolean flags and sets the + value to be the largest value for the numeric flag. + + For example, if the specs are [-finline-limit=[1-1000], -fstrict-aliasing], + the base line is [-finline-limit=[1-1000]:-finline-limit=999, + -fstrict-aliasing:-fstrict-aliasing] + + Generate a set of task, each turns off one of the flag or sets a value that is + smaller than the largest value for the flag. + + Args: + specs: an array of specifications from which the result flag_set is created. + + Returns: + An array containing one generation of the initial tasks for the negative + flag elimination algorithm. + """ + + # The set of tasks to be generated. + results = set([]) + flag_set = [] + + for spec in specs: + numeric_flag_match = flags.Search(spec) + if numeric_flag_match: + # Numeric flag. + end_value = int(numeric_flag_match.group('end')) + flag_set.append(flags.Flag(spec, end_value - 1)) + continue + + # Boolean flag. + flag_set.append(flags.Flag(spec)) + + # The base line task that set all the flags to their largest values. + parent_task = Task(flags.FlagSet(flag_set)) + results.add(parent_task) + + for spec in specs: + results.add(Task(flags.FlagSet(_GenerateInitialFlags(specs, spec)))) + + return [IterativeEliminationFirstGeneration(results, parent_task)] + + def _ComputeCost(cost_func, specs, flag_set): """Compute the mock cost of the flag_set using the input cost function. @@ -242,6 +340,13 @@ class MockAlgorithmsTest(unittest.TestCase): build and test phases by letting the user define the fitness function. """ + def _GenerateFlagSpecifications(self): + """Generate the testing specifications.""" + + mock_test_file = 'scale_mock_test' + _GenerateTestFlags(NUM_FLAGS, FLAG_RANGES, mock_test_file) + return flags.ReadConf(mock_test_file) + def testBestHillClimb(self): """Test the best hill climb algorithm. @@ -252,9 +357,7 @@ class MockAlgorithmsTest(unittest.TestCase): Task.InitLogCommand(None, None, 'output') # Generate the testing specs. - mock_test_file = 'scale_mock_test' - _GenerateTestFlags(NUM_FLAGS, FLAG_RANGES, mock_test_file) - specs = flags.ReadConf(mock_test_file) + specs = self._GenerateFlagSpecifications() # Generate the initial generations for a test whose cost function is the # summation of the values of all the flags. @@ -292,10 +395,7 @@ class MockAlgorithmsTest(unittest.TestCase): Task.InitLogCommand(None, None, 'output') # Generate the testing specs. - mock_test_file = 'scale_mock_test' - _GenerateTestFlags(NUM_FLAGS, FLAG_RANGES, mock_test_file) - specs = flags.ReadConf(mock_test_file) - + specs = self._GenerateFlagSpecifications() # Initiate the build/test command and the log directory. GAGeneration.InitMetaData(STOP_THRESHOLD, NUM_CHROMOSOMES, NUM_TRIALS, specs, MUTATION_RATE) @@ -310,6 +410,43 @@ class MockAlgorithmsTest(unittest.TestCase): cost_func = 'sys.maxint - sum(values[0:len(values)])' _TestAlgorithm(cost_func, specs, generations, -1) + def testIterativeElimination(self): + """Test the iterative elimination algorithm. + + Test whether it finds the best results as expected. + """ + + # Initiate the build/test command and the log directory. + Task.InitLogCommand(None, None, 'output') + + # Generate the testing specs. + specs = self._GenerateFlagSpecifications() + + # Generate the initial generations. The generation contains the base line + # task that turns on all the flags and tasks that each turn off one of the + # flags. + generations = _GenerateAllIterativeEliminationTasks(specs) + + # Test the algorithm. The cost function is the summation of all the values + # of all the flags. Therefore, the best value is supposed to be 0, i.e., + # when all the flags are disabled. + _TestAlgorithm('sum(values[0:len(values)])', specs, generations, 0) + + # This test uses a cost function that is the negative of the previous cost + # function. Therefore, the best result should be found in task with all the + # flags enabled. + all_flags_tasks = _GenerateAllFlagsTasks(specs) + cost_function = 'sys.maxint - sum(values[0:len(values)])' + # Compute the cost of the task that turns on all the flags. + all_flags = list(all_flags_tasks)[0].GetFlags() + cost = _ComputeCost(cost_function, specs, all_flags) + + # Test the algorithm. The cost function is negative of the summation of all + # the values of all the flags. Therefore, the best value is supposed to be + # 0, i.e., when all the flags are disabled. + # The concrete type of the generation decides how the next generation will + # be generated. + _TestAlgorithm(cost_function, specs, generations, cost) if __name__ == '__main__': unittest.main() |