Search NASA⌕ Search

SEARCH · Search NASA

Results for “Computational Load Balancing”

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 109 records · Page 6

Adaptive Load-Balancing Algorithms using Symmetric Broadcast Networks

In a distributed computing environment, it is important to ensure that the processor workloads are adequately balanced, Among numerous load-balancing algorithms, a unique approach due to Das and Prasad defines a symmetric broadcast network (SBN) that provides a robust communication pattern among the processors in a topology-independent manner. In this paper, we propose and analyze three efficient SBN-based dynamic load-balancing algorithms, and implement them on an SGI Origin2000. A thorough experimental study with Poisson distributed synthetic loads demonstrates that our algorithms are effective in balancing system load. By optimizing completion time and idle time, the proposed algorithms are shown to compare favorably with several existing approaches.

Das, Sajal K.↗

Tiling Framework for Heterogeneous Computing of Matrix based Tiled Algorithms

Tiling matrix operations can improve the load balancing and performance of applications on heterogeneous computing resources. Writing a tile-based algorithm for each operation with a traditional, hand-tuned tiling approach that uses for loops in C/C++ is cumbersome and error prone. Moreover, it must enable and support the heterogeneous memory management of data objects and also explore architecture-supported, native, tiled-data transfer APIs instead of copying the tiled data to continuous memory before the data transfer. The tiling framework provides a tiled data structure for heterogeneous memory mapping and parameterization to a heterogeneous task specification API. We have integrated our tiled framework into MatRIS (Math kernels library using IRIS). IRIS is a heterogeneous run-time framework with a heterogeneous programming model, memory model, and task execution model. Experiments reveal that the tiled framework for BLAS operations has improved the programmability of tiled BLAS and improved performance by ~20% when compared against the traditional method that copies the data to continuous memory locations for heterogeneous computing.

Miniskar, Narasinga Rao↗

Combinatorial Algorithms to Enable Computational Science and Engineering: Work from the CSCAPES Institute

This final progress report summarizes the work accomplished at the Combinatorial Scientific Computing and Petascale Simulations Institute. We developed Zoltan, a parallel mesh partitioning library that made use of accurate hypergraph models to provide load balancing in mesh-based computations. We developed several graph coloring algorithms for computing Jacobian and Hessian matrices and organized them into a software package called ColPack. We developed parallel algorithms for graph coloring and graph matching problems, and also designed multi-scale graph algorithms. Three PhD students graduated, six more are continuing their PhD studies, and four postdoctoral scholars were advised. Six of these students and Fellows have joined DOE Labs (Sandia, Berkeley), as staff scientists or as postdoctoral scientists. We also organized the SIAM Workshop on Combinatorial Scientific Computing (CSC) in 2007, 2009, and 2011 to continue to foster the CSC community.

97 MATHEMATICS AND COMPUTING↗

Atomistic nanoelectronic device engineering with sustained performances up to 1.44 PFlop/s

We present a multi-dimensional, atomistic, quantum transport simulation approach to investigate the performances of realistic nanoscale transistors for various geometries and material systems. The central computation consists in solving the Schrödinger equation with open boundary conditions several thousand times. To do that, a Wave Function approach is used since it can be relatively easily parallelized. To further improve the computational efficiency, three additional levels of parallelization are identified, the work load is optimally balanced between the CPUs, computational interleaving is applied where possible, and a mixed precision scheme is introduced. Using two different device types, a high electron mobility and a band-to-band tunneling transistor, sustained performances up to 1.28 PFlop/s in double precision (55% of the peak performance) and 1.44 PFlop/s in mixed precision are reached on 221,400 cores on the CRAY-XT5 Jaguar at Oak Ridge National Lab.

Luisier, Mathieu↗

New Results on Communication- and Memory-Aware Load Balancing Model and Algorithms

While load balancing in distributed-memory computing has been well-studied, we present an innovative approach to this problem: a unified, reduced-order model that combines three key components to describe “work” in a distributed system: computation, communication, and memory. Our model enables an optimizer to explore complex tradeoffs in task placement, such as augmented parallelism, at the expense of data replication increasing memory usage. We propose a fully distributed, heuristic-based load balancing optimization algorithm, and demonstrate that it quickly finds close-to-optimal solutions. We formalize the complex optimization problem as a mixed-integer linear program, and compare it to our strategy. Finally, we show that when applied to an electromagnetics code, our approach obtains up to 2.3x speedups for the imbalanced execution.

97 MATHEMATICS AND COMPUTING↗

Computer simulation of the effect of dDAVP with saline loading on fluid balance after 24-hour head-down tilt

Fluid loading (FL) before Shuttle reentry is a countermeasure currently in use by NASA to improve the orthostatic tolerance of astronauts during reentry and postflight. The fluid load consists of water and salt tablets equivalent to 32 oz (946 ml) of isotonic saline. However, the effectiveness of this countermeasure has been observed to decrease with the duration of spaceflight. The countermeasure's effectiveness may be improved by enhancing fluid retention using analogs of vasopressin such as lypressin (LVP) and desmopressin (dDAVP). In a computer simulation study reported previously, we attempted to assess the improvement in fluid retention obtained by the use of LVP administered before FL. The present study is concerned with the use of dDAVP. In a recent 24-hour, 6 degree head-down tilt (HDT) study involving seven men, dDAVP was found to improve orthostatic tolerance as assessed by both lower body negative pressure (LBNP) and stand tests. The treatment restored Luft's cumulative stress index (cumulative product of magnitude and duration of LBNP) to nearly pre-bedrest level. The heart rate was lower and stroke volume was marginally higher at the same LBNP levels with administration of dDAVP compared to placebo. Lower heart rates were also observed with dDAVP during stand test, despite the lower level of cardiovascular stress. These improvements were seen with only a small but significant increase in plasma volume of approximately 3 percent. This paper presents a computer simulation analysis of some of the results of this HDT study.

NASA Discipline Cardiopulmonary↗

Modeling the fracture of ice sheets on parallel computers.

The objective of this project is to investigate the complex fracture of ice and understand its role within larger ice sheet simulations and global climate change. At the present time, ice fracture is not explicitly considered within ice sheet models due in part to large computational costs associated with the accurate modeling of this complex phenomena. However, fracture not only plays an extremely important role in regional behavior but also influences ice dynamics over much larger zones in ways that are currently not well understood. Dramatic illustrations of fracture-induced phenomena most notably include the recent collapse of ice shelves in Antarctica (e.g. partial collapse of the Wilkins shelf in March of 2008 and the diminishing extent of the Larsen B shelf from 1998 to 2002). Other fracture examples include ice calving (fracture of icebergs) which is presently approximated in simplistic ways within ice sheet models, and the draining of supraglacial lakes through a complex network of cracks, a so called ice sheet plumbing system, that is believed to cause accelerated ice sheet flows due essentially to lubrication of the contact surface with the ground. These dramatic changes are emblematic of the ongoing change in the Earth's polar regions and highlight the important role of fracturing ice. To model ice fracture, a simulation capability will be designed centered around extended finite elements and solved by specialized multigrid methods on parallel computers. In addition, appropriate dynamic load balancing techniques will be employed to ensure an approximate equal amount of work for each processor.

54 ENVIRONMENTAL SCIENCES↗

Scalable load balancing for massively parallel distributed Monte Carlo particle transport

In order to run computer simulations efficiently on massively parallel computers with hundreds of thousands or millions of processors, care must be taken that the calculation is load balanced across the processors. Examining the workload of every processor leads to an unscalable algorithm, with run time at least as large as O(N), where N is the number of processors. We present a scalable load balancing algorithm, with run time 0(log(N)), that involves iterated processor-pair-wise balancing steps, ultimately leading to a globally balanced workload. We demonstrate scalability of the algorithm up to 2 million processors on the Sequoia supercomputer at Lawrence Livermore National Laboratory. (authors)

97 MATHEMATICS AND COMPUTING↗

Dynamic Calibration of the NASA Ames Rotor Test Apparatus Steady/Dynamic Rotor Balance

The NASA Ames Rotor Test Apparatus was modified to include a Steady/Dynamic Rotor Balance. The dynamic calibration procedures and configurations are discussed. Random excitation was applied at the rotor hub, and vibratory force and moment responses were measured on the steady/dynamic rotor balance. Transfer functions were computed using the load cell data and the vibratory force and moment responses from the rotor balance. Calibration results showing the influence of frequency bandwidth, hub mass, rotor RPM, thrust preload, and dynamic loads through the stationary push rods are presented and discussed.

Peterson, Randall L.↗

Parallel Load Balancing for Adaptive Unstructured Meshes

Mesh adaption is a powerful tool for efficient unstructured-grid computations but causes load imbalance among processors on a parallel machine. We describe a novel method to dynamically balance the processor workloads with a global view. Mesh question, repartitioning, processor assignment, and remapping are critical components of the framework that must be accomplished rapidly and efficiently so as not to cause a significant overhead to the numerical simulation. A data redistribution model will also be presented that predicts the remapping cost. This model is required to determine whether the gain from a balanced workload distribution offsets the cost of data movement. Results presented will demonstrate that this is an effective dynamic load balancing strategy which remains viable on a large number of processors.

Biswas, Rupak↗

A parallel p ‐adaptive discontinuous Galerkin method for the Euler equations with dynamic load‐balancing on tetrahedral grids

Abstract A novel p ‐adaptive discontinuous Galerkin (DG) method has been developed to solve the Euler equations on three‐dimensional tetrahedral grids. Hierarchical orthogonal basis functions are adopted for the DG spatial discretization while a third order TVD Runge‐Kutta method is used for the time integration. A vertex‐based limiter is applied to the numerical solution in order to eliminate oscillations in the high order method. An error indicator constructed from the solution of order and is used to adapt degrees of freedom in each computational element, which remarkably reduces the computational cost while still maintaining an accurate solution. The developed method is implemented with under the Charm++ parallel computing framework. Charm++ is a parallel computing framework that includes various load‐balancing strategies. Implementing the numerical solver under Charm++ system provides us with access to a suite of dynamic load balancing strategies. This can be efficiently used to alleviate the load imbalances created by p ‐adaptation. A number of numerical experiments are performed to demonstrate both the numerical accuracy and parallel performance of the developed p ‐adaptive DG method. It is observed that the unbalanced load distribution caused by the parallel p ‐adaptive DG method can be alleviated by the dynamic load balancing from Charm++ system. Due to this, high performance gain can be achieved. For the testcases studied in the current work, the parallel performance gain ranged from 1.5× to 3.7×. Therefore, the developed p ‐adaptive DG method can significantly reduce the total simulation time in comparison to the standard DG method without p ‐adaptation.

97 MATHEMATICS AND COMPUTING↗

Data Structure and Parallel Decomposition Considerations on a Fibonacci Grid

The Fibonacci grid, proposed by Swinbank and Purser (see companion abstract), provides attractive properties for global numerical atmospheric prediction by offering an optimally homogeneous, geometrically regular, and approximately isotropic discretization, with only the polar regions requiring special numerical treatment. It is a mathematical idealization, applied to the sphere, of the multi-spiral patterns often found in botanical structures, such as in pine cones and sunflower heads. Computationally, it is natural to organize the domain, into zones, in each of which the same pair, or triple, of "Fibonacci spirals" dominate. But the further subdivision of such zones into "tiles" of a shape and size suitable for distribution to the processors of a massively parallel computer requires very careful consideration if the subsequent spatial computations along the respective spirals, especially those computations (such as compact differencing schemes) that involve recursion, can be implemented in an efficient "load-balanced "manner without requiring excessive amounts of inter-processor communications. In this paper we show how certain "number theoretic" properties of the Fibonacci sequence (whose numbers prescribe the multiplicity of successive spirals) may be exploited in the decomposition of grid zones into tidy arrangements of triangular grid tiles, each tile possessing one side approximately parallel to the constant-latitude zone boundary. We also describe how the spatially recursive processes may be decomposed across such a tiling, and the directionality of the recursions reversed on alternate grid lines, to ensure a very high degree of load balancing throughout the execution of the computations required for one time step of a global model.

Michalakes, John↗

Optimal net-load balancing in smart grids with high PV penetration

Mitigating mismatches in supply demand curve is critical for smooth power grid operation. Traditionally, load curtailment techniques such as Demand Response (DR) have been used for this purpose. However, smart grids with high PV penetration sometimes exhibit supply surplus causing over-voltages. Thus, load curtailment techniques cannot be the only component of a net-load balancing framework. Supply curtailment techniques such as Volt-Var Optimizations are complex and computationally expensive. This increases the complexity of net-load balancing systems used by the grid operator and limits their scalability. Recently, new technologies have been developed that enable the rapid and selective connection of PV modules of an installation to the grid. Taking advantage of these advancements, we develop a unified optimal net-load balancing framework which performs both load and solar curtailment. We show that when the available curtailment values are discrete, this problem is NP-hard and develop bounded approximation algorithms for minimizing the curtailment cost. Our algorithms produce fast solutions, given the tight timing constraints required for grid operation. We also incorporate the notion of fairness to ensure that curtailment is evenly distributed among all the nodes. Finally, we develop an online algorithm which performs net-load balancing using only data available for the current interval. Using both theoretical analysis and practical evaluations, we show that our net-load balancing algorithms provide solutions which are close to optimal in a small amount of time.

14 SOLAR ENERGY↗

A fully non-linear multi-species Fokker–Planck–Landau collision operator for simulation of fusion plasma

Fusion edge plasmas can be far from thermal equilibrium and require the use of a non-linear collision operator for accurate numerical simulations. In this article, the non-linear single-species Fokker–Planck–Landau collision operator developed by Yoon and Chang (2014) [9] is generalized to include multiple particle species. The finite volume discretization used in this work naturally yields exact conservation of mass, momentum, and energy. The implementation of this new non-linear Fokker–Planck–Landau operator in the gyrokinetic particle-in-cell codes XGC1 and XGCa is described and results of a verification study are discussed. Finally, the numerical techniques that make our non-linear collision operator viable on high-performance computing systems are described, including specialized load balancing algorithms and nested OpenMP parallelization. The collision operator's good weak and strong scaling behavior are shown.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

PLUM: Parallel Load Balancing for Adaptive Unstructured Meshes

Mesh adaption is a powerful tool for efficient unstructured-grid computations but causes load imbalance among processors on a parallel machine. We present a novel method called PLUM to dynamically balance the processor workloads with a global view. This paper presents the implementation and integration of all major components within our dynamic load balancing strategy for adaptive grid calculations. Mesh adaption, repartitioning, processor assignment, and remapping are critical components of the framework that must be accomplished rapidly and efficiently so as not to cause a significant overhead to the numerical simulation. A data redistribution model is also presented that predicts the remapping cost on the SP2. This model is required to determine whether the gain from a balanced workload distribution offsets the cost of data movement. Results presented in this paper demonstrate that PLUM is an effective dynamic load balancing strategy which remains viable on a large number of processors.

Oliker, Leonid↗

Novel techniques for data decomposition and load balancing for parallel processing of vision systems: Implementation and evaluation using a motion estimation system

Computer vision systems employ a sequence of vision algorithms in which the output of an algorithm is the input of the next algorithm in the sequence. Algorithms that constitute such systems exhibit vastly different computational characteristics, and therefore, require different data decomposition techniques and efficient load balancing techniques for parallel implementation. However, since the input data for a task is produced as the output data of the previous task, this information can be exploited to perform knowledge based data decomposition and load balancing. Presented here are algorithms for a motion estimation system. The motion estimation is based on the point correspondence between the involved images which are a sequence of stereo image pairs. Researchers propose algorithms to obtain point correspondences by matching feature points among stereo image pairs at any two consecutive time instants. Furthermore, the proposed algorithms employ non-iterative procedures, which results in saving considerable amounts of computation time. The system consists of the following steps: (1) extraction of features; (2) stereo match of images in one time instant; (3) time match of images from consecutive time instants; (4) stereo match to compute final unambiguous points; and (5) computation of motion parameters.

Choudhary, Alok Nidhi↗

Explicit spatial scattering for load balancing in conservatively synchronized parallel discrete-event simulations

We re-examine the problem of load balancing in conservatively synchronized parallel, discrete-event simulations executed on high-performance computing clusters, focusing on simulations where computational and messaging load tend to be spatially clustered. Such domains are frequently characterized by the presence of geographic 'hot-spots' - regions that generate significantly more simulation events than others. Examples of such domains include simulation of urban regions, transportation networks and networks where interaction between entities is often constrained by physical proximity. Noting that in conservatively synchronized parallel simulations, the speed of execution of the simulation is determined by the slowest (i.e most heavily loaded) simulation process, we study different partitioning strategies in achieving equitable processor-load distribution in domains with spatially clustered load. In particular, we study the effectiveness of partitioning via spatial scattering to achieve optimal load balance. In this partitioning technique, nearby entities are explicitly assigned to different processors, thereby scattering the load across the cluster. This is motivated by two observations, namely, (i) since load is spatially clustered, spatial scattering should, intuitively, spread the load across the compute cluster, and (ii) in parallel simulations, equitable distribution of CPU load is a greater determinant of execution speed than message passing overhead. Through large-scale simulation experiments - both of abstracted and real simulation models - we observe that scatter partitioning, even with its greatly increased messaging overhead, significantly outperforms more conventional spatial partitioning techniques that seek to reduce messaging overhead. Further, even if hot-spots change over the course of the simulation, if the underlying feature of spatial clustering is retained, load continues to be balanced with spatial scattering leading us to the observation that spatial scattering can often obviate the need for dynamic load balancing.

97 MATHEMATICS AND COMPUTING↗

Load‐balanced and locality‐aware scheduling for data‐intensive workloads at extreme scales

Summary Data‐driven programming models such as many‐task computing (MTC) have been prevalent for running data‐intensive scientific applications. MTC applies over‐decomposition to enable distributed scheduling. To achieve extreme scalability, MTC proposes a fully distributed task scheduling architecture that employs as many schedulers as the compute nodes to make scheduling decisions. Achieving distributed load balancing and best exploiting data locality are two important goals for the best performance of distributed scheduling of data‐intensive applications. Our previous research proposed a data‐aware work‐stealing technique to optimize both load balancing and data locality by using both dedicated and shared task ready queues in each scheduler. Tasks were organized in queues based on the input data size and location. Distributed key‐value store was applied to manage task metadata. We implemented the technique in MATRIX, a distributed MTC task execution framework. In this work, we devise an analytical suboptimal upper bound of the proposed technique, compare MATRIX with other scheduling systems, and explore the scalability of the technique at extreme scales. Results show that the technique is not only scalable but can achieve performance within 15% of the suboptimal solution. Copyright © 2015 John Wiley & Sons, Ltd.

Wang, Ke↗