Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “Asynchronous iterations”

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 37 records · Page 2

Asynchronous sequential circuit design using pass transistor iterative logic arrays

The iterative logic array (ILA) is introduced as a new architecture for asynchronous sequential circuits. This is the first ILA architecture for sequential circuits reported in the literature. The ILA architecture produces a very regular circuit structure. Moreover, it is immune to both 1-1 and 0-0 crossovers and is free of hazards. This paper also presents a new critical race free STT state assignment which produces a simple form of design equations that greatly simplifies the ILA realizations.

Liu, M. N.↗

Scalable Asynchronous Domain Decomposition Solvers

We discuss how parallel implementations of linear iterative solvers generally alternate between phases of data exchange and phases of local computation. Increasingly large problem sizes and more heterogeneous compute architectures make load balancing and the design of low latency network interconnects that are able to satisfy the communication requirements of linear solvers very challenging tasks. In particular, global communication patterns such as inner products become increasingly limiting at scale. We explore the use of asynchronous communication based on one-sided Message Passing Interface primitives in the context of domain decomposition solvers. In particular, a scalable asynchronous two-level Schwarz method is presented. We discuss practical issues encountered in the development of a scalable solver and show experimental results obtained on a state-of-the-art supercomputer system that illustrate the benefits of asynchronous solvers in load balanced as well as load imbalanced scenarios. Using the novel method, we can observe speedups of up to four times over its classical synchronous equivalent.

97 MATHEMATICS AND COMPUTING↗

Frog: Asynchronous Graph Processing on GPU with Hybrid Coloring Model

GPUs have been increasingly used to accelerate graph processing for complicated computational problems regarding graph theory. Many parallel graph algorithms adopt the asynchronous computing model to accelerate the iterative convergence. Unfortunately, the consistent asynchronous computing requires locking or atomic operations, leading to significant penalties/overheads when implemented on GPUs. As such, coloring algorithm is adopted to separate the vertices with potential updating conflicts, guaranteeing the consistency/correctness of the parallel processing. Common coloring algorithms, however, may suffer from low parallelism because of a large number of colors generally required for processing a large-scale graph with billions of vertices. We propose a light-weight asynchronous processing framework called Frog with a preprocessing/hybrid coloring model. The fundamental idea is based on Pareto principle (or 80-20 rule) about coloring algorithms as we observed through masses of realworld graph coloring cases. We find that a majority of vertices (about 80%) are colored with only a few colors, such that they can be read and updated in a very high degree of parallelism without violating the sequential consistency. Accordingly, our solution separates the processing of the vertices based on the distribution of colors. In this work, we mainly answer three questions: (1) how to partition the vertices in a sparse graph with maximized parallelism, (2) how to process large-scale graphs that cannot fit into GPU memory, and (3) how to reduce the overhead of data transfers on PCIe while processing each partition. Here, we conduct experiments on real-world data (Amazon, DBLP, YouTube, RoadNet-CA, WikiTalk and Twitter) to evaluate our approach and make comparisons with well-known non-preprocessed (such as Totem, Medusa, MapGraph and Gunrock) and preprocessed (Cusha) approaches, by testing four classical algorithms (BFS, PageRank, SSSP and CC). On all the tested applications and datasets, Frog is able to significantly outperform existing GPU-based graph processing systems except Gunrock and MapGraph. MapGraph gets better performance than Frog when running BFS on RoadNet-CA. The comparison between Gunrock and Frog is inconclusive. Frog can outperform Gunrock more than 1.04X when running PageRank and SSSP, while the advantage of Frog is not obvious when running BFS and CC on some datasets especially for RoadNet-CA.

97 MATHEMATICS AND COMPUTING↗

Quasi-perfect FIFO: Synchronous or asynchronous with application in controller design for the UNICON laser memory

The first-in-first-out memory buffer (FIFO), is an elastic digital memory whose main application is in data buffering between devices operating at different rates. Data written into the top is moved autonomously down toward the bottom of the FIFO to the lowest unoccupied location, and data read from the bottom of the FIFO will cause data from the top to move autonomously down toward the bottom. The FIFO is available in MOS LSI asynchronous form with data rate in the 1 MHz region. The FIFO described yields a simple high-speed iterative implementation, either synchronous of asynchronous. Because of this simple iterative structure, the FIFO is expandable in both number of words and bits per word, and it is attractive from the viewpoint of integrated-circuit production. For the synchronous FIFO, a model was built and successfully used in the controller for the UNICON laser memory. For the asynchronous FIFO, a model was built and also successfully used in a high-performance magnetic tape controller.

Lim, R. S.↗

Neutron transport methods for multiphysics heterogeneous reactor core simulation in Griffin

Griffin is a reactor physics application based on the Multiphysics Object-Oriented Simulation Environment (MOOSE). This work discloses the methods, algorithms, and implementation for simulating heterogeneous reactor dynamics models. Griffin utilizes a discontinuous finite-element method with discrete ordinates (DFEM-S ) to discretize the field variable of the multigroup neutron transport equation. Multiphysics feedback is handled using two-step tabulated cross-section methodology. Feedback quantities are evaluated using the MOOSE-MultiApp system to couple various engineering phenomena, such as heat conduction and thermal fluids. The multiphysics DFEM-S system is solved using fixed-point iteration with a fully asynchronous parallel sweeper, unstructured coarse-mesh finite difference acceleration, and a multi-timescale improved quasi-static method scheme. The implementation is applied to a multiphysics microreactor model, with two transients: one initiated by a single heat-pipe failure and another by control drum rotation. Importantly, these examples demonstrate the ability of Griffin to tractably solve the neutron transport equation considering seven independent variables and feedback.

97 MATHEMATICS AND COMPUTING↗

A fully distributed asynchronous approach for multi-area coordinated network-constrained unit commitment

This paper discusses a consensus-based alternating direction method of multipliers (ADMM) approach to solve the multi-area coordinated network-constrained unit commitment (NCUC) problem in a distributed manner. Due to political and technical difficulties, it is neither practical nor feasible to solve the multi-area coordination problem in a centralized fashion, which requires full access to all data of individual areas. In comparison, in the proposed fully-distributed approach, local NCUC problems of individual areas can be solved independently, and only limited information is exchanged among adjacent areas for facilitating multi-area coordination. Furthermore, as traditional ADMM can only guarantee convergence for convex problems, this paper discusses several strategies to mitigate oscillations, enhance convergence performance, and derive good-enough feasible solutions, including: (i) A tie-line power flow based area coordination strategy is designed to reduce the number of global consensus variables; (ii) Different penalty parameters \r{ho} are assigned to individual consensus variables and are updated via certain rules during the iterative procedure, which would reduce the impact of initial values of \r{ho} on convergence performance; (iii) Heuristic rules are adopted to fix certain unit commitment variables for avoiding oscillations during the iterative procedure; and (iv) An asynchronous distributed strategy is studied, which solves NCUC subproblems of small areas multiple times and exchanges information with adjacent areas more frequently within one complete run of slower NCUC subproblems of large areas. Numerical cases illustrate effectiveness of the proposed asynchronous fully-distributed NCUC approach, and investigate key factors that would affect its convergence performance.

24 POWER TRANSMISSION AND DISTRIBUTION↗

Error field detection and correction studies towards ITER operation

In magnetic fusion devices, error field (EF) sources, spurious magnetic field perturbations, need to be identified and corrected for safe and stable (disruption-free) tokamak operation. Within Work Package Tokamak Exploitation RT04, a series of studies have been carried out to test the portability of the novel non-disruptive method, designed and tested in DIII-D (Paz-Soldan et al 2022 Nucl. Fusion62 126007), and to perform an assessment of model-based EF control strategies towards their applicability in ITER. In this paper, the lessons learned, the physical mechanism behind the magnetic island healing, which relies on enhanced viscous torque that acts against the static electro-magnetic torque, and the main control achievements are reported, together with the first design of the asynchronous EF correction current/density controller for ITER.

70 PLASMA PHYSICS AND FUSION TECHNOLOGY↗

A Novel Multithreaded Algorithm For Extracting Maximal Chordal Subgraphs

Chordal graphs are triangulated graphs where any cycle larger than three is bisected by a chord. Many combinatorial optimization problems such as computing the minimum fill-in, the size of the maximum clique and the chromatic number are NP-hard on general graphs but have polynomial time solutions on chordal graphs. In this paper, we present a novel multithreaded algorithm to extract a maximal chordal subgraph from a general graph. Our algorithm is based on an iterative approach where each thread can asynchronously update a subset of edges that are dynamically assigned to it. We implement our algorithm on two different multithreaded architectures – Cray XMT, a massively multithreaded platform, and AMD Magny-Cours, a shared memory multicore platform. In addition to the proof of correctness, we present the performance of our algorithm using a testset of carefully generated synthetical graphs with up to half-a-billion edges and real world networks from gene correlation studies. We demonstrate that our algorithm achieves high scalability for all inputs on both types of architectures.

Halappanavar, Mahantesh↗

Graph-based Reversible Evaluation and Tangents Library

GRETL is a C++ library for evaluation, re-evaluation and algorithmic differentiation of functional operations on an arbitrary computational graph with limited memory usage. Similar to popular machine learning frameworks in Python, like PyTorch and JAX, it tracks and stores both operations and output data as functions are evaluated. Once this composition of functions is built up, the entire chain of operations can be back propagated to compute sensitivities of the final result with respect to any number of inputs. In contrast to most machine learning applications, memory usage becomes the bottleneck for back propagation in many physics applications, especially for time-dependent PDEs. Dynamic check pointing becomes essential. An important distinguishing feature of GRETL is its ability to limit the maximum memory usage by automatically dynamic checkpointing the data output for each graph operation (see Wang, Moin, Iaccarino, 2009). During backpropagation, parts of the graph that are no longer in memory are automatically re-evaluated from upstream checkpointed states as needed for derivative sensitivity calculations (or more precisely, for vector-Jacobian products). GRETL is particularly beneficial for applications, such as coupled multi-physics, where deriving adjoint-based sensitivities and managing checkpoint memory across modules becomes onerous. Cases which can be readily handled by the GRETL library include: different time-integration algorithms per physics (e.g., coupled predictor-corrector algorithms, IMEX, etc.), sub-cycling, asynchronous integrators, state dependent timestep sizes, iterative solvers and coupling algorithms, controller algorithms, and more.

Tupek, MichaelR [Lawrence Livermore National Labor↗

An asynchronous traversal engine for graph-based rich metadata management

Rich metadata in high-performance computing (HPC) systems contains extended information about users, jobs, data files, and their relationships. Property graphs are a promising data model to represent heterogeneous rich metadata flexibly. Specifically, a property graph can use vertices to represent different entities and edges to record the relationships between vertices with unique annotations. The high-volume HPC use case, with millions of entities and relationships, naturally requires an out-of-core distributed property graph database, which must support live updates (to ingest production information in real time), low-latency point queries (for frequent metadata operations such as permission checking), and large-scale traversals (for provenance data mining). Among these needs, large-scale property graph traversals are particularly challenging for distributed graph storage systems. Most existing graph systems implement a "level synchronous" breadth-first search algorithm that relies on global synchronization in each traversal step. This performs well in many problem domains; but a rich metadata management system is characterized by imbalanced graphs, long traversal lengths, and concurrent workloads, each of which has the potential to introduce or exacerbate stragglers (i.e., abnormally slow steps or servers in a graph traversal) that lead to low overall throughput for synchronous traversal algorithms. Previous research indicated that the straggler problem can be mitigated by using asynchronous traversal algorithms, and many graph-processing frameworks have successfully demonstrated this approach. Such systems require the graph to be loaded into a separate batch-processing framework instead of being iteratively accessed, however. In this work, we investigate a general asynchronous graph traversal engine that can operate atop a rich metadata graph in its native format. We outline a traversal-aware query language and key optimizations (traversal-affiliate caching and execution merging) necessary for efficient performance. We further explore the effect of different graph partitioning strategies on the traversal performance for both synchronous and asynchronous traversal engines. Our experiments show that the asynchronous graph traversal engine is more efficient than its synchronous counterpart in the case of HPC rich metadata processing, where more servers are involved and larger traversals are needed. Furthermore, the asynchronous traversal engine is more adaptive to different graph partitioning strategies.

96 KNOWLEDGE MANAGEMENT AND PRESERVATION↗

Enabling Communication Between Astronauts and Ground Teams for Space Exploration Missions

Over the last four years, Playbook’s Mission Log has evolved to become an enabling capability for analog missions that simulate deep space, exploration missions with communication transmission latency. Playbook is a planning and execution web-application for mission operations, aggregating multiple sources of information for astronauts to execute the mission in one place: timeline, procedures, chat interface. Playbook’s Mission Log provides a multimedia chat software interface with unique features and functionalities that support asynchronous communication between analog astronauts and ground support teams. This paper describes the iterative design the Mission Log has undergone based on user observations and solicited feedback. Key features include indicators that help users cope with asynchronous communication as well as aids that assist teams coordinate work. Future work and capabilities are outlined, which build upon the increased use of the Mission Log as a communication and coordination tool for space exploration.

communication↗

Data exchange and processing synchronization in distributed systems

Systems, methods, techniques and apparatuses of asynchronous communication is distributed systems are disclosed. One exemplary embodiment is a method determining, with a plurality of agent nodes structured to communicate asynchronously in a distributed system, a first set of iterations including an iteration determined by each of the plurality of agent nodes; determining, with a first agent node of the plurality of agent nodes, a local vector clock; receiving, with the first agent node, a first iteration of the first set of iterations and a remote vector clock determined based on the first iteration; updating, with the first agent node, the local vector clock based on the received remote vector clock; and determining a first iteration of a second set of iterations based on the first set of iterations after determining all iterations of the first set of iterations have been received based on the local vector clock.

Cintuglu, Mehmet H.↗

Saturation: An efficient iteration strategy for symbolic state-space generation

This paper presents a novel algorithm for generating state spaces of asynchronous systems using Multi-valued Decision Diagrams. In contrast to related work, the next-state function of a system is not encoded as a single Boolean function, but as cross-products of integer functions. This permits the application of various iteration strategies to build a system's state space. In particular, this paper introduces a new elegant strategy, called saturation, and implements it in the tool SMART. On top of usually performing several orders of magnitude faster than existing BDD-based state-space generators, the algorithm's required peak memory is often close to the nal memory needed for storing the overall state spaces.

Ciardo, Gianfranco↗

Exploiting parallel computing with limited program changes using a network of microcomputers

Network computing and multiprocessor computers are two discernible trends in parallel processing. The computational behavior of an iterative distributed process in which some subtasks are completed later than others because of an imbalance in computational requirements is of significant interest. The effects of asynchronus processing was studied. A small existing program was converted to perform finite element analysis by distributing substructure analysis over a network of four Apple IIe microcomputers connected to a shared disk, simulating a parallel computer. The substructure analysis uses an iterative, fully stressed, structural resizing procedure. A framework of beams divided into three substructures is used as the finite element model. The effects of asynchronous processing on the convergence of the design variables are determined by not resizing particular substructures on various iterations.

Rogers, J. L., Jr.↗

Seven open problems in applied combinatorics

We present and discuss seven different open problems in applied combinatorics. Additionally, the application areas relevant to this compilation include quantum computing, algorithmic differentiation, topological data analysis, iterative methods, hypergraph cut algorithms, and power systems.

97 MATHEMATICS AND COMPUTING↗

On the Degradation of the Effectiveness of Nonlinear Diffusion Acceleration with Parallel Block Jacobi Splitting

MOOSE's radiation transport module Rattlesnake comprises a first order S N solver that can be accelerated with a flexible Nonlinear Diffusion Acceleration. At each NDA iteration, the streaming and collision operator of the S{sub N} equations are (approximately) inverted using a transport sweep. When executed on multiple processors parallel block Jacobi (PBJ) splitting is utilized lagging the processor sub-domain's incoming angular fluxes making the implemented method asynchronous, i.e. the convergence properties of NDA become dependent on the number of concurrent tasks and details of the partitioning. Within this work, we study the NDA convergence properties for the two-dimensional C5G7 benchmark problem PBJ with p = 1, 2, 4, 8, 12, 16, 24, 32, 48, 60, 72, 96 and 144 concurrent tasks. Rosa studied the convergence properties of PBJ splitting methods with and without transport synthetic acceleration (TSA) in slab geometry and two-dimensional Cartesian geometry, respectively. Rosa's iteration scheme lags both the incoming angular fluxes and the scattering source making it very similar to the method described here. Rosa found by means of Fourier analysis that convergence of unaccelerated PBJ can degrade for optically thin subdomains, i.e. for a large number of processors given a fixed domain size. Depending on the choice of parameters application of TSA can lead to an effective algorithm. In contrast to Rosa's work, this work focuses on PBJ splitting for NDA accelerated solution of the multigroup eigenvalue problem. Later, Zerr and Anistratov used their integral transport matrix method in conjunction with PBJ. This iteration scheme is different as it does not lag the scattering source. Nevertheless, Fourier analysis with Diamond Difference spatial discretization showed that the method degrades with increasing the overall size of the spatial domain while keeping the sub-domain size constant. In the case of an infinite medium, the observed spectral radius becomes unity. These references establish the iterative performance of PBJ for one-group fixed source problems discretized on rectangular cells, but for the Rattlesnake first order NDA method, an emphasis lies on multigroup eigenvalue problems. In this setting, the additional complication arises that the low order equations are not exactly inverted, but only to some iterative criterion. Further, as the low order problem is solved using Jacobian-Free Newton Krylov methods, a suitable preconditioner for the GMRES iterations is required. As the effectiveness of the preconditioners may decrease when more concurrent processes are used, we expect the low order solve to impact the overall effectiveness of the NDA method in parallel execution as well. Therefore, this work focuses on the question of how detrimental the asynchronicity of the high and low order iterative solutions is for the effectiveness of NDA solutions of realistic, unstructured grid, multigroup eigenvalue problems. The iterative convergence properties of Rattlesnake's NDA method for multigroup eigenvalue problems are studied for varying number of concurrent processes. Rattlesnake's NDA method is asynchronous because the high order transport sweep uses PBJ splitting and because the low order solve's preconditioners, algebraic multigrid and additive Schwarz, are asynchronous. We found that up to 144 processes the number of Picard iterations increases by a factor of 2-3 affecting but not destroying NDA's parallel performance for the C5G7 benchmark problem, a representative LWR (light water reactor) configuration. The solution of the NDA low order eigenvalue problem posed greater problems than expected for the solvers currently available in Rattlesnake mainly because of problems to effectively precondition the modified low-order problem. As a matter of fact, the low order problem becomes an advection-diffusion problem. Non-robustness was observed for the AMG preconditioned coarse mesh acceleration for more than 60 concurrent processes, which was fixed by increasing the number of permissible V-cycles per AMG call. For fine mesh acceleration AMG proved to be ineffective and we resorted to ASM. For both AMG and ASM, increasing number of linear iterations per nonlinear are observed when increasing the number of processes, but for ASM this problem appears to be worse. The results from this work also indicate that initial development efforts should be diverted from implementation of a high-order parallel sweeping algorithm to the effective and robust iterative solution of the low order NDA multigroup eigenvalue problem. (authors)

97 MATHEMATICS AND COMPUTING↗

Benchmark Tracking System for Performance Monitoring

Benchmarking is essential for high-performance software development, particularly for monitoring performance across code iterations. This project focused on enhancing the benchmarking process for Lamellar, an asynchronous runtime for High-Performance Computing (HPC) systems developed at Pacific Northwest National Laboratory. Prior to this work, benchmark results were difficult to track and compare across code versions, presenting significant challenges in identifying performance regressions and long-term trends. The primary objective was to establish a systematic, reproducible approach for measuring performance and detecting regressions following code commits. Our methodology involved three key components: standardizing benchmark outputs, implementing data versioning, and developing analysis tools. We standardized the benchmark output format to JSON Line records containing specific fields (execution time, hardware specifications, and environmental variables). To address data management challenges, we evaluated several options and eventually chose a git repository dedicated to benchmark data. We developed a suite of Python tools that processed benchmark results, enriched them with metadata, and facilitated search in the repository. The resulting system enables more efficient filtering and comparison of performance metrics across commit histories, hardware configurations, and benchmark variants through a unified query interface. Our implementation reduces computational overhead by first checking for existing results through configuration matching before initiating new benchmark runs, thereby conserving resources. The system has been validated by Lamellar developers. It organizes results by benchmark type and build configurations for efficient retrieval. Future developments include a planned Large Language Model interface for predicting benchmark performance, incorporating the criterion package for statistical analysis, which will enable automated detection of statistically significant performance changes, and integration with continuous integration pipelines. Despite these enhancements being reserved for future work, this project has successfully provided the Lamellar development team with a framework for maintaining consistent performance standards and identifying optimization opportunities across workloads and hardware environments.

97 MATHEMATICS AND COMPUTING↗

SIAM Conference on Parallel Processing for Scientific Computing, 4th, Chicago, IL, Dec. 11-13, 1989, Proceedings

Attention is given to such topics as an evaluation of block algorithm variants in LAPACK and presents a large-grain parallel sparse system solver, a multiprocessor method for the solution of the generalized Eigenvalue problem on an interval, and a parallel QR algorithm for iterative subspace methods on the CM2. A discussion of numerical methods includes the topics of asynchronous numerical solutions of PDEs on parallel computers, parallel homotopy curve tracking on a hypercube, and solving Navier-Stokes equations on the Cedar Multi-Cluster system. A section on differential equations includes a discussion of a six-color procedure for the parallel solution of elliptic systems using the finite quadtree structure, data parallel algorithms for the finite element method, and domain decomposition methods in aerodynamics. Topics dealing with massively parallel computing include hypercube vs. 2-dimensional meshes and massively parallel computation of conservation laws. Performance and tools are also discussed.

Dongarra, Jack↗