Load Balancing Problem Using C++

Filed Under: C++
Load Balancing Problem Using C

Today, we’ll learn to solve the load balancing problem using C++. It is an interesting greedy problem. This problem is also known as the life problem. Greedy problems are very important for interview preparation. There can be multiple solutions to the same problem but we aim to learn the most efficient one. So without wasting any time, let’s go through the problem statement.

Problem Statement for Load Balancing Problem Using C++

You own a super-fast computer server consisting of N-hyper-scalar amazingly fast processors Sigma 007. These processors are numbered from 1 to N. Each of these processors processes independent jobs. A new incoming job is assigned to an arbitrary processor. Sometimes, a computer gets assigned too many jobs and others even wait idly. This causes the whole system to undergo rebalancing.

Rebalancing process in rounds: During each round, a processor can transfer at most one job to each of its neighbors on the bus. The goal of the rebalancing is to achieve that all the processors have the same number of jobs.

Determine the balanced load after rebalancing. If rebalancing is not possible, return -1.

For example,

processors_count: 3
load: [0, 99, 3]
max_transfers_needed: 34

processors_count: 2
load: [49, 50]
max_transfers_needed: -1

processors_count: 8
load: [16, 17, 15, 0, 20, 1, 1, 2]
max_transfers_needed: 23

processors_count: 10
load: [0, 0, 100, 0, 0, 0, 0, 0, 0, 0 ]
max_transfers_needed: 70

Approach to Solving Load Balancing Problem Using C++

Note that, this is a minimization problem. We have to minimize the load on all the computers.

  • Calculate the total load on the server.
  • If the total load is not divisible by the total number of computers on the server, rebalancing is not possible. Return -1
  • Otherwise, calculate the load on each computer after balancing the overall load.
    • balanced_load = (total_load / total_number_of_computers);
  • Declare min_diff and set its value to the minimum possible integer.
    • int min_diff = INT_MIN;
  • Now, we’ll start iterating over the loads. For each load, we’ll perform the following logic.
    • Transfer the excess load to the next computer. This will make this computer balanced. Now we’re left with N – 1 computer left to balance.
      • arr[i + 1] += arr[i] – balance_load;
    • Update the difference if:
      • max_diff = max(max_diff, abs(arr[i] – balance_load));
  • Repeat the steps mentioned above for each value of i until i = N – 2.
  • Finally, return the value of max_diff.

Algorithm

Below is the step by step process that we’ll follow to implement the algorithm.

int job_scheduling(vector <int> arr,int n)
{
    int sum = 0;

    for(int i = 0;i < n; i++)
        sum += arr[i];

    if(sum % n != 0)
    {
        return -1;
    }

    int balance_load = (sum / n);

    int max_diff = INT_MIN;

    for(int i = 0;i < n - 1; i++)
    {
            arr[i + 1] += arr[i] - balance_load;
            max_diff = max(max_diff, abs(arr[i] - balance_load));
    }

    return max_diff;
}

Load Balancing Problem Using C++ Program

#include <iostream>
#include <climits>
#include <vector>

using namespace std;

int job_scheduling(vector <int> arr,int n)
{
    int sum = 0;

    for(int i = 0;i < n; i++)
        sum += arr[i];

    if(sum % n != 0)
    {
        return -1;
    }

    int balance_load = (sum / n);

    int max_diff = INT_MIN;

    for(int i = 0;i < n - 1; i++)
    {
            arr[i + 1] += arr[i] - balance_load;
            max_diff = max(max_diff, abs(arr[i] - balance_load));
    }

    return max_diff;
}

int main()
{
    // take the input
    cout << "Enter the number of processors" << endl;
    int N;
    cin >> N;

    // vector to store the load on each processor
    vector <int> arr(N);

    // take the loads as input
    cout << "Enter the load on each processor" << endl;

    for(int i = 0; i < N; i++)
        cin >> arr[i];
    
    // evalute the answer
    int max_diff = job_scheduling(arr, N);

    // print the output
    if(max_diff == -1)
        cout << "Load balancing is not possible for this configuration" << endl;
    else
        cout << "For perfect balance of loads, the max difference is: "<< max_diff << endl;

    return 0;
}
Job Scheduler Code
Load Balancer Code

Output

Load Balancing Problem Output
Load Balancing Problem Output

Conclusion

In this article, we solved the load balancing problem using C++. Notice that, this was a mathematical problem overall. To check if the balancing is possible or not, we took the help of the modulus operator property. In the end, we implemented a C++ program to demonstrate the working of our solution. That’s all for today, thanks for reading.

Further Readings

To learn more about C++ programming, data structures and algorithms, you can go through the following articles.

https://www.journaldev.com/61662/intersection-point-of-two-linked-lists-cpp

https://www.journaldev.com/61310/sort-linked-lists-cpp

close
Generic selectors
Exact matches only
Search in title
Search in content
Post Type Selectors