Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “domain compilation”

Search indexed NASA NTRS and DOE OSTI research on propulsion, heat transfer, battery materials and energy systems. Follow report and document links to the original sources.

Quote a phrase for an exact phrase match. Source license links do not imply unrestricted reuse.

At least 217 records · Page 12

Implementation and Synthesis of Math Library Functions

Achieving speed and accuracy for math library functions like exp, sin, and log is difficult. This is because low-level implementation languages like C do not help math library developers catch mathematical errors, build implementations incrementally, or separate high-level and low-level decision making. This ultimately puts development of such functions out of reach for all but the most experienced experts. To address this, we introduce MegaLibm, a domain-specific language for implementing, testing, and tuning math library implementations. MegaLibm is safe, modular, and tunable. Implementations in MegaLibm can automatically detect mathematical mistakes like sign flips via semantic wellformedness checks, and components like range reductions can be implemented in a modular, composable way, simplifying implementations. Once the high-level algorithm is done, tuning parameters like working precisions and evaluation schemes can be adjusted through orthogonal tuning parameters to achieve the desired speed and accuracy. MegaLibm also enables math library developers to work interactively, compiling, testing, and tuning their implementations and invoking tools like Sollya and type-directed synthesis to complete components and synthesize entire implementations. MegaLibm can express 8 state-of-the-art math library implementations with comparable speed and accuracy to the original C code, and can synthesize 5 variations and 3 from-scratch implementations with minimal guidance.

97 MATHEMATICS AND COMPUTING↗

Analysis of Plant Pan-Genomes and Transcriptomes with GET_HOMOLOGUES-EST, a Clustering Solution for Sequences of the Same Species

The pan-genome of a species is defined as the union of all the genes and noncoding sequences found in all its individuals. However, constructing a pan-genome for plants with large genomes is daunting both in sequencing cost and the scale of the required computational analysis. A more affordable alternative is to focus on the genic repertoire by using transcriptomic data. Here, the software GET_HOMOLOGUES-EST was benchmarked with genomic and RNA-seq data of 19 Arabidopsis thaliana ecotypes and then applied to the analysis of transcripts from 16 Hordeum vulgare genotypes. The goal was to sample their pan-genomes and classify sequences as core, if detected in all accessions, or accessory, when absent in some of them. The resulting sequence clusters were used to simulate pan-genome growth, and to compile Average Nucleotide Identity matrices that summarize intra-species variation. Although transcripts were found to under-estimate pan-genome size by at least 10%, we concluded that clusters of expressed sequences can recapitulate phylogeny and reproduce two properties observed in A. thaliana gene models: accessory loci show lower expression and higher non-synonymous substitution rates than core genes. Finally, accessory sequences were observed to preferentially encode transposon components in both species, plus disease resistance genes in cultivated barleys, and a variety of protein domains from other families that appear frequently associated with presence/absence variation in the literature. These results demonstrate that pan-genome analyses are useful to explore germplasm diversity.

54 ENVIRONMENTAL SCIENCES↗

Union: A Unified HW-SW Co-Design Ecosystem in MLIR for Evaluating Tensor Operationson Spatial Accelerators

To meet the extreme compute demands for deep learning across commercial and scientific applications, dataflow accelerators are becoming increasingly popular. While these“domain-specific” accelerators are not fully programmable like CPUs and GPUs, they retain varying levels of flexibility with respect to data orchestration, i.e., dataflow and tiling optimizations to enhance efficiency. There are several challenges when designing new algorithms and mapping approaches to execute the algorithms for a target problem on new hardware. Previous works have addressed these challenges individually. To address this challenge as a whole, in this work, we present an HW-SW co-design ecosystem for spatial accelerators called Union within the popular MLIR compiler infrastructure. Our framework allows exploring different algorithms and their mappings on several accelerator cost models. Union also includes a plug-and-play library of accelerator cost models and mappers which can easily be extended. The algorithms and accelerator cost models are connected via a novel mapping abstraction that captures the map space of spatial accelerators which can be systematically pruned based on constraints from the hardware, workload, and mapper. We demonstrate the value of Union for the community with several case studies which examine offloading different tensor operations (CONV/GEMM/Tensor Contraction) on diverse accelerator architectures using different mapping schemes.

Jeong, Geonhwa↗

Unified Language Frontend for Physic-Informed AI/ML

Artificial intelligence and machine learning (AI/ML) are becoming important tools for scientific modeling and simulation as in several other fields such as image analysis and natural language processing. ML techniques can leverage the computing power available in modern systems and reduce the human effort needed to configure experiments, interpret and visualize results, draw conclusions from huge quantities of raw data, and build surrogates for physics based models. Domain scientists in fields like fluid dynamics, microelectronics and chemistry can automate many of their most difficult and repetitive tasks or improve the design times by use of the faster ML-surrogates. However, modern ML and traditional scientific highperformance computing (HPC) tend to use completely different software ecosystems. While ML frameworks like PyTorch and TensorFlow provide Python APIs, most HPC applications and libraries are written in C++. Direct interoperability between the two languages is possible but is tedious and error-prone. In this work, we show that a compiler-based approach can bridge the gap between ML frameworks and scientific software with less developer effort and better efficiency. We use the MLIR (multi-level intermediate representation) ecosystem to compile a pre-trained convolutional neural network (CNN) in PyTorch to freestanding C++ source code in the Kokkos programming model. Kokkos is a programming model widely used in HPC to write portable, shared-memory parallel code that can natively target a variety of CPU and GPU architectures. Our compiler-generated source code can be directly integrated into any Kokkosbased application with no dependencies on Python or cross-language interfaces.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

UPC++

UPC++ is a Partitioned Global Address Space (PGAS) extension for C++, with three main objectives: 1) to provide an object-oriented PGAS programming model in the context of the popular C++ language; 2) to add useful parallel programming idioms unavailable in UPC, such as asynchronous remote function invocation and multidimensional arrays, to support complex scientific applications; 3) to offer an easy on-ramp to PGAS programming through interoperability with other existing parallel programming systems (e.g., MPI, OpenMP, CUDA). UPC++ includes two main features beyond UPC: 1) One of the major limitations of UPC in the context of DOE application is the relatively weak notion of multidimensional arrays, which it inherited from C. To remedy this problem in UPC++, we included a multidimensional domain and array library based on that of Titanium. Titanium's library is similar to Chapel's dense and strided domains, as both were inspired by the dense and strided regions and arrays in ZPL. 2) Another feature provided by UPC++ but not by UPC is remote function invocation, which is inspired by Phalanx, X10, Habanero-C, and C++11. The user may start an asynchronous remote function invocation with the following syntax: "async(place)(function, args...);". UPC++ provides two programming constructs for specifying dynamic dependencies among tasks: 1) event-driven execution as in Phalanx and Habanero-C; 2) finish-async as in X10. We implemented UPC++ with a "compiler-free" approach using C++ templates and runtime libraries. The UPC++ front-end consists of a set of C++ header files that enables the C++ compiler to "translate" UPC++ features in a user program to runtime library calls. In particular, we use templates and operator overloading to customize the behavior of UPC++ types. This software package has been replaced with UPCC++ V 1.0

Amir Kamil, YiliZheng↗

Semicoherent symmetric quantum processes: Theory and applications

Discovering pragmatic and efficient approaches to construct ε-approximations of quantum operators such as real (imaginary) time-evolution propagators in terms of the basic quantum operations (gates) is challenging. Prior ε-approximations are invaluable, in that they enable the compilation of classical and quantum algorithm modeling of, e.g., dynamical and thermodynamic quantum properties. In parallel, symmetries are powerful tools concisely describing the fundamental laws of nature; the symmetric underpinnings of physical laws have consistently provided profound insights and substantially increased predictive power. In this work, we consider the interplay between the ε-approximate processes and the exact symmetries in a semicoherent context—where measurements occur at each logical clock cycle. Here we draw inspiration from Pascual Jordan's groundbreaking formulation of nonassociative, but commutative, symmetric algebraic form. Our symmetrized formalism is then applied in various domains such as quantum random walks, real-time evolutions, variational algorithm ansatzes, and efficient entanglement verification. Our work paves the way for a deeper understanding and greater appreciation of how symmetries can be used to control quantum dynamics in settings where coherence is a limited resource.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Quantum Computing in the Cloud: Analyzing job and machine characteristics

As the popularity of quantum computing continues to grow, quantum machine access over the cloud is critical to both academic and industry researchers across the globe. And as cloud quantum computing demands increase exponentially, the analysis of resource consumption and execution characteristics are key to efficient management of jobs and resources at both the vendor-end as well as the client-end. While the analysis of resource consumption and management are popular in the classical HPC domain, it is severely lacking for more nascent technology like quantum computing. This paper is a first-of-its-kind academic study, analyzing various trends in job execution and resources consumption / utilization on quantum cloud systems. We focus on IBM Furthermore, quantum systems and analyze characteristics over a two year period, encompassing over 6000 jobs which contain over 600,000 quantum circuit executions and correspond to almost 10 billion “shots” or trials over 20+ quantum machines. Specifically, we analyze trends focused on, but not limited to, execution times on quantum machines, queuing/waiting times in the cloud, circuit compilation times, machine utilization, as well as the impact of job and machine characteristics on all of these trends. Furthermore, our analysis identifies several similarities and differences with classical HPC cloud systems. Based on our insights, we make recommendations and contributions to improve the management of resources and jobs on future quantum cloud systems.

42 ENGINEERING↗

9Cr steel visualization and predictive modeling

The goals of this work were to develop tools to visualize and characterize materials information, to explore new alloy compositions and/or processing, to better predict tensile strength and other mechanical properties. The 9–12 wt% Cr (9Cr) steel test data were compiled from several sources. About 3000 records with 30 predictor variables represent 82 unique steel alloy compositions, variations of thermo-mechanical processing steps and temperatures (homogenization, normalization and tempering cycles), test conditions and outcomes. Detailed data processing steps such as visualization and exploratory analysis, including univariate and bivariate analysis, different clustering techniques used to segment the data, statistical post-hoc analysis to verify significance of the findings, feature engineering to identify predictors of importance, and predictive modeling with cross-validation were performed. The outcome of analysis at each step was reviewed in the context of the domain knowledge of this class of steel, to see if there were underlying physical mechanisms that explain statistical relationships. Data analytics techniques and their parameters were fine-tuned to facilitate interpretation of the results as aligned with the insights from domain experts. Here, the ensemble predictive modeling using Random Forest regressor and post-hoc means comparison corroborated domain knowledge on the role of Co which is known to increase strength of steel alloys through solid-solution strengthening and to affect diffusion of alloying elements and precipitates. Alloys with Co content of 0.7–8 wt% had significantly higher mean strength than the ones without (while having Cr locked within 10–11 wt% range in either group and keeping other compositional element ratios fixed). End products of the computational techniques exploration are presented as the tools that can be used in iterative workflow of materials development and testing.

36 MATERIALS SCIENCE↗

A multi-criteria CCUS screening evaluation of the Gulf of Mexico, USA

Continued research into reservoir characterization along with offshore carbon dioxide (CO 2 ) transportation and infrastructure assets is needed to facilitate development of safe and successful carbon capture, utilization, and storage (CCUS) projects. This paper outlines a multi-criteria evaluation methodology that incorporates disparate sets of quantitative, spatially variable data into a decision-making framework for screening the Gulf of Mexico (GOM) outer continental shelf (OCS) for potentially viable CO 2 storage and enhanced oil recovery (EOR) sites. Criteria categories include favorable geologic characteristics, logistics, and potential risks. Data compiled for 14 criteria from several publicly available geographic information system (GIS) layers was aggregated over 2559 spatially balanced points across the study area using the National Energy Technology Laboratory (NETL)-developed Cumulative Spatial Impact Layers™ (CSIL) GIS tool. Criteria are weighted by qualitative expert opinion relative to their perceived importance to given scenarios— the output of combined criteria values and weights enables regional CO 2 storage suitability differentiation. The methodology considers both technical and non-technical factors impacting CCUS decision-making. The flexible methodology enables a systematic approach to regional ranking at high spatial resolution over a large study domain. Additionally, the framework enables high-grading of priority sites that warrant further characterization and follow-on analysis. Areas along the Louisiana coast and Mississippi River Delta consistently rank high for all scenarios largely a result of the favorable geology with the potential for stacked storage, as well as the density of existing pipelines and platforms, and proximity to several onshore CO 2 sources. High-graded regions for the CO 2 EOR-related scenarios are typically located further offshore towards the middle and edge of the OCS compared to higher priority regions for the geologic storage scenarios which fall closer to the Louisiana coastline.

54 ENVIRONMENTAL SCIENCES↗

Computing with a Chemical Reservoir

Contemporary computation is expensive, with large language models and artificial intelligence becoming more common in daily life. However, high-performance computing is reaching the limits in speed and energy expenditure, and domain science requires ever-increasing computational capacity, with simulations and data analysis pipelines ever-growing in complexity. As we progress towards post-exascale computation, with the associated high energy costs, new methods of energy-conscious computation are required. Novel analog and hybrid digital-analog systems can overcome these challenges, and chemical reactions offer a promising avenue. Computers based on chemistry can provide compact desktop devices with immense computational power. These devices are readily scalable by considering greater reaction systems or vessels, meeting the high-performance requirements for scientific workflows. In this article, we present ChemComp, a compilation pipeline for the conversion of ordinary differential equations into implementable chemical reactions. We then demonstrate the solving capabilities of ChemComp by emulating a potential chemical reservoir device. We leverage the multi-layer intermediate representation (MLIR) compiler framework to implement an expressive chemical reaction abstraction and propose a path for chemical reaction networks (CRNs) to represent mathematical problems effectively. Combined, we demonstrate a potential workflow that can harness chemistry’s computing power to create energy-efficient, high-performance computation systems for contemporary computing needs.

artificial intelligence↗

Towards High-Assurance High-Performance Program Synthesis

Domain-specific automatic program synthesis tools, also called application generators, are playing an ever-increasing role in software development. However, high-performance application generators require difficult manual construction, and are very difficult to verify correct. This paper describes research and an implemented system that transforms program synthesis tools based on deductive synthesis into high-performance application generators. Deductive synthesis uses theorem-proving to construct solutions when given problem specifications. The verification condition for a deductive synthesis tool is essentially the soundness of the implemented inference rules. Theory Operationalization for Program Synthesis (TOPS) synergistically combines reformulation, automated mathematical classification, and compilation through partial deduction to decision procedures. It transforms general-purpose deductive synthesis, with exponential performance, into efficient special-purpose deductive synthesis, with near-linear performance. This paper describes our experience with and empirical results of PD(TH) theory-based partial deduction - in which partial deduction of a set of first-order formulae is performed within the context of a background theory. The implemented TOPS system currently performs a special variant of PD(TH) in which the compilation process results in the transformation of a set of first order formulae into the theory of an instantiated library decision procedure augmented by a compiled unit theory.

Lowry, Michael↗

HESS J1943+213: A NON-CLASSICAL HIGH-FREQUENCY-PEAKED BL LAC OBJECT

HESS J1943+213 is an unidentified TeV source that is likely a high-frequency-peaked BL Lac (HBL) object, but that is also compatible with a pulsar wind nebula (PWN) nature. Each of these enormously different astronomical interpretations is supported by some of the observed unusual characteristics. In order to finally classify and understand this object, we took a three-pronged approach, through time-domain, high angular resolution, and multi-frequency radio studies. First, our deep time-domain observations with the Arecibo telescope failed to uncover the putative pulsar powering the proposed PWN. We conclude with ∼70% certainty that HESS J1943+213 does not host a pulsar. Second, long-baseline interferometry of the source with e-MERLIN at 1.5 and 5 GHz shows only a core, that is, a point source at ∼1–100 mas resolution. Its 2013 flux density is about one-third lower than that detected in the 2011 observations with similar resolution. This radio variability of the core strengthens the HBL object hypothesis. Third, additional evidence against the PWN scenario comes from the radio spectrum we compiled. The extended structure follows a power-law behavior with spectral index α = −0.54±0.04 while the core component displays a flat spectrum (α = −0.03±0.03). In contrast, the radio synchrotron emission of PWNe predicts a single power-law distribution. Overall, we rule out the PWN hypothesis and conclude that the source is a BL Lac object. The consistently high fraction (70%) of the flux density from the extended structure then leads us to conclude that HESS J1943+213 must be a non-classical HBL object.

79 ASTRONOMY AND ASTROPHYSICS↗

Aboveground biomass density models for NASA’s Global Ecosystem Dynamics Investigation (GEDI) lidar mission

NASA's Global Ecosystem Dynamics Investigation (GEDI) is collecting spaceborne full waveform lidar data with a primary science goal of producing accurate estimates of forest aboveground biomass density (AGBD). This paper presents the development of the models used to create GEDI's footprint-level (~25 m) AGBD (GEDI04_A) product, including a description of the datasets used and the procedure for final model selection. The data used to fit our models are from a compilation of globally distributed spatially and temporally coincident field and airborne lidar datasets, whereby we simulated GEDI-like waveforms from airborne lidar to build a calibration database. We used this database to expand the geographic extent of past waveform lidar studies, and divided the globe into four broad strata by Plant Functional Type (PFT) and six geographic regions. GEDI's waveform-to-biomass models take the form of parametric Ordinary Least Squares (OLS) models with simulated Relative Height (RH) metrics as predictor variables. From an exhaustive set of candidate models, we selected the best input predictor variables, and data transformations for each geographic stratum in the GEDI domain to produce a set of comprehensive predictive footprint-level models. We found that model selection frequently favored combinations of RH metrics at the 98th, 90th, 50th, and 10th height above ground-level percentiles (RH98, RH90, RH50, and RH10, respectively), but that inclusion of lower RH metrics (e.g. RH10) did not markedly improve model performance. Second, forced inclusion of RH98 in all models was important and did not degrade model performance, and the best performing models were parsimonious, typically having only 1-3 predictors. Third, stratification by geographic domain (PFT, geographic region) improved model performance in comparison to global models without stratification. Fourth, for the vast majority of strata, the best performing models were fit using square root transformation of field AGBD and/or height metrics. There was considerable variability in model performance across geographic strata, and areas with sparse training data and/or high AGBD values had the poorest performance. These models are used to produce global predictions of AGBD, but will be improved in the future as more and better training data become available.

54 ENVIRONMENTAL SCIENCES↗

Aboveground biomass density models for NASA’s Global Ecosystem Dynamics Investigation (GEDI) lidar mission

NASA’s Global Ecosystem Dynamics Investigation (GEDI) is collecting spaceborne full waveform lidar data with a primary science goal of producing accurate estimates of forest aboveground biomass density (AGBD). This paper presents the development of the models used to create GEDI’s footprint-level (~25 m) AGBD (GEDI04_A) product, including a description of the datasets used and the procedure for final model selection. The data used to fit our models are from a compilation of globally distributed spatially and temporally coincident field and airborne lidar datasets, whereby we simulated GEDI-like waveforms from airborne lidar to build a calibration database. We used this database to expand the geographic extent of past waveform lidar studies, and divided the globe into four broad strata by Plant Functional Type (PFT) and six geographic regions. GEDI’s waveform-to-biomass models take the form of parametric Ordinary Least Squares (OLS) models with simulated Relative Height (RH) metrics as predictor variables. From an exhaustive set of candidate models, we selected the best input predictor variables, and data transformations for each geographic stratum in the GEDI domain to produce a set of comprehensive predictive footprint-level models. We found that model selection frequently favored combinations of RH metrics at the 98th, 90th, 50th, and 10th height above ground-level percentiles (RH98, RH90, RH50, and RH10, respectively), but that inclusion of lower RH metrics (e.g. RH10) did not markedly improve model performance. Second, forced inclusion of RH98 in all models was important and did not degrade model performance, and the best performing models were parsimonious, typically having only 1-3 predictors. Third, stratification by geographic domain (PFT, geographic region) improved model performance in comparison to global models without stratification. Fourth, for the vast majority of strata, the best performing models were fit using square root transformation of field AGBD and/or height metrics. There was considerable variability in model performance across geographic strata, and areas with sparse training data and/or high AGBD values had the poorest performance. These models are used to produce global predictions of AGBD, but will be improved in the future as more and better training data become available.

Laura Duncanson↗

Toward Performance Portable Programming for Heterogeneous System-on-Chips: Case Study with Qualcomm Snapdragon SoC

Future heterogeneous Domain-Specific System-on-Chips (DSSoC) will be extraordinarily complex in terms of processors, memory hierarchies, and interconnection networks.To manage this complexity, architects, system software designers, and application developers need programming technologies that are flexible, accurate, efficient, and productive. These technologies will need to be as independent of any one specific architecture as is practical, because the sheer dimensionality and scale of the complexity will not allow porting and optimizing applications foreach given DSSoC. To address these issues, we are developing Cosmic Castle, a performance portable programming toolchain for streaming applications on heterogeneous architectures. The primary focus of Cosmic Castle is on enabling efficient and performant code generation through the smart compiler and intelligent runtime system. This paper presents the preliminary evaluation of our ongoing work toward Cosmic Castle. Specifically, we detail our code porting efforts and evaluate various benchmarks on the Qualcomm Snapdragon SoC using tools developed through Cosmic Castle.

Cabrera, Anthony↗

Data Locality Enhancement of Dynamic Simulations for Exascale Computing (Final Report)

The development of modern processors exhibits two trends that complicate the optimizations of modern software. The first is the increasing sensitivity of processors' throughput to irregularities in computation. With more processors produced through a massive integration of simple cores, future systems will increasingly favor regular data-level parallel computations, but deviate from the needs of applications with complex patterns. Some evidences are already shown on Graphic Processing Units (GPU): Irregular data accesses (e.g., indirect references A[D[i]]) and conditional branches are limiting many GPU applications' performance at a level an order of magnitude lower than the peak of GPU. The second hardware trend is the growing gap between memory bandwidth and the aggregate speed—that is, the sum of all cores' computing power—of a Chip Multiprocessor (CMP). Despite the capped growth of the peak CPU speed, the aggregate speed of a CMP keeps increasing as more cores get into a single chip. It is expected that by 2018, node concurrency in an exascale system will increase by hundreds of times, whereas, memory bandwidth will expand by only 10 to 20 times. Consequently, data movement and storage is expected to consume more than 70% of the total system power. Bridging this gap is difficult; the complexities of modern CMP memory hierarchy make it even harder: Data cache becomes shared among computing units, and the sharing is often non-uniform—whether two computing units share a cache depends on their proximity and the level of the cache. On the recent IBM Power7 architecture, for instance, four hardware contexts (or SMT threads) in a core share the entire memory hierarchy, all cores in one chip share an on-chip L3 cache, and cores across chips share L3 and main memory through off-chip connections. These two trends complicate the translation of computing power into performance, especially for a program with either intensive data accesses or complex patterns in data accesses or control flow paths. Unfortunately, both attributes present and will persist in a class of important applications. For instance, many scientific simulations deal with a large volume of data. And meanwhile, as most real-world processes are non-uniform and evolving (e.g., the evolution of a galaxy or the process of a drug injection), both the computations and data accesses of these programs tend to be irregular and dynamically changing. Currently, the lack of support to these applications on modern CMP severely limits their performance. On GPU, as our recent study shows and other studies echo, performance enhancement of a factor of integers is possible when memory accesses or control flows are streamlined for a set of GPU applications. On multicore CPU, our studies show that traditional locality enhancement, for being oblivious to the new features of multicore memory hierarchy, may even cause large slowdown to data-intensive dynamic applications. The severity of the issues is expected to worsen as the two hardware trends continue. Some recent studies try to match software with the trends, but in a limited scope or manner. For irregularities on GPU, most studies focus on irregularities analyzable through static analysis (e.g., data accesses in regular loops). Dynamic irregularities are harder to address because the needed analysis and transformations typically have to happen at run time. Some other research resorts to hardware extensions, an actual adoption of which is unclear for the entailed space cost and complexity. For data locality, recent years have seen some exploitations of the new memory hierarchy on multicore for performance, but most of them are on process or thread scheduling, rather than program transformations. Our recent study reveals that program-level transformations may magnify the scheduling benefits by a factor of seven, concluding that program-level transformation should play a central role for data locality enhancement on modern CMP. But research in this direction has been sparse, and most have focused on data layout or cache performance modeling, rather than program transformations to match with the new memory hierarchy features. Overall, it is still an open question how to bridge the gap between dynamic computations and the two prominent properties of modern processors. The goal of this project is to develop a set of techniques and software tools to enhance the matching between memory accesses in dynamic simulations and the prominent features of modern and future CMP, alleviating the memory performance issues for petascale and exascale computing. This report summarizes the discoveries and products produced throughout this project. It includes free launch, a new software approach to overcoming the shortcomings of both methods; coherence-free multiview, an approach that allows multiple views of a single data object to co-exist on GPU memory during a GPU kernel execution; algorithmic optimizations to data analytics problems, especially those that involve lots of distance calculations. Supporting dynamic parallelism is important for GPU to benefit a broad range of applications. There are currently two fundamental ways for programs to exploit dynamic parallelism on GPU: a software-based approach with software-managed worklists, and a hardware-based approach through dynamic subkernel launches. Neither is satisfactory. The former is complicated to program and is often subject to some load imbalance; the latter suffers large runtime overhead. In this work, we propose free launch, a new software approach to overcoming the shortcomings of both methods. It allows programmers to use subkernel launches to express dynamic parallelism. It employs a novel compiler-based code transformation named subkernel launch removal to replace the subkernel launches with the reuse of parent threads. Coupled with an adaptive task assignment mechanism, the transformation reassigns the tasks in the subkernels to the parent threads with a good load balance. The technique requires no hardware extensions, immediately deployable on existing GPUs. It keeps the programming convenience of the subkernel launch-based approach while avoiding its large runtime overhead. Meanwhile, its superior load balancing makes it outperform manual worklist-based techniques by 3X on average. The work was published at the 48th Annual IEEE/ACM International Symposium on Microarchitecture (Micro'2015). A Graphic Processing Unit (GPU) system is typically equipped with many types of memory (e.g., global, constant, texture, shared, cache). Data placement determines what data are placed on which type of memory, essential for GPU memory performance. Prior optimizations of data placement always require a single view of a data object on memory, which limits the optimization effectiveness. In this work, we propose coherence-free multiview, an approach that allows multiple views of a single data object to co-exist on GPU memory during a GPU kernel execution. We demonstrate that under certain conditions, the multiple views can remain incoherent while facilitating enhanced data placement. We present a theorem and some compiler support to ensure the soundness of the usage of coherence-free multiview. We further develop reference-discerning data placement, a new way to enhance data placements on GPU. It enables more flexible data placements by using coherence-free multiview to leverage the slack in coherence requirement of some GPU programs. Experiments on three types of GPU systems show that, with less than 200KB space cost, the new data placement technique can provide a 1.6X average (up to 4.27X) speedup. In addition, we have examined algorithmic optimizations to data analytics problems, especially those that involve lots of distance calculations. Computing distances among data points is an essential part of many important algorithms in data analytics, graph analysis, and other domains. In each of these domains, developers have spent significant manual effort optimizing algorithms, often through novel applications of the triangle equality, in order to minimize the number of distance computations in the algorithms. In this work, we observe that many algorithms across these domains can be generalized as an instance of a generic distance-related abstraction. Based on this abstraction, we derive seven principles for correctly applying the triangular inequality to optimize distance-related algorithms. Guided by the findings, we develop Triangular OPtimizer (TOP), the first software framework that is able to automatically produce optimized algorithms that either matches or outperforms manually designed algorithms for solving distance-related problems. TOP achieves up to 237x speedups and 2.5X on average. The work has been published at the 32nd International Conference on Machine Learning (ICML'15) and the 41st International Conference on Very Large Data Bases (VLDB'15).

42 ENGINEERING↗

A Synthesis Methodology for Intelligent Memory Interfaces in Accelerator Systems

Domain-specific systems improve the performance of a specific set of applications compared to general-purpose processing systems by deploying custom hardware accelerators. These hardware accelerators are generated using high-level synthesis (HLS) tools. The HLS tools enable a comprehensive design space exploration to optimize the compute performance of the generated accelerators. However, they often ignore the challenges of implementing the accelerators in a system-on-chip, particularly how the accelerators access memory. Our work introduces a buffering system design that improves accelerators' memory accesses by intelligently employing burst transactions to prefetch useful data from external memory to on-chip local buffers. Our design is dynamic, parametric, and transparent to the accelerators generated by HLS tools. We derive the buffering system parameters using appropriate compiler-based analysis passes and memory channel latency constraints. The proposed buffering system design results in, on average, 8.8x performance improvements while lowering memory channel utilization on average by 53.2% for a set of PolyBench kernels.

Limaye, Ankur M. (ORCID:0000000194062584)↗

The Essence of Cryptol: A Denotational Cryptol Interpreter in Coq for Foundational Assurances for Quantum Resistant Cryptosystems

Systems of the utmost consequence need a means to establish authenticity of software and data. Cryptosystems implement authentication, but can be vulnerable to cryptographic and implementation attacks. With the threat of quantum cryptographic attacks, “post-quantum” cryptosystems (PQCs) must be henceforth used in these systems. However, the new cryptography needs new ways to, rigorously and machine-checkably, prove systems free of vulnerabilities. We propose a retargetable capability to rapidly instantiate proven correct postquantum cryptosystems through novel proof-carrying synthesis and proof-automation technique, extending those proven successful on existing systems. This capability is crucial to meeting the cryptographic requirements for future high-consequence systems. Since specifications for high consequence cryptography are presently captured in a domain specific language known as Cryptol. While this can enable convenient fully automated reasoning about Cryptol specificaitons and implementations via the Software Analysis Workbench (SAW), Cryptol has expressivity gaps, so that cryptosystems with probabilistic programming features like Falcon cannot be fully expressed in the language. Moreover, SAW’s automation fails for programs and specificaitons with inductive and recursive structure, as in the Sphincs+ PQC. Finally, Cryptol and SAW together represent some 200,000 lines of unverified Haskell, so that the any guarantees about high consequence cryptography are presently contingent on a large, unverified, yet trusted computing base. The first step of the larger project of agile, assured crpytography is therefore to provide a formal, mechanized semantics for Cryptol, so that the specifications expressed by cryptographers in Cryptol can be reasoned about and compiled into performant implementations with a foundational, machine checkable certificate of correctness. This report describes our work on this first step, culminating in the design of a certified denotational interpreter, in Coq, for core Cryptol.

97 MATHEMATICS AND COMPUTING↗