In this paper, using the BSP/CGM model, we propose a parallel algorithm and implement it on a GPGPU to obtain a minimum spanning tree of a graph. Previous works for this problem are based on the solution of the list ranking problem which, though efficient in theory, did not produce good speedups in practice. In a later work, based on the idea of computing a structure called strut, we proposed a parallel algorithm under the BSP/CGP model to obtain a minimum spanning tree without using list ranking. It is based on the construction of an auxiliary bipartite graph and uses integer sorting. In this paper, we improve that work in some aspects. The proposed algorithm does not require the computation of the bipartite graph, and the strut construction does not require the sorting algorithm. The efficiency and scalability of the proposed algorithm are verified through experimental results obtained by an implementation on GPGPU.

In the last decades, with the advances in multicore/manycore architectures, it became interesting to design algorithms which can take advantage of such architectures aiming the achievement of more efficient algorithms to solve difficult problems. A large number of real-world problems solved with the help of computer programs demand faster or better quality solutions. Some of these problems can be modeled as classical theoretical problems, such as the 0-1 multidimensional knapsack problem (0-1 MKP), known to belong to the NP-hard class of problems, for which we can not obtain an exact solution efficiently. This motivates the search for alternative strategies which can achieve good quality approximate solutions, like metaheuristics, and also different ways to enable their execution in reduced times, such as parallel algorithms which explore multicore/manycore architectures. In this work we describe a parallelization of a simulated annealing approachusing GPGPU to solve 0-1 MKP and compare our results to previous works in order to prove the viability of its use.

The knapsack problem is a widely known problem in combinatorial optimization and has been object of many researches in the last decades. The problem has a great number of variants and obtaining an exact solution to any of these is not easily accomplished, which motivates the search for alternative techniques to solve the problem. Among these alternatives, augmented neural networks seem to be suitable on the search for approximate solutions for the problem. In this work we propose a parallel implementation for the multidimensional knapsack problem using augmented neural networks. The obtained results show that augmented neural networks allow efficient parallelization using CUDA: even smaller numbers of epoques resulted on equal or even better solutions than the sequential implementation. Differently, MPI implementation did not achieve satisfactory results.

Given a sequence $(A)$ of real numbers, we wish to find a list of all nonoverlapping contiguous subsequences of $(A)$ that are maximal. A maximal subsequence $(M)$ of $(A)$ has the property that no proper subsequence of $(M)$ has a greater sum of values. Furthermore, $(M)$ may not be contained properly within any subsequence of $(A)$ with this property. This problem has several applications in Computational Biology and can be solved sequentially in linear time. We present a BSP/CGM algorithm that solves this problem using $(p)$ processors in $(O (\vert A\vert/p))$ time and $(O (\vert A\vert/p))$ space per processor. The algorithm uses a constant number of communication rounds of size at most $(O (\vert A\vert/p))$. Thus, the algorithm achieves linear speedup and is highly scalable. To our knowledge, there are no previous known parallel BSP/CGM algorithms to solve this problem.

Abstract The InteGrade middleware intends to exploit the idle time of computing resources in computer laboratories. In this work we investigate the performance of running parallel applications with communication among processors on the InteGrade grid. As costly communication on a grid can be prohibitive, we explore the so‐called systolic or wavefront paradigm to design the parallel algorithms in which no global communication is used. To evaluate the InteGrade middleware we considered three parallel algorithms that solve the matrix chain product problem, the 0–1 Knapsack Problem, and the local sequence alignment problem, respectively. We show that these three applications running under the InteGrade middleware and MPI take slightly more time than the same applications running on a cluster with only LAM‐MPI support. The results can be considered promising and the time difference between the two is not substantial. The overhead of the InteGrade middleware is acceptable, in view of the benefits obtained to facilitate the use of grid computing by the user. These benefits include job submission, checkpointing, security, job migration, etc. Copyright © 2009 John Wiley & Sons, Ltd.

We present a new BSP/CGM parallel algorithm for the transitive closure problem. Our algorithm uses O(n/sup 3//p/spl alpha/) local computation time with O(p//spl alpha/) communication rounds, where /spl alpha/ is the size in bits that can be stored in a primitive data item. For all the randomly generated graphs that were used in the tests, the number of communication rounds was bounded by log p/spl bsol//spl alpha/+1. Our algorithm, even for the worst case, improves the previous results. The algorithm was implemented and the results show the efficiency and scalability of the presented algorithm and compare favorably with other parallel implementations.

Comparison of the DNA sequences and genes of two genomes can be useful to investigate the common functionalities of the corresponding organisms and get a better understanding of how the genes or groups of genes are organized and involved in several functions. We use high-performance parallel computing to compare the whole genomes of two organisms, namely Xanthomonas axonopodis pv. citri and Xanthomonas campestris pv. campestris, each with more than five million base pairs. Our purpose is two-fold. First we intend to exploit the high-performance power of a cluster of low-cost microcomputers, propose a parallel solution to this problem, and show its feasibility with implementation and performance results. Second we do additional comparisons of the two genomes by locating and compare not only the homologous genes (expressed in terms of the 20-letter amino acids) but also compare the regions or gaps (in terms of the 4-letter DNA nucleotides) between the corresponding homologous genes. We have implemented the proposed comparison strategy to compare the two genomes Xanthomonas axonopodis pv. citri (Xac) and Xanthomonas campestris pv. campestris (Xcc). The parallel platform used is a Beowulf cluster of 64 nodes consisting of low cost microcomputers. Xac has 5175554 base pairs and 4313 protein-coding genes while Xcc has 5076187 base pairs and 4182 protein-coding genes. The parallel solution is based on the dynamic programming approach and presents not only less processing time, but also better quality results as compared to approaches based on Blast and EGG.

We describe a parallel algorithm using the BSP/CGM model (Bulk Synchronous Parallel/Coarse Grained Multicomputer) to obtain the Euler tours in graphs. It is based on the PRAM (parallel random access machine) algorithm by Caceres et al. For an input graph of n vertices and m edges, the algorithm requires local computation time of O((m+n)/p), O((m+n'p) memory and O(logp) communication rounds, where p is the number of processors. To our knowledge there are no other parallel algorithms under the coarse-grained models for the Euler tours in graphs. The proposed algorithm is implemented using MPI (message passing interface) and the C language. The parallel program runs on a Beowulf with 66 nodes. The implementation results confirm the theoretical complexity results of the algorithm.

In this paper we present a coarse-grained parallel algorithm for solving the string edit distance problem for a string A and all substrings of a string C. Our method is based on a novel CGM/BSP parallel dynamic programming technique for computing all highest scoring paths in a weighted grid graph. The algorithm requires \log p rounds/supersteps and O(\fracn^2p\log m) local computation, where $p$ is the number of processors, p^2 \leq m \leq n. To our knowledge, this is the first efficient CGM/BSP algorithm for the alignment of all substrings of C with A. Furthermore, the CGM/BSP parallel dynamic programming technique presented is of interest in its own right and we expect it to lead to other parallel dynamic programming methods for the CGM/BSP.