This special issue of Concurrency and Computation: Practice and Experience comprises four papers extending the original workshop publications accepted and presented at MPP 2019 (8th Workshop on Parallel Programming Models – Special Issue on IoT and Machine Learning), held in Rio de Janeiro in conjunction with IPDPS 2019. The papers represent interesting research ideas of parallel programming models, tools, and optimizations suited for being applied to IoT-based applications. The paper titled “Enabling Heterogeneous Ray-Tracing Acceleration in Edge/Cloud Architectures” represents a very interesting research on reconfigurable accelerators for Ray-Tracing, specialized in computing ray-triangle intersections at the network edge of a heterogeneous cloud computing environment. The authors validated their approach on the Xilinx Zynq FPGA platform. The paper titled “An Incremental Reinforcement Learning Scheduling Strategy for Data-Intensive Scientific Workflows in the Cloud” is a research work proposing a new scheduling algorithm based on Reinforcement Learning for scientific workflows on HPC distributed resources and Clouds. The paper titled “Latency-aware Adaptive Micro-Batching Techniques for Streamed Data Compression on GPUs” proposes a set of Autonomic Computing strategies for configuring the optimal parallelism degree and batch size on streaming data compression parallel applications on GPU architectures. Finally, the paper titled “Gamma – General Abstract Model for Multiset mAnipulation and Dynamic Dataflow Model: an Equivalence Study” is an interesting research study on new applications of the Gamma Model (General Abstract Model for Multiset mAnipulation) and its joint utilization with the Dataflow programming model. As Guest Editors, we would like to express our gratitude for the valuable contributions made by all authors. We would like to thank all the reviewers who helped us during the thorough review process based on several review rounds. Finally, we would like to thank all the editorial board members and all staff of Concurrency and Computation: Practice and Experience for allowing us to publish our Special Issue and for their invaluable support during the whole publication process.

Modern GPUs allow concurrent kernel execution and preemption to improve hardware utilization and responsiveness. Currently, the decision on the simultaneous execution of kernels is performed by the hardware, which can lead to unreasonable use of resources. In this work, we tackle the problem of co-scheduling for GPUs in high competition scenarios. We propose a novel graph-based preemptive co-scheduling algorithm, with the focus on reducing the number of preemptions. We show that the optimal preemptive makespan can be computed by solving a Linear Program in polynomial time. Based on this solution we propose graph theoretical model and an algorithm to build preemptive schedules which minimize the number of preemptions. We show, however, that finding the minimum amount of preemptions among all preemptive solutions of optimal makespan is a NP-hard problem. We performed experiments on real-world GPU applications and our approach can achieve optimal makespan by preempting 6 to 9% of the tasks.

The Kronecker product, also called tensor product, is a fundamental matrix algebra operation, used to model complex systems using structured descriptions. This operation needs to be computed efficiently, since it is a critical kernel for iterative algorithms. In this work, we focus on the vector-kronecker product operation, where we present an in-depth performance analysis of a sequential and a parallel algorithm previously proposed. Based on this analysis, we proposed three optimizations: changing the memory access pattern, reducing load imbalance and manually vectorizing some portions of the code with Intel SSE4.2 intrinsics. The obtained results show better cache usage and load balance, thus improving the performance, especially for larger matrices.

Julia is a quite recent dynamic language proposed to tackle the trade-off between productivity and efficiency. The idea is to provide the usability o flanguages such as Python or MATLAB side by sidewith the performance of C and C++. The support for multithreading programming in Julia was only released last year, and therefore still requires performance studies. In this work, we focus on the parallel loops and more specifically on the available mechanisms for assigning the loop iterations to the threads. We analyse the per-formance of the macros @spawn and @threads, used for loop parallelization. Our results show that there is no best fit solution for all cases. The use of @spawn provides better load balance for unbalanced loops with reasonably heavy iterations, but incurs in high overhead for workstealing. While @threads has low overhead, and workswell for loops with good balance among iterations.

This Special Issue of Concurrency and Computation: Practice and Experience gathers seven selected research articles, which are the result of extended work previously presented at the Brazilian “XVII Simpósio em Sistemas Computacionais de Alto Desempenho,” WSCAD 2016, held in conjunction with the 28th International Symposium on Computer Architecture and High Performance Computing, SBAC-PAD 2016, Aracaju, SE, Brazil, October 5-7, 2016. Since 2000, this workshop has presented important and interesting research in the fields of computer architecture, high-performance computing, and distributed systems. The scope of the current special Issue is broad and representative of the multidisciplinary nature of high-performance and distributed computing, covering important issues of the field, such as parallel applications, GPU computing, energy consumption, and cloud computing. The papers and their main focus are the following. The paper entitled “Parallel rule-based selective sampling and on-demand learning to rank” by Mateus F. e Freitas, Daniel X. Sousa, Wellington S. Martins, Thierson C. Rosa, Rodrigo M. Silva, and Marcos A. Gonçalves uses parallelism techniques to improve the performance of the Learning to Rank (L2R) task. More specifically, the authors1 propose two methods to exploit parallelism on rule-based systems: Learning to Rank (L2R) training data sets using selective sampling and query-customized ranking models generated on the fly. The authors propose parallel algorithms and GPU implementations for these two cases showing that data set reduction takes only a few seconds with speedups of up to 148× over a serial baseline and that queries can be processed in only a few milliseconds with speedups of 1000× over a serial baseline and 29× over a parallel baseline for the best case. The extended work provides the implementations on multiple GPUs, further increasing the speedup over the baselines. Focusing on GPU computing, in the contribution2 entitled “Maximizing the GPU resource usage by reordering concurrent kernels submission,” authors Rommel A.Q. Cruz, Cristiana Bentes, Bernardo Breder, Eduardo Vasconcellos, Esteban Clua, Pablo M.C. de Carvalho, and Lúcia M.A. Drummond propose a reordering strategy to identify the best order to submit the kernels to execute on the GPU, aiming at maximizing its utilization and increasing the overall throughput. The authors model the problem as a series of knapsack problems and use a dynamic programming approach to solve them. The amount of resources is modeled as the knapsack capacity, and the strategy tries to fulfill the knapsack with kernels that take the most advantage of the available resources, favoring kernels with smaller execution time. The proposed strategy was evaluated using real-world and synthetic applications with different numbers of kernels and resource requirements. The results show that the reordering strategy provides significant gains in the average turnaround time and system throughput compared to the kernels submission implemented in modern GPUs. Tackling energy efficiency issues, in the work3 entitled “Energy efficiency and I/O performance of low-power architectures,” authors Pablo J. Pavan, Ricardo K. Lorenzoni, Vinícius R. Machado, Jean L. Bez, Edson L. Padoin, Francieli Z. Boito, Philippe O.A. Navaux, and Jean-François Méhaut present an energy efficiency and I/O performance analysis of low-power architectures with the goal of evaluating the viability of using them as storage servers. The results show that despite the fact that the power demand of the storage device accounts for a small fraction of the power demand of the whole system, significant increases in power demand are observed when accessing the storage device. The authors also investigate the access pattern impact on power demand, looking at the whole system and at the storage device by itself, finally comparing all of the tested configurations regarding energy efficiency. This study provides guidelines for the replacement of traditional storage servers by low-power alternatives. As a consequence, the choice will depend on the expected workload, estimates of power demand of the system, and factors limiting the performance. Related to cloud computing models, in the contribution4 entitled “Statistical analysis of Amazon EC2 cloud pricing models,” authors Gustavo Portella, Genaina N. Rodrigues, Eduardo Nakano, and Alba C.M.A. Melo show a statistical analysis for two Amazon cloud pricing models: on demand and spot. While the on-demand cloud instances are charged a fixed price and can only be terminated by the user, with very high availability, the spot instances are charged dynamically, which price is 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. The analysis for on-demand instances resulted in multiple linear regression equations that represent the influence of the characteristics of the processor and RAM memory in the composition of the price of different types of instances available on the Amazon EC2 provider. To analyze the Amazon spot pricing, the authors used time-smoothed moving averages by 12-hour periods, aiming to provide a price-availability trade-off to the user. With an extensive experimental evaluation, the authors conclude that the user's bid can be set at 30% of the on-demand price, with an availability above 90%, depending on the instance type. Also dealing with GPU computing, in the contribution5 entitled “DTM@GPU: characterizing and evaluating trace redundancy in GPU,” authors Leandro A. J. Marzulo, Alexandre C. Sena, Alexandre S. Nery, Cristiana Bentes, Igor M. Coelho, Maria Clicia S. de Castro, Saulo T. Oliveira, Tiago A. O. Alves, and Felipe M. G. França explore the concept of instruction reuse in GPUs. They propose the DTMGPU model that adapts the DTM (Dynamic Trace Memoization) technique to the NVIDIA GPU architecture. The proposed model considers the particularities of the GPU architecture in the reuse mechanism. Instruction reuse can be of two types: intra-thread and inter-threads. The authors perform a detailed investigation on the characteristics of the reused traces. This characterization shows the number and size of the reused traces, the influence of the cache size on reuse rates, and the cycles that are saved when all threads in a warp reuse instructions or traces. The results show approximately up to 35.3% of reuse, yielding an estimated speedup gain of 10.7%. Dealing with parallel and dataflow models, the paper6 entitled “DF-DTM: Dynamic Task Memoization and reuse in dataflow” and authored by Leandro Rouberte, Alexandre C. Sena, Alexandre S. Nery, Leandro A. J. Marzulo, Tiago A. O. Alves, and Felipe M. G. França also discusses instruction reuse and the DTM (Dynamic Trace Memoization) technique, but in a different environment, a Dataflow System. The authors propose the Dataflow Dynamic Task Memoization (DF-DTM) technique that allows the reuse of both nodes and subgraphs in dataflow, which are analogous to instructions and traces, respectively. The potential of DF-DTM is evaluated by a series of experiments that analyze the behavior of redundant tasks in five relevant benchmarks, where up to 99.70% of the instantiated tasks could be reused. This work also evaluates how reuse rates can be affected by limiting the subgraph size, memoization table size, task granularity, and problem size, showing that DF-DTM can yield good reuse rates in more realistic environments. Finally, considering GPU issues, the paper in this Special Issue,7 “Evaluating optimizations that reduce global memory accesses of stencil computations in GPGPUs,” authored by Thiago Nasciutti, Jairo Panetta, and Pedro Lopes, presents a performance study on different optimizations for 3D stencil computations on GPUs. The focus is on memory-oriented optimizations with varying grid and stencil sizes. The optimizations reduce global memory contention caused by the set of multiprocessors. The optimizations evaluated are grid tiling, inserting spatial and temporal loops into kernels, register reuse, and some of their combinations. A standardized experiment evaluates performance variation with grid size and stencil size for each optimization. Experimental data show that codes that use these optimizations are up to 3.3 times faster than the classical stencil formulation and that the optimization degree depends on the grid and stencil sizes. We hope that the readers can benefit from the perspectives presented in this Special Issue. The topics covered in the papers are timely and important, and the authors have done an excellent job in presenting their innovative contributions. Regarding the reviewing process, our referees (integrated by recognized researchers from the international community) made a great effort in evaluating the papers. We would like to acknowledge their effort in providing us with excellent feedback at the right time. Therefore, we wish to thank all the authors and reviewers. Finally, we would also like to express our gratitude to the Editor in Chief of this Journal, for his advice, vision, and support.

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 In a program, there is usually a significant amount of instructions that are repeatedly executed with the same inputs during the execution. This redundancy allows the reuse of previous computations, potentially reducing the program execution time. The Dynamic Trace Memoization technique (DTM) was proposed to exploit the reuse of a dynamic sequence of redundant instructions for superscalar CPUs. This paper proposes the application of the DTM technique on a GPU architecture. We propose the DTM@GPU model that adapts the original DTM technique to the NVIDIA GPU architecture by introducing architectural modifications and the identification of different trace reuse styles in multithreaded environments. We investigate reuse opportunities in real‐world GPU applications and the potential performance gains. We also perform a detailed investigation on the characteristics of the reused traces. This characterization shows the number and size of the reused traces, the influence of the cache size on reuse rates, and the cycles that are saved when all threads in a warp reuse instructions or traces. The results show approximately up to 35.3% of reuse, yielding an estimated speedup gain of 10.7%.

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.

The vast amount of data obtained from current remote sensing data acquisition technologies represents a wealth of useful and affordable geospatial data for policy and decision makers. However, the consequent computational cost of analyzing these data may become prohibitive. This letter extends previous efforts in exploiting distributed processing to speed up the image interpretation process. In this letter, we propose and evaluate a mechanism to exploit task parallelism in addition to data parallelism. Experiments conducted on cloud computing infrastructure, following an object-based interpretation model, demonstrated that substantial performance gains can be obtained with the proposed mechanism.

Image segmentation is a critical step in image analysis, and usually involves a high computational cost, especially when dealing with large volumes of data. Given the significant increase in the spatial, spectral and temporal resolutions of remote sensing imagery in the last years, current sequential and parallel solutions fail to deliver the expected performance and scalability. This work proposes a scalable and efficient segmentation method, capable of handling efficiently very large high resolution images. The proposed solution is based on the MapReduce model, which offers a highly scalable and reliable framework for storing and processing massive data in cloud computing environments. The solution was implemented and validated using the Hadoop platform. Experimental results attest the viability of performing region growing segmentation in the MapReduce framework.

This letter proposes a parallel version for graphics processing units (GPU) of a region-growing image segmentation algorithm widely used by the geographic object-based image analysis (GEOBIA) community. Initially, all image pixels are considered as seeds or primitive segments. Fine-grained parallel threads assigned to individual pixels merge adjacent segments iteratively always ensuring to minimize the overall heterogeneity increase. Besides spectral features the merging criterion considers morphological features that can be efficiently computed in the underlying GPU architecture. Two alternatives using different merging criteria are proposed and tested. An experimental analysis upon five different test images has shown that the parallel algorithm may run up to 19 times faster than its sequential counterpart.

This paper presents a description and the evaluation of the Netuno supercomputer, a high-performance cluster installed at Federal University of Rio de Janeiro in Brazil. The results for the High Performance Linpack (HPL) benchmark and two real applications are reported. Since building a high-performance cluster for running a wide range of applications is a non-trivial task, some lessons learned from assembling and operating this cluster, such as the excelent performance of the OpenMPI library, and the importance of the use an efficient parallel file system over the traditional NFS system, can be useful knowledge to support the design of new systems. Currently, Netuno is being heavily used to run large scale simulations in the areas of ocean modeling, meteorology, engineering, physics, and geophysics.

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.

Direct volume rendering has become a popular technique for visualizing volumetric data from sources such as scientific simulations, analytic functions, medical scanners, among others. Volume rendering algorithms, such as raycasting, can produce high-quality images, however, the use of raycasting has been limited due to its high demands on computational power and memory bandwidth. In this paper, we propose a new implementation of the raycasting algorithm that takes advantage of the highly parallel architecture of the Cell Broadband Engine processor, with 9 heterogeneous cores, in order to allow efficient raycasting of irregular datasets. All the computational power of the Cell BE processor, though, comes at the cost of a different programming model. Applications need to be rewritten, which requires using multithreading and vectorized code. In our approach, we tackle this problem by distributing ray computations using the visible faces, and vectorizing the lighting integral operations inside each core. Our experimental results show that we can obtain good speedups reducing the overall rendering time significantly.

In multi-agent systems, blackboard communication provides an easy way for agents to communicate. However, in a distributed architecture, the blackboard is commonly implemented in a single node, that is the "blackboard server". This approach may work well for a small number of agents. Nevertheless, when the number of agents increases, the blackboard server becomes the bottleneck for the system scalability. In this work we propose a novel agent communication system based on distributed-shared mechanisms that allows the implementation of a shared address space on a distributed system, without centralizing the blackboard. Our idea is to distribute the shared data over the nodes and use a message passing sub-system, totally transparent to the agents. We implemented this idea in a multi-agent system based on social laws, and used a distributed-shared memory system to handle the messaging. We created a conflict simulator, and showed that the distributed-shared mechanisms easy the implementation of a truly distributed blackboard.

State-of-the-art software distributed shared-memory systems (SDSMs) provide a cost-effective solution to run single-program-multiple-data (SPMD) applications on clusters of distributed memory computers. However, SDSMs are unsuitable for running applications with dynamic, highly asynchronous task parallelism (ATP), such as graphics, simulators, and decision support systems. In ATP-based applications, the execution of tasks depends not only on the input data but also on the variable amount of data that each task produces at runtime, which generates high load imbalance and communication traffic that degrades performance of SDSM systems drastically. In this work, we propose a new load balancing (LB) mechanism to enable SDSM systems to support dynamic task scheduling as required by ATP applications. To evaluate the benefits of our LB mechanism, we developed Clik a new multithreaded SDSM system with automatic load balancing. Our preliminary performance results of Clik running on a 16-node Linux SMP cluster for five ATP applications showed that Clik attained significant speedups. For four of our five applications, the speedups varied from 7.2 up to 13.8 on 16 processors

In this paper we evaluate the impact of the programming model on the performance and complexity of Entry Consistency-based software distributed shared-memory systems (software DSMs). We study three novel software DSMs that can all take advantage of lock-style primitives but impose different variations of the shared-memory programming model. The first variation is a plain shared-memory model based on barriers and mutual exclusion locks, where the association between shared data and lock variables is determined transparently by the system. The second model dictates that all accesses to shared data must be delimited by lock/unlock-type primitives (with or without mutual exclusion), even though the lock-data association is still performed transparently. The third model requires that all shared data accesses be delimited by lock/unlock-type primitives and the association between locks and data is specified explicitly by the programmer. A comparison of our software DSMs shows that increasing the model complexity simplifies the systems substantially. Our results also show that the second model can perform significantly worse than the first model, while the third model improves performance by 25% and 27% on average compared to the first and second models, respectively. We conclude that increasing the burden on the programmer is not necessarily a good option for software DSMs; only the most elaborate model we study achieves performance that justifies its programming complexity.

In this paper we propose a novel software-only distributed shared memory system (SW-DSM), the Affinity Entry Consistency (AEC) protocol. The protocol is based on Entry Consistency but, unlike previous approaches, does not require the explicit association of shared data to synchronization variables, uses the page as its coherence unit, and generates the set of modifications (in the form of diffs) made to shared pages eagerly. The AEC protocol hides the overhead of generating and applying diffs behind synchronization delays, and uses a novel technique, Lock Acquirer Prediction (LAP), to tolerate the overhead of transferring diffs through the network. LAP attempts to predict the next acquirer of a lock at the time of the release, so that the acquirer can be updated even before requesting ownership of the lack. Using execution-driven simulation of real applications, we show that LAP performs very well under AEC; LAP predictions are within the 80-97% range of accuracy. Our results also show that LAP improves performance by 7-28% for our applications. In addition we find that most of the diff creation overhead in the AEC protocol can usually be overlapped with synchronization latencies. A comparison against simulated TreadMarks shows that AEC outperforms TreadMarks by as much as 47%. We conclude that LAP is a useful technique for improving the performance of update-based SW-DSMs, while AEC is an efficient implementation of the Entry Consistency model.