WPABA 2011 - Final Program

Friday October 14, 2011 -- West Parlor

Time

First session: 9:00-10:00

9:00-9:10

Presentation

9:10-9:35

A GPU-Based Implementation of Differential Evolution for Solving the Gene Regulatory Network Model Inference Problem.
Luis E. Ramirez-Chavez, Carlos A. Coello Coello and Eduardo Rodriguez-Tello

9:35-10:00

GPU-based acceleration of bioinspired motion estimation model.
Fermin Ayuso, Guillermo Botella, Carlos García, Manuel Prieto and Francisco Tirado

10:00-10:30

Morning break

Time

Second session: 10:30-12:00

10:30-10:55

Fuzzy Logic based GA driven Reliable Multiprocessor System Design Optimization.
Anil Kumar and Shampa Chakarverty

10:55-11:20

Bioinspired Similarity-Based Planning Support for the Porting of Scientific Applications.
Wei Ding, Chung-Hsing Hsu, Oscar R. Hernandez, Barbara M. Chapman and Richard L. Graham

11:20-11:45

Parallel MOEA Implementation for Fast Evaluation of the 3D Thermal-Aware Floorplanning Problem.
Ignacio Arnaldo, José L. Risco-Martín, José Luis Ayala, José Manuel Colmenar, Alfredo Cuesta and José Ignacio Hidalgo

11:45-12:00

Questions and Workshop time

12:00-13:30

Lunch

Time

Third session: 13:30-15:00

13:30-13:55

The Impact of the Topology on Multiple Swarms Particle Optimization using Asynchronous Communication.
Arion Campos Jr, Aurora T. R. Pozo and Elias P. Duarte Jr.

13:55-14:20

Automatic Parallelization of Java Source Code for Multi-Core Systems Using Genetic Algorithms.
J. Manuel Colmenar, Alfredo Cuesta, José L. Risco-Martín, J. Ignacio Hidalgo and Juan Lanchares

14:20-14:45

DEVS-based parallel framework for Multi-Objective Evolutionary Algorithms.
Alejandro Moreno, Luís De La Torre, José L. Risco-Martin, Eva Besada-Portas, José L. Ayala and Joaquín Aranda

14:45-15:00

Questions and Workshop time

15:00-15:30

Afternoon break

 

A GPU-Based Implementation of Differential Evolution for Solving the Gene Regulatory Network Model Inference Problem.
Luis E. Ramirez-Chavez, Carlos A. Coello Coello and Eduardo Rodriguez-Tello
Abstract: In this paper, we present what we believe to be the first GPU-based implementation (using CUDA) for solving the gene regulatory network model inference problem. Our implementation uses differential evolution as the search engine, and adopts a power law system of differential equations (an S-System) for modelling the dynamics of the gene regulatory networks of our interest. Our preliminary results indicate that the use of GPUs produces an important reduction in the computational times required to solve this costly optimization problem. This could bring important benefits in Bioinformatics because of the many practical applications that the solution of this problem has.

GPU-based acceleration of bioinspired motion estimation model.
Fermin Ayuso, Guillermo Botella, Carlos García, Manuel Prieto and Francisco Tirado
Abstract: In this paper, we describe a specific and efficient implementation of a gradient-based optical flow model. This scheme has been particularized with a validated neuromorphic motion estimation system for the robust extraction of the image velocity. This model has many characteristics which enhance the capability regarding other optical flow gradient family algorithms. Our implementation has been performed using the specific graphic processors (GPUs) designing a framework ad-hoc for this model which can be reused in many machine vision approaches. As result is presented the throughput obtained in comparison with a general CPU and many applications which come from the scheme designed.

Fuzzy Logic based GA driven Reliable Multiprocessor System Design Optimization.
Anil Kumar and Shampa Chakarverty
Abstract: Fault tolerant systems are highly constrained and multi-objective in nature, making their design exploration particularly untraceable. In contrast with rigidly mathematical approaches such as Linear Programming (LP) and Mixed Integer Linear Programming (MILP), evolutionary algorithms are free to experiment with a variety of solutions by manipulating them in a guided manner. With their flexibility and nature-inspired heuristics, these algorithms are able to deliver near optimal results for mediums to large sized problems in polynomial time. Traditionally, the solutions are ranked based on their absolute fitness values. This generally results in wide variations in the solutions’ ranks even for small changes in their fitness values to realistic ranks. Results show the effectiveness of the fuzzy-based fitness evaluation model in generating high quality solutions. In order to tackle the design complexity of fault tolerant system design, we employ a hierarchical genetic algorithm where the search space is divided into four parts viz. selection of computing elements, tasks to processors mapping, selection of communication resources and finally, mapping data-transfers to values. Further, there is the problem of rationally attributing relative importance or weights to the array of different objectives involved in the system design. In this paper, we develop a fuzzy logic based fitness evaluation model that is driven by users’ varying and often approximate preferences for a set of quality parameters under different states of functionality. These are encapsulated in the form of fuzzy rules which guide the mapping of communication links. The hierarchical and phased evolution strategy is adaptive and responds to each fault by evolving it’s most efficient and cost-effective reconfigured architecture.

Bioinspired Similarity-Based Planning Support for the Porting of Scientific Applications.
Wei Ding, Chung-Hsing Hsu, Oscar R. Hernandez, Barbara M. Chapman and Richard L. Graham
Abstract: In this paper, we propose a methodology to address an important aspect of software porting that receives little attention, namely planning support. When a scientific application consisting of many subroutines is to be ported, the selection of key subroutines greatly impact the productivity and overall porting strategy because these subroutines may represent a significant aspect of the code in terms of functionality or performance. They may as well serve as indicators of the difficulty and amount of effort involved in porting a code to a new platform. The proposed methodology is based on the idea that similar subroutines can be ported with similar strategies and result in a similar porting. By viewing subroutines as DNA-like sequences, we are able to use various bioinformatics techniques to conduct the similarity analysis of subroutines. To the best of our knowledge, we are one of the first exploring this bioinspired view of program to the planning problem. In the paper we describe the methodology and present a tool called Klonos to facilitate the execution of the methodology. As a proof of concept, we use Klonos to conduct experiments on the OpenMP porting of several scientific benchmarks. We also identify the advantages and limitations of the bioinspired view of a program code.

Parallel MOEA Implementation for Fast Evaluation of the 3D Thermal-Aware Floorplanning Problem.
Ignacio Arnaldo, José L. Risco-Martín, José Luis Ayala, José Manuel Colmenar, Alfredo Cuesta and José Ignacio Hidalgo
Abstract: Thermal-aware floorplanning algorithms attempt to place hardware modules in order to spread heat dissipation, avoiding problems related to increasing transistor scale integration. Most of the proposals include an evolutionary algorithm for either partially or completely carry out the task. This accounts for an evaluation of the layout in thermal models that takes 99.5% of the computational time in the best floorplanning algorithm proposal so far and makes infeasible the optimization of complex many-core systems. The contribution of this paper is to present a parallelization of this evaluation phase in a Master-Worker model to achieve a dramatic speed-up of the thermal-aware floorplanning process.

The Impact of the Topology on Multiple Swarms Particle Optimization using Asynchronous Communication.
Arion Campos Jr, Aurora T. R. Pozo and Elias P. Duarte Jr.
Abstract: The high computational cost of complex optimization problems has motivated the development of parallel optimization algorithms. This paper investigates the impact of the topology on multiple swarms particle optimization using asynchronous communication. The total number of particles is divided into swarms that search for solutions independently. The communication among swarms occurs in an asynchronous way, i.e. messages are not exchanged periodically on fixed interval. When an improvement occurs on the best particle, this solution migrates among swarms. The goal is to take advantage of parallel execution for improving the solutions to speed up the optimization tasks. The proposed strategies were simulated and aspects of the information dissemination on different topologies are considered. Benchmark functions were implemented in a centralized environment as reference results. Next, the particles were distributed among swarms using different topologies. The impact of the topologies and communication among swarms are evaluated and the benefits obtained with the parallel strategy are analyzed, showing promising results.

Automatic Parallelization of Java Source Code for Multi-Core Systems Using Genetic Algorithms.
J. Manuel Colmenar, Alfredo Cuesta, José L. Risco-Martín, J. Ignacio Hidalgo and Juan Lanchares
Abstract: Parallelization of source code is a hard task that requires advanced programming skills as well as a deep knowledge of both the target program and the selected parallel paradigm. In addition, the parallelization of code for multi-core machines is influenced by the target hardware because the generation of too many threads may reduce performance. However, the parallelization of a code may be interpreted as the search for a combination of methods, some of them parallelized, that run without errors spending the less time possible in a target hardware. Therefore, following this approach, we propose an optimization flow that applies a genetic algorithm to find solutions in that search space. One of the key points of our optimization is the automatic generation of parallelized methods that, given the codification of an individual, provides the corresponding parallel code. As a result, our fully automated optimization flow reaches an average speedup of 2.02 compared to the exhaustive exploration in the analyzed benchmark. In addition, the parallelized codes provided by the optimization flow in our test runs are as fast as those obtained by the brute-force exploration method.

DEVS-based parallel framework for Multi-Objective Evolutionary Algorithms.
Alejandro Moreno, Luís De La Torre, José L. Risco-Martin, Eva Besada-Portas, José L. Ayala and Joaquín Aranda
Abstract: Discrete Event Specification (DEVS) is a sound formal modeling and simulation framework based on concepts derived from dynamic systems theory. DEVS provides a framework for information modeling with several advantages to analyze and design complex systems: completeness, verifiability, extensibility, and maintainability. Multi-Objective Evolutionary Algorithms (MOEAs) are stochastic optimization heuristics where the exploration of the solution space of a certain problem is carried out by imitating the population genetics stated in Darwin's theory of evolution. MOEAs have been successfully applied to many NP-hard combinatorial optimization problems. Optimization of these problems by MOEAs often demand a high computational cost. MOEA generally must iterate a substantial number of times to find a valid and good enough solution to a given problem. The research work presented in this document describes a generic DEVS framework that is able to automatically parallelize a MOEA with multithreading. This framework has been applied to the 3D thermal aware floorplanning problem, reaching excellent results. The parallel implementation of MOEA using DEVS multithread environment has allowed us to obtain optimized configurations with a speed-up of 4.51.