This demonstration addresses a key open challenge in Open Radio Access Network (O-RAN) deployments: how to intelligently allocate Transport Network (TN) resources to ensure low-latency for mission-critical applications. The demo emulates a Smart Factory scenario where the time-sensitive control traffic of robotic arms competes with industrial camera broadband video streams. We propose an intelligent transport controller that combines network slicing, Adaptive Neuro-Fuzzy Inference System (ANFIS), and Federated Learning (FL) to dynamically prioritize traffic per slice. The architecture uses $\mathbf{P 4}$ switches for local queue monitoring and real-time resource scheduling. The integration with the O-RAN disaggregated stack is based on Open Air Interface (OAI). Experimental results demonstrate valuable load balancing and buffer occupation reduction in the O-RAN midhaul.

Multiple Sequence Alignment (MSA) is an important operation in Bioinformatics, used to simultaneously compare 3 or more sequences. The MSA problem was proven NP-Hard, so strategies have been proposed to reduce the search space and solve it in parallel. Recently, asymmetric multicore processors (AMPs) have become popular, with performance and energy-efficient cores, like the P-Cores and E-cores from Intel. However, parallel MSA applications have complex access patterns and adapting them for AMPs can be challenging. In this paper, we propose PA-Star21, an asymmetric-aware strategy based on A-Star, which computes optimal MSAs taking asymmetry into account when distributing the search space among threads. Our experimental results show that the proposed optimizations can reduce considerably the average execution time of PA-Star2 achieving a speedup of up to 7.70×. We also show that the asymmetric-aware strategy can reduce the average execution time for one of the hardest sequences set from the BAliBASE benchmark, when compared to the symmetric counterpart. Finally, we show that our approach is energy-efficient.11PA-Star2 is open source and the code is publicly available at1PA-Star2 is open source and the code is publicly available at https://github.com/danielsundfeld/astar_msa

Summary The Hirschberg algorithm is commonly used for protein sequence alignment, which is a very important task in bioinformatics. This article presents the AFMC framework for using the Hirschberg method to perform sequence alignment in multiple cloud computing services of different models, such as Infrastructure‐as‐a‐Service and Function‐as‐a‐Service (FaaS). Experiments were carried out in which several instances of AWS EC2, Azure VMs and Google Compute Engine as well as varied configurations of AWS Lambda, Azure Function, and Google Cloud Function were used to pairwise align COVID‐19 spike proteins. The services were submitted to different levels of simultaneity to align the genetic sequences. The findings reveal that there is a tradeoff between predicted execution time and cost for this application, for example, FaaS‐oriented cloud service models generally took less time to process the workloads. On the other hand, it was observed that, as the level of concurrence increased, there was a marked augmentation in cost. In this context, a framework that provides multi cloud solutions for bioinformatics such as AFMC is essential.

Summary Cloud computing is currently one of the prime choices in the computing infrastructure landscape. In addition to advantages such as the pay‐per‐use bill model and resource elasticity, there are technical benefits regarding heterogeneity and large‐scale configuration. Alongside the classical need for performance, for example, time, space, and energy, there is an interest in the financial cost that might come from budget constraints. Based on scalability considerations and the pricing model of traditional public clouds, a reasonable optimization strategy output could be the most suitable configuration of virtual machines to run a specific workload. From the perspective of runtime and monetary cost optimizations, we provide the adaptation of a Hadoop applications execution cost model extracted from the literature aiming at Spark applications modeled with the MapReduce paradigm. We evaluate our optimizer model executing an improved version of the Diff Sequences Spark application to perform SARS‐CoV‐2 coronavirus pairwise sequence comparisons using the AWS EC2's virtual machine instances. The experimental results with our model outperformed 80% of the random resource selection scenarios. By only employing spot worker nodes exposed to revocation scenarios rather than on‐demand workers, we obtained an average monetary cost reduction of 35.66% with a slight runtime increase of 3.36%.

The price of virtual machine instances in the Amazon EC2 spot model is often much lower than in the on-demand counterpart. However, this price reduction comes with a decrease in the availability guarantees. Several mechanisms have been proposed to analyze the spot model in the last years, employing different strategies. To our knowledge, there is no work that accurately captures the trade-off between spot price and availability, for short term analysis, and does long term analysis for spot price tendencies, in favor of user decision making. In this work, we propose (a) a utility-based strategy, that balances cost and availability of spot instances and is targeted to short-term analysis, and (b) a LSTM (Long Short Term Memory) neural network framework for long term spot price tendency analysis. Our experiments show that, for r4.2xlarge, 90 percent of spot bid suggestions ensured at least 5.73 hours of availability in the second quarter of 2020, with a bid price of approximately 38 percent of the on-demand price. The LSTM experiments were able to predict spot prices tendencies for several instance types with very low error. Our LSTM framework predicted an average value of 0.19 USD/hour for the r5.2xlarge instance type (Mean Squared Error$<10^{-6}$) for a 7-day period of time, which is about 37 percent of the on-demand price. Finally, we used our combined mechanism on an application that compares thousands of SARS-CoV-2 DNA sequences and show that our approach is able to provide good choices of instances, with low bids and very good availability.

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.

Summary This article presents a high‐level synthesis implementation of the longest common subsequence (LCS) algorithm combined with a weighted‐based scheduler for comparing biological sequences prioritizing energy consumption or execution time. The LCS algorithm has been thoroughly tailored using Vivado High‐Level Synthesis tool, which is able to synthesize register transfer level (RTL) from high‐level language descriptions, such as C/C++. Performance and energy consumption results were obtained with a CPU Intel Core i7‐3770 CPU and an Alpha‐Data ADM‐PCIE‐KU3 board that has a Xilinx Kintex UltraScale XCKU060 FPGA chip. We executed a batch of 20 comparisons of sequences on 10k, 20k, and 50k sizes. Our experiments showed that the energy consumption on the combined approach was significantly lower when compared to the CPU, achieving 75% energy reduction on 50k comparisons. We also used the tool proposed in this article to do a case study on Covid‐19, with real SARS‐CoV‐2 sequences, comparing their LCS scores.

The parallelization of Smith-Waterman (SW) sequence comparison tools for long DNA sequences has been a big challenge over the years, requesting the use of several devices and sophisticated optimizations. Pruning is one of these optimizations, which can reduce considerably the amount of computation. This article proposes MultiBP, a sequence comparison solution in multiple GPUs with block pruning. Two MultiBP strategies are proposed. In static score-sharing, workload is statically distributed to the GPUs, and the best score is sent to neighbor GPUs to simulate a global view. In the dynamic strategy, execution is divided into cycles and workload is dynamically assigned, according to the GPUs processing rate. MultiBP was integrated to MASA-CUDAlign and tested in homogeneous and heterogeneous platforms, with different NVidia GPU architectures. The best results in our homogeneous and heterogeneous platforms were mostly obtained by the static and dynamic approaches, respectively. We also show that our decision module is able to select the best strategy in most cases. Finally, the comparison of the human and chimpanzee chromosomes 1 in a cluster with 512 V100 NVidia GPUs took 11 minutes and obtained the impressive rate of 82,822 GCUPS (Billions of Cells Updated per Second) which is, to our knowledge, the best performance for SW tools in GPUs.

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.

Sequence comparison tools based on the Smith-Waterman (SW) algorithm provide the optimal result but have high execution times when the sequences compared are long, since a huge dynamic programming (DP) matrix is computed. Block pruning is an optimization that does not compute some parts of the DP matrix and can reduce considerably the execution time when the sequences compared are similar. However, block pruning's resulting task graph is dynamic and irregular. Since different pruning scenarios lead to different pruning shapes, we advocate that no single scheduling policy will behave the best for all scenarios. This paper proposes MASA-StarPU, a sequence aligner that integrates the domain specific framework MASA to the generic programming environment StarPU, creating a tool which has the benefits of StarPU (i.e., multiple task scheduling policies) and MASA (i.e., fast sequence alignment). MASA-StarPU was executed in two different multicore platforms and the results show that a bad choice of the scheduling policy may have a great impact on the performance. For instance, using 24 cores, the 5M × 5M comparison took 1484s with the dmdas policy whereas the same comparison took 3601s with lws. We also show that no scheduling policy behaves the best for all scenarios.

Parameter sensitivity analysis (SA) is an effective tool to gain knowledge about complex analysis applications and assess the variability in their analysis results. However, it is an expensive process as it requires the execution of the target application multiple times with a large number of different input parameter values. In this work, we propose optimizations to reduce the overall computation cost of SA in the context of analysis applications that segment high-resolution slide tissue images, ie, images with resolutions of 100k × 100k pixels. Two cost-cutting techniques are combined to efficiently execute SA: use of distributed hybrid systems for parallel execution and computation reuse at multiple levels of an analysis pipeline to reduce the amount of computation. These techniques were evaluated using a cancer image analysis workflow on a hybrid cluster with 256 nodes, each with an Intel Phi and a dual socket CPU. Our parallel execution method attained an efficiency of over 90% on 256 nodes. The hybrid execution on the CPU and Intel Phi improved the performance by 2×. Multilevel computation reuse led to performance gains of over 2.9×.

Summary Structural alignments of Ribonucleic acid (RNA) sequences solved by the Sankoff algorithm are computationally expensive and often require constraints to be used in practice. Modern Graphics Processing Units (GPUs) contain more than 1000 cores, which compute in parallel to speed up applications. Here, we present a GPU‐based solution to the RNA structural alignment problem that makes use of precalculated base pair probabilities on the individual sequences. We designed and developed an unconstrained version of the Sankoff algorithm, obtaining the optimal result and calculating the entire four‐dimension dynamic programming matrix (4D DP). Our approach uses a two‐level wavefront strategy to exploit parallelism. The 4D DP matrix is divided in one external matrix (EM) and several internal matrices (IM). We applied wavefront strategies on the EM and IMs in a two‐level hierarchical way. At the first level, the wavefront is applied to the EM, calculating the cells that belong to the same diagonal in parallel. In the second level, since each cell in the EM is itself an IM matrix, the cells that belong to the same IM diagonal are calculated in parallel. The results obtained with real RNA sequences show that our GPU version is capable of outperforming a multicore CPU version of the unconstrained version of the Sankoff algorithm. Compared with the CPU‐based version running on 32 cores, our approach is able to achieve a speedup of 7.81x on the NVidia Tesla P100. In this case, the execution time was reduced from 6 hours and 18 minutes (32 cores) to 48 minutes and 20 seconds (GPU).

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.

Summary Biological sequence comparison is often used as an auxiliary task in the analysis of genetic material. Pairwise comparison algorithms like Smith‐Waterman evaluate two strings representing sequences of proteins, DNA or RNA to obtain optimal alignment between them. Many applications have been proposed to address the sequence comparison problem, prioritizing the use of graphics cards and proprietary languages such as CUDA. In this paper, we propose and evaluate MASA‐OpenCL, an OpenCL solution for comparing long DNA sequences that is based on the MASA sequence alignment framework, with pruning capability proportional to the similarity of the sequences compared. The results of MASA‐OpenCL were compared to its CUDA counterpart (MASA‐CUDAlign) and, in most cases, MASA‐OpenCL achieved better performance. In order to better understand the behavior of MASA‐OpenCL, we performed a statistical analysis considering 11 comparisons of sequences with high, medium and low similarity in 4 GPUs. As a result, we obtained a multiple linear regression model that considers (a) the sizes of the sequences, (b) the similarity between them, (c) the computational power of the GPU, and (d) the GPU memory bandwidth. We used this model to predict the performance in two other GPUs, with low error rates.

Summary In this paper, we conduct statistical analyses for two Amazon cloud pricing models: on demand and spot. On demand cloud instances are charged a fixed price and can only be terminated by the user, with very high availability. On the other hand, spot instances are charged a dynamic price determined by a market‐driven model and can be revoked by the provider when the spot price becomes higher than the user‐defined price, having possibly low availability. Our analysis for on‐demand instances resulted in multiple linear regression equations that represent the influence of characteristics of the processor and RAM memory in the composition of the price of different types of instances available on the Amazon EC2 provider. In order to analyze the Amazon spot pricing, we used time‐smoothed moving averages by 12‐hour periods, aiming to provide a price‐availability trade‐off to the user. Our experiments with spot price histories from September to November 2016 show that the user's bid can be set at 30% of the on‐demand price, with an availability above of 90%, depending on instance type.

BACKGROUND: We present a performance per watt analysis of CUDAlign 4.0, a parallel strategy to obtain the optimal pairwise alignment of huge DNA sequences in multi-GPU platforms using the exact Smith-Waterman method. RESULTS: Our study includes acceleration factors, performance, scalability, power efficiency and energy costs. We also quantify the influence of the contents of the compared sequences, identify potential scenarios for energy savings on speculative executions, and calculate performance and energy usage differences among distinct GPU generations and models. For a sequence alignment on chromosome-wide scale (around 2 Petacells), we are able to reduce execution times from 9.5 h on a Kepler GPU to just 2.5 h on a Pascal counterpart, with energy costs cut by 60%. CONCLUSIONS: We find GPUs to be an order of magnitude ahead in performance per watt compared to Xeon Phis. Finally, versus typical low-power devices like FPGAs, GPUs keep similar GFLOPS/w ratios in 2017 on a five times faster execution.

This is a pre-copyedited, author-produced version of an article accepted for publication in The Computer Journal following peer review. The version of record Edans F O Sandes, George L M Teodoro, Maria Emilia M T Walter, Xavier Martorell, Eduard Ayguade, Alba C M A Melo; Formalization of Block Pruning: Reducing the Number of Cells Computed in Exact Biological Sequence Comparison Algorithms, The Computer Journal, Volume 61, Issue 5, 1 May 2018, Pages 687–713 is available online at: The Computer Journal https://academic.oup.com/comjnl/article-abstract/61/5/687/4539903 and https://doi.org/10.1093/comjnl/bxx090.

The Irregular Wavefront Propagation Pattern (IWPP) is a core computing structure in several image analysis operations. Efficient implementation of IWPP on the Intel Xeon Phi is difficult because of the irregular data access and computation characteristics. The traditional IWPP algorithm relies on atomic instructions, which are not available in the SIMD set of the Intel Phi. To overcome this limitation, we have proposed a new IWPP algorithm that can take advantage of non-atomic SIMD instructions supported on the Intel Xeon Phi. We have also developed and evaluated methods to use CPU and Intel Phi cooperatively for parallel execution of the IWPP algorithms. Our new cooperative IWPP version is also able to handle large out-of-core images that would not fit into the memory of the accelerator. The new IWPP algorithm is used to implement the Morphological Reconstruction and Fill Holes operations, which are operations commonly found in image analysis applications. The vectorization implemented with the new IWPP has attained improvements of up to about 5× on top of the original IWPP and significant gains as compared to state-of-the-art the CPU and GPU versions. The new version running on an Intel Phi is 6.21× and 3.14× faster than running on a 16-core CPU and on a GPU, respectively. Finally, the cooperative execution using two Intel Phi devices and a multi-core CPU has reached performance gains of 2.14× as compared to the execution using a single Intel Xeon Phi.

We investigate efficient sensitivity analysis (SA) of algorithms that segment and classify image features in a large dataset of high-resolution images. Algorithm SA is the process of evaluating variations of methods and parameter values to quantify differences in the output. A SA can be very compute demanding because it requires re-processing the input dataset several times with different parameters to assess variations in output. In this work, we introduce strategies to efficiently speed up SA via runtime optimizations targeting distributed hybrid systems and reuse of computations from runs with different parameters. We evaluate our approach using a cancer image analysis workflow on a hybrid cluster with 256 nodes, each with an Intel Phi and a dual socket CPU. The SA attained a parallel efficiency of over 90% on 256 nodes. The cooperative execution using the CPUs and the Phi available in each node with smart task assignment strategies resulted in an additional speedup of about 2×. Finally, multi-level computation reuse lead to an additional speedup of up to 2.46× on the parallel version. The level of performance attained with the proposed optimizations will allow the use of SA in large-scale studies.

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.

Motivation: Sensitivity analysis and parameter tuning are important processes in large-scale image analysis. They are very costly because the image analysis workflows are required to be executed several times to systematically correlate output variations with parameter changes or to tune parameters. An integrated solution with minimum user interaction that uses effective methodologies and high performance computing is required to scale these studies to large imaging datasets and expensive analysis workflows. Results: The experiments with two segmentation workflows show that the proposed approach can (i) quickly identify and prune parameters that are non-influential; (ii) search a small fraction (about 100 points) of the parameter search space with billions to trillions of points and improve the quality of segmentation results (Dice and Jaccard metrics) by as much as 1.42× compared to the results from the default parameters; (iii) attain good scalability on a high performance cluster with several effective optimizations. Conclusions: Our work demonstrates the feasibility of performing sensitivity analyses, parameter studies and auto-tuning with large datasets. The proposed framework can enable the quantification of error estimations and output variations in image segmentation pipelines. Availability and Implementation: Source code: https://github.com/SBU-BMI/region-templates/ . Contact: [email protected]. Supplementary information: Supplementary data are available at Bioinformatics online.

MOTIVATION: Structured RNAs can be hard to search for as they often are not well conserved in their primary structure and are local in their genomic or transcriptomic context. Thus, the need for tools which in particular can make local structural alignments of RNAs is only increasing. RESULTS: To meet the demand for both large-scale screens and hands on analysis through web servers, we present a new multithreaded version of Foldalign. We substantially improve execution time while maintaining all previous functionalities, including carrying out local structural alignments of sequences with low similarity. Furthermore, the improvements allow for comparing longer RNAs and increasing the sequence length. For example, lengths in the range 2000-6000 nucleotides improve execution up to a factor of five. AVAILABILITY AND IMPLEMENTATION: The Foldalign software and the web server are available at http://rth.dk/resources/foldalign CONTACT: [email protected] SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

Summary Cloud computing has evolved to provide computing resources on‐demand through a virtualized infrastructure, letting applications, computing power, data storage, and network resources to be provisioned and managed over private networks or over the Internet. Cloud services normally run on large data centers and demand a huge amount of electricity. Consequently, the electricity cost represents one of the major concerns of data centers, because it is sometimes nonlinear with the capacity of the data centers, and it is also associated with a high amount of carbon emission (CO2). However, energy‐saving schemes that result in too much degradation of the system performance or in violations of service‐level agreement (SLA) parameters would eventually cause the users to move to another cloud provider. Thus, there is a need to reach a balance between energy savings and the costs incurred by these savings in the execution of the applications. Therefore, in this paper, we propose and evaluate a power and SLA‐aware application consolidation solution for cloud federations. It comprises a multi‐agent system for server consolidation, taking into account SLA, power consumption, and carbon footprint. Different for similar solutions available in the literature, in our solution, when a cloud is overloaded, its data center needs to negotiate with other data centers before migrating the workload to another cloud. Simulation results show that our approach can reduce up to 46% of the power consumption while trying to meet performance requirements. Furthermore, we show that federated clouds can provide an adequate solution to deal with power consumption in the clouds. Copyright © 2016 John Wiley & Sons, Ltd.

This paper proposes and evaluates CUDAlign 4.0, a parallel strategy to obtain the optimal alignment of huge DNA sequences in multi-GPU platforms, using the exact Smith–Waterman (SW) algorithm. In the first phase of CUDAlign 4.0, a huge Dynamic Programming (DP) matrix is computed by multiple GPUs, which asynchronously communicate border elements to the right neighbor in order to find the optimal score. After that, the traceback phase of SW is executed. The efficient parallelization of the traceback phase is very challenging because of the high amount of data dependency, which particularly impacts the performance and limits the application scalability. In order to obtain a multi-GPU highly parallel traceback phase, we propose and evaluate a new parallel traceback algorithm called Incremental Speculative Traceback (IST), which pipelines the traceback phase, speculating incrementally over the values calculated so far, producing results in advance. With CUDAlign 4.0, we were able to calculate SW matrices with up to 60 Peta cells, obtaining the optimal local alignments of all Human and Chimpanzee homologous chromosomes, whose sizes range from 26 Millions of Base Pairs (MBP) up to 249 MBP. As far as we know, this is the first time such comparison was made with the SW exact method. We also show that the IST algorithm is able to reduce the traceback time from 2.15$\times$up to 21.03$\times$, when compared with the baseline traceback algorithm. The human$\times$chimpanzee chromosome 5 comparison (180 MBP$\times$183 MBP) attained 10,370.00 GCUPS (Billions of Cells Updated per Second) using 384 GPUs, with a speculation hit ratio of 98.2 percent.

Nowadays, cloud users face three important problems: (a) choosing one or more appropriate cloud provider(s) to run their application(s), (b) selecting appropriate cloud resources, which implies having enough information about the available resources, including their characteristics and constraints, and (c) configuring the cloud resources. These problems are mostly due to the wide range of resources. These resources usually have distinct dependencies, and they are offered at various clouds' layers. In this complex scenario, the users often have to handle cloud resources and their dependencies manually. This is an error-prone and time-consuming activity, even for skilled cloud users and system administrators. In this context, this paper proposes a software product line engineering (SPLE) method and a tool to deal with these issues. Our SPL-based engineering method enables a declarative and goal-oriented strategy. Furthermore, it allows resource selection and configuration in inter-cloud environments. In our proposal, the cloud users specify their applications and requirements, and our tool automatically selects and configures a suitable computing environment, taking into account temporal and functional dependencies. Experimental results on Amazon EC2 and Google Compute Engine (GCE) show that our approach enables unskilled users to have access to advanced inter-cloud computing configurations, without being concerned with the characteristics of each cloud.

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.

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.

We investigate the execution of the Irregular Wave front Propagation Pattern (IWPP), a fundamental computing structure used in several image analysis operations, on the Intel® Xeon PhiTM co-processor. An efficient implementation of IWPP on the Xeon Phi is a challenging problem because of IWPP's irregularity and the use of atomic instructions in the original IWPP algorithm to resolve race conditions. On the Xeon Phi, the use of SIMD and vectorization instructions is critical to attain high performance. However, SIMD atomic instructions are not supported. Therefore, we propose a new IWPP algorithm that can take advantage of the supported SIMD instruction set. We also evaluate an alternate storage container (priority queue) to track active elements in the wave front in an effort to improve the parallel algorithm efficiency. The new IWPP algorithm is evaluated with Morphological Reconstruction and Imfill operations as use cases. Our results show performance improvements of up to 5.63× on top of the original IWPP due to vectorization. Moreover, the new IWPP achieves speedups of 45.7× and 1.62×, respectively, as compared to efficient CPU and GPU implementations.

This paper proposes and evaluates a parallel strategy to execute the exact Smith-Waterman (SW) biological sequence comparison algorithm for huge DNA sequences in multi-GPU platforms. In our strategy, the computation of a single huge SW matrix is spread over multiple GPUs, which communicate border elements to the neighbour, using a circular buffer mechanism. We also provide a method to predict the execution time and speedup of a comparison, given the number of the GPUs and the sizes of the sequences. The results obtained with a large multi-GPU environment show that our solution is scalable when varying the sizes of the sequences and/or the number of GPUs and that our prediction method is accurate. With our proposal, we were able to compare the largest human chromosome with its homologous chimpanzee chromosome (249 Millions of Base Pairs (MBP) x 228 MBP) using 64 GPUs, achieving 1.7 TCUPS (Tera Cells Updated per Second). As far as we know, this is the largest comparison ever done using the Smith-Waterman algorithm.

This paper proposes and evaluates a parallel strategy to execute the exact Smith-Waterman (SW) algorithm for megabase DNA sequences in heterogeneous multi-GPU platforms. In our strategy, the computation of a single huge SW matrix is spread over multiple GPUs, which communicate border elements to the neighbour, using a circular buffer mechanism that hides the communication overhead. We compared 4 pairs of human-chimpanzee homologous chromosomes using 2 different GPU environments, obtaining a performance of up to 140.36 GCUPS (Billion of cells processed per second) with 3 heterogeneous GPUS.

Online social networks (OSNs) offer people the opportunity to join communities where they share a common interest or objective. This kind of community is useful for studying the human behavior, diffusion of information, and dynamics of groups. As the members of a community are always changing, an efficient solution is needed to query information in real time. This paper introduces the Follow Model to present the basic relationship between users in OSNs, and combines it with the MapReduce solution to develop new algorithms with parallel paradigms for querying. Two models for reverse relation and high-order relation of the users were implemented in the Hadoop system. Based on 75 GB message data and 26 GB relation network data from Twitter, a case study was realized using two dynamic discussion communities: #musicmonday and #beatcancer. The querying performance demonstrates that the new solution with the implementation in Hadoop significantly improves the ability to find useful information from OSNs.

In Genome Projects, biological sequences are aligned thousands of times, in a daily basis. The Smith-Waterman algorithm is able to retrieve the optimal local alignment with quadratic time and space complexity. So far, aligning huge sequences, such as whole chromosomes, with the Smith-Waterman algorithm has been regarded as unfeasible, due to huge computing and memory requirements. However, high-performance computing platforms such as GPUs are making it possible to obtain the optimal result for huge sequences in reasonable time. In this paper, we propose and evaluate CUDAlign 2.1, 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 which are able to reduce significantly the amount of data processed, while enforcing full parallelism most of the time. Using the NVIDIA GTX 560 Ti board and comparing real DNA sequences that range from 162 KBP (Thousand Base Pairs) to 59 MBP (Million Base Pairs), we show that CUDAlign 2.1 is scalable. Also, we show that CUDAlign 2.1 is able to produce the optimal alignment between the chimpanzee chromosome 22 (33 MBP) and the human chromosome 21 (47 MBP) in 8.4 hours and the optimal alignment between the chimpanzee chromosome Y (24 MBP) and the human chromosome Y (59 MBP) in 13.1 hours.

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.

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.

As new protein sequences are discovered on an everyday basis and protein databases continue to grow exponentially with time, computational tools take more and more time to search protein databases to discover the common ancestors of them. HMMER is among the most used tools in protein search and comparison and multiple efforts have been made to accelerate its execution by using dedicated hardware prototyped on FPGAs. In this paper we introduce a novel algorithm called the Divergence Algorithm, which not only enables the FPGA accelerator to reduce execution time, but also enables further acceleration of the alignment generation algorithm of the HMMER programs by reducing the number of cells of the Dynamic Programming matrices it has to calculate. We also propose a more accurate performance measurement strategy that considers all the execution times while doing protein searches and alignments, while other works only consider hardware execution times and do not include alignment generation times. Using our proposed hardware accelerator and the Divergence Algorithm, we were able to achieve gains up to 182× when compared to the unaccelerated HMMER software running on a general purpose CPU.

Multiple sequence alignment (MSA) is an important problem in Bioinformatics since it is often used to identify evolutionary relationships and predict secondary/tertiary structure, among others. MSAs are usually scored with the Sum-of-Pairs (SP) function and the exact SP MSA is known to be NP-Hard. Therefore, heuristic methods are used to solve this problem. In this paper, we propose and evaluate a parallel island injection genetic algorithm to solve the MSA problem. Unlike the other strategies, our parallel solution uses two types of interconnected archipelagoes, each with distinct types of individuals. Our results with real protein data sets show that our strategy is able to obtain better results, when compared to the traditional island model. Also, we were able to reduce considerably the execution time, when compared to the sequential version.

Biological sequence comparison is a very important operation in Bioinformatics. Even though there do exist exact methods to compare biological sequences, these methods are often neglected due to their quadratic time and space complexity. In order to accelerate these methods, many GPU algorithms were proposed in the literature. Nevertheless, all of them restrict the size of the smallest sequence in such a way that Megabase genome comparison is prevented. In this paper, we propose and evaluate CUDAlign, a GPU algorithm that is able to compare Megabase biological sequences with an exact Smith-Waterman affine gap variant. CUDAlign was implemented in CUDA and tested in two GPU boards, separately. For real sequences whose size range from 1MBP (Megabase Pairs) to 47MBP, a close to uniform GCUPS (Giga Cells Updates per Second) was obtained, showing the potential scalability of our approach. Also, CUDAlign was able to compare the human chromosome 21 and the chimpanzee chromosome 22. This operation took 21 hours on GeForce GTX 280, resulting in a peak performance of 20.375 GCUPS. As far as we know, this is the first time such huge chromosomes are compared with an exact method.

The recent and astonishing accomplishments in the field of Genomics would not have been possible without the techniques, algorithms, and tools developed in Bioinformatics. Biological sequence comparison is an important operation in Bioinformatics because it is used to determine how similar two sequences are. As a result of this operation, one or more alignments are produced. DIALIGN is an exact algorithm that uses dynamic programming to obtain optimal biological sequence alignments in quadratic space and time. One effective way to accelerate DIALIGN is to design FPGA-based architectures to execute it. Nevertheless, the complete retrieval of an alignment in hardware requires modifications on the original algorithm because it executes in quadratic space. In this paper, we propose and evaluate two FPGA-based accelerators executing DIALIGN in linear space: one to obtain the optimal DIALIGN score (DIALIGN-Score) and one to retrieve the DIALIGN alignment (DIALIGN-Alignment). Because it appears to be no documented variant of the DIALIGN algorithm that produces alignments in linear space, we here propose a linear space variant of the DIALIGN algorithm and have designed the DIALIGN-Alignment accelerator to implement it. The experimental results show that impressive speedups can be obtained with both accelerators when comparing long biological sequences: the DIALIGN-Score accelerator achieved a speedup of 383.4 and the DIALIGN-Alignment accelerator reached a speedup of 141.38.

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.

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.

Biological Sequence Comparison is a very important operation in computational biology since it is used to relate organisms and understand evolutionary processes. This article presents the design and evaluation of an allocation framework for biological sequence comparison applications that use dynamic programming and run in heterogeneous environments. Its goal is to determine which processors will execute the application, considering some characteristics of the heterogeneous environment, such as observed processor power and network bandwidth. The results obtained with four different task allocation policies in a 10-machine heterogeneous environment show that, for some sequence sizes, we were able to reduce the execution time of the parallel application in more than a half, when the appropriate number of processors is used.

DNA sequence alignment is a very important problem in bioinformatics. The algorithm proposed by Smith-Waterman (SW) is an exact method that obtains optimal local alignments in quadratic space and time. For long sequences, quadratic complexity makes the use of this algorithm impractical. In this scenario, the use of a reconfigurable architecture is a very attractive alternative. This article presents the design and evaluation of an FPGA-based architecture that obtains the similarity score between DNA sequences, as well as its coordinates. The results obtained in a Xilinx xc2vp70 FPGA prototype presented a speedup of 246.9 over the software solution to compare sequences of size 100 MBP and 100 BP, respectively. Different from others hardware solutions that just calculate alignment scores, our design was able to avoid architecture's bottlenecks and accelerate the most computer intensive part of a sequence alignment software algorithm.

Grid computing is emerging as a new infrastructure to provide collaborative and secure resource sharing over multiple geographically distributed organizations. In this scenario, resource discovery is a very important component, since it is responsible to retrieve information about the resources that compose the grid. Traditionally, the kind of data to be retrieved by resource discovery mechanisms is statically defined. In a highly heterogeneous and dynamic environment such as a grid, statically defined searches are usually inappropriate. In this paper, we propose and evaluate an extensible resource discovery mechanism for grid systems, where the basic resource information retrieval can be extended to include userdefined specific resource searches. Our experimental results show that the proposed mechanism is able to incorporate new searches to our grid resource discovery service in reasonable time.

The algorithm proposed by Smith-Waterman is an exact method that obtains optimal local alignments in quadratic space and time. For long sequences, quadratic complexity makes the use of this algorithm impractical. In this scenario, parallel computing is a very attractive alternative. In this paper, we propose and evaluate z-align, a parallel exact strategy based on the divergence concept to locally align long biological sequences using an affine gap function. Z-align runs in limited memory space, where the amount of memory used can be defined by the user. The results collected in a cluster with 16 processors presented very good speedups for long real DNA sequences. By comparing the results obtained with z-align and BLAST, it is clear that z-align is able to produce longer and more significant alignments.

The evolution of DNA sequencing techniques generated huge sequence repositories and hence the need for efficient algorithms to compare them. To increase search speed, heuristic algorithms like BLAST were developed and are widely used. In order to further reduce BLAST execution time, this paper evaluates an adaptive task allocation framework to perform BLAST searches in a grid environment against segmented genetic databases segments. Our results present very good speedups and also show that no single task allocation strategy is able to achieve the lowest execution times for all scenarios. Also, our results show that the proposed adaptive strategy was able to deal with the heterogeneous and non-dedicated nature of a grid.

Sequence comparison is a basic operation in DNA sequencing projects, and most sequence comparison methods used are based on heuristics, that are faster but do not produce optimal alignments. Recently, many organisms have had their DNA entirely sequenced, and this reality presents the need for comparing long DNA sequences, which is a challenging task due to its high demands for computational power and memory. Although DSM is presented as a feasible parallel programming paradigm, much of the work in DSM is validated by benchmarks and there are only a few examples of real parallel applications running on DSM systems. In this article, we present and evaluate a parallelization strategy for implementing a local DNA sequence alignment algorithm. This strategy was implemented in JIAJIA, a scope consistent software DSM system. Our results on an eight-machine cluster presented very good speedups, which are comparable with the ones obtained with MPI, showing that our parallelization strategy and programming support were appropriate.

Summary form only given. Biological inspired techniques have proven to be efficient in solving a variety of real problems using parallel and distributed processing. In this paper, we wish to study the DNA sequencing problem known for its computational requirements which far exceed the computing capabilities of the fastest available sequential machines. Sequence comparison is a basic operation of the DNA sequencing problem, mainly due to the large number of DNA sequences. While most of the methods used are based on heuristic paradigms and have relatively a fast execution time, they do not produce optimal alignments sought by most biologists. Recently, many organisms had their DNA entirely sequenced, and this reality presents the need for comparing long DNA sequences, which is a challenging task due to its high demands for computational requirements (power and memory). In this paper, we present an efficient parallel strategy for implementing a sequence alignment algorithm for long sequences, and evaluate its performance using a cluster of workstations. This strategy was implemented in JIAJIA, a scope consistent software DSM system. Our results indicate clearly that our scheme is feasible, achieve a good speedup and can help in obtaining a better solution to the DNA sequencing problem when compared to previous schemes.