Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Load-balancing in parallel processing application

I'm building a network-distributed parallel processing application that uses a combination of CPU and GPU resources across many machines.

The app has to perform some very computationally expensive operations on a very large dataset over thousands of iterations:

for step = 0 to requested_iterations
  for i = 0 to width
    for j = 0 to height
      for k = 0 to depth
        matrix[i,j,k] = G*f(matrix[i,j,k])

Also, the matrix operations have to be executed synchronously: that is, each iteration depends on the results of the frame that came immediately before it.

The hardware available in this ad-hoc grid, comprising both dedicated servers and idle desktop machines, varies greatly in performance from machine to machine. I'm wondering what the best way is to balance the work load across the entire system.

Some idiosyncracies:

  1. The grid should be as robust as possible. Some simulations require weeks to run, and it would be nice not to have to cancel a run if one out of 100 machines goes offline.

  2. Some of the lower-end machines (desktops that are idle but have to wake up when someone logs in) may join and leave the grid at any time.

  3. The dedicated servers may also join and leave the grid, but this is predictable.

So far, what the best idea I've been able to come up with is:

  1. Have each node track the time itself takes to process a group of n cells in the matrix (cells processed per unit time) and report this to a central repository.
  2. Weight this time against the total time for a frame (across the entire grid) of the simulation and the total size of the problem domain. So, each node would get a score expressed in work units (matrix cells) per time, and a scalar rating expressing its performance vs the rest of the grid.
  3. On each frame, distribute the work load based on those scores so that each machine finishes as close to the same time as possible. If machine A is 100x faster than machine B, it will receive 100x as many matrix cells to process in a given frame (assuming that the matrix size is large enough to warrant including the extra machines).
  4. Nodes that leave the grid (desktops that are logged into, etc.) will have their workload redistributed among the remaining nodes.

Or,

Arrange the nodes in a tree structure, where each node has a "weight" assigned. Nodes that are higher in the tree have a weight based on their ability combined with that of their children. This weight is adjusted per frame. When a node loses communication its child, it uses a cached tree graph to contact the orphaned children and re-balance its branch.

If it makes a difference, the app is a combination of C# and OpenCL.

Links to papers, example apps, and especially tutorials are welcome.

Edit

This isn't homework. I'm turning a simulator I wrote as part of my thesis into a more useful product. Right now the work is distributed uniformly with no accounting for performance of each machine, and no facility to recover from machines joining or leaving the grid.

Thanks for the excellent, detailed responses.

like image 607
3Dave Avatar asked Aug 26 '11 15:08

3Dave


People also ask

What is load balancing used for?

Load balancing refers to efficiently distributing incoming network traffic across a group of backend servers, also known as a server farm or server pool.

What is the example of load balancing?

So, for example: if application server #1 is twice as powerful as application server #2 (and application server #3), application server #1 is provisioned with a higher weight and application server #2 and #3 get the same, lower, weight.

What is parallel computing and its applications?

It is the use of multiple processing elements simultaneously for solving any problem. Problems are broken down into instructions and are solved concurrently as each resource that has been applied to work is working at the same time.


2 Answers

For heterogeneous clusters, I like to let each processor request a new job as the processor becomes available. Implementation involves a light weight server that can handle many requests at a time (but usually only returns a job number). Implementation might go something like this:

  • Break the job down into its smallest components (we know there are 1000 tasks now)
  • Start a network server (preferably UDP with timeouts to avoid network congestion) which counts upwards
  • Start your cluster processes.
  • Each process asks, "What job number should I perform?" and the server replies with a number
  • As the process finishes, it asks for the next job number. When all tasks are complete, the server returns a -1 to the processes, so they shut down.

This is a lighter weight alternative to what you suggest above. Your fast processors still do more work than your slower machines, but you don't have to calculate how long the tasks take. If a processor drops out for whatever reason, it will stop asking for tasks. Your server could choose to recycle task numbers after a certain amount of time.

This is pretty much what a cluster scheduler would do on its own, except the processors don't have startup and shutdown costs, so your individual tasks can be smaller without penalty.

like image 113
michael Avatar answered Sep 22 '22 12:09

michael


I would go for decentralized solution.

Every node picks (not given) same amount of work from center. After some run every node is able to deside for itself an average power of calculation and communicate it with others.

After all every node will have a table of every node's average calc power. Having this information (could be even persistant,why not?) each node can deside to "ask" some other node with more power to delegate a stuff to it by signing a contract.

Before every process start every node have to make broadcast signal about: "I start doing X". One time finished always broadcast: "I finished X".

Well, it's no so easy, cause there will be case when you begin job, after your hard disk failed and you will never finish it. Others, especially those ones who are waiting a result from you should figure out this and pick from the basket your job and begin the stuff from the beginning. Here come "ping" technique with timer.

Bad: The first tuning time can take non indifferent amount of time.

Good: You will have almost fault tolerant solution. Leave them for a week, and even if some of nodes fail your grid still alive and does its work.

Many years ago I did something like this and with pretty good results. But it wasn't definitely on such large scale as described by you. And scale, actually, makes a difference.

So the choice is up to you.

Hope this helps.

like image 28
Tigran Avatar answered Sep 23 '22 12:09

Tigran