More Like this

1. Self-Learning Threshold-Based Load Balancing

   https://doi.org/10.1287/ijoc.2021.1100  

   Goldsztajn, Diego ; Borst, Sem C. ; van Leeuwaarden, Johan S. ; Mukherjee, Debankur ; Whiting, Philip A. ( January 2022 , INFORMS Journal on Computing)

   We consider a large-scale service system where incoming tasks have to be instantaneously dispatched to one out of many parallel server pools. The user-perceived performance degrades with the number of concurrent tasks and the dispatcher aims at maximizing the overall quality of service by balancing the load through a simple threshold policy. We demonstrate that such a policy is optimal on the fluid and diffusion scales, while only involving a small communication overhead, which is crucial for large-scale deployments. In order to set the threshold optimally, it is important, however, to learn the load of the system, which may be unknown. For that purpose, we design a control rule for tuning the threshold in an online manner. We derive conditions that guarantee that this adaptive threshold settles at the optimal value, along with estimates for the time until this happens. In addition, we provide numerical experiments that support the theoretical results and further indicate that our policy copes effectively with time-varying demand patterns. Summary of Contribution: Data centers and cloud computing platforms are the digital factories of the world, and managing resources and workloads in these systems involves operations research challenges of an unprecedented scale. Due to the massive size, complex dynamics, and wide range of time scales, the design and implementation of optimal resource-allocation strategies is prohibitively demanding from a computation and communication perspective. These resource-allocation strategies are essential for certain interactive applications, for which the available computing resources need to be distributed optimally among users in order to provide the best overall experienced performance. This is the subject of the present article, which considers the problem of distributing tasks among the various server pools of a large-scale service system, with the objective of optimizing the overall quality of service provided to users. A solution to this load-balancing problem cannot rely on maintaining complete state information at the gateway of the system, since this is computationally unfeasible, due to the magnitude and complexity of modern data centers and cloud computing platforms. Therefore, we examine a computationally light load-balancing algorithm that is yet asymptotically optimal in a regime where the size of the system approaches infinity. The analysis is based on a Markovian stochastic model, which is studied through fluid and diffusion limits in the aforementioned large-scale regime. The article analyzes the load-balancing algorithm theoretically and provides numerical experiments that support and extend the theoretical results. 

   more » « less
2. Priority Weighted Round Robin Algorithm for Load Balancing in the Cloud

   https://doi.org/10.1109/SmartCloud55982.2022.00044  

   Katangur, Ajay ; Akkaladevi, Somasheker ; Vivekanandhan, Sadiskumar ( October 2022 , 2022 IEEE 7th International Conference on Smart Cloud (SmartCloud))

   Cloud computing, which helps in sharing resources through networks, has become one of the most widely used technologies in recent years. Vast numbers of organizations are moving to the cloud since it is more cost-effective and easy to maintain. An increase in the number of consumers using the cloud, however, results in increased traffic, which leads to the problem of balancing tasks on the loads. Numerous dynamic algorithms [1] have been proposed and implemented to handle these loads in different ways. The performance of these dynamic algorithms are scaled with different parameters, such as response time, throughput, utilization, efficiency, etc. The weighted round-robin algorithm is one of the most widely used load balancing algorithms. The proposed algorithm is an improvement of the weighted round-robin algorithm, which considers the priority of every task before assigning the tasks to different virtual machines (VMs). The proposed algorithm uses the priority of tasks to decide to which VMs the tasks should be assigned dynamically. The same process is used to migrate the tasks from overloaded VMs to under-loaded VMs. The simulations are conducted using CloudSim by varying cloud resources. Simulation results show that the proposed algorithm performs equivalent to the dynamic weighted round robin algorithm in all the QoS factors, but it shows significant improvement in handling high-priority tasks. 

   more » « less
3. Fine-grained dynamic load balancing in spatial join by work stealing on distributed memory

   https://doi.org/10.1145/3557915.3560936  

   Yang, Jie ; Puri, Satish ; Zhou, Hui ( November 2022 , Proceedings of the 30th International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL))

   Spatial join is an important operation for combining spatial data. Parallelization is essential for improving spatial join performance. However, load imbalance due to data skew limits the scalability of parallel spatial join. There are many work sharing techniques to address this problem in a parallel environment. One of the techniques is to use data and space partitioning and then scheduling the partitions among threads/processes with the goal of minimizing workload differences across threads/processes. However, load imbalance still exists due to differences in join costs of different pairs of input geometries in the partitions. For the load imbalance problem, we have designed a work stealing spatial join system (WSSJ-DM) on a distributed memory environment. Work stealing is an approach for dynamic load balancing in which an idle processor steals computational tasks from other processors. This is the first work that uses work stealing concept (instead of work sharing) to parallelize spatial join computation on a large compute cluster. We have evaluated the scalability of the system on shared and distributed memory. Our experimental evaluation shows that work stealing is an effective strategy. We compared WSSJ-DM with work sharing implementations of spatial join on a high performance computing environment using partitioned and un-partitioned datasets. Static and dynamic load balancing approaches were used for comparison. We study the effect of memory affinity in work stealing operations involved in spatial join on a multi-core processor. WSSJ-DM performed spatial join using ST_Intersection on Lakes (8.4M polygons) and Parks (10M polygons) in 30 seconds using 35 compute nodes on a cluster (1260 CPU cores). A work sharing Master-Worker implementation took 160 seconds in contrast. 

   more » « less
4. Accelerating Distributed Graphical Fluid Simulations with Micro‐partitioning

   https://doi.org/10.1111/cgf.13809  

   Qu, Hang ; Mashayekhi, Omid ; Shah, Chinmayee ; Levis, Philip ( September 2019 , Computer Graphics Forum)

   Graphical fluid simulations are CPU‐bound. Parallelizing simulations on hundreds of cores in the computing cloud would make them faster, but requires evenly balancing load across nodes. Good load balancing depends on manual decisions from experts, which are time‐consuming and error prone, or dynamic approaches that estimate and react to future load, which are non‐deterministic and hard to debug.

   This paper proposes Birdshot scheduling, an automatic and purely static load balancing algorithm whose performance is close to expert decisions and reactive algorithms without their difficulty or complexity. Birdshot scheduling's key insight is to leverage the high‐latency, high‐throughput, full bisection bandwidth of cloud computing nodes. Birdshot scheduling splits the simulation domain into many micro‐partitions and statically assigns them to nodes randomly. Analytical results show that randomly assigned micro‐partitions balance load with high probability. The high‐throughput network easily handles the increased data transfers from micro‐partitions, and full bisection bandwidth allows random placement with no performance penalty. Overlapping the communications and computations of different micro‐partitions masks latency.

   Experiments with particle‐level set, SPH, FLIP and explicit Eulerian methods show that Birdshot scheduling speeds up simulations by a factor of 2‐3, and can out‐perform reactive scheduling algorithms. Birdshot scheduling performs within 21% of state‐of‐the‐art dynamic methods that require running a second, parallel simulation. Unlike speculative algorithms, Birdshot scheduling is purely static: it requires no controller, runtime data collection, partition migration or support for these operations from the programmer.

    

   more » « less
5. Mu: An Efficient, Fair and Responsive Serverless Framework for Resource-Constrained Edge Clouds

   https://doi.org/10.1145/3472883.3487014  

   Mittal, Viyom ; Qi, Shixiong ; Bhattacharya, Ratnadeep ; Lyu, Xiaosu ; Li, Junfeng ; Kulkarni, Sameer G. ; Li, Dan ; Hwang, Jinho ; Ramakrishnan, K. K. ; Wood, Timothy ( November 2021 , Proceedings of the ACM Symposium on Cloud Computing)

   Serverless computing platforms simplify development, deployment, and automated management of modular software functions. However, existing serverless platforms typically assume an over-provisioned cloud, making them a poor fit for Edge Computing environments where resources are scarce. In this paper we propose a redesigned serverless platform that comprehensively tackles the key challenges for serverless functions in a resource constrained Edge Cloud. Our Mu platform cleanly integrates the core resource management components of a serverless platform: autoscaling, load balancing, and placement. Each worker node in Mu transparently propagates metrics such as service rate and queue length in response headers, feeding this information to the load balancing system so that it can better route requests, and to our autoscaler to anticipate workload fluctuations and proactively meet SLOs. Data from the Autoscaler is then used by the placement engine to account for heterogeneity and fairness across competing functions, ensuring overall resource efficiency, and minimizing resource fragmentation. We implement our design as a set of extensions to the Knative serverless platform and demonstrate its improvements in terms of resource efficiency, fairness, and response time. Evaluating Mu, shows that it improves fairness by more than 2x over the default Kubernetes placement engine, improves 99th percentile response times by 62% through better load balancing, reduces SLO violations and resource consumption by pro-active and precise autoscaling. Mu reduces the average number of pods required by more than ~15% for a set of real Azure workloads. 

   more » « less