SEARCH · Engineering Papers

Results for “software design parallel computation”

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.

SourceResearch connectionFrom yearThrough year

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

At least 469 records · Page 26

All sources NASA NTRS DOE OSTI

DOE OSTI2018

Persistent Octrees for Parallel Mesh Refinement Through Non-Volatile Byte-Addressable Memory

We report that octree-based mesh adaptation has enabled simulations of complex physical phenomena. Existing meshing algorithms were proposed with the assumption that computer memory is volatile. Consequently, for failure recovery, the in-core algorithms need to save memory states as snapshots with slow file I/Os. The out-of-core algorithms store octants on disks for persistence. However, neither of them was designed to leverage unique characteristics of non-volatile byte-addressable memory (NVBM). In this paper, we propose a novel data structure Distributed Persistent Merged octree (DPM-octree) for both meshing and in-memory storage of persistent octrees using NVBM. It is a multi-version data structure and can recover from failures using its earlier persistent version stored in NVBM. In addition, we design a feature-directed sampling approach to help dynamically transform the DPM-octree layout for reducing NVBM-induced memory write latency. DPM-octree uses parity trees which are created using erasure coding and stored in NVBM to support low-latency in-memory octant recovery after data loss. DPM-octree has been successfully integrated with Gerris software for simulation of fluid dynamics. Finally, our experimental results with real-world scientific workloads show that DPM-octree scales up to 1.1 billion mesh elements with 1000 processors on the Titan supercomputer.

97 MATHEMATICS AND COMPUTING↗

DOE OSTI2017

RAJA Performance Suite

The RAJA Performance Suite is designed to evaluate performance of the RAJA performance portability library on a wide variety of important high performance computing (HPC) algorithmic lulmels. These kernels assess compiler optimizations and various parallel programming model backends accessible through RAJA, such as OpenMP, CUDA, etc. The Initial version of the suite contains 25 computational kernels, each of which appears in 6 variants: Baseline SequcntiaJ, RAJA SequentiaJ, Baseline OpenMP, RAJA OpenMP, Baseline CUDA, RAJA CUDA. All variants of each kernel perform essentially the same mathematical operations and the loop body code for each kernel is identical across all variants. There are a few kernels, such as those that contain reduction operations, that require CUDA-specific coding for their CUDA variants. ActuaJ computer instructions executed and how they run in parallel differs depending on the parallel programming model backend used and which optimizations are perfonned by the compiler used to build the Perfonnance Suite executable. The Suite will be used primarily by RAJA developers to perform regular assessments of RAJA performance across a range of hardware platforms and compilers as RAJA features are being developed. It will also be used by LLNL hardware and software vendor panners for new defining requirements for future computing platform procurements and acceptance testing. In particular, the RAJA Performance Suite will be used for compiler acceptance testing of the upcoming CORAUSierra machine {initial LLNL delivery expected in late-2017/early 2018) and the CORAL-2 procurement. The Suite will aJso be used to generate concise source code reproducers of compiler and runtime issues we uncover so that we may provide them to relevant vendors to be fixed.

Hornung, RichardD.↗

DOE OSTI2024

xesn: Echo state networks powered by Xarray and Dask

Xesn is a Python package that allows scientists to easily design Echo State Networks (ESNs) for forecasting problems. ESNs are a Recurrent Neural Network architecture introduced by Jaeger (2001) that are part of a class of techniques termed Reservoir Computing. One defining characteristic of these techniques is that all internal weights are determined by a handful of global, scalar parameters, thereby avoiding problems during backpropagation and reducing training time significantly. Because this architecture is conceptually simple, many scientists implement ESNs from scratch, leading to questions about computational performance. Xesn offers a straightforward, standard implementation of ESNs that operates efficiently on CPU and GPU hardware. The package leverages optimization tools to automate the parameter selection process, so that scientists can reduce the time finding a good architecture and focus on using ESNs for their domain application. Importantly, the package flexibly handles forecasting tasks for out-of-core, multi-dimensional datasets, eliminating the need to write parallel programming code. Xesn was initially developed to handle the problem of forecasting weather dynamics, and so it integrates naturally with Python packages that have become familiar to weather and climate scientists such as Xarray (Hoyer & Hamman, 2017). However, the software is ultimately general enough to be utilized in other domains where ESNs have been useful, such as in signal processing (Jaeger & Haas, 2004).

97 MATHEMATICS AND COMPUTING↗

DOE OSTI2026

Elevating SolTrace's Capabilities for the Next Generation of Concentrating Solar Analysis

SolTrace is an open-source Monte Carlo ray tracing software developed at NREL. SolTrace can characterize concentrating solar thermal (CST) collector optical performance and is CST technology agnostic. Shown in Fig. 1, SolTrace is a foundational tool in NREL's CST system and component modeling suite. SolTrace's generic surface elements can flexibly model novel collector and receiver designs to predict spatial and temporal flux distributions - critical to understand for CST component design, performance prediction, and system integration. Since its initial development, SolTrace has over 1,650 references on Google Scholar, over 9,800 downloads since 2017, and has served the CST research and development community as a benchmark of 3rd party verification. SolTrace provides users with many options for defining surface shape and boundaries. However, SolTrace provides limited documentation which can result in a steep learning curve for new users. Additionally, SolTrace lacks the computational performance required to evaluate optical performance of a CST system over the course of a year and/or iteratively over design parameters in a timely manner. To address this, we are working towards a new release of SolTrace that enables increased computational throughput by implementing ray tracing acceleration structures and enabling GPU parallelization. Additionally, we are working to improve SolTrace's usability, accessibility, and maintainability by (1) automating solar position time-dependent simulation processes, (2) creating general CST collector templates of grouped elements, (3) updating the user interface to better visualize model inputs and outputs, and (4) creating a user support network through forums, "how to" videos, and documentation.

14 SOLAR ENERGY↗

DOE OSTI2017

Exploring performance and energy tradeoffs for irregular applications: A case study on the Tilera many-core architecture

High performance, parallel applications with irregular data accesses are becoming a critical workload class for modern systems. In particular, the execution of such workloads on emerging many-core systems is expected to be a significant component of applications in data mining, machine learning, scientific computing and graph analytics. However, power and energy constraints limit the capabilities of individual cores, memory hierarchy and on-chip interconnect of such systems, thus leading to architectural and software trade-os that must be understood in the context of the intended application’s behavior. Irregular applications are notoriously hard to optimize given their data-dependent access patterns, lack of structured locality and complex data structures and code patterns. We have ported two irregular applications, graph community detection using the Louvain method (Grappolo) and high-performance conjugate gradient (HPCCG), to the Tilera many-core system and have conducted a detailed study of platform-independent and platform-specific optimizations that improve their performance as well as reduce their overall energy consumption. To conduct this study, we employ an auto-tuning based approach that explores the optimization design space along three dimensions - memory layout schemes, GCC compiler flag choices and OpenMP loop scheduling options. We leverage MIT’s OpenTuner auto-tuning framework to explore and recommend energy optimal choices for different combinations of parameters. We then conduct an in-depth architectural characterization to understand the memory behavior of the selected workloads. Finally, we perform a correlation study to demonstrate the interplay between the hardware behavior and application characteristics. Using auto-tuning, we demonstrate whole-node energy savings and performance improvements of up to 49:6% and 60% relative to a baseline instantiation, and up to 31% and 45:4% relative to manually optimized variants.

auto tuning↗

NASA NTRS2009

Hardware Implementation of a Bilateral Subtraction Filter

A bilateral subtraction filter has been implemented as a hardware module in the form of a field-programmable gate array (FPGA). In general, a bilateral subtraction filter is a key subsystem of a high-quality stereoscopic machine vision system that utilizes images that are large and/or dense. Bilateral subtraction filters have been implemented in software on general-purpose computers, but the processing speeds attainable in this way even on computers containing the fastest processors are insufficient for real-time applications. The present FPGA bilateral subtraction filter is intended to accelerate processing to real-time speed and to be a prototype of a link in a stereoscopic-machine- vision processing chain, now under development, that would process large and/or dense images in real time and would be implemented in an FPGA. In terms that are necessarily oversimplified for the sake of brevity, a bilateral subtraction filter is a smoothing, edge-preserving filter for suppressing low-frequency noise. The filter operation amounts to replacing the value for each pixel with a weighted average of the values of that pixel and the neighboring pixels in a predefined neighborhood or window (e.g., a 9 9 window). The filter weights depend partly on pixel values and partly on the window size. The present FPGA implementation of a bilateral subtraction filter utilizes a 9 9 window. This implementation was designed to take advantage of the ability to do many of the component computations in parallel pipelines to enable processing of image data at the rate at which they are generated. The filter can be considered to be divided into the following parts (see figure): a) An image pixel pipeline with a 9 9- pixel window generator, b) An array of processing elements; c) An adder tree; d) A smoothing-and-delaying unit; and e) A subtraction unit. After each 9 9 window is created, the affected pixel data are fed to the processing elements. Each processing element is fed the pixel value for its position in the window as well as the pixel value for the central pixel of the window. The absolute difference between these two pixel values is calculated and used as an address in a lookup table. Each processing element has a lookup table, unique for its position in the window, containing the weight coefficients for the Gaussian function for that position. The pixel value is multiplied by the weight, and the outputs of the processing element are the weight and pixel-value weight product. The products and weights are fed to the adder tree. The sum of the products and the sum of the weights are fed to the divider, which computes the sum of products the sum of weights. The output of the divider is denoted the bilateral smoothed image. The smoothing function is a simple weighted average computed over a 3 3 subwindow centered in the 9 9 window. After smoothing, the image is delayed by an additional amount of time needed to match the processing time for computing the bilateral smoothed image. The bilateral smoothed image is then subtracted from the 3 3 smoothed image to produce the final output. The prototype filter as implemented in a commercially available FPGA processes one pixel per clock cycle. Operation at a clock speed of 66 MHz has been demonstrated, and results of a static timing analysis have been interpreted as suggesting that the clock speed could be increased to as much as 100 MHz.

Huertas, Andres↗

DOE OSTI2017

ELSI: A unified software interface for Kohn–Sham electronic structure solvers

Solving the electronic structure from a generalized or standard eigenproblem is often the bottleneck in large scale calculations based on Kohn-Sham density-functional theory. This problem must be addressed by essentially all current electronic structure codes, based on similar matrix expressions, and by high-performance computation. We here present a unified software interface, ELSI, to access different strategies that address the Kohn-Sham eigenvalue problem. Currently supported algorithms include the dense generalized eigensolver library ELPA, the orbital minimization method implemented in libOMM, and the pole expansion and selected inversion (PEXSI) approach with lower computational complexity for semilocal density functionals. The ELSI interface aims to simplify the implementation and optimal use of the different strategies, by offering (a) a unified software framework designed for the electronic structure solvers in Kohn-Sham density-functional theory; (b) reasonable default parameters for a chosen solver; (c) automatic conversion between input and internal working matrix formats, and in the future (d) recommendation of the optimal solver depending on the specific problem. As a result, comparative benchmarks are shown for system sizes up to 11,520 atoms (172,800 basis functions) on distributed memory supercomputing architectures.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

NASA NTRSDate not supplied

Predictive Modeling of Carbon Ablators

Efforts to build a Predictive Material Modeling (PMM) framework from the micro-scale to the macro-scale are presented in this abstract. To reduce the need for extensive testing, accelerate the design cycle process, and reduce uncertainty margins applied to final designs, NASA is developing simulation and modeling tools that enable characterization of material properties and response to high-enthalpy environments. The Porous Microstructure Analysis (PuMA) code has been developed for computing macroscale (volume averaged) properties of porous materials using microscale images from micro-computed tomography (micro-CT). Microscale modeling requires a realistic representation of a material microstructure; these are obtained either synthetically during the design of the material or through X-ray micro-CT. Volume averaged properties are then used to inform macroscale material response models, such as those implemented in the Porous-material Analysis Toolbox based on OpenFOAM (PATO) software, also actively developed by NASA. The computational model in PATO is a generic heat and mass transfer model for porous reactive materials containing several solid phases and a single gas phase. The detailed chemical interactions occurring between the solid phases and the gas phase are modeled at the pore scale assuming local thermal equilibrium. These tools were developed to efficiently interface with other pre-existing codes such as SPARTA (direct simulation Monte Carlo), DPLR (hypersonic CFD), NEQAIR (radiative transport) and DAKOTA (uncertainty quantification and optimization). Detailed flight data (Mars Science Laboratory [MSL] Entry Descent and Landing Instrument [MEDLI]) is critical for validating these computational tools for NASA applications. Examples of modeling ablative material response using these codes will be presented including 3D simulations of the full-scale heatshield of the MSL capsule. The simulations demonstrate the ability of the modern material response code, PATO, to handle the material response of geometrically complex and large domains, through the use of massively parallel computations.

Thermal Protection Systems↗

NASA NTRSDate not supplied

Predictive Modeling of Carbon Ablators Using Micro and Macro-Scale Modeling

Thermal Protection Systems↗

DOE OSTI2023

MOOSE: A Modular Platform for Fission and Fusion Multiphysics

The Multiphysics Object-Oriented Simulation Environment (MOOSE) Framework, as well as MOOSE-based simulation tools, have accelerated the development of fission energy and advanced reactor technologies through the United States Department of Energy, Office of Nuclear Science, Nuclear Energy Advanced Modeling & Simulation (NEAMS) Program. MOOSE contains a complete platform of multiphysics simulation capabilities, capable of running on massively parallel systems, and is developed in an open-source manner with great attention paid to high-quality software quality assurance practices. This overall approach could greatly benefit the fusion energy community, which requires rapid design iteration and improvement in order to facilitate the successful development of fusion as an alternative energy source to fossil fuels. In the first half of this talk, applications of MOOSE and MOOSE-based tools for advanced reactor designs will be showcased, as well as MOOSE ecosystem infrastructure (such as the NEAMS Virtual Test Bed) that enables and accelerates fission reactor design. In the second half, a discussion of how the MOOSE approach to modeling and simulation is currently being applied internationally in fusion energy research and development at the United Kingdom Atomic Energy Authority will be discussed, and ongoing/future domestic research efforts will be highlighted.

11 NUCLEAR FUEL CYCLE AND FUEL MATERIALS↗

NASA NTRS1998

The SGI/Cray T3E: Experiences and Insights

The NASA Goddard Space Flight Center is home to the fifth most powerful supercomputer in the world, a 1024 processor SGI/Cray T3E-600. The original 512 processor system was placed at Goddard in March, 1997 as part of a cooperative agreement between the High Performance Computing and Communications Program's Earth and Space Sciences Project (ESS) and SGI/Cray Research. The goal of this system is to facilitate achievement of the Project milestones of 10, 50 and 100 GFLOPS sustained performance on selected Earth and space science application codes. The additional 512 processors were purchased in March, 1998 by the NASA Earth Science Enterprise for the NASA Seasonal to Interannual Prediction Project (NSIPP). These two "halves" still operate as a single system, and must satisfy the unique requirements of both aforementioned groups, as well as guest researchers from the Earth, space, microgravity, manned space flight and aeronautics communities. Few large scalable parallel systems are configured for capability computing, so models are hard to find. This unique environment has created a challenging system administration task, and has yielded some insights into the supercomputing needs of the various NASA Enterprises, as well as insights into the strengths and weaknesses of the T3E architecture and software. The T3E is a distributed memory system in which the processing elements (PE's) are connected by a low latency, high bandwidth bidirectional 3-D torus. Due to the focus on high speed communication between PE's, the T3E requires PE's to be allocated contiguously per job. Further, jobs will only execute on the user specified number of PE's and PE timesharing is possible but impractical. With a highly varied job mix in both size and runtime of jobs, the resulting scenario is PE fragmentation and an inability to achieve near 100% utilization. SGI/Cray has provided several scheduling and configuration tools to minimize the impact of fragmentation. These tools include PScheD (the political scheduler), GRM (the global resource manager) and NQE (the Network Queuing Environment). Features and impact of these tools will be discussed, as will resulting performance and utilization data. As a distributed memory system, the T3E is designed to be programmed through explicit message passing. Consequently, certain assumptions related to code design are made by the operating system (UNICOS/mk) and its scheduling tools. With the exception of HPF, which does run on the T3E, however poorly, alternative programming styles have the potential to impact the T3E in unexpected and undesirable ways. Several examples will be presented (preceeded with the disclaimer, "Don't try this at home! Violators will be prosecuted!")

Bernard, Lisa Hamet↗

DOE OSTI2016

CTF Parallel Performance Improvements

CTF is a modernized version of COBRA-TF (Coolant Boiling in Rod Arrays-Two Fluid), which is a thermal hydraulic (T/H) sub-channel code based on a two-phase, two-fluid model that formulates the conservation equations of mass, energy, and momentum for three fields of vapor, continuous liquid, and entrained liquid droplets. Under the Consortium for Advanced Simulation of Light Water Reactors (CASL) program sponsored by the U.S. Department of Energy, CTF is being further developed and improved for modeling and simulation of light water reactors. The code improvements for predicting T/H responses of pressurized water reactor (PWR) cores are focused on its applications to specific challenge problems deemed significant to the industry, such as departure from nucleate boiling (DNB) and crud-induced power shift. The code is also being used for T/H feedback in normal operating condition depletions in PWR and boiling water reactor designs in the reactor core simulator, Virtual Environment for Reactor Applications Core Simulator (VERA-CS), being developed by CASL. CTF modifications under the CASL program include software optimization, new closure models, and parallelization for modeling full reactor core T/H responses. The purpose of this work was to improve the parallel performance of CTF. CTF was originally parallelized via a domain-decomposition strategy using the Message Passing Interface (MPI), in which the basis of a solution domain was a physical assembly in the model. In other words, a user who wanted to perform a parallel solution with CTF had to provide the code one processor per assembly in the model (e.g., 56 cores for a 56 assembly quarter-core model, or 193 cores for a 193 assembly full-core model). This design was rigid, demanding a very specific number of processors for a model; furthermore, when CTF was run in VERA-CS-which typically uses thousands of processors- many processors sat idle during the CTF solve because CTF was unable to use any more processors than there are physical assemblies. This was not necessarily a problem if the CTF execution speed was very fast, but the average time spent in a CTF solve for prototypical PWR operating conditions was significant (i.e., over 20 % of the simulation wall time was being spent in CTF for a standard core depletion simulation). Larger, more computationally intensive simulations performed in support of the CASL DNB challenge problem demonstrated a need for improvements in this original parallelization approach. The specific goal of this work was to allow CTF to use more processors than there are physical assemblies in the model, which would not only speed up CTF and improve the overall efficiency of VERA-CS but also give users more-flexible options for executing their simulations. (authors)

21 SPECIFIC NUCLEAR REACTORS AND ASSOCIATED PLANTS↗

DOE OSTI2015

Developing Uintah's Runtime System for Forthcoming Architectures

The need to solve ever-more complex science and engineering problems on computer architectures that are rapidly evolving poses considerable challenges for modern simulation frameworks and packages. While the decomposition of software into a programming model that generates a task-graph for execution by a runtime system make portability and performance possible, it also imposes considerable demands on that runtime system. Here, the challenge of meeting those demands for near-term and longer term systems in the context of the Uintah framework is considered in key areas such as support for data structures, tasks on heterogeneous architectures, performance portability, power management and designing for resilience by the use of replication based upon adaptive mesh refinement processes is addressed. Examples of techniques in these areas are used to illustrate performance improvements obtained for present large-scale systems and the needs of proposed systems considered.

97 MATHEMATICS AND COMPUTING↗

NASA NTRS2022

Parallel Grand-Canonical Monte Carlo (ParaGrandMC) User’s Manual Version 2.0

This manual describes the commands and command line options for the Parallel Grand Canonical Monte Carlo version 2.0 (ParaGrandMC.2.0) simulation code. This is a highly scalable parallel FORTRAN 2003 code for simulating the thermodynamic evolution of materials at the atomic level, and predicting their thermodynamic state, phase diagram, chemical composition and mechanical properties. The code is specifically designed to simulate multi-component alloy systems, predict solid-state phase transformations such as austenite-martensite transformations, precipitate formation, recrystallization, capillary effects at interfaces, surface absorption, etc., which can aid the design of novel metallic alloys. While the software is mainly tailored for modeling metal alloys, it can also be used for other types of solid-state systems, and to some degree for liquid or gaseous systems, including multiphase systems forming solid-liquid-gas interfaces. In addition to performing Monte Carlo (MC) simulations, the code can also perform Molecular Dynamics (MD) and Langevin Dynamics (LD) simulations, which can be combined and interchanged with MC for faster and more efficient system evolution. A detailed description of the MC part of the code is provided in the NASA ParaGrandMC report: NASA/CR–2016-219202; http://www.sti.nasa.gov.

High performance computing↗

DOE OSTI2022

Algorithm 1028: VTMOP: Solver for Blackbox Multiobjective Optimization Problems

VTMOP is a Fortran 2008 software package containing two Fortran modules for solving computationally expensive bound-constrained blackbox multiobjective optimization problems. VTMOP implements the algorithm of [32], which handles two or more objectives, does not require any derivatives, and produces well-distributed points over the Pareto front. The first module contains a general framework for solving multiobjective optimization problems by combining response surface methodology, trust region methodology, and an adaptive weighting scheme. The second module features a driver subroutine that implements this framework when the objective functions can be wrapped as a Fortran subroutine. Lastly, support is provided for both serial and parallel execution paradigms, and VTMOP is demonstrated on several test problems as well as one real-world problem in the area of particle accelerator optimization.

97 MATHEMATICS AND COMPUTING↗

NASA NTRS2006

Promoted-Combustion Chamber with Induction Heating Coil

An improved promoted-combustion system has been developed for studying the effects of elevated temperatures on the flammability of metals in pure oxygen. In prior promoted-combustion chambers, initial temperatures of metal specimens in experiments have been limited to the temperatures of gas supplies, usually near room temperature. Although limited elevated temperature promoted-combustion chambers have been developed using water-cooled induction coils for preheating specimens, these designs have been limited to low-pressure operation due to the hollow induction coil. In contrast, the improved promoted-combustion chamber can sustain a pressure up to 10 kpsi (69 MPa) and, through utilization of a solid induction coil, is capable of preheating a metal specimen up to its melting point [potentially in excess of 2,000 F (approximately equal to 1,100 C)]. Hence, the improved promoted combustion chamber makes a greater range of physical conditions and material properties accessible for experimentation. The chamber consists of a vertical cylindrical housing with an inner diameter of 8 in. (20.32 cm) and an inner height of 20.4 in. (51.81 cm). A threaded, sealing cover at one end of the housing can be unscrewed to gain access for installing a specimen. Inlet and outlet ports for gases are provided. Six openings arranged in a helical pattern in the chamber wall contain sealed sapphire windows for viewing an experiment in progress. The base of the chamber contains pressure-sealed electrical connectors for supplying power to the induction coil. The connectors feature a unique design that prevents induction heating of the housing and the pressure sealing surfaces; this is important because if such spurious induction heating were allowed to occur, chamber pressure could be lost. The induction coil is 10 in. (25.4 cm) long and is fitted with a specimen holder at its upper end. At its lower end, the induction coil is mounted on a ceramic base, which affords thermal insulation to prevent heating of the base of the chamber during use. A sapphire cylinder protects the coil against slag generated during an experiment. The induction coil is energized by a 6-kW water-cooled power supply operating at a frequency of 400 kHz. The induction coil is part of a parallel-tuned circuit, the tuning of which is used to adjust the coupling of power to the specimen. The chamber is mounted on a test stand along with pumps, valves, and plumbing for transferring pressurized gas into and out of the chamber. In addition to multiple video cameras aimed through the windows encircling the chamber, the chamber is instrumented with gauges for monitoring the progress of an experiment. One of the gauges is a dual-frequency infrared temperature transducer aimed at the specimen through one window. Chamber operation is achieved via a console that contains a computer running apparatus-specific software, a video recorder, and real-time video monitors. For safety, a blast wall separates the console from the test stand.

Richardson, Erin↗

DOE OSTI2026

Performance-Aligned LLMs for Generating Fast HPC Code

Optimizing scientific software is a difficult task because codebases are often large and complex, and performance can depend upon several factors including the algorithm, its implementation, and hardware among others. Causes of poor performance can originate from disparate sources and be difficult to diagnose. Recent years have seen a multitude of work that use large language models (LLMs) to assist in software development tasks. However, these tools are trained to model the distribution of code as text, and are not specifically designed to understand performance aspects of code. In this work, we introduce a reinforcement learning based methodology to align the outputs of code LLMs with performance. This allows us to build upon the current code modeling capabilities of LLMs and extend them to generate better performing code. Here, we demonstrate that our fine-tuned model improves the expected speedup of generated code over base models for a set of benchmark tasks from 0.9 to 1.6 for serial code and 1.9 to 4.5 for OpenMP parallel code.

Computer science↗

DOE OSTI2022

Direction-optimizing Label Propagation Framework for Structure Detection in Graphs: Design, Implementation, and Experimental Analysis

Label Propagation is not only a well-known machine learning algorithm for classification but also an effective method for discovering communities and connected components in networks. We propose a new Direction-optimizing Label Propagation Algorithm (DOLPA) framework that enhances the performance of the standard Label Propagation Algorithm (LPA), increases its scalability, and extends its versatility and application scope. As a central feature, the DOLPA framework relies on the use of frontiers and alternates between label push and label pull operations to attain high performance. It is formulated in such a way that the same basic algorithm can be used for finding communities or connected components in graphs by only changing the objective function used. Additionally, DOLPA has parameters for tuning the processing order of vertices in a graph to reduce the number of edges visited and improve the quality of solution obtained. We present the design and implementation of the enhanced algorithm as well as our shared-memory parallelization of it using OpenMP. We also present an extensive experimental evaluation of our implementations using the LFR benchmark and real-world networks drawn from various domains. Compared with an implementation of LPA for community detection available in a widely used network analysis software, we achieve at most five times the F-Score while maintaining similar runtime for graphs with overlapping communities. We also compare DOLPA against an implementation of the Louvain method for community detection using the same LFR-graphs and show that DOLPA achieves about three times the F-Score at just 10% of the runtime. For connected component decomposition, our algorithm achieves orders of magnitude speedups over the basic LP-based algorithm on large-diameter graphs, up to 13.2× speedup over the Shiloach-Vishkin algorithm, and up to 1.6× speedup over Afforest on an Intel Xeon processor using 40 threads.

97 MATHEMATICS AND COMPUTING↗