Scheduling languages express to a compiler—or equivalently, a code generator—a sequence of optimizations to apply. Performance tools that support a scheduling language interface allow exploration of optimizations, i.e., exploratory compilers . While scheduling languages have become a common feature of tools for experts, the proliferation of these languages without unifying common features may be confusing to users. Moreover, we recognize a need to organize the compiler developer community around common exploratory compiler infrastructure, and future advances to address, for example, data layout and data movement. To support a broader set of users may require raising the level of abstraction. This article provides a chronology of scheduling languages, discussing their origins in iterative compilation and autotuning, noting the common features that are used in existing frameworks, and calling for changes to increase their utility and portability.

We introduce a new scheduling language, based on the formalism of Multi-Dimensional Homomorphisms (MDH). In contrast to existing scheduling languages, our MDH-based language is designed to systematically "de-compose" computations for the memory and core hierarchies of architectures, and "re-compose" the computed intermediate results back to the final result -- we say "(de/re)-composition" for short. We argue that our scheduling langauge is easy to use and yet expressive enough to express well-performing (de/re)-compositions of popular related approaches, e.g., the TVM compiler, for MDH-supported computations (such as linear algebra routines and stencil computations). Moreover, our language is designed as auto-tunable, i.e., any optimization decision can optionally be left to the auto-tuning engine of our system, and our system can automatically recommend schedules for the user, based on its auto-tuning capabilities. Also, by relying on the MDH approach, we can formally guarantee the correctness of optimizations expressed in our language, thereby further enhancing user experience. Our experiments on GPU and CPU confirm that we can express optimizations that cannot be expressed straightforwardly (or at all) in TVM's scheduling language, thereby achieving higher performance than TVM, and also vendor libraries provided by NVIDIA and Intel, for time-intensive computations used in real-world deep learning neural networks.

Most of the existing distributed feature selection schemes neglect how good the subsets are that are mapped to the computational nodes, which causes a waste of time and hardware resources. A distributed integrated feature selection scheme (DIFS) with Subset Quality Evaluation (SQE) is proposed. SQE studies the relevance between the quality of a subset and the number of selected features from this subset, which helps shorten the feature selection time efficiently. We have given the implementation of our scheme for the Column Subset Selection (CSS) problem. We integrate a CSS algorithm in DIFS and information entropy as the SQE metric. We prove that the speedup of DIFS can reach m^3 compared to the centralized algorithm in ideal situations where m is the number of computational nodes, and give a well bounded approximation guarantee of the solution for CSS problem. Extensive experiments on eight data sets are used to verify the performance of scheme. Experiments results demonstrate the effectiveness of SQE and the impressive speedup DIFS can achieve. Although there is a slight increase of the reconstruction error value in some situations. Additional experiments of classification tasks reveal that the performance of DIFS is better than existing state-of-the-art distributed algorithms.

Projected and subspace clustering aim to find groups of similar objects within a subspace of the full-dimensional space. Where subspace clustering tries to identify clusters in all possible subspaces, projected clustering assigns each point to a single cluster within one projected subspace, resulting in a much smaller result set. PROCLUS is an adaptation of the k-medoids clustering algorithm, CLARANS, to projected clustering. Even though PROCLUS is the first projected clustering algorithm, it is still competitive in comparative empirical studies. PROCLUS is, however, still too slow for large-scale data or real-time interaction when used in information retrieval processes. Therefore, we propose novel algorithmic strategies to reduce computations and exploit the massive parallelism offered by modern graphical processing units (GPUs). To take advantage of their high degree of parallelism, standard sequential algorithms need to be significantly restructured. We therefore also propose a novel GPU-parallelized algorithm, GPU-FAST-PROCLUS, that takes advantage of the computational power of modern GPUs. We provide experimental studies that demonstrate the benefit of our proposed strategies and GPU-parallelizations. In this experimental evaluation, we obtain 3 orders of magnitude speedup compared to PROCLUS.

Heterogeneous computing mixes different devices, such as CPUs of different speeds, or systems with accelerators, e.g. a combination of CPUs and GPUs. The latter may improve the execution performance of complex applications by specialized device. The trade-off is an increased implementation complexity, also leading to more complex modelling. In this paper, Heterogeneous Graph Nodes (HGNs) are introduced to reduce the implementation complexity of modeling how to exploit heterogeneous environments. The HGNs proposed are an extension of the nodes used in Condensed Graphs (CG). CG are directed acyclic graphs which have shown to be an architecture-neutral modeling tool for expressing computational work-flows. Our proposed HGNs model the execution of a computational task on multiple compute devices. By always looking for the most optimized computation device, HGNs allow for reducing the execution time of the given task, as well as provides a modeling tool that minimizes the complexity of heterogeneous modelling and implementation. Our experiments confirm that combining HGNs and graph modeling may significantly reduce the overall execution time as well as the modeling and implementation complexity of workflows in heterogeneous distributed environments.

Building and successfully deploying applications on high-end heterogeneous resources such as GPUs, MICs or FPGAs, and typically with several library dependencies, is a complex task. Modern containerization provides a lightweight virtualization environment which can help solve some of these complex deployment and execution issues. By using containers, the software can be packaged with all the dependencies and tested in a single environment and deployable on heterogeneous architectures, easily. In this paper, we present our experiences with the container-based virtualized solutions that we developed for the use case applications in the EU H2020 project CloudLightning. We present specifics on their management and orchestration with specific software on the heterogeneous resources of our test-bed. The use cases include a Genomics application targeting FPGA-based DFEs, an Upscaling application for reservoir modeling, a ray tracing application targeting the MIC (Intel Xeon Phi co-processor), and a BLAS application with libraries, optimized for both CPU and GPU. An overview of the CloudLightning project and how the use case applications have been developed to be used as cloud services in the self-organizing, self-managing cloud technology, is also included.

Summary Applications written for heterogeneous CPU‐GPU systems often suffer from poor performance portability. Finding good work partitions can also be challenging as different devices are suited for different applications. This article describes ImageCL, a high‐level domain‐specific language and source‐to‐source compiler, targeting single system as well as distributed heterogeneous hardware. Initially targeting image processing algorithms, our framework now also handles general stencil‐based operations. It resembles OpenCL, but abstracts away performance optimization details which instead are handled by our source‐to‐source compiler. Machine learning‐based auto‐tuning is used to determine which optimizations to apply. For the distributed case, by measuring performance counters on a small input on one device, previously trained performance models are used to predict the throughput of the application on multiple different devices, making it possible to balance the load evenly. Models for the communication overhead are created in a similar fashion and used to predict the optimal number of nodes to use. ImageCL outperforms other state‐of‐the‐art solutions on image processing benchmarks in several cases, achieving speedups of up to 4.57×. On both CPUs and GPUs we are only 3% and 2% slower than an oracle for load balancing and scalability prediction, respectively, using synthetic benchmarks.

Summary Heterogeneous computing, combining devices with different architectures such as CPUs and GPUs, is rising in popularity and promises increased performance combined with reduced energy consumption. OpenCL has been proposed as a standard for programming such systems and offers functional portability. However, it suffers from poor performance portability, because applications must be retuned for every new device. In this paper, we use machine learning‐based auto‐tuning to address this problem. Benchmarks are run on a random subset of the tuning parameter spaces, and the results are used to build a machine learning‐based performance model. The model can then be used to find interesting subspaces for further search. We evaluate our method using five image processing benchmarks, with tuning parameter space sizes up to 2.3 M, using different input sizes, on several devices, including an Intel i7 4771 (Haswell) CPU, an Nvidia Tesla K40 GPU, and an AMD Radeon HD 7970 GPU. We compare different machine learning algorithms for the performance model. Our model achieves a mean relative error as low as 3.8% and is able to find solutions on average only 0.29% slower than the best configuration in some cases, evaluating less than 1.1% of the search space. The source code of our framework is available athttps://github.com/acelster/ML‐autotuning.

As clouds increase in size and as machines of different types are added to the infrastructure in order to\nmaximize performance and power efficiency, heterogeneous clouds are being created. However, exploiting\ndifferent architectures poses significant challenges. To efficiently access heterogeneous resources and, at the\nsame time, to exploit these resources to reduce application development effort, to make optimisations easier\nand to simplify service deployment, requires a re-evaluation of our approach to service delivery. We\npropose a novel cloud management and delivery architecture based on the principles of self-organisation\nand self-management that shifts the deployment and optimisation effort from the consumer to the software\nstack running on the cloud infrastructure. Our goal is to address inefficient use of resources and\nconsequently to deliver savings to the cloud provider and consumer in terms of reduced power consumption\nand improved service delivery, with hyperscale systems particularly in mind. The framework is general but\nalso endeavours to enable cloud services for high performance computing. Infrastructure-as-a-Service\nprovision is the primary use case, however, we posit that genomics, oil and gas exploration, and ray tracing\nare three downstream use cases that will benefit from the proposed architecture.

Segmentation of anatomical structures, from modalities like computed tomography (CT), magnetic resonance imaging (MRI) and ultrasound, is a key enabling technology for medical applications such as diagnostics, planning and guidance. More efficient implementations are necessary, as most segmentation methods are computationally expensive, and the amount of medical imaging data is growing. The increased programmability of graphic processing units (GPUs) in recent years have enabled their use in several areas. GPUs can solve large data parallel problems at a higher speed than the traditional CPU, while being more affordable and energy efficient than distributed systems. Furthermore, using a GPU enables concurrent visualization and interactive segmentation, where the user can help the algorithm to achieve a satisfactory result. This review investigates the use of GPUs to accelerate medical image segmentation methods. A set of criteria for efficient use of GPUs are defined and each segmentation method is rated accordingly. In addition, references to relevant GPU implementations and insight into GPU optimization are provided and discussed. The review concludes that most segmentation methods may benefit from GPU processing due to the methods' data parallel structure and high thread count. However, factors such as synchronization, branch divergence and memory usage can limit the speedup.

As the size of computational clusters grows, one can expect that I/O will consume an increasing portion of wall-clock time as the problem and node sizes are scaled up, unless parallel I/O is introduced. Unfortunately, using parallel I/O is non-trivial, so few applications developed by individual researchers enjoy its benefits. In this paper, we describe our novel method for analyzing I/O and communication operations at run-time. When nodes perform I/O or communication operations, our technique protects the memory associated with the requests from the application. Subsequent operations are analyzed for overlap between communication and I/O operations. When found, the I/O operation is automatically transformed, by our injected library, from an individual operation to a collective and shared MPI I/O operation. This allows users to benefit from parallel file systems without redesigning or recompiling their applications, and we demonstrate speedup for common usage patterns.

Fast bit-reversal algorithms have been of strong interest for many decades, especially after Cooley and Tukey introduced their FFT implementation in 1965. Many recent algorithms, including FFTW try to avoid the bit-reversal all together by doing in-place algorithms within their FFTs. We therefore motivate our work by showing that for FFTs of up to 65.536 points, a minimally tuned Cooley-Tukey FFT in C using our bit-reversal algorithm performs comparable or better than the default FFTW algorithm. In this paper, we present an extremely fast linear bit-reversal adapted for modern multithreaded architectures. Our bit-reversal algorithm takes advantage of recursive calls combined with the fact that it only generates pairs of indices for which the corresponding elements need to be exchanges, thereby avoiding any explicit tests. In addition we have implemented an adaptive approach which explores the trade-off between compile time and run-time work load. By generating look-up tables at compile time, our algorithm becomes even faster at run-time. Our results also show that by using more than one thread on tightly coupled architectures, further speed-up can be achieved.

Optimization algorithms are becoming increasingly more important in many areas, such as finance and engineering. Typically, real problems involve several hundreds of variables, and are subject to as many constraints. Several methods have been developed trying to reduce the theoretical time complexity. Nevertheless, when problems exceed reasonable sizes they end up being very computationally intensive. Heterogeneous systems composed by coupling commodity CPUs and GPUs are becoming relatively cheap, highly performing systems. Recent developments of GPGPU technologies give even more powerful control over them. In this paper, we show how we use a revised simplex algorithm for solving linear programming problems originally described by Dantzig for both our CPU and GPU implementations. Previously, this approach has showed not to scale beyond around 200 variables. However, by taking advantage of modern libraries such as ATLAS for matrix-matrix multiplication, and the NVIDIA CUDA programming library on recent GPUs, we show that we can scale to problem sizes up to at least 2000 variables in our experiments for both architectures. On the GPU, we also achieve an appreciable precision on large problems with thousands of variables and constraints while achieving between 2X and 2.5X speed-ups over the serial ATLAS-based CPU version. With further tuning of both the algorithm and its implementations, even better results should be achievable for both the CPU and GPU versions.

In 2006, John Mellor-Crummey and Michael Scott received the Dijkstra Prize in distributed computing for their 1991 paper on algorithms for scalable synchronization on shared memory multiprocessors, which included a novel spin-lock algorithm (a.k.a. MCS spin-lock) that carefully distributes spin locations in memory to lessen the impact of bandwidth limitations on spin algorithms. Their empirical work and architectural suggestions have had a major impact on how the field has viewed spin-locks. Motivated by emerging architectures with an increasing number of cores, we present an empirical study on recent shared memory architectures, including IBM P5+ and SGI ccNUMA systems. Our results show that latency will have a much greater impact on performance than bandwidth on these and future architectures with many cores and private caches. Several test cases and a tabular overview of our results are included.

A novel fast algorithm for computing a sequence of bit-reversed integers is presented. In finding a mapping function from a sequence of integers to a sequence of their bit-reverse, a recursive approach is taken to overcome the logarithmic factor burdening the standard scheme. The associated constant for the timing factor is shown to be very low even at the register level. The method generalizes to radix-r and mixed-radix cases and provides an efficient vectorizable scheme with the same low constant.>