Friday October
14, 2011 -- West Parlor
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. |
9:35-10:00 |
GPU-based acceleration of bioinspired motion estimation model. |
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. |
10:55-11:20 |
Bioinspired Similarity-Based Planning Support for the Porting of Scientific Applications. |
11:20-11:45 |
Parallel MOEA Implementation for Fast Evaluation of the 3D Thermal-Aware Floorplanning Problem. |
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. |
13:55-14:20 |
Automatic Parallelization of Java Source Code for Multi-Core Systems Using Genetic Algorithms. |
14:20-14:45 |
DEVS-based parallel framework for Multi-Objective Evolutionary Algorithms. |
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.