- Study the following articles:
- 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).

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).