1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
|
"""A generation of a set of tasks.
Part of the Chrome build flags optimization.
This module contains the base generation class. This class contains the tasks of
this current generation. The generation will not evolve to the next generation
until all the tasks in this generation are done executing. It also contains a
set of tasks that could potentially be used to generate the next generation,
e.g., in the genetic algorithm, a set of good species will be kept to evolve to
the successive generations. For the hill climbing algorithm example, the
candidate_pool will contain a current task t being evaluated and the exe_pool
will contains all the task t's neighbor.
"""
__author__ = 'yuhenglong@google.com (Yuheng Long)'
class NoneOverridingError(Exception):
"""Define an Exception class for subclasses not overriding certain methods."""
pass
class Generation(object):
"""A generation of a framework run.
The base class of generation. Concrete subclasses, e.g., GAGeneration should
override the Next and Improve method to implement algorithm specific
applications.
"""
def __init__(self, exe_pool, candidate_pool):
"""Set up the tasks set of this generation.
Args:
exe_pool: A set of tasks to be run.
candidate_pool: A set of tasks to be considered to be used to generate the
next generation.
"""
self._exe_pool = exe_pool
self._candidate_pool = candidate_pool
# Keeping the record of how many tasks are pending. Pending tasks are the
# ones that have been sent out to the next stage for execution but have not
# finished. A generation is not ready for the reproduction of the new
# generations until all its pending tasks have been executed.
self._pending = len(exe_pool)
def Pool(self):
"""Return the task set of this generation."""
return self._exe_pool
def Done(self):
"""All the tasks in this generation are done.
Returns:
True if all the tasks have been executed. That is the number of pending
task is 0.
"""
return self._pending == 0
def UpdateTask(self, task):
"""Match a task t in this generation that is equal to the input task.
This method is called when the input task has just finished execution. This
method finds out whether there is a pending task t in the current generation
that is the same as the input task. Two tasks are the same if their flag
options are the same. A task is pending if it has not been performed.
If there is a pending task t that matches the input task, task t will be
substituted with the input task in this generation. In that case, the input
task, as well as its build and test results encapsulated in the task, will
be stored in the current generation. These results could be used to produce
the next generation.
If there is a match, the current generation will have one less pending task.
When there is no pending task, the generation can be used to produce the
next generation.
The caller of this function is responsible for not calling this method on
the same task more than once.
Args:
task: A task that has its results ready.
"""
# If there is a match.
if task in self._exe_pool:
# Remove the place holder task in this generation and store the new input
# task and its result.
self._exe_pool.remove(task)
self._exe_pool.add(task)
# The current generation will have one less task to wait on.
self._pending -= 1
assert self._pending >= 0
def Improve(self):
"""True if this generation has improvement over its parent generation.
Raises:
NoneOverridingError: The subclass should override this method.
"""
raise NoneOverridingError('Must be implemented by child class')
def Next(self):
"""Calculate the next generation.
This is the core of the framework implementation. It must be overridden by
the concrete subclass to implement algorithm specific generations.
Returns:
A set of new generations.
Raises:
NoneOverridingError: The subclass should override this method.
"""
raise NoneOverridingError('Must be implemented by child class')
|
