Hervé Paulino

Heterogeneity is omnipresent in today’s commodity computational systems, which comprise at least one multi-core Central Processing Unit (CPU) and one Graphics Processing Unit (GPU). Nonetheless, all this computing power is not being exploited in mainstream computing, as the programming of these systems entails many details of the underlying architecture and of its distinct execution models. Current research on parallel programming is addressing these issues but, still, the systems’ heterogeneity is exposed at language level.
This paper proposes a uniform framework, grounded on the Single Operation Multiple Data model, for the programming of such heterogeneous systems. The model is declarative, empowering the compiler to generate code for multiple architectures from the same source. To this extent, we designed a simple extension of the Java programming language that embodies the model, and developed a compiler that generates code for both multi-core CPUs and GPUs. A performance evaluation attests the validity of the approach that, despite being based on a simple programming model, is able to deliver performance gains on par with hand-tuned data parallel multi-threaded Java applications.

Distributed transactional memory (DTM) presents itself as a highly expressive and programmer friendly model for con- currency control in distributed programming. Current DTM systems make use of both data distribution and replication as a way of providing scalability and fault tolerance, but both techniques have advantages and drawbacks. As such, each one is suitable for different target applications, and deployment environments. In this paper we address the support of different data replication models in DTM. To that end we propose ReDstm, a modular and non-intrusive framework for DTM, that supports multiple data replication models in a general purpose programming language (Java). We show its application in the implementation of distributed software transactional memories with different replication models, and evaluate the framework via a set of well-known benchmarks, analysing the impact of the different replication models on memory usage and transaction throughput.

Os protocolos de replicação parcial de dados apresentam um grande potencial de escalabilidade. O SCORe é um protocolo para replicação parcial proposto recentemente que faz uso de controlo de concorrência multi-versão. Neste artigo abordamos um dos problemas principais que afeta o desempenho deste tipo de protocolos: a localidade dos dados, i.e., pode-se dar o caso do nó local não ter uma cópia dos dados a que pretende aceder, e nesse caso é necessário realizar uma ou mais operações de leitura remota. Assim, a não ser que se empreguem técnicas para melhorar a localidade no acesso aos dados, o número de operações de leitura remota aumenta com o tamanho do sistema, acabando por afetar o desempenho do mesmo. Nesse sentido, introduzimos um mecanismo de caching que permite replicar cópias de dados remotos de maneira a que seja possível servir localmente dados remotos enquanto que se mantém a consistência dos mesmos e a escalabilidade oferecida pelo protocolo. Avaliamos o mecanismo de caching com um benchmark conhecido da literatura e os resultados experimentais mostram resultados animadores com algum aumento no desempenho do sistema e uma redução considerável da quantidade de operações de leitura remota.

Currentcomputationalsystemsareheterogeneousbynature, featuring a combination of CPUs and GPUs. As the latter are becoming an established platform for high-performance computing, the focus is shifting towards the seamless programming of the heterogeneous systems as a whole. The distinct nature of the architectural and execution models in place raise several challenges, as the best hardware configuration is behavior and data-set dependent. In this paper, we focus the execution of compound computations in multi-CPU/multi-GPU environments, in the scope of Marrow algorithmic skeleton framework, the only, to the best of our knowledge, to support skeleton nesting in GPU computing. We address how these computations may be efficiently scheduled onto the target hardware, and how the system may adapt itself to changes in the CPU’s load and in the input data-set.

An emerging trend in the field of Graphics Processing Unit (GPU) computing is the harnessing of multiple devices to cope with scalability and performance requirements. How- ever, multi-GPU execution adds new challenges to the al- ready complex world of General Purpose computing on GPUs (GPGPU), such as the efficient problem decomposition, and dealing with device heterogeneity. To this extent, we pro- pose the use of the Marrow algorithmic skeleton framework (ASkF) to abstract most of the details intrinsic to the pro- gramming of such platforms. To the best of our knowledge, Marrow is the first ASkF to support skeleton nesting on single and (now) multiple GPU systems. In this paper we present how it can transparently distribute the execution of skeleton compositions among a set of, possibly, hetero- geneous devices. An experimental evaluation assesses the proposal’s effectiveness, from a scalability and performance perspective, with good results.

Transactional memory (TM) is consistently making its way into mainstream programming, being already deployed by some of the major CPU manufacturers and in several reference compilers. To cope with requirements such as scalability and dependability, recent proposals explore the combination of TM with data replication, bringing TM to distributed environments - conceiving distributed transactional memory (DTM). However, current DTM frameworks support only full data replication. They provide the best possible level of tolerance to data loss, but limit the system's total storage capacity to the capacity of the node with fewer resources, and require coordination among all the system's nodes, an approach bound to hamper scalability in large scale systems. In this context, a partial data replication strategy can help to lessen these shortcomings. Each node replicates only a subset of the system's dataset, an approach that aims at combining the best of data distribution and full replication, while trying to attenuate their disadvantages. The key idea is to allow the dataset to be distributed among the participating nodes and to decrease the number of nodes that have to participate in a transaction's confirmation, as any given transaction only has to be confirmed by the nodes that replicate the data items in its read and write sets. By distributing the data and reducing the coordination cost among nodes, partial data replication leverages the system's scalability. Although this strategy has already been explored by the distributed databases research field, it is yet to be addressed in the context of (D)TM. More specifically, partial data replication has been broadly applied in key-value stores, and even though these work on in-memory data and support transactions, they present significant differences when compared with DTM systems for general purpose programming languages. To this extent, we propose PARdstm, to the best of our knowledge, the first DTM framework to include support for partial data replication. As such, the contributions of this work are: a reasoning on how partial data replication shall be supported in general purpose programming languages (Java, in particular), and a modular software framework that embeds such principles to provide a highly expressive and non-intrusive programming API. Initial experimental results give evidence that our approach may enhance scalability in large scale systems, when compared to full data replication. An ongoing comprehensive study will allow us to assess in which contexts of use (workloads, number of nodes, etc.) partial data replication may be an effective alternative.

A crescente utilização de Unidades de Processamento Gráfico (GPUs) na computação de caráter geral levanta questões de desempenho e de escalabilidade. Para responder a estes requisitos de forma efetiva, cada vez mais se recorre à utilização colaborativa de vários GPUs num só sistema. Esta abordagem introduz, no entanto, novos desafios, tal como a decomposição do domínio do problema e a gestão da possível heterogeneidade dos dispositivos. Neste contexto assume particular relevância a proposta de abstrações que escondam a complexidade da programação destes sistemas. Existe já algum trabalho na área, mas este restringe-se ao paralelismo de dados. Por conseguinte, neste artigo abordamos a utilização de uma biblioteca de esqueletos algorítmicos, Marrow, para a exploração de paralelismo de tarefas em sistemas computacionais com estas características. Os resultados são promissores, apresentado a escalabilidade esperada nos sistemas testados.

Os sistemas de memória transacional distribuída atuais recorrem essencialmente à distribuição ou à replicação total para distribuir os seus dados pelos múltiplos nós do sistema. No entanto, estas estratégias de replicação de dados apresentam limitações. A distribuição não oferece tolerância a falhas e a replicação total limita a capacidade de armazenamento do sistema. Nesse contexto, a replicação parcial de dados surge como uma solução intermédia, que combina o melhor das duas anteriores com o intuito de mitigar as suas desvantagens. Esta estratégia tem sido explorada no contexto das bases de dados distribuídas, mas tem sido pouco abordada no contexto da memória transacional e, tanto quanto sabemos, nunca antes tinha sido incorporada num sistema de memória transacional distribuída para uma linguagem de propósito geral. Assim, neste artigo propomos e avaliamos uma infraestrutura para replicação parcial de dados para programas Java bytecode, que foi desenvolvida com base num sistema já existente de memória transacional distribuída. A modularidade da infraestrutura que apresentamos permite a implementação de múltiplos algoritmos e, por conseguinte, avaliar em que contextos de utilização (workloads, número de nós, etc.) a replicação parcial se apresenta como uma alternativa viável a outras estratégias de replicação de dados.

O controlo da concorrência no acesso a estado partilhado assume actualmente um papel de destaque no desenvolvimento de software. Trabalhos recentes propõem que tal gestão seja expressa ao nível dos dados, em alternativa à usual centralidade no código. A principal vantagem é o acoplamento da gestão da concorrência com a declaração dos dados, eliminando desse modo a descentralização dos erros de concorrência, facilitando a sua correção. No entanto, as abordagens centradas nos dados existentes pecam por não garantirem a ausência de deadlocks em todos os cenários e/ou exigirem do programador a agregação explícita dos recursos que devem ser avaliados atomicamente. A nossa proposta colmata ambas estas limitações. O programador anota isoladamente que zonas de memória requerem acesso exclusivo, sendo que uma análise estática infere quais dessas devem ser agrupadas e adquiridas atomicamente, e garante que o código gerado é ausente de deadlocks. De modo a aferir-se a eficiência da nossa solução, comparamos o seu desempenho e a sua produtividade relativamente à memória transacional e outras abordagens centrada nos dados.

A decomposição correta de um problema paralelo com base na hierarquia de memória onde irá executar pode levar a ganhos de desempenho significativos durante execução do mesmo. No entanto, os subsistemas de memória das arquiteturas multicore modernas apresentam variadas configurações, em termos das suas organizações hierárquicas e da capacidade dos seus diversos níveis de memória. Existem diversas abordagens que permitem adequar a execução de uma aplicação à estratificação hierárquica da memória,. Contudo estas exigem do programador um conhecimento profundo da arquitetura alvo e de programação paralela em geral. A abordagem apresentada neste artigo contrasta com as demais, transpondo esta responsabilidade para o sistema de execução, colocando sobre a sua alçada a decomposição hierárquica da computação. Nessa medida, ao programador cabe apenas expressar de forma genérica os algoritmos de subdivisão do domínio do problema. Avaliamos o desempenho da nossa abordagem relativamente a outra baseada na usual decomposição horizontal do domínio do problema. Os resultados são bons, apresentando ganhos de performance em aplicações que usufruem do tipo de otimização efetuada e desempenhos equiparáveis nas restantes.

The Graphics Processing Unit (GPU) is gaining popular- ity as a co-processor to the Central Processing Unit (CPU). However, harnessing its capabilities is a non-trivial exercise that requires good knowledge of parallel programming, more so when the complexity of these applications is increasingly rising. Languages such as StreamIt [1] and Lime [2] have addressed the offloading of composed computations to GPUs. However, to the best of our knowledge, no support exists at library level. To this extent, we propose Marrow, an algorithmic skeleton frame- work for the orchestration of OpenCL computations. Marrow expands the set of skeletons currently available for GPU computing, and enables their combination, through nesting, into complex structures. Moreover, it introduces optimizations that overlap communication and computa- tion, thus conjoining programming simplicity with performance gains in many application scenarios. We evaluated the framework from a perfor- mance perspective, comparing it against hand-tuned OpenCL programs. The results are favourable, indicating that Marrow’s skeletons are both flexible and efficient in the context of GPU computing.