CSE144 - Project Homework #3
Due: Nov 26th, 1:00 PM

In this assignment, you are asked to implement a constrained left-edge channel routing algorithm for a standard-cell based design. The layout of the chip includes only two rows as in the second project. The order of the cells in each row is determined by using the simulated annealing algorithm developed in the second project. Those of you who could not complete the second assignment should use an already placed version of the circuit provided. However, you are urged to use the placement generated by your own algorithm.

Algorithm Details and Input/Output Specification

Since you are going to be using the results attained through the program developed in your previous assignments, the input specification of your program is exactly the same as the previous assignments. However, considering the long running times of the programs developed in the second project, you have to store the results of placement in a separate file. To achieve this you need to update the placement program. The specification of the intermediate file format is given in the following specifications.

A walk-through example:

The table below gives the results from the first and second projects run on the circuit given in the first column.

Because of the long running time of the placement algorithm (the second project), you have to save the placement result in a file with the following structure.

Partition 0: 3 5 0
Partition 1: 2 1 4

Then after read in the partition and placement results you should implement a channel router, using the results from the first two projects.

Parsing the connectivity matrix (from the first column in the above table), you will find out that there are exactly 6 wires in this circuit (the format of this matrix is explained in the first project assignment). These wires together with their corresponding cells and port numbers are as follows.

Wire (first cell, second cell), Ports(port number of the first cell, port number of the second cell)
Wire 1: (3,0), Ports(2,1)
Wire 2: (3,2), Ports(3,1)
Wire 3: (4,1), Ports(3,1)
Wire 4: (4,2), Ports(2,1)
Wire 5: (5,3), Ports(2,1)
Wire 6: (5,4), Ports(3,1)

However, there are 5 nets in the circuits. Therefore, you will first need to find the nets and their positions. The following observations for this example may be illustrative. Wire 2 and Wire 4 are parts of the same net. Wire 2 connects  port 3 of cell 3 to port 1 of cell 2, and Wire 4 connects port 2 of cell 4 to port 1 of cell 2. Therefore, they are on the same net.

You will need possibly to use a data structure in which every net is represented as a set of all its pins plus the leftmost and rightmost position of the net. The following structure is an illustrative data structure for this. It represents the nets in the given circuit. The pin positions follow the assumption from the second project - the pins are placed on every third position inside the cell. For this example the position of port 1 of cell 0 is 23, because cell 0 is the third cell on partition 0 and the size of cells 3 and 5 is 10 (10+10+3=23).

Net (pin position1, partition), (pin position2, partition), ... [Leftmost position of the net, rightmost position of the net]
Net 1: (6,0) (23,0) [6,23]
Net 2: (9,0) (3,1) (26,1) [3,26]
Net 3: (29,1) (13,1) [13,29]
Net 4: (16,0) (3,0) [3,16]
Net 5: (19,0) (23,1) [19,23]

The following shows the positions of the ports, corresponding to the above nets.
00400100200000040050001000000
00200000000030000000005002003

Using the information attained so far, you are asked to implement the constrained left-edge algorithm. Here is what you have to do initially.

• Sort the nets in ascending order of their starting positions..

  Net (pin position1, partition), (pin position2, partition), ... [Leftmost position of the net, rightmost position of the net]
  Net 2: (9,0) (3,1) (26,1) [3,26]
  Net 4: (16,0) (3,0) [3,16]
  Net 1: (6,0) (23,0) [6,23]
  Net 3: (29,1) (13,1) [13,29]
  Net 5: (19,0) (23,1) [19,23]

• Construct HCG and VCG.

• Find the successors of each net in VCG. The successor information can be inserted in the data structure, as shown below.

  Net (pin position1, partition), (pin position2, partition), ... [Leftmost position of the net, rightmost position of the net] {successors}
  Net 2: (9,0) (3,1) (26,1) [3,26] { }
  Net 4: (16,0) (3,0) [3,16] { 2 }
  Net 1: (6,0) (23,0) [6,23] { 5 }
  Net 3: (29,1) (13,1) [13,29] { }
  Net 5: (19,0) (23,1) [19,23] { }

• When you construct your VC graph, you should search for possible loops in the vertical constraint graph. You program should be able to detect and eliminate any loops that exist in the VC graph. The easiest (and suggested) way of eliminating the loop(s) is to switch any one of the cells contiributing to the loop(s) with one of its neighbours until no loops remain in the VC graph. If the VCG of the initial placement contains any loops, the loop free placement should be included in the outputs.
• Now apply the constrained left-edge algorithm.

Output Specification:
Your program should first output the partitions. The list of the nets together with their port positions, starting and end position of the net, successors, and  the track number should be output. More formally the format of the file is:

Net i : (PinPosition1, PinPosition2,...) [LeftmostPosition, RightmostPosition] {VCG successors} TrackNumber

---- Output starts here ----
Partition 0: 3 5 0
Partition 1: 2 1 4

Net 1: (6, 23) [6,23] { 5 } 3
Net 2: (9, 3, 26) [3,26] { } 1
Net 3: (29, 13) [13,29] { } 4
Net 4: (16, 3) [3,16] { 2 } 2
Net 5: (19, 23) [19,23] { } 2
---- Output ends here ----
 

The above results correspond to the following visual representation of the routed channel.
0123456789012345678901234567890
--4--1--2------4--5---1-------
             -----------------
      ------------------
   --------------  -----
   ------------------------
--2---------3---------5--2--3-
 

The placement results for the examples from the second project:
circuit1
circuit2