Improvements in the score matrix calculation method using parallel score estimating algorithm

The increasing amount of sequences stored in genomic databases has become unfeasible to the sequential analysis. Then, the parallel computing brought its power to the Bioinformatics through parallel algorithms to align and analyze the sequences, providing improvements mainly in the running time of these algorithms. In many situations, the parallel strategy contributes to reducing the computational complexity of the big problems. This work shows some results obtained by an implementation of a parallel score estimating technique for the score matrix calculation stage, which is the first stage of a progressive multiple sequence alignment. The performance and quality of the parallel score estimating are compared with the results of a dynamic programming approach also implemented in parallel. This comparison shows a significant reduction of running time. Moreover, the quality of the final alignment, using the new strategy, is analyzed and compared with the quality of the approach with dynamic programming.

A transactional runtime system for the Cell/BE architecture

Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)

Energy-performance tradeoffs in software transactional memory

Transactional memory (TM) is a new synchronization mechanism devised to simplify parallel programming, thereby helping programmers to unleash the power of current multicore processors. Although software implementations of TM (STM) have been extensively analyzed in terms of runtime performance, little attention has been paid to an equally important constraint faced by nearly all computer systems: energy consumption. In this work we conduct a comprehensive study of energy and runtime tradeoff sin software transactional memory systems. We characterize the behavior of three state-of-the-art lock-based STM algorithms, along with three different conflict resolution schemes. As a result of this characterization, we propose a DVFS-based technique that can be integrated into the resolution policies so as to improve the energy-delay product (EDP). Experimental results show that our DVFS-enhanced policies are indeed beneficial for applications with high contention levels. Improvements of up to 59% in EDP can be observed in this scenario, with an average EDP reduction of 16% across the STAMP workloads. © 2012 IEEE.

Transaction scheduling using dynamic conflict avoidance

Software transaction memory (STM) systems have been used as an approach to improve performance, by allowing the concurrent execution of atomic blocks. However, under high-contention workloads, STM-based systems can considerably degrade performance, as transaction conflict rate increases. Contention management policies have been used as a way to select which transaction to abort when a conflict occurs. In general, contention managers are not capable of avoiding conflicts, as they can only select which transaction to abort and the moment it should restart. Since contention managers act only after a conflict is detected, it becomes harder to effectively increase transaction throughput. More proactive approaches have emerged, aiming at predicting when a transaction is likely to abort, postponing its execution. Nevertheless, most of the proposed proactive techniques are limited, as they do not replace the doomed transaction by another or, when they do, they rely on the operating system for that, having little or no control on which transaction to run. This article proposes LUTS, a lightweight user-level transaction scheduler. Unlike other techniques, LUTS provides the means for selecting another transaction to run in parallel, thus improving system throughput. We discuss LUTS design and propose a dynamic conflict-avoidance heuristic built around its scheduling capabilities. Experimental results, conducted with the STAMP and STMBench7 benchmark suites, running on TinySTM and SwissTM, show how our conflict-avoidance heuristic can effectively improve STM performance on high contention applications. © 2012 Springer Science+Business Media, LLC.

Algoritmos busca tabu paralelos aplicados ao planejamento da expansão da transmissão de energia elétrica

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES)

Geração de algoritmos de escalonamento para simulação de grades computacionais

Pós-graduação em Ciência da Computação - IBILCE

Estratégia de decomposição aplicada ao problema de planejamento da expansão de sistemas de distribuição

Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)

Avaliação de Desempenho de Aplicações Paralelas Utilizando MPI e PETSc

This work presents a study about the use of standards and directions on parallel programming in distributed systems, using the MPI standard and PETSc toolkit, performing an analysis of their performances over certain mathematic operations involving matrices. The concepts are used to develop applications to solve problems involving Principal Components Analysis (PCA), which are executed in a Beowulf cluster. The results are compared to the ones of an analogous application with sequencial execution, and then it is analized if there was any performance boost on the parallel application

Three-Dimensional Semiautomatic Road Extraction From a High-Resolution Aerial Image by Dynamic-Programming Optimization in the Object Space

Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)

Bifurcation Analysis of a Van der Pol-Duffing Circuit with Parallel Resistor

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES)

Design and Analysis of Optical Interconnection Networks for a Dataflow Parallel Computer

This work shows the design, simulation, and analysis of two optical interconnection networks for a Dataflow parallel computer architecture. To verify the optical interconnection network performance on the Dataflow architecture, we have analyzed the load balancing among the processors during the parallel programs executions. The load balancing is a very important parameter because it is directly associated to the dataflow parallelism degree. This article proves that optical interconnection networks designed with simple optical devices can provide efficiently the dataflow requirements of a high performance communication system.

Binary integer programming formulations for scheduling in market-driven foundries

This paper describes the development and solution of binary integer formulations for production scheduling problems in market-driven foundries. This industrial sector is comprised of small and mid-sized companies with little or no automation, working with diversified production, involving several different metal alloy specifications in small tailor-made product lots. The characteristics and constraints involved in a typical production environment at these industries challenge the formulation of mathematical programming models that can be computationally solved when considering real applications. However, despite the interest on the part of these industries in counting on effective methods for production scheduling, there are few studies available on the subject. The computational tests prove the robustness and feasibility of proposed models in situations analogous to those found in production scheduling at the analyzed industrial sector. (C) 2010 Elsevier Ltd. All rights reserved.

Modeling and analysis of artificial neural networks applied in operations research

Artificial neural networks are dynamic systems consisting of highly interconnected and parallel nonlinear processing elements. Systems based on artificial neural networks have high computational rates due to the use of a massive number of these computational elements. Neural networks with feedback connections provide a computing model capable of solving a rich class of optimization problems. In this paper, a modified Hopfield network is developed for solving problems related to operations research. The internal parameters of the network are obtained using the valid-subspace technique. Simulated examples are presented as an illustration of the proposed approach. Copyright (C) 2000 IFAC.

An investigation on parallel, divergent and convergent acetylene dual jet diffusion flames

Results are presented and discussed of an experimental investigation on acetylene turbulent dual jet diffusion flames. The study includes parameters of flames in parallel, divergent and convergent configurations. Tests with two parallel jets with addition of helium in the fuel stream were also performed and analysed. The variation of overall flame length and of other name physical characteristics, such as width, volume and conditions for lifting, are presented as functions of burner tip Reynolds number, jet distance from each other and inclination angle. The effects of diluent concentration in the fuel gas stream are presented for single and two parallel jets. (C) 1999 Elsevier B.V. Ltd.

A Beam Search Method to Solve the Problem of Assignment Cells to Switches in a Cellular Mobile Network

Assigning cells to switches in a cellular mobile network is known as an NP-hard optimization problem. This means that the alternative for the solution of this type of problem is the use of heuristic methods, because they allow the discovery of a good solution in a very satisfactory computational time. This paper proposes a Beam Search method to solve the problem of assignment cell in cellular mobile networks. Some modifications in this algorithm are also presented, which allows its parallel application. Computational results obtained from several tests confirm the effectiveness of this approach and provide good solutions for large scale problems.