JLE: JAVA LAYOUT EDITOR
Place and Route Layout Editor for Integrated Circuits
Virtuoso* Layout Editor from Cadence
JLE, Version 0.1
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
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
The graphical user interface will enable the user to do the following things:
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.
NAME NET NET MODEL
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.
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.
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.
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.
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
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: