======================================================================== PISA (www.tik.ee.ethz.ch/pisa/) ======================================================================== Department of Computer Science University of Amsterdam ======================================================================== MMPN - Multiprocessor Mappings of Process Networks Variator Implementation with PISALib Documentation file: mmpn_documentation.txt author: Cagkan Erbas, cagkan@science.uva.nl ======================================================================== The Problem =========== MMPN (Multiprocessor Mappings of Process Networks) is a 3-dimentional optimization problem which captures the trade-offs during the mapping stage in Sesame. The three trade-offs, namely the maximum processing time, power consumption, and total cost of the architecture are formulated as the multiple conflicting objectives of the mapping decision problem. @InProceedings{erbas03, author = {C. Erbas and S. Cerav-Erbas and A. D. Pimentel}, title = {A Multiobjective Optimization Model for Exploring Multiprocessor Mappings of Process Networks}, booktitle = {Proc. of the Int. Conference on Hardware/Software Codesign and System Synthesis}, month = {Oct.}, year = {2003}, } @Article{erbas06, author = {C. Erbas and S. Cerav-Erbas and A. D. Pimentel}, title = {Multiobjective Optimization and Evolutionary Algorithms for the Application Mapping Problem in Multiprocessor System-on-Chip Design}, journal = {IEEE Transactions on Evolutionary Computation}, year = 2006, volume = 10, number = 5, note = (to appear) } These two papers can be found in the 'papers' directory. The Variation ============= MMPN uses an integer vector representation for the individuals. There is a choice between different mutation and recombination operators (see 'The Parameters' section). The Parameters ============== MMPN uses the following values for the common parameters. These parameters are specified in 'PISA_cfg'. alpha (size of the initial population) mu (number of parent individuals) lambda (number of offspring individuals, has to be equal to mu) dim (number of objectives, has to be 3) MMPN takes a number of parameters which are supplied by the problem specification file. The name of this parameter file is passed to MMPN as command line argument (see the problem specification files in the 'problems' directory). seed seed for the random number generator length1 length of the bits for process mappings length2 length of the bits for channel mappings max_gene_values max integer values of the individual vector maxgen maximum number of generations outputfile name of file for output of the last population in archive recombination_mode set '0' for uniform, '1' for one point, '2' for two point crossover mutation_probability probability that a given individual goes into mutation recombination_probability probability that a given pair of individuals undergoes crossover gene_mutation_probability probability that a gene is mutated num_processor number of processors in the architecture num_memory number of memory elements in the architecture memory_set vector representing the number of memory elements reachable from the processor; this vector is indexed with respect to processor id (proc_id) processor input specification for a processor: [proc_id] [cp] [wpe] [wpc] [up] ... proc_id: processor id cp: processing capacity wpe: power dissipation during computation wpc: power dissipation during communication up: cost of the processor mem_id1: id of the first memory connected to the processor mem_id2: id of the second memory connected to the processor the number of mem_id's are specified (and thus should be) memory_set[proc_id] memory input specification for a memory: [mem_id] [cm] [wme] [um] mem_id: memory id (starts from num_processor and increases) cm: processing capacity wme: power dissipation during computation um: cost of the memory process input specification for a process: [p_id] [alfa_p] [beta_p] ... p_id: process id alfa_p: computational workload beta_p: communicational workload proc_id1: id of the first processor from its allele set channel input specification for a channel: [c_id] [source] [sink] [alfa_m] c_id: channel id (starts from length1) source: id of the source process sink: id of the sink process alfa_m: computational workload Source Files ============ Four generic files are taken from PISALib: 'variator.{h,c}' is a taken from PISALib. It contains the main function and all functions implementing the control flow. 'variator_internal.{h,c}' is taken from PISALib. It contains functions that are called by the functions in the 'variator' part and do the work in the background (file access etc.). 'variator_user.{h,c}' defines and implements the MMPN specific operations. Additionally, 'problems' directory contains three problem specifications. The 'tools' directory contains some additional tools which may be of interest for the user of this module. Usage ===== Call MMPN with the following arguments: mmpn paramfile filenamebase poll paramfile: specifies a problem specification (e.g. 'problems/mjpeg-arch1') filenamebase: specifies the name (and optionally the directory) of the communication files. The filenames of the communication files and the configuration file are built by appending 'sta', 'var', 'sel','ini', 'arc' and 'cfg' to the filenamebase. E.g., this gives the following names for the '../PISA_' filenamebase: ../PISA_cfg - configuration file ../PISA_ini - initial population ../PISA_sel - individuals selected for variation (parents) ../PISA_var - variated individuals (offspring) ../PISA_arc - individuals in the archive Caution: the filenamebase must be consistent with the name of the configuration file and the filenamebase specified for the selector module. poll: gives the value for the polling time in seconds (e.g. 0.5). This polling time must be larger than 0.01 seconds. Output ====== MMPN writes the content of the archive in the last generation to a specified output file. One individual is written per line using the following format: ID (max. proc time) (power cons.) (cost) chromosome Note that this file contains weakly nondominated points. From the 'tools' directory 'nondominated' program can be used to delete these weakly nondominated points. The other three programs in the 'tools' directory calculate the metrics defined in the IEEE TEC paper (see the Problem section). Limitations =========== The MMPN problem has three objectives which requires dim to be 3.