1 """benchmarks
2
3 Helper module implementing benchmark reading and creation capabilities
4
5 Right now, YAL and ACADEMIC benchmark support is implemented.
6
7 TODO: when porting to python 3000 use abstract classes/methods
8 TODO: decide if the entities of a benchmark are named blocks or modules
9 """
10 from dsc_suite.tools.toolpaths import FOLDER_FOR_BENCHMARKS
14 """ class Benchmark() - encapsulating basic benchmark operations
15
16 Use this class for benchmark format independent operations.
17 E.g., use this class for random benchmark generation.
18
19 This class currently handles only rectangluar blocks (i.e.,
20 storing only dimension informations of blocks). Benchmark
21 status information is used to distinguish 2D/3D,
22 rectangular/rectilinear, ...
23
24 The most important variable is data, which stores the
25 benchmark information. It's format is as following:
26 data = {modulename : [moduletype, dimensions, connections]
27 where dimensions is a list and connections is a dictionary.
28 """
29
30 MODULETYPE = 0
31 DIMENSIONS = 1
32 CONNECTIONS = 2
33
34
35
37 """ Benchmark(data, status)
38
39 data ... data from an external source
40 status ... benchmark status dictionary
41
42 Takes data and creates an own benchmark instance. data needs to
43 be in the right format. No format testing is done!
44 Example status = {'source' : 'YAL',
45 'name' : filename,
46 'number of dimensions' : 2,
47 'shape of modules' : 'rectangluar'}
48 """
49 self._status = status
50 self.data = data
51
52 @staticmethod
54 """ static helper method to implement abstract methods """
55 import inspect
56 caller = inspect.getouterframes(inspect.currentframe())[1][3]
57 raise NotImplementedError(caller + ' must be imnplemented in subclass')
58
59 @staticmethod
61 """ load_benchmark_file(filename) -> string
62
63 filename ... benchmark file
64 string ... string representation of benchmark file
65
66 Loading benchmark file and reading content into a single
67 string for further processing.
68 (TODO: Exception handling)
69 """
70 string = str()
71 textfile = open(filename)
72 for i in textfile:
73 string += i
74 textfile.close()
75 return string
76
78 """ parse_benchmark_string(text) -> data
79
80 text ... string representation of benchmark file
81 data ... dictionary representation of benchmark
82
83 Abstract method!!! Needs to be implemented in subclass.
84
85 Parsing string representation of a SPECIFIC benchmark.
86 data format: {modulename: [moduletype, dimensions, connections]}
87 """
88 self.__abstract()
89
91 """ load_benchmark(filename)
92
93 filename ... benchmark file
94
95 This method shall be executed in every __init__ of a file based
96 benchmark (e.g., YAL). It loads the benchmark file and parses
97 the content into the data variable, which then is accessible
98 through several getter methods (e.g., get_blocks, get_dimensions)
99 or by direct access (e.g., blocks, dimensions).
100 """
101 text = self.load_benchmark_file(FOLDER_FOR_BENCHMARKS + '/' + filename)
102 self.data = self.parse_benchmark_string(text)
103
105 """ get_status() -> status
106
107 status ... dictionary containing status information regarding benchmark
108 status.keys() = ['source', 'name', 'number of dimensions', 'shapes of modules']
109
110 Getter method for the status dictionary.
111 """
112 return self._status
113
115 """ get_blocks() -> blocks
116
117 blocks ... list of module names
118
119 Getter method for getting a list of module names.
120 """
121
122 return self.data.keys()
123
125 """ rename_blocks(block_list)
126
127 block_list ... list of block name tuples
128
129 Renames blocks with a occurences in block_list.
130 block_list format: [[a,b], [c,d], ...]
131 Where a's new name would be b and c's new name d.
132 If there was a b or before it will be overwritten
133 without a warning.
134 """
135
136 for old, new in block_list:
137 if old in self.data:
138 self.data[new] = self.data[old]
139 del self.data[old]
140
141 for block in self.data:
142 for old, new in block_list:
143 if old in self.data[block][self.CONNECTIONS]:
144 self.data[block][self.CONNECTIONS][new] = self.data[block][self.CONNECTIONS][old]
145 del self.data[block][self.CONNECTIONS][old]
146
147
149 for name in block_list:
150 del self.data[name]
151 for block in self.data:
152 for name in block_list:
153 if self.data[block][self.CONNECTIONS].has_key(name):
154 del self.data[block][self.CONNECTIONS][name]
155
156
158 """ get_dimensions() -> dimensions
159
160 dimensions ... dictionary of module dimensions
161 dimensions format: {'M1' : [X, Y, Z], ...}
162
163 Getter method to a dictionary of module dimensions.
164 Dimensions are floats. Returns a dictionary with
165 dimensions corresponding to len(data[X][DIMENSIONS])
166 (i.e., 'number of dimensions').
167 """
168 temp = dict()
169 for i in self.data:
170
171 temp[i] = self.data[i][self.DIMENSIONS]
172 return temp
173
175 """ get_connections() -> connections
176
177 connections ... dictionary of module connections
178 connections format: {'MN' : connection weight factor, ...}
179
180 Getter method to a dictionary of module connections.
181 Returns a dictionary with connections to other any other
182 module. Maybe it could be optimized removing nonexisting
183 (i.e., weight == 0) connections.
184 """
185 temp = dict()
186 for i in self.data:
187
188 temp[i] = self.data[i][self.CONNECTIONS]
189 return temp
190
191 - def join(self, benchmark):
192 """ join(benchmark)
193
194 benchmark ... benchmark which is added to current data
195
196 Add new benchmark data to the current benchmark. Identical module names
197 are renamed. Only benchmarks with the same dimensionalty can be merged.
198 The resulting benchmark don't have connections between the modules of
199 the different benchmarks. So, typically further connections should be
200 added (e.g., using the random connection generator of the RandomBench
201 class).
202 """
203 from exceptions import ValueError
204 if not (self.status['number of dimensions'] == benchmark.status['number of dimensions']):
205 raise ValueError('joining benchmarks: number of dimensions does not match')
206
207 self._status['source'] += '; ' + benchmark.status['source']
208 self._status['name'] += '; ' + benchmark.status['name']
209
210 if not (benchmark.status['shape of modules'] in self.status['shape of modules']):
211 self._status['shape of modules'] += '; ' + benchmark.status['shape of modules']
212
213 for module in benchmark.data:
214 if module in self.blocks:
215 i = 1
216 while module+'-'+str(i) in self.blocks:
217 i += 1
218 self.data[module+'-'+str(i)] = benchmark.data[module]
219 else:
220 self.data[module] = benchmark.data[module]
221
223 for block in self.data:
224 if block in connections:
225 self.data[block][self.CONNECTIONS] = connections[block]
226 remove_list = []
227 for new in self.data[block][self.CONNECTIONS]:
228 if not new in self.data:
229 remove_list.append(new)
230 for wrong in remove_list:
231 del self.data[block][self.CONNECTIONS][wrong]
232
233
238
241
242 - def to_3d(self, z='half-minimum'):
243 """ to_3d(z)
244
245 z ... if integer: new z dimension of all modules
246
247 Transforms a current 2D benchmark into a 3D benchmark.
248
249 TODO: More versatile methods needs to be implemented.
250 (e.g., randomized z-dimension, folded 2d, ...)
251 """
252 assert z > 0
253
254 if not (self.status['number of dimensions'] == 2):
255 raise ValueError('transformation into 3D only possible for benchmarks previously 2d')
256
257 if (type(z) == int) or (type(z) == float):
258 new_z = z
259 elif z == 'half-minimum':
260 new_z = min(min(self.dimensions.values(), key=lambda x: x[0])[0],
261 min(self.dimensions.values(), key=lambda x: x[1])[1])
262 new_z /= float(2)
263 else:
264 raise ValueError('unconsidered parameter given')
265 for module in self.data:
266 self.data[module][self.DIMENSIONS].append(new_z)
267 self._status['number of dimensions'] = 3
268
269
270
271 status = property(get_status)
272 blocks = property(get_blocks)
273 dimensions = property(get_dimensions)
274 connections = property(get_connections, set_connections)
275
276
277
278 -class YAL(Benchmark):
279 """ class YAL(Benchmark) - reading yal benchmarks
280
281 Use this class to load a YAL file.
282 This is a 2D benchmark format.
283
284 Currently tested only for benchmarks from folders
285 'Beasley and OKP' and 'MCNC'.
286 """
287
289 """ YAL(filename)
290
291 filename ... YAL benchmark file
292
293 Loads YAL benchmark file and creates data set.
294 """
295 self._status = {'source' : 'YAL',
296 'name' : filename,
297 'number of dimensions' : 2,
298 'shape of modules' : 'rectangluar'}
299 self.load_benchmark(filename)
300
302 """ parse_benchmark_string(text) -> data
303
304 text ... string representation of benchmark file
305 data ... dictionary representation of benchmark
306
307 Parsing string representation of YAL benchmark.
308 data format: {modulename: [moduletype, dimensions, connections]}
309 """
310 data = dict()
311 searchpos = 0
312
313 modpos = text.find('MODULE', searchpos)
314
315 while modpos != -1:
316 endmodpos = text.find('ENDMODULE', modpos)
317 modulename = text[modpos+7:text.find(';', modpos)].strip()
318 typepos = text.find('TYPE', modpos)
319 moduletype = text[typepos+5:text.find(';', typepos)].strip()
320 dimpos = text.find('DIMENSIONS', modpos)
321 dims = text[dimpos+11:text.find(';', dimpos)].split()
322 xdim = (max(float(dims[0]), float(dims[2]), float(dims[4]), float(dims[6]))
323 - min(float(dims[0]), float(dims[2]), float(dims[4]), float(dims[6])))
324 assert xdim >= 0
325 ydim = (max(float(dims[1]), float(dims[3]), float(dims[5]), float(dims[7]))
326 - min(float(dims[1]), float(dims[3]), float(dims[5]), float(dims[7])))
327 assert ydim >= 0
328
329 data[modulename] = [moduletype, [xdim, ydim], []]
330
331
332
333 netpos = text.find('NETWORK', modpos)
334 endnetpos = text.find('ENDNETWORK', netpos)
335 semicolon = text.find(';', netpos)
336 nextsemicolon = text.find(';', semicolon+1)
337 while nextsemicolon < endnetpos < endmodpos:
338 network = text[semicolon+1:nextsemicolon].split()
339 data[network[1]][self.CONNECTIONS] = network[2:]
340 semicolon, nextsemicolon = nextsemicolon, text.find(';', nextsemicolon+1)
341
342
343 modpos = text.find('MODULE', endmodpos+10)
344
345
346 for i in data:
347 if data[i][self.MODULETYPE] == 'PARENT':
348 temp = i
349 del(data[temp])
350
351
352
353 self.transform(data)
354
355 return data
356
378
382
383 """ class RandomBench(Benchmark) - generates random benchmark
384
385 Use this subclass to the basic Benchmark class to generate
386 random benchmarks. Various approaches can be used (i.e.,
387 different distributions for both, area and aspect ratio of
388 generated modules). Generation of a 2D benchmark.
389 """
390
391 - def __init__(self, n=10, method='uniform', aspect_ratio=(1,2), area=(10,100), ndigits=1):
392 """ Benchmark(n, method, aspect_ratio, area)
393
394 n ... number of generated modules
395 method ... random generation method
396 aspect_ratio ... tuple (a, b), parameterizing aspect ratio
397 area ... tuple (a, b), parameterizing area
398 ndigits ... number of digits used for rounding
399
400 Generates random benchmark with n modules. For generation of random
401 benchmarks a variety of approaches can be used (determined by given
402 method). Area and aspect ratio of modules are limited by a tuple
403 (e.g., (1.3, 2.5)).
404
405 Following methods are possible:
406 'uniform' ... uniform distribution
407 'gauss' ... gauss distribution
408 'half-gauss' ... folded gauss distribution
409 'exponential' ... exponetial distribution
410
411 Combination of different methods possible to use a different
412 distribution for aspect ratio and area, respectively.
413 (e.g., 'uniform/gauss' -> uniform distribution for aspect ratio,
414 gauss distribution for area)
415
416 The meaning of the tuple (a, b) is as follows:
417 a ... the lower/left limit
418 b ... the upper/right limit
419 """
420 status = {'source' : 'Random Benchmark',
421 'name' : "%s, %s, ar=%s, area=%s" % (str(n), method, str(aspect_ratio), str(area)),
422 'number of dimensions' : 2,
423 'shape of modules' : 'rectangluar'}
424 dimensions = self.generate_dimensions(n, method, aspect_ratio, area, ndigits)
425
426
427 data = dict()
428 for module in dimensions:
429 data[module] = ['GENERAL', dimensions[module], {}]
430 Benchmark.__init__(self, data, status)
431
432
433 @staticmethod
435
436 """ generate_dimensions(n, method, aspect_ratio, area) -> dimensions
437
438 n ... number of generated modules
439 method ... random generation method
440 aspect_ratio ... tuple (a, b), parameterizing aspect ratio
441 area ... tuple (a, b), parameterizing area
442 ndigits ... number of digits used for rounding
443 dimensions ... dictionary with n random generated dimensions
444
445 Generates random dimensions with n modules. For generation of random
446 benchmarks a variety of approaches can be used (determined by given
447 method). Area and aspect ratio of modules are limited by a tuple
448 (e.g., (1.3, 2.5)).
449
450 Following methods are possible:
451 'uniform' ... uniform distribution
452 'gauss' ... gauss distribution
453 'half-gauss' ... folded gauss distribution
454 'exponential' ... exponetial distribution
455
456 Combination of different methods possible to use a different
457 distribution for aspect ratio and area, respectively.
458 (e.g., 'uniform/gauss' -> uniform distribution for aspect ratio,
459 gauss distribution for area)
460
461 The meaning of the tuple (a, b, c) is as follows:
462 a ... the lower/left limit
463 b ... the upper/right limit
464
465 TODO: Depending on method, various parameters can be given for the
466 distribution. Currently predetermined parameters are used.
467 'uniform' ... lower limit, upper limit
468 'gauss/half-gauss' ... mu - mean value, sigma - standard deviation
469 'exponential' ... lambda
470
471 FUTURE IDEA: Implementing a flag random, which determines, if the
472 returned distributions are randomized or calculated (e.g., uniform
473 can mean: uniform random distribution or real uniform distribution,
474 such as range(1,10))
475
476 2nd FUTURE IDEA: Generating dimensions by randomizing not aspect ratio
477 and area, but width and height directly!!!
478 """
479 from exceptions import ValueError
480 from dsc_suite.tools.combinatorics import EnumerativeCombinatorics
481 from dsc_suite.tools.statistics import ProbabilityDistributions
482
483 method_list = ProbabilityDistributions.IMPLEMENTED_DISTRIBUTIONS
484 method_variations = EnumerativeCombinatorics.vary(method_list, 2)
485 possible_methods = [m[0]+'/'+m[1] for m in method_variations] + method_list
486 if not (method in possible_methods):
487 raise ValueError('%s is not a valid distribution for RandomBench!' % method)
488
489 if '/' in method:
490 aspect_ratio_method, area_method = method.split('/')
491 else:
492 aspect_ratio_method = method
493 area_method = method
494
495 aspect_ratio_distribution = ProbabilityDistributions.get_distribution(n, aspect_ratio_method, *(aspect_ratio))
496 area_distribution = ProbabilityDistributions.get_distribution(n, area_method, *(area))
497
498
499
500
501
502 dimensions = dict()
503 for i in range(n):
504 width = (area_distribution[i]/aspect_ratio_distribution[i])**0.5
505 height = area_distribution[i]/width
506 dimensions['M%02i' % i] = [round(width, ndigits), round(height, ndigits)]
507 return dimensions
508
510 """ class YAL(Benchmark) - reading academic benchmarks
511
512 Use this class to load a ACADEMIC file.
513 This is a 3D benchmark format.
514 """
516
517 self._status = {'name' : filename,
518 'number of dimensions' : 3,
519 'shape of modules' : 'rectangular',
520 'source' : 'BrainOfMine'}
521 self.load_benchmark(filename)
522
523
525
526 data = eval(text)
527 return data
528