Initial allocation compensation algorithm for redundancy allocation: The scanning heuristic

The tiny feature size in current semiconductor integrated circuits naturally requires redundancy strategies to improve manufacturing yield and operating reliability. To find an optimal redundancy architecture that provides maximum yield and reliability is a trade-off problem. In the reliability optimization field, this type of problem is generally called a redundancy allocation problem. In this paper, we propose a new iterative algorithm, the scanning heuristic, to solve the redundancy allocation problem. The solution quality of conventional iterative heuristics is highly dependent on the initial starting point of the algorithm employed. To overcome this weakness, the scanning heuristic systematically divides the original solution space into several small bounded solution spaces. The local optimum in each divided solution space then becomes a candidate for the final solution. The experimental results demonstrate that the proposed heuristic, and subsequently some combinations of heuristics, are superior to existing heuristics in terms of solution quality.