Package dsc_suite :: Package ds :: Module data_structure
[hide private]
[frames] | no frames]

Source Code for Module dsc_suite.ds.data_structure

  1  """module data_structure 
  2   
  3  This module implements the basic data structure interface. 
  4  """ 
  5   
  6  from dsc_suite.routing.estimations import middle_point_manhatten 
  7  from random import randrange 
  8   
  9  """ dictionary of supported cost evaluation methods 
 10  key ... short name 
 11  value ... [index, 'name', 'Information'] 
 12  Order is important as used in the cost_evaluation function, 
 13  as a dictionary don't represent an ordered list, an index is 
 14  required. 
 15  """ 
 16  COST_CRITERIA_LIST = {'MPMWE' : [0, 'Middle point Manhatten wirelength estimation', 'Calculates shortest Manhatten distance between two points. Assumes the Pins of each module in its middle. Supports net weights (e.g., as in the YAL benchmarks).'], 
 17                        'HESA' : [1, 'Half of enveloping surface area', 'Calculates the half of the surrounding (bounding) box area, thus includes unused whitespace.']} 
18 19 20 ##### DATA STRUCTURE CLASS ##################################################### 21 -class DataStructure(object):
22 """ class DataStructure() - defines basic data structure interface 23 24 Used by Optimization Algorithms to access the implemented data 25 structure subclasses. The needed module data is obtained using the 26 Benchmark class. The most important variable is data, which stores 27 the benchmark information. It's format is as following: 28 data = {modulename : [moduletype, dimensions, connections] 29 where dimensions is a list and connections is a dictionary. 30 """ 31 # static members / constants 32 MODULETYPE = 0 33 DIMENSIONS = 1 34 CONNECTIONS = 2 35 36 ORIGINAL = 0 37 ROTATED = 1 38 39 name = 'Data Structure' 40
41 - def __init__(self, benchmark):
42 self.benchmark = benchmark 43 # the following attributes are needed and concretized 44 # in the according subclasses 45 self.num_parts = 0 46 self.part_lengths = [] 47 self.num_representations = 0 48 self.best_representation = None 49 #self.best_representation_index = None 50 self.worst_solution = None 51 # cost 1 ... footprint area 52 # cost 2 ... total wirelength 53 # single parts dont belong necessarily to the same solution 54 self.worst_cost_parts = [0, 0] 55 self.best_cost_parts = [float('inf'), float('inf')] 56 self.cost_part_names = ['Half Surface', 'Wirelength']
57 58 @staticmethod
59 - def __abstract():
60 """ static helper method to implement abstract methods """ 61 import inspect 62 caller = inspect.getouterframes(inspect.currentframe())[1][3] 63 raise NotImplementedError(caller + ' must be imnplemented in subclass')
64
65 - def set_benchmark(self, benchmark):
66 """ set_benchmark(benchmark) 67 68 benchmark ... sets benchmark which is currently used 69 70 Loading benchmark into data structure. So all the important informations 71 (e.g., number of modules, dimensions, ...) can be used. 72 """ 73 # TODO: Really required?? If yes, update data structure relevant 74 # information (e.g., part_lengths, num_representations)!!! 75 self.__abstract()
76
77 - def get_all_representations(self):
78 """ generate_abstract_soltioins() -> abstract_solutions 79 80 abstract_solutions ... list of all possible abstract solutions 81 82 This method generates all possible abstract solutions. The returned 83 format is strongy dependend on the underlying data structure. When 84 benchmarks with a big number of modules is loaded very long 85 computation and intense memory and processor usage can occur! 86 """ 87 representations = [] 88 i = 0 89 while i < self.num_representations: 90 representations.append(self.get_representation(i)) 91 i += 1 92 return representations
93
94 - def get_part_of_representation(self, part_index, part_number):
95 """ 96 get a single element out of a part of the abstract 97 representation, part_number between 0 and part_lengths[part_index] 98 """ 99 self.__abstract()
100
101 - def get_representation(self, number):
102 """ 103 number ranges between 0 and num_representations-1 104 global mapping method to get a specific representation out 105 of all the abstract representations. 106 Not optimal, cause its used very often to generate 107 the solution space. So take care! 108 """ 109 # this function is called very often while generating 110 # the whole solution space, so the import function or 111 # a lambda function at this point could be sub optimal 112 assert(number < self.num_representations) 113 representation = [] 114 for part_index in range(self.num_parts): 115 part_number = number//reduce(lambda a,b:a*b, self.part_lengths[part_index+1:]+[1]) % self.part_lengths[part_index] 116 representation.append(self.get_part_of_representation(part_index, part_number)) 117 return representation
118
119 - def get_part_numbers(self, number):
120 assert(number < self.num_representations) 121 part_numbers = [] 122 for part_index in range(self.num_parts): 123 part_number = number//reduce(lambda a,b:a*b, self.part_lengths[part_index+1:]+[1]) % self.part_lengths[part_index] 124 part_numbers.append(part_number) 125 return part_numbers
126
127 - def convert_part_numbers(self, part_numbers):
128 number = 0 129 for part_index in range(self.num_parts): 130 number += part_numbers[part_index] * reduce(lambda a,b:a*b, self.part_lengths[part_index+1:]+[1]) 131 return number
132
133 - def __getitem__(self, key):
134 return self.get_representation(key)
135 136 # TODO: def get_number_of_representation ??? 137
139 repr_number = randrange(self.num_representations) 140 return self.get_representation(repr_number)
141 142
143 - def generate_solution_space(self):
144 """ 145 OBSOLETE!!! 146 147 assuming seperate lists, sequences, etc. 148 (e.g., representations = (locii1_permutations, locii2_permutations)) 149 so that a for each element in each part of the datastructrure 150 the combination which each other element combination of the other parts 151 is assumed to be the abstract_solution. 152 This is done due to lower memory usage. 153 154 """ 155 print "Generating solution space" 156 print "Number of solutions: ", self.num_representations 157 counter = 0 158 costs_list = [] 159 while counter < self.num_representations: 160 costs_list.append(self.cost_evaluation(self.get_representation(counter))) 161 counter += 1 162 return costs_list
163
164 - def create_packing(self, representation):
165 """ 166 returns packing in dict format 167 packing = {'name' : [x, y, z, w, h, d], ...} 168 """ 169 self.__abstract()
170
171 - def packing_to_representation(self, packing):
172 """ 173 is not possible with every data structure 174 """ 175 self.__abstract()
176
177 - def cost_evaluation(self, representation, criteria=['MPMWE', 'HESA'], return_packing=False):
178 """ Calculate and return costs of current representation applied to benchmark. 179 180 criteria ... cost evaluation criteria to calculate, list 181 return_packing ... if True also return packing 182 costs ... return a list of costs 183 184 This pre-implemented cost_evaluation can be used data structure 185 independent. But for some specific data structures it could be 186 possible to optimize the evaluation by using internal information. 187 188 Supported criteria listed in COST_CRITERIA_LIST. 189 Short names are used. Parameter criteria is in list format. 190 191 !!Instead of changing calculation of existent criteria, add a new one!! 192 193 Weights and cost factors have to be implemented inside optimization. 194 """ 195 packing = self.create_packing(representation) 196 # TODO check whether or not packing is overlapping free 197 # if it is done it could be runtime expensive 198 # from dsc_suite.tools.geometry import valid_packing 199 # assert(valid_packing(packing)) 200 if 'HESA' in criteria: 201 nod = self.benchmark.status['number of dimensions'] 202 temp = max(packing.values(), key=lambda x: x[0]+x[nod]) 203 width = temp[0] + temp[nod] 204 temp = max(packing.values(), key=lambda x: x[1]+x[1+nod]) 205 height = temp[1] + temp[1+nod] 206 temp = max(packing.values(), key=lambda x: x[2]+x[2+nod]) 207 depth = temp[2] + temp[2+nod] 208 cost_HESA = width * height + width * depth + height * depth 209 else: 210 cost_HESA = None 211 if 'MPMWE' in criteria: 212 cost_MPMWE = 0.0 213 for i in packing: 214 temp = self.benchmark.connections[i] 215 for j in temp: 216 net_weight = self.benchmark.connections[i][j] 217 net_length = middle_point_manhatten(packing[i], packing[j]) 218 cost_MPMWE += net_weight*net_length 219 else: 220 cost_MPMWE = None 221 """ Attend to conformity with COST_CRITERIA_LIST """ 222 costs = [cost_MPMWE, cost_HESA] 223 if return_packing: 224 return [costs[i] for i in [COST_CRITERIA_LIST[c][0] for c in criteria]], packing 225 return [costs[i] for i in [COST_CRITERIA_LIST[c][0] for c in criteria]]
226
227 - def get_operations(self):
228 """ 229 returns a dict of possible operations onto a abstract solution 230 {'name' : [function, globality_factor]} 231 globality_factor ... the higher, the bigger is the solution change 232 this factor is given by the authors but it also can be determined 233 in test runs evaluation the cost influences caused by applying the 234 according function. 235 """ 236 self.__abstract()
237
238 - def merge_representations(self, representation_a, representation_b):
239 """ Merge two representations into all possible children. 240 241 Typically, used for genetic and/or evolutionary algorithms. 242 Returns a list with all possible children. 243 """ 244 self.__abstract()
245