We demonstrate the efficiency of this scheme by solving some NP-complete problems on a network of up to 256 Transputers.
Every processor performs the same algorithm but on a different part of the solution tree.
In this case, it is necessary to distribute subproblems among the processors to achieve a well balanced workload. We present a load balancing method which overcomes the problem of search overhead and idle times by an appropriate load model and avoids trashing effects by a feedback control strategy. To show the performance of our strategy, we solved the Vertex Cover and the weighted Vertex Cover problem for graphs of up to 150 nodes, using highly efficient branch and bound algorithms. Although the computing times were very short on a 256 processor network, we were able to achieve a speedup of up to 237.32 on a 256 processor DeBruijn network, compared to the sequential algorithm.