Package dsc_suite :: Package tools :: Module benchmarks
[hide private]
[frames] | no frames]

Source Code for Module dsc_suite.tools.benchmarks

  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 
11 12 ##### BENCHMARK CLASS ########################################################## 13 -class Benchmark(object):
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 # static members / constants 30 MODULETYPE = 0 31 DIMENSIONS = 1 32 CONNECTIONS = 2 33 # if something is changed here, also update the parsing methods 34 #DATA = [MODULETYPE, DIMENSIONS, CONNECTIONS] 35
36 - def __init__(self, data, status):
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
53 - def __abstract():
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
60 - def load_benchmark_file(filename):
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
77 - def parse_benchmark_string(self, text):
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
90 - def load_benchmark(self, filename):
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
104 - def get_status(self):
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
114 - def get_blocks(self):
115 """ get_blocks() -> blocks 116 117 blocks ... list of module names 118 119 Getter method for getting a list of module names. 120 """ 121 # Attention: returns a reference! 122 return self.data.keys()
123
124 - def rename_blocks(self, block_list):
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 # renaming blocks 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 # renaming connections 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
148 - def remove_blocks(self, block_list):
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
157 - def get_dimensions(self):
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 # Attention: returns references! 171 temp[i] = self.data[i][self.DIMENSIONS] 172 return temp
173
174 - def get_connections(self):
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 # Attention: returns references! 188 temp[i] = self.data[i][self.CONNECTIONS] 189 return temp
190
191 - def join(self, benchmark): # vielleicht auch den + operator der Klasse ueberschreiben
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
222 - def set_connections(self, connections):
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
234 - def add_connections(self, connections):
235 # maybe using a static method from RandomBench, where a connection list 236 # is derived from given block list 237 pass
238
239 - def remove_connections(self, connections):
240 pass
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 #from exceptions import ValueError 254 if not (self.status['number of dimensions'] == 2): 255 raise ValueError('transformation into 3D only possible for benchmarks previously 2d') 256 # different methods should be possible 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 # managed attributes (only works with python new style classes) 270 # which means inheriting from object 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 ##### YAL BENCHMARK SUBCLASS ################################################### 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
288 - def __init__(self, filename):
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
301 - def parse_benchmark_string(self, text):
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 # gewonnene daten speichern 329 data[modulename] = [moduletype, [xdim, ydim], []] 330 # iolist erst mal ignorieren 331 # spaeter notwendig, um herauszufinden, welche bloecke 332 # aussen liegen sollten (die meisten netze zu den ausgangspins) 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 # als letztes noch das naechste modul finden 343 modpos = text.find('MODULE', endmodpos+10) 344 345 # erst mal PARENT-Block ignorieren 346 for i in data: 347 if data[i][self.MODULETYPE] == 'PARENT': 348 temp = i 349 del(data[temp]) 350 351 # wenn VDD und GND raussollen, dann hier noch machen! 352 # wenn netznamen wichtig sind, auskommentieren! 353 self.transform(data) 354 355 return data
356
357 - def transform(self, data):
358 """ transform(data) 359 360 data ... parsed benchmark data 361 362 Transforms connections from net based to a combination of 363 priority plus partner information for each module. (i.e., 364 ['net1', 'net2', ...] -> {block_x : 3, block_y : 4, ...}) 365 Not efficient, yet. Possible improvements: exploit symmetries, 366 Modifies data dictionary given by reference! 367 """ 368 temp = dict() 369 for i in data: 370 temp[i] = dict() 371 for i in data: 372 for j in data: 373 # wie viele gemeinsame netze ? 374 cn = len(set(data[i][self.CONNECTIONS]).intersection(set(data[j][self.CONNECTIONS]))) 375 temp[i][j] = cn 376 for i in data: 377 data[i][self.CONNECTIONS] = temp[i]
378
379 380 ##### RANDOM BENCHMARK SUBCLASS ################################################ 381 -class RandomBench(Benchmark):
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 #TODO connections = self.generate_connections(interconnect_method, interconnect_percentage ... 426 # data format: {modulename: [moduletype, dimensions, connections]} 427 data = dict() 428 for module in dimensions: 429 data[module] = ['GENERAL', dimensions[module], {}] 430 Benchmark.__init__(self, data, status)
431 432 433 @staticmethod
434 - def generate_dimensions(n, method, aspect_ratio, area, ndigits):
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 # maybe later given by parameter flag 499 #aspect_ratio_distribution.sort() 500 #area_distribution.sort() 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
509 -class ACADEMIC(Benchmark):
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 """
515 - def __init__(self, filename):
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
524 - def parse_benchmark_string(self, text):
525 526 data = eval(text) 527 return data
528