Search

There has been an increasing interest in running High Performance Computing (HPC) applications in the cloud, mainly due to rapid resource provisioning and significant reduction of operational costs. Biological sequence comparison is an important HPC application that compares sequences in search of similarities. MASA-OpenMP is a highly optimized sequence comparison tool that obtains optimal results. Yet, it can take a long time, depending on the number of sequences compared and their lengths. The Covid-19 pandemic study is of particular interest nowadays, and the comparison of SARS-CoV-2 sequences is crucial to understanding this disease. In this paper, we compare SARS-CoV-2 sequences with MASA-OpenMP in the Amazon Elastic Compute Cloud (Amazon EC2), using both spot and on-demand instances. To efficiently execute a MASA-OpenMP application composed of more than 22,000 tasks on EC2 respecting a given deadline, we propose an execution modeling for MASA-OpenMP on top of the Burst-HADS framework. Burst-HADS is a spot instance-based dynamic scheduler for Bag-of-Tasks applications in the cloud, which minimizes both execution time and financial costs regarding a given deadline even in the presence of spot interruptions. Performance results reveal that, by using spots, our Burst-HADS strategy considerably reduces the monetary cost for executing 22,600 SARS-CoV-2 sequence comparisons with MASA-OpenMP when contrasted to the on-demand only approach. We also show that our strategy can meet the deadlines, even in scenarios with several spot interruptions.

Sequence comparison is a task performed in several Bioinformatics applications daily all over the world. Algorithms that retrieve the optimal result have quadratic time complexity, requiring a huge amount of computing power when the sequences compared are long. In order to reduce the execution time, many parallel solutions have been proposed in the literature. Nevertheless, depending on the sizes of the sequences, even those parallel solutions take hours or days to complete. Pruning techniques can significantly improve the performance of the parallel solutions and a few approaches have been proposed to provide pruning capabilities for sequence comparison applications. This paper proposes and evaluates a variant of the block pruning approach that runs in multiple GPUs, in homogeneous or heterogeneous environments. Experimental results obtained with DNA sequences in two testbeds show that significant performance gains are obtained with pruning, compared to its non-pruning counterpart, achieving the impressive performance of 694.8 GCUPS (Billions of Cells Updated per Second) for four GPUs.

In the Amazon EC2 cloud provider, the price of spot instances is much lower than on demand instances, however, at the cost of availability issues of the former. Recently, several strategies were proposed to analyze the Amazon EC2 spot pricing model employing techniques such as statistical and probabilistic modeling and neural networks. To the best of our knowledge, there is no work in the literature that can accurately capture the trade-off between price and availability in favor of user decision-making. In this work, we propose and evaluate a utility-based strategy that balances spot instance cost and availability to Amazon EC2 users. Our experiments show that the average availability reaches up to 98% for spot instances, using data gathered from Amazon (September to November 2016), and a bid value below 28% of the on demand price for the m4.10xlarge general purpose instance type.

In this paper, we propose and evaluate CUDASankoff, a solution to the RNA structural alignment problem based on the Sankoff algorithm in Graphics Processing Units (GPUs). To our knowledge, this is the first time the Sankoff algorithm is implemented in GPU. In our solution, we show how to linearize the Sankoff 4-dimensional dynamic programming (4D DP) matrix and we propose a two-level wavefront approach to exploit the parallelism. The results were obtained with two different NVidia GPUs, comparing sets of real RNA sequences with lengths from 46 to 281 nucleotides. We show that our GPU approach is up to 24 times faster than a 16-core CPU solution in the 281 nucleotide Sankoff execution.

International audience; Configuring and executing application across multiple clouds is a challenging task due to the various terminologies used by cloud providers to describe their services and features. Likewise, the services are regularly offered at different levels of abstraction, such as infrastructure-as-a-service (IaaS) and platform-as-a-service (PaaS). While IaaS services provide low-level access to the infrastructure, PaaS services enable the users to delegate the management of the computing environment to the cloud providers. Consequently, at the IaaS level, the users are responsible for managing the computing resources, whereas, at the PaaS level, the users must develop native cloud applications following the constraints defined by the PaaS provider. These two options exist, mostly because the clouds target web applications, whereas users' applications are commonly batch-oriented. Considering how difficult is the task of configuring and executing applications across various clouds, we advocate the use of autonomic systems to do this work automatically. For this purpose, in this paper, we propose and evaluate an autonomic and goal-oriented system. Our system implements self-configuration, self-healing, and context-awareness properties. In addition, it relies on a hierarchical P2P overlay (a) to manage the virtual machines running on the clouds and (b) to deal with inter-cloud communication. Likewise, it depends on a software product line engineering (SPLE) method to enable applications' deployment and reconfiguration at runtime, without requiring pre-configured virtual machine images. Experimental results show that our system frees the users from the duty of configuring and managing the execution of a non-native application on single clouds and over many clouds. In particular, our system tackles the lack of middleware prototypes that can support different scenarios when using simultaneous services from multiple clouds.

Biological sequence comparison is a very common task in Bioinformatics applications. Many parallel solutions have been proposed for this problem, using different HPC platforms, programmed usually with platform-specific languages and frameworks. With this approach, it is difficult to port solutions among different platforms such as CPUs and GPUs, for instance. To tackle this problem, this paper proposes and evaluates an OpenCL parallel solution for Biological Sequence Comparison, which was integrated to the CUDAlign Megabase Sequence Comparison tool. The evaluation of our solution shows we were able to obtain a program for CPUs and GPUs (NVidia and AMD) with basically the same OpenCL code. In addition, in the comparison with SW# and CUDAlign optimized CUDA codes, we show that the performance of our OpenCL version has comparable and, many times, superior performance.

In this paper, we propose and evaluate a parallel solution for the exact Multiple Sequence Alignment problem based on the A-Star algorithm. In our parallel solution, we use a multi-index data structure, templates and a locality-sensitive hash function. The results were collected in two machines (4 cores and 32 cores), with real and synthetic sequence sets ranging from 3 to 14 sequences. We show that our parallel solution executes 2.89× and 4.77× faster than a state-of-the-art parallel MSA tool, with a proportional increase in memory usage, when comparing 2 hard instances of the benchmark Bali base reference set 1.

This paper proposes and evaluates a strategy to run Biological Sequence Comparison applications on hybrid platforms composed of GPUs and multicores with SIMD extensions. Our strategy provides multiple task allocation policies and the user can choose the one which is more appropriate to his/her problem. We also propose a workload adjustment mechanism that tackles situations that arise when slow nodes receive the last tasks. The results obtained comparing query sequences to 5 public genomic databases in a platform composed of 4 GPUs and 2 multicores show that we are able to reduce the execution time with hybrid platforms, when compared to the GPU-only solution. We also show that our workload adjustment technique can provide significant performance gains in our target platforms.

Smith-Waterman (SW) is a popular application in Bioinformatics which calculates the best score/alignment between two genomic sequences. Even though SW provides the best result, it is not widely used in genome projects due to huge requirements in computing power and memory space. Recently, Cloud Computing has been receiving a lot of attention since it is able to provide utility computing in an elastic environment. The advantages of Cloud Computing can be obtained at zero cost since many of the Public Clouds provide free usage slots, allowing users to run their applications for free in Cloud environments. Also, many Clouds can be put together and seen as a unique environment, creating Federated Clouds. In this paper, we propose and evaluate an approach to implement the SW algorithm in Federated Clouds. A hierarchical Multi-Cloud architecture is proposed which is able to transparently connect and manage several Clouds. The results obtained with our architecture and our MapReduce SW implementation in five Public Clouds show that, only by using the free quota, we were able to run the SW application over a huge genomic database in time that is comparable with the one obtained in multicore clusters, showing the appropriateness of our approach.

Broadcasting is a fundamental task, being used for neighboring discovery in various medium access control and routing protocols. This paper presents a comparative analysis of various broadcast techniques and topology control mechanisms. Overall, nine topology control mechanisms and seven broadcast protocols are combined, generating sixty-three possible solutions. Among the broadcast algorithms studied, two are proposed in this paper: the Record Route Elimination (RRE) and Record Route Elimination with Distance Prediction (RRE-DP). The simulation results show that the RRE and RRE-DP allow for a significant reduction in energy consumption, regardless of the topology control mechanism associated.

Finding a biologically relevant sequence alignment may be difficult since several sequence alignments are possible, taking different parameters in consideration. A perceptron neuron can be used to associate weights to a set of alignment characteristics and to decide if two residues should be aligned. Finding a good set of weights can be a hard problem and simulated annealing can be used for this purpose but it can take a long time. In this paper, we propose a parallelization strategy for simulated annealing optimizing a Fragment Based Alignment in Linear Space (FBALS). The results were superior to the competing algorithm and the obtained speedups were compatible with the number of processing cores, indicating a good parallel strategy.

Sequence alignment is a very important problem in Bioinformatics since it is very useful to discover relationships among biological sequences. In this article we propose a new sequence alignment algorithm that is able to identify sequence similarities in linear space. Our solution is capable of using several parameters specifying in which conditions a given residue can be aligned. This decision is taken based on a perceptron neuron and the best set of parameters is found using simulated annealing. Comparing our algorithm to a well established algorithm, we found that for pairwise alignments, our approach was faster for all instances tested with speedups up to 7.63 and yields better quality results for the majority of the instances.

In this paper, we propose and evaluate a framework for fault tolerant work?ow execution in grid environments that dynamically chooses an appropriate fault tolerance technique with a user-defined rule-based system. In this first version, binary trees are used. We also provide a generic interface that can be used to add fault tolerance techniques to the framework. A prototype of our framework was implemented in Java using Integrade as the grid middleware. By now, the fault tolerance techniques Retry and Replication are implemented. The results obtained with 3 real work?ows in an experimental grid environment show that the overhead introduced by our framework in a failure-free execution is small. Moreover, we show that, using our framework, work?ows are able to execute successfully in the presence of failures and that the framework can dynamically choose an appropriate fault tolerance technique.

Cross-species chromosome alignments can reveal ancestral relationships and may be used to identify the peculiarities of the species. It is thus an important problem in Bioinformatics. So far, aligning huge sequences, such as whole chromosomes, with exact methods has been regarded as unfeasible, due to huge computing and memory requirements. However, high performance computing platforms such as GPUs are being able to change this scenario, making it possible to obtain the exact result for huge sequences in reasonable time. In this paper, we propose and evaluate a parallel algorithm that uses GPU to align huge sequences, executing the Smith-Waterman algorithm combined with Myers-Miller, with linear space complexity. In order to achieve that, we propose optimizations that are able to reduce significantly the amount of data processed and that enforce full parallelism most of the time. Using the GTX 285 Board, our algorithm was able to produce the optimal alignment between sequences composed of 33 Millions of Base Pairs (MBP) and 47 MBP in 18.5 hours.

The opportunistic computing paradigm is extremely valuable to modern technical and scientific endeavors, as it can support the demand for large and steady amounts of computing capacity. The applications of opportunistic computing environments often require independent and intensive processing over different data sets, characterizing themselves as BoT applications. Opportunistic computing systems, however, usually employ centralized approaches to do task allocation, a problematic situation on sizable settings. This paper proposes and evaluates a peer-to-peer technique that allows the self-scheduling of tasks without any central controller whatsoever, aiming at opportunistic computing scenarios running BoT applications. Its key is to employ range query capabilities of search overlays like Skip Graphs as an infrastructure for fully distributed allocation decisions. Experimental results obtained in a message-passing simulator consisting of 5,000 nodes and 75,000 tasks show that central points of failure were eliminated and communication bottlenecks were highly alleviated, subject to some congestion characteristics of the search overlay.

Pairwise Sequence Alignment is a basic operation in Bioinformatics that is performed thousands of times, in a daily basis. The exact methods proposed in the literature have quadratic time complexity. For this reason, heuristic methods such as BLAST are widely used. Nevertheless, it is known that exact methods present better sensitivity, leading to better results. To obtain exact results faster, many parallel strategies have been proposed but most of them fail to align huge biological sequences. This happens because not only the quadratic time must be considered but also the space should be reduced. In this paper, we evaluate the performance and sensibility of z-align, a parallel exact strategy that runs in user-restricted memory space. The results obtained in a 64-processor cluster show that two sequences of size 23MBP (Mega Base Pairs) and 24MBP, respectively, were successfully aligned with z-align. Also, in order to align two 3MBP sequences, a speedup of 34.35 was achieved. Finally, when comparing z-align with BLAST, we can see that the z-align alignments are longer and have a higher score.

In order to make shared memory programming possible in distributed architectures, we use an abstraction called distributed shared memory. The behavior of distributed shared memory systems is dictated by the memory consistency model. In order to provide a better understanding on the semantics of the memory consistency models, many researchers have proposed formalisms to define them. Even with formal definitions, it is still difficult to say what kind of execution histories can be produced on a particular memory model. In this paper, we propose a tool that shows what operations orderings could lead to user-defined execution histories on different memory models. We also present a prototype of our tool that analyses execution histories for four different memory consistency models: sequential consistency, PipelinedRAM consistency, release consistency and scope consistency.

In this article, we address two important issues in DSM research: improving performance and providing reliability. To improve performance, we designed a low-overhead multiple coherence protocol mechanism and to augment the reliability of the system, we propose a coordinated checkpointing/recovery mechanism. Both mechanisms were implemented and incorporated in JIAJIA, a DSM system that implements scope consistency with a write-invalidate protocol. Our results on an eight machine cluster with some popular benchmarks show, for the multiple coherence protocol strategy, a significant reduction on the number of messages exchanged, leading to better performance results. Also, our results for the checkpointing strategy show that the overhead introduced in failure-free executions is small when considering the benefits obtained.

Distributed shared memory systems allow the use of the shared memory programming paradigm in distributed architectures where no physically shared memory exist. To reduce coherence overhead, relaxed memory consistency models were proposed. Scope consistent software DSMs provide a relaxed memory model that guarantees consistency only at synchronization operations, on a per-lock basis. Much of the work in DSM systems is validated by benchmarks and there are only a few examples of real parallel applications running on DSM systems. Binary space partition trees are widely used in computer graphics and pattern recognition to accelerate hidden surface removal. Depending on the size of the scene, the computational cost of generating BSP trees can be very high. We propose and evaluate a parallel algorithm that distributes the task of calculating BSP sub-trees among several nodes. This algorithm was implemented in JIAJIA, a scope consistent software DSM system. Our results on an eight-machine cluster presented very good speedups, showing that our parallelization strategy and programming support were appropriate.