In the past, I spent considerable time trying to work out an optimal way to answer the find an idle node problem. Each time I thought I had found "the way" my approach got more and more complicated. Finally, at one point, I thought, all the fancy ideas seem to no better than just picking any node. Then it dawned on me, the simplest way to find a free node is to pick a node at random. Pages of code became victims of the delete key due to this simple idea. In my later years, I have learned that randomness is a powerful tool when facing problems that have no easy solution. A dart thrown at the stock listings always seems to better than the best stock broker. (Hint: Place a dart board behind the stock listings, don't have the stock broker hold then up.)
About that heartbeat idea. It may be better to call it a handshake instead of a heartbeat because both the master and worker can benefit. Master nodes can send their workers a periodic handshake. If the node does not reply, the master knows for sure that the node is dead and the nodes work must be redone (on the master or on another worker). On the worker node, if a worker stop getting a reply from the master, then it can assume the master is dead or has finished without the worker, and stop working. The node then become free to do other work.
We can now come back to issue of redundant work. A very valid point. A possible refinement is to assign a limit to the number of worker nodes a master may use. lets call this a Branch Number. If this number is zero for all branches (loops), then the program runs on one node. If it is equal to the number of nodes in the cluster, then the program could flood the cluster with redundant work. There is probably an optimum number for each branch point in the program. How is this number determined? There could be several ways, a compiler could guess at this, but it is hard to know how the program will behave for a given cluster at runtime. Another way is to let the program optimize these for a given cluster. It may take several runs, but the program could optimize itself for a specific cluster. All that would be needed is set of list of Branch Numbers for that particular cluster. Dynamic behavior would also help load balance the cluster. If you think of two or more dynamic programs running on a cluster, then they could easily be competing for resources. The end result is a single binary that adapts at run-time to various cluster hardware, cluster loads, and to node failure. Just what I wanted.
As to issues of interconnect type or processor speed. A self tuning dynamic program will run as best it can within a given hardware environment. This means that the number of nodes a program uses will depend on the cluster internals. The idea is that instead of writing codes to use a fixed number of nodes, the program will find the best number that will work on the cluster at hand.
You Have Finally Lost Your Mind
So there you have it, the path is clear, dynamic execution can give us what we really need in the cluster world. (well, at least what I want). Of course, many of you now believe I have have gone off-the-deep-end. Furthermore, I am sure you may have questions or polite insightful comments about this approach to computing. (All of which I would love the hear about, you may contact me through clustermonkey.net). My goal here was not to design new algorithm per se , but rather to throw another log on the cluster discussion fire.Actually, I must confess, some of the ideas are not that new. A similar type of problem occurs every day in the networking world. As you know, a network is a shared device. How do arbitrary computers connected to an Ethernet network handle the traffic on the network. Instead of some complicated algorithm or central control device that helps manage traffic (that would by itself generate more traffic), Ethernet uses the power of randomness. If an Ethernet device finds the network busy, it waits for a random amount of time, and then retries. Simple, robust and low overhead.
In the future, I believe cluster computing can work the same way, but there is one more thing that has to happen before we can become the ultimate master of our nodes. Next month, we'll talk about how to express your problem so that it is more amenable to dynamic execution. Warning: Some of you are going to get upset.
Note: This article is the second of three part series. The first and third parts are:
- Part One: Cluster Programming: You Can't Always Get What You Want
- Part Three: Cluster Programming: Explicit Implications of Cluster Computing
This article was originally published in Linux Magazine. It has been updated and formatted for the web. If you want to read more about HPC clusters and Linux you may wish to visit Linux Magazine.
Douglas Eadline can be found swinging randomly through the trees at here at ClusterMonkey
