Abstract Binary combinatorial optimization plays a crucial role in various scientific and engineering fields. While deterministic approaches have traditionally been used to solve these problems, stochastic methods, particularly metaheuristics, have gained popularity in recent years for efficiently handling large problem instances. Ant Colony Optimization (ACO) is among the most successful metaheuristics and is frequently employed in non‐binary combinatorial problems due to its adaptability. Although for binary combinatorial problems ACO can suffer from issues such as rapid convergence to local minima, its eminently parallel structure means that it can be exploited to solve large and complex problems also in this field. In order to provide a versatile ACO implementation that achieves competitive results across a wide range of binary combinatorial optimization problems, we introduce a parallel multicolony strategy with an improved cooperation scheme to maintain search diversity. We evaluate our proposal (Binary Parallel Cooperative ACO, BiPCACO) using a comprehensive benchmark framework, showcasing its performance and, most importantly, its flexibility as a successful all‐purpose solver for binary combinatorial problems.

Abstract Due to the increasingly large amount of data acquired into point clouds, from LiDAR (Light Detection and Ranging) sensors and 2D/3D sensors, massive point clouds processing has become a topic with high interest for several fields. Current client-server applications usually use multiresolution out-of-core proposals; nevertheless, the construction of the data structures required is very time-consuming. Furthermore, these multiresolution approaches present problems regarding point density changes between different levels of detail and artifacts due to the rendering of elements entering and leaving the field of view. We present an autotuning multiresolution out-of-core strategy to avoid these problems. Other objectives are reducing loading times while maintaining low memory requirements, high visualization quality and achieving interactive visualization of massive point clouds. This strategy identifies certain parameters, called performance parameters, and defines a set of premises to obtain the goals mentioned above. The optimal parameter values depend on the number of points per cell in the multiresolution structure. We test our proposal in our web-based visualization software designed to work with the structures and storage format used and display massive point clouds achieving interactive visualization of point clouds with more than 27 billion points.

Acquiring a functional comprehension of the deregulation of cell signaling networks in disease allows progress in the development of new therapies and drugs. Computational models are becoming increasingly popular as a systematic tool to analyze the functioning of complex biochemical networks, such as those involved in cell signaling. CellNOpt is a framework to build predictive logic-based models of signaling pathways by training a prior knowledge network to biochemical data obtained from perturbation experiments. This training can be formulated as an optimization problem that can be solved using metaheuristics. However, the genetic algorithm used so far in CellNOpt presents limitations in terms of execution time and quality of solutions when applied to large instances. Thus, in order to overcome those issues, in this paper we propose the use of a method based on ant colony optimization, adapted to the problem at hand and parallelized using a hybrid approach. The performance of this novel method is illustrated with several challenging benchmark problems in the study of new therapies for liver cancer.

Abstract Land consolidation is an essential tool for public administrations to reduce the fragmentation of land ownership. In particular, parcel exchange shows promising potential for restructuring parcel holdings, even more when the number of parcels and owners involved is large. Unfortunately, the number of possible exchange combinations grows very quickly with the number of participating landowners and parcels, with the associated challenge of finding an acceptable solution. In this paper, we present a high-performance solution for parcel exchange based on genetic algorithms. Our proposal, using Apache Spark framework, is based on the exploiting of distributed-memory systems with effortless access in order to reduce the execution time. This also allows increasing the search width through multiple populations that share their advances. This can be achieved without compromising the search depth thanks to the higher amount of resources available from using distributed-memory systems. Our proposal is capable of achieving better solutions in lower amounts of time compared to previous works, showing that genetic algorithms on a high performance system can be used to propose fair parcel exchanges under strict time constraints, even in complex scenarios. The performance achieved allows for fast trial of several options, reducing the time usually needed to perform administrative procedures associated with land fragmentation problems. Specifically, our proposal is capable of combining the benefits of both depth-focused and width-focused multithreaded parallelization. It matches the speedup gains of depth-focused multithreaded parallelization. The width-focused parallelization provides local minimum resilience and fitness value reduction potential. In this paper, multithreading solutions and Spark-based solutions are tested.

In recent years, the evolution and improvement of LiDAR (Light Detection and Ranging) hardware has increased the quality and quantity of the gathered data, making the storage, processing and management thereof particularly challenging. In this work we present a novel, multi-resolution, out-of-core technique, used for web-based visualization and implemented through a non-redundant, data point organization method, which we call Hierarchically Layered Tiles (HLT), and a tree-like structure called Tile Grid Partitioning Tree (TGPT). The design of these elements is mainly focused on attaining very low levels of memory consumption, disk storage usage and network traffic on both, client and server-side, while delivering high-performance interactive visualization of massive LiDAR point clouds (up to 28 billion points) on multiplatform environments (mobile devices or desktop computers). HLT and TGPT were incorporated and tested in ViLMA (Visualization for LiDAR data using a Multi-resolution Approach), our own web-based visualization software specially designed to work with massive LiDAR point clouds.

Solving tridiagonal linear-equation systems is a fundamental computing kernel in a wide range of scientific and engineering applications, and its computation can be modeled with parallel algorithms. These parallel solvers are typically designed to compute problems whose data fit in a common shared-memory space where all the cores taking part in the computation have access. However, when the problem size is large, data cannot be entirely stored in the common shared-memory space, and a high number of high-latency communications are performed. One alternative is to partition the problem among different memory spaces. At this point, conventional parallel algorithms do not facilitate the partition of computation in independent tiles, since each reduction depends on equations that may be in different tiles. This article proposes an algorithm based on a tree reduction, called the Tree Partitioning Reduction (TPR) method, which partitions the problem into independent slices that can be partially computed in parallel within different common shared-memory spaces. The TPR method can be implemented for any parallel and distributed programming paradigm. Furthermore, in this work, TPR is efficiently implemented for CUDA GPUs to solve large size problems, providing highly competitive performance results with respect to existing packages, being, on average, 22.03× faster than CUSPARSE.

Big data technologies have been growing up quickly during past years. New storage and computing solutions appear while those already established in the market are improved with new features and better performance. Along with this growth also rises the number of applications and fields where the inclusion of big data technologies provides a large number of benefits, from the reduction in computational costs and economic resources to the improvement in the quality of the services provided which has a direct impact on the customers satisfaction. LiDAR (Light Detection and Ranging) data processing is one of the topics that could benefit from the adoption of these kind of technologies due to the massive datasets that are being gathered nowadays, with applications in archaeology, geography, geology or forestry, among many others. An efficient management of this volume of data becomes a key point especially in visualization, computing and analytic processes. In this paper, we analyse how web applications for the visualization of LiDAR data can benefit from the adoption of big data storage technologies, as well as the advantages and disadvantages that may determine the choice of one of them.

GPUs fulfill high computation demands, but it is necessary to develop code carefully, selecting algorithms well suited to the GPU architecture and applying different optimizations. This article presents a GPU-suitable algorithm and a tuning strategy for performing the scan primitive over large problem sizes in CUDA. This tuning strategy defines different performance premises to find the GPU execution parameters that maximize performance. Taking these premises into consideration, we easily develop the kernels using CUDA skeletons to ensure efficiency and portability. Based on this, we describe an optimal proposal analyzed over different multiple GPU environments, the first multiple-GPU batch scan proposal to the best of our knowledge. The resulting implementations outperform other well-known libraries in most cases, such as CUDPP, ModernGPU, Thrust, CUB and LightScan.

This work describes an efficient implementation for solving tridiagonal systems on Graphics Processing Units (GPUs). The Wang and Mou algorithm has a computation and communication pattern that matches very well to the GPU features. Thus, an implementation of this algorithm is presented here for solving large problem sizes, i.e., larger than CUDA GPU's shared memory capacity, in a Multiple-GPU environment. Also, small and medium problem sizes can take advantage of this implementation. Finally, this proposal has been tuned in order to obtain the maximum performance, resulting in a compact implementation that outperforms the CUSPARSE library (6.33x).

Summary Optimization problems appear in many different applications in science and engineering. A large number of different algorithms have been proposed for solving them; however, there is no unique general optimization method that performs efficiently across a diverse set of problems. Thus, a multimethod optimization, in which different algorithms cooperate to outperform the results obtained by any of them in isolation, is a very appealing alternative. Besides, as real‐life optimization problems are becoming more and more challenging, the use of HPC techniques to implement these algorithms represents an effective strategy to speed up the time‐to‐solution. In addition, a parallel multimethod approach can benefit from the effortless access to q large number of distributed resources facilitated by cloud computing. In this paper, we propose a self‐adaptive cooperative parallel multimethod for global optimization. This proposal aims to perform a thorough exploration of the solution space by means of multiple concurrent executions of a broad range of search strategies. For its evaluation, we consider an extremely challenging case‐study from the field of computational systems biology. We also assess the performance of the proposal on a public cloud, demonstrating both the potential of the multimethod approach and the opportunity that the cloud provides for these problems.

Summary The rise of heterogeneous systems has given place to great challenges for users as they involve new concepts, restrictions, and frameworks. Their exploitation is further complicated in the context of distributed memory systems, which require the usage of additional different programming paradigms and tools. In this paper, we propose a novel approach to program heterogeneous clusters that is based on high‐level abstractions such as tiles and hierarchical decomposition combined with the powerful APIs that data types and embedded languages can provide in languages such as C++. Rather than building our proposal from scratch, we have implemented it as a natural integration of the existing Hierarchically Tiled Arrays (HTA) and Heterogeneous Programming Library (HPL) projects, ie, the first one being focused on distributed computing and the second one on heterogeneous processing. The result, called Heterogeneous Hierarchically Tiled Arrays (H2TA), is very intuitive and easy to use thanks to the global view of the data and the single‐threaded view of the execution that it provides at cluster level together with the transparency it provides with respect to the management of the heterogeneous devices. An evaluation comparing our proposal with MPI‐based implementations shows its large programmability advantages and the reasonable overhead incurred.

Current Graphics Processing Units (GPUs) are capable of obtaining high computational performance in scientific applications. Nevertheless, programmers have to use suitable parallel algorithms for these architectures and usually have to consider optimization techniques in the implementation in order to achieve said performance. There are many efficient proposals for limited-size problems which fit directly in the shared memory of CUDA GPUs, however, there are few GPU proposals that tackle the design of efficient algorithms for large problem sizes that exceed shared memory storage capacity. In this work, we present a tuning strategy that addresses this problem for some parallel prefix algorithms that can be represented according to a set of common permutations of the digits of each of its element indices [1], denoted as Index-Digit (ID) algorithms. Specifically, our strategy has been applied to develop flexible Multi-Stage (MS) algorithms for the Fast Fourier Transform (FFT) algorithm (MS-ID-FFT) and a tridiagonal system solver (MS-ID-TS) on the GPU. The resulting implementation is compact and outperforms other well-known and commonly used state-of-the-art libraries, with an improvement of up to 1.47x with respect to NVIDIA's complex CUFFT, and up to 33.2x in comparison with NVIDIA's CUSPARSE for real data tridiagonal systems.

Systems biology is an emerging approach focused in generating new knowledge about complex biological systems by combining experimental data with mathematical modeling and advanced computational techniques. Many problems in this field are extremely challenging and require substantial supercomputing resources to be solved. This is the case of parameter estimation in large-scale nonlinear dynamic systems biology models. Recently, Cloud Computing has emerged as a new paradigm for on-demand delivery of computing resources. However, scientific computing community has been quite hesitant in using the Cloud, simply because traditional programming models do not fit well with the new paradigm, and the earliest cloud programming models do not allow most scientific computations being efficiently run in the Cloud. In this paper we explore and compare two distributed computing models: the MPI (message-passing interface) model, that is high-performance oriented, and the Spark model, which is throughput oriented but outperforms other cloud programming solutions adding improved support for iterative algorithms through in-memory computing. The performance of a very well known metaheuristic, the Differential Evolution algorithm, has been thoroughly assessed using a challenging parameter estimation problem from the domain of computational systems biology. The experiments have been carried out both in a local cluster and in the Microsoft Azure public cloud, allowing performance and cost evaluation for both infrastructures.

BACKGROUND: The development of large-scale kinetic models is one of the current key issues in computational systems biology and bioinformatics. Here we consider the problem of parameter estimation in nonlinear dynamic models. Global optimization methods can be used to solve this type of problems but the associated computational cost is very large. Moreover, many of these methods need the tuning of a number of adjustable search parameters, requiring a number of initial exploratory runs and therefore further increasing the computation times. Here we present a novel parallel method, self-adaptive cooperative enhanced scatter search (saCeSS), to accelerate the solution of this class of problems. The method is based on the scatter search optimization metaheuristic and incorporates several key new mechanisms: (i) asynchronous cooperation between parallel processes, (ii) coarse and fine-grained parallelism, and (iii) self-tuning strategies. RESULTS: The performance and robustness of saCeSS is illustrated by solving a set of challenging parameter estimation problems, including medium and large-scale kinetic models of the bacterium E. coli, bakerés yeast S. cerevisiae, the vinegar fly D. melanogaster, Chinese Hamster Ovary cells, and a generic signal transduction network. The results consistently show that saCeSS is a robust and efficient method, allowing very significant reduction of computation times with respect to several previous state of the art methods (from days to minutes, in several cases) even when only a small number of processors is used. CONCLUSIONS: The new parallel cooperative method presented here allows the solution of medium and large scale parameter estimation problems in reasonable computation times and with small hardware requirements. Further, the method includes self-tuning mechanisms which facilitate its use by non-experts. We believe that this new method can play a key role in the development of large-scale and even whole-cell dynamic models.

Summary Stencil computations are very common in scientific codes. Heterogeneous systems achieve good results solving these problems, but their programming is complex because of the ghost regions required in multi‐device implementations and the difficulty to properly exploit their hardware. The Heterogeneous Programming Library (HPL) is a recent framework that improves the programmability of heterogeneous devices. This paper describes two extensions of HPL focused on stencil computations. The first one allows to automatically update the ghost regions they involve. The second one automates the implementation of the computational kernels of these algorithms. In our evaluation, the first mechanism reduces on average the number of lines of code and the Halstead programming effort of the host code of comparable HPL baselines by 34% and 64.2%, respectively, while the second contribution reduces these metrics by 72% and 79% in the computational kernels, respectively. Also, the first technique has negligible performance overheads, while the second one matches the performance of manually developed kernels. As an added benefit, the facilitation of the development of these codes thanks to these techniques helps programmers experiment with optimizations suited for this applications such as the ghost cell expansion technique, which provides speedups of up to 13% in our experiments.

The advent of cloud computing technologies, which dynamically provide on-demand access to computational resources over the Internet, is offering new possibilities to many scientists and researchers. Nowadays, Infrastructure as a Service (IaaS) cloud providers can offset the increasing processing requirements of data-intensive computing applications, becoming an emerging alternative to traditional servers and clusters. In this paper, a comprehensive study of the leading public IaaS cloud platform, Amazon EC2, has been conducted in order to assess its suitability for data-intensive computing. One of the key contributions of this work is the analysis of the storage-optimized family of EC2 instances. Furthermore, this study presents a detailed analysis of both performance and cost metrics. More specifically, multiple experiments have been carried out to analyze the full I/O software stack, ranging from the low-level storage devices and cluster file systems up to real-world applications using representative data-intensive parallel codes and MapReduce-based workloads. The analysis of the experimental results has shown that data-intensive applications can benefit from tailored EC2-based virtual clusters, enabling users to obtain the highest performance and cost-effectiveness in the cloud.

Modern graphics processing units (GPUs) offer very high computing power at relatively low cost. Nevertheless, designing efficient algorithms for the GPUs normally requires additional time and effort, even for experienced programmers. In this work we present a tuning methodology that allows the design for CUDA-enabled GPU architectures of index-digit algorithms, that is, algorithms where the data movement can be described as the permutations of the digits comprising the indices of the data elements. This methodology, based on two-stages identified as GPU resource analysis and operators string manipulation, is applied to FFT and tridiagonal systems solver algorithms, analyzing the performance features and the most adequate solutions. The resulting implementation is compact and outperforms other well-known and commonly used state-of-the-art libraries, with an improvement of up to 19.2 percent over NVIDIA's complex CUFFT , and more than 3000 percent over the NVIDIA'sCUDPP for real data tridiagonal systems.

Modern GPUs (Graphics Processing Units) offer very high computing power at relatively low cost. Nevertheless, designing efficient algorithms for the GPUs usually requires additional time and effort, even for experienced programmers. On the other hand, tridiagonal systems solvers are an important building block for a wide range of applications. In this paper, we present a new tuning parallel proposal in order to generate new tridiagonal systems solvers. This proposal is based on the combination of a new reduction algorithm (Redundant Reduction-RR) with a tuning proposal to generate efficient parallel prefix algorithms on the GPU. Specifically, we present two new solvers combining RR with two GPU efficient parallel prefix patterns. The performance of the resulting proposals was analyzed using three different CUDA GPUs, obtaining an improvement of up to 20.5x over the CUSPARSE library and 28.9x over CUDPP.

The eruption of multicore processors and several kinds of accelerators has generalized the interest in parallel programming. The OpenCL standard is very appealing because it provides code portability across most of these platforms. It defines a programming model where a host code requests the execution of kernels in computational devices. Unfortunately, the host application programming interface of OpenCL is quite verbose, which makes the development of its host code tedious and error-prone. More importantly, OpenCL does not provide automatic performance portability. As a result, users have to hand-tune OpenCL codes for each specific device, which implies trying different versions of the kernels and task partition granularities. As an answer to this situation, we present OCLoptimizer, a tool that automatically generates host codes and optimizes OpenCL kernels for each specific target device based on a user provided configuration file. This configuration file describes basic kernel characteristics and annotations in the kernels that indicate the code transformations to test. Our tool can explore different granularities for the problem decomposition as well as different alternatives for the kernel. This exploration is performed by means of an iterative optimization process whose parameters and search strategy are defined by the user specifications. Support for OpenCL codes composed of multiple kernels is also provided by the tool. Experiments performed on multicore CPUs and different accelerators show that the tool is very effective, generating codes with an average speedup of 2.54 with respect to baseline hand-tuned implementations, in single kernel codes and 1.79 in a code with multiple kernels.

Summary Providing high‐performance inter‐node communication is a key capability for running high performance computing applications efficiently on parallel architectures. In fact, current systems deployments are aggregating a significant number of cores interconnected via advanced networking hardware with Remote Direct Memory Access (RDMA) mechanisms, that enable zero‐copy and kernel‐bypass features. The use of Java for parallel programming is becoming more promising thanks to some useful characteristics of this language, particularly its built‐in multithreading support, portability, easy‐to‐learn properties, and high productivity, along with the continuous increase in the performance of the Java virtual machine. However, current parallel Java applications generally suffer from inefficient communication middleware, mainly based on protocols with high communication overhead that do not take full advantage of RDMA‐enabled networks. This paper presents efficient low‐level Java communication devices that overcome these constraints by fully exploiting the underlying RDMA hardware, providing low‐latency and high‐bandwidth communications for parallel Java applications. The performance evaluation conducted on representative RDMA networks and parallel systems has shown significant point‐to‐point performance increases compared with previous Java communication middleware, allowing to obtain up to 40% improvement in application‐level performance on 4096 cores of a Cray XE6 supercomputer. Copyright © 2015 John Wiley & Sons, Ltd.

Current GPUs (Graphics Processing Units) offer high computational power at relatively low cost, nonetheless, this enhanced performance often comes at the expenses of flexibility and code complexity. Efficient GPU programming requires detailed knowledge on certain hardware aspects. The scan operator is an important building block for a wide range of algorithms. In this paper, we present a number of parallel scan methods based on the traditional cyclic reduction tridiagonal solver and the Ladner-Fischer parallel prefix adder. Futhermore, we analyze a set of new features introduced in the Kepler Nvidia architecture such as read-only data cache and shuffle instructions. Our methods provide an excellent performance in many cases, up to 48% improvement over the CUDA Data Parallel Primitives (CUDPP) library.

Multicore cache hierarchies: design and programmability issuesWelcome to this special issue of the journal Concurrency and Computation: Practice and Experience on Multicore Cache Hierachies -Design and Programmability Issues, which contains three original manuscripts.Caches have been playing an essential role in the performance of single-core systems due to the gap between processor speed and main memory latency.First level caches are strongly restricted by their access time but current processors are able to hide most of their latency using outof-order execution as well as miss overlapping techniques.On the other hand, last levels of the cache memory hierarchy are not so dependable on their access time but on their locality issues.The locality in lower levels is filtered by the upper levels.As requests going down in the memory hierarchy, they require a greater number of cycles to be satisfied, so it becomes more difficult to hide the latency of last-level caches.In multicore systems, their importance is even larger due to the growing number of cores that share the bandwidth that this memory can provide.In an attempt to make a more efficient usage of their caches, the memory hierarchies of many chip multiprocessors present last-level caches, which can be allocated across threads and part of them may be private to a thread while other parts may be shared by multiple threads.Then, caching techniques will continue their evolution during next years in order to tackle the new challenges imposed by multicore platforms and workloads.A clear indicator of the current interest of the research community in new techniques for optimizing the performance and power consumption of multicore cache hierarchies is the organization during last years of specific sessions devoted to these topics at top international conferences on computer architecture and parallel computing.This special issue contributes to this promising field with extended and carefully reviewed versions of selected papers first from the International Workshop on Multicore Cache Hierachies -Design and Programmability Issues, which was held as part of the 10th IEEE International Symposium on Parallel and Distributed Processing with Applications (ISPA 2012) in Madrid (Spain), and second from all the community in the field as the Call for Papers was also open to contributions that were not sent to the mentioned workshop.The first contribution, by O. G. Lorenzo et al. [1], presents a set of three hardware counter (HC)-based tools to characterize memory access of parallel codes in symmetric multiprocessors.This toolkit simplifies accessing and programming HCs, which are included in modern microprocessors.Hardware counters are used to obtain information about memory accesses in a parallel code at very low cost.This information is presented to the user in a friendly way.The first tool can be used to automatically monitor the memory accesses of a system and to analyze a code even if the source is not available.The second tool allows the user to insert in a source code, in a simple and transparent way, the instructions needed to monitor and manage HCs, so specific parts of the code can be analyzed.The third tool takes the information gathered by the aforementioned tools, processes it and displays it graphically, allowing the user to adjust the level of detail.The aim of these tools is to characterize the memory accesses of parallel codes in multicore systems, in which the cache hierarchy can greatly influence the performance.Cache coherence techniques have been introduced to enable fast access while preserving the data coherence but these coherence protocols are critical in hard real-time systems.Because the frequent inter-cache communication leads to unpredictable interferences between the cores, the system's timing behavior is hard to analyze.Pyka et al. [2] propose a new hard real-time capable strategy for multicore systems called on-demand coherent cache (ODC 2 ).The technique is based on marginal hardware extensions compared to non-coherent caches and the use of common synchronization techniques.ODC 2 provides coherent accesses to cached shared data as well as caching of private data.Because the presented strategy does not induce interferences between local caches, ODC 2 is capable for hard real-time systems.

SUMMARY Two of the main sources of inefficiency in current caches are the non‐uniform distribution of the memory accesses across the cache sets, which causes misses due to the mapping restrictions of non fully associative caches and the access patterns with little locality that degrade the performance of caches under the traditional least recently used. replacement policy. This paper proposes a technique to tackle in a coordinated way both kinds of problems in the context of chip multiprocessors, whose last level caches can be shared by threads with different patterns of locality. Our proposal, called thread‐aware mapping and replacement miss reduction (TAMR2) policy, tracks the behavior of each thread in each set in order to decide the appropriate combination of policies to deal with these problems. Despite its small overhead, TAMR2 achieved in our experiments average power consumption and memory latency reductions of 10% and 12%, respectively, resulting in an average throughput improvement of 5.6%, relative to a traditional cache design using four cores. TAMR2 also outperformed many recent related approaches in the field. Copyright © 2013 John Wiley & Sons, Ltd.

In order to increase the efficiency of existing software many works are incorporating GPU processing. However, despite the current advances in GPU languages and tools, taking advantage of their parallel architecture is still far more complex than programming standard multi-core CPUs. Performance profiling and analysis of known applications provides a useful insight of the hardware architecture and memory hierarchy. Afterwards, this analysis can be used to identify potential bottlenecks and tune other software so it can make a more efficient usage of the available resources. In this work we implement a small signal processing library which will be used to characterize the performance of most recent NVIDIA GPU architectures. The methodology used in our signal processing library is based on a series of building blocks that enable us to easily design several well-known algorithms with little effort. The library was built paying special attention to flexibility and adaptability. In this work we also show how a generic approach can be used to easily design these GPU algorithms while obtaining competitive performance, which results specially interesting from the productivity standpoint.

This paper presents smdev, a shared memory communication middleware for multi-core systems. smdev provides a simple and powerful messaging application program interface that is able to exploit the underlying multi-core architecture replacing inter-process and network-based communications by threads and shared memory transfers. The performance evaluation of smdev on several multi-core systems has shown noticeable improvements compared with other Java shared memory solutions, reaching and even overcoming the performance of natively compiled libraries. Thus, smdev has obtained start-up latencies around 0.76 μs and almost 90 Gbps bandwidth for point-to-point communications, as well as high performance and scalability both for collective operations and representative messaging kernels. This fact has motivated the integration of smdev in F-MPJ, our message-passing implementation in Java.

SUMMARY This special issue contributes to this promising field with extended and carefully reviewed versions of selected papers from two workshops, namely the 2nd Minisymposium on GPU Computing, which was held as part of the 9th International Conference on Parallel Processing and Applied Mathematics (PPAM 2011) in Torun (Poland); and the Workshop on Exploitation of Hardware Accelerators (WEHA 2011), which was held in conjunction with The 2011 International Conference on High Performance Computing & Simulation in Istanbul (Turkey). Copyright © 2012 John Wiley & Sons, Ltd.

SUMMARY Cloud computing is offering new approaches for High Performance Computing (HPC) as it provides dynamically scalable resources as a service over the Internet. In addition, General‐Purpose computation on Graphical Processing Units (GPGPU) has gained much attention from scientific computing in multiple domains, thus becoming an important programming model in HPC. Compute Unified Device Architecture (CUDA) has been established as a popular programming model for GPGPUs, removing the need for using the graphics APIs for computing applications. Open Computing Language (OpenCL) is an emerging alternative not only for GPGPU but also for any parallel architecture. GPU clusters, usually programmed with a hybrid parallel paradigm mixing Message Passing Interface (MPI) with CUDA/OpenCL, are currently gaining high popularity. Therefore, cloud providers are deploying clusters with multiple GPUs per node and high‐speed network interconnects in order to make them a feasible option for HPC as a Service (HPCaaS). This paper evaluates GPGPU for high performance cloud computing on a public cloud computing infrastructure, Amazon EC2 Cluster GPU Instances (CGI), equipped with NVIDIA Tesla GPUs and a 10 Gigabit Ethernet network. The analysis of the results, obtained using up to 64 GPUs and 256‐processor cores, has shown that GPGPU is a viable option for high performance cloud computing despite the significant impact that virtualized environments still have on network overhead, which still hampers the adoption of GPGPU communication‐intensive applications. Copyright © 2012 John Wiley & Sons, Ltd.

SUMMARY This work presents cost‐effective multi‐graphics processing unit (GPU) parallel implementations of a finite‐volume numerical scheme for solving pollutant transport problems in bidimensional domains. The fluid is modeled by 2D shallow‐water equations, whereas the transport of pollutant is modeled by a transport equation. The 2D domain is discretized using a first‐order Roe finite‐volume scheme. Specifically, this paper presents multi‐GPU implementations of both a solution that exploits recomputation on the GPU and an optimized solution that is based on a ghost cell decoupling approach. Our multi‐GPU implementations have been optimized using nonblocking communications, overlapping communications and computations and the application of ghost cell expansion to minimize communications. The fastest one reached a speedup of 78 × using four GPUs on an InfiniBand network with respect to a parallel execution on a multicore CPU with six cores and two‐way hyperthreading per core. Such performance, measured using a realistic problem, enabled the calculation of solutions not only in real time but also in orders of magnitude faster than the simulated time.Copyright © 2012 John Wiley & Sons, Ltd.

First-level caches are usually split for both instructions and data instead of unifying them in a single cache. Although that approach eases the pipeline design and provides a simple way to independently treat data and instructions, its global hit rate is usually smaller than that of a unified cache. Furthermore, unified lower-level caches usually behave and process memory requests disregarding whether they are data or instruction requests. In this article, we propose a new technique aimed to balance the amount of space devoted to instructions and data for optimizing set-associative caches: the Virtually Split Cache or VSC. Our technique combines the sharing of resources from unified approaches with the bandwidth and parallelism that split configurations provide, thus reducing power consumption while not degrading performance. Our design dynamically adjusts cache resources devoted to instructions and data depending on their particular demand. Two VSC designs are proposed in order to track the instructions and data requirements. The Shadow Tag VSC (ST-VSC) is based on shadow tags that store the last evicted line related to data and instructions in order to determine how well the cache would work with one more way per set devoted to each kind. The Global Selector VSC (GS-VSC) uses a saturation counter that is updated every time a cache miss occurs either under an instruction or data request applying a duel-like mechanism. Experiments with a variable and a fixed latency VSC show that ST-VSC and GS-VSC reduce on average the cache hierarchy power consumption by 29% and 24%, respectively, with respect to a standard baseline. As for performance, while the fixed latency designs virtually match the split baseline in a single-core system, a variable latency ST-VSC and GS-VSC increase the average IPC by 2.5% and 2%, respectively. In multicore systems, even the slower fixed latency ST-VSC and GS-VSC designs improve the baseline IPC by 3.1% and 2.5%, respectively, in a four-core system thanks to the reduction in the bandwidth demanded from the lower cache levels. This is in contrast with many techniques that trade performance degradation for power consumption reduction. VSC particularly benefits embedded processors with a single level of cache, where up to an average 9.2% IPC improvement is achieved. Interestingly, we also find that partitioning the LLC for instructions and data can improve performance around 2%.

Current Chip Multiprocessors (CMPs) consist of several cores, cache memories and interconnection networks in the same chip. Private last level cache (LLC) configurations assign a static portion of the LLC to each core. This provides lower latency and isolation, at the cost of depriving the system of the possibility of reassigning underutilized resources. A way of taking advantage of underutilized resources in other private LLCs in the same chip is to use the coherence mechanism to determine the state of those caches and spill lines to them. Also, it is well known that memory references are not uniformly distributed across the sets of a set-associative cache. Therefore, applying a uniform spilling policy to all the sets in a cache may not be the best option. This paper proposes Adaptive Set-Granular Cooperative Caching (ASCC), which measures the degree of stress of each set and performs spills between spiller and potential receiver sets, while it tackles capacity problems. Also, it adds a neutral state to prevent sets from being either spillers or receivers when it could be harmful. Furthermore, we propose Adaptive Variable-Granularity Cooperative Caching (AVGCC), which dynamically adjusts the granularity for applying these policies. Both techniques have a negligible storage overhead and can adapt to many core environments using scalable structures. AVGCC improved average performance by 7.8% and reduced average memory latency by 27% related to a traditional private LLC configuration in a 4-core CMP. Finally, we propose an extension of AVGCC to provide Quality of Service that increases the average performance gain to 8.1%.

Multicores are now the norm. Their cache hierarchy has often a last level shared cache. The performance of this shared cache during the execution of multithreaded applications depends on the parallelization scheme followed. For example, critical parameters for the performance of parallelized loops are the number of threads and the block size. The selection of the optimal scheme in a compiler can be guided using heuristics or the execution time. Heuristics can be imprecise, while an execution time guided search is very time-consuming. This paper shows the usage of an analytical model to predict the cache behavior of shared caches during the execution of multithreaded applications that have been parallelized at loop level. The model predicts the number of misses generated by a given code when different number of threads or block sizes are used. The execution time of the codes analyzed is highly correlated to the number of misses generated in the shared cache, thus, the prediction of the model is a powerful tool to select the best parallelization scheme for them.

SUMMARY The popularity of Partitioned Global Address Space (PGAS) languages has increased during the last years thanks to their high programmability and performance through an efficient exploitation of data locality, especially on hierarchical architectures such as multicore clusters. This paper describes UPCBLAS, a parallel numerical library for dense matrix computations using the PGAS Unified Parallel C language. The routines developed in UPCBLAS are built on top of sequential basic linear algebra subprograms functions and exploit the particularities of the PGAS paradigm, taking into account data locality in order to achieve a good performance. Furthermore, the routines implement other optimization techniques, several of them by automatically taking into account the hardware characteristics of the underlying systems on which they are executed. The library has been experimentally evaluated on a multicore supercomputer and compared with a message‐passing‐based parallel numerical library, demonstrating good scalability and efficiency. Copyright © 2012 John Wiley & Sons, Ltd.

Real-time systems are subject to timing constraints, whose upper bound is given by the Worst-Case Execution Time (WCET). Cache memory behavior is difficult to predict analytically and estimating a safe and precise worst-case value is even more challenging. The worst-case memory performance (WCMP) component of the WCET can only be estimated with the precise knowledge of the stream of data addresses accessed by the code, which is determined by the access patterns and the base addresses of the data structures accessed. The regularity of strided access patterns simplifies their analysis, as they are characterized by relatively few parameters, which are often available at compile time. Unfortunately codes may exhibit irregular access patterns, which are much more difficult to statically analyze. As for the base addresses of the data structures, they are not always available at compile-time for many reasons: stack variables, dynamically allocated memory, modules compiled separately, etc. This article addresses these problems by presenting a model that predicts an %safe and upper bound of the data cache performance for codes both with regular and irregular access patterns, which is valid for any possible base addresses of the data structures. The model analyzes irregular access patterns due to the presence of indirections in the code and it can provide two kinds of predictions: a safe hard boundary that is suitable for hard real-time systems and a soft boundary whose safeness is not guaranteed but which is valid most of the times. In fact, in all our experiments the number of misses was below the soft boundary predicted by the model. This turns this soft boundary prediction into a valuable tool, particularly for non and soft real-time systems, which tolerate a percentage of the runs exceeding their deadlines.

The up trend in the number of cores in cluster architectures underscores the need for scalable communication middleware on these systems. One of the strategies to take advantage of this increase in the available computational power is the use of efficient message-passing middleware for inter-node communications and thread-based shared memory transfers within each node. This paper presents a Java communication middleware that exploits hybrid shared/distributed memory architectures through the use of scalable Java NIO sockets for inter-node communications and multi-threading on shared memory. Thus, communication-intensive applications running on clusters of multi-core processors can take advantage of the use of this middleware. The performance of these codes generally relies on collective operations, such as broadcasting, scattering or gathering data, which have been optimized to make the most of these architectures. The evaluation of this middleware when relying on multi-core aware communication patterns has shown significant performance improvements both in collective operations and communication-intensive applications.

MapReduce is a powerful tool for processing large data sets used by many applications running in distributed environments. However, despite the increasing number of computationally intensive problems that require low-latency communications, the adoption of MapReduce in High Performance Computing (HPC) is still emerging. Here languages based on the Partitioned Global Address Space (PGAS) programming model have shown to be a good choice for implementing parallel applications, in order to take advantage of the increasing number of cores per node and the programmability benefits achieved by their global memory view, such as the transparent access to remote data. This paper presents the first PGAS-based MapReduce implementation that uses the Unified Parallel C (UPC) language, which (1) obtains programmability benefits in parallel programming, (2) offers advanced configuration options to define a customized load distribution for different codes, and (3) overcomes performance penalties and bottlenecks that have traditionally prevented the deployment of MapReduce applications in HPC. The performance evaluation of representative applications on shared and distributed memory environments assesses the scalability of the presented MapReduce framework, confirming its suitability.

Fast Fourier Transform (FFT) is a useful tool for applications requiring signal analysis and processing. However, its high computational cost requires efficient implementations, specially if real time applications are used, where response time is a decisive factor. Thus, the computational cost and wide application range that requires FFT transforms has motivated the research of efficient implementations. Recently, GPU computing is becoming more and more relevant because of their high computational power and low cost, but due to its novelty there is some lack of tools and libraries. In this paper we propose an efficient implementation of the FFT with AMD's Brook+ language. We describe several features and optimization strategies, analyzing the scalability and performance compared to other well-known existing solutions.

UNLABELLED: We have implemented a high-performance computing (HPC) version of ProtTest that can be executed in parallel in multicore desktops and clusters. This version, called ProtTest 3, includes new features and extended capabilities. AVAILABILITY: ProtTest 3 source code and binaries are freely available under GNU license for download from http://darwin.uvigo.es/software/prottest3, linked to a Mercurial repository at Bitbucket (https://bitbucket.org/). CONTACT: [email protected] SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

SUMMARY Since its release, the Java programming language has attracted considerable attention from the high‐performance computing (HPC) community because of its portability, high programming productivity, and built‐in multithreading and networking support. As a consequence, several initiatives have been taken to develop a high‐performance Java message‐passing library to program distributed memory architectures, such as clusters. The performance of Java message‐passing applications relies heavily on the communications performance. Thus, the design and implementation of low‐level communication devices that support message‐passing libraries is an important research issue in Java for HPC. MPJ Express is our Java message‐passing implementation for developing high‐performance parallel Java applications. Its public release currently contains three communication devices: the first one is built using the Java New Input/Output (NIO) package for the TCP/IP; the second one is specifically designed for the Myrinet Express library on Myrinet; and the third one supports thread‐based shared memory communications. Although these devices have been successfully deployed in many production environments, previous performance evaluations of MPJ Express suggest that the buffering layer, tightly coupled with these devices, incurs a certain degree of copying overhead, which represents one of the main performance penalties. This paper presents a more efficient Java message‐passing communications device, based on Java Input/Output sockets, that avoids this buffering overhead. Moreover, this device implements several strategies, both in the communication protocol and in the HPC hardware support, which optimizes Java message‐passing communications. In order to evaluate its benefits, this paper analyzes the performance of this device comparatively with other Java and native message‐passing libraries on various high‐speed networks, such as Gigabit Ethernet, Scalable Coherent Interface, Myrinet, and InfiniBand, as well as on a shared memory multicore scenario. The reported communication overhead reduction encourages the upcoming incorporation of this device in MPJ Express ( http://mpj‐express.org ). Copyright © 2011 John Wiley & Sons, Ltd.

The well-known memory wall problem has motivated wide research in the design of caches. Last-level caches, whose misses can stall the processors for hundreds of cycles, have received particular attention. Strategies to modify adaptably the cache insertion, promotion, eviction and even placement policies have been proposed, some techniques being better at reducing different kinds of misses. For example changes in the placement policy of a cache, which are a natural option to reduce conflict misses, can do little to fight capacity misses, which depend on the relation between the working set of the application and the cache size. Nevertheless, other techniques such as the recently proposed dynamic insertion policy (DIP), whose aim is to retain a fraction of the working set in the cache when it is larger than the cache size, attack primarily capacity misses. In this paper we present a coordinated strategy to reduce both capacity and conflict misses by changing the placement and insertion policies of the cache. Our strategy takes its decisions based on the concept of the Set Saturation Level (SSL), which tries to measure to which degree a set can hold its working set. Despite requiring only less than 1% storage overhead, our proposal, called Bimodal Set Balancing Cache, reduced the average miss rate of a baseline 2MB 8-way second level cache by 16%, which translated into an average IPC improvement of 4.8% in our experiments.

The hierarchical radiosity algorithm provides high-quality illumination and the view-independent results obtained can be re-employed for different camera positions. On the other hand, the utilization of multiresolution models is a common solution for the real-time rendering of complex scenes. In this case, the level of detail of each object depends on the specific camera position. Unfortunately, global illumination computations may present an important performance loss in this context. In this paper we present a new solution for hierarchical radiosity for multiresolution systems. Our proposal is based on the application of an enriched hierarchical radiosity algorithm to an input scene with low-resolution objects (represented by coarse meshes) and the efficient data management of the resulting values. The representation of the information we use permits the application of the radiosity values obtained for the coarse version of an object to finer resolution versions of that object. Results of our implementation show that our algorithm produces high-quality images with an important reduction in computational costs.

Abstract With the evolution of high‐performance computing toward heterogeneous, massively parallel systems, parallel applications have developed new checkpoint and restart necessities. Whether due to a failure in the execution or to a migration of the application processes to different machines, checkpointing tools must be able to operate in heterogeneous environments. However, some of the data manipulated by a parallel application are not truly portable. Examples of these include opaque state (e.g. data structures for communications support) or diversity of interfaces for a single feature (e.g. communications, I/O). Directly manipulating the underlyingad hocrepresentations renders checkpointing tools unable to work on different environments. Portable checkpointers usually work around portability issues at the cost of transparency: the user must provide information such as what data need to be stored, where to store them, or where to checkpoint. CPPC (ComPiler for Portable Checkpointing) is a checkpointing tool designed to feature both portability and transparency. It is made up of a library and a compiler. The CPPC library contains routines for variable level checkpointing, using portable code and protocols. The CPPC compiler helps to achieve transparency by relieving the user from time‐consuming tasks, such as data flow and communications analyses and adding instrumentation code. This paper covers both the operation of the CPPC library and its compiler support. Experimental results using benchmarks and large‐scale real applications are included, demonstrating usability, efficiency, and portability. Copyright © 2009 John Wiley & Sons, Ltd.

Real-time systems are subject to temporal constraints and require a schedulability analysis to ensure that task execution finishes within lower and upper specified bounds. Worst-case memory performance (WCMP) plays a key role in the calculation of the upper bound of the execution time. Data caches complicate the calculation of the WCMP, since their behavior is highly dependent on the sequence of memory addresses accessed, which is often not available. For example, the address of a data structure may not be available at compile-time, and it may change between different executions of the program. We present an analytical model that provides fast, safe and tight estimations of the WCMP component of the worst-case execution time, using no information about the data base addresses. The address-independent absolute WCMP for codes with references that follow the same access pattern can be very high with respect to the average behavior because those references may be aligned with respect to the cache, thus generating systematic interferences among them. Our model can also provide a tighter and safe estimation for the WCMP for these codes when the user avoids these alignments.

This paper presents our current research efforts on efficient Java communication libraries over InfiniBand. The use of Java for network communications still delivers insufficient performance and does not exploit the performance and other special capabilities (RDMA and QoS) of high-speed networks, especially for this interconnect. In order to increase its Java communication performance, InfiniBand has been supported in our high performance sockets implementation, Java Fast Sockets (JFS), and it has been greatly improved the efficiency of Java Direct InfiniBand (Jdib), our low-level communication layer, enabling zero-copy RDMA capability in Java. According to our experimental results, Java communication performance has been improved significantly, reducing start-up latencies from 34 mus down to 12 and 7 mus for JFS and Jdib, respectively, whereas peak bandwidth has been increased from 0.78 Gbps sending serialized data up to 6.7 and 11.2 Gbps for JFS and Jdib, respectively. Finally, it has been analyzed the impact of these communication improvements on parallel Java applications, obtaining significant speedup increases of up to one order of magnitude on 128 cores.

Unified Parallel C (UPC) is an extension of ANSI C designed for parallel programming. UPC collective primitives, which are part of the UPC standard, increase programming productivity while reducing the communication overhead. This paper presents an up-to-date performance evaluation of two publicly available UPC collective implementations on three scenarios: shared, distributed, and hybrid shared/distributed memory architectures. The characterization of the throughput of collective primitives is useful for increasing performance through the runtime selection of the appropriate primitive implementation, which depends on the message size and the memory architecture, as well as to detect inefficient implementations. In fact, based on the analysis of the UPC collectives performance, we proposed some optimizations for the current UPC collective libraries. We have also compared the performance of the UPC collective primitives and their MPI counterparts, showing that there is room for improvement. Finally, this paper concludes with an analysis of the influence of the performance of the UPC collectives on a representative communication-intensive application, showing that their optimization is highly important for UPC scalability.

Efficient memory hierarchy design is critical due to the increasing gap between the speed of the processors and the memory. One of the sources of inefficiency in current caches is the non-uniform distribution of the memory accesses on the cache sets. Its consequence is that while some cache sets may have working sets that are far from fitting in them, other sets may be underutilized because their working set has fewer lines than the set. In this paper we present a technique that aims to balance the pressure on the cache sets by detecting when it may be beneficial to associate sets, displacing lines from stressed sets to underutilized ones. This new technique, called Set Balancing Cache or SBC, achieved an average reduction of 13% in the miss rate of ten benchmarks from the SPEC CPU2006 suite, resulting in an average IPC improvement of 5%.

Java is a valuable and emerging alternative for the development of parallel applications, thanks to the availability of several Java message-passing libraries and its full multithreading support. The combination of both shared and distributed memory programming is an interesting option for parallel programming multi-core systems. However, the concerns about Java performance are hindering its adoption in this field, although it is difficult to evaluate accurately its performance due to the lack of standard benchmarks in Java. This paper presents NPB-MPJ, the first extensive implementation of the NAS Parallel Benchmarks (NPB), the standard parallel benchmark suite, for Message-Passing in Java (MPJ) libraries. Together with the design and implementation details of NPB-MPJ, this paper gathers several optimization techniques that can serve as a guide for the development of more efficient Java applications for High Performance Computing (HPC). NPB-MPJ has been used in the performance evaluation of Java against C/Fortran parallel libraries on two representative multi-core clusters. Thus, NPB-MPJ provides an up-to-date snapshot of MPJ performance, whose comparative analysis of current Java and native parallel solutions confirms that MPJ is an alternative for parallel programming multi-core systems.

Physically-based illumination is an essential factor for realistic rendering. In this context, hierarchical radiosity is one of the most accurate global illumination methods. One of the key features of the radiosity approach is that it obtains view-independent global illumination results. Unfortunately, global illumination has high computational and memory requirements, and hierarchical radiosity, though more efficient than other radiosity solutions, is not an exception. The progressive popularization of multiprocessor and multi-core processor systems makes the design and implementation of efficient parallel algorithms an appealing alternative in this field. In this paper we present a novel parallel radiosity method addressing the hierarchical radiosity computation on current homogeneous multi-core environments. One of the main contributions of our work is the use of different tasks to exploit the independent interactions among the geometric elements in the scene. Our parallel solution leads to a versatile radiosity implementation that takes advantage of the multiple computational resources in the system, such as multi-core processors and SMT (Simultaneous Multithreading) capabilities. Good results in terms of performance have been achieved.

While caches are essential to reduce execution time and power consumption, they complicate the estimation of the worst-case execution time (WCET), crucial for many real-time systems (RTS). Most research on static worst-case cache behavior prediction has focused on hard RTS, which need complete information on the access patterns and addresses of the data to guarantee the predicted WCET is a safe upper bound of any execution time. Access patterns are available in those codes that have a steady state of access patterns after the first iteration of a loop (in the following regular codes), however, the addresses of the data are not always known at compile time for many reasons: stack variables, dynamically allocated memory, modules compiled separately, etc. Even when available, their usefulness to predict cache behavior in systems with virtual memory decreases in the presence of physically-indexed caches. In this paper we present a model that predicts a reasonable bound of the worst-case behavior of data caches during the execution of regular codes without information on the base address of the data structures. In 99.7% of our tests the number of misses performed below the boundary predicted by the model. This turns the model into a valuable tool, particularly for non-RTS and soft RTS, which tolerate a percentage of the runs exceeding their deadlines.

The recognition of program constructs that are frequently used by software developers is a powerful mechanism for optimizing and parallelizing compilers to improve the performance of the object code. The development of techniques for automatic recognition of computational kernels such as inductions, reductions and array recurrences has been an intensive research area in the scope of compiler technology during the 90's. This article presents a new compiler framework that, unlike previous techniques that focus on specific and isolated kernels, recognizes a comprehensive collection of computational kernels that appear frequently in full-scale real applications. The XARK compiler operates on top of the Gated Single Assignment (GSA) form of a high-level intermediate representation (IR) of the source code. Recognition is carried out through a demand-driven analysis of this high-level IR at two different levels. First, the dependences between the statements that compose the strongly connected components (SCCs) of the data-dependence graph of the GSA form are analyzed. As a result of this intra-SCC analysis, the computational kernels corresponding to the execution of the statements of the SCCs are recognized. Second, the dependences between statements of different SCCs are examined in order to recognize more complex kernels that result from combining simpler kernels in the same code. Overall, the XARK compiler builds a hierarchical representation of the source code as kernels and dependence relationships between those kernels. This article describes in detail the collection of computational kernels recognized by the XARK compiler. Besides, the internals of the recognition algorithms are presented. The design of the algorithms enables to extend the recognition capabilities of XARK to cope with new kernels, and provides an advanced symbolic analysis framework to run other compiler techniques on demand. Finally, extensive experiments showing the effectiveness of XARK for a collection of benchmarks from different application domains are presented. In particular, the SparsKit-II library for the manipulation of sparse matrices, the Perfect benchmarks, the SPEC CPU2000 collection and the PLTMG package for solving elliptic partial differential equations are analyzed in detail.

The use of Java for parallel programming on clusters relies on the need of efficient communication middleware and high-speed cluster interconnect support. Nevertheless, currently there are no solutions that fully fulfill these issues. In this paper, a Java sockets library has been tailored to increase the efficiency of Java parallel applications on clusters. This library supports high-speed cluster interconnects and its API has been extended to meet the requirements of a high performance Java RMI implementation and Java parallel applications on clusters. Thus, it provides Java with a more efficient communication middleware on clusters. The performance evaluation of this middleware on a Gigabit Ethernet (GbE) and a scalable coherent interface (SCI) cluster has shown experimental evidence of throughput increase. Moreover, qualitative aspects of the solution such as transparency to the user, interoperability with other systems and no need of source code modifications are decisive to boost the performance of existing Java parallel applications and their developments in high performance Java cluster computing.

The running times of large-scale computational science and engineering parallel applications, executed on clusters or grid platforms, are usually longer than the mean-time-between-failures (MTBF). Hardware failures must be tolerated by the parallel applications to ensure that no all computation done is lost on machine failures. Checkpointing and rollback recovery is a very useful technique to implement fault-tolerant applications. Although extensive research has been carried out in this field, there are few available tools to help parallel programmers to enhance with fault tolerant capability their applications. This work presents two different approaches to endow with fault tolerance the MPI version of an air quality simulation. A segment-level solution has been implemented by means of the extension of a checkpointing library for sequential codes. A variable-level solution has been implemented manually in the code. The main differences between both approaches are portability, transparency-level and checkpointing overheads. Experimental results comparing both strategies on a cluster of PCs are shown in the paper

Nowadays, one of the most active areas of research in computer graphics is focused on improving the performance of global illumination methods. In this paper we present a new parallel method for hierarchical radiosity computation. Contrary to usual solutions in the literature our approach carries out an effective partitioning and distribution of the input geometry among the processors. Thus, the memory constraint is reduced when processing large scenes. The method presented in this paper also introduces a multi-thread scheduling to improve interaction between processors. This solution replaces the polling strategy usually used in parallel computing, when several independent tasks need to establish asynchronous communication. The great flexibility of our parallel implementation has been demonstrated by the good results achieved on a testbed with different computing systems and test scenes

Abstract The memory hierarchy plays an essential role in the performance of current computers, so good analysis tools that help in predicting and understanding its behavior are required. Analytical modeling is the ideal base for such tools if its traditional limitations in accuracy and scope of application can be overcome. While there has been extensive research on the modeling of codes with regular access patterns, less attention has been paid to codes with irregular patterns due to the increased difficulty in analyzing them. Nevertheless, many important applications exhibit this kind of pattern, and their lack of locality make them more cache‐demanding, which makes their study more relevant. The focus of this paper is the automation of the Probabilistic Miss Equations (PME) model, an analytical model of the cache behavior that provides fast and accurate predictions for codes with irregular access patterns. The information requirements of the PME model are defined and its integration in the XARK compiler, a research compiler oriented to automatic kernel recognition in scientific codes, is described. We show how to exploit the powerful information‐gathering capabilities provided by this compiler to allow the automated modeling of loop‐oriented scientific codes. Experimental results that validate the correctness of the automated PME model are also presented. Copyright © 2007 John Wiley & Sons, Ltd.

This special issue of Concurrency and Computation: Practice and Experience contains a selection of the papers presented at the 12th International Workshop on Compilers for Parallel Computers (CPC'2006), held in A Coruña, Spain, 9-11 January 2006.The CPC Workshop series is well established as an invitational workshop for leading research groups in the field (mainly from Europe, North America and Asia-Pacific) to provide a forum for exchanging and developing new ideas in compiler design for parallel systems and related topics.The Workshop series began in 1989 in Oxford, U.K., and continued every 18 months in a European city: Paris,

The performance of memory hierarchies, in which caches play an essential role, is critical in nowadays general-purpose and embedded computing systems because of the growing memory bottleneck problem. Unfortunately, cache behavior is very unstable and difficult to predict. This is particularly true in the presence of irregular access patterns, which exhibit little locality. Such patterns are very common, for example, in applications in which pointers or compressed sparse matrices give place to indirections. Nevertheless, cache behavior in the presence of irregular access patterns has not been widely studied. In this paper we present an extension of a systematic analytical modeling technique based on PMEs (probabilistic miss equations), previously developed by the authors, that allows the automated analysis of the cache behavior for codes with irregular access patterns resulting from indirections. The model generates very accurate predictions despite the irregularities and has very low computing requirements, being the first model that gathers these desirable characteristics that can automatically analyze this kind of codes. These properties enable this model to help drive compiler optimizations, as we show with an example.

This paper presents communication strategies for achieving efficient parallel and distributed Java applications on clusters with high-speed interconnects. Communication performance is critical for the overall cluster performance. Previous efforts at obtaining efficient Java communications have a limited applicability on high-speed interconnects as they are focused on high level APIs like RMI, ignoring the particularities of these systems and their native high performance communication protocols. By relying on a custom Java socket implementation higher degrees of performance can be achieved exploiting high-speed interconnect facilities. Several protocol definitions are presented, looking for obtaining high performance Java communications. Moreover, the quality of the protocol implementations and their design decisions has been thoroughly evaluated on a scalable coherent interface (SCI) and gigabit Ethernet (GbE) testbed cluster. The results of this analysis have demonstrated that these Java protocols obtain similar results to native communications

Summary form only given. The automatic parallelization of loops that contain complex computations is still a challenge for current parallelizing compilers. The main limitations are related to the analysis of expressions that contain subscripted subscripts, and the analysis of conditional statements that introduce complex control flows at run-time. We use the term complex loop to designate loops with such characteristics. We describe the parallelization of sequential complex loop nests using a generic compiler framework (proposed in an earlier paper [Arenaz et al., ICS'2003] ) that accomplishes kernel recognition through the analysis of the gated single assignment program representation. Specifically, we focus on an extension of this framework that enables its use as a powerful tool for gathering source code information that is relevant for the parallelization of each computational kernel. A set of example codes are analyzed in detail to illustrate the potential of our approach. Experimental results using a benchmark suite of complex loop nests are also presented.

The use of Java for parallel programming on clusters according to the message-passing paradigm is an attractive choice. In this case, the overall application performance will largely depend on the performance of the underlying Java message-passing library. This paper evaluates, models and compares the performance of MPI-like point-to-point and collective communication primitives from selected Java message-passing implementations on clusters with different interconnection networks. We have developed our own micro-benchmark suite to characterize the message-passing communication overhead and thus derive analytical latency models.

This paper presents a new approach for the detection of coarse-grain parallelism in loop nests that contain complex computations, including subscripted subscripts as well as conditional statements that introduce complex control flows at run-time. The approach is based on the recognition of the computational kernels calculated in a loop without considering the semantics of the code. The detection is carried out on top of the Gated Single Assignment (GSA) program representation at two different levels. First, the use-def chains between the statements that compose the strongly connected components (SCCs) of the GSA use-def chain graph are analyzed (intra-SCC analysis). As a result, the kernel computed in each SCC is recognized. Second, the use-def chains between statements of different SCCs are examined (inter-SCC analysis). This second abstraction level enables the detection of more complex computational kernels by the compiler. A prototype was implemented using the infrastructure provided by the Polaris compiler. Experimental results that show the effectiveness of our approach for the detection of coarse-grain parallelism in a suite of real codes are presented.

Land consolidation is a strategic instrument for rural planning and thus economic development in the Spanish region of Galicia. This paper describes an experimental system embedded in a GIS environment to aid rural engineers to develop land consolidation plans. The system supports all the stages of the plan and many functionalities are implemented as heuristic processes based on expert knowledge and advice. The overall aim is to overcome administrative and technical problems of traditional consolidation procedures. The system provides an integrated framework for the management of spatial and administrative consolidation information. It also includes optimization-based algorithms for the automated generation of multiple alternative parcel reallocations, as well as an environment to refine and objectively evaluate the proposed solutions. These key capabilities result in a powerful tool for decision making that dramatically reduces the time and cost of land consolidation plans. Pilot experiences in two consolidation zones of Galicia assess the feasibility and effectiveness of the system.

The increasing gap between processor and main memory speeds makes the role of the memory hierarchy behavior in the system performance essential. Both hardware and software techniques to improve this behavior require good analysis tools that help predict and understand such behavior. Analytical modeling arises as a good choice in this field due to its high speed if its traditional limited precision is overcome. We present a modular analytical modeling strategy for arbitrary set-associative caches with LRU replacement policy. The model differs from all the previous related works in its probabilistic approach. Both perfectly and nonperfectly nested loops as well as reuse between different nests are considered by this model, so it makes the analysis of complete programs with regular computations feasible. Moreover, the model achieves good levels of accuracy while being extremely fast and flexible enough to allow its extension. Our approach has been extensively validated using well-known benchmarks. Finally, the model has also proven its ability to drive code optimizations even more successfully than current production compilers.

The performance of the communication primitives of parallel computers is critical for the overall system performance. The characterization of the communication overhead is very important to estimate the global performance of parallel applications and to detect possible bottlenecks. In this paper, we evaluate, model and compare the performance of the message-passing libraries provided by the Fujitsu AP3000 multicomputer: MPI/AP, PVM/AP and APlib. Our aim is to fairly characterize the communication primitives using general models and performance metrics.

While much work has been devoted to the study of cache behavior during the execution of codes with regular access patterns, little attention has been paid to irregular codes. An important portion of these codes are scientific applications that handle compressed sparse matrices. In this work a probabilistic model for the prediction of the number of misses on a K-way associative cache memory considering sparse matrices with a uniform or banded distribution is presented. Two different irregular kernels are considered: the sparse matrix-vector product and the transposition of a sparse matrix. The model was validated with simulations on synthetic uniform matrices and banded matrices from the Harwell-Boeing collection. Keywords: Sparse matrix, irregular computation, cache performance, probabilistic model. 1 Introduction Sparse matrices are in the kernel of many numerical applications. Their compressed storage [2], which permits both operations and memory savings, generates irregular access ...

The Viterbi (1967) algorithm (VA) is known to be an efficient method for the realization of maximum-likelihood (ML) decoding of convolutional codes. The VA is characterized by a graph, called a trellis, which defines the transitions between states. To define an area efficient architecture for the VA is equivalent to obtaining an efficient mapping of the trellis. We present a methodology that permits the efficient hardware mapping of the VA onto a processor network of arbitrary size. This formal model is employed for the partitioning of the computations among an arbitrary number of processors in such a way that the data are recirculated, optimizing the use of the PEs and the communications. Therefore, the algorithm is mapped onto a column of processing elements and an optimal design solution is obtained for a particular set of area and/or speed constraints. Furthermore, the management of the surviving path memory for its mapping and distribution among the processors was studied. As a result, we obtain a regular and modular design appropriate for its VLSI implementation in which the only necessary communications between processors are the data recirculations between stages.

We present an unified parallel architecture for four of the most important fast orthogonal transforms with trigonometric kernel: Complex Valued Fourier (CFFT), Real Valued Fourier (RFFT), Hartley (FHT), and Cosine (FCT). Out of these, only the CFFT has a data flow coinciding with the one generated by the successive doubling method, which can be transformed on a constant geometry flow using perfect unshuffle or shuffle permutations. The other three require some type of hardware modification to guarantee the constant geometry of the successive doubling method. We have defined a generalized processing section (PS), based on a circular CORDIC rotator, for the four transforms. This PS section permits the evaluation of the CFFT and FCT transforms in n data recirculations and the RFFT and FHT transforms in n-1 data recirculations, with n being the number of stages of a transform of length N=r/sup n/. Also, the efficiency of the partitioned parallel architecture is optimum because there is no cycle loss in the systolic computation of all the butterflies for each of the four transforms.>

A semisystolic architecture is presented for the parallel calculation of the decimation in time and radix-2 fast Hartley transform (FHT) of a real sequence with N=2/sup n/ data items. The architecture is based on a constant geometry algorithm for computing the FHT which facilitates its mapping in VLSI technology and minimizes the communications among processors. The circuit proposed is characterized by its modular design and its interconnective regularity. It permits the computation of arbitrarily sized FHTs as a consequence of the partition of the data and the recirculation of partial results over the processing units in the successive stages of the transform. Each calculation stage requires N/4Q cycles where Q is the number of processors (Q=2/sup q/). The total calculation time is (Nlog/sub 2/N)/4Q cycles.>

This paper describes ACLE (Array C Language Emulator), a software package comprising an ACLAN-to-C translator and a library of simulation routines enabling the execution of programs written in ACLAN to be simulated on a conventional sequential computer. Array C LANguage (ACLAN) is a machine-independent programming language that extends C by endowing it with structures for programming array processors. ACLAN was successfully proven by developing many parallel algorithms for hypercube computers. An algorithmic solution for mapping algorithms onto these computers is explained.