Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “Parallel Architectures”

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.

571 records · Page 32
All sourcesNASA NTRSDOE OSTI
DOE OSTI2020

QCOR; A Language Extension Specification for the Heterogeneous Quantum-Classical Model of Computation

Quantum computing (QC) is an emerging computational paradigm that leverages the laws of quantum mechanics to perform elementary logic operations. Existing programming models for QC were designed with fault-tolerant hardware in mind, envisioning stand-alone applications. However, the susceptibility of near-term quantum computers to noise limits their stand-alone utility. To better leverage limited computational strengths of noisy quantum devices, hybrid algorithms have been suggested whereby quantum computers are used in tandem with their classical counterparts in a heterogeneous fashion. This modus operandi calls out for a programming model and a high-level programming language that natively and seamlessly supports heterogeneous quantum-classical hardware architectures in a single-source-code paradigm. Motivated by the lack of such a model, we introduce a language extension specification, called QCOR, which enables single-source quantum-classical programming. Programs written using the QCOR library–based language extensions can be compiled to produce functional hybrid binary executables. After defining QCOR’s programming model, memory model, and execution model, we discuss how QCOR enables variational, iterative, and feed-forward QC. Additionally, QCOR approaches quantum-classical computation in a hardware-agnostic heterogeneous fashion and strives to build on best practices of high-performance computing. The high level of abstraction in the language extension is intended to accelerate the adoption of QC by researchers familiar with classical high-performance computing.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2020

Optimizing the hypre solver for manycore and GPU architectures

The solution of large-scale combustion problems with codes such as Uintah on modern computer architectures requires the use of multithreading and GPUs to achieve performance. Uintah uses a low-Mach number approximation that requires iteratively solving a large system of linear equations. The Hypre iterative solver has solved such systems in a scalable way for Uintah, but the use of OpenMP with Hypre leads to at least slowdown due to OpenMP overheads. The proposed solution uses the MPI Endpoints within Hypre, where each team of threads acts as a different MPI rank. This approach minimizes OpenMP synchronization overhead and performs as fast or (up to 1.44) faster than Hypre's MPI-only version, and allows the rest of Uintah to be optimized using OpenMP. The profiling of the GPU version of Hypre shows the bottleneck to be the launch overhead of thousands of micro-kernels. The GPU performance was improved by fusing these micro-kernels and was further optimized by using Cuda-aware MPI, resulting in an overall speedup of 1.16—1.44 compared to the baseline GPU implementation. The above optimization strategies were published in the International Conference on Computational Science 2020 [1]. This work extends the previously published research by carrying out the second phase of communication-centered optimizations in Hypre to improve its scalability on large-scale supercomputers. Additionally, this includes an efficient non-blocking inter-thread communication scheme, communication-reducing patch assignment, and expression of logical communication parallelism to a new version of the MPICH library that utilizes the underlying network parallelism [2]. The above optimizations avoid communication bottlenecks previously observed during strong scaling and improve performance by up to 2 on 256 nodes of Intel Knight's Landing processor.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2021

How the Size and Density of Charge-Transfer Excitons Depend on Heterojunction’s Architecture

We have characterized the size, intensity, density, and distribution of charge-transfer (CT) excitons as a function of the acceptor–donor architecture of prototypical organic interfaces. This characterization was done by computational analysis of 17 models of varying numbers, positions, and orientations of the donor and acceptor molecules. The models’ building blocks were phenyl-C61-butyric acid methyl ester (PCBM) fullerene acceptors and dual-band donor polymers composed of thiophene, benzothiadiazole, and benzotriazole subunits. The electronic structure of the donor–acceptor complexes was computed with the time-dependent long-range-corrected density-functional tight-binding method and analyzed with the fragment-based one-electron transition density matrix. In all models, the complexes with edge-on orientation have denser spectra of low-energy CT states lying below the absorption bands compared to the complexes with face-on orientation. This CT-state distribution in edge-on complexes provides a gate to efficiently populate cold CT excitons. Moreover, the cold CT excitons have a higher degree of charge separation in the edge-on than in the face-on complexes. The CT amount and the CT exciton size generally increase with the energy of the CT states, although the electron remains localized on a single molecule in cold CT states. Delocalization over two PCBM molecules was observed for high-energy CT states. The exciton size also depends on the orientation. Larger excitons are produced by the delocalization of the electrons perpendicularly to the interface. When the delocalization is parallel, the smaller electron–hole distances yield moderately sized CT excitons.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗
DOE OSTI2025

Scalable training of trustworthy and energy-efficient predictive graph foundation models for atomistic materials modeling: a case study with HydraGNN

We present our work on developing and training scalable, trustworthy, and energy-efficient predictive graph foundation models (GFMs) using HydraGNN, a multi-headed graph convolutional neural network architecture. HydraGNN expands the boundaries of graph neural network (GNN) computations in both training scale and data diversity. It abstracts over message passing algorithms, allowing both reproduction of and comparison across algorithmic innovations that define nearest-neighbor convolution in GNNs. This work discusses a series of optimizations that have allowed scaling up the GFMs training to tens of thousands of GPUs on datasets consisting of hundreds of millions of graphs. Our GFMs use multitask learning (MTL) to simultaneously learn graph-level and node-level properties of atomistic structures, such as energy and atomic forces. Using over 154 million atomistic structures for training, we illustrate the performance of our approach along with the lessons learned on two state-of-the-art US Department of Energy (US-DOE) supercomputers, namely the Perlmutter petascale system at the National Energy Research Scientific Computing Center and the Frontier exascale system at Oak Ridge Leadership Computing Facility. The HydraGNN architecture enables the GFM to achieve near-linear strong scaling performance using more than 2000 GPUs on Perlmutter and 16,000 GPUs on Frontier.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2020

Residential Building Energy Efficiency Field Studies: Low-Rise Multifamily

In recent years, the U.S. Department of Energy (DOE) has conducted a series of research studies to validate energy efficient building technologies in the field. Much of the work has focused on single-family construction, and some has also addressed commercial energy codes. The work detailed in this DOE-funded study (EE0007616) focuses on low-rise multifamily buildings (three stories or fewer above grade) in various regions of the United States, and reports on how state-level building codes are being implemented, both in terms of observed characteristics and also in terms of estimated energy impacts. Nearly 100 buildings across four states—Illinois, Minnesota, Oregon, and Washington—were sampled, which represent a range of climate types from mild temperature to very cold continental. Both common entry and outdoor entry buildings were included, and a parallel research project evaluated envelope air tightness and current still-evolving air tightness testing methods. Finally, a set of structured interviews of building designers and other relevant professionals was carried to out to gain more insight into this market. To the greatest extent possible, the methodology developed under the project for low-rise multifamily buildings mirrored the approach established by Pacific Northwest National Laboratory (PNNL) for single-family residential buildings (https://www.energy.gov/eere/buildings/downloads/residential-building-energy-code-field-study). This included the general approach to sampling, recruitment, and data collection, as well as data analysis and presentation. The range of permitting dates for the sites encompassed two energy code cycles in most regions. All states in the study had adopted a variation of the International Energy Conservation Code (IECC) for the structure of their state code. The low-rise multifamily occupancy presents a hybrid building type: most of the building’s conditioned floor area was covered by the residential chapter of the code while portions of the building (such as corridors and common spaces) fell under the commercial code chapter. The key items assessed in this work were: Building Shell—exterior wall insulation, ceiling insulation, foundation insulation, windows. Common Areas—HVAC and lighting. Living Units—lighting, ventilation. A few items were not assessed in detail, given their relative paucity in this occupancy type; these included duct leakage, pipe insulation, and hot water circulation controls. Building characteristics were collected via a combination of architectural, mechanical, electrical, and plumbing plan reviews and field inspections, and entered into a spreadsheet-based tool that was later queried to build a database. Data went through quality control both upon arrival and via a later semi-automated review and assurance process. Most of the data are presented graphically so that the reader can quickly assess compliance with the applicable energy codes (both by state and by code year). As a final step, EnergyPlus™ simulations were created for all buildings in the study to estimate both the as-found energy use intensity (EUI) and the energy and CO 2 that could be saved if features that were found to not meet code minimums were brought up to code. The savings estimates were tabulated for each of the four states in the study. The research team found that the single-family approach was largely applicable to low-rise multifamily buildings. This applies to both the data collection and the prototype EUI analysis. Most of the occupied space is living units and falls under residential energy codes, and many characteristics use similar envelope construction and relatively straightforward mechanical systems and lighting. One of the most challenging aspects of this work was to build an effective spreadsheet-based data collection instrument that could allow efficient collection of both building plan and field data. The research team is of the view that other methods could be equally effective if the work is done carefully with diligent quality control. The primary findings for the work center around the thermal envelope and mechanical systems and lighting at the sites: For thermal envelope components, the majority of buildings met or were better than the prescriptive code.This suggests that building designers and builders are aware of code requirements. In some cases, surveyed buildings were designed to qualify for energy efficiency certification programs. These buildings made up at least 20% of sampled buildings in each state. Almost all buildings met mechanical system efficiency requirements (for both living units and common areas). In some cases, sites employed systems that were considerably more efficient than required by the applicable energy code. Dwelling units had a majority of high-efficacy lighting, often in excess of the state’s residential code requirements. While high-efficacy fixtures were also typical in common areas (corridors and stairwells), lighting power densities (LPDs) in these areas were sometimes higher than levels dictated by the applicable part of the state commercial energy code. The simulation models run on a series of low-rise multifamily prototypes, informed by a composite of the field data collected, calculated annual EUIs of between 20 and 50 kBtu/ft2-yr, with the range representing the effects of both building characteristics and building location (climate zone). A detailed process (based on simulations of prototype buildings) was used to estimate the amount of avoided energy use that would occur if 100% adherence to energy codes were attained. The results indicated modest savings are attainable for items such as window thermal performance and common area lighting. The result is overall only a modest potential for additional energy savings, averaging about 10% of EUI.

29 ENERGY PLANNING, POLICY, AND ECONOMY↗
DOE OSTI2020

Fast GPU 3D diffeomorphic image registration

3D image registration is one of the most fundamental and computationally expensive operations in medical image analysis. Here, we present a mixed-precision, Gauss–Newton–Krylov solver for diffeomorphic registration of two images. Our work extends the publicly available CLAIRE library to GPU architectures. Despite the importance of image registration, only a few implementations of large deformation diffeomorphic registration packages support GPUs. Our contributions are new algorithms to significantly reduce the run time of the two main computational kernels in CLAIRE: calculation of derivatives and scattered-data interpolation. Additionally, we deploy (i) highly-optimized, mixed-precision GPU-kernels for the evaluation of scattered-data interpolation, (ii) replace Fast-Fourier-Transform (FFT)-based first-order derivatives with optimized 8th-order finite differences, and (iii) compare with state-of-the-art CPU and GPU implementations. As a highlight, we demonstrate that we can register clinical images in less than 6 s on a single NVIDIA Tesla V100. This amounts to over 20 speed-up over the current version of CLAIRE and over 30 speed-up over existing GPU implementations.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2020

Locality-Aware Scheduling for Scalable Heterogeneous Environments

Heterogeneous computing promise boost performance of scientific applications by allowing massively parallel execution of computational tasks. However, manually managing extremely heterogeneous, multi-device systems is complicated and may result in sub-optimal performance. Specifically, data management is an extremely challenging problem on multi-device systems. In this work, we introduce two locality-aware schedulers for the Minos Computing Library (MCL), an asynchronous, task-based programming model and runtime for extremely heterogeneous systems. The first scheduler implements a pure locality-aware algorithm to maximize data reuse, though it might incur in ”hot-spots” that limit system utilization. The second scheduler mitigates this drawback by dynamically targeting between locality-awareness and system utilization based on the current workload and available computing devices. Our results show that locality-awareness greatly benefit applications that exhibit data reuse, providing up to 6.9x and 7.9x over the original MCL scheduler and equivalent OpenCL implementations, respectively. Moreover, our schedulers introduce negligible overhead compared with the original MCL scheduler and achieve similar performance for applications that don’t benefit from data locality.

Architecture, co-design, Task-based programming mo↗
DOE OSTI2023

Distributed out-of-memory NMF on CPU/GPU architectures

We propose an efficient distributed out-of-memory implementation of the non-negative matrix factorization (NMF) algorithm for heterogeneous high-performance-computing systems. The proposed implementation is based on prior work on NMFk, which can perform automatic model selection and extract latent variables and patterns from data. In this work, we extend NMFk by adding support for dense and sparse matrix operation on multi-node, multi-GPU systems. The resulting algorithm is optimized for out-of-memory problems where the memory required to factorize a given matrix is greater than the available GPU memory. Memory complexity is reduced by batching/tiling strategies, and sparse and dense matrix operations are significantly accelerated with GPU cores (or tensor cores when available). Input/output latency associated with batch copies between host and device is hidden using CUDA streams to overlap data transfers and compute asynchronously, and latency associated with collective communications (both intra-node and inter-node) is reduced using optimized NVIDIA Collective Communication Library (NCCL) based communicators. Benchmark results show significant improvement, from 32X to 76x speedup, with the new implementation using GPUs over the CPU-based NMFk. Good weak scaling was demonstrated on up to 4096 multi-GPU cluster nodes with approximately 25,000 GPUs when decomposing a dense 340 Terabyte-size matrix and an 11 Exabyte-size sparse matrix of density 10 -6 .

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2026

HydraGNN_Predictive_GFM_2026 - Ensemble of predictive graph foundation models for atomistic materials modeling

This release contains data and parameters of HydraGNN-based graph foundation models trained as a result of the work published in the pre-print "Exascale Multi-Task Graph Foundation Models for Imbalanced, Multi-Fidelity Atomistic Data" by M. Lupo Pasini et al. (https://arxiv.org/abs/2604.15380). We jointly train on 16 open first-principles datasets (544+ million structures covering 85+ elements) using a multi-task architecture with per-dataset heads and a scalable ADIOS2/DDStore data pipeline. On Frontier, we execute six large-scale DeepHyper hyperparameter optimization campaigns in FP64 and promote the top-performing message-passing models to sustained 2,048-node training, yielding a PaiNN-based lead model. The version of HydraGNN used to generate the outputs provided in this release is HydraGNN v5.0 (https://github.com/ORNL/HydraGNN/releases/tag/v5.0) The list of datasets used for the training of the graph foundation model is the following: 1) Alexandria [1] 2) ANI1x [2] 3) MPTrj [3] 4) Open Catalyst 2020 (OC20) [4] 5) Open Catalyst 2022 (OC22) [5] 6) Open Catalyst 2025 (OC25) [6] 7) Open Direct ir Capture 2023 (ODAC23) [7] 8) Open Materials 2024 (OMat24) [8] 9) Open Molecules 2025 (OMol25) [9] 10) OMol25-neutral (subset of OMol25 that contains only molecules with zero total charge) 11) OMol25-non-neutral (subset of OMol25 that contains only molecules with non-zero total charge) 12) Open Polymers 2026 (OPoly2026) [10] 13) Nabla2DFT [11] 14) QCML [12] 15) QM7X [reference 13] 16) transition1x [14] Dataset references: [1] J. Schmidt et al., “A dataset of 175k stable and metastable materials calculated with the PBEsol and SCAN functionals,” Scientific Data, vol. 9, p. 64, 2022. [2] J. S. Smith et al., “The ANI-1ccx and ANI-1x data sets, coupled-cluster and density functional theory properties for molecules,” Scientific Data, vol. 7, p. 134, 2020. [Online]. Available: https: //www.nature.com/articles/s41597-020-0473-z [3] A. Jain et al., “Commentary: The Materials Project: A materials genome approach to accelerating materials innovation,” APL Materials, vol. 1, no. 1, p. 011002, 07 2013. [Online]. Available: https://doi.org/10.1063/1.4812323 [4] L. Chanussot et al., “Open catalyst 2020 (oc20) dataset and community challenges,” ACS Catalysis, vol. 11, no. 10, pp. 6059–6072, 2021. [Online]. Available: https://doi.org/10.1021/acscatal.0c04525 [5] K. Tran et al., “Open catalyst 2022 (oc22) dataset and challenges for oxidation electrocatalysts,” ACS Catalysis, vol. 13, no. 5, pp. 3066–3084, 2023. [Online]. Available: https://doi.org/10.1021/acscatal.2c05426 [6] S. J. Sahoo et al., “The open catalyst 2025 (oc25) dataset and models for solid-liquid interfaces,” arXiv preprint arXiv:2509.17862, 2025. [Online]. Available: https://arxiv.org/abs/2509.17862 [7] A. Sriram et al., “The open DAC 2023 dataset and challenges for sorbent discovery in direct air capture,” ACS Central Science, vol. 10, no. 5, pp. 923–941, 2024. [8] L. Barroso-Luque et al., “Open materials 2024 (omat24) inorganic materials dataset and models,” 2024. [Online]. Available: https://arxiv.org/abs/2410.12771 [9] D. S. Levine et al., “The open molecules 2025 (OMol25) dataset, evaluations, and models,” 2025. [Online]. Available: https://arxiv.org/abs/2505.08762 [10] D. S. Levine et al., The open polymers 2026 (OPoly26) dataset and evaluations,” arXiv preprint arXiv:2512.23117, 2025. [Online]. Available: https://arxiv.org/abs/2512.23117 [11] K. Khrabrov et al., “Nabla2dft: A universal quantum chemistry dataset of drug-like molecules and a benchmark for neural network potentials,” in NeurIPS 2024 Datasets and Benchmarks Track, 2024. [Online]. Available: https://openreview.net/forum?id=ElUrNM9U8c [12] S. Ganscha et al., “The QCML dataset, quantum chemistry reference data from 33.5M DFT and 14.7B semi-empirical calculations,” Scientific Data, vol. 12, p. 406, 2025. [13] J. Hoja et al., “QM7-X, a comprehensive dataset of quantum-mechanical properties spanning the chemical space of small organic molecules,” Scientific Data, vol. 8, p. 43, 2021. [Online]. Available: https://www.nature.com/articles/s41597-021-00812-2 [14] M. Schreiner et al., “Transition1x - a dataset for building generalizable reactive machine learning potentials,” Scientific Data, vol. 9, p. 779, 2022. The folder "datasets_ADIOS2_format" contains the set of pre-processed datasets in Adaptable I/O System (ADIOS) format (https://www.exascaleproject.org/research-project/adios/) that have been used for the development and training of GFMs in this work. The "datasets_ADIOS2_format" directory contains 2 sub-directories, one for the version "v1" of the datasets and one for the version "v2" of the datasets. The version "v1" of the datasets provides values of the total energy as they are extracted from the original data as it was released by the respective institutions. The version "v2" of the datasets provides values of the energy that have been realigned. The realignment was performed by training a linear regression model that predicts the total energy as a function of the chemical composition of the atomistic structure, and then subtract such prediction from the original value of the total energy. Both folders "v1" and "v2" contain 16 sub-directories, each corresponding to an ADIOS2-formatted dataset The folder "DeepHyper-results" contains the configurational files and model's parameters for all the 186 HPO trials that were successfully completed by the scalable hyperparameter optimization (HPO) runs on Frontier. The content of the folder "DeepHyper-results" I structured as follows: 1) task-list.txt: list of mpnn name, jobid, and deephyper task id 2) gfm_${MPNN}_${JOBID}_0.${TASKID}: run directory with checkpoint files 3) gfm_${MPNN}: deephyper summary directory (*.csv) for each specific MPNN type 4) deephyper-experiment-${JOBID}: output and error logs for each job The file "deephyper-sorted.csv" contains the details of each HydraGNN model built and tested by HPO, obtained by merging the (*.csv) filed from each HPO run executed. Out of all the HPO trials, we selected 10 to continue the training of the respective HydraGNN models. Due to limited computational budget available in the LRN070 allocation we could not complete the training till convergence for all these 10 selected models. The folder "models" contains multiple sub-folders, one per each HydraGNN model trained. Each model sub-folder contains the parameters of each HydraGNN model, with multiple checkpoint-restarts. The list of sub-folders are as follows: 1) multidataset_hpo-BEST1-fp64 2) multidataset_hpo-BEST2-fp64 3) multidataset_hpo-BEST3-fp64 4) multidataset_hpo-BEST4-fp64 5) multidataset_hpo-BEST5-fp64 6) multidataset_hpo-BEST6-fp64 7) multidataset_hpo-BEST7-fp64 8) multidataset_hpo-BEST8-fp64 9) multidataset_hpo-BEST9-fp64 10) multidataset_hpo-BEST10-fp64 Within each one of these folders, additional auxiliary log files are provided with descriptions about how the training proceeded. The lead PaiNN-model is contained inside "multidataset_hpo-BEST6-fp64". The file "mlp_branch_weights" contains the parameters of the multi-layer perceptron (MLP) used to reconcile the predictions of the 16 output decoding heads of the HydragNN architectures. The MLP takes in input the chemical composition of the atomistic structure and predicts averaging weights to linearly mix the predictions of each output decoding head toward consolidating them into a single one. The folder "1.1billion-structure-inference" contains 1.1 billion atomistic structures randomly generated. Each structures is associated with energy and forces predicted with the lead-PaiNN model combined with the MLP model for reconciliation of the multi-branch predictions generated by the 16 output decoding heads. The folder "1.1billion-structure-inference" contains 9,300 (*.tar.gz) subdirectories, one per Frontier compute node used to execute the inference at exascale. Once uncompressed, each (*.tar.gz) subdirectory contains an ADIOS2 (*.bp) file container, where each atomistic structure is stored as a PyTorch-Geometric Data object. The file "export_dataset_environment_variables.sh" contains the environment variables that need to be set before running the HydraGNN code to reproduce the results provided in this dataset release. The code that can be used to load the ADIOS2 files, load HydraGNN models, and run inference is available at: https://github.com/ORNL/HydraGNN/releases/tag/v5.0

36 MATERIALS SCIENCE↗
DOE OSTI2025

Hybrid PDES Simulation of HPC Networks Using Zombie Packets

Although high-fidelity network simulations have proven to be reliable and cost-effective tools to peer into architectural questions for high-performance computing (HPC) networks, they incur a high resource cost. The time spent in simulating a single millisecond of network traffic in the highest detail can take hours, even for static, well-behaved traffic patterns such as uniform random. Surrogate models offer a significant reduction in runtime, yet they cannot serve as complete replacements and should only be used when appropriate. Thus, there is a need for hybrid modeling, where high-fidelity simulation and surrogates run side-by-side. Here, we present a surrogate model for HPC networks in which: packets bypass the network, while the network state is left untouched, i.e., suspended. To bypass the network, we use historical data to estimate the arrival time at which every packet should be scheduled at; to suspend the network, all in-flight packets are scheduled to arrive at their destinations, and are kept in the system to awaken as zombies when switching back to high-fidelity. Speedup for a hybrid model is relative to the proportion of surrogate to high-fidelity. This light-weight surrogate obtained up to 76× speedup. Keeping the zombies in the network showed an increase in the accuracy of the high-fidelity simulation on restart when compared to restarting the network from an empty state.

HPC networks↗
DOE OSTI2025

Track reconstruction as a service for collider physics

Optimizing charged-particle track reconstruction algorithms is crucial for efficient event reconstruction in Large Hadron Collider (LHC) experiments due to their significant computational demands. Existing track reconstruction algorithms have been adapted to run on massively parallel coprocessors, such as graphics processing units (GPUs), to reduce processing time. Nevertheless, challenges remain in fully harnessing the computational capacity of coprocessors in a scalable and non-disruptive manner. This paper proposes an inference-as-a-service approach for particle tracking in high energy physics experiments. To evaluate the efficacy of this approach, two distinct tracking algorithms are tested: Patatrack, a rule-based algorithm, and Exa.TrkX, a machine learning-based algorithm. The as-a-service implementations show enhanced GPU utilization and can process requests from multiple CPU cores concurrently without increasing per-request latency. The impact of data transfer is minimal and insignificant compared to running on local coprocessors. This approach greatly improves the computational efficiency of charged particle tracking, providing a solution to the computing challenges anticipated in the High-Luminosity LHC era.

46 INSTRUMENTATION RELATED TO NUCLEAR SCIENCE AND ↗
DOE OSTI2021

Scalable Pattern Matching in Metadata Graphs via Constraint Checking

Pattern matching is a fundamental tool for answering complex graph queries. Unfortunately, existing solutions have limited capabilities: They do not scale to process large graphs and/or support only a restricted set of search templates or usage scenarios. Moreover, the algorithms at the core of the existing techniques are not suitable for today’s graph processing infrastructures relying on horizontal scalability and shared-nothing clusters, as most of these algorithms are inherently sequential and difficult to parallelize. In this article we present an algorithmic pipeline that bases pattern matching on constraint checking. The key intuition is that each vertex and edge participating in a match has to meet a set of constraints implicitly specified by the search template. These constraints can be verified independently and typically are less expensive to compute than searching the full template. The pipeline we propose generates these constraints and iterates over them to eliminate all the vertices and edges that do not participate in any match, thus reducing the background graph to a subgraph that is the union of all template matches—the complete set of all vertices and edges that participate in at least one match. Additional analysis can be performed on this annotated, reduced graph, such as full match enumeration, match counting, or computing vertex/edge centrality. Furthermore, a vertex-centric formulation for constraint checking algorithms exists, and this makes it possible to harness existing high-performance, vertex-centric graph processing frameworks. This technique (i) enables highly scalable pattern matching in metadata (labeled) graphs; (ii) supports arbitrary patterns with 100% precision; (iii) enables tradeoffs between precision and time-to-solution, while always selects all vertices and edges that participate in matches, thus offering 100% recall; and (iv) supports a set of popular data analytics scenarios. We implement our approach on top of HavoqGT, an open-source asynchronous graph processing framework, and demonstrate its advantages through strong and weak scaling experiments on massive scale real-world (up to 257 billion edges) and synthetic (up to 4.4 trillion edges) labeled graphs, respectively, and at scales (1,024 nodes / 36,864 cores), orders of magnitude larger than used in the past for similar problems. This article serves two purposes: First, it synthesises the knowledge accumulated during a long-term project. Second, it presents new system features, usage scenarios, optimizations, and comparisons with related work that strengthen the confidence that pattern matching based on iterative pruning via constraint checking is an effective and scalable approach in practice. The new contributions include the following: (i) We demonstrate the ability of the constraint checking approach to efficiently support two additional search scenarios that often emerge in practice, interactive incremental search and exploratory search. (ii) We empirically compare our solution with two additional state-of-the-art systems, Arabsque and TriAD. (iii) We show the ability of our solution to accommodate a more diverse range of datasets with varying properties, e.g., scale, skewness, label distribution, and match frequency. (iv) We introduce or extend a number of system features (e.g., work aggregation, load balancing, and the ability to cap the generated traffic) and design optimizations and demonstrate their advantages with respect to improving performance and scalability. (v) We present bottleneck analysis and insights into artifacts that influence performance. (vi) We present a theoretical complexity argument that motivates the performance gains we observe.

97 MATHEMATICS AND COMPUTING↗