A generic strategy for dynamic load balancing of distributed memory parallel computational mechanics using unstructured meshes

A large class of computational problems are characterised by frequent synchronisation, and computational requirements which change as a function of time. When such a problem is solved on a message passing multiprocessor machine [5], the combination of these characteristics leads to system performance which deteriorate in time. As the communication performance of parallel hardware steadily improves so load balance becomes a dominant factor in obtaining high parallel efficiency. Performance can be improved with periodic redistribution of computational load; however, redistribution can sometimes be very costly. We study the issue of deciding when to invoke a global load re-balancing mechanism. Such a decision policy must actively weigh the costs of remapping against the performance benefits, and should be general enough to apply automatically to a wide range of computations. This paper discusses a generic strategy for Dynamic Load Balancing (DLB) in unstructured mesh computational mechanics applications. The strategy is intended to handle varying levels of load changes throughout the run. The major issues involved in a generic dynamic load balancing scheme will be investigated together with techniques to automate the implementation of a dynamic load balancing mechanism within the Computer Aided Parallelisation Tools (CAPTools) environment, which is a semi-automatic tool for parallelisation of mesh based FORTRAN codes.

Load-balancing for parallel adaptive unstructured grids

A parallel method for the dynamic partitioning of unstructured meshes is outlined. The method includes diffusive load-balancing techniques and an iterative optimisation technique known as relative gain optimisationwhich both balances theworkload and attempts to minimise the interprocessor communications overhead. It can also optionally include amultilevel strategy. Experiments on a series of adaptively refined meshes indicate that the algorithmprovides partitions of an equivalent or higher quality to static partitioners (which do not reuse the existing partition) and much more rapidly. Perhaps more importantly, the algorithm results in only a small fraction of the amount of data migration compared to the static partitioners.

Parallel dynamic load-balancing for adaptive unstructured meshes

This chapter describes a parallel optimization technique that incorporates a distributed load-balancing algorithm and provides an extremely fast solution to the problem of load-balancing adaptive unstructured meshes. Moreover, a parallel graph contraction technique can be employed to enhance the partition quality and the resulting strategy outperforms or matches results from existing state-of-the-art static mesh partitioning algorithms. The strategy can also be applied to static partitioning problems. Dynamic procedures have been found to be much faster than static techniques, to provide partitions of similar or higher quality and, in comparison, involve the migration of a fraction of the data. The method employs a new iterative optimization technique that balances the workload and attempts to minimize the interprocessor communications overhead. Experiments on a series of adaptively refined meshes indicate that the algorithm provides partitions of an equivalent or higher quality to static partitioners (which do not reuse the existing partition) and much more quickly. The dynamic evolution of load has three major influences on possible partitioning techniques; cost, reuse, and parallelism. The unstructured mesh may be modified every few time-steps and so the load-balancing must have a low cost relative to that of the solution algorithm in between remeshing.

Dynamic load-balancing for parallel adaptive unstructured meshes

A parallel method for dynamic partitioning of unstructured meshes is described. The method employs a new iterative optimisation technique which both balances the workload and attempts to minimise the interprocessor communications overhead. Experiments on a series of adaptively refined meshes indicate that the algorithm provides partitions of an equivalent or higher quality to static partitioners (which do not reuse the existing partition) and much more quickly. Perhaps more importantly, the algorithm results in only a small fraction of the amount of data migration compared to the static partitioners.

Load balancing for aspect ratio in adaptive finite element simulations

In parallel adaptive finite element simulations the work load on the individual processors may change frequently. To (re)distribute the load evenly over the processors a load balancing heuristic is needed. Common strategies try to minimise subdomain dependencies by optimising the cutsize of the partitioning. However for certain solvers cutsize only plays a minor role, and their convergence is highly dependent on the subdomain shapes. Degenerated subdomain shapes cause them to need significantly more iterations to converge. In this work a new parallel load balancing strategy is introduced which directly addresses the problem of generating and conserving reasonably good subdomain shapes in a dynamically changing Finite Element Simulation. Geometric data is used to formulate several cost functions to rate elements in terms of their suitability to be migrated. The well known diffusive method which calculates the necessary load flow is enhanced by weighting the subdomain edges with the help of these cost functions. The proposed methods have been tested and results are presented.

Quality balancing for parallel adaptive FEM

We present a dynamic distributed load balancing algorithm for parallel, adaptive finite element simulations using preconditioned conjugate gradient solvers based on domain-decomposition. The load balancer is designed to maintain good partition aspect ratios. It can calculate a balancing flow using different versions of diffusion and a variant of breadth first search. Elements to be migrated are chosen according to a cost function aiming at the optimization of subdomain shapes. We show how to use information from the second step to guide the first. Experimental results using Bramble's preconditioner and comparisons to existing state-ot-the-art load balancers show the benefits of the construction.

Load balancing for parallel adaptive FEM

We present a dynamic distributed load balancing algorithm for parallel, adaptive finite element simulations using preconditioned conjugate gradient solvers based on domain-decomposition. The load balancer is designed to maintain good partition aspect ratios. It calculates a balancing flow using different versions of diffusion and a variant of breadth first search. Elements to be migrated are chosen according to a cost function aiming at the optimization of subdomain shapes. We show how to use information from the second step to guide the first. Experimental results using Bramble's preconditioner and comparisons to existing state-of-the-art balancers show the benefits of the construction.

Dynamic load balancing of distributed memory parallel computational mechanics using unstructured meshes for multi-physical modelling

As the complexity of parallel applications increase, the performance limitations resulting from computational load imbalance become dominant. Mapping the problem space to the processors in a parallel machine in a manner that balances the workload of each processors will typically reduce the run-time. In many cases the computation time required for a given calculation cannot be predetermined even at run-time and so static partition of the problem returns poor performance. For problems in which the computational load across the discretisation is dynamic and inhomogeneous, for example multi-physics problems involving fluid and solid mechanics with phase changes, the workload for a static subdomain will change over the course of a computation and cannot be estimated beforehand. For such applications the mapping of loads to process is required to change dynamically, at run-time in order to maintain reasonable efficiency. The issue of dynamic load balancing are examined in the context of PHYSICA, a three dimensional unstructured mesh multi-physics continuum mechanics computational modelling code.

Mesh partitioning and load balancing for distributed memory parallel systems

A method is outlined for optimising graph partitions which arise in mapping unstructured mesh calculations to parallel computers. The method employs a relative gain iterative technique to both evenly balance the workload and minimise the number and volume of interprocessor communications. A parallel graph reduction technique is also briefly described and can be used to give a global perspective to the optimisation. The algorithms work efficiently in parallel as well as sequentially and when combined with a fast direct partitioning technique (such as the Greedy algorithm) to give an initial partition, the resulting two-stage process proves itself to be both a powerful and flexible solution to the static graph-partitioning problem. Experiments indicate that the resulting parallel code can provide high quality partitions, independent of the initial partition, within a few seconds. The algorithms can also be used for dynamic load-balancing, reusing existing partitions and in this case the procedures are much faster than static techniques, provide partitions of similar or higher quality and, in comparison, involve the migration of a fraction of the data.

Automatic implementation of dynamic load balancing strategies for structured computational mechanics codes

This paper presents a new dynamic load balancing technique for structured mesh computational mechanics codes in which the processor partition range limits of just one of the partitioned dimensions uses non-coincidental limits, as opposed to using coincidental limits in all of the partitioned dimensions. The partition range limits are 'staggered', allowing greater flexibility in obtaining a balanced load distribution in comparison to when the limits are changed 'globally'. as the load increase/decrease on one processor no longer restricts the load decrease/increase on a neighbouring processor. The automatic implementation of this 'staggered' load balancing strategy within an existing parallel code is presented in this paper, along with some preliminary results.

Balancing Energy and Performance in Dense Linear System Solvers for Hybrid ARM+GPU platforms

The high performance computing community has traditionally focused uniquely on the reduction of execution time, though in the last years, the optimization of energy consumption has become a main issue. A reduction of energy usage without a degradation of performance requires the adoption of energy-efficient hardware platforms accompanied by the development of energy-aware algorithms and computational kernels. The solution of linear systems is a key operation for many scientific and engineering problems. Its relevance has motivated an important amount of work, and consequently, it is possible to find high performance solvers for a wide variety of hardware platforms. In this work, we aim to develop a high performance and energy-efficient linear system solver. In particular, we develop two solvers for a low-power CPU-GPU platform, the NVIDIA Jetson TK1. These solvers implement the Gauss-Huard algorithm yielding an efficient usage of the target hardware as well as an efficient memory access. The experimental evaluation shows that the novel proposal reports important savings in both time and energy-consumption when compared with the state-of-the-art solvers of the platform.

Balancing Belligerents or Feeding the Beast: Transforming Conflict Traps

Since the end of the Cold War, recurring civil conflicts have been the dominant form of violent armed conflict in the world, accounting for 70% of conflicts active between 2000-2013. Duration and intensity of episodes within recurring conflicts in Africa exhibit four behaviors characteristic of archetypal dynamic system structures. The overarching questions asked in this study are whether these patterns are robustly correlated with fundamental concepts of resiliency in dynamic systems that scale from micro-to macro levels; are they consistent with theoretical risk factors and causal mechanisms; and what are the policy implications. Econometric analysis and dynamic systems modeling of 36 conflicts in Africa between 1989 -2014 are combined with process tracing in a case study of Somalia to evaluate correlations between state characteristics, peace operations and foreign aid on the likelihood of observed conflict patterns, test hypothesized causal mechanisms across scales, and develop policy recommendations for increasing human security while decreasing resiliency of belligerents. Findings are that observed conflict patterns scale from micro to macro levels; are strongly correlated with state characteristics that proxy a mix of cooperative (e.g., gender equality) and coercive (e.g., security forces) conflict-balancing mechanisms; and are weakly correlated with UN and regional peace operations and humanitarian aid. Interactions between peace operations and aid interventions that effect conflict persistence at micro levels are not seen in macro level analysis, due to interdependent, micro-level feedback mechanisms, sequencing, and lagged effects. This study finds that the dynamic system structures associated with observed conflict patterns contain tipping points between balancing mechanisms at the interface of micro-macro level interactions that are determined as much by factors related to how intervention policies are designed and implemented, as what they are. Policy implications are that reducing risk of conflict persistence requires that peace operations and aid interventions (1) simultaneously increase transparency, promote inclusivity (with emphasis on gender equality), and empower local civilian involvement in accountability measures at the local levels; (2) build bridges to horizontally and vertically integrate across levels; and (3) pave pathways towards conflict transformation mechanisms and justice that scale from the individual, to community, regional, and national levels.

Probabilistic design optimization of horizontal axis wind turbine rotors

Considerable interest in renewable energy has increased in recent years due to the concerns raised over the environmental impact of conventional energy sources and their price volatility. In particular, wind power has enjoyed a dramatic global growth in installed capacity over the past few decades. Nowadays, the advancement of wind turbine industry represents a challenge for several engineering areas, including materials science, computer science, aerodynamics, analytical design and analysis methods, testing and monitoring, and power electronics. In particular, the technological improvement of wind turbines is currently tied to the use of advanced design methodologies, allowing the designers to develop new and more efficient design concepts. Integrating mathematical optimization techniques into the multidisciplinary design of wind turbines constitutes a promising way to enhance the profitability of these devices. In the literature, wind turbine design optimization is typically performed deterministically. Deterministic optimizations do not consider any degree of randomness affecting the inputs of the system under consideration, and result, therefore, in an unique set of outputs. However, given the stochastic nature of the wind and the uncertainties associated, for instance, with wind turbine operating conditions or geometric tolerances, deterministically optimized designs may be inefficient. Therefore, one of the ways to further improve the design of modern wind turbines is to take into account the aforementioned sources of uncertainty in the optimization process, achieving robust configurations with minimal performance sensitivity to factors causing variability. The research work presented in this thesis deals with the development of a novel integrated multidisciplinary design framework for the robust aeroservoelastic design optimization of multi-megawatt horizontal axis wind turbine (HAWT) rotors, accounting for the stochastic variability related to the input variables. The design system is based on a multidisciplinary analysis module integrating several simulations tools needed to characterize the aeroservoelastic behavior of wind turbines, and determine their economical performance by means of the levelized cost of energy (LCOE). The reported design framework is portable and modular in that any of its analysis modules can be replaced with counterparts of user-selected fidelity. The presented technology is applied to the design of a 5-MW HAWT rotor to be used at sites of wind power density class from 3 to 7, where the mean wind speed at 50 m above the ground ranges from 6.4 to 11.9 m/s. Assuming the mean wind speed to vary stochastically in such range, the rotor design is optimized by minimizing the mean and standard deviation of the LCOE. Airfoil shapes, spanwise distributions of blade chord and twist, internal structural layup and rotor speed are optimized concurrently, subject to an extensive set of structural and aeroelastic constraints. The effectiveness of the multidisciplinary and robust design framework is demonstrated by showing that the probabilistically designed turbine achieves more favorable probabilistic performance than those of the initial baseline turbine and a turbine designed deterministically.

Balancing the demands of two tasks: an investigation of cognitive-motor dual-tasking in relapsing remitting multiple sclerosis

Background: People with relapsing remitting MS (PwRRMS) suffer disproportionate decrements in gait under dual-task conditions, when walking and a cognitive task are combined. There has been much less investigation of the impact of cognitive demands on balance. This study investigated whether: (1) PwRRMS show disproportionate decrements in postural stability under dual-task conditions compared to healthy controls; (2) dual-task decrements are associated with everyday dual-tasking difficulties. In addition, the impact of mood, fatigue and disease severity on dual-tasking were also examined. Methods: 34 PwRRMS and 34 matched controls completed cognitive (digit span) and balance (movement of centre of pressure on a Biosway, on stable and unstable surfaces) tasks under single and dual-task conditions. Everyday dual-tasking was measured using the DTQ. Mood was measured by the HADS. Fatigue was measured via the MFIS. Results: No differences in age, gender, years of education, estimated pre-morbid IQ or baseline digit span between the groups. Compared to healthy controls, PwRRMS showed a significantly greater decrement in postural stability under dual-task conditions on an unstable surface (p=0.007), but not a stable surface (p=0.679). PwRRMS reported higher levels of everyday dual-tasking difficulties (p<0.001). Balance decrement scores were not correlated with everyday dual-tasking difficulties, or with fatigue. Stable surface balance decrement scores were significantly associated with levels of anxiety (rho=0.527, p=0.001) and depression (rho=0.451, p=0.007). Conclusion: RRMS causes difficulties with dual-tasking, impacting balance, particularly under challenging conditions, which may contribute to an increased risk of gait difficulties and falls. The striking relationship between anxiety/depression and dual-task decrement suggests that worry may be contributing to dual-task difficulties.