Simple framework for physical chip design (place & route) based on KLayout.
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

367 lines
13 KiB

# Copyright (c) 2020-2021 Thomas Kramer.
# This file is part of klayout-pnr
# (see
# This program is free software: you can redistribute it and/or modify
# it under the terms of the GNU Affero General Public License as
# published by the Free Software Foundation, either version 3 of the
# License, or (at your option) any later version.
# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# GNU Affero General Public License for more details.
# You should have received a copy of the GNU Affero General Public License
# along with this program. If not, see <>.
from liberty.parser import parse_liberty
from typing import Dict, List, Tuple
from .placer.quadratic_placer import QuadraticPlacer
from .placer.quadratic_placer_with_density_penalty import QuadraticDensityPlacer
from .legalizer.tetris import TetrisLegalizer
from .legalizer.annealing_legalizer import AnnealingLegalizer
from .router.stupid_router import *
from .router.stupid_gridless_router import *
from .router.airwire_router import AirwireRouter
from .netlist.verilog_reader import VerilogNetlistReader
from .netlist.liberty_reader import LibertyNetlistReader
from .test_data import *
from .netlist import util as net_util
from .layout import pin_detection
from .layout import polygon_label
import math
import itertools
import collections
import os
import sys
import logging
import numpy as np
logger = logging.getLogger(__name__)
handler = logging.StreamHandler(sys.stdout)
handler.setFormatter(logging.Formatter(fmt='%(module)s %(levelname)s\t%(message)s'))
def create_dummy_pins(netlist: db.Netlist, circuit: db.Circuit, core_area: db.DSimplePolygon) -> Tuple[
db.Circuit, Dict[int, Tuple[int, int]]]:
Create dummy pin instances and locations that are distributed evenly around the `core_area`.
:param netlist:
:param circuit:
:param core_area:
:return: Tuple[new top level circuit, positions of dummy pins Dict[sub circuit id, (x,y)]]
# Create dummy circuit for pads.
dummy_pad = db.Circuit() = 'dummy_pad'
new_top = db.Circuit() = 'DUMMY_TOP'
inst = new_top.create_subcircuit(circuit, 'i_{}'.format(
port_nodes = []
# Create virtual modules
for p in circuit.each_pin():
assert isinstance(p, db.Pin)
pad_inst: db.SubCircuit = new_top.create_subcircuit(dummy_pad, 'i_dummy_pad_{}'.format(
# net = circuit.net_for_pin(p)
net = new_top.create_net(
pad_inst.connect_pin(dummy_pad.pin_by_name('IO'), net)
inst.connect_pin(p, net)
top_pin = new_top.create_pin(
new_top.connect_pin(top_pin, net)
pad_ring_box = core_area.bbox()
# Create dummy node positions for ports.
node_positions = dict()
for i, n in enumerate(port_nodes):
# Distribute them on the edge of a unit square.
p = (pad_ring_box.width() + pad_ring_box.height()) * 2 * i / len(port_nodes)
w = pad_ring_box.width()
h = pad_ring_box.height()
if p < w:
x, y = p, pad_ring_box.p1.y
elif p < w + h:
x, y = pad_ring_box.p2.x, p - h
elif p < w + h + w:
x, y = pad_ring_box.p2.x - (p - w - h), pad_ring_box.p2.y
x, y = pad_ring_box.p1.x, pad_ring_box.p2.y - (p - w - h - w)
node_positions[n] = (x, y)
return new_top, node_positions
def test_simple_flow():
1) Read a verilog netlist and a liberty library.
2) Convert the netlist into a networkx.MultiGraph structure.
3) Feed the MultiGraph to the QuadraticPlacer
4) Plot the result.
library = parse_liberty(get_example_liberty_library())
liberty_reader = LibertyNetlistReader()
leaf_cells = liberty_reader.read_liberty(library)
# Read LEF library (using klayout).
# lefdef_config = db.LEFDEFReaderConfiguration(
# )
# load_options = db.LoadLayoutOptions()
# load_options.lefdef_config = lefdef_config
lef_library = db.Layout()
lef_file = get_path('gscl45nm.lef')'Read LEF: {}'.format(lef_file))
klayout_verilog_reader = VerilogNetlistReader(leaf_circuits=leaf_cells)
klayout_netlist = klayout_verilog_reader.read_netlist(get_example_verilog_netlist(file_name='seq_chip_nl.v'))
# klayout_netlist = klayout_verilog_reader.read_netlist(get_example_verilog_netlist(file_name='my_chip_45_nl.v'))
top_circuit: db.Circuit = next(klayout_netlist.each_circuit_top_down())"Top circuit: {}".format(
# Define area to place the cells within.
core_area = db.SimplePolygon(db.Box(db.Point(0, 0), db.Point(12000, 12000))).to_dtype(1)
# Create a new top_circuit with dummy pad instances at dummy positions.
top_circuit, fixed_positions = create_dummy_pins(klayout_netlist, top_circuit, core_area)
# Print number of subcircuit instances in the flat netlist. This includes standar-cells, pads, macros, ...
num_cells = len(list(top_circuit.each_subcircuit()))'Number of cell instances: {}'.format(num_cells))
# Find layer number of the 'OUTLINE' layer which is used as the abutment box of the cells.
l_outline = lef_library.find_layer('OUTLINE')
# Get abutment boxes for all cells.
cell_outlines = { cell.bbox_per_layer(l_outline) for cell in lef_library.each_cell()
cell_area = {
name: cell.area() for name, cell in cell_outlines.items()
# Get cell shapes with dummy height.
cell_shapes = {
name: (bbox.width(), bbox.height()) for name, bbox in cell_outlines.items()
# === PLACEMENT ==='Start global placement.')
# placer = QuadraticPlacer()
placer = QuadraticDensityPlacer(density_penalty=20000)
cell_transf =,
fixed_circuits={n for n in fixed_positions})
layout = db.Layout()
# Populate layout library.
# Find all GDS file in the search path and add their content cells to the layout.
gds_paths = ['../test_data/lib/gds']'Read GDS files from : {}'.format(gds_paths))
load_options = db.LoadLayoutOptions()
load_options.create_other_layers = True
for path in gds_paths:
if not os.path.isabs(path):
path = os.path.join(os.path.dirname(__file__), path)
dir_content = os.listdir(path)
for f in dir_content:
f = os.path.join(path, f)
if os.path.isfile(f) and f.lower().endswith('.gds'):
# logger.debug('Read GDS: {}'.format(f)), load_options)'Number of cells in layout: {}'.format(layout.cells()))
assert layout.cells() > 1, "No cells loaded."
l_metal1_pin = layout.find_layer(21, 0)
l_metal1_label = layout.find_layer(21, 1)
# Find pin shapes of the cells.
cell_pin_shapes = dict()
for cell in layout.each_cell():
cell_pin_shapes[] = pin_detection.find_pins_from_text_labels(cell, l_metal1_pin, l_metal1_label)
# Check that cell heights are unique.
cell_heights = {cell_shapes[][1] for cell in layout.each_cell()}
assert len(cell_heights) == 1, "Cell heights are not all the same: {}".format(cell_heights)
row_height = cell_heights.pop()
cell_widths = {cell_shapes[][0] for cell in layout.each_cell()}
x_grid_pitch = cell_widths.pop()
for w in cell_widths:
x_grid_pitch = math.gcd(x_grid_pitch, w)"Detected x-grid pitch for placement: {}".format(x_grid_pitch))
assert x_grid_pitch > 1, "Cells don't have a width that is a integer multiple of a number larger than 1."
# === LEGALIZATION ==='Start legalization.')
legalizer = TetrisLegalizer(row_height=row_height, x_grid_pitch=x_grid_pitch)
# Convert global placement result into legal placements.
cell_transf = legalizer.legalize(
# Create a lookup table: {subcircuit: geometric transformation, ...}
transf_by_subcircuit = {
top_circuit.subcircuit_by_id(k): v for k, v in cell_transf.items()
# === DRAW LAYOUT without routes ==='Draw layout without routes.')
# Create top level cell.
top_cell: db.Cell = layout.create_cell('TOP')
# Order cell instances by the IDs of their sub-circuits.
cell_instances_by_subcircuit_id = dict()
for sc, trans in transf_by_subcircuit.items():
cell_name = sc.circuit_ref().name
cell = layout.cell_by_name(cell_name)
cell_inst = db.CellInstArray(cell, trans)
cell_inst = top_cell.insert(cell_inst)
# Store subcircuit ID with the cell instance.
cell_instances_by_subcircuit_id[] = cell_inst
except RuntimeError as err:
logger.warning('Cell not found: {}'.format(cell_name))
# (debug) Sketch core area.
core_area_layer = layout.layer(db.LayerInfo(123, 0, 'core_area'))
# === PREPARE for routing ===
# Draw layout of routing terminals, i.e. pin shapes of cells and macros.
# Create flat structure of routing terminals.
# Plot pin shapes and net names.
routing_terminal_layer = layout.layer(db.LayerInfo(21, 0, 'routing_terminal'))
routing_terminal_cell = layout.create_cell("routing_terminals")
top_cell.insert(db.CellInstArray(routing_terminal_cell.cell_index(), db.Trans(0, 0)))
pin_shapes_by_net = collections.defaultdict(set)
terminal_ids = itertools.count(1)
for net in top_circuit.each_net():
assert isinstance(net, db.Net)
net_pins = net.each_subcircuit_pin()
for p in net_pins:
subcircuit_id = p.subcircuit().id()
if subcircuit_id not in cell_instances_by_subcircuit_id:
logger.warning('No cell instance for subcircuit {}'.format(p.subcircuit().name))
cell_inst = cell_instances_by_subcircuit_id[subcircuit_id]
assert isinstance(cell_inst, db.Instance)
assert cell_inst.is_valid()
cell = cell_inst.cell
cell_name =
transf = cell_inst.trans
# Get the name of the pin.
pin_name =
# Get the associated pin shapes.
pin_shapes = cell_pin_shapes[cell_name][pin_name]
# Move the pin shapes to the location of the cell.
placed_pin_shapes = db.Shapes()
# Insert shapes and plot net names.
for s in placed_pin_shapes.each():
s = routing_terminal_cell.shapes(routing_terminal_layer).insert(s)
label_text =
s.set_property('terminal_id', next(terminal_ids))
text_position = polygon_label.find_polygon_label_position(s.polygon, label_text)
routing_terminal_cell.shapes(routing_terminal_layer).insert(db.Text(label_text, text_position))
# === Sketch pin connections ===
layout.layer(db.LayerInfo(123, 1, 'air_wires'))
airwire_router = AirwireRouter(airwire_layer=(123, 1))
# === ROUTE ===
def layer(number, purpose):
return layout.layer(db.LayerInfo(number, purpose))
router_config = RouterConfig()
router_config.routing_layers = {
layer(21, 0): 'hv',
layer(23, 0): 'v',
layer(25, 0): 'h'
# router = StupidRouter(router_config)
router = StupidGridlessRouter(router_config)
# === STREAM OUT ===
# Write full layout to file.
gds_out = '/tmp/test.gds''Write GDS: {}'.format(gds_out))
oasis_out = '/tmp/test.oas''Write OASIS: {}'.format(oasis_out))