Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “distributed memory algorithm”

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 343 records · Page 19

Improved Evaluation of Large Network Matrices for Linear Power Flow Within Optimization Problems

This work presents methods for evaluating the Power Transfer Distribution Factor (PTDF) and Line Outage Distribution Factor (LODF) matrices by employing sparse linear algebra for large-scale computing applications. These matrices play a critical role in many power system applications, such as the Unit Commitment Problem (UC), pre- and post-contingency power flow analysis, and transmission expansion. These matrices are typically dense, which means they require a significant amount of time and memory to be computed for large networks. However, by analyzing the structure of the matrices and their computation method, it is possible to use reduced memory methods based on sparse matrix operations. This paper shows that sparse linear algebra algorithms are faster and require less memory and time than traditional dense approaches. Additionally, we explore the effect of matrix sparsification by eliminating trailing digits on power flow calculations.

large scale↗

Parallel phase model : a programming model for high-end parallel machines with manycores.

This paper presents a parallel programming model, Parallel Phase Model (PPM), for next-generation high-end parallel machines based on a distributed memory architecture consisting of a networked cluster of nodes with a large number of cores on each node. PPM has a unified high-level programming abstraction that facilitates the design and implementation of parallel algorithms to exploit both the parallelism of the many cores and the parallelism at the cluster level. The programming abstraction will be suitable for expressing both fine-grained and coarse-grained parallelism. It includes a few high-level parallel programming language constructs that can be added as an extension to an existing (sequential or parallel) programming language such as C; and the implementation of PPM also includes a light-weight runtime library that runs on top of an existing network communication software layer (e.g. MPI). Design philosophy of PPM and details of the programming abstraction are also presented. Several unstructured applications that inherently require high-volume random fine-grained data accesses have been implemented in PPM with very promising results.

99 GENERAL AND MISCELLANEOUS↗

Progress on Optimizing Wind Farms and Rotor Designs Using Adjoints

Modern wind plants are increasingly tasked with multiple performance objectives. In addition to designing plants that maximize power output and minimize the levelized cost of energy (LCOE), the design and operation of wind plants is increasingly influenced by challenges regarding grid integration of variable generation renewables. This places a growing emphasis on making wind plants more controllable and predictable. WindSE is a Reynolds-averaged Navier-Stokes (RANS) model designed around analytical gradient and adjoint methods, with the ability to capture terrain-induced effects, as shown in Figure 1. The recent addition of an unsteady solver with an actuator line method (ALM) and ongoing work to enable massively parallel optimizations gives it a unique niche to explore coupled plant-level controls and design problems. This code is an open source python package built on the FEniCS framework that utilizes fast, parallel PETSc solvers to model fluid flow throughout wind-farm scale domains. Two recent studies performed using WindSE demonstrate the capability to optimize under a wide variety of flow conditions and objective functions. In the first, we present an optimization focused on modifying the layout of a wind farm with a fixed number of turbines for maximum total power output [1]. This study highlights the ability to quickly perform simulations using the steady Navier-Stokes solver combined with rotors represented as actuator disks while also stressing the importance of capturing terrain-induced effects. Gradient-based optimization using the RANS equations is viable due to the inclusion of efficiently computed adjoint derivatives. We interpret the physical results of the optimal layout and also discuss the computational cost of scaling to larger problems. In the second study, we present the capabilities of the unsteady Navier-Stokes solver, where rotor-blade profiles represented by actuator lines are optimized to enhance wake steering effects and overall power production [2]. We quantify the wind plant performance gains obtained from this type of simultaneous control co-design optimization as compared to optimizing the blade design and yaw independently. Figure 2 shows the differences between a baseline two-turbine system and an optimized system where we fine-tune the blade chord profile. Results and challenges from each study are quickly summarized and used to motivate the current development efforts within WindSE. Current and future work is focused on enabling higher-resolution studies with more degrees of freedom through parallelization of both the simulation and optimization algorithms. We present benchmarking results to show that WindSE performs well in both weak- and strong-scaling tests and further demonstrate that the optimizer obtains the same convergence rates in both shared- and distributed-memory environments. Using larger wind farms, we can study deep-array effects within an optimization context, allowing the use of objective functions that have been previously unstudied. As an example, we present ongoing work on a blockage metric which characterizes the loss of available kinetic energy due to wake effects from multiple upstream turbines.

adjoint optimization↗

Distributed Halide

Many image processing tasks are naturally expressed as a pipeline of small computational kernels known as stencils. Halide is a popular domain-specific language and compiler designed to implement image processing algorithms. Halide uses simple language constructs to express what to compute and a separate scheduling co-language for expressing when and where to perform the computation. This approach has demonstrated performance comparable to or better than hand-optimized code. Until now, however, Halide has been restricted to parallel shared memory execution, limiting its performance for memory-bandwidth-bound pipelines or large-scale image processing tasks. We present an extension to Halide to support distributed-memory parallel execution of complex stencil pipelines. These extensions compose with the existing scheduling constructs in Halide, allowing expression of complex computation and communication strategies. Existing Halide applications can be distributed with minimal changes, allowing programmers to explore the tradeoff between recomputation and communication with little effort. Approximately 10 new of lines code are needed even for a 200 line, 99 stage application. On nine image processing benchmarks, our extensions give up to a 1.4× speedup on a single node over regular multithreaded execution with the same number of cores, by mitigating the effects of non-uniform memory access. The distributed benchmarks achieve up to 18× speedup on a 16 node testing machine and up to 57× speedup on 64 nodes of the NERSC Cori supercomputer.

97 MATHEMATICS AND COMPUTING↗

A Comparison of PETSC Library and HPF Implementations of an Archetypal PDE Computation

Two paradigms for distributed-memory parallel computation that free the application programmer from the details of message passing are compared for an archetypal structured scientific computation a nonlinear, structured-grid partial differential equation boundary value problem using the same algorithm on the same hardware. Both paradigms, parallel libraries represented by Argonne's PETSC, and parallel languages represented by the Portland Group's HPF, are found to be easy to use for this problem class, and both are reasonably effective in exploiting concurrency after a short learning curve. The level of involvement required by the application programmer under either paradigm includes specification of the data partitioning (corresponding to a geometrically simple decomposition of the domain of the PDE). Programming in SPAM style for the PETSC library requires writing the routines that discretize the PDE and its Jacobian, managing subdomain-to-processor mappings (affine global- to-local index mappings), and interfacing to library solver routines. Programming for HPF requires a complete sequential implementation of the same algorithm, introducing concurrency through subdomain blocking (an effort similar to the index mapping), and modest experimentation with rewriting loops to elucidate to the compiler the latent concurrency. Correctness and scalability are cross-validated on up to 32 nodes of an IBM SP2.

Hayder, M. Ehtesham↗

Concurrent Monte Carlo transport and fluence optimization with fluence adjusting scalable transport Monte Carlo

Purpose: The future of radiation therapy will require advanced inverse planning solutions to support single-arc, multiple-arc, and “4π” delivery modes, which present unique challenges in finding an optimal treatment plan over a vast search space, while still preserving dosimetric accuracy. The successful clinical implementation of such methods would benefit from Monte Carlo (MC) based dose calculation methods, which can offer improvements in dosimetric accuracy when compared to deterministic methods. The standard method for MC based treatment planning optimization leverages the accuracy of the MC dose calculation and efficiency of well-developed optimization methods, by precalculating the fluence to dose relationship within a patient with MC methods and subsequently optimizing the fluence weights. However, the sequential nature of this implementation is computationally time consuming and memory intensive. Methods to reduce the overhead of the MC precalculation have been explored in the past, demonstrating promising reductions of computational time overhead, but with limited impact on the memory overhead due to the sequential nature of the dose calculation and fluence optimization. The authors propose an entirely new form of “concurrent” Monte Carlo treat plan optimization: a platform which optimizes the fluence during the dose calculation, reduces wasted computation time being spent on beamlets that weakly contribute to the final dose distribution, and requires only a low memory footprint to function. In this initial investigation, the authors explore the key theoretical and practical considerations of optimizing fluence in such a manner. Methods: The authors present a novel derivation and implementation of a gradient descent algorithm that allows for optimization during MC particle transport, based on highly stochastic information generated through particle transport of very few histories. A gradient rescaling and renormalization algorithm, and the concept of momentum from stochastic gradient descent were used to address obstacles unique to performing gradient descent fluence optimization during MC particle transport. The authors have applied their method to two simple geometrical phantoms, and one clinical patient geometry to examine the capability of this platform to generate conformal plans as well as assess its computational scaling and efficiency, respectively. Results: The authors obtain a reduction of at least 50% in total histories transported in their investigation compared to a theoretical unweighted beamlet calculation and subsequent fluence optimization method, and observe a roughly fixed optimization time overhead consisting of ∼10% of the total computation time in all cases. Finally, the authors demonstrate a negligible increase in memory overhead of ∼7–8 MB to allow for optimization of a clinical patient geometry surrounded by 36 beams using their platform. Conclusions: This study demonstrates a fluence optimization approach, which could significantly improve the development of next generation radiation therapy solutions while incurring minimal additional computational overhead.

60 APPLIED LIFE SCIENCES↗

Streaming data analytics via message passing with application to graph algorithms

The need to process streaming data, which arrives continuously at high-volume in real-time, arises in a variety of contexts including data produced by experiments, collections of environmental or network sensors, and running simulations. Streaming data can also be formulated as queries or transactions which operate on a large dynamic data store, e.g. a distributed database. We describe a lightweight, portable framework named PHISH which enables a set of independent processes to compute on a stream of data in a distributed-memory parallel manner. Datums are routed between processes in patterns defined by the application. PHISH can run on top of either message-passing via MPI or sockets via ZMQ. The former means streaming computations can be run on any parallel machine which supports MPI; the latter allows them to run on a heterogeneous, geographically dispersed network of machines. We illustrate how PHISH can support streaming MapReduce operations, and describe streaming versions of three algorithms for large, sparse graph analytics: triangle enumeration, subgraph isomorphism matching, and connected component finding. Lastly, we also provide benchmark timings for MPI versus socket performance of several kernel operations useful in streaming algorithms.

97 MATHEMATICS AND COMPUTING↗

Computation of Coupled Thermal-Fluid Problems in Distributed Memory Environment

The thermal-fluid coupling problems are very important to aerospace and engineering applications. Instead of analyzing heat transfer and fluid flow separately, this study merged two well-accepted engineering solution methods, SINDA for thermal analysis and FDNS for fluid flow simulation, into a unified multi-disciplinary thermal fluid prediction method. A fully conservative patched grid interface algorithm for arbitrary two-dimensional and three-dimensional geometry has been developed. The state-of-the-art parallel computing concept was used to couple SINDA and FDNS for the communication of boundary conditions through PVM (Parallel Virtual Machine) libraries. Therefore, the thermal analysis performed by SINDA and the fluid flow calculated by FDNS are fully coupled to obtain steady state or transient solutions. The natural convection between two thick-walled eccentric tubes was calculated and the predicted results match the experiment data perfectly. A 3-D rocket engine model and a real 3-D SSME geometry were used to test the current model, and the reasonable temperature field was obtained.

Wei, H.↗

Scalable measurement error mitigation via iterative bayesian unfolding

Measurement errors are a significant obstacle to achieving scalable quantum computation. To counteract systematic readout errors, researchers have developed postprocessing techniques known as measurement error mitigation methods. However, these methods face a tradeoff between scalability and returning nonnegative probabilities. In this paper, we present a solution to overcome this challenge. Our approach focuses on iterative Bayesian unfolding, a standard mitigation technique used in high-energy physics experiments, and implements it in a scalable way. We demonstrate our method on experimental Greenberger-Horne-Zeilinger state preparation on up to 127 qubits and on the Bernstein-Vazirani algorithm on up to 26 qubits. Compared to state-of-the-art methods (such as M3), our implementation guarantees valid probability distributions, returns comparable or better-mitigated results, and does so without a noticeable time and memory overhead. Published by the American Physical Society 2024

Pokharel, Bibek (ORCID:0000000342841353)↗

Scalable Computation of Topological Abstractions for Scalar Data

Topological data analysis has become an important tool for large scale scalar data analysis and visualization, efficiently extracting the inherent structure and features of interest of the data. However, with growing dataset sizes and complexity, it is increasingly becoming infeasible to compute topological abstractions of interest in serial and on single machines. This paper presents the state of the art in the scalable computation of topological abstractions on scalar data, in shared memory parallel on single machines, and in distributed memory parallel on multiple machines. We highlight results for set‐based, graph‐based and complex‐based abstractions and organize the state of the art based on this taxonomy. The paper identifies parallelization and distribution techniques common in topological algorithms and highlights further areas of interest with underdeveloped efforts.

97 MATHEMATICS AND COMPUTING↗

A multiarchitecture parallel-processing development environment

A description is given of the hardware and software of a multiprocessor test bed - the second generation Hypercluster system. The Hypercluster architecture consists of a standard hypercube distributed-memory topology, with multiprocessor shared-memory nodes. By using standard, off-the-shelf hardware, the system can be upgraded to use rapidly improving computer technology. The Hypercluster's multiarchitecture nature makes it suitable for researching parallel algorithms in computational field simulation applications (e.g., computational fluid dynamics). The dedicated test-bed environment of the Hypercluster and its custom-built software allows experiments with various parallel-processing concepts such as message passing algorithms, debugging tools, and computational 'steering'. Such research would be difficult, if not impossible, to achieve on shared, commercial systems.

Townsend, Scott↗

A novel digital pulse processing architecture for nuclear instrumentation

The field of nuclear instrumentation covers a wide range of applications, including counting, spectrometry, pulse shape discrimination and multi-channel coincidence. These applications are the topic of many researches, new algorithms and implementations are constantly proposed thanks to advances in digital signal processing. However, these improvements are not yet implemented in instrumentation devices. This is especially true for neutron-gamma discrimination applications which traditionally use charge comparison method while literature proposes other algorithms based on frequency domain or wavelet theory which show better performances. Another example is pileups which are generally rejected while pileup correction algorithms also exist. These processes are traditionally performed offline due to two issues. The first is the Poissonian characteristic of the signal, composed of random arrival pulses which requires to current architectures to work in data flow. The second is the real-time requirement, which implies losing pulses when the pulse rate is too high. Despite the possibility of treating the pulses independently from each other, current architectures paralyze the acquisition of the signal during the processing of a pulse. This loss is called dead-time. These two issues have led current architectures to use dedicated solutions based on re-configurable components like Field Programmable Gate Arrays (FPGAs) to overcome the need of performance necessary to deal with dead-time. However, dedicated hardware algorithm implementations on re-configurable technologies are complex and time-consuming. For all these reasons, a programmable Digital pulse Processing (DPP) architecture in a high level language such as Cor C++ which can reduce dead-time would be worthwhile for nuclear instrumentation. This would reduce prototyping and test duration by reducing the level of hardware expertise to implement new algorithms. However, today's programmable solutions do not meet the need of performance to operate online and not allow scaling with the increase in the number of measurement channel. That is why an innovative DPP architecture is proposed in this paper. This architecture is able to overcome dead-time while being programmable and is flexible with the number of measurement channel. Proposed architecture is based on an innovative execution model for pulse processing applications which can be summarized as follow. The signal is not composed of pulses only, consequently, pulses processing does not have to operate on the entire signal. Therefore, the first step of our proposal is pulse extraction by the use of dedicated components named pulse extractors. The triggering step can be achieved after the analog-to-digital conversion without any signal shaping or filtering stages. Pileup detection and accurate pulse time stamping are done at this stage. Any application downstream this step can work on adaptive variable-sized array of samples simplifying pulse processing methods. Then, once the data flow is broken, it is possible to distribute pulses on Functional Units (FUs) which perform processing. As the date of each pulse is known, they can be processed individually out-of-order to provide the results. To manage the pulses distribution, a scheduler and an interconnection network are used. pulses are distributed on the first FU which is not busy without congesting the interconnection network. For this reason, the process duration does not result anymore in dead-time if there are enough FUs. FUs are designed to be standalone and to comprises at least a programmable general purpose processor (ARM, Microblaze) allowing the implementation of complex algorithms without any modification of the hardware. An acquisition chain is composed of a succession of algorithms which lead to organize our FUs as a software macro-pipeline, A simple approach consists in assigning one algorithm per FU. Consequently, the global latency becomes the worst latency of algorithms execution on FU. Moreover, as algorithms are executed locally - i.e. on a FU - this approach limits shared memory requirement. To handle multichannel, we propose FUs sharing, this approach maximize the chance to find a non-busy FU to process an incoming pulse. This is possible since each channel receive random event independently, the pulse extractors associated to them do not necessarily need to access simultaneously to all Computing resources at the same time to distribute their pulses. The major contribution of this paper is the proposition of an execution model and its associated hardware programmable architecture for digital pulse processing that can handle multiple acquisition channels while maintaining the scalability thanks to the use of shared resources. This execution model and associated architecture are validated by simulation of a cycle accurate architecture SystemC model. Proposed architecture shows promising results in terms of scalability while maintaining zero dead-time. This work also permit the sizing of hardware resources requirement required for a predefined set of applications. Future work will focus on the interconnection network and a scheduling policy that can exploit the variable-length of pulses. Then, the hardware implementation of this architecture will be performed and tested for a representative set of application.

46 INSTRUMENTATION RELATED TO NUCLEAR SCIENCE AND ↗

Evolution of CMS Workload Management Towards Multicore Job Support

The successful exploitation of multicore processor architectures is a key element of the LHC distributed computing system in the coming era of the LHC Run 2. High-pileup complex-collision events represent a challenge for the traditional sequential programming in terms of memory and processing time budget. The CMS data production and processing framework is introducing the parallel execution of the reconstruction and simulation algorithms to overcome these limitations. CMS plans to execute multicore jobs while still supporting singlecore processing for other tasks difficult to parallelize, such as user analysis. The CMS strategy for job management thus aims at integrating single and multicore job scheduling across the Grid. This is accomplished by employing multicore pilots with internal dynamic partitioning of the allocated resources, capable of running payloads of various core counts simultaneously. An extensive test programme has been conducted to enable multicore scheduling with the various local batch systems available at CMS sites, with the focus on the Tier-0 and Tier-1s, responsible during 2015 of the prompt data reconstruction. Scale tests have been run to analyse the performance of this scheduling strategy and ensure an efficient use of the distributed resources. This paper presents the evolution of the CMS job management and resource provisioning systems in order to support this hybrid scheduling model, as well as its deployment and performance tests, which will enable CMS to transition to a multicore production model for the second LHC run.

Perez-Calero Yzquierdo, A.↗

A Parallel EM Algorithm for Model-Based Clustering Applied to the Exploration of Large Spatio-Temporal Data

We develop a parallel EM algorithm for multivariate Gaussian mixture models and use it to perform model-based clustering of a large climate data set. Three variants of the EM algorithm are reformulated in parallel and a new variant that is faster is presented. All are implemented using the single program, multiple data (SPMD) programming model, which is able to take advantage of the combined collective memory of large distributed computer architectures to process larger data sets. Displays of the estimated mixture model rather than the data allow us to explore multivariate relationships in a way that scales to arbitrary size data. We study the performance of our methodology on simulated data and apply our methodology to a high resolution climate dataset produced by the community atmosphere model (CAM5). This article has supplementary material online.

Chen, Wei-Chen↗

MICADO: Parallel implementation of a 2D-1D iterative algorithm for the 3D neutron transport problem in prismatic geometries

The large increase in computing power over the past few years now makes it possible to consider developing 3D full-core heterogeneous deterministic neutron transport solvers for reference calculations. Among all approaches presented in the literature, the method first introduced in [1] seems very promising. It consists in iterating over resolutions of 2D and ID MOC problems by taking advantage of prismatic geometries without introducing approximations of a low order operator such as diffusion. However, before developing a solver with all industrial options at EDF, several points needed to be clarified. In this work, we first prove the convergence of this iterative process, under some assumptions. We then present our high-performance, parallel implementation of this algorithm in the MICADO solver. Benchmarking the solver against the Takeda case shows that the 2D-1D coupling algorithm does not seem to affect the spatial convergence order of the MOC solver. As for performance issues, our study shows that even though the data distribution is suited to the 2D solver part, the efficiency of the ID part is sufficient to ensure a good parallel efficiency of the global algorithm. After this study, the main remaining difficulty implementation-wise is about the memory requirement of a vector used for initialization. An efficient acceleration operator will also need to be developed. (authors)

97 MATHEMATICS AND COMPUTING↗

Implementing Directive-Based Deferred Execution for Effective Network Aggregation

Remote direct memory access technology provides an efficient mechanism for one-sided communication that can be leveraged to implement a distributed shared memory programming model. However, when applications generate large numbers of small, irregular messages, network congestion often arises. Existing solutions address this small message problem by facilitating message aggregation but typically require disruptive code transformations that detract from the algorithmic intent of applications, or can be limited by dependent operations on aggregated data between synchronisation points. A solution is to use a directive-assisted approach that enables compilers to transform code dependent on aggregated communication for deferred execution. This paper presents an algorithm that a compiler can use to implement and optimise deferred execution for code dependent on aggregated data, based on an "aggregation context" extension for the OpenSHMEM partitioned global address space library. This new capability addresses a key challenge of message aggregation, allowing its full potential to reduce network congestion and enhance programmability to be realised.

Welch, Aaron [ORNL]↗

Devastator Parallel Discrete Event Simulation Runtime (Devastator) v1.0

The Devastator runtime is a modern C++ implementation of optimistic parallel discrete event simulation methods. Devastator allows simulation application code to productively specify their component and event functionality with C++14 constructs. It utilizes GASNet-EX for distributed memory communication and includes parallel performance optimizations such as light-weight thread message queues and asynchronous GVT. Furthermore, it supports efficient event broadcasts and pause-rewind-resume functionality to support periodic load balancing and outer loop optimization algorithms.

Chan, Cy↗

Statistical prediction with Kanerva's sparse distributed memory

A new viewpoint of the processing performed by Kanerva's sparse distributed memory (SDM) is presented. In conditions of near- or over-capacity, where the associative-memory behavior of the model breaks down, the processing performed by the model can be interpreted as that of a statistical predictor. Mathematical results are presented which serve as the framework for a new statistical viewpoint of sparse distributed memory and for which the standard formulation of SDM is a special case. This viewpoint suggests possible enhancements to the SDM model, including a procedure for improving the predictiveness of the system based on Holland's work with genetic algorithms, and a method for improving the capacity of SDM even when used as an associative memory.

Rogers, David↗