Added the skeleton for the flagging framework.

BUG=None
TEST=None

Change-Id: I72c37ac70ed2adca588ad9866a6bcc26775aed8b
Reviewed-on: https://gerrit-int.chromium.org/39096
Reviewed-by: Luis Lozano <llozano@chromium.org>
Tested-by: Yuheng Long <yuhenglong@google.com>
Commit-Queue: Yuheng Long <yuhenglong@google.com>

12 files changed, 522 insertions, 0 deletions

diff --git a/bestflags/builder.py b/bestflags/builder.py
new file mode 100644
index 00000000..a75bd425
--- /dev/null
+++ b/bestflags/builder.py
@@ -0,0 +1,59 @@
+"""The Build stage of the framework.
+
+Build the image according to the flag set. This stage sets up a number of
+processes, calls the actual build method and caches the results.
+"""
+
+__author__ = 'yuhenglong@google.com (Yuheng Long)'
+
+import multiprocessing
+
+
+class Builder(object):
+  """Compiling the source code to generate images using multiple processes."""
+
+  def __init__(self, numProcess, images):
+    """Set up the process pool and the images cached.
+
+    Args:
+      numProcess: Maximum number of builds to run in parallel
+      images: Images that have been generated before
+    """
+    if numProcess <= 0:
+      numProcess = 1
+    self._pool = multiprocessing.Pool(numProcess)
+    self._images = images
+
+  def _set_cost(self, flag_set, image, cost):
+    """Record the build result for the current flag_set.
+
+    Args:
+      flag_set: The optimization combination
+      image: The result image for the build
+      cost: the time it takes to build the image
+    """
+
+    pass
+
+  def _build_task(self, task):
+    """Compile the task and generate output.
+
+    This stage includes compiling the input task, generating an image for the
+    task and computing the checksum for the image.
+
+    Args:
+      task: The task to be compiled
+    """
+
+    pass
+
+  def build(self, generation):
+    """Build the images for all entities in a generation.
+
+    Call them in parallel in processes.
+
+    Args:
+      generation: A new generation to be built.
+    """
+
+    self._pool.map(self._build_task, generation.task, 1)
diff --git a/bestflags/builder_test.py b/bestflags/builder_test.py
new file mode 100644
index 00000000..9a636ff3
--- /dev/null
+++ b/bestflags/builder_test.py
@@ -0,0 +1,42 @@
+"""Builder unittest."""
+
+__author__ = 'yuhenglong@google.com (Yuheng Long)'
+
+import unittest
+
+import builder
+
+
+class BuilderTest(unittest.TestCase):
+  """This class test the Builder.
+
+  Given the same flags set, the image and the cost should result the same from
+  the builder.
+  """
+
+  def setUp(self):
+    """Create the Builder to be tested."""
+
+    self.builder = builder.Builder(1, None)
+
+  def testCompile(self):
+    """"Test the build method.
+
+    Call the build method twice, and test the results. The results should be the
+    same, i.e., the image, the cost and the checksum should be the same.
+    Either the compile method or the set_compile_result of the input Generation
+    for the Builder should be called, but not both.
+    """
+    self.builder.build(self)
+
+  def testInit(self):
+    """"Test the init method.
+
+    If a certain flag set has been encountered before, the builder should not
+    recompile the image with the same optimization flag set.
+    """
+
+    pass
+
+if __name__ == '__main__':
+  unittest.main()
diff --git a/bestflags/executor.py b/bestflags/executor.py
new file mode 100644
index 00000000..91dd9288
--- /dev/null
+++ b/bestflags/executor.py
@@ -0,0 +1,64 @@
+"""The Execution stage of the framework.
+
+Execute the image against a set of benchmarks. This stage sets up a number of
+processes, calls the actual execute method and caches the results.
+"""
+
+__author__ = 'yuhenglong@google.com (Yuheng Long)'
+
+import multiprocessing
+
+
+class Tester(object):
+  """Execute the generated images against a set of benchmark applications."""
+
+  def __init__(self, numProcess, costs):
+    """Set up the process pool and the results cached.
+
+    Args:
+        numProcess: Maximum number of execution to run in parallel
+        costs: Executions that have been benchmarked before
+    """
+
+    self._pool = multiprocessing.Pool(numProcess)
+    self._costs = costs
+
+  def _set_cost(self, image, cost):
+    """Record the execution result for the current image.
+
+    Args:
+      image: The input image for the execution
+      cost: the time it takes to execute the image
+    """
+
+    pass
+
+  def _execute(self, task):
+    """Execute the benchmarks on task.
+
+    The concrete subclass should implement the actual execution.
+
+    Args:
+      task: The input task for the execution
+    """
+    # raise Exception('Must be implemented in child class')
+    pass
+
+  def _execute_task(self, task):
+    """Execute the input task and record the cost.
+
+    Args:
+      task: The task to be compiled
+    """
+    pass
+
+  def execute(self, generation):
+    """Execute the image for all entities in a generation.
+
+    Call them in parallel in processes.
+
+    Args:
+      generation: A new generation to be executed.
+    """
+
+    self._pool.map(self._execute_task, generation.task, 1)
diff --git a/bestflags/executor_test.py b/bestflags/executor_test.py
new file mode 100644
index 00000000..0f27fb9a
--- /dev/null
+++ b/bestflags/executor_test.py
@@ -0,0 +1,42 @@
+"""Tester unittest."""
+
+__author__ = 'yuhenglong@google.com (Yuheng Long)'
+
+import unittest
+
+import executor
+
+
+class TesterTest(unittest.TestCase):
+  """This class test the Executor.
+
+  Given the same flags set and/or checksum, the image and the cost should be the
+  same from the Executor.
+  """
+
+  def setUp(self):
+    """Create the Executor to be tested."""
+
+    self.tester = executor.Tester(1, None)
+
+  def testExecute(self):
+    """"Test the execute method.
+
+    Call the execute method twice, and test the results. The results should be
+    the same, i.e., the cost should be the same.
+    Either the execute method or the set_execution_result of the input
+    Generation for the Tester should be called, but not both.
+    """
+    self.tester.execute(self)
+
+  def testInit(self):
+    """"Test the init method.
+
+    If a certain checksum has been encountered before, the Tester should not
+    reexecute the images with the same checksum.
+    """
+
+    pass
+
+if __name__ == '__main__':
+  unittest.main()
diff --git a/bestflags/generation.py b/bestflags/generation.py
new file mode 100644
index 00000000..a6d38c81
--- /dev/null
+++ b/bestflags/generation.py
@@ -0,0 +1,42 @@
+"""A generation of a set of tasks.
+
+This contains the core algorithm of producing the next generation of execution.
+"""
+
+__author__ = 'yuhenglong@google.com (Yuheng Long)'
+
+
+class Generation(object):
+  """A generation of a framework run.
+
+  This also contains the core implementation, reproducing new generations.
+  """
+
+  def __init__(self, pool):
+    """Set up the tasks set of this generation.
+
+    Args:
+        pool: a set of tasks to be run
+    """
+    self._pool = pool
+
+  def next(self):
+    """Calculate the next generation.
+
+    This is the core of the framework implementation.
+
+    Returns:
+      A new generation.
+    """
+
+  def pool(self):
+    """Return the task set of this generation."""
+    pass
+
+  def improve(self):
+    """True if this generation has improvement over its parent generation."""
+    pass
+
+  def get_best(self):
+    """Get the best flagset."""
+    return self._pool[0]
diff --git a/bestflags/generation_test.py b/bestflags/generation_test.py
new file mode 100644
index 00000000..d97f51be
--- /dev/null
+++ b/bestflags/generation_test.py
@@ -0,0 +1,41 @@
+"""Generation unittest."""
+
+__author__ = 'yuhenglong@google.com (Yuheng Long)'
+
+import unittest
+
+import generation
+
+
+class GenerationTest(unittest.TestCase):
+  """This class test the Generation class.
+
+  A generation class should not produce a task that has been generated before.
+  The task returned as the best task should really be the best.
+
+  Given two generations, if the second one has improved upon the first one,
+  the result method should return true and false otherwise.
+  """
+
+  def setUp(self):
+    pass
+
+  def testNext(self):
+    """"Test the next method.
+
+    Call the next method n times and all the tasks in each generation should be
+    unique.
+    """
+    pass
+
+  def testImprove(self):
+    """"Test the improve method.
+
+    If the successor generation has improvement upon the parent generation, the
+    result from the improve method should indicate so.
+    """
+
+    pass
+
+if __name__ == '__main__':
+  unittest.main()
diff --git a/bestflags/pipeline_process.py b/bestflags/pipeline_process.py
new file mode 100644
index 00000000..6b878b30
--- /dev/null
+++ b/bestflags/pipeline_process.py
@@ -0,0 +1,51 @@
+"""Pipeline process that encapsulates the actual content.
+
+The actual stages include the Steering algorithm, the builder and the executor.
+"""
+
+__author__ = 'yuhenglong@google.com (Yuheng Long)'
+
+import multiprocessing
+
+
+class PipelineProcess(multiprocessing.Process):
+  """A process that encapsulates the actual content.
+
+  It continuously pull tasks from the queue until a poison pill is received.
+  Once a job is received, it will hand it to the actual stage for processing.
+  """
+
+  # Poison pill means shutdown
+  POISON_PILL = None
+
+  def __init__(self, method, task_queue, result_queue):
+    """Set up input/output queue and the actual method to be called.
+
+    Args:
+      method: The actual pipeline stage to be invoked.
+      task_queue: The input task queue for this pipeline stage.
+      result_queue: The output task queue for this pipeline stage.
+    """
+
+    multiprocessing.Process.__init__(self)
+    self._method = method
+    self._task_queue = task_queue
+    self._result_queue = result_queue
+
+  def run(self):
+    """Busy pulling the next task from the queue for execution.
+
+    Once a job is pulled, this stage invokes the actual stage method and submits
+    the result to the next pipeline stage.
+
+    The process will terminate on receiving the poison pill from previous stage.
+    """
+
+    while True:
+      next_task = self.task_queue.get()
+      if next_task is None:
+        # Poison pill means shutdown
+        self.result_queue.put(None)
+        break
+      self._method(next_task)
+      self.result_queue.put(next_task)
diff --git a/bestflags/pipeline_process_test.py b/bestflags/pipeline_process_test.py
new file mode 100644
index 00000000..8df23278
--- /dev/null
+++ b/bestflags/pipeline_process_test.py
@@ -0,0 +1,29 @@
+"""Pipeline Process unittest."""
+
+__author__ = 'yuhenglong@google.com (Yuheng Long)'
+
+import unittest
+
+import pipeline_process
+
+
+class PipelineProcessTest(unittest.TestCase):
+  """This class test the PipelineProcess.
+
+  All the task inserted into the input queue should be taken out and hand to the
+  actual pipeline handler, except for the POISON_PILL.  All these task should
+  also be passed to the next pipeline stage via the output queue.
+  """
+
+  def setUp(self):
+    pass
+
+  def testRun(self):
+    """"Test the run method.
+
+    Ensure that all the tasks inserted into the queue are properly handled.
+    """
+    pass
+
+if __name__ == '__main__':
+  unittest.main()
diff --git a/bestflags/steering.py b/bestflags/steering.py
new file mode 100644
index 00000000..7d9064b5
--- /dev/null
+++ b/bestflags/steering.py
@@ -0,0 +1,25 @@
+"""A Genetic Algorithm implementation for selecting good flags."""
+
+__author__ = 'yuhenglong@google.com (Yuheng Long)'
+
+
+class Steering(object):
+  """The steering algorithm that produce the next generation to be run."""
+
+  def __init__(self, steps):
+    """Set up the number of steps generations this algorithm should evolve.
+
+    Args:
+      steps: number of steps that the feed back loop should perform
+    """
+
+    self._steps = steps
+
+  def run(self, generation):
+    """Generate a set of new generations for the next round of execution.
+
+    Args:
+      generation: the previous generation.
+    """
+
+    pass
diff --git a/bestflags/steering_test.py b/bestflags/steering_test.py
new file mode 100644
index 00000000..c538d5fb
--- /dev/null
+++ b/bestflags/steering_test.py
@@ -0,0 +1,29 @@
+"""Steering stage unittest."""
+
+__author__ = 'yuhenglong@google.com (Yuheng Long)'
+
+import unittest
+
+import steering
+
+
+class SteeringTest(unittest.TestCase):
+  """This class test the Steering class.
+
+  This steering algorithm should stop either it has generated a certain number
+  of generations or the generation has no further improvement.
+  """
+
+  def setUp(self):
+    pass
+
+  def testGeneration(self):
+    """"Test proper termination for a number of generations."""
+    pass
+
+  def testImprove(self):
+    """"Test proper termination for no improvement between generations."""
+    pass
+
+if __name__ == '__main__':
+  unittest.main()
diff --git a/bestflags/task.py b/bestflags/task.py
new file mode 100644
index 00000000..b092ffc9
--- /dev/null
+++ b/bestflags/task.py
@@ -0,0 +1,66 @@
+"""A reproducing entity.
+
+The Task class is used by different modules. Each module fills in the
+corresponding information into a Task instance. Class Task contains the bit set
+representing the flags selection. The builder module is responsible for filling
+the image and the checksum field of a Task. The executor module will put the
+execution output to the execution field.
+"""
+
+__author__ = 'yuhenglong@google.com (Yuheng Long)'
+
+
+class Task(object):
+  """A single reproducing entity.
+
+  A single test of performance with a particular set of flags. It records the
+  flag set, the image, the check sum of the image and the cost.
+  """
+
+  def __init__(self, flag_set):
+    """Set up the optimization flag selection for this task.
+
+    Args:
+      flag_set: the optimization flag set that is encapsulated by this task.
+    """
+    self._flag_set = flag_set
+
+  def reproduce_with(self, other):
+    """Create a new SolutionCandidate by reproduction with another.
+
+    Mix two Tasks together to form a new Task of the same class. This is one of
+    the core functions of a GA.
+
+    Args:
+      other: The other Task to reproduce with.
+
+    Returns: A Task that is a mix between self and other.
+    """
+    pass
+
+  def compile(self):
+    """Run a compile.
+
+    This method compile an image using the present flags, get the image,
+    test the existent of the image and gathers monitoring information, and sets
+    the internal cost (fitness) for this set of flags.
+    """
+    pass
+
+  def get_flags(self):
+    pass
+
+  def set_flags(self, flags):
+    pass
+
+  def get_checksum(self):
+    pass
+
+  def set_checksum(self, checksum):
+    pass
+
+  def get_image(self):
+    pass
+
+  def set_image(self, image):
+    pass
diff --git a/bestflags/task_test.py b/bestflags/task_test.py
new file mode 100644
index 00000000..c21dc4dc
--- /dev/null
+++ b/bestflags/task_test.py
@@ -0,0 +1,32 @@
+"""Task unittest."""
+
+__author__ = 'yuhenglong@google.com (Yuheng Long)'
+
+import unittest
+
+import task
+
+
+class TaskTest(unittest.TestCase):
+  """This class test the Task class.
+
+  The getter and setter should function properly.
+  """
+
+  def setUp(self):
+    pass
+
+  def testFlag(self):
+    """"Test proper access of the flags."""
+    pass
+
+  def testChecksum(self):
+    """"Test proper access of the check sum."""
+    pass
+
+  def testImage(self):
+    """"Test proper access of the image."""
+    pass
+
+if __name__ == '__main__':
+  unittest.main()