n-diffusion p-diffusion metal metal-2 FIGURE 25.4 Different layers. CAD system also supports verification, synthesis, and testing of the design. Using a CAD system, the designer can make sure that all of the parts work before actually implementing the design A variety of VLSI CAD systems are commercially available that perform all or some of the levels of abstraction of design. Most of these systems support a layout editor for designing a circuit layout. A layout-editor is software that provides commands for drawing lines and boxes, copying objects, moving objects, erasing unwanted objects, and so on. The output of such an editor is a design file that describes the layout. Usually, the design file is represented in a standard format, called Caltech Intermediate Form(CIF), which is accepted by the fabrication industr What Is layout? For a specific circuit, a layout specifies the position and dimension of the different layers of materials as they would be laid on the silicon wafer. However, the layout description is only a symbolic representation, which implifies the description of the actual fabrication process. For example, the layout representation does not explicitly indicate the thickness of the layers, thickness of oxide coating, amount of ionization in the transistors channels, etc., but these factors are implicitly understood in the fabrication process. Some of the main layers used in any layout description are n-diffusion, p-diffusion, poly, metal-l, and metal-2. Each of these layers is represented by a polygon of a particular color or pattern. As an example, Fig 25.4 presents a specific pattern for each layer that will be used through the rest of this section. As is shown in Fig. 25.5, an n-diffusion layer crossing a poly layer implies an nMOS transistor, and a P-diffusion crossing poly implies a pMOS transistor. Note that the widths of diffusion and poly are represented with a scalable parameter called lambda. These measurements, referred to as design rules, are introduced to prevent errors on the chip, such as preventing thin lines from opening(disconnecting)and short circuiting p-diffusion (before fabrication) (before fabrication) silicon oxide D-diffusion n-diffusion cross-sectional view arte (after fabrication) 9 -nMos transistor b- pMOS transistor FIGURE 25.5 Layout and fabrication of MOS transistors. c 2000 by CRC Press LLC
© 2000 by CRC Press LLC CAD system also supports verification, synthesis, and testing of the design. Using a CAD system, the designer can make sure that all of the parts work before actually implementing the design. A variety of VLSI CAD systems are commercially available that perform all or some of the levels of abstraction of design. Most of these systems support a layout editor for designing a circuit layout.A layout-editor is software that provides commands for drawing lines and boxes, copying objects, moving objects, erasing unwanted objects, and so on. The output of such an editor is a design file that describes the layout. Usually, the design file is represented in a standard format, called Caltech Intermediate Form (CIF), which is accepted by the fabrication industry. What Is Layout? For a specific circuit, a layout specifies the position and dimension of the different layers of materials as they would be laid on the silicon wafer. However, the layout description is only a symbolic representation, which simplifies the description of the actual fabrication process. For example, the layout representation does not explicitly indicate the thickness of the layers, thickness of oxide coating, amount of ionization in the transistors channels, etc., but these factors are implicitly understood in the fabrication process. Some of the main layers used in any layout description are n-diffusion, p-diffusion, poly, metal-1, and metal-2. Each of these layers is represented by a polygon of a particular color or pattern. As an example, Fig. 25.4 presents a specific pattern for each layer that will be used through the rest of this section. As is shown in Fig. 25.5, an n-diffusion layer crossing a poly layer implies an nMOS transistor, and a p-diffusion crossing poly implies a pMOS transistor. Note that the widths of diffusion and poly are represented with a scalable parameter called lambda. These measurements, referred to as design rules, are introduced to prevent errors on the chip, such as preventing thin lines from opening (disconnecting) and short circuiting. FIGURE 25.4 Different layers. FIGURE 25.5 Layout and fabrication of MOS transistors
n-diffusion mask poly mask cross-sectional view FIGURE 25.6 Fabrication steps for an nMOS transistor. Implementing the design rules based on lambda makes the design process independent of the fabrication process. This allows the design to be rescaled as the fabrication process improves Metal layers are used as wires for connections between the components. This is because metal has the lowest propagation delay compared to the other layers. However, sometimes a poly layer is also used for short wires in order to reduce the complexity of the wire routing. Any wire can cross another wire without getting electricall affected as long as they are in different layers. Two different layers can be electrically connected together using contacts. The fabrication process of the contacts depends on types of the layers that are to be connected. Therefore, a layout editor supports different types of contacts by using different patterns From the circuit layout, the actual chip is fabricated. Based on the layers in the layout, various layers of materials,one on top of the others, are laid down on a silicon wafer. Typically, the processing of laying down each of these materials involves several steps, such as masking, oxide coating, lithography and etching [Mead and Conway, 1980]. For example, as shown in Fig. 25.6(a), for fabricating an nMOS transistor, first two mask one for poly and one for n-diffusion, are obtained from the circuit layout. Next, the n-diffusion mask is used to create a layer of silicon oxide on the wafer [see Fig. 25. 6(b). The wafer will be covered with a thin layer of oxide in places where the transistors are supposed to be placed as opposed to a thick layer in other places. The poly mask is used to place a layer of polysilicon on top of the oxide layer to define the gate terminals of the transistor [see Fig. 25.6(c)). Finally, the n-diffusion regions are made to form the source and drain terminals of the transistor [see Fig. 25.6(d)] To better illustrate the concept of layout design, the design of an inverter in the Cmos technology is shown in Fig. 25.7. An inverter produces an output voltage that is the logical inverse of its input. Considering the circuit diagram of Fig. 25.7(a), when the input is 1, the lower nMOS is on, but the upper pMOS is off. Thus, the output becomes o by becoming connected to the ground through the nMOS. On the other hand, if the input is 0, the pMOS is on and the nMOS is off, so the output must find a charge-up path through the pMOS to the supply and therefore becomes 1. Figure 25.7(b)represents a layout for such an inverter. As can be seen from this figure, the problem of a layout design is essentially reduced to drawing and painting a set of polygons. Layout editors provide commands for drawing such polygons. The commands are usually entered at the keyboard or with a mouse and, in some menu-driven packages, can be selected as options from a pull-down menu. c 2000 by CRC Press LLC
© 2000 by CRC Press LLC Implementing the design rules based on lambda makes the design process independent of the fabrication process. This allows the design to be rescaled as the fabrication process improves. Metal layers are used as wires for connections between the components. This is because metal has the lowest propagation delay compared to the other layers. However, sometimes a poly layer is also used for short wires in order to reduce the complexity of the wire routing.Any wire can cross another wire without getting electrically affected as long as they are in different layers. Two different layers can be electrically connected together using contacts. The fabrication process of the contacts depends on types of the layers that are to be connected. Therefore, a layout editor supports different types of contacts by using different patterns. From the circuit layout, the actual chip is fabricated. Based on the layers in the layout, various layers of materials, one on top of the others, are laid down on a silicon wafer. Typically, the processing of laying down each of these materials involves several steps, such as masking, oxide coating, lithography and etching [Mead and Conway, 1980]. For example, as shown in Fig. 25.6(a), for fabricating an nMOS transistor, first two masks, one for poly and one for n-diffusion, are obtained from the circuit layout. Next, the n-diffusion mask is used to create a layer of silicon oxide on the wafer [see Fig. 25.6(b)]. The wafer will be covered with a thin layer of oxide in places where the transistors are supposed to be placed as opposed to a thick layer in other places. The poly mask is used to place a layer of polysilicon on top of the oxide layer to define the gate terminals of the transistor [see Fig. 25.6(c)]. Finally, the n-diffusion regions are made to form the source and drain terminals of the transistor [see Fig. 25.6(d)]. To better illustrate the concept of layout design, the design of an inverter in the CMOS technology is shown in Fig. 25.7. An inverter produces an output voltage that is the logical inverse of its input. Considering the circuit diagram of Fig. 25.7(a), when the input is 1, the lower nMOS is on, but the upper pMOS is off. Thus, the output becomes 0 by becoming connected to the ground through the nMOS. On the other hand, if the input is 0, the pMOS is on and the nMOS is off, so the output must find a charge-up path through the pMOS to the supply and therefore becomes 1. Figure 25.7(b) represents a layout for such an inverter. As can be seen from this figure, the problem of a layout design is essentially reduced to drawing and painting a set of polygons. Layout editors provide commands for drawing such polygons. The commands are usually entered at the keyboard or with a mouse and, in some menu-driven packages, can be selected as options from a pull-down menu. FIGURE 25.6 Fabrication steps for an nMOS transistor
pMOS output (e)Circuit diogram FIGURE 25.7 An inverter. net 4 FIGURE 25.8 Placement and routing In addition to the drawing commands, often a layout system provides tools for minimizing the overall area of the layout(i. e, size of the chip). Today a VLSI chip consists of a lot of individual cells, with each one laid out separately. A cell can be an inverter, a NAND gate, a multiplier, a memory unit, etc. The designer can make the layout of a cell and then store it in a file called the cell library. Later, each time the designer wants to design a circuit that requires the stored cell, he or she simply copies the layout from the cell library. A layout may consist of many cells. Most of the layout systems provide routines, called floorplanning, placement and routing routines, for placing the cells and then interconnecting them with wires in such a way that minimizes the layout area. As an example, Fig 25.8 presents the placement of three cells. The area between the cells is used for op uting. The entire routing surface is divided into a set of rectangular routing areas called channels. The sides each channel consist of a set of terminals. A wire that connects the terminals with the same id is called a net. The router finds a location for the wire segments of each net within the channel. The following sections classify various types of placement and routing techniques and provide an overview of the main steps of some Floorplanning Techniques The floorplanning problem in Computer Aided Design of Integrated Circuits is similar to that in Architecture and the goal is to find a location for each cell based on proximity (layout adjacency) criteria to other cells. we c 2000 by CRC Press LLC
© 2000 by CRC Press LLC In addition to the drawing commands, often a layout system provides tools for minimizing the overall area of the layout (i.e., size of the chip). Today a VLSI chip consists of a lot of individual cells, with each one laid out separately. A cell can be an inverter, a NAND gate, a multiplier, a memory unit, etc. The designer can make the layout of a cell and then store it in a file called the cell library. Later, each time the designer wants to design a circuit that requires the stored cell, he or she simply copies the layout from the cell library. A layout may consist of many cells. Most of the layout systems provide routines, called floorplanning, placement and routing routines, for placing the cells and then interconnecting them with wires in such a way that minimizes the layout area. As an example, Fig. 25.8 presents the placement of three cells. The area between the cells is used for routing. The entire routing surface is divided into a set of rectangular routing areas called channels. The sides of each channel consist of a set of terminals. A wire that connects the terminals with the same ID is called a net. The router finds a location for the wire segments of each net within the channel. The following sections classify various types of placement and routing techniques and provide an overview of the main steps of some of these techniques. Floorplanning Techniques The floorplanning problem in Computer Aided Design of Integrated Circuits is similar to that in Architecture and the goal is to find a location for each cell based on proximity (layout adjacency) criteria to other cells. We FIGURE 25.7 An inverter. FIGURE 25.8 Placement and routing
7 FIGURE 25.9 A hierarchical floorplan and its associated tree. The root node has degree 5. The internal node labeled with I indicates a vertical slicing. The internal node labeled with -indicates a horizontal slicing 1234 FIGURE 25.10 a sliceable floorplan and its associated binary tree consider rectangular floorplans whose boundaries are rectangles. It is desirable to obtain a floorplan that minimizes the overall area of the layout An important goal in floorplanning is the cell sizing problem where the goal is to determine the dimensions of variable cells whose area is invariant. All cells are assumed to be rectangular, and in the cell sizing problem the goal is to determine the width and height of each cell subject to predetermined upper and lower bounds on their ratio, and to their product being equal to its area, so that the final floorplan has optimal area. One of the early approaches in floorplanning is the hierarchical, where recursive bipartition or partition into more than two parts is recursively employed and a floorplan tree is constructed. The tree simply reflects the hierarchical construction of the floorplan. Figure 25.9 shows a hierarchical floorplan and its associated tree The partitioning problem and related algorithms are discussed extensively later in this section. Many early hierarchical floorplanning tools insist that the floorplan be sliceable. a sliceable floorplan is recursively defined as follows: (a)a cell or(b)a floorplan that can be bipartitioned into two sliceable floorplans with either a horizontal or vertical line. Figure 25 10 shows a sliceable floorplan whose tree is binary Many tools that produce sliceable floorplans are still in use because of their mplicity. In particular, many problems arising in sliceable floorplanning are solv able optimally in polynomial time [Sarrafzadeh and Wong, 1996]. Unfortunately, sliceable floorplans are rarely optimal (in terms of their area), and they often result in layouts with very difficult routing phases.( Routing is discussed later in this section.) Figure 25 11 shows a compact floorplan that is not sliceable. Hierarchical tools that produce nonsliceable floorplans have also been proposed [Sarrafzadeh and Wong, 1996]. The major problem in the development of such tools is that we are often facing problems that are intractable and thus we have to FIGURE 25.11 A com problem can be tackled optimally in sliceable floorplans [Otten, 1983 and Stock- sliceable ut that is not ly on heuristics in order to obtain fast solutions. For example, the cell sizing pact layo meyer,1983] but the problem is intractable for general nonsliceable floorplans A second approach to floorplanning is the rectangular dual graph. The idea here is to use duality arguments and express the cell adjacency constraints in terms of a graph, and then use an algorithm to translate the graph into a rectangular floorplan. A rectangular dual graph of a rectangular floorplan is a planar graph G=(VE) where V is the set of cells and E is the set of edges, and an edge(Cnc )is in E if and only if cells Ci and cz are adjacent in the floorplan. See Fig. 25. 12 for a rectangular floorplan and its rectangular dual graph G
© 2000 by CRC Press LLC consider rectangular floorplans whose boundaries are rectangles. It is desirable to obtain a floorplan that minimizes the overall area of the layout. An important goal in floorplanning is the cell sizing problem where the goal is to determine the dimensions of variable cells whose area is invariant. All cells are assumed to be rectangular, and in the cell sizing problem the goal is to determine the width and height of each cell subject to predetermined upper and lower bounds on their ratio, and to their product being equal to its area, so that the final floorplan has optimal area. One of the early approaches in floorplanning is the hierarchical, where recursive bipartition or partition into more than two parts is recursively employed and a floorplan tree is constructed. The tree simply reflects the hierarchical construction of the floorplan. Figure 25.9 shows a hierarchical floorplan and its associated tree. The partitioning problem and related algorithms are discussed extensively later in this section. Many early hierarchical floorplanning tools insist that the floorplan be sliceable. A sliceable floorplan is recursively defined as follows: (a) a cell or (b) a floorplan that can be bipartitioned into two sliceable floorplans with either a horizontal or vertical line. Figure 25.10 shows a sliceable floorplan whose tree is binary. Many tools that produce sliceable floorplans are still in use because of their simplicity. In particular, many problems arising in sliceable floorplanning are solvable optimally in polynomial time [Sarrafzadeh and Wong, 1996]. Unfortunately, sliceable floorplans are rarely optimal (in terms of their area), and they often result in layouts with very difficult routing phases. (Routing is discussed later in this section.) Figure 25.11 shows a compact floorplan that is not sliceable. Hierarchical tools that produce nonsliceable floorplans have also been proposed [Sarrafzadeh and Wong, 1996]. The major problem in the development of such tools is that we are often facing problems that are intractable and thus we have to rely on heuristics in order to obtain fast solutions. For example, the cell sizing problem can be tackled optimally in sliceable floorplans [Otten, 1983 and Stockmeyer, 1983] but the problem is intractable for general nonsliceable floorplans. A second approach to floorplanning is the rectangular dual graph. The idea here is to use duality arguments and express the cell adjacency constraints in terms of a graph, and then use an algorithm to translate the graph into a rectangular floorplan. A rectangular dual graph of a rectangular floorplan is a planar graph G = (V,E), where V is the set of cells and E is the set of edges, and an edge (C1,C2) is in E if and only if cells C1 and C2 are adjacent in the floorplan. See Fig. 25.12 for a rectangular floorplan and its rectangular dual graph G. FIGURE 25.9 A hierarchical floorplan and its associated tree. The root node has degree 5. The internal node labeled with | indicates a vertical slicing. The internal node labeled with — indicates a horizontal slicing. FIGURE 25.10 A sliceable floorplan and its associated binary tree. FIGURE 25.11 A compact layout that is not sliceable
FIGURE 25.12 A rectangular floorplan and its associated dual planer graph → FIGURE 25. 13 A cross junction can be replaced by 2 T-junctions FIGURE 25. 14 For a cycle of size 3 that is not a face we cannot satisfy all constraints. Let us assume that the floorplan does not contain cross junctions. Figure 25. 13 shows a cross junction. This restriction does not significantly increase the area of a floorplan because, as Fig. 25. 13 shows, a cross junction can be replaced by two T-junctions by simply adding a short edge e It has been shown that in the absence of cross junctions the dual graph is planar triangulated(PT),and every T-junction corresponds to a triangulated face of the dual Pt graph. Unfortunately, not all Pt graph have a rectangular floorplan. For example, in the graph of Fig. 25. 14 we cannot satisfy the adjacency require ments of edges(a, b),(b, c)and(c, a) at the same time. Note that the later edges form a cycle of length three that is not a face. It has been shown that a Pt graph has a rectangular floorplan if and only if it does not contain such cycles of length three. Moreover, a linear time algorithm to obtain such a floorplan has been presented [Sarrafzadeh and Wong, 1996]. The rectangular dual graph approach is a new method for floorplan ning, and many floorplanning problems, such as the sizing problem, have not been tackled yet Rectangular floorplans can be obtained using simulated annealing and genetic algorithms. Both techniques are used to solve general optimization problems for which the solution space is not well understood. The approaches are easy to implement, but the algorithms have many parameters which require empirical adjust ments,and the results are usually unpredictable A final approach to floorplanning, which unfortunately requires substantial computational resources and results to an intractable problem, is to formulate the problem as a mixed-integer linear programming(LP) Consider the following definitions Wi H R, width, height and area of cell C X,Y coordinates of lower left corner of cell Ci he width and height of the final flo A, B, lower and upper bound for the ratio W /H, of cell Ci Pip Qi variables that take o/1 values for each pair of cells C and Ci The goal is to find X, Y;, W; and H, for each cell so that all constraints are satisfied and XY is minimized The latter is a nonlinear constraint. However, we can fix the width w and minimize the height of the floorplan c 2000 by CRC Press LLC
© 2000 by CRC Press LLC Let us assume that the floorplan does not contain cross junctions. Figure 25.13 shows a cross junction. This restriction does not significantly increase the area of a floorplan because, as Fig. 25.13 shows, a cross junction can be replaced by two T-junctions by simply adding a short edge e. It has been shown that in the absence of cross junctions the dual graph is planar triangulated (PT), and every T-junction corresponds to a triangulated face of the dual PT graph. Unfortunately, not all PT graphs have a rectangular floorplan. For example, in the graph of Fig. 25.14 we cannot satisfy the adjacency requirements of edges (a,b), (b,c) and (c,a) at the same time. Note that the later edges form a cycle of length three that is not a face. It has been shown that a PT graph has a rectangular floorplan if and only if it does not contain such cycles of length three. Moreover, a linear time algorithm to obtain such a floorplan has been presented [Sarrafzadeh and Wong, 1996]. The rectangular dual graph approach is a new method for floorplanning, and many floorplanning problems, such as the sizing problem, have not been tackled yet. Rectangular floorplans can be obtained using simulated annealing and genetic algorithms. Both techniques are used to solve general optimization problems for which the solution space is not well understood. The approaches are easy to implement, but the algorithms have many parameters which require empirical adjustments, and the results are usually unpredictable. A final approach to floorplanning, which unfortunately requires substantial computational resources and results to an intractable problem, is to formulate the problem as a mixed-integer linear programming (LP). Consider the following definitions: Wi ,Hi ,Ri : width, height and area of cell Ci Xi ,Yi : coordinates of lower left corner of cell Ci X,Y : the width and height of the final floorplan Ai ,Bi : lower and upper bound for the ratio Wi /Hi of cell Ci Pij, Qij : variables that take 0/1 values for each pair of cells Ci and Cj The goal is to find Xi ,Yi ,Wi , and Hi for each cell so that all constraints are satisfied and XY is minimized. The latter is a nonlinear constraint. However, we can fix the width W and minimize the height of the floorplan as follows: FIGURE 25.12 A rectangular floorplan and its associated dual planer graph. FIGURE 25.13 A cross junction can be replaced by 2 T-junctions. FIGURE 25.14 For a cycle of size 3 that is not a face we cannot satisfy all constraints