Algorithms for VLSI Design Automation

Programming Project (two persons): Transistor-Chain Construction for CMOS Cell Compilation

Summary: Cell compilation is the process of translating a netlist of transistors into layout. This project deals with CMOS transistor circuits obeying a layout in which pairs of nMOS and pMOS transistors with the same gate signal are located under the same polysilicon strip. Chains of these pairs can be formed by merging the diffusion areas of the transistors. The optimal solution merges the maximal number of diffusion areas and leads in this way to the narrowest cell width. Many algorithms for this problem have been proposed in the literature. This project considers one of them.

Detailed Description

Study the following articles:

Wimer, S., R.Y. Pinter and J. Feldman, "Optimal Chaining of CMOS Transistors in a Functional Cell", IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. CAD-6(5), pp 795-801, (September 1987).

Bron, C. and J. Kerbosch, "Algorithm 457: Finding All Cliques of an Undirected Graph", Communications of the ACM, Vol. 16(9), pp 575-577, (September 1973).

The most important issues in the first paper are: the construction of the set of all possible subchains followed by the selection of a subset from this set in which all transistors occur exactly once and that contains the minimal number of chains. The second article is used for solving the latter problem.
In order to simplify the programming you may (but do not need to) assume the following:

The netlist of transistors consists of a single complex CMOS gate; it consists of two series-parallel networks that are each other's dual.
Input signals only occur once which means that the pairing of nMOS and pMOS transistor is unique.
The series-parallel networks have a maximal height and width of 4. So each network contains at most 16 transistors and the entire cell at most 32.
The input can be considered correct and does not need to be verified.

The description of the CMOS complex gate network should be read from a text file with the following structure:
- The first line gives the number of transistors in the network.
- The second line gives the number of nets in the network.
- Each following line describes a single transistor by means of three items. The first two are numbers corresponding to the nets to which the transistor's source and drain are connected. The third is a string that represents the signal connected to the transistor's gate.
- The following convention should be observed for the net numbers: number 0 is reserved for the negative supply voltage (Vss), number 1 for the positive supply voltage (Vdd) and number 2 for the output of the complex gate.
- Here is an example of a NAND gate:
```
   +------+ Vdd (1)
   |      |
A ++   B ++
-o|    -o|
  ++     ++
   |      |
   +--+---+ out (2)
      |
     ++
  A -|
     ++
      | (3)
     ++
  B -|
     ++
      |
   +--+---+ Vss (0)
      
```
  The file describing this network looks like:
```
4
4
1 2 A
2 1 B
2 3 A
0 3 B
```
The program's output is simply the list of subchains that forms the optimal solution. The transistor pairs are given from left to right and a separation between chains of transistors is indicated in a suitable way.
You should test your program for a number of netlists and include the results in your report.
An optional extension of the project computes the metal wires that are necessary to complete the layout and minimizes the number of tracks of metail wires by means of the left-edge algorithm (which is presented in the book).

Last update on: Wed Mar 17 23:15:20 MET 1999by Sabih Gerez.