Initial allocation compensation algorithm for redundancy allocation: The scanning heuristic

IIE Transactions, July, 2008 by Chunghun Ha, Way Kuo

1. Introduction

The manufacturing yield and operating reliability of a complex system can be enhanced with three main approaches: (i) adding redundancies to vulnerable components; (ii) increasing the robustness of the weak components themselves; and (iii) simplifying the system configuration (Kuoet al., 2001; Ha and Kuo, 2005). Among the three, the redundancy strategy is the easiest to apply, and it has been verified as a very effective approach. However, the redundancy strategy consumes relatively large quantities of resources, such as weight, volume, and cost, compared to other methods. As the resource constraints on current products are very tight, the strategy has become less popular, and the methods of improving component reliability and/or simplifying the system structure have gradually come to be more commonly utilized in industry than adding redundancies.

However, current mainstream micron/submicron electronic products, such as semiconductor integrated circuits, systems on a chip, and nanosystems, have revived the importance of the redundancy strategy (Heath et al., 1998; Koren and Koren, 1998). The current downscaling trend in semiconductor architecture makes systems more vulnerable to smaller manufacturing particles and defects. It is well known that certain limitations on enhancing yield and reliability emerge with the development of new robust materials (Doering and Nishi, 2001; Keyes, 2001). Various defecttolerant and self-repairable techniques are frequently recommended to efficiently manage particles and defects, and the redundancy strategy is at the heart of these techniques (Koren and Koren, 1998; Chakraborty and Mazumder, 2002). In fact, most advanced memory integrated circuits and VLSIs, including internal memory blocks, employ a hierarchical redundancy scheme (Yoo et al., 1996; Li et al., 2005; Hara et al., 2006).

Let us consider the manufacturing yield of semiconductor integrated circuits. Assume the following conditions exist: (i) particles are randomly distributed on a wafer with a constant density: (ii) all particles are chip-kill particles; (iii) no other conditions generate the failure of chips. Then, the yield is defined as the ratio of the number of working chips to the total possible number of chips on the wafer. If a redundancy strategy is applied, the number of failed chips decreases, which makes the yield increase. On the other hand, the area of the chip increases because we must assign some additional area to build redundancies on the chip. This causes the yield to decrease because the total number of chips per wafer decreases since the total wafer area is constant. Therefore, to enhance the yield, we have to employ redundancy and decrease the chip area at the same time, which is a contradiction.

To find an optimal redundancy architecture that provides maximum yield and reliability is a trade-off problem. We must efficiently achieve the architecture; in other words, the number of redundancies must be optimized to maximize the yield and reliability under the limited resources. In the reliability optimization field, this type of problem is generally called a redundancy allocation problem. The objective of this paper is to develop an algorithm, specifically a greedy heuristic, that can be applied to various complex systems in which a redundancy strategy is employed. The algorithm can be applied to current defect-tolerant semiconductor systems and, with minor modifications, to future defect-tolerant nanosystems.

In this paper, we propose an efficient iterative heuristic, a scanning heuristic, and its variants. The scanning heuristic finds the best local optimum by solving several subproblems with hierarchical structures. The solution path of each subproblem is bound by a lower bound (actually, an initial allocation) and an upper bound, where the bounds are systematically generated by avoiding as much as possible any overlapping of the solution paths. Because the proposed method does not rely on any assumptions of linearity, separability, single constraint, or convexity, it is very adaptable to various types of redundancy allocation problems. In addition, this method can be combined with many popular heuristics or meta-heuristics where multiple starting points must be considered, such as the genetic algorithm (Coit and Smith, 1996a) and the ant colony optimization (Liang and Smith, 2004).

In Section 2, the mathematical form of the redundancy allocation problem is defined and definitions, notations, and acronyms are listed. In Section 3, the simplest greedy heuristic is introduced, and detailed procedures for the scanning algorithm are presented along with supporting simple examples. Two combinations of heuristics with different properties are explained in Section 4. In Section 5, the computational complexity of several selected heuristics is analyzed. Section 6 demonstrates numerical experiments for the proposed algorithms and other existing heuristics. The conclusion and a discussion are presented in Section 7.