Netlist

Overview

The netlist logically consists of several different components: Blocks, Ports, Pins and Nets Each component in the netlist has a unique template identifier (BlockId, PortId, PinId, NetId) used to retrieve information about it. In this implementation these ID’s are unique throughout the netlist (i.e. every port in the netlist has a unique ID, even if the ports share a common type).

Block

A Block is the primitive netlist element (a node in the netlist hyper-graph). Blocks have various attributes (a name, a type etc.) and are associated with sets of input/output/clock ports.

Block related information can be retrieved using the block_*() member functions.

Pins

Pins define single-bit connections between a block and a net.

Pin related information can be retrieved using the pin_*() member functions.

Nets

Nets represent the connections between blocks (the edges of the netlist hyper-graph). Each net has a single driver pin, and a set of sink pins.

Net related information can be retrieved using the net_*() member functions.

Ports

A Port is a (potentially multi-bit) group of pins.

For example, the two operands and output of an N-bit adder would logically be grouped as three ports. Ports have a specified bit-width which defines how many pins form the port.

Port related information can be retrieved using the port_*() member functions.

Usage

The following provides usage examples for common use-cases.

Walking the netlist

To iterate over the whole netlist use the blocks() and/or nets() member functions: 

 Netlist netlist;

 //... initialize the netlist

 //Iterate over all the blocks
 for(BlockId blk_id : netlist.blocks()) {
     //Do something with each block
 }


 //Iterate over all the nets
 for(NetId net_id : netlist.nets()) {
     //Do something with each net
 }

To retrieve information about a netlist component call one of the associated member functions: 

 //Print out each block's name
 for(BlockId blk_id : netlist.blocks()) {

     //Get the block name
     const std::string& block_name = netlist.block_name(blk_id);

     //Print it
     printf("Block: %s\n", block_name.c_str());
 }

Note that the member functions are associated with the type of component (e.g. block_name() yields the name of a block, net_name() yields the name of a net).

Tracing cross-references

It is common to need to trace the netlist connectivity. The Netlist allows this to be done efficiently by maintaining cross-references between the various netlist components.

The following diagram shows the main methods and relationships between netlist components: 

           +---------+      pin_block()
           |         |<--------------------------+
           |  Block  |                           |
           |         |-----------------------+   |
           +---------+      block_pins()     |   |
              |   ^                          v   |
              |   |                       +---------+  net_pins()  +---------+
              |   |                       |         |<-------------|         |
block_ports() |   | port_block()          |   Pin   |              |   Net   |
              |   |                       |         |------------->|         |
              |   |                       +---------+  pin_net()   +---------+
              v   |                          ^   |
           +---------+      port_pins()      |   |
           |         |-----------------------+   |
           |  Port   |                           |
           |         |<--------------------------+
           +---------+      pin_port()

Note that methods which are plurals (e.g. net_pins()) return multiple components.

As an example consider the case where we wish to find all the blocks associated with a particular net: 

 NetId net_id;

 //... Initialize net_id with the net of interest

 //Iterate through each pin on the net to get the associated port
 for(PinId pin_id : netlist.net_pins(net_id)) {

     //Get the port associated with the pin
     PortId port_id = netlist.pin_port(pin_id);

     //Get the block associated with the port
     BlockId blk_id = netlist.port_block(port_id);

     //Print out the block name
     const std::string& block_name = netlist.block_name(blk_id);
     printf("Associated block: %s\n", block_name.c_str());
 }

Netlist also defines some convenience functions for common operations to avoid tracking the intermediate IDs if they are not needed. The following produces the same result as above: 

 NetId net_id;

 //... Initialize net_id with the net of interest

 //Iterate through each pin on the net to get the associated port
 for(PinId pin_id : netlist.net_pins(net_id)) {

     //Get the block associated with the pin (bypassing the port)
     BlockId blk_id = netlist.pin_block(pin_id);

     //Print out the block name
     const std::string& block_name = netlist.block_name(blk_id);
     printf("Associated block: %s\n", block_name.c_str());
 }

As another example, consider the inverse problem of identifying the nets connected as inputs to a particular block: 

 BlkId blk_id;

 //... Initialize blk_id with the block of interest

 //Iterate through the ports
 for(PortId port_id : netlist.block_input_ports(blk_id)) {

     //Iterate through the pins
     for(PinId pin_id : netlist.port_pins(port_id)) {
         //Retrieve the net
         NetId net_id = netlist.pin_net(pin_id);

         //Get its name
         const std::string& net_name = netlist.net_name(net_id);
         printf("Associated net: %s\n", net_name.c_str());
     }
 }

Here we used the block_input_ports() method which returned an iterable range of all the input ports associated with blk_id. We then used the port_pins() method to get iterable ranges of all the pins associated with each port, from which we can find the associated net.

Often port information is not relevant so this can be further simplified by iterating over a block’s pins directly (e.g. by calling one of the block_*_pins() functions): 

 BlkId blk_id;

 //... Initialize blk_id with the block of interest

 //Iterate over the blocks ports directly
 for(PinId pin_id : netlist.block_input_pins(blk_id)) {

     //Retrieve the net
     NetId net_id = netlist.pin_net(pin_id);

     //Get its name
     const std::string& net_name = netlist.net_name(net_id);
     printf("Associated net: %s\n", net_name.c_str());
 }

Note the use of range-based-for loops in the above examples; it could also have written (more verbosely) using a conventional for loop and explicit iterators as follows: 

 BlkId blk_id;

 //... Initialize blk_id with the block of interest

 //Iterate over the blocks ports directly
 auto pins = netlist.block_input_pins(blk_id);
 for(auto pin_iter = pins.begin(); pin_iter != pins.end(); ++pin_iter) {

     //Retrieve the net
     NetId net_id = netlist.pin_net(*pin_iter);

     //Get its name
     const std::string& net_name = netlist.net_name(net_id);
     printf("Associated net: %s\n", net_name.c_str());
 }

Creating the netlist

The netlist can be created by using the create_*() member functions to create individual Blocks/Ports/Pins/Nets.

For instance to create the following netlist (where each block is the same type, and has an input port ‘A’ and output port ‘B’): 

 -----------        net1         -----------
 | block_1 |-------------------->| block_2 |
 -----------          |          -----------
                      |
                      |          -----------
                      ---------->| block_3 |
                                 -----------
We could do the following: 
 const t_model* blk_model = .... //Initialize the block model appropriately

 Netlist netlist("my_netlist"); //Initialize the netlist with name 'my_netlist'

 //Create the first block
 BlockId blk1 = netlist.create_block("block_1", blk_model);

 //Create the first block's output port
 //  Note that the input/output/clock type of the port is determined
 //  automatically from the block model
 PortId blk1_out = netlist.create_port(blk1, "B");

 //Create the net
 NetId net1 = netlist.create_net("net1");

 //Associate the net with blk1
 netlist.create_pin(blk1_out, 0, net1, PinType::DRIVER);

 //Create block 2 and hook it up to net1
 BlockId blk2 = netlist.create_block("block_2", blk_model);
 PortId blk2_in = netlist.create_port(blk2, "A");
 netlist.create_pin(blk2_in, 0, net1, PinType::SINK);

 //Create block 3 and hook it up to net1
 BlockId blk3 = netlist.create_block("block_3", blk_model);
 PortId blk3_in = netlist.create_port(blk3, "A");
 netlist.create_pin(blk3_in, 0, net1, PinType::SINK);

Modifying the netlist

The netlist can also be modified by using the remove_*() member functions. If we wanted to remove block_3 from the netlist creation example above we could do the following: 

 //Mark blk3 and any references to it invalid
 netlist.remove_block(blk3);

 //Compress the netlist to actually remove the data associated with blk3
 // NOTE: This will invalidate all client held IDs (e.g. blk1, blk1_out, net1, blk2, blk2_in)
 netlist.compress();

The resulting netlist connectivity now looks like: 

 -----------        net1         -----------
 | block_1 |-------------------->| block_2 |
 -----------                     -----------

Note that until compress() is called any ‘removed’ elements will have invalid IDs (e.g. BlockId::INVALID()). As a result after calling remove_block() (which invalidates blk3) we then called compress() to remove the invalid IDs.

Also note that compress() is relatively slow. As a result avoid calling compress() after every call to a remove_*() function, and instead batch up calls to remove_*() and call compress() only after a set of modifications have been applied.

Verifying the netlist

Particularly after construction and/or modification it is a good idea to check that the netlist is in a valid and consistent state. This can be done with the verify() member function: 

 netlist.verify()

If the netlist is not valid verify() will throw an exception, otherwise it returns true.

Invariants

The Netlist maintains stronger invariants if the netlist is in compressed form.

is compressed (‘not dirty’)

If the netlist is compressed (i.e. !is_dirty(), meaning there have been NO calls to remove_*() since the last call to compress()) the following invariant will hold:

  • Any range returned will contain only valid IDs

In practise this means the following conditions hold:

  • Blocks will not contain empty ports/pins (e.g. ports with no pin/net connections)

  • Ports will not contain pins with no associated net

  • Nets will not contain invalid sink pins

This means that no error checking for invalid IDs is needed if simply iterating through netlist (see below for some exceptions).

NOTE: you may still encounter invalid IDs in the following cases:

  • net_driver() will return an invalid ID if the net is undriven

  • port_pin()/port_net() will return an invalid ID if the bit index corresponds to an unconnected pin

is NOT compressed (‘dirty’)

If the netlist is not compressed (i.e. is_dirty(), meaning there have been calls to remove_*() with no subsequent calls to compress()) then the invariant above does not hold.

Any range may return invalid IDs. In practise this means,

  • Blocks may contain invalid ports/pins

  • Ports may contain invalid pins

  • Pins may not have a valid associated net

  • Nets may contain invalid sink pins

Implementation Details

The netlist is stored in Struct-of-Arrays format rather than the more conventional Array-of-Structs. This improves cache locality by keeping component attributes of the same type in contiguous memory. This prevents unneeded member data from being pulled into the cache (since most code accesses only a few attributes at a time this tends to be more efficient).

Clients of this class pass nearly-opaque IDs (BlockId, PortId, PinId, NetId, StringId) to retrieve information. The ID is internally converted to an index to retrieve the required value from it’s associated storage.

By using nearly-opaque IDs we can change the underlying data layout as need to optimize performance/memory, without disrupting client code.

Strings

To minimize memory usage, we store each unique string only once in the netlist and give it a unique ID (StringId). Any references to this string then make use of the StringId.

In particular this prevents the (potentially large) strings from begin duplicated multiple times in various look-ups, instead the more space efficient StringId is duplicated.

Note that StringId is an internal implementation detail and should not be exposed as part of the public interface. Any public functions should take and return std::string’s instead.

Block pins/Block ports data layout

The pins/ports for each block are stored in a similar manner, for brevity we describe only pins here.

The pins for each block (i.e. PinId’s) are stored in a single vector for each block (the block_pins_ member). This allows us to iterate over all pins (i.e. block_pins()), or specific subsets of pins (e.g. only inputs with block_input_pins()).

To accomplish this all pins of the same group (input/output/clock) are located next to each other. An example is shown below, where the block has n input pins, m output pins and k clock pins.

 -------------------------------------------------------------------------------------------------------------------
 | ipin_1 | ipin_2 | ... | ipin_n | opin_1 | opin_2 | ... | opin_m | clock_pin_1 | clock_pin_2 | ... | clock_pin_k |
 -------------------------------------------------------------------------------------------------------------------
 ^                                ^                                ^                                               ^
 |                                |                                |                                               |
begin                         opin_begin                    clock_pin_begin                                       end

Provided we know the internal dividing points (i.e. opin_begin and clock_pin_begin) we can easily build the various ranges of interest: 

 all pins   : [begin, end)
 input pins : [begin, opin_begin)
 output pins: [opin_begin, clock_pin_begin)
 clock pins : [clock_pin_begin, end)

Since any reallocation would invalidate any iterators to these internal dividers, we separately store the number of input/output/clock pins per block (i.e. in block_num_input_pins_, block_num_output_pins_ and block_num_clock_pins_). The internal dividers can then be easily calculated (e.g. see block_output_pins()), even if new pins are inserted (provided the counts are updated).

Adding data to the netlist

The Netlist should contain only information directly related to the netlist state (i.e. netlist connectivity). Various mappings to/from elements (e.g. what CLB contains an atom block), and algorithmic state (e.g. if a net is routed) do NOT constitute netlist state and should NOT be stored here.

Such implementation state should be stored in other data structures (which may reference the Netlist’s IDs).

The netlist state should be immutable (i.e. read-only) for most of the CAD flow.

Interactions with other netlists

Currently, the AtomNetlist and ClusteredNetlist are both derived from Netlist. The AtomNetlist has primitive specific details (t_model, TruthTable), and handles all operations with the atoms. The ClusteredNetlist contains information on the CLB (Clustered Logic Block) level, which includes the physical description of the blocks (t_logical_block_type), as well as the internal hierarchy and wiring (t_pb/t_pb_route).

The calling-conventions of the functions in the AtomNetlist and ClusteredNetlist is as follows:

Functions where the derived class (Atom/Clustered) calls the base class (Netlist) create_*()

Functions where the base class calls the derived class (Non-Virtual Interface idiom as described https://en.wikibooks.org/wiki/More_C%2B%2B_Idioms/Non-Virtual_Interface) remove_*() clean_*() validate_*_sizes() shrink_to_fit() The derived functions based off of the virtual functions have suffix *_impl()

Classes

template<typename BlockId, typename PortId, typename PinId, typename NetId>
class Netlist

Public Functions

const std::string &netlist_name() const

Retrieve the name of the netlist.

const std::string &netlist_id() const

Retrieve the unique identifier for this netlist This is typically a secure digest of the input file.

bool verify() const

Sanity check for internal consistency (throws an exception on failure)

bool is_dirty() const

Returns true if the netlist has invalid entries due to modifications (e.g. from remove_*() calls)

bool is_compressed() const

Returns true if the netlist has no invalid entries due to modifications (e.g. from remove_*() calls)

Note

This is a convenience method which is the logical inverse of is_dirty()

void print_stats() const

Item counts and container info (for debugging)

const std::string &block_name(const BlockId blk_id) const

Returns the name of the specified block.

bool block_is_combinational(const BlockId blk_id) const

Returns true if the block is purely combinational (i.e. no input clocks and not a primary input.

attr_range block_attrs(const BlockId blk_id) const

Returns a range of all attributes associated with the specified block.

param_range block_params(const BlockId blk_id) const

Returns a range of all parameters associated with the specified block.

pin_range block_pins(const BlockId blk_id) const

Returns a range of all pins associated with the specified block.

pin_range block_input_pins(const BlockId blk_id) const

Returns a range of all input pins associated with the specified block.

pin_range block_output_pins(const BlockId blk_id) const

Returns a range of all output pins associated with the specified block.

Note

This is typically only data pins, but some blocks (e.g. PLLs) can produce outputs which are clocks.

pin_range block_clock_pins(const BlockId blk_id) const

Returns a range of all clock pins associated with the specified block.

port_range block_ports(const BlockId blk_id) const

Returns a range of all ports associated with the specified block.

port_range block_input_ports(const BlockId blk_id) const

Returns a range consisting of the input ports associated with the specified block.

port_range block_output_ports(const BlockId blk_id) const

Returns a range consisting of the output ports associated with the specified block.

Note

This is typically only data ports, but some blocks (e.g. PLLs) can produce outputs which are clocks.

port_range block_clock_ports(const BlockId blk_id) const

Returns a range consisting of the input clock ports associated with the specified block.

void remove_block(const BlockId blk_id)

Removes a block from the netlist. This will also remove the associated ports and pins.

Parameters

  • blk_id: The block to be removed

const std::string &port_name(const PortId port_id) const

Returns the name of the specified port.

BlockId port_block(const PortId port_id) const

Returns the block associated with the specified port.

pin_range port_pins(const PortId port_id) const

Returns the set of valid pins associated with the port.

PinId port_pin(const PortId port_id, const BitIndex port_bit) const

Returns the pin (potentially invalid) associated with the specified port and port bit index.

Note

This function is a synonym for find_pin()

Parameters

  • port_id: The ID of the associated port

  • port_bit: The bit index of the pin in the port

NetId port_net(const PortId port_id, const BitIndex port_bit) const

Returns the net (potentially invalid) associated with the specified port and port bit index.

Parameters

  • port_id: The ID of the associated port

  • port_bit: The bit index of the pin in the port

BitIndex port_width(const PortId port_id) const

Returns the width (number of bits) in the specified port.

PortType port_type(const PortId port_id) const

Returns the type of the specified port.

void remove_port(const PortId port_id)

Removes a port from the netlist.

The port’s pins are also marked invalid and removed from any associated nets

Parameters

  • port_id: The ID of the port to be removed

std::string pin_name(const PinId pin_id) const

Returns the constructed name (derived from block and port) for the specified pin.

PinType pin_type(const PinId pin_id) const

Returns the type of the specified pin.

NetId pin_net(const PinId pin_id) const

Returns the net associated with the specified pin.

int pin_net_index(const PinId pin_id) const

Returns the index of the specified pin within it’s connected net.

PortId pin_port(const PinId pin_id) const

Returns the port associated with the specified pin.

BitIndex pin_port_bit(const PinId pin_id) const

Returns the port bit index associated with the specified pin.

BlockId pin_block(const PinId pin_id) const

Returns the block associated with the specified pin.

PortType pin_port_type(const PinId pin_id) const

Returns the port type associated with the specified pin.

bool pin_is_constant(const PinId pin_id) const

Returns true if the pin is a constant (i.e. its value never changes)

void remove_pin(const PinId pin_id)

Removes a pin from the netlist.

The pin is marked invalid, and removed from any assoicated nets

Parameters

  • pin_id: The pin_id of the pin to be removed

const std::string &net_name(const NetId net_id) const

Returns the name of the specified net.

pin_range net_pins(const NetId net_id) const

Returns a range consisting of all the pins in the net (driver and sinks)

The first element in the range is the driver (and may be invalid) The remaining elements (potentially none) are the sinks

PinId net_pin(const NetId net_id, int net_pin_index) const

Returns the net_pin_index’th pin of the specified net.

BlockId net_pin_block(const NetId net_id, int net_pin_index) const

Returns the block associated with the net_pin_index’th pin of the specified net.

PinId net_driver(const NetId net_id) const

Returns the (potentially invalid) net driver pin.

BlockId net_driver_block(const NetId net_id) const

Returns the (potentially invalid) net driver block.

pin_range net_sinks(const NetId net_id) const

Returns a (potentially empty) range consisting of net’s sink pins.

bool net_is_constant(const NetId net_id) const

Returns true if the net is driven by a constant pin (i.e. its value never changes)

void remove_net(const NetId net_id)

Removes a net from the netlist.

This will mark the net’s pins as having no associated.

Parameters

  • net_id: The net to be removed

void remove_net_pin(const NetId net_id, const PinId pin_id)

Removes a connection betwen a net and pin.

The pin is removed from the net and the pin will be marked as having no associated net

Parameters

  • net_id: The net from which the pin is to be removed

  • pin_id: The pin to be removed from the net

block_range blocks() const

Returns a range consisting of all blocks in the netlist.

port_range ports() const

Returns a range consisting of all ports in the netlist.

net_range nets() const

Returns a range consisting of all nets in the netlist.

pin_range pins() const

Returns a range consisting of all pins in the netlist.

BlockId find_block(const std::string &name) const

Returns the BlockId of the specified block or BlockId::INVALID() if not found.

Parameters

  • name: The name of the block

PortId find_port(const BlockId blk_id, const std::string &name) const

Returns the PortId of the specifed port if it exists or PortId::INVALID() if not.

Note

This method is typically less efficient than searching by a t_model_port With the overloaded AtomNetlist method

Parameters

  • blk_id: The ID of the block who’s ports will be checked

  • name: The name of the port to look for

NetId find_net(const std::string &name) const

Returns the NetId of the specified net or NetId::INVALID() if not found.

Parameters

  • name: The name of the net

PinId find_pin(const PortId port_id, BitIndex port_bit) const

Returns the PinId of the specified pin or PinId::INVALID() if not found.

Parameters

  • port_id: The ID of the associated port

  • port_bit: The bit index of the pin in the port

PinId find_pin(const std::string name) const

Returns the PinId of the specified pin or PinId::INVALID() if not found.

Note

This method is SLOW, O(num_pins) avoid if possible

Parameters

  • name: The name of the pin

void set_pin_net(const PinId pin, PinType pin_type, const NetId net)

Add the specified pin to the specified net as pin_type.

Automatically removes any previous net connection for this pin.

Parameters

  • pin: The pin to add

  • pin_type: The type of the pin (i.e. driver or sink)

  • net: The net to add the pin to

void set_pin_is_constant(const PinId pin_id, const bool value)

Mark a pin as being a constant generator.

There are some cases where a pin can not be identified as a is constant until after the full netlist has been built; so we expose a way to mark existing pins as constants.

Parameters

  • pin_id: The pin to be marked

  • value: The boolean value to set the pin_is_constant attribute

void set_block_name(const BlockId blk_id, const std::string new_name)

Re-name a block.

Parameters

  • blk_id: : The block to be renamed

  • new_name: : The new name for the specified block

void set_block_attr(const BlockId blk_id, const std::string &name, const std::string &value)

Set a block attribute.

Parameters

  • blk_id: The block to which the attribute is attached

  • name: The name of the attribute to set

  • value: The new value for the specified attribute on the specified block

void set_block_param(const BlockId blk_id, const std::string &name, const std::string &value)

Set a block parameter.

Parameters

  • blk_id: The block to which the parameter is attached

  • name: The name of the parameter to set

  • value: The new value for the specified parameter on the specified block

void merge_nets(const NetId driver_net, const NetId sink_net)

Merges sink_net into driver_net.

After merging driver_net will contain all the sinks of sink_net

Parameters

  • driver_net: The net which includes the driver pin

  • sink_net: The target net to be merged into driver_net (must have no driver pin)

IdRemapper remove_and_compress()

Wrapper for remove_unused() & compress()

This function should be used in the case where a netlist is fully modified

void remove_unused()

This should be called after completing a series of netlist modifications (e.g. removing blocks/ports/pins/nets).

Marks netlist components which have become redundant due to other removals (e.g. ports with only invalid pins) as invalid so they will be destroyed during compress()

IdRemapper compress()

Compresses the netlist, removing any invalid and/or unreferenced blocks/ports/pins/nets.

Note

this invalidates all existing IDs!