Many scientific applications compute using sparse data and store that data in a variety of sparse formats because each format has unique space and performance benefits. Optimizing applications that use sparse data involves translating the sparse data into the chosen format and transforming the computation to iterate over that format. This paper presents a formal definition of sparse tensor formats and an automated approach to synthesize the transformation between formats. This approach is unique in that it supports ordering constraints not supported by other approaches and synthesizes the transformation code in a high-level intermediate representation suitable for applying composable transformations such as loop fusion and temporary storage reduction. We demonstrate that the synthesized code for COO to CSR with optimizations is 2.85x faster than TACO, Intel MKL, and SPARSKIT while the more complex COO to DIA is 1.4x slower than TACO but faster than SPARSKIT and Intel MKL using the geometric average of execution time.

Reproducibility plays an essential role in scientific research to ensure accuracy and serves as a foundation for future advancements. Scientific reproducibility becomes particularly challenging when dealing with vast amounts of input files that change hands or move across different laboratories or organizations. Preserving the provenance of data files ensures critical information about the originality of data files is captured to support the reproducibility of scientific research. The paper focuses on capturing and verifying input and output data file provenance using the principles of blockchain. The technique stores the hashes of data files in a database along with user and workflow information. It allows the workflow to verify the data against the hashes at any point. The method is demonstrated using Parflow, a Hydrologic model, as a proof-of-concept.

This article presents a code generator for sparse tensor contraction computations. It leverages a mathematical representation of loop nest computations in the sparse polyhedral framework (SPF), which extends the polyhedral model to support non-affine computations, such as those that arise in sparse tensors. SPF is extended to perform layout specification, optimization, and code generation of sparse tensor code: (1) We develop a polyhedral layout specification that decouples iteration spaces for layout and computation; and (2) we develop efficient co-iteration of sparse tensors by combining polyhedra scanning over the layout of one sparse tensor with the synthesis of code to find corresponding elements in other tensors through an SMT solver. We compare the generated code with that produced by a state-of-the-art tensor compiler, TACO. We achieve on average 1.63× faster parallel performance than TACO on sparse-sparse co-iteration and describe how to improve that to 2.72× average speedup by switching the find algorithms. We also demonstrate that decoupling iteration spaces of layout and computation enables additional layout and computation combinations to be supported.

Many important applications including machine learning, molecular dynamics, and computational fluid dynamics, use sparse data. Processing sparse data leads to non-affine loop bounds and frustrates the use of the polyhedral model for code transformation. The Sparse Polyhedral Framework (SPF) addresses limitations of the Polyhedral model by supporting non-affine constraints in sets and relations using uninterpreted functions. This work contributes an object-oriented API that wraps the SPF intermediate representation (IR) and integrates the Inspector/Executor Generation Library and Omega+ for precise set and relation manipulation and code generation. The result is a well-specified definition of a full computation using the SPF IR. The API provides a single entry point for tools to interact with the SPF, generate and manipulate polyhedral data flow graphs, and transform sparse applications.

Tensor computations present significant performance challenges that impact a wide spectrum of applications. Efforts on improving the performance of tensor computations include exploring data layout, execution scheduling, and parallelism in common tensor kernels. This work presents a benchmark suite for arbitrary-order sparse tensor kernels using state-of-the-art tensor formats: coordinate (COO) and hierarchical coordinate (HiCOO). It demonstrates a set of reference tensor kernel implementations and some observations on Intel CPUs and NVIDIA GPUs. The full paper can be referred to at http://arxiv.org/abs/2001.00660.

This poster introduces a compiler intermediate language designed for dataflow optimizations within a polyhedral framework. This intermediate representation describes computations at a high level, defines a set of loop and data transformations that can be applied, and provides visual feedback reflecting the expected effect of transformations on the performance model. Computations are represented as macro-dataflow graphs, with support for both regular and irregular scientific applications, including stencils and sparse linear algebra kernels. This layer provides optimizations such as loop transformations or temporary storage reductions. The multi-level intermediate representation enables this broad range of optimizations by allowing each layer to be transformed independently, while respecting dependences. The approach is evaluated on a computational fluid dynamics solver, sparse matrix-vector multiplication kernels, and the matrix-tensor Khatri-Rao product. The experimental results either outperform or are competitive with existing implementations.

AdaptLidarTools is a software package that processes full-waveform lidar data. Full-waveform lidar is an active remote sensing technique in which a laser beam is emitted towards a target and the backscattered energy is recorded as a near continuous waveform. A collection of waveforms from airborne lidar can capture landscape characteristics in three dimensions. Specific to vegetation, the extracted echoes and echo properties from the waveforms can provide scientists structural (height, volume, layers of canopy, among others) and functional (leaf area index, diversity) characteristics. The discrete waveforms can be transformed into georeferenced 2D rasters (images), allowing scientists to correlate field-based observations for validation of the waveform observations and fusing the data with other geospatial information. AdaptLidarTools provides an extensible, open-source framework that processes the waveforms and produces multiple data outputs that can be used in vegetation and terrain analysis. AdaptLidarTools is designed to explore new methods to fit full-waveform lidar signals and to maximize the information in the waveforms for vegetation applications. The toolkit explores first differencing, complementary to Gaussian fitting, for faster processing of full-waveform lidar signals and for handling increasingly large volumes of full-waveform lidar datasets. AdaptLidarTools takes approximately 30 min to derive a raster of a given echo property from a raw waveform file of 1 GB size. The toolkit generates first order echo properties such as position, amplitude, pulse width, and other properties such as rise time, fall time and backscattered cross section. It also generates other properties that current proprietary and open-source tools do not. The derived echo properties are delivered as georeferenced raster files of a given spatial resolution that can be viewed and processed by most remote sensing data processing software.

This paper presents a combined compile-time and runtime loop-carried dependence analysis of sparse matrix codes and evaluates its performance in the context of wavefront parallellism. Sparse computations incorporate indirect memory accesses such as x[col[j]] whose memory locations cannot be determined until runtime. The key contributions of this paper are two compile-time techniques for significantly reducing the overhead of runtime dependence testing: (1) identifying new equality constraints that result in more efficient runtime inspectors, and (2) identifying subset relations between dependence constraints such that one dependence test subsumes another one that is therefore eliminated. New equality constraints discovery is enabled by taking advantage of domain-specific knowledge about index arrays, such as col[j]. These simplifications lead to automatically-generated inspectors that make it practical to parallelize such computations. We analyze our simplification methods for a collection of seven sparse computations. The evaluation shows our methods reduce the complexity of the runtime inspectors significantly. Experimental results for a collection of five large matrices show parallel speedups ranging from 2x to more than 8x running on a 8-core CPU.

This paper describes an approach to performance optimization using modified macro dataflow graphs, which contain nodes representing the loops and data involved in the stencil computation. The targeted applications include existing scientific applications that contain a series of stencil computations that share data, i.e. loop chains. The performance of stencil applications can be improved by modifying the execution schedules. However, modern architectures are increasingly constrained by the memory subsystem bandwidth. To fully realize the benefits of the schedule changes for improved locality, temporary storage allocation must also be minimized.

Irregular applications such as big graph analysis, material simulations, molecular dynamics simulations, and finite element analysis have performance problems due to their use of sparse data structures. Inspector-executor strategies improve sparse computation performance through parallelization and data locality optimizations. An inspector reschedules and reorders data at runtime, and an executor is a transformed version of the original computation that uses the newly reorganized schedules and data structures. Inspector-executor transformations are commonly written in a domain-specific or even application-specific fashion. Significant progress has been made in incorporating such inspector-executor transformations into existing compiler transformation frameworks, thus enabling their use with compile-time transformations. However, composing inspector-executor transformations in a general way has only been done in the context of the Sparse Polyhedral Framework (SPF). Though SPF enables the general composition of such transformations, the resulting inspector and executor performance suffers due to missed specialization opportunities. This paper reviews the history and current state of the art for inspector-executor strategies and reviews how the SPF enables the composition of inspector-executor transformations. Further, it describes a research vision to combine this generality in SPF with specialization to achieve composable and high performance inspectors and executors, producing a powerful compiler framework for sparse matrix computations.

Stencil computations figure prominently in the core kernels of many scientific computations, such as partial differential equation solvers. Parallel scaling of stencil computations can be significantly improved on multicore processors using advanced tiling techniques that include the time dimension, such as diamond tiling. Such techniques are difficult to include in general purpose optimizing compilers because of the need for inter-procedural pointer and array data-flow analysis, plus the need to tune scheduling strategies and tile size parameters for each pairing of stencil computation and machine.

Many scientific applications are organized in a data parallel way: as sequences of parallel and/or reduction loops. This exposes parallelism well, but does not convert data reuse between loops into data locality. This paper focuses on this issue in parallel loops whose loop-to-loop dependence structure is data-dependent due to indirect references such as A[B[i]]. Such references are a common occurrence in sparse matrix computations, molecular dynamics simulations, and unstructured-mesh computational fluid dynamics (CFD). Previously, sparse tiling approaches were developed for individual benchmarks to group iterations across such loops to improve data locality. These approaches were shown to benefit applications such as moldyn, Gauss-Seidel, and the sparse matrix powers kernel, however the run-time routines for performing sparse tiling were hand coded per application. In this paper, we present a generalized full sparse tiling algorithm that uses the newly developed loop chain abstraction as input, improves inter-loop data locality, and creates a task graph to expose shared-memory parallelism at runtime. We evaluate the overhead and performance impact of the generalized full sparse tiling algorithm on two codes: a sparse Jacobi iterative solver and the Airfoil CFD benchmark.

Climate and other big data applications face substantial problems in terms of data storage, retrieval, sharing and management. While several community repositories and tools are available to help with climate data, these problems still persist and the community is actively looking for better solutions. In this project we apply NDN to support climate modeling applications. The information-centric nature of NDN, where content becomes a first class entity, simplifies many of the problems in this domain. NDN offers lightweight data publication, discovery and retrieval compared to IP-based solutions. However, introducing a new network architecture to a mature domain that routinely produces petabytes of datasets and a plethora of assorted tools to manipulate them, is a risky proposition. The advantages of NDN alone may not be sufficient to overcome the natural inertia. Our approach is to introduce NDN while carefully avoiding undue disruption to existing workflows. To that extent we employ a user interface that employs familiar filesystem operations to publish, discover and retrieve data, integrated with domain-specific translators that automatically convert and publish datasets as NDN objects. We outline the advantages of NDN in this application domain and the challenges we faced during the adaptation. We believe this is the first exercise in applying NDN in an existing, large, mature application domain.

Structured-grid PDE solver frameworks parallelize over boxes, which are rectangular domains of cells or faces in a structured grid. In the Chombo framework, the box sizes are typically 163 or 323, but larger box sizes such as 1283 would result in less surface area and therefore less storage, copying, and/or ghost cells communication overhead. Unfortunately, current on node parallelization schemes perform poorly for these larger box sizes. In this paper, we investigate 30 different inter-loop optimization strategies and demonstrate the parallel scaling advantages of some of these variants on NUMA multicore nodes. Shifted, fused, and communication-avoiding variants for 1283 boxes result in close to ideal parallel scaling and come close to matching the performance of 163 boxes on three different multicore systems for a benchmark that is a proxy for program idioms found in Computational Fluid Dynamic (CFD) codes.

Suppose one is considering purchase of a computer equipped with accelerators. Or suppose one has access to such a computer and is considering porting code to take advantage of the accelerators. Is there a reason to suppose the purchase cost or programmer effort will be worth it? It would be nice to able to estimate the expected improvements in advance of paying money or time. We exhibit an analytical framework and tool-set for providing such estimates: the tools first look for user-defined idioms that are patterns of computation and data access identified in advance as possibly being able to benefit from accelerator hardware. A performance model is then applied to estimate how much faster these idioms would be if they were ported and run on the accelerators, and a recommendation is made as to whether or not each idiom is worth the porting effort to put them on the accelerator and an estimate is provided of what the overall application speedup would be if this were done.

Virtual organizations (VOs), communities that enable coordinated resource sharing among multiple sites, are becoming more prevalent in the high-performance computing community. In order to promote cross-site resource usability, most VOs prepare service agreements that include a minimum set of common resource functionality, starting with a common software stack and evolving into more complicated service and interoperability agreements. VO service agreements are often difficult to verify and maintain, however, because the sites are dynamic and autonomous. Automated verification of service agreements is critical: manual and user tests are not practical on a large scale. The Inca test harness and reporting framework is a generic system for the automated testing, data collection, verification, and monitoring of service agreements. This paper describes Inca’s architecture, system impact, and performance. Inca is being used by the TeraGrid project to verify software installations, monitor service availability, and collect performance data.