An IDA algorithm for optimal spare allocation
A new algorithm for the Optimal Spare Allocation problem in reconfigurable arrays is presented. It is based on a previously published branch and bound search method [4]. Enhanced with a strong heuristic function, it yields an effective A∗ search, which performs more efficiently in the iterative deepening implementation (IDA∗). A parallel implementation of the algorithm for a distributed shared memory machine using TreadMarks was used for evaluation. The results demonstrate the efficiency of the scheme and show how computationally intensive problems can be handled by appropriate domain heuristics and cooperative distributed computational power. 1 The Optimal Spare Allocation Problem The Optimal Spare Allocation (OSA) problem (or equivalently Vertex Cover in Bipartite Graphs) [4] is an NP-HARD problem arising in fault tolerant computing. It deals with the optimal allocation of spare rows and columns over a two-dimensional array of cells where some cells are faulty. The cells can be processors, memory units or VLSI components in practical applications. A number of spare rows and a number of spare columns are given, with two costs associated to spare rows and columns respectively. One spare row (column) can replace any row (column) in the array, repairing all the faulty cells along this row (column). The purpose is to repair all the faulty cells using spares, with the minimum possible overall cost. The sample instance [4] given below, consists of a (10×10) array with 12 faulty cells. There are 3 spare rows with a cost of 8 associated to each one of them and 3 spare columns with a cost of 15 associated to each one of them. An optimal solution with a cost of 39 would include the spare row allocations {4, 2, 8} and the spare column allocation {9}. ∗Currently with the Department of Computer Science, Duke University, Durham, NC 27708; Email: mgl@cs.duke.edu. 1 2 3 4 5 6 7 8 9 10 1 2 X X X 3 4 X X X X X 5 6 7 8 X X X 9 10 X