Solving Memory Reconfiguration and Network Reliability Problems with BDD-based Boolean Transformations
Date Issued
2006
Date
2006
Author(s)
Lin, Hung-Yau
DOI
en-US
Abstract
In volume semiconductor industries, the desire to produce as many defect-free memory chips as possible never ceases. However, as the density of memory chips grows constantly along with the rapid advancement of VLSI technology, it becomes harder and harder to fabricate memory chips containing no defect. For devices having a uniform structure such as dynamic random access memories, introducing spare rows as well as spare columns is one of the effective solutions to compensate for the occurrence of faulty cells. Devices with such redundancy are known as reconfigurable memory arrays. Searching for a solution which replaces with spares all faulty cells of a reconfigurable memory array is called the memory reconfiguration problem or the spare allocation problem. The spare allocation problem has been shown to be NP-complete. The first part of this thesis describes an efficient Boolean transformation technique which transforms a memory reconfiguration problem into a set of Boolean function operations. A repair solution can then be derived from one of the Boolean functions. The idea of the Boolean transformation technique is not limited to spare allocation problems. It can also be applied to problems in other fields.
In the past, many algorithms have been presented to solve network reliability evaluation problems in which vertices are considered perfectly reliable. Such problems have been shown to be a NP-hard problem. However, the vertices as well as the links of a network can fail in the real world. Taking the effect of imperfect vertices into account makes the performance of these algorithms worse. The second part of this thesis presents two low overhead strategies for taking into account the imperfect vertices in a network. In the design of a network topology, it is important to identify the most crucial component, i.e. a vertex or a link, of a network so that efforts can be made to keep it functional. A highly efficient algorithm is also presented in this part to identify the most crucial component of a network. The algorithms presented in the second part require a tool capable of encoding SDP (sum of disjoint products) forms of a Boolean expression.
Efficient tools for Boolean function manipulations are essential for the Boolean encoding/transformation techniques presented in this thesis. The reduced ordered binary decision diagram and the Boolean satisfiability (SAT) are two of the efficient tools. The Boolean operations in the memory reconfiguration problem can be performed with any Boolean solvers, such as the SAT solver or the reduced ordered binary decision diagram. However, a reliability or unavailability expression in the network reliability evaluation problem needs to be stored in a traversable data structure which implicitly encodes the SDP forms of the expression. These requirements exclude the SAT solver from being used in the network reliability evaluation problem. The reduced ordered binary decision diagram is therefore the primary tool used in this thesis.
Subjects
記憶體修復
網路可靠度
有序二元決策圖
布林轉換
布林運算
memory reconfiguration problem
network reliability problem
ordered binary decision diagram
ROBDD
Boolean transformation
Boolean operation
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
ntu-95-F87921110-1.pdf
Size
23.31 KB
Format
Adobe PDF
Checksum
(MD5):302b77c44f2011500b8c3f7c2d0629c1