diff options
Diffstat (limited to 'crosperf/machine_image_manager.py')
| -rw-r--r-- | crosperf/machine_image_manager.py | 304 |
1 files changed, 304 insertions, 0 deletions
diff --git a/crosperf/machine_image_manager.py b/crosperf/machine_image_manager.py new file mode 100644 index 00000000..3cc464bb --- /dev/null +++ b/crosperf/machine_image_manager.py @@ -0,0 +1,304 @@ + +# Copyright 2015 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. + +"""MachineImageManager allocates images to duts.""" + +class MachineImageManager(object): + """Management of allocating images to duts. + + * Data structure we have - + + duts_ - list of duts, for each duts, we assume the following 2 properties + exist - label_ (the current label the duts_ carries or None, if it has an + alien image) and name (a string) + + labels_ - a list of labels, for each label, we assume these properties + exist - remote (a set/vector/list of dut names (not dut object), to each + of which this image is compatible), remote could be none, which means + universal compatible. + + label_duts_ - for each label, we maintain a list of duts, onto which the + label is imaged. Note this is an array of lists. Each element of each list + is an integer which is dut oridnal. We access this array using label + ordinal. + + allocate_log_ - a list of allocation record. For example, if we allocate + l1 to d1, then l2 to d2, then allocate_log_ would be [(1, 1), (2, 2)]. + This is used for debug/log, etc. All tuples in the list are integer pairs + (label_ordinal, dut_ordinal). + + n_duts_ - number of duts. + + n_labels_ - number of labels. + + dut_name_ordinal_ - mapping from dut name (a string) to an integer, + starting from 0. So that duts_[dut_name_ordinal_[a_dut.name]]= a_dut. + + * Problem abstraction - + + Assume we have the following matrix - label X machine (row X col). A 'X' + in (i, j) in the matrix means machine and lable is not compatible, or that + we cannot image li to Mj. + + M1 M2 M3 + L1 X + + L2 X + + L3 X X + + Now that we'll try to find a way to fill Ys in the matrix so that - + + a) - each row at least get a Y, this ensures that each label get imaged + at least once, an apparent prerequiste. + + b) - each column get at most N Ys. This make sure we can successfully + finish all tests by re-image each machine at most N times. That being + said, we could *OPTIONALLY* reimage some machines more than N times to + *accelerate* the test speed. + + How to choose initial N for b) - + If number of duts (nd) is equal to or more than that of labels (nl), we + start from N == 1. Else we start from N = nl - nd + 1. + + We will begin the search with pre-defined N, if we fail to find such a + solution for such N, we increase N by 1 and continue the search till we + get N == nl, at this case we fails. + + Such a solution ensures minimal number of reimages. + + * Solution representation + + The solution will be placed inside the matrix, like below + + M1 M2 M3 M4 + L1 X X Y + + L2 Y X + + L3 X Y X + + * Allocation algorithm + + When Mj asks for a image, we check column j, pick the first cell that + contains a 'Y', and mark the cell '_'. If no such 'Y' exists (like M4 in + the above solution matrix), we just pick an image that the minimal reimage + number. + + After allocate for M3 + M1 M2 M3 M4 + L1 X X _ + + L2 Y X + + L3 X Y X + + After allocate for M4 + M1 M2 M3 M4 + L1 X X _ + + L2 Y X _ + + L3 X Y X + + After allocate for M2 + M1 M2 M3 M4 + L1 X X _ + + L2 Y X _ + + L3 X _ X + + After allocate for M1 + M1 M2 M3 M4 + L1 X X _ + + L2 _ X _ + + L3 X _ X + + After allocate for M2 + M1 M2 M3 M4 + L1 X X _ + + L2 _ _ X _ + + L3 X _ X + + If we try to allocate for M1 or M2 or M3 again, we get None. + + * Special / common case to handle seperately + + We have only 1 dut or if we have only 1 label, that's simple enough. + + """ + + def __init__(self, labels, duts): + self.labels_ = labels + self.duts_ = duts + self.n_labels_ = len(labels) + self.n_duts_ = len(duts) + self.dut_name_ordinal_ = dict() + for idx, dut in enumerate(self.duts_): + self.dut_name_ordinal_[dut.name] = idx + + # Generate initial matrix containg 'X' or ' '. + self.matrix_ = [['X' if (l.remote and len(l.remote)) else ' ' \ + for _ in range(self.n_duts_)] for l in self.labels_] + for ol, l in enumerate(self.labels_): + if l.remote: + for r in l.remote: + self.matrix_[ol][self.dut_name_ordinal_[r]] = ' ' + + self.label_duts_ = [[] for _ in range(self.n_labels_)] + self.allocate_log_ = [] + + def compute_initial_allocation(self): + """Compute the initial label-dut allocation. + + This method finds the most efficient way that every label gets imaged at + least once. + + Returns: + False, only if not all labels could be imaged to a certain machine, + otherwise True. + """ + + if self.n_duts_ == 1: + for i, v in self.matrix_vertical_generator(0): + if v != 'X': + self.matrix_[i][0] = 'Y' + return + + if self.n_labels_ == 1: + for j, v in self.matrix_horizontal_generator(0): + if v != 'X': + self.matrix_[0][j] = 'Y' + return + + if self.n_duts_ >= self.n_labels_: + n = 1 + else: + n = self.n_labels_ - self.n_duts_ + 1 + while n <= self.n_labels_: + if self._compute_initial_allocation_internal(0, n): + break + n += 1 + + return n <= self.n_labels_ + + def _record_allocate_log(self, label_i, dut_j): + self.allocate_log_.append((label_i, dut_j)) + self.label_duts_[label_i].append(dut_j) + + def allocate(self, dut, schedv2=None): + """Allocate a label for dut. + + Args: + dut: the dut that asks for a new image. + schedv2: the scheduling instance, we need the benchmark run + information with schedv2 for a better allocation. + + Returns: + a label to image onto the dut or None if no more available images for + the dut. + """ + j = self.dut_name_ordinal_[dut.name] + # 'can_' prefix means candidate label's. + can_reimage_number = 999 + can_i = 999 + can_label = None + can_pending_br_num = 0 + for i, v in self.matrix_vertical_generator(j): + label = self.labels_[i] + + # 2 optimizations here regarding allocating label to dut. + # Note schedv2 might be None in case we do not need this + # optimization or we are in testing mode. + if schedv2 is not None: + pending_br_num = len(schedv2.get_label_map()[label]) + if pending_br_num == 0: + # (A) - we have finished all br of this label, + # apparently, we do not want to reimaeg dut to + # this label. + continue + else: + # In case we do not have a schedv2 instance, mark + # pending_br_num as 0, so pending_br_num >= + # can_pending_br_num is always True. + pending_br_num = 0 + + # For this time being, I just comment this out until we have a + # better estimation how long each benchmarkrun takes. + # if (pending_br_num <= 5 and + # len(self.label_duts_[i]) >= 1): + # # (B) this is heuristic - if there are just a few test cases + # # (say <5) left undone for this label, and there is at least + # # 1 other machine working on this lable, we probably not want + # # to bother to reimage this dut to help with these 5 test + # # cases + # continue + + if v == 'Y': + self.matrix_[i][j] = '_' + self._record_allocate_log(i, j) + return label + if v == ' ': + label_reimage_number = len(self.label_duts_[i]) + if ((can_label is None) or + (label_reimage_number < can_reimage_number or + (label_reimage_number == can_reimage_number and + pending_br_num >= can_pending_br_num))): + can_reimage_number = label_reimage_number + can_i = i + can_label = label + can_pending_br_num = pending_br_num + + # All labels are marked either '_' (already taken) or 'X' (not + # compatible), so return None to notify machine thread to quit. + if can_label is None: + return None + + # At this point, we don't find any 'Y' for the machine, so we go the + # 'min' approach. + self.matrix_[can_i][j] = '_' + self._record_allocate_log(can_i, j) + return can_label + + def matrix_vertical_generator(self, col): + """Iterate matrix vertically at column 'col'. + + Yield row number i and value at matrix_[i][col]. + """ + for i, _ in enumerate(self.labels_): + yield i, self.matrix_[i][col] + + def matrix_horizontal_generator(self, row): + """Iterate matrix horizontally at row 'row'. + + Yield col number j and value at matrix_[row][j]. + """ + for j, _ in enumerate(self.duts_): + yield j, self.matrix_[row][j] + + def _compute_initial_allocation_internal(self, level, N): + """Search matrix for d with N.""" + + if level == self.n_labels_: + return True + + for j, v in self.matrix_horizontal_generator(level): + if v == ' ': + # Before we put a 'Y', we check how many Y column 'j' has. + # Note y[0] is row idx, y[1] is the cell value. + ny = reduce(lambda x, y: x + 1 if (y[1] == 'Y') else x, + self.matrix_vertical_generator(j), 0) + if ny < N: + self.matrix_[level][j] = 'Y' + if self._compute_initial_allocation_internal(level + 1, N): + return True + self.matrix_[level][j] = ' ' + + return False |