SEARCH · Engineering Papers

Results for “synchronization overhead”

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 19 records

All sources NASA NTRS DOE OSTI

NASA NTRS1989

Alternative majority-voting methods for real-time computing systems

Two techniques that provide a compromise between the high time overhead in maintaining synchronous voting and the difficulty of combining results in asynchronous voting are proposed. These techniques are specifically suited for real-time applications with a single-source/single-sink structure that need instantaneous error masking. They provide a compromise between a tightly synchronized system in which the synchronization overhead can be quite high, and an asynchronous system which lacks suitable algorithms for combining the output data. Both quorum-majority voting (QMV) and compare-majority voting (CMV) are most applicable to distributed real-time systems with single-source/single-sink tasks. All real-time systems eventually have to resolve their outputs into a single action at some stage. The development of the advanced information processing system (AIPS) and other similar systems serve to emphasize the importance of these techniques. Time bounds suggest that it is possible to reduce the overhead for quorum-majority voting to below that for synchronous voting. All the bounds assume that the computation phase is nonpreemptive and that there is no multitasking.

Shin, Kang G.↗

DOE OSTI2020

Accelerating Parallel Applications in Cloud Platforms via Adaptive Time-Slice Control

Cloud platforms can provide flexible and cost-effective environments for parallel applications. However, the resource over-commitment issues, i.e., cloud providers often provide much more executable virtual CPUs than available physical CPUs, still impede the synchronization operations of parallel applications, causing severe performance degradation. Existing methods optimize parallel applications by promoting the priorities of involved VMs. They cannot fully explore the performance of parallel applications, because they ignore the time-slice requirements of different phases of parallel applications. Furthermore, non-parallel applications experience unsatisfied performance because of low scheduling priorities. Given empirical analysis on time-slices of virtual machines (VMs), we find that shortening time-slices can mitigate synchronization overhead which incurs during communication phases, while over-short time-slices cause frequent cache misses in computation phases. Accordingly, we propose an Adaptive Time-slice Control (ATC) mechanism. ATC first detects the phases of parallel applications based on lock latency or cache misses. Then, ATC shortens time-slices during communication phases and prolongs time-slices during computation phases for parallel applications, and sets a uniform time-slice for non-parallel applications. Finally, we evaluate ATC using seven well-known benchmarks with 25+ applications. Experiments show that ATC obtains 1.5-75x performance gain for running parallel applications than state-of-the-art solutions, with nearly unaffected impact on non-parallel applications.

97 MATHEMATICS AND COMPUTING↗

DOE OSTI2020

Optimizing the hypre solver for manycore and GPU architectures

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

97 MATHEMATICS AND COMPUTING↗

DOE OSTI2022

LC-MEMENTO: A Memory Model for Accelerated Architectures

With the advent of heterogeneous architectures, in particular, with the ubiquity of multi-GPU systems, it is becoming increasingly important to manage device memory efficiently in order to reap the benefits of the additional core count. To date, such responsibility mainly falls on the programmer where device-to-host data communication (and vice versa), if not done properly, may incur costly memory transfer operations and synchronization. The problem may be compounded by additional requirement to maintain system-wide memory consistency that may involve expensive synchronization overhead. In this paper, we present Location Consistency Memory Model for Enhanced Transfer Operations (LC-MEMENTO). This framework considers incorporating runtime techniques for multi-GPU memory management to support relaxed synchronization semantics and memory transfer operations automatically. Specifically, we implement a relaxed form of a memory consistency model based on the Location Consistency (LC) in an Asynchronous Many-Task Runtime (ARTS) and demonstrate that, this memory model enables additional optimization opportunities for the three representative applications encompassing different computational patterns (scientific computation, graphs, data streaming, etc.).

Memory Models, Accelerators, Adaptive Optimization↗

NASA NTRS1989

Performance impacts of look-ahead execution in the conversation scheme

The look-ahead execution approach, which allows participant processes that exist early to exit from a conversation before other participants finish their conversation activities, is presented here as a fundamental approach to reducing the synchronization overhead. Queuing network models are developed for systems operating under the basic conversation execution scheme and systems operating under the look-ahead execution scheme. Based on the models, various performance indicators such as the system throughput, the average number of processors idling inside a conversation due to the synchronization required, and the average time spent in conversation are evaluated numerically for different application environments. The results provide insights into the extent of benefits provided by the look-ahead execution approach.

Kim, K. H.↗

DOE OSTI2026

Physics-aware adaptive checkpointing with shadow systems for nonlinear PDE simulations

Large-scale simulations of nonlinear partial differential equations (PDEs) that exhibit strongly transient behavior and pattern-forming dynamics produce enormous amounts of data, which, even with modern storage systems, cannot be stored for later curation. Current I/O strategies either write dense time series of snapshots, which is often prohibitive in I/O and storage, or store a few checkpoints that enable restart but incur expensive recomputation cost and provide no control over post-restart error growth, especially when lossy compression is used. Moreover, most, if not all, existing strategies take no account of the actual physical state of the system. Here, we present a simple physics-aware I/O framework in which a low-cost shadow system adaptively triggers lossy checkpoints when the shadow system deviates from the fine-scale simulation. The shadow system can be a coarsened replica of the fine-scale simulation that evolves concurrently. This means that checkpoints are taken based on the physical state of the system: fewer checkpoints are triggered when the system is quiescent while more are taken when the system undergoes a rapid change. This type of behavior is observed in many systems such as Brusselator and FitzHugh–Nagumo. We illustrate that our framework maintains stable restarts, keeps fine-scale restart errors bounded by shadow errors, and reconstructs the time history with significantly lower error and storage than interpolating fixed-interval snapshots, with low-cost shadow replay and modest online synchronization overhead.

Gong, Qian [ORNL] (ORCID:0000000235704142)↗

DOE OSTI2021

Fast and Scalable Sparse Triangular Solver for Multi-GPU Based HPC Architectures

Designing efficient and scalable sparse linear algebra kernels on modern multi-GPU based HPC systems is a daunting task due to significant irregular memory references and workload imbalance across the GPUs. This is particularly the case for \textit{Sparse Triangular Solver (SpTRSV)} which introduces additional two-dimensional computation dependencies among subsequent computation steps. Dependency information is exchanged and shared among GPUs, thus warrant for efficient memory allocation, data partitioning, and workload distribution as well as fine-grained communication and synchronization support. In this work, we demonstrate that directly adopting unified memory can adversely affect the performance of SpTRSV on multi-GPU architectures, despite linking via fast interconnect like NVLinks and NVSwitches. Alternatively, we employ the latest NVSHMEM technology based on Partitioned Global Address Space programming model to enable efficient fine-grained communication and drastic synchronization overhead reduction. Furthermore, to handle workload imbalance, we propose a malleable task-pool execution model which can further enhance the utilization of GPUs. By applying these techniques, our experiments on the NVIDIA multi-GPU supernode V100-DGX-1 and DGX-2 systems demonstrate that our design can achieve on average 3.53x (up to 9.86x) speedup on a DGX-1 system and 3.66x (up to 9.64x) speedup on a DGX-2 system with 4-GPUs over the Unified-Memory design. The comprehensive sensitivity and scalability studies also show that the proposed zero-copy SpTRSV is able to fully utilize the computing and communication resources of the multi-GPU system.

Xie, Chenhao↗

DOE OSTI2026

Topology-Dependent Performance of Free-Space Photonic Quantum Networks Under Noise

Photonic quantum communication enables secure and high-fidelity information transfer beyond classical limits, with direct relevance to emerging quantum networks operating in free-space environments. While physical-layer models of depolarizing noise, Gamma–Gamma turbulence statistics, entanglement swapping, and decoy-state QKD security bounds are individually well established, prior work typically treats these components in isolation or under fixed network assumptions. In this work, we develop a unified topology-aware analytical framework that simultaneously integrates free-space optical link budgets, turbulence-induced visibility degradation, depolarizing qubit noise, multi-hop entanglement cascade dynamics, teleportation fidelity thresholds, CHSH nonlocality certification, and asymptotic decoy-state secret key rate bounds across star, mesh, and ring graph structures. Rather than introducing new physical channel models, we demonstrate that identical physical links exhibit fundamentally different end-to-end performance once embedded within different network topologies. Mesh architectures minimize visibility cascade through hop-count reduction but incur quadratic hardware scaling. Star topologies minimize link count but concentrate noise and synchronization overhead at the hub. Ring configurations offer linear hardware scaling with multiplicative fidelity degradation. The results establish topology as a first-order design parameter in near-term free-space quantum networks operating without full quantum repeater infrastructures. While motivated by distributed multi-agent architectures, the framework applies broadly to terrestrial, airborne, and satellite-assisted photonic quantum communication systems.

QKD↗

NASA NTRS1987

Problem size, parallel architecture and optimal speedup

The communication and synchronization overhead inherent in parallel processing can lead to situations where adding processors to the solution method actually increases execution time. Problem type, problem size, and architecture type all affect the optimal number of processors to employ. The numerical solution of an elliptic partial differential equation is examined in order to study the relationship between problem size and architecture. The equation's domain is discretized into n sup 2 grid points which are divided into partitions and mapped onto the individual processor memories. The relationships between grid size, stencil type, partitioning strategy, processor execution time, and communication network type are analytically quantified. In so doing, the optimal number of processors was determined to assign to the solution, and identified (1) the smallest grid size which fully benefits from using all available processors, (2) the leverage on performance given by increasing processor speed or communication network speed, and (3) the suitability of various architectures for large numerical problems.

Nicol, David M.↗

NASA NTRS1988

Problem size, parallel architecture, and optimal speedup

Nicol, David M.↗

NASA NTRS1990

Graphics applications utilizing parallel processing

The results are presented of research conducted to develop a parallel graphic application algorithm to depict the numerical solution of the 1-D wave equation, the vibrating string. The research was conducted on a Flexible Flex/32 multiprocessor and a Sequent Balance 21000 multiprocessor. The wave equation is implemented using the finite difference method. The synchronization issues that arose from the parallel implementation and the strategies used to alleviate the effects of the synchronization overhead are discussed.

Rice, John R.↗

NASA NTRS1991

Fast Parallel Computation Of Manipulator Inverse Dynamics

Method for fast parallel computation of inverse dynamics problem, essential for real-time dynamic control and simulation of robot manipulators, undergoing development. Enables exploitation of high degree of parallelism and, achievement of significant computational efficiency, while minimizing various communication and synchronization overheads as well as complexity of required computer architecture. Universal real-time robotic controller and simulator (URRCS) consists of internal host processor and several SIMD processors with ring topology. Architecture modular and expandable: more SIMD processors added to match size of problem. Operate asynchronously and in MIMD fashion.

Fijany, Amir↗

NASA NTRS1996

Balancing Contention and Synchronization on the Intel Paragon

The Intel Paragon is a mesh-connected distributed memory parallel computer. It uses an oblivious and deterministic message routing algorithm: this permits us to develop highly optimized schedules for frequently needed communication patterns. The complete exchange is one such pattern. Several approaches are available for carrying it out on the mesh. We study an algorithm developed by Scott. This algorithm assumes that a communication link can carry one message at a time and that a node can only transmit one message at a time. It requires global synchronization to enforce a schedule of transmissions. Unfortunately global synchronization has substantial overhead on the Paragon. At the same time the powerful interconnection mechanism of this machine permits 2 or 3 messages to share a communication link with minor overhead. It can also overlap multiple message transmission from the same node to some extent. We develop a generalization of Scott's algorithm that executes complete exchange with a prescribed contention. Schedules that incur greater contention require fewer synchronization steps. This permits us to tradeoff contention against synchronization overhead. We describe the performance of this algorithm and compare it with Scott's original algorithm as well as with a naive algorithm that does not take interconnection structure into account. The Bounded contention algorithm is always better than Scott's algorithm and outperforms the naive algorithm for all but the smallest message sizes. The naive algorithm fails to work on meshes larger than 12 x 12. These results show that due consideration of processor interconnect and machine performance parameters is necessary to obtain peak performance from the Paragon and its successor mesh machines.

Bokhari, Shahid H.↗

NASA NTRS1985

Ensuring fault tolerance of phase-locked clocks

Processors within a real-time multiprocessor system must be synchronized with as little overhead as possible. Although synchronization can be achieved via both software (e.g., interactive convergence and interactive consistency algorithms) and hardware (e.g., multistage synchronizers and phase-locked clocks), phase-locked clocks are most attractive due to their small overheads. Despite the fact that synchronization of the multiprocessor system with phase-locked clocks is totally different in nature from the interactive consistency algorithm, it is presently proven that it must satisfy the same condition, N equal to or greater than 3m + 1, where N is the total number of clocks in the multiprocessor system and m is the maximum number of faults tolerable. Also presented are results showing how to design phase-locked clocks so as to be impervious up to a given arbitrary number of malicious failures.

Krishna, C. M.↗

DOE OSTI2024

Synchronization for CXL Based Memory

Compute Express Link (CXL) is an important emerging standard for disaggregated memory. While this standard provisions coherency across numerous hosts and devices, implementing hardware support for type three devices is challenging. In this work, we look at the overhead of software synchronization and using software-based coherency. Moreover, we discuss the limits of software-based coherency in fully expressing modern synchronization techniques for a CXL-based disaggregate memory system. We demonstrate our approach using a CXL hardware prototype and running a version of the famous Peterson Lock (enhanced to run with more than two threads). We analyze its performance and share how more advanced synchronization techniques might interact with software-based coherence CXL hardware and program execution models.

High Performance Computing (HPC)↗

NASA NTRS1990

The cost of conservative synchronization in parallel discrete event simulations

The performance of a synchronous conservative parallel discrete-event simulation protocol is analyzed. The class of simulation models considered is oriented around a physical domain and possesses a limited ability to predict future behavior. A stochastic model is used to show that as the volume of simulation activity in the model increases relative to a fixed architecture, the complexity of the average per-event overhead due to synchronization, event list manipulation, lookahead calculations, and processor idle time approach the complexity of the average per-event overhead of a serial simulation. The method is therefore within a constant factor of optimal. The analysis demonstrates that on large problems--those for which parallel processing is ideally suited--there is often enough parallel workload so that processors are not usually idle. The viability of the method is also demonstrated empirically, showing how good performance is achieved on large problems using a thirty-two node Intel iPSC/2 distributed memory multiprocessor.

Nicol, David M.↗

NASA NTRS1986

SAGE observations of stratospheric nitrogen dioxide

The global distribution of nitrogen dioxide in the middle to upper stratosphere (25-45 km altitude) for the period February 1979 to November 1981 has been determined from observations of attenuated solar radiation in the visible region 0.385-0.45 micron by the Stratospheric Aerosol and Gas Experiment (SAGE) satellite instrument. The SAGE-derived NO2 vertical profiles compare well with observations by balloon- and aircraft-borne sensors. The global SAGE NO2 distributions generally show a maximum in mixing ratio of 8 parts per billion by volume at about 35 km altitude near the equatorial latitudes at local sunset. The location of the mixing ratio peak moves synchronously with the overhead sun for the four different seasons. High-latitude NO2 column content shows strong seasonal variation, with a maximum in local summer and a minimum in local winter. Selected data at high-latitude winter seasons are presented, suggesting that the large variation shown could be explained by the coupling of both dynamics and photochemistry of the NO(x) species. Finally, profiles of the ratio of sunset to sunrise NO2 mixing ratios, peaking at about a factor of two at 30 km, are shown.

Chu, W. P.↗

NASA NTRS1991

Asynchronous and corrected-asynchronous numerical solutions of parabolic PDES on MIMD multiprocessors

A major problem in achieving significant speed-up on parallel machines is the overhead involved with synchronizing the concurrent process. Removing the synchronization constraint has the potential of speeding up the computation. The authors present asynchronous (AS) and corrected-asynchronous (CA) finite difference schemes for the multi-dimensional heat equation. Although the discussion concentrates on the Euler scheme for the solution of the heat equation, it has the potential for being extended to other schemes and other parabolic partial differential equations (PDEs). These schemes are analyzed and implemented on the shared memory multi-user Sequent Balance machine. Numerical results for one and two dimensional problems are presented. It is shown experimentally that the synchronization penalty can be about 50 percent of run time: in most cases, the asynchronous scheme runs twice as fast as the parallel synchronous scheme. In general, the efficiency of the parallel schemes increases with processor load, with the time level, and with the problem dimension. The efficiency of the AS may reach 90 percent and over, but it provides accurate results only for steady-state values. The CA, on the other hand, is less efficient, but provides more accurate results for intermediate (non steady-state) values.

Amitai, Dganit↗