Engineering for Performance in High Performance Computing; Bill Gropp, Director of the Parallel Computing Institute, University of Illinois Urbana-Champaign, USA

Achieving good performance on any system requires balancing many competing factors.  More than just minimizing communication (or floating point or memory motion), for high end systems the goal is to achieve the lowest cost solution.  And while cost is typically considered in terms of time to solution, other metrics, including total energy consumed, are likely to be important in the future.

Making effective use of the next generations of extreme scale systems requires rethinking the algorithms, the programming models, and the development process.  This talk will discuss these challenges and argue that performance modeling, combined with a more dynamic and adaptive style of programming, will be necessary for extreme scale systems.

Performance Engineering for Stencil Updates on Modern Processors; Jan Treibig (Friedrich-Alexander-Universität Erlangen-Nürnberg), Georg Hager (Friedrich-Alexander-Universität Erlangen-Nürnberg), Gerhard Wellein (Friedrich-Alexander-Universität Erlangen-Nürnberg)

We apply the recently introduced ECM (Execution-Cache-Memory) performance model for multicore processors on stencil- and stencil-like algorithms. ECM is an extension of the Roofline Model and allows a prediction of single-core performance and saturation properties of streaming codes on multicore chips. This leads to deeper insight into performance behavior and energy consumption and enables a model-guided performance engineering approach, in which the concept of "optimal performance" is well-defined. Case studies for several short- and long-range stencil codes are presented.

ppOpen-HPC: Open Source Infrastructure for Development and Execution of Large-Scale Scientific Applications on Post-Peta-Scale Supercomputers with Automatic Tuning (AT); Kengo Nakajima, Takahiro Katagiri, Masaki Satoh, Takashi Furumura, Hiroshi Okuda (The University of Tokyo), Takeshi Iwashita (Kyoto University), and Hide Sakaguchi (JAMSTEC)

In this presentation, recent achievements and progress of the "ppOpen-HPC" project are overviewed. Moreover, results of collaborations with users of ppOpen-HPC are also provided. ppOpen-HPC is an open source infrastructure for development and execution of optimized and reliable simulation code on post-peta-scale (pp) parallel computers based on many-core architectures, and it consists of various types of libraries, which cover general procedures for scientific computation. Source code developed on a PC with a single processor is linked with these libraries, and the parallel code generated is optimized for post-peta-scale systems. The target post-peta-scale system is the Post T2K System (http://www.cc.u-tokyo.ac.jp/support/press/SCD-ITC.pdf) of the University of Tokyo based on many-core architectures, such as Intel MIC/Xeon Phi. It will be installed in FY.2015-2016 and its peak performance is expected to be 20-30 PFLOPS. ppOpen-HPC supports approximately 2,000 users of the supercomputer system in the University of Tokyo, enabling them to switch from homogeneous multicore clusters to a post-peta-scale system based on many-core architectures. ppOpen-HPC is a five-year project (FY.2011-2015) supported by Japanese government (http://postpeta.jst.go.jp/en/). ppOpen-HPC is developed by the University of Tokyo (four departments), Kyoto University and JAMSTEC. The expertise of members covers a wide range of disciplines related to scientific computing, such as system software, numerical libraries/algorithms, computational mechanics, and earth sciences. ppOpen-HPC includes the four components, ppOpen-APPL, ppOpen-MATH, ppOpen-AT, and ppOpen-SYS. Libraries in ppOpen-APPL, ppOpen-MATH, and ppOpen-SYS are called from user's programs written in Fortran and C/C++ with MPI.

All issues related to hybrid parallel programming models are hidden from users by ppOpen-HPC. In ppOpen-HPC, we are focusing on five types of discretization methods for scientific computing, which are FEM, FDM, FVM, BEM, and DEM. ppOpen-APPL is a set of libraries covering various types of procedures for these five methods, such as parallel I/O of data-sets, assembling of coefficient matrix, linear-solvers with robust and scalable preconditioners, adaptive mesh refinement (AMR), and dynamic load-balancing. Each component should be developed based on existing practical application code. ppOpen-APPL provides common data structures and interfaces based on parallel netCDF, which will enable users to easily implement the procedures of ppOpen-HPC for legacy code. Automatic tuning (AT) enables a smooth and easy shift to further development on new/future architectures through the use of ppOpen-AT. Directive-based special AT languages for specific procedures in scientific computing, focused on optimum memory access, are being developed. ppOpen-AT automatically and adaptively generates optimum implementation for efficient memory accesses in the processes of methods for scientific computing in each component of ppOpen-APPL, such as explicit time marching procedures, matrix assembling procedures, and implicit linear solvers. And this is achieved in various environmental constraints such as the architecture of the supercomputer system, available resources, problem size, etc. ppOpen-AT will also optimize widely-used open-source applications and numerical libraries, such as OpenFOAM and PETSc. In the presentation, an example of application of ppOpen-AT on 3D FDM code of seismic simulations for Intel Xeon/Phi will be demonstrated. Finally, ppOpen-SYS consists of libraries related to node-to-node communication and fault-tolerance.

A roofline model of energy; Richard Vuduc (Georgia Tech)

Given a computation, how much time, energy, or power does it require? We sketch a first-principles model aimed at answering this question. We summarize a series of on-going experiments to validate and refine the model against measurement on a variety of real systems. We explore what the model implies about algorithmic time-energy tradeoffs, historical trends in architecture, and power capping, among other consequences.

Reproducible Experiments in High-Performance Computing: Techniques and Stencil Compiler Benchmark Study; Helmar Burkhart (University of Basel), Severin Gsponer (University of Basel), Danilo Guerrera (University of Basel), and Antonio Maffia (University of Basel)

For decades, experiments on parallel computers have been reported at conferences and in journals without the possibility to verify the results presented. Thus, one of the major principles of science, reproducible results as a kind of correctness proof, has been neglected in the field of experimental high-performance computing. While this is still the state-of-the-art, current research targets for solutions to this problem. Leading conferences more and more provide sessions or workshops on this topic (e.g. REPPAR’14 in conjunction with Euro-Par 2014).

In the first part of the lecture we will report on ongoing work elsewhere, as well as our own research activities. Recently we have defined a taxonomy of reproducibility which identifies different scenarios of increasing complexity. At the lower end (but still a challenge) is the fixed and local experiment that becomes repeatable from remote sites on the Internet, while at the other end of the spectrum both modifiable and portable experiment types can be identified. We will outline these and further scenarios and discuss the problems to be solved, which include both technical and legal aspects (e.g. program and data provenance issues).

The second part of the talk will provide practical experiences regarding reproducibility from a benchmark case study we did. In our experiments we explore the class of stencil calculations that are part of many scientific kernels. Because of the rather low arithmetic intensity, stencils are hard to optimize on many-cores, i.e. it is a challenge to optimize caches uses. Several stencil-specific compilers have been developed for simplifying the implementation process in parallel environments using different techniques. In our study, we compare three stencil compilers: PLUTO (polyhedral compilation approach), POCHOIR (cache-oblivious algorithm approach), and PATUS (autotuning approach). In order to make our experiments reproducible, a first prototype of a work-flow engine has been developed. We report both on the results of the study (relevant for scientists working with stencil applications), and the technical aspects of the engine (relevant for scientists that target for reproducible experiments).

We conclude with a discussion of future research activities envisaged.

Performance, power, and energy modeling and characterization of sparse matrix-vector multiplication on multicore architectures, A. Cristiano I. Malossi (IBM Research - Zurich), Yves Ineichen (IBM Research - Zurich), Costas Bekas (IBM Research - Zurich), Alessandro Curioni (IBM Research - Zurich), Enrique S. Quintana-Ortí (Universidad Jaime I)

While Moore's law is expected to remain valid for approximately one more decade, the end of Dennard scaling (i.e., the ability to shrink the feature size of integrated circuit technology while maintaining a constant power density), which partly motivated the transition to multicore architectures around 2004, is now pushing processor design towards ``dark silicon'' and, in consequence, heterogeneous systems. The scientific community, as responsible for a large fraction of the energy consumed in today's large-scale computing facilities, is not immune to these trends, and a number of research projects now place energy in par with performance among their goals, in a holistic effort for higher energy efficiency all the way from the hardware to the application software.

Along this line, optimizing the 7/13 ``dwarfs'', introduced by UC Berkeley in 2006, represents a challenge with a potential tremendous impact on a vast number of scientific/engineering applications and libraries, which are indeed composed of these computational blocks. However, without a careful modeling and a subsequent understanding of the phenomena, the optimization process of these kernels is doomed to fail.

In this talk we will analyze the interactions occurring in the performance-power-energy triangle for the sparse matrix-vector product (SpMV), a challenging kernel due to its indirect and irregular memory access pattern. SpMV constitutes the key ingredient of the sparse linear algebra dwarf, as well as for many iterative methods for the solution of linear systems arising in, e.g., boundary value problems, eigenvalue problems, finite element methods, economic modeling, web search, and information retrieval, among others.

In the first part of our analysis we will identify a set of few critical parameters that drive the performance and instantaneous power consumption of a baseline implementation of the SpMV. We will show the link between these parameters and the algorithmic and architecture features, and on top of them we will build a general classification of sparse matrices, which represents a tool to obtain an instantaneous qualitative indication of the performance-power-energy features of SpMV (i.e., a characterizations along these three magnitudes), based only on a few statistical information about the sparse matrix structure, and independent from the original problem.

In a second step, we will use a small synthetic sparse benchmark collection (the training set) to build a general model which is able to provide accurate quantitative estimations of performance-power-energy for any matrix. To prove the robustness of our methodology, we will test the model against the entire University of Florida Matrix Collection, run on two different high-end multithreaded architectures, representative of state-of-the-art multicore technology.

The model and classification presented here can impact large clusters and cloud systems, where the prediction of performance and energy consumption yields important benefits in terms of, e.g., optimal jobs scheduling and costs prediction, among others.

D-Stacked Logic-in-Memory Hardware For Sparse Matrix Operations; Franz Franchetti, Qiuling Zhu, Larry Pileggi (Department of Electrical and Computer Engineering, Carnegie Mellon University)

This paper introduces a 3D-stacked logic-in-memory (LiM) system to accelerate the processing of sparse matrix data that is held in a 3D DRAM system. We build a customized content addressable memory (CAM) hardware structure to exploit the inherent sparse data patterns and model the LiM based hardware accelerator layers that are stacked in between DRAM dies for the efficient sparse matrix operations. Through silicon vias (TSVs) are used to provide the required high inter-layer bandwidth. Furthermore, we adapt the algorithm and data structure to fully leverage the underlying hardware capabilities, and develop the necessary design framework to facilitate the design space evaluation and LiM hardware synthesis. Our simulation demonstrates more than two orders of magnitude of performance and energy efficiency improvements compared with the traditional multithreaded software implementation on modern processors.

Massively Parallel and near Linear Time Graph Analytics; Yves Ineichen, Costas Bekas, Alessandro Curioni (IBM Research - Zurich)

Over the years graph analytics has become a cornerstone for a wide variety of research areas and applications, and a respectable number of algorithms have been developed to extract knowledge from big and complex graphs. Unfortunately, the high complexity of these algorithms poses a severe restriction on the problem sizes. Indeed, in modern applications such as social or bio inspired networks, the demand to analyze larger and larger graphs now routinely range in the tens of millions and out-reaching to the billions in notable cases.

We believe that in the era of the big data regime accuracy has to be traded for algorithmic complexity and scalability to drive big data analytics. With this goal in mind we developed novel near linear (O(N)) methods for graph analytics. In this talk we will focus on two algorithms: estimating subgraph centralities (measure for the importance of a node), and spectrograms (density of eigenvalues) of the adjacency matrix of the graph. On one hand we discuss the underlaying mathematical models relaying on matrix trace estimation techniques. On the other hand we discuss the exhibited parallelism on multiple levels in order to attain good parallel efficiency on a large number of processes. To that end we explore the scalability of the proposed algorithms with benchmarks on huge datasets, e.g. the graph of the European street network containing 51 million nodes and 108 million non-zeros. Due to the iterative behavior of the methods, a very good estimate can be computed in a matter of seconds.

Both analytics have an immediate impact on visualizing and exploring large graphs arising in many fields.

Performance Prediction for Tensor Contractions; Paolo Bientinesi, Elmar Peise, Diego Fabregat, Edoardo Di Napoli (RWTH Aachen)

In many scientific disciplines, simulations rely on the fast contraction of tensors and matrices (a contraction is the generalization of the matrix product to tensors). Surprisingly, while matrix operations are thoroughly supported by highly optimized libraries, the domain of tensors is still sparsely populated. The contrast is staggering: On the one hand, GEMM---the matrix-matrix multiplication kernel---is possibly the most optimized routine in scientific computing; on the other hand, high-performance black-box libraries for high dimensional contractions are only recently starting to appear. Our research attempts to fill the gap, not by developing an actual tensor library---a ``tensor-BLAS''---but by identifying when and how a contraction among tensors of arbitrary dimension can be expressed, and therefore computed, in terms of the existing highly-efficient BLAS kernels.

In this talk, I first present a set of conditions to quickly determine whether a given contraction can be decomposed directly in terms of GEMM (with or without the help of a copying operation), or can only be computed via kernels from lower level BLAS. Then I will show how, due to the nature of tensors, one contraction can be decomposed in many ways, all mathematically equivalent, but significantly different in terms of performance; in order to guide the user among dozens of alternatives, we apply tools for performance modeling and prediction. Given a contraction, the objective is to identify and generate the fastest algorithm(s), without ever executing it.

The key insight is that tensor contractions typically rely only on one or two kernels, which are invoked a large number of times, always with operands of the same shape. We apply automatic tools that we developed to predict the performance of LAPACK-like algorithms: first, an automatic system constructs a database of piecewise multivariate polynomial models for BLAS kernels; then, by symbolic replacement, the execution of an algorithm is replaced with a sequence of queries to the database; finally, a composition step allows us to combine the BLAS models to obtain a prediction. In this talk, I illustrate how these techniques also successfully apply to tensor contractions.

Using Adaptive Sparse Grids to Solve High-Dimensional Dynamic Economic Models; Simon Scheidegger, Johannes Brumm (University of Zurich)

We present a flexible and scalable method to compute global solutions of high-dimensional stochastic dynamic economic models. Within a time-iteration setup, we interpolate policy functions using an adaptive sparse grid algorithm with piecewise multi-linear (hierarchical) basis functions. As the dimensionality increases, sparse grids grow considerably slower than standard tensor product grids. In addition, the grid scheme we use is automatically refined locally and can thus capture steep gradients or even non-differentiabilities. To further increase the maximum problem size we can handle, our implementation is fully hybrid parallel. This parallelization enables us to efficiently use high-performance computing architectures. 

High-Performance Implementation of High-Dimensional Quadrature for Bayesian Inverse Problems; Robert Gantner, Christoph Schwab (ETH Zurich)

We consider the Bayesian approach to inverse problems, specifically focussing on parametric PDE models. Such problems involve high- or possibly even infinite-dimensional integrals over a prior distribution, requiring dimension-adaptive methods and their high-performance implementation. We consider two methods for high-dimensional numerical quadrature: adaptive Smolyak quadrature and an integrand-adapted quasi-Monte Carlo method.

The convergence behavior in the number of quadrature points, as well as the computational efficiency in terms of parallel speedup of the two methods are compared by applying them to various problems, including a parametric diffusion equation. A comparison with naive Monte Carlo sampling shows their clear superiority in these cases.

This work is supported by the Swiss National Science Foundation (SNF) under project number 200021_149819 and by the European Research Council (ERC) under FP7 Grant AdG247277.

Entropy-stable space-time discontinuous Galerkin schemes for hyperbolic systems of conservation laws; Andreas Hiltebrand, Siddhartha Mishra (ETH Zurich)

We propose and analyse a space-time discontinuous Galerkin (DG) finite element method to approximate hyperbolic systems of conservation laws. Entropy stability is ensured by discretising the entropy variables and by using entropy-stable numerical fluxes. As we are interested in problems with shocks, we include a streamline diffusion and a shock-capturing term in the formulation to suppress spurious oscillations. The approximate solutions are shown to converge to an entropy measure valued solution for systems of conservation laws. At every time step, the discretisation corresponds to a big nonlinear system of algebraic equations for the degrees of freedom. A Newton-Krylov method is applied to solve these systems. To increase the efficiency, we consider and study several preconditioners. Various experiments show their performance and additionally demonstrate the robustness and the high-resolution properties of the scheme.