High Performance Computing (HPC) is increasingly transitioning to the cloud, although cost remains a significant barrier. While On-demand instances and Committed Use Discounts provide predictable pricing, the Spot market offers an appealing opportunity for substantial cost savings – though it does not guarantee resource availability. Effectively managing multiple instances for parallel HPC applications is essential. Services like AWS EC2 Fleet or Spot Fleet help with this, but they come with limitations, notably being constrained to a single region. Furthermore, simply selecting the lowest-priced instance often leads to suboptimal performance and, surprisingly, higher overall costs. To truly economize, a more sophisticated approach is required: one that involves profiling applications and instances to understand their intricate cost-performance trade-offs. The most cost-effective execution prioritizes instances that strike a better balance between the price per hour being charged and the actual performance they offer the application, even if its current Spot price is not the lowest available. This paper addresses these challenges by conducting a thorough analysis of existing EC2 (Spot) Fleet policies and introducing Fleet-MR, a novel multi-region instance selection framework. Fleet-MR aims to improve execution times or reduce costs, and its effectiveness is validated through experimental evaluations.

ABSTRACT This study proposes strategies to reduce the financial cost of using cloud clusters, through Amazon Web Services (AWS) ParallelCluster, to run the weather forecast model Brazilian developments on the Regional Atmospheric Modeling System (BRAMS). We developed an instance selection algorithm that obtains and compares the costs of various instance types in different regions and markets, recommending those with the lowest costs. If the suggested instance is a Spot instance and is revoked by the cloud provider, the proposed strategy resumes the application execution from a pre‐recorded checkpoint by rescheduling it on On‐Demand instances. This study also presents a detailed analysis of BRAMS execution across various instance architectures and proposes a novel three‐queue architecture for managing BRAMS execution on On‐Demand and Spot instances within AWS ParallelCluster. The results obtained from small and large spatial domains executed in AWS ParallelCluster using the proposed strategies show that adopting a cloud cluster is a promising alternative for this type of High‐Performance Computing application, compared with execution on a supercomputer.

This paper presents the framework SIM@ ClOUD that optimizes cost-related resource allocation decisions for simulation jobs in cloud environments. SIM@ CLOUD offers comprehensive management of simulations throughout their execution life-cycle in the cloud, including the selection of Virtual Machine (VM) types across different regions and markets. By leveraging Spot VMs and application checkpointing, the framework transparently reduces the monetary costs associated with the execution without client intervention. Historical data analysis enables the prediction of simulation execution times, which is refined further by a dynamic predictor for adaptive VM selection. SIM@ CLOUD is being deployed in an industrial setting and employs a cachebased storage solution to improve access latency to in-house data by VMs located in geographically distinct regions. An evaluation carried out on AWS EC2, using real oil reservoir simulations, demonstrates the effectiveness of the framework.

Federated Learning systems allow training machine learning models distributed across multiple clients, each one using private local data. Iteratively, the clients send their training contributions to a server, which performs a merge to produce an enhanced global model. Due to resource and data heterogeneity, client selection is crucial to optimize the system efficiency and improve the global model generalization. Selecting more clients is likely to increase the overall energy consumption, while a small number of clients may decline the performance of the trained model or require longer training time. We propose two time- and energy-aware client selection algorithms, MEC and ECMTC, which are proven regarding their optimality and evaluated against state-of-the-art algorithms on an extensive series of experiments in both simulation and HPC platform scenarios. The results indicate the benefits of jointly optimizing the time and energy consumption metrics using our proposals.

Summary Web scraping is a widely used technique for decision‐making, collecting, and structuring public data from the internet. As the volume of data continues to grow, the need for more efficient methods of data extraction becomes crucial. This article introduces a novel web scraping framework that utilizes Burstable virtual machines (VMs) on Amazon Web Services with the objective of reducing the monetary cost of execution while ensuring compliance with service level agreements (SLAs). To achieve this, the framework utilizes a combination of fixed and temporary Burstable VMs in a mixed cluster, which can be elastically scaled up to fulfill the SLA and scaled down to minimize monetary costs. Two strategies for handling VM allocation are proposed and evaluated: (i) a queue and SLA‐based strategy that employs queue size information and SLA criteria to determine the required number of VMs for the current scraping requests, and (ii) a credit‐based strategy that incorporates information about Burstable VM credits to effectively manage instance creation and termination. Experimental tests show that the proposed framework meets the defined SLA while achieving cost reductions of up to 74% compared to an approach that executes on fixed‐size clusters of Burstable instances.

Petroleum reservoir simulation uses computer models to predict fluid flow in porous media, aiding to forecast oil production. Engineers execute numerous simulations with different geological realizations to refine the accuracy of the model. These experiments require considerable computational resources, which are not always available within the on-premises infrastructure. Commercial public cloud platforms can offer many advantages, such as virtually unlimited scalability and pay-per-use pricing. This paper introduces MScheduler, a meta scheduler framework for reservoir simulations at Petrobras, a Brazilian energy company. It efficiently executes jobs in the cloud, utilizing spot Virtual Machines (VMs) to reduce costs and ensure job completion even with VM termination. Contributions include a novel methodology for reservoir simulation checkpointing, a cost-based scheduler, and an analysis of the strategy using real production jobs from Petrobras.

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%.

Cloud providers offer several types of Virtual Machines (VMs) in diverse markets, with different guarantees in terms of availability and reliability. Among them, the most popular market models are the on-demand and the spot. On-demand VMs are allocated for a fixed cost per time, and their availability is ensured during the whole execution. On the other hand, in the spot market, VMs are offered with a huge discount, but their availability fluctuates according to cloud’s current demand that can terminate or hibernate a spot VM at any time. Furthermore, to cope with workload variations, cloud providers have also introduced the concept of burstable VMs, which can burst up their CPU performance during a limited period of time. In this work, we present the Burst Hibernation-Aware Dynamic Scheduler (Burst-HADS), a framework that executes Bag-of-Tasks applications with deadline constraints by exploiting both spot and on-demand burstable VMs, aiming at minimizing both the monetary cost and the execution time. Performance results on Amazon EC2 show that Burst-HADS reduces the monetary cost and meets the application deadline even in spot hibernation scenarios, when compared to other approaches from the related literature which uses only spot and non-burstable on-demand instances.

Under the coordination of a central server, Federate Learning (FL) enables a set of clients to collaboratively train a global machine learning model without exchanging their local data. When such clients have powerful machines, it is called cross-silo FL, and they store their data in private repositories denoted silos. We are interested in this paper in cross-silo FL where silos are geographically located in different regions of multi-cloud providers. Thus, aiming at minimizing financial costs and execution times of a cross-silo FL application, we propose a model based on a scheduling problem mathematical formulation, which receives as input both the application parameters and the cloud providers' resource features where clients' data are stored and renders the best assignment of clients and server to virtual machines. This formulation is part of a framework proposal to execute FL applications in different cloud providers. Taking as a use case a Tumor-Infiltrating Lymphocytes Classification problem, an FL application whose clients' datasets spread over different cloud providers' data repositories, evaluation results show that our model is scalable and improves the execution time and financial costs of the FL application by up to 53.70% and 48.34% in a scenario with 50 clients, executing in around 200 seconds, when compared to results where VMs are randomly selected. Experimental results with client silos in different Google (GCP) and Amazon (AWS) cloud regions also confirmed the effectiveness of our proposed model in a real multi-cloud environment.

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.

Cloud platforms offer different types of virtual machines which ensure different guarantees in terms of availability and volatility, provisioning the same resource through multiple pricing models. For instance, in Amazon EC2 cloud, the user pays per hour for on-demand instances while spot instances are unused resources available for a lower price. Despite the monetary advantages, a spot instance can be terminated or hibernated by EC2 at any moment. Using both hibernationprone spot instances (for cost sake) and on-demand instances, we propose in this paper a static scheduling for applications which are composed of independent tasks (bag-of-task) with deadline constraints. However, if a spot instance hibernates and it does not resume within a time which guarantees the application's deadline, a temporal failure takes place. Our scheduling, thus, aims at minimizing monetary costs of bag-of-tasks applications in EC2 cloud, respecting its deadline and avoiding temporal failures. Performance results with task execution traces, configuration of Amazon EC2 virtual machines, and EC2 market history confirms the effectiveness of our scheduling and that it tolerates temporal failures.

Summary The increasing amount of resources available on current GPUs sparked new interest in the problem of sharing its resources by different kernels. While new generations of GPUs support concurrent kernel execution, their scheduling decisions are taken by the hardware at runtime. The hardware decisions, however, heavily depend on the order at which the kernels are submitted to execution. In this work, we propose a novel optimization approach to reorder the kernels invocation focusing on maximizing the resources utilization, improving the average turnaround time. We model the kernel assignments to the hardware resources as a series of knapsack problems and use a dynamic programming approach to solve them. We evaluate our method using kernels with different sizes and resource requirements. Our results show significant gains in the average turnaround time and system throughput compared to the kernels submission implemented in modern GPUs.

Summary The Pre‐stack Kirchhoff Time Migration (PKTM) is a central process in petroleum exploration. As PKTM is computationally intensive, many works have proposed the use of accelerators like GPU and FPGA to improve its execution time. On the other hand, although many off‐the‐shelf processors are endowed with a set of SIMD vector instructions, few papers tackle the problem considering vectorization and all of them consider that compilers can successfully vectorize the code. In this paper, we show that programming PKTM by using SIMD vector instructions manually is more efficient than the automatically and semi‐automatically vectorized codes, provided by a hardware specific compiler and library. Experiments considering both real and synthetic datasets showed that our solution is more than four times faster than the traditional code. It also outperformed automatically vectorized codes in all tests. We believe that the proposed strategy can be used together with the other ones to accelerate seismic migration methods in general without new investments in hardware. Copyright © 2016 John Wiley & Sons, Ltd.

The quadratic assignment problem (QAP) is a combinatorial optimization problem that arises in many real-world applications, such as equipment allocation in industry. The QAP is NP-hard and, in practice, one of the hardest combinatorial optimization problems to solve to optimality. Exact solutions of QAP are typically obtained by the branch-and-bound method. This method, however, potentially requires a high computational effort, and the use of good lower bounds is essential to prune the search tree. Branch-and-bound algorithms that use the dual-ascent procedure based on the level-2 reformulation linearization technique (RLT2) belong to the state of the art on exactly solving QAP. In this work, we propose a parallel implementation of that branch-and-bound algorithm. Our approach uses the Auction Algorithm of Bertsekas and Castañon to solve the linear assignment problems of RLT2, which allows us to take advantage of the massive parallel environment of graphics processing units to speed up the lower bound computation and implement some memory optimization techniques to address large-size problems. We report experimental results that show significant execution time reductions compared to previous works and allow us to provide, for the first time, exact solutions for two instances of QAP: tai35b and tai40b.

Abstract The latest trends in high performance computing systems show an increasing demand on the use of a large scale multicore system in an efficient way so that high compute‐intensive applications can be executed reasonably well. However, the exploitation of the degree of parallelism available at each multicore component can be limited by the poor utilization of the memory hierarchy. Actually, the multicore architecture introduces some distinct features that are already observed in shared memory and distributed environments. One example is that subsets of cores can share different subsets of memory. In order to achieve high performance, it is imperative that a careful allocation scheme of an application is carried out on the available cores, based on a scheduling specification that considers not only processors characteristics but also memory contention. This paper proposes a multicore cluster representation that captures relevant performance characteristics in multicores systems such as the influence of memory hierarchy and contention on application performance. Improved performance was achieved by a branch‐and‐bound application applied to the partitioning sets problem that incorporated a memory aware load balancing strategy based on the proposed multicore cluster representation. An in‐depth analysis on this application execution showed its applicability to modern systems. Copyright © 2014 John Wiley & Sons, Ltd.

Cloud computing establishes a new computing model where a wide range of computing resources are provided to several types of users. Especially for bioinformatics experiments modeled as scientific workflows, clouds provide several types of resources as virtual machines (VM), storage, databases and computing power that can be combined for empowering the scientific workflow execution. These workflows usually require high performance environments and parallelism techniques since their activities are data and computing intensive and can execute for a long time. There are then some Scientific Workflow Management Systems (SWfMS) that already manage the parallel execution of scientific workflows in clouds. Most of them instantiate a virtual cluster for the execution. However, they rely on the user to estimate the amount of VMs to be instantiated to create this virtual cluster. Estimating the amount of VMs to instantiate is then a crucial task to avoid negative impacts on the workflow performance with under or over estimations. This dimensioning also is not a trivial task in clouds due to the large number of VM types to choose in a cloud provider. Previously proposed approach named GraspCC already provides a near optimal estimation of the amount of VM for general applications, not scientific workflows. In this paper, we coupled the GraspCC to SciCumulus (Cloud-based Parallel Engine for Scientific Workflows) engine to estimate the necessary amount of VMs for bioinformatics workflows. We have evaluated GraspCC by comparing the estimative with real executions of a set of large-scale comparative genomics workflows. It showed the suitability of GraspCC to estimate the amount of VMs in real bioinformatics cloud workflows.

Parallel rendering algorithms usually suffer from high load imbalance during execution, due to the irregular nature of the datasets. In this paper, we propose a new load balancing scheme for tile-based parallel rendering that includes strategies for load estimation, tile decomposition and tile assignment. The load estimation strategy computes the rendering cost for each pixel, and uses it as a prediction for the next frame. The tile decomposition strategy adaptively divides the screen into tiles based on the computed costs, until an evenly tile partition is achieved. The tile assignment strategy distributes the tiles among rendering processors, based on a 2-optimal scheduling. Experimental results show that our scheme achieves significant performance gains by reducing the load imbalance when compared to the traditional tile subdivision and static random distribution schemes.

Abstract Multicast routing problems are often modeled as Steiner Problems in undirected or directed graphs, the latter case being particularly suitable to cases where most of the traffic has a single source. Sequential Steiner heuristics are not convenient in that context, because one cannot assume that a central node has complete information about the topology and the state of a large wide area network. This article introduces a distributed version of a Dual Ascent primal‐dual heuristic, known for its remarkably good practical results, lower and upper bounds, in both undirected and directed Steiner problems. Complexity analysis and experimental results are also presented, showing the efficiency of the proposed algorithm when compared with the best distributed algorithms in the literature. © 2008 Wiley Periodicals, Inc. NETWORKS, 2009

Data mining techniques are becoming increasingly more popular as a reasonable means to collect summaries from the rapidly growing datasets in many areas. However, as the size of the raw data increases, parallel data mining algorithms are becoming a necessity. In this paper, we present a run-time support system that was designed to allow the efficient implementation of data-mining algorithms on heterogeneous distributed environments. We believe that the runtime framework is suitable for a broader class of applications, beyond data mining. We also present a parallelization strategy that is supported by the run-time system. We show scalability results of three different data-mining algorithms that were parallelized using our approach and our run-time support. All applications scale almost linearly up to a large number of nodes.

This paper presents several strategies for parallel implementations of the greedy randomized adaptive search procedure (GRASP) and the variable neighborhood search (VNS) applied to a combinatorial optimization problem known as the traveling purchaser problem (TPP). Parallel algorithms based on master-worker, completely distributed and independent models, using static and dynamic load balance were proposed. The performance of these parallel algorithms was analyzed comparing them among themselves and with their sequential versions.