Search

In this paper, we developed a Spark application, named Diff Sequences Spark, which compares 540 SARS-CoV-2 sequences from South America in Amazon EC2 Cloud, generating as output the positions where the differences occur. We analyzed the performance of the proposed application on selected memory and storage optimized virtual machines (VMs) at on-demand and spot markets. The execution times and financial costs of the memory optimized VMs outperformed the storage optimized ones. Regarding the markets, Diff Sequences Spark reduced the average execution times and monetary costs when using spot VMs compared to their respective on-demand VMs, even in scenarios with several spot revocations, benefiting from the low overhead fault tolerance Spark framework.

O Apache Spark tem se mostrado um framework promissor para auxiliar na execução de experimentos científicos baseados em simulação e que demandam execuções em ambientes de alto desempenho. Entretanto, o Spark possui mais de 180 parâmetros para serem configurados, o que torna a tarefa de configuração entediante e propensa a erros, se realizada manualmente. O presente artigo explora a utilização de múltiplos métodos de aprendizado de máquina para auxiliar na configuração dos parâmetros do Spark. Tais modelos foram treinados na plataforma Orange e posteriormente incorporados a ferramenta SpaCE, desenvolvida em um trabalho anterior. Os modelos foram treinados a partir de um dataset com dados de proveniência de mais de 500 execuções de dataflows de astronomia. Os resultados mostraram que o uso de métodos de aprendizado de máquina nesse contexto é promissor. Além disso, os resultados mostraram que a estratégia de partição dos dados de entrada do dataflow é o atributo que que tem maior relevância na obtenção de menores tempos de execução e que as Redes Neurais Artificiais são o método de aprendizado de máquina que traz os melhores resultados.

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.

Nuvens computacionais executam as requisições de seus clientes em um ambiente virtual configurado de acordo com as necessidades das aplicações. O cliente normalmente paga por uma quantidade de recursos estimada para sua aplicação executar, mas esta pode vir a consumir mais ou menos recursos do que o esperado. Para evitar tais situações, o gerenciamento eficiente de recursos é essencial. Esse trabalho visa elucidar alguns pontos estudados sobre o consumo de recursos de aplicações executando em Docker containers.

Nos últimos anos, o Apache Spark vem sendo utilizado como framework para execução de experimentos científicos modelados como workflows. Por mais que represente um avanço, o Spark não foi projetado para gerenciar execuções de aplicações científicas, e seu escalonamento não considera estimativas de consumo de recursos pelas atividades do workflow. Esse artigo apresenta o Spark-SGreedy, uma proposta de algoritmo de escalonamento de workflows no Spark que usa dados de proveniência (histórico) para analisar a previsão de consumo de recursos das atividades do workflow e escaloná-las de acordo com tal previsão.

Nuvens computacionais oferecem recursos e serviços a seus usuários, que por sua vez desejam que suas requisições sejam atendidas rapidamente, com baixos custos de utilização. Do lado do provedor, é desejado maximizar o uso de recursos do ambiente para atender um maior número de clientes. Este trabalho incorpora a MEC, um controlador de recursos pertencente à ferramenta MEMiC, que realiza decisões de preempção de máquinas virtuais, um modelo preditivo para guiar tais decisões objetivando a minimização do tempo de serviço e maximizando o uso dos recursos de memória. Resultados experimentais mostram as vantagens de abordagem proativa proposta.

The dynamic nature of application and service requirements has lead the cloud community to invest in the study and development of elasticity features that have the ability to re-dimension resource capacities dynamically. Both online applications under unpredictable workloads or scientific workflows with different datasets require autonomic scaling in order to avoid either performance degradation due to an insufficient resource capacity or paying for additional, sub-utilized and possibly unnecessary capacity. In an effort to improve utilization, focus has recently turned to vertical elasticity where the processing, memory or storage capacity of a single virtual machine (VM) is adjusted in accordance with the application's needs. Given the increasing influence of memory availability on performance, this work presents the main features of the Memory Elasticity Controller (MEC). This VM allocation tool aims to improve the throughput of jobs or workflow tasks by continuously and judiciously calibrating the amount of host memory allocated to each VM in accordance with that VM's respective job's changing run time requirements while, at the same time, trying to avoid compromising the job's performance. This paper presents the tool's architecture and describes the functionality adopted to manage and provide vertical memory elasticity to concurrently executing VMs on a server. Results show that MEC is able to provide both resource providers and applications with an additional opportunity to improve throughput and performance.

A virtualização por contêineres vem ganhando popularidade nos últimos anos devido à criação de ambientes virtuais isolados com uma alocação eficiente de recursos computacionais para a execução de aplicações considerando o compartilhamento de recursos. Este trabalho tem por objetivo verificar se esta melhoria é sempre possível através da comparação do uso de contêineres e máquinas virtuais para a execução de uma aplicação científica de biodiversidade usado em um serviço de nuvem. Em particular, sua eficiência na escalabilidade desses ambientes virtuais em Computação de Alta Vazão é analisada.

In combinatorial optimization problems, the neighborhood search (NS) is a fundamental component for local search based heuristics. It consists of selecting a solution from a high cardinality set of neighbor solutions, by means of operations called moves. To perform this search, NS algorithms usually adopt two main approaches: selecting the first or best improving move. The Multi Improvement (MI) strategy is a recently proposed method that consists in exploring simultaneously multiple move operations during the NS phase aiming to reach good quality solutions with shorter computational steps. This paper presents a benchmark for MI strategies in hybrid CPU/GPU systems. This technique efficiently explores the CPU processing power together with the massive parallelism achieved by modern GPUs, emerging as an efficient alternative for classic CPU neighborhood search strategies. The advantage of this approach depends heavily on finding the best tradeoff between CPU and GPU processing, as well as minimizing the memory transfers involved in the process. In the experiments, several MI configurations were tested in a hybrid CPU/GPU environment presenting better results than classical neighborhood search strategies for the Minimum Latency Problem, a hard combinatorial optimization problem.

Parallel applications composed of a set of tasks that follow a partial precedence order represent an important class of scientific applications. In high performance computing, environments dedicated to scientific applications are composed of clusters of multicore machines, which consist typically of a set of processing cores that partially share a hierarchy of cache memory. Harnessing the available memory is crucial to achieve good performance in these clusters. This paper proposes strategies based on the list scheduling framework to schedule application tasks on individual cores of multicore clusters. Our idea is to minimize the execution time of the application, by taking into consideration cache contention. Experiments with a representative set of applications show that the scheduling algorithms with contention-aware mechanisms can improve significantly the application performance.

While the task scheduling problem under the delay model has been studied extensively, relatively little research exists for more realistic communication models such as the LogP model which considers, in addition to latency, the cost of sending and receiving messages, and the network or link capacity. The task scheduling problem is known to be NP-complete even under the delay model (a special case of the LogP model). This paper investigates the similarities and differences between task-clustering algorithms for the delay and LogP models, and describes task-scheduling algorithm for the allocation of arbitrary task graphs to fully connected networks of processors under the LogP model. The strategy exploits the replication and clustering of tasks to minimize the ill effects of communication overhead on the makespan. A number of restrictions are presented which are used to simplify the design of the new algorithm. The quality of the schedules produced by the algorithm compare favorably with two well-known delay model-based algorithms and a previously existing LogP strategy.

During their execution, a significant number of applications often sub utilize the capacity of the resources to which they are allocated or require more. Furthermore, with the current scale up trend in server design, effective utilization can only be achieved by applications sharing such resources. Cluster management systems already support static resource partitioning at job submission time and given that application utilization more than often varies during the execution, it will become increasingly more important to permit applications to harness all available spare capacity. This paper investigates the feasibility of malleable evolving versions of applications to improve performance and system efficiency. Extending a previous classification, we show that improvements can be achieved for a real astrophysics application.

Multicore architectures are an important contribution in computing technology since they are capable of providing more processing power with better cost-benefit than single-core processors. Cores execute instructions independently but share critical resources such as L2 cache memory and data channels. Clusters using multicore architectures or multiprocessors chips (MPC's) suggest a hierarchical memory environment. Parallel applications should take advantage of such memory hierarchy to achieve high performance. This paper presents a performance analysis of a synthetic application in a multicore cluster and introduces a preliminary architecture model that considers communication through both shared memory and data channels and its impact on the application performance.

This paper addresses the challenge of how to permit tightly coupled parallel applications, optimised for uniform, stable, static environments, execute equally efficiently in environments which exhibit the complete opposite characteristics. Using the N-body problem as a case study, both the traditional and proposed grid enabled MPI implementations of the popular ring algorithm are analysed. Results with respect to performance show the latter approach to be competitive on a cluster and significantly more effective in heterogeneous and dynamic environments.

Na busca por melhores serviços ou maiores lucros, a utilização de metaheurísticas tem sido um importante aliado da indústria para resolver questões operacionais complexas em tempos computacionais aceitáveis. O desenvolvimento de metaheurísticas paralelas eficientes é difícil e, para executar instâncias reais, os algoritmos necessitam de muito poder computacional. Enquanto a computação em grades pode oferecer tal poder computacional, suas características específicas criam uma complexidade adicional para desenvolver aplicações eficientes. Este trabalho propõe uma estratégia simples de paralelização para executar metaheurísticas seqüenciais em grades computacionais. O objetivo é eliminar a necessidade do desenvolvedor encarar a tarefa de paralelizar uma metaheurística, e mostrar que executando múltiplas instâncias de uma metaheurística seqüencial de forma coordenada em paralelo é possível reduzir o tempo para alcançar boas soluções. A paralelização proposta é composta de duas camadas: um middleware de gerenciamento da execução na grade e a estratégia de coordenação das metaheurísticas seqüenciais. Para validar essa proposta foram desenvolvidas duas novas metaheurísticas paralelas, uma para o problema do torneio com viagens espelhado e a outra para o problema da árvore geradora de custo mínimo com restrição de diâmetro. Ambas as paralelizações foram capazes de melhorar, para várias instâncias, os melhores resultados conhecidos na literatura.

Metaheuristics are general high-level procedures that coordinate simple heuristics and rules to find good approximate solutions to computationally difficult combinatorial optimization problems. Parallel implementations of metaheuristics appear quite naturally as an effective approach to speedup the search for approximate solutions. Besides the accelerations obtained, parallelization also allows solving larger problems or finding better solutions. We present in this work four slightly differing strategies for the parallelization of an extended GRASP with ILS heuristic for the mirrored traveling tournament problem, with the objective of harnessing the benefits of grid computing. Computational experiments on a dedicated cluster illustrate the effectiveness and the scalability of the proposed strategies. In particular, we show that the parallel strategy implementing cooperation through a pool of elite solutions scales better than the others and is able to find solutions that cannot be reached by the others. Computational grids are distributed high latency environments which offer significantly more computing power than traditional clusters. The best parallel strategy was also implemented and tested using a true grid platform. We report original results from pioneer computational experiments on a shared computational grid formed by 82 machines distributed over four clusters in three cities, illustrating the potential of the application of computational grids in the fields of metaheuristics and combinatorial optimization.

The MPI message passing library is used extensively in the scientific community as a tool for parallel programming. Even though improvements have been made to existing implementations to support execution on computational grids, MPI was initially designed to deal with homogeneous, fault- free, static environments such as computing clusters. The typical programming approach is to execute a single MPI process on each resource. However, this may not be appropriate for heterogeneous, non-dedicated and dynamic environments such as grids. This paper aims to show that programmers can implement parallel MPI solutions to their problems in an architectural independent style and obtain good performance on a grid by transferring responsibility to an application management system (AMS). A comparison of program implementations under a traditional MPI execution model and a fine-grain model highlight the advantages of using the latter.

Computational grids aim to aggregate significant numbers of resources to provide sufficient, but low cost, computational power to an ever growing variety applications. Writing applications capable of executing efficiently in these grid environments is however extremely difficult for inexperienced users. The grid's geographically distributed resources are typically heterogeneous, non-dedicated, and are offered without any performance or availability guarantees. This work investigates an alternative approach (based on smarter system-aware applications) to solve the problem of developing and managing the execution of grid applications efficiently. Results show that these system-aware MPI applications are indeed faster than their conventional implementations and easily grid enabled.

Researchers are constantly looking for ways to improve the execution time of parallel applications on distributed systems. Although compile-time static scheduling heuristics employ complex mechanisms, the quality of their schedules are handicapped by estimated run-time costs. On the other hand, while dynamic schedulers use actual run-time costs, they have to be of low complexity in order to reduce the scheduling overhead. We investigate the viability of integrating these two approaches into a hybrid scheduling framework. The relationship between static schedulers, dynamic heuristics and scheduling events are examined. The results show that a hybrid scheduler can indeed improve the schedules produced by good traditional static list scheduling algorithms.

Task scheduling is a key element in achieving high performance from multicomputer systems. To be efficient, scheduling algorithms must be based on a cost model appropriate for computing systems in use. The optimal scheduling of tasks is NP-hard, and a large number of heuristic algorithms have been proposed for a variety of scheduling conditions (graph types, granularities or cost models). This paper studies the problem of task scheduling under the LogP model and presents both theoretical and experimental results for a cluster-based, task duplication methodology.

While the NP-complete problem of scheduling weighted arbitrary directed acyclic graphs under the delay model has been studied extensively, comparatively little work exists for this problem under more realistic models such as the LogP model. Recently, a number of LogP-based scheduling heuristics and related works have appeared in the literature, including a task clustering algorithm design methodology which identifies four crucial design issues (Boeres et al., 1997). Through the use of five task replication-based scheduling heuristics based on this design methodology, this paper investigates the effect of various implementations of these design issues on the schedules produced for the allocation of arbitrary task graphs to fully connected networks of processors under a LogP-type model. The quality of the schedules produced by these algorithms are also compared with good, well-known delay model-based algorithms and an existing LogP strategy.

While the task scheduling problem under the delay model has been studied extensively, relatively little research exists for more realistic communication models such as the LogP model. The task scheduling problem is known to be NPcomplete even under the delay model (a simplified instance of the LogP model). This chapter describes the LogP model and the influence of its communication parameters on task scheduling. The similarities and differences between clustering algorithms under the delay and LogP models are discussed and a design methodology for clustering-based scheduling algorithms for the LogP model is presented. Using this design methodology, a task scheduling algorithm for the allocation of arbitrary task graphs to fully connected networks of processors under LogP model is proposed. The strategy exploits the replication and clustering of tasks to minimize the ill effects of communication on the makespan.

Effective tools for the design of parallel algorithms must be based on a computational model for parallel computing that is a trade-off between realism and simplicity. Where the underlying programming model requires the mapping and scheduling of tasks, the computational model should incorporate some notion of interprocessor communication delay. If the target architecture is massively parallel then a more complex model, including some notion of locality, may be required.

Computational grids aim to aggregate significant numbers of resources to provide sufficient, but low cost, computational power to various applications. Writing applications capable of executing efficiently in grids, is however extremely difficult. Their geographically distributed resources are typically heterogeneous, non-dedicated, and offer no performance or availability guarantees. This makes the collective management of resources and application both complex and arduous. This work investigates an alternative approach (based on system-awareness) to solve the problem of developing and managing the execution of grid applications efficiently. Results show that these system-aware applications are indeed faster than their conventional implementations and easily grid enabled.

The complexity of the static scheduling problem on heterogeneous resources has motivated the development of low complexity heuristics such as list scheduling. However, the greedy characteristic of such heuristics can, in many cases, generate poor results. This work proposes the integration of list scheduling heuristics with search mechanisms based on both genetic algorithms and GRASP, to efficiently schedule tasks on distributed systems. The results show that the hybrid approach is robust and can converge quickly to good quality solutions.