Carafe extracts break fault primitives one electrical node at a time by constructing a graph for each electrical node using a plane sweep algorithm. The vertices in this graph represent devices in the circuit, such as transistor terminals, transistor gate connections, and I/O ports. Each vertex is given a unique name of the form node_#, where node is the name of the electrical node, and # a number which makes the name of each vertex unique. The edges in this graph represent places where the electrical node can break; each edge has a list of it length-widths which represent material that, if broken, cause the nodes to become disconnected. Carafe creates fault primitives for each length-width on the edge lists, where the names of the two objects affected by the fault will be the names of the two vertices in the graph connected by the edge. Carafe repeats this process for each electrical node in the circuit until all break fault primitives have been extracted. Carafe will then sort the break primitives by layer and perform compound fault extraction one layer at a time.
Figure 4.8: The layout of a typical standard-cell inverter.
Figure 4.9: Conversion of the In node to a graph: (a) the graph of the node, (b) the length-widths attached to the graph edges.
Figure 4.8 shows a simple inverter. Figure 4.9 (a) shows the graph constructed for the In node and Figure 4.9 (b) shows the length-widths associated with each edge in the graph. There are three kinds of length-widths: vertical, horizontal, and inter-layer. Length-widths 1, 2, 6, 7, 8 and 9 are vertical length-widths, 4 is a horizontal length-width, and 3 and 5 are inter-layer length-widths. The critical areas for the vertical, horizontal, and inter-layer length-widths are the same as the horizontal, vertical, and diagonal length-widths shown in Figure 4.5, respectively.
Carafe reports break faults by listing the pairs of nodes that are disconnected by the breaks. For example, if length-width 1 from Figure 4.9 (b) were to cause a break, Carafe would report the following break:
(In_0 and In_1)
Note that in Figure 4.9 (b) length-width 3 is a metal 2 contact break so it does not interact with any other fault primitives during compound fault extraction. Carafe does not extract break primitives at junctions like that in Figure 4.9 (b) where vertex In_1 is located. Instead, Carafe depends on the critical areas from breaks around the junction to overlap in order to detect the break. Figure 4.10 shows the two critical areas for length-widths 1 and 2 from Figure 4.9 (a) for some defect size. Figure 4.10 (b) shows the resulting overlapping critical areas. Region 1 represents the critical area for the break:
region 2 represents the critical area for the breaks:(In_0 and In_1)
and region 3 represents the critical area for the break:(In_0 and In_1) (In_1 and In_2)
(In_1 and In_2)
Figure 4.10: (a) Critical areas for two length-widths 1 and 2, (b) Regions formed by overlapping critical areas.
This procedure will produce inter-node compound break faults, and generally the most ``accurate'' break faults. However, Carafe is capable of simplifying the process to save both time and space by extracting only intra-node break faults. The change in the above procedure is that after all fault primitives for a node are extract, they are be sorted by layer and compound fault extraction is performed using only those primitives. Once fault extraction is complete, Carafe discards these fault primitives. This process is repeated for each electrical node in the circuit. After every electrical node in the circuit had been extracted, all break faults have been found.
This procedural modification treats defects that break more than one node as though only a single node was affected. This saves time and space since all break fault primitives do not have to be available at the same time, and the number of possible faults is reduced as there are fewer combinations of objects to break. The reduced input to the compound fault extractor and the reduced fault size greatly improves performance. However, the critical area for defects causing inter-node breaks are counted multiple times, once for each node they break.