A study of adaptive load balancing algorithms for distributed systems

With the advent of distributed computer systems with a largely transparent user interface, new questions have arisen regarding the management of such an environment by an operating system. One fertile area of research is that of load balancing, which attempts to improve system performance by redistributing the workload submitted to the system by the users. Early work in this field concentrated on static placement of computational objects to improve performance, given prior knowledge of process behaviour. More recently this has evolved into studying dynamic load balancing with process migration, thus allowing the system to adapt to varying loads. In this thesis, we describe a simulated system which facilitates experimentation with various load balancing algorithms. The system runs under UNIX and provides functions for user processes to communicate through software ports; processes reside on simulated homogeneous processors, connected by a user-specified topology, and a mechanism is included to allow migration of a process from one processor to another. We present the results of a study of adaptive load balancing algorithms, conducted using the aforementioned simulated system, under varying conditions; these results show the relative merits of different approaches to the load balancing problem, and we analyse the trade-offs between them. Following from this study, we present further novel modifications to suggested algorithms, and show their effects on system performance.

The relative performance of scalable load balancing algorithms in loosely-coupled distributed systems. Available in 2 volumes.

The computer systems of today are characterised by data and program control that are distributed functionally and geographically across a network. A major issue of concern in this environment is the operating system activity of resource management for different processors in the network. To ensure equity in load distribution and improved system performance, load balancing is often undertaken. The research conducted in this field so far, has been primarily concerned with a small set of algorithms operating on tightly-coupled distributed systems. More recent studies have investigated the performance of such algorithms in loosely-coupled architectures but using a small set of processors. This thesis describes a simulation model developed to study the behaviour and general performance characteristics of a range of dynamic load balancing algorithms. Further, the scalability of these algorithms are discussed and a range of regionalised load balancing algorithms developed. In particular, we examine the impact of network diameter and delay on the performance of such algorithms across a range of system workloads. The results produced seem to suggest that the performance of simple dynamic policies are scalable but lack the load stability of more complex global average algorithms.

Dynamic causal modeling of load-dependent modulation of effective connectivity within the verbal working memory network

Neuroimaging studies have consistently shown that working memory (WM) tasks engage a distributed neural network that primarily includes the dorsolateral prefrontal cortex, the parietal cortex, and the anterior cingulate cortex. The current challenge is to provide a mechanistic account of the changes observed in regional activity. To achieve this, we characterized neuroplastic responses in effective connectivity between these regions at increasing WM loads using dynamic causal modeling of functional magnetic resonance imaging data obtained from healthy individuals during a verbal n-back task. Our data demonstrate that increasing memory load was associated with (a) right-hemisphere dominance, (b) increasing forward (i.e., posterior to anterior) effective connectivity within the WM network, and (c) reduction in individual variability in WM network architecture resulting in the right-hemisphere forward model reaching an exceedance probability of 99% in the most demanding condition. Our results provide direct empirical support that task difficulty, in our case WM load, is a significant moderator of short-term plasticity, complementing existing theories of task-related reduction in variability in neural networks. Hum Brain Mapp, 2013. © 2013 Wiley Periodicals, Inc.

The lateral and ventromedial prefrontal cortex work as a dynamic integrated system:evidence from FMRI connectivity analysis

Recent functional magnetic resonance imaging (fMRI) investigations of the interaction between cognition and reward processing have found that the lateral prefrontal cortex (PFC) areas are preferentially activated to both increasing cognitive demand and reward level. Conversely, ventromedial PFC (VMPFC) areas show decreased activation to the same conditions, indicating a possible reciprocal relationship between cognitive and emotional processing regions. We report an fMRI study of a rewarded working memory task, in which we further explore how the relationship between reward and cognitive processing is mediated. We not only assess the integrity of reciprocal neural connections between the lateral PFC and VMPFC brain regions in different experimental contexts but also test whether additional cortical and subcortical regions influence this relationship. Psychophysiological interaction analyses were used as a measure of functional connectivity in order to characterize the influence of both cognitive and motivational variables on connectivity between the lateral PFC and the VMPFC. Psychophysiological interactions revealed negative functional connectivity between the lateral PFC and the VMPFC in the context of high memory load, and high memory load in tandem with a highly motivating context, but not in the context of reward alone. Physiophysiological interactions further indicated that the dorsal anterior cingulate and the caudate nucleus modulate this pathway. These findings provide evidence for a dynamic interplay between lateral PFC and VMPFC regions and are consistent with an emotional gating role for the VMPFC during cognitively demanding tasks. Our findings also support neuropsychological theories of mood disorders, which have long emphasized a dysfunctional relationship between emotion/motivational and cognitive processes in depression.

A dynamic bandwidth reservation scheme for hybrid IEEE 802.16 wireless networks

A dynamic bandwidth reservation (DBR) scheme for hybrid IEEE 802.16 wireless networks is investigated, in which 802.16 networks serve as the backhaul for client networks, such as WiFi hotspots and cellular networks. The DBR scheme implemented in the subscription stations (SSs) (co-locating with access pointers) consists of two components: connection admission controller (CAC), and bandwidth controller (BC). The CAC processes the received connection set-up requests from the client networks connected to the SSs. The BC manages the request and release of bandwidth from the base station (BS). It dynamically changes the reserved bandwidth between a small number of values. Hysteresis is incorporated in bandwidth release to reduce bandwidth request signalling load and connection blocking probability. An analytical model is proposed to evaluate the performances of reserved bandwidth, connection blocking probability and signalling load. The impacts of hysteresis mechanism and probability of reservation request blocking are taken into account. Simulation verifies the analytical model. ©2008 IEEE.

The effect of load on agent-based algorithms for distributed task allocation

Multi-agent algorithms inspired by the division of labour in social insects and by markets, are applied to a constrained problem of distributed task allocation. The efficiency (average number of tasks performed), the flexibility (ability to react to changes in the environment), and the sensitivity to load (ability to cope with differing demands) are investigated in both static and dynamic environments. A hybrid algorithm combining both approaches, is shown to exhibit improved efficiency and robustness. We employ nature inspired particle swarm optimisation to obtain optimised parameters for all algorithms in a range of representative environments. Although results are obtained for large population sizes to avoid finite size effects, the influence of population size on the performance is also analysed. From a theoretical point of view, we analyse the causes of efficiency loss, derive theoretical upper bounds for the efficiency, and compare these with the experimental results.

Improving scheduling techniques in heterogeneous systems with dynamic, on-line optimisations

Computational performance increasingly depends on parallelism, and many systems rely on heterogeneous resources such as GPUs and FPGAs to accelerate computationally intensive applications. However, implementations for such heterogeneous systems are often hand-crafted and optimised to one computation scenario, and it can be challenging to maintain high performance when application parameters change. In this paper, we demonstrate that machine learning can help to dynamically choose parameters for task scheduling and load-balancing based on changing characteristics of the incoming workload. We use a financial option pricing application as a case study. We propose a simulation of processing financial tasks on a heterogeneous system with GPUs and FPGAs, and show how dynamic, on-line optimisations could improve such a system. We compare on-line and batch processing algorithms, and we also consider cases with no dynamic optimisations.

Dynamic network rating for low carbon distribution network operation:a U.K. application

Dynamic asset rating (DAR) is one of the number of techniques that could be used to facilitate low carbon electricity network operation. Previous work has looked at this technique from an asset perspective. This paper focuses, instead, from a network perspective by proposing a dynamic network rating (DNR) approach. The models available for use with DAR are discussed and compared using measured load and weather data from a trial network area within Milton Keynes in the central area of the U.K. This paper then uses the most appropriate model to investigate, through a network case study, the potential gains in dynamic rating compared to static rating for the different network assets - transformers, overhead lines, and cables. This will inform the network operator of the potential DNR gains on an 11-kV network with all assets present and highlight the limiting assets within each season.

Thermal modelling for dynamic transformer rating in low carbon distribution network operation

Dynamic asset rating is one of a number of techniques that could be used to facilitate low carbon electricity network operation. This paper focusses on distribution level transformer dynamic rating under this context. The models available for use with dynamic asset rating are discussed and compared using measured load and weather conditions from a trial Network area within Milton Keynes. The paper then uses the most appropriate model to investigate, through simulation, the potential gains in dynamic rating compared to static rating under two transformer cooling methods to understand the potential gain to the Network Operator.

Characterizing permanent deformation and fracture of asphalt mixtures by using compressive dynamic modulus tests

Permanent deformation and fracture may develop simultaneously when an asphalt mixture is subjected to a compressive load. The objective of this research is to separate viscoplasticity and viscofracture from viscoelasticity so that the permanent deformation and fracture of the asphalt mixtures can be individually and accurately characterized without the influence of viscoelasticity. The undamaged properties of 16 asphalt mixtures that have two binder types, two air void contents, and two aging conditions are first obtained by conducting nondestructive creep tests and nondestructive dynamic modulus tests. Testing results are analyzed by using the linear viscoelastic theory in which the creep compliance and the relaxation modulus are modeled by the Prony model. The dynamic modulus and phase angle of the undamaged asphalt mixtures remained constant with the load cycles. The undamaged asphalt mixtures are then used to perform the destructive dynamic modulus tests in which the dynamic modulus and phase angle of the damaged asphalt mixtures vary with load cycles. This indicates plastic evolution and crack propagation. The growth of cracks is signaled principally by the increase of the phase angle, which occurs only in the tertiary stage. The measured total strain is successfully decomposed into elastic strain, viscoelastic strain, plastic strain, viscoplastic strain, and viscofracture strain by employing the pseudostrain concept and the extended elastic-viscoelastic correspondence principle. The separated viscoplastic strain uses a predictive model to characterize the permanent deformation. The separated viscofracture strain uses a fracture strain model to characterize the fracture of the asphalt mixtures in which the flow number is determined and a crack speed index is proposed. Comparisons of the 16 samples show that aged asphalt mixtures with a low air void content have a better performance, resisting permanent deformation and fracture. © 2012 American Society of Civil Engineers.