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.']}
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
32 MODULETYPE = 0
33 DIMENSIONS = 1
34 CONNECTIONS = 2
35
36 ORIGINAL = 0
37 ROTATED = 1
38
39 name = 'Data Structure'
40
42 self.benchmark = benchmark
43
44
45 self.num_parts = 0
46 self.part_lengths = []
47 self.num_representations = 0
48 self.best_representation = None
49
50 self.worst_solution = None
51
52
53
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
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
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
74
75 self.__abstract()
76
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
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
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
110
111
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
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
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
135
136
137
139 repr_number = randrange(self.num_representations)
140 return self.get_representation(repr_number)
141
142
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
165 """
166 returns packing in dict format
167 packing = {'name' : [x, y, z, w, h, d], ...}
168 """
169 self.__abstract()
170
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
197
198
199
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
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
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