CSC 456 Fall 2013/4a bc
Load Balancing
In multi-processor systems, load-balancing is used to break-up and distribute the work load to individual processors in order to make effective use of processor time. When the work load is divided up at compile-time, the balance is said to be statically balanced. Dividing the work load up during run-time is dynamically balancing the load. Static load balancing has reduced overhead as the work is divided before run time. Dynamic load balancing assigns work as processors become idle, so there is greater overhead. However, dynamic balancing can lead to increased performance of load balancing due to being able to assign work to a processor when it does become idle, reducing the overall idle time of processors.
Static Vs. Dynamic Techniques
Static Load balancing
Round Robin
Round robin is a load balancing technique which evenly distributes tasks across available processors. Each processor is lined up, and given a task one after the other until it loops around again back to the first processor. Visualize a dealer in a casino passing out cards to each player in a circle, one at a time. The advantage is that this is a very simple load balancing technique to implement, with very little overhead. A disadvantage is that there is no care given to the job size or performance. This can create problems if a processor is unlucky and is continually assigned large tasks, causing it to fall behind.
Random
Central Manager
Dynamic Load Balancing
Local Queue
Central Queue
Real World applications of Load Balancing
Examples of Load Balancing in action
Server Load balancing pseudocode
server_load_vec_desc = sort_descending(server_load_vec);
server_load_vec_asc = sort_ascending(server_load_vec);
while (server_load_vec_desc[0].deviation > DEVIATION_THRESHOLD) {
populate_range_load_vector(server_load_vec_desc[0].server_name);
sort descending range_load_vec;
i=0;
while (server_load_vec_desc[0].deviation > DEVIATION_THRESHOLD &&
i < range_load_vec.size()) {
if (moving range_load_vec[i] from server_load_vec_desc[0] to server_load_vec_asc[0] reduces deviation) {
add range_load_vec[i] to balance plan
partial_deviation = range_load_vec[i].loadestimate * loadavg_per_loadestimate;
server_load_vec_desc[0].loadavg -= partial_deviation;
server_load_vec_desc[0].deviation -= partial_deviation;
server_load_vec_asc[0].loadavg += partial_deviation;
server_load_vec_asc[0].deviation += partial_deviation;
server_load_vec_asc = sort_ascending(server_load_vec_asc);
}
i++;
}
if (i == range_load_vec.size())
remove server_load_vec_desc[0] and corresponding entry in server_load_vec_asc
server_load_vec_desc = sort_descending(server_load_vec_desc);
}