1ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen 22e307b303ac37c3e971086f23da2df25fef2c1b4Ting-Yuan Huang# Copyright 2015 The Chromium OS Authors. All rights reserved. 32e307b303ac37c3e971086f23da2df25fef2c1b4Ting-Yuan Huang# Use of this source code is governed by a BSD-style license that can be 42e307b303ac37c3e971086f23da2df25fef2c1b4Ting-Yuan Huang# found in the LICENSE file. 5ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen 62e307b303ac37c3e971086f23da2df25fef2c1b4Ting-Yuan Huang"""MachineImageManager allocates images to duts.""" 7f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano 8ba64928c5dcbacbc70b4358881a89ad96227164dHan Shenclass MachineImageManager(object): 9f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano """Management of allocating images to duts. 10ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen 11ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen * Data structure we have - 12ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen 13ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen duts_ - list of duts, for each duts, we assume the following 2 properties 14ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen exist - label_ (the current label the duts_ carries or None, if it has an 15ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen alien image) and name (a string) 16ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen 17ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen labels_ - a list of labels, for each label, we assume these properties 18ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen exist - remote (a set/vector/list of dut names (not dut object), to each 19ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen of which this image is compatible), remote could be none, which means 20ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen universal compatible. 21ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen 22ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen label_duts_ - for each label, we maintain a list of duts, onto which the 23ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen label is imaged. Note this is an array of lists. Each element of each list 24ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen is an integer which is dut oridnal. We access this array using label 25ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen ordinal. 26ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen 27ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen allocate_log_ - a list of allocation record. For example, if we allocate 28ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen l1 to d1, then l2 to d2, then allocate_log_ would be [(1, 1), (2, 2)]. 29ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen This is used for debug/log, etc. All tuples in the list are integer pairs 30ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen (label_ordinal, dut_ordinal). 31ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen 32ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen n_duts_ - number of duts. 33ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen 34ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen n_labels_ - number of labels. 35ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen 36ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen dut_name_ordinal_ - mapping from dut name (a string) to an integer, 37ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen starting from 0. So that duts_[dut_name_ordinal_[a_dut.name]]= a_dut. 38ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen 39ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen * Problem abstraction - 40ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen 41ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen Assume we have the following matrix - label X machine (row X col). A 'X' 42ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen in (i, j) in the matrix means machine and lable is not compatible, or that 43ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen we cannot image li to Mj. 44ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen 45ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen M1 M2 M3 46ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen L1 X 47ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen 48ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen L2 X 49ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen 50ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen L3 X X 51ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen 52ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen Now that we'll try to find a way to fill Ys in the matrix so that - 53ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen 54ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen a) - each row at least get a Y, this ensures that each label get imaged 55ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen at least once, an apparent prerequiste. 56ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen 57ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen b) - each column get at most N Ys. This make sure we can successfully 58ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen finish all tests by re-image each machine at most N times. That being 59ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen said, we could *OPTIONALLY* reimage some machines more than N times to 60ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen *accelerate* the test speed. 61ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen 62ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen How to choose initial N for b) - 63ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen If number of duts (nd) is equal to or more than that of labels (nl), we 64ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen start from N == 1. Else we start from N = nl - nd + 1. 65ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen 66ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen We will begin the search with pre-defined N, if we fail to find such a 67ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen solution for such N, we increase N by 1 and continue the search till we 68ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen get N == nl, at this case we fails. 69ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen 70ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen Such a solution ensures minimal number of reimages. 71ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen 72ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen * Solution representation 73ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen 74ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen The solution will be placed inside the matrix, like below 75ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen 76ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen M1 M2 M3 M4 77ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen L1 X X Y 78ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen 79ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen L2 Y X 80ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen 81ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen L3 X Y X 82ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen 83ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen * Allocation algorithm 84ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen 85ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen When Mj asks for a image, we check column j, pick the first cell that 86ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen contains a 'Y', and mark the cell '_'. If no such 'Y' exists (like M4 in 87ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen the above solution matrix), we just pick an image that the minimal reimage 88ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen number. 89ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen 90ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen After allocate for M3 91ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen M1 M2 M3 M4 92ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen L1 X X _ 93ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen 94ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen L2 Y X 95ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen 96ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen L3 X Y X 97ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen 98ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen After allocate for M4 99ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen M1 M2 M3 M4 100ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen L1 X X _ 101ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen 102ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen L2 Y X _ 103ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen 104ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen L3 X Y X 105ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen 106ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen After allocate for M2 107ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen M1 M2 M3 M4 108ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen L1 X X _ 109ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen 110ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen L2 Y X _ 111ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen 112ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen L3 X _ X 113ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen 114ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen After allocate for M1 115ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen M1 M2 M3 M4 116ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen L1 X X _ 117ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen 118ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen L2 _ X _ 119ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen 120ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen L3 X _ X 121ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen 122ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen After allocate for M2 123ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen M1 M2 M3 M4 124ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen L1 X X _ 125ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen 126ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen L2 _ _ X _ 127ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen 128ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen L3 X _ X 129ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen 130ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen If we try to allocate for M1 or M2 or M3 again, we get None. 131ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen 132ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen * Special / common case to handle seperately 133ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen 134ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen We have only 1 dut or if we have only 1 label, that's simple enough. 135ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen 136ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen """ 137ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen 138f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano def __init__(self, labels, duts): 139f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano self.labels_ = labels 140f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano self.duts_ = duts 141f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano self.n_labels_ = len(labels) 142f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano self.n_duts_ = len(duts) 143f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano self.dut_name_ordinal_ = dict() 144f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano for idx, dut in enumerate(self.duts_): 145f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano self.dut_name_ordinal_[dut.name] = idx 146f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano 147f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano # Generate initial matrix containg 'X' or ' '. 148f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano self.matrix_ = [['X' if (l.remote and len(l.remote)) else ' ' \ 1492e307b303ac37c3e971086f23da2df25fef2c1b4Ting-Yuan Huang for _ in range(self.n_duts_)] for l in self.labels_] 150f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano for ol, l in enumerate(self.labels_): 151f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano if l.remote: 152f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano for r in l.remote: 153f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano self.matrix_[ol][self.dut_name_ordinal_[r]] = ' ' 154f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano 155f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano self.label_duts_ = [[] for _ in range(self.n_labels_)] 156f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano self.allocate_log_ = [] 157f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano 158f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano def compute_initial_allocation(self): 159f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano """Compute the initial label-dut allocation. 160ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen 161ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen This method finds the most efficient way that every label gets imaged at 162ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen least once. 163ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen 164ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen Returns: 165ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen False, only if not all labels could be imaged to a certain machine, 166ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen otherwise True. 167ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen """ 168ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen 169f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano if self.n_duts_ == 1: 170f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano for i, v in self.matrix_vertical_generator(0): 171f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano if v != 'X': 172f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano self.matrix_[i][0] = 'Y' 173f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano return 174ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen 175f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano if self.n_labels_ == 1: 176f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano for j, v in self.matrix_horizontal_generator(0): 177f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano if v != 'X': 178f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano self.matrix_[0][j] = 'Y' 179f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano return 180ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen 181f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano if self.n_duts_ >= self.n_labels_: 182f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano n = 1 183f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano else: 184f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano n = self.n_labels_ - self.n_duts_ + 1 185f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano while n <= self.n_labels_: 186f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano if self._compute_initial_allocation_internal(0, n): 187f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano break 188f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano n += 1 189ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen 190f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano return n <= self.n_labels_ 191ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen 192f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano def _record_allocate_log(self, label_i, dut_j): 193f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano self.allocate_log_.append((label_i, dut_j)) 194f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano self.label_duts_[label_i].append(dut_j) 195ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen 196f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano def allocate(self, dut, schedv2=None): 197f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano """Allocate a label for dut. 198ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen 1992e307b303ac37c3e971086f23da2df25fef2c1b4Ting-Yuan Huang Args: 200ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen dut: the dut that asks for a new image. 20198351672bfc0c9082081a22f27282e0bfc471b99Han Shen schedv2: the scheduling instance, we need the benchmark run 20298351672bfc0c9082081a22f27282e0bfc471b99Han Shen information with schedv2 for a better allocation. 203ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen 204ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen Returns: 205ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen a label to image onto the dut or None if no more available images for 206ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen the dut. 207ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen """ 208f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano j = self.dut_name_ordinal_[dut.name] 209f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano # 'can_' prefix means candidate label's. 210f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano can_reimage_number = 999 211f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano can_i = 999 212f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano can_label = None 213f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano can_pending_br_num = 0 214f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano for i, v in self.matrix_vertical_generator(j): 215f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano label = self.labels_[i] 216f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano 217f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano # 2 optimizations here regarding allocating label to dut. 218f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano # Note schedv2 might be None in case we do not need this 219f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano # optimization or we are in testing mode. 220f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano if schedv2 is not None: 2212e307b303ac37c3e971086f23da2df25fef2c1b4Ting-Yuan Huang pending_br_num = len(schedv2.get_label_map()[label]) 222f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano if pending_br_num == 0: 223f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano # (A) - we have finished all br of this label, 224f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano # apparently, we do not want to reimaeg dut to 225f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano # this label. 226f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano continue 227f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano else: 228f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano # In case we do not have a schedv2 instance, mark 229f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano # pending_br_num as 0, so pending_br_num >= 230f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano # can_pending_br_num is always True. 231f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano pending_br_num = 0 232f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano 233f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano # For this time being, I just comment this out until we have a 234f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano # better estimation how long each benchmarkrun takes. 235f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano # if (pending_br_num <= 5 and 236f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano # len(self.label_duts_[i]) >= 1): 237f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano # # (B) this is heuristic - if there are just a few test cases 238f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano # # (say <5) left undone for this label, and there is at least 239f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano # # 1 other machine working on this lable, we probably not want 240f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano # # to bother to reimage this dut to help with these 5 test 241f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano # # cases 242f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano # continue 243f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano 244f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano if v == 'Y': 245f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano self.matrix_[i][j] = '_' 246f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano self._record_allocate_log(i, j) 247f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano return label 248f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano if v == ' ': 249f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano label_reimage_number = len(self.label_duts_[i]) 250f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano if ((can_label is None) or 251f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano (label_reimage_number < can_reimage_number or 252f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano (label_reimage_number == can_reimage_number and 253f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano pending_br_num >= can_pending_br_num))): 254f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano can_reimage_number = label_reimage_number 255f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano can_i = i 256f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano can_label = label 257f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano can_pending_br_num = pending_br_num 258f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano 259f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano # All labels are marked either '_' (already taken) or 'X' (not 260f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano # compatible), so return None to notify machine thread to quit. 261f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano if can_label is None: 262f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano return None 263f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano 264f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano # At this point, we don't find any 'Y' for the machine, so we go the 265f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano # 'min' approach. 266f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano self.matrix_[can_i][j] = '_' 267f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano self._record_allocate_log(can_i, j) 268f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano return can_label 269f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano 270f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano def matrix_vertical_generator(self, col): 271f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano """Iterate matrix vertically at column 'col'. 272ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen 273ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen Yield row number i and value at matrix_[i][col]. 274ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen """ 2752e307b303ac37c3e971086f23da2df25fef2c1b4Ting-Yuan Huang for i, _ in enumerate(self.labels_): 276f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano yield i, self.matrix_[i][col] 277ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen 278f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano def matrix_horizontal_generator(self, row): 279f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano """Iterate matrix horizontally at row 'row'. 280ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen 281ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen Yield col number j and value at matrix_[row][j]. 282ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen """ 2832e307b303ac37c3e971086f23da2df25fef2c1b4Ting-Yuan Huang for j, _ in enumerate(self.duts_): 284f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano yield j, self.matrix_[row][j] 285f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano 286f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano def _compute_initial_allocation_internal(self, level, N): 2872e307b303ac37c3e971086f23da2df25fef2c1b4Ting-Yuan Huang """Search matrix for d with N.""" 288f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano 289f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano if level == self.n_labels_: 290f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano return True 291f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano 292f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano for j, v in self.matrix_horizontal_generator(level): 293f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano if v == ' ': 294f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano # Before we put a 'Y', we check how many Y column 'j' has. 295f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano # Note y[0] is row idx, y[1] is the cell value. 296f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano ny = reduce(lambda x, y: x + 1 if (y[1] == 'Y') else x, 297f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano self.matrix_vertical_generator(j), 0) 298f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano if ny < N: 299f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano self.matrix_[level][j] = 'Y' 300f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano if self._compute_initial_allocation_internal(level + 1, N): 301ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen return True 302f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano self.matrix_[level][j] = ' ' 303ba64928c5dcbacbc70b4358881a89ad96227164dHan Shen 304f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano return False 305