Place and Route Layout Editor for Integrated Circuits


Virtuoso* Layout Editor from Cadence


JLE, Version 0.1



I. Introduction




II. Definition:

Graphical User Interface: GUI

Circuit Netlist Format.

Design Rules Format:

Layout Editing, Place and Route:

III. UML Model for Layout Program

IV. STATE DIAGRAM for Layout Program




I. Introduction


                Integrated Circuit design is a complicated process where circuits are designed and fabricated.  The Design Flow typically consists of many stages, but can be generally divided into ‘front-end’ and back-end stages.  The front-end stage has the circuit designed in a schematic editor as an abstract model and simulated.  The schematic simulation assumes that the device’s models represent the physical behavior of devices in silicon, and that interconnect between the devices will not change significantly the behavior of the circuit.  The back-end stage is the ‘physical’ design of the circuit.  A ‘Layout Designer’ typically has the job of creating a physical layout from the schematic according to devices and nets in the schematic, and according to a large set of ‘Design Rules’.  The layout designer attempts to create and place all the devices from the schematic into the layout such way that area is minimized, and various other thermal and device matching requirements are satisfied.  The devices, after being placed, are connected together with metal routing paths and sometimes polysilicon.  When all the devices are placed and routed, a Design Rule Check (DRC) is run to check if lines are not too close or too narrow.  This is done because when the chip is fabricated, various stages of masking, etching, diffusion and implantation create variations in the final widths of layers.



                This project will develop a tool for implementing the physical layout stage of the design flow.  It will require a reading of a schematic netlist, creation of devices from that netlist, placement of the devices into the layout, several strategies for routing devices together, a Design Rule and Layout Versus Schematic checker, and a post-layout evaluator to determine the efficiency of the P&R.



                There are various commercial tools with many of the capabilities described in this project, but none of them have all desired capabilities.  For example, Cadence’s Virtuoso layout program has a basic editor, and exports the layout and connectivity to a tool called Virtuoso Custom Router.  The router is fairly good, but has many problems that keep it from becoming liked by Layout Designers.  This project will create a tool that has both combined, will be based on object-oriented programming, and thus will be much more adaptable to real Layout needs.

                Another layout tool on the market it MyCad’s MyChip layout tool.  This tool is used at Pima Community College for the IC-CAD certification program.  It is a very good tool, but a full license costs at least $5000.  Otherwise, you can only have 500 objects in your layout.  It does not have a router built-in.  It also cannot be modified to fix various problems or read different types of netlists.

                There are other layout tools out there, but an internet search seems to indicate that none of them have been written in Java, so this is an original project.




                The process of Layout Place and Route is very much like the maze problem where each pair of terminals that must be connected with each other have to find a path through the maze of already placed devices and routed nets without shorting other nets or creating DRC violations.  Also, like the Uno game, there are many strategies for actually placing and routing devices, and there are many rules controlling the process.  One of the possible strategies will be ‘Manual’, which will allow a human ‘player’ to attempt to create an optimal layout.  Another strategy will be a simple ‘Greedy’ routing algorithm which does a messy job, but does it fast. This greedy algorithm is like a semi-random wall-hugger rat in the maze paradigm. A third strategy will try to use a recursive back-tracking algorithm.  It will create a set of possible routes for each net-pair, and then pick one.



II. Definition:


Graphical User Interface: GUI


The graphical user interface will enable the user to do the following things:


  • Menu:
    • File:
      • Read Netlist: Loads a circuit netlist
      • Save Route: Saves the results of a place and route
      • Read Route: Loads a previous place and route results file
    • Options:
      • Grid Lines: Turn on/off grid lines
      • Flight Lines: Turn on/off lines between connected terminals
    • Edit:
      • Undo
      • Path
      • Rectangle
      • Delete
      • Move
    • P&R: (Place and Route)
      • Place Devices
      • Route: Fast-Greedy
      • Route:  Combinational
    • Evaluate
      • DRC: Checks for errors of Design Rules
      • LVS:  Check Layout Versus Schematic connectivity.
      • Route Report:  Calculates the area used by the placement, and the total routing length.
  • Toolbar:
    • Undo
    • Path: Draw path
    • Rectangle: Draws a rectangle
    • Delete: Delete an object (path or rectangle)
    • Move: to drag an object (device or path)
  • Layer Select Bar (LSB):
    • Will graphically display all the possible layers
    • The currently selected layer is the one that new graphics are created with, or deleted.
  • Mouse Actions:
    • The left mouse will be used to draw and drag objects, for selecting layers in the LSW, For choosing menu actions and toolbar actions.
  • Keyboard Mnemonics
    • All of the menu and toolbar items will have keyboard mnemonics or shortcuts.
    • Paths may be started by typing P
    • Rectangles: R
    • Move: M
    • Delete: D
  • Drawing Panel
    • The drawing panel will be composed of a grid, where each square represents the minimum object size. It this project, each grid will represent 1 um.
    • The panel will be black with light grey grid lines.


Circuit Netlist Format. 


The circuit netlist reader class will be separated from the gui and layout code.  It will read a simplified netlist.  The netlist form will basically state the devices name, its connecting nets, and the device model.  The netlist will be limited to five basic device types: Capacitors, Resistors, Diodes, N-channel and P-channel MOSFETS.  Sizes of devices will not be included in the netlist.  Each device will have only one size in the layout.  To have multiple devices will require a development of complicated P-cells (Parameterized Cells), which takes a long time.


For example:


C101       N100       N211       P2P1CAP

R1           N211       N212       POLYRES

D2           N100       GND       NPDIODE

M1          VDD       N212       N200       PCH

M2          GND       N212       N200       NCH


                The netlist will be read into the program into an ArrayList.  For each device read, a new device of that type will be created and added to the list.  Each device will have its own class, but they will all be extended from a generic ‘Devices’ super-class.  The generic Devices class will define general things like X,Y position, Width and Height of the rectangle it creates, it’s instance-name and model-name.  The sub-classes will define device-dependent things like net names which correspond to specific terminals, and the X,Y coordinates of those terminals within the device.  Device objects will be created by a Factory Pattern, using a Device_Factory and sub-factories for each device type.  These include a capacitor_factory, resistor_factory, pch_factory, nch_factory.



Design Rules Format:


                The Design Rules state the minimum widths of layers and  minimum spacing between layers.  The design rules will be kept in a ‘Technology File’.  There will be only two rules: minimum widths of paths and minimum spacing.  with the format:


LayerName            RuleType               Value

METAL1               WIDTH                  1.0

METAL2               WIDTH                  1.0

METAL1               SPACE                   1.0

METAL2               SPACE                   1.0


                The Design Rules file will be read automatically at the start of the layout program.  It will always have the filename technology.txt .  A Design_Rules class will manage the rules.  A hash-table will be created to hold the rules.  It will use the combination of LayerName_RuleType as the keys.  The class will have methods to get and put rule names.  The technology file will specify also the order of layers and their names.  A typical 2 metal CMOS process can have: metal2, via, metal1, contact,  poly, n-diffusion, p-diffusion, nwell and psub.  In this version, psub ( the substrate) will not be considered.


Layout Editing, Place and Route:


                In the program, the following ‘Design Flow’ must be followed.  The design flow is described more in the State Diagram.


1.        Read a circuit netlist

2.        Place the devices into the Layout Panel.

3.        Route devices together.

4.        Verify the design: DRC

5.        Verify the design: LVS

6.        Evaluate the Place and Route efficiency by area and total routing length

7.        Save the Layout


The first step, reading the netlist, is described above.


The second step, placement, will simply iterate through the ArrayList of devices and put them into the layout with minimum spacings.  It will try to place all the devices into a square region.  It will start putting devices in the upper-left corner, and continue across the screen in  rows.  Each row will have sqrt(n) devices, where n is the number of devices.  The user will be able to select and move devices after initial placement.  The user will be able to see which devices connect to which by turning on the flightlines. 


The third step, routing, has three options: Manual, Greedy, and Combinational.  

In Manual Routing mode,  the user have to connect all devices using metal routing layers by hand.  While routing devices, a user must follow the Design-Rules, but there may be errors in the process.


The Greedy routing strategy will run an automatic routing.  This routing will be simple: it  randomly sorts the net-pairs that must be connected, and simply selects the shortest path between the two terminals for each routing. When a pair of terminals cannot be connected, it moves that pair of terminals up in the list a random distance, deletes all routes below its new position in the list, and tries the routing again.  It will continue this process until all nets are successfully routed.


The Combinational routing algorithm improve the Greedy algorithm by using a recursive-backtracking algorithm to search the tree of possible routes.  First it will sort the nets by distance between the two connecting terminals, in increasing order.  This way, closer devices is routed first.  Then, for each net, it will several (n) possible routes.  If it will not be able find a path, it must back-track up the recursion tree.  If it can find a path, it must also remember the paths that it already tried in order to make sure that they are not re-tried.


Fourth and Fifth, the design placement and routing must be DRC and LVS clean.  In the auto-routing mode, this should be already the case.  But, a DRC and LVS must be run anyway because my experience is that they do not always work well.  The DRC process will require an algorithm which looks at each square and its nearby squares to make sure no rules are violated.  The LVS part will look at each net in  layout and trace it to make sure it is only connected to terminals it should be.


Sixth Stage: Layout P&R evaluation.  The placement is scored according to a measurement of the total area of the rectangle where all the devices lie inside.  This is done by looping through all the devices and picking the biggest and smallest X and Y coordinates.  The routing score is done by looping through all of the path objects and summing their lengths.  There will be also a ‘Time’ score which tracks how much time it takes to complete the P&R from beginning to end. These scores will be used to compare different P&R’s.  These will be used to determine ‘who’ wins.  A slower P&R cost the company more in terms of computer and employee time, and lost market-share.  Actually, a market share is much much bigger, sometimes equal to millions per week.  The device area is important because smaller area means more die per wafer, and smaller products like cell-phones and PDA’s.  The smaller routing is important because a shorter line between two terminals allows a faster signal transfer, and define how fast the device can run.


Seventh Stage: Save the Layout. This will just write the state of the layout routing to a file as a serializable object.




                This project will follow all of the requirements specified for other term projects, which may include a multi-view GUI, multiple strategies for ‘winning’,  all the ‘features’ such as saving a layout in progress, loading a save layout, UML diagrams and Javadoc.  The same project timeline and deliverables will apply.  The same style and design guidelines will be followed.




                The most important part of this project will be a defining the architecture for devices, nets, and layout.  The architecture is defined in the Conceptual Model     




                There will be several algorithms to implement the layout tool and routers. These include the netlist reading and device generation, the Nets class generation which determines all the devices that each net connects to, the devices placement algorithm, the Greedy and Combinational routing algorithms, the DRC, LVS, and Layout Save-State and Read-Saved-State algorithms.  These algorithms have been described above, and will be described in more detail in the next version of this report if needed.


III. UML Model for Layout Program




This project has the following architecture details.   (Above, the diamond arrow means that class is contained by the pointing class).


Layout_GUI : This class contain the main() statement and builds the frame.  It contains the following inner classes:

                Layout_Frame:  The frame for the GUI.

                                Layout_Panel:  The drawing panel, where layers will be shown

Observer:  This class will have an observer to listen the model.

                                MouseListener:  Listens for mouse events

                                ActionListener:  Listens for toolbar and menu evens

                                KeyboardListener:  Listens for mnemonic events



Layout_Model: Extends Observerable.  The model maintains data structures and performs all the actions for the GUI.



Devices and Device_Factory:  These classes are used to build new devices.

Class Devices:  The devices will be defined by a general class which may contain things that all devices have, like X, Y coordinate, Width, Height.

Class  Device_Cap, Device_Res etc:  Each device type will have a class which extends Devices.  This class can define device specific details such as the terminals.  For example, a capacitor has two terminals while MOSFETs have three: source, gate and drain.

                Class Device_Factory: A super class for the specific device factory classes.

                Class Factory_Cap, etc.  A class that is used to generate a specific device.

Class Devices_List:  An ArrayList or LinkedList to manage all devices.  There will be one instance of Devices_list called All_Devices which contain pointers to all devices.



                Class Net_List: Each net may be connected with many devices, so we  need to have a collection which contains all of the nets.  The Net_List class may be a Hash Table where the key will be a net name.  The object associated with each key will be a Devices_List which contains pointers to all the Devices which connect to the net name represented by the key.

                Class Net:  Each net will have the object which contains a pointer to its Devices_List, and a pointer to its NetPaths_List.

                Class NetPaths_List:  This class will have an ArrayList of all the NetPath’s needed to connect all the devices for each net.  That is, a net may connect to many devices, but a NetPath can only be a path which connects two points.  To connect three or more terminals will require more NetPaths.

Class NetPath: This class will represent a particular path, which will be a list of visited coordinates.  The coordinates may be 3-dimensional (X, Y, Z), where Z represents which layer the point is on.  For example, Z=0 will represent M2, Z=1 will represent M1.  This method makes it easy to represent a path which travels between various layers.


                Class Layout_Grid_List:  This class will represent the placement of devices and paths in the layout.  Since a layout consists of many possible layers  and each grid square can contain any combination of these layers, it makes sense to have a different 2D array for each layer, called a Layer_Grid.  Thus, for a technology that has the above 2 layers, we would need 2 2D Layer_Grid arrays to keep track of whether that element (metal1 or metal2) appears at any particular x,y coordinate.  These arrays will be used by a repaint method to draw the layout in the layout panel.  They will be used also by the DRC method to check for layer spacing violations.  Furthermore, they will be used by the auto-routing methods to determine the paths for routes.


                The remaining classes (Technology, Netlist_File, Auto_Router, DRC, LVS, Eval) do specific things which are self-explanatory, and will be described in the documentation further.


IV. STATE DIAGRAM for Layout Program



            The state-machine above is centered on the GUI, since it always returns to an idle state which is the GUI.

            All the others states are traversed to by some mouse/menu/keyboard action.

            The normal flow would be as follows: 1. Load Netlist, 2. Device Placement, 3. Manual or Auto Route,

            4. Run DRC, 5. Run LVS, 6. Run Layout Evaluator,  7. Save Layout.

            The user can, of course, go from any state to any other state. For example, a layout route and DRC may

            be repeated many times until a correct route is obtained.




Browse code here:


















                Layout Model




                Route Strategies