An Algorithm for Optimal Spare Allocation Parallel Implementation for Distributed Shared Memory Machine using TreadmarksTM
The Spare Allocation problem (or equivalently Vertex Cover in bipartite graphs) deals with the optimal allocation of spare rows and columns over a two-dimensional array of cells, some of which are faulty. The purpose is to repair all the faulty cells using spares with the minimum possible overall cost. In order to solve the problem optimally, a branch and bound algorithm is employed. Several heuristics for pruning the search tree and a heuristic that estimates the final cost from partial solutions are used to inform and guide the search procedure, leading to an effective A* search algorithm. However, memory limitations on one hand and the good enough quality of the heuristic function that low bounds the cost, on the other, force an Iterative Deepening implementation of the algorithm (IDA * ). Moving in the parallel implementation, many complications arise. A * is by its nature sequential and attempts to parallelize it, led to an amount of redundant search and/or early memory overflows. IDA * provides for parallelism, but work balancing issues should be addressed carefully. The final parallel IDA * search algorithm is scalable and leads to a significant amount of speedup, as demonstrated by the experimental results.