Physical Design¶

Generate Edge Intersection Graph¶

Header: fiction/physical_design/generate_edge_intersection_graph.hpp

struct generate_edge_intersection_graph_params¶

Parameters for the edge intersection graph generation algorithm.

Public Members

bool crossings = false¶: Allow crossings by not creating edges between paths that only share single-coordinate sub-paths.

std::optional<uint32_t> path_limit = std::nullopt¶: If a value is given, for each objective, only up to the path_limit shortest paths will be enumerated (using Yen’s algorithm) instead of all paths.

struct generate_edge_intersection_graph_stats¶

Public Members

mockturtle::stopwatch::duration time_total = {0}¶: Runtime measurement.

std::size_t number_of_unroutable_objectives = {0}¶: For each routing objective that cannot be fulfilled in the given layout, this counter is incremented.

std::vector<std::vector<std::size_t>> cliques = {}¶: Stores all cliques in the resulting graph that were created during path enumeration. There might be more cliques in the overall graph but these ones correspond to one routing objective each, which could be useful information to have in certain algorithms.

std::vector<std::size_t> objective_indices = {}¶: Routing objective index for each vertex ID.

std::size_t num_vertices¶: Stores the size of the generated edge intersection graph.

template<typename Lyt> edge_intersection_graph fiction::physical_design::generate_edge_intersection_graph(const Lyt &lyt, const std::vector<routing_objective> &objectives, generate_edge_intersection_graph_params ps = {}, generate_edge_intersection_graph_stats *pst = nullptr)¶

Creates an edge intersection graph of all paths that satisfy a given list of routing objectives. That is, this function generates an undirected graph whose nodes represent paths in the given layout and whose edges represent intersections of these paths. An intersection is understood as the non-disjunction of paths, i.e., they share at least one coordinate. To generate the paths for the routing objectives, all possible paths from source to target in the layout are enumerated while taking obstructions into consideration. The given layout must be clocked.

Template Parameters:

Lyt – Type of the clocked layout.

Parameters:

lyt – The layout to generate the edge intersection graph for.
objectives – Source coordinates and indexed destination inputs.
ps – Parameters.
pst – Statistics.

Returns:

An edge intersection graph of paths satisfying the given routing objectives in lyt.

Aspect Ratio Iterator¶

Header: fiction/physical_design/aspect_ratio_iterator.hpp

template<typename AspectRatio> class aspect_ratio_iterator¶

An iterator type that iterates over increasingly larger 2D aspect ratios via factorization, starting from a number of faces \(n\). After iterating over all possible factorizations of n, the next step increases \(n\) and continues with the factorization. Thereby, a sequence of aspect ratios starting from \(n = 4\) faces looks like this: \(1 \times 4, 4 \times 1, 2 \times 2, 1 \times 5, 5 \times 1, 1 \times 6, 6 \times 1, 2 \times 3, 3 \times 2, \dots\)

Template Parameters:: AspectRatio – Aspect ratio type.

Public Functions

inline explicit aspect_ratio_iterator(uint64_t n = 0ul)¶

Standard constructor. Takes a starting value and computes an initial factorization. The value n represents the amount of faces in the desired aspect ratios. For example, \(n = 1\) yields the size-based extent 1 x 1. A starting value of 2 yields extents 1 x 2 and 2 x 1.

Parameters:: n – Starting value of the aspect ratio iteration.

inline aspect_ratio_iterator &operator++()¶

Lets the iterator point to the next dimension of the current factorization. If there are no next factors, num is incremented and the next factors are computed.

Prefix version.

Returns:: Reference to this.

inline aspect_ratio_iterator operator++(int)¶

Creates a new iterator that points to the next dimension of the current factorization. If there are no next factors, num is incremented and the next factors are computed.

Postfix version. Less performance than the prefix version due to copy construction.

Returns:: Resulting iterator.

inline AspectRatio operator*() const¶: Return the current extent.

inline bool operator==(const uint64_t m) const¶: Compare iterator positions.

inline bool operator==(const aspect_ratio_iterator &other) const¶: Compare iterator positions.

inline bool operator!=(const uint64_t m) const¶: Compare iterator positions.

inline bool operator!=(const aspect_ratio_iterator &other) const¶: Compare iterator positions.

inline bool operator<(const uint64_t m) const¶: Compare iterator positions.

inline bool operator<(const aspect_ratio_iterator &other) const¶: Compare iterator positions.

inline bool operator<=(const uint64_t m) const¶: Compare iterator positions.

inline bool operator<=(const aspect_ratio_iterator &other) const¶: Compare iterator positions.

Placement Utils¶

C++

Header: fiction/physical_design/placement_utils.hpp

Place 0-input gates.

Template Parameters:

Geometry – Coordinate geometry of the gate-level layout.
Ntk – Logic network type.

Parameters:

lyt – Gate-level layout in which to place a 0-input gate.
t – Tile in lyt to place the gate onto.
ntk – Network whose node is to be placed.
n – Node in ntk to place onto t in lyt.

Returns:

Output port pointing to the placed gate in lyt.

template<typename Geometry, typename Ntk> fiction::layouts::gate_level_layout<Geometry>::object_id fiction::physical_design::place(fiction::layouts::gate_level_layout<Geometry> &lyt, const fiction::layouts::layout_base::coordinate &t, const Ntk &ntk, const mockturtle::node<Ntk> &n, const typename fiction::layouts::gate_level_layout<Geometry>::object_id &a)¶

Place 1-input gates.

Template Parameters:

Geometry – Coordinate geometry of the gate-level layout.
Ntk – Logic network type.

Parameters:

lyt – Gate-level layout in which to place a 1-input gate.
t – Tile in lyt to place the gate onto.
ntk – Network whose node is to be placed.
n – Node in ntk to place onto t in lyt.
a – Incoming signal to the newly placed gate in lyt.

Returns:

Output port pointing to the placed gate in lyt.

Place 2-input gates.

Template Parameters:

Geometry – Coordinate geometry of the gate-level layout.
Ntk – Logic network type.

Parameters:

lyt – Gate-level layout in which to place a 2-input gate.
t – Tile in lyt to place the gate onto.
ntk – Network whose node is to be placed.
n – Node in ntk to place onto t in lyt.
a – First incoming signal to the newly placed gate in lyt.
b – Second incoming signal to the newly placed gate in lyt.
c – Third optional incoming constant value signal to the newly placed gate in lyt. Might change the gate function when set, e.g., from a MAJ to an AND if c == false.

Returns:

Output port pointing to the placed gate in lyt.

Place 3-input gates.

Template Parameters:

Geometry – Coordinate geometry of the gate-level layout.
Ntk – Logic network type.

Parameters:

lyt – Gate-level layout in which to place a 3-input gate.
t – Tile in lyt to place the gate onto.
ntk – Network whose node is to be placed.
n – Node in ntk to place onto t in lyt.
a – First incoming signal to the newly placed gate in lyt.
b – Second incoming signal to the newly placed gate in lyt.
c – Third incoming signal to the newly placed gate in lyt.

Returns:

Output port pointing to the placed gate in lyt.

template<typename Geometry, typename Ntk> fiction::layouts::gate_level_layout<Geometry>::object_id fiction::physical_design::place(fiction::layouts::gate_level_layout<Geometry> &lyt, const fiction::layouts::layout_base::coordinate &t, const Ntk &ntk, const mockturtle::node<Ntk> &n, const mockturtle::node_map<typename fiction::layouts::gate_level_layout<Geometry>::object_id, Ntk> &node2pos)¶

Place any gate from a network. This function automatically identifies the arity of the passed node and fetches its incoming signals from the given network and a provided mockturtle::node_map. This function does not update the mockturtle::node_map.

Template Parameters:

Geometry – Coordinate geometry of the gate-level layout.
Ntk – Logic network type.

Parameters:

lyt – Gate-level layout in which to place any gate.
t – Tile in lyt to place the gate onto.
ntk – Network whose node is to be placed.
n – Node in ntk to place onto t in lyt.
node2pos – Mapping from network nodes to layout output ports. The map is used to fetch location of the fanins. The mockturtle::node_map is not updated by this function.

Returns:

Output port of the newly placed gate in lyt.

template<typename Ntk, uint16_t fanout_size = 2> struct branching_signal_container¶

A container class to help identify layout locations of branching nodes like fanouts. When a node from a network is to placed in a layout, fetching the node’s fanins and looking for their locations in the layout does not work properly when branching nodes like fanouts are involved that got extended by wire nodes. This container solves that issue.

Template Parameters:

Ntk – Logic network type.
fanout_size – Maximum fanout size possible in the layout and/or the network.

Public Functions

inline layouts::layout_object_id operator[](const mockturtle::node<Ntk> &n) const¶

Accesses the branching container to find the location of a given node n. Returns the signal to that location if it was already stored or the default signal, otherwise.

Parameters:: n – Node whose branching position is desired.
Returns:: Signal to n’s layout location or the default signal if it wasn’t found.

inline void update_branch(const mockturtle::node<Ntk> &ntk_node, const layouts::layout_object_id &lyt_signal)¶

Updates the given node’s branch by another layout signal, thereby, creating a new branch or updating the position of an existing one, e.g., if further wire segments were moving the head of the branch.

Parameters:

ntk_node – Node whose branch is to be updated.
lyt_signal – New signal pointing to the end of the branch.

struct branching_signal¶

Branch type.

Public Functions

inline branching_signal(const mockturtle::node<Ntk> &n, const layouts::layout_object_id &s)¶: Associates a network destination with a layout output port.

Public Members

const mockturtle::node<Ntk> ntk_node¶: Destination network node.

layouts::layout_object_id lyt_signal¶: Output port at the end of the route.

template<typename Geometry, typename Ntk, uint16_t fanout_size = 2> fiction::layouts::gate_level_layout<Geometry>::object_id fiction::physical_design::place(fiction::layouts::gate_level_layout<Geometry> &lyt, const fiction::layouts::layout_base::coordinate &t, const Ntk &ntk, const mockturtle::node<Ntk> &n, const mockturtle::node_map<branching_signal_container<Ntk, fanout_size>, Ntk> &node2pos)¶

Place any gate from a network. This function automatically identifies the arity of the passed node and fetches its incoming signals from the given network and a provided branching_signal_container mockturtle::node_map. This function does not update the mockturtle::node_map.

Template Parameters:

Geometry – Coordinate geometry of the gate-level layout.
Ntk – Logic network type.

Parameters:

lyt – Gate-level layout in which to place any gate.
t – Tile in lyt to place the gate onto.
ntk – Network whose node is to be placed.
n – Node in ntk to place onto t in lyt.
node2pos – Mapping from network nodes to layout output ports via branches. The map is used to fetch location of the fanins. The mockturtle::node_map is not updated by this function.

Returns:

Output port of the newly placed gate in lyt.

Python

place(lyt: cartesian_gate_layout, t: coordinate | tuple[int, int] | tuple[int, int, int], ntk: technology_network, n: int) → mnt.pyfiction.layouts.layout_object_id¶

place(lyt: cartesian_gate_layout, t: coordinate | tuple[int, int] | tuple[int, int, int], ntk: technology_network, n: int, a: mnt.pyfiction.layouts.layout_object_id) → mnt.pyfiction.layouts.layout_object_id

place(lyt: mnt.pyfiction.layouts.shifted_cartesian_gate_layout, t: coordinate | tuple[int, int] | tuple[int, int, int], ntk: technology_network, n: int) → mnt.pyfiction.layouts.layout_object_id

place(lyt: mnt.pyfiction.layouts.shifted_cartesian_gate_layout, t: coordinate | tuple[int, int] | tuple[int, int, int], ntk: technology_network, n: int, a: mnt.pyfiction.layouts.layout_object_id) → mnt.pyfiction.layouts.layout_object_id

place(lyt: hexagonal_gate_layout, t: coordinate | tuple[int, int] | tuple[int, int, int], ntk: technology_network, n: int) → mnt.pyfiction.layouts.layout_object_id

place(lyt: hexagonal_gate_layout, t: coordinate | tuple[int, int] | tuple[int, int, int], ntk: technology_network, n: int, a: mnt.pyfiction.layouts.layout_object_id) → mnt.pyfiction.layouts.layout_object_id

Overloaded function.

place(lyt: mnt.pyfiction.layouts.cartesian_gate_layout, t: mnt.pyfiction.layouts.coordinate | tuple[int, int] | tuple[int, int, int], ntk: mnt.pyfiction.networks.technology_network, n: int) -> mnt.pyfiction.layouts.layout_object_id

Places a primary input at the given coordinate and returns its output port.

place(lyt: mnt.pyfiction.layouts.cartesian_gate_layout, t: mnt.pyfiction.layouts.coordinate | tuple[int, int] | tuple[int, int, int], ntk: mnt.pyfiction.networks.technology_network, n: int, a: mnt.pyfiction.layouts.layout_object_id) -> mnt.pyfiction.layouts.layout_object_id
place(lyt: mnt.pyfiction.layouts.cartesian_gate_layout, t: mnt.pyfiction.layouts.coordinate | tuple[int, int] | tuple[int, int, int], ntk: mnt.pyfiction.networks.technology_network, n: int, a: mnt.pyfiction.layouts.layout_object_id, b: mnt.pyfiction.layouts.layout_object_id, c: bool | None) -> mnt.pyfiction.layouts.layout_object_id
place(lyt: mnt.pyfiction.layouts.cartesian_gate_layout, t: mnt.pyfiction.layouts.coordinate | tuple[int, int] | tuple[int, int, int], ntk: mnt.pyfiction.networks.technology_network, n: int, a: mnt.pyfiction.layouts.layout_object_id, b: mnt.pyfiction.layouts.layout_object_id, c: mnt.pyfiction.layouts.layout_object_id) -> mnt.pyfiction.layouts.layout_object_id
place(lyt: mnt.pyfiction.layouts.shifted_cartesian_gate_layout, t: mnt.pyfiction.layouts.coordinate | tuple[int, int] | tuple[int, int, int], ntk: mnt.pyfiction.networks.technology_network, n: int) -> mnt.pyfiction.layouts.layout_object_id

Places a primary input at the given coordinate and returns its output port.

place(lyt: mnt.pyfiction.layouts.shifted_cartesian_gate_layout, t: mnt.pyfiction.layouts.coordinate | tuple[int, int] | tuple[int, int, int], ntk: mnt.pyfiction.networks.technology_network, n: int, a: mnt.pyfiction.layouts.layout_object_id) -> mnt.pyfiction.layouts.layout_object_id
place(lyt: mnt.pyfiction.layouts.shifted_cartesian_gate_layout, t: mnt.pyfiction.layouts.coordinate | tuple[int, int] | tuple[int, int, int], ntk: mnt.pyfiction.networks.technology_network, n: int, a: mnt.pyfiction.layouts.layout_object_id, b: mnt.pyfiction.layouts.layout_object_id, c: bool | None) -> mnt.pyfiction.layouts.layout_object_id
place(lyt: mnt.pyfiction.layouts.shifted_cartesian_gate_layout, t: mnt.pyfiction.layouts.coordinate | tuple[int, int] | tuple[int, int, int], ntk: mnt.pyfiction.networks.technology_network, n: int, a: mnt.pyfiction.layouts.layout_object_id, b: mnt.pyfiction.layouts.layout_object_id, c: mnt.pyfiction.layouts.layout_object_id) -> mnt.pyfiction.layouts.layout_object_id
place(lyt: mnt.pyfiction.layouts.hexagonal_gate_layout, t: mnt.pyfiction.layouts.coordinate | tuple[int, int] | tuple[int, int, int], ntk: mnt.pyfiction.networks.technology_network, n: int) -> mnt.pyfiction.layouts.layout_object_id

Places a primary input at the given coordinate and returns its output port.

place(lyt: mnt.pyfiction.layouts.hexagonal_gate_layout, t: mnt.pyfiction.layouts.coordinate | tuple[int, int] | tuple[int, int, int], ntk: mnt.pyfiction.networks.technology_network, n: int, a: mnt.pyfiction.layouts.layout_object_id) -> mnt.pyfiction.layouts.layout_object_id
place(lyt: mnt.pyfiction.layouts.hexagonal_gate_layout, t: mnt.pyfiction.layouts.coordinate | tuple[int, int] | tuple[int, int, int], ntk: mnt.pyfiction.networks.technology_network, n: int, a: mnt.pyfiction.layouts.layout_object_id, b: mnt.pyfiction.layouts.layout_object_id, c: bool | None) -> mnt.pyfiction.layouts.layout_object_id
place(lyt: mnt.pyfiction.layouts.hexagonal_gate_layout, t: mnt.pyfiction.layouts.coordinate | tuple[int, int] | tuple[int, int, int], ntk: mnt.pyfiction.networks.technology_network, n: int, a: mnt.pyfiction.layouts.layout_object_id, b: mnt.pyfiction.layouts.layout_object_id, c: mnt.pyfiction.layouts.layout_object_id) -> mnt.pyfiction.layouts.layout_object_id

Routing Utils¶

C++

Header: fiction/physical_design/routing_utils.hpp

struct routing_objective¶

Routing objectives identify a geometric source and an ordered destination input.

Public Functions

inline bool operator==(const routing_objective &other) const noexcept¶

Equality operator.

Parameters:: other – Routing objective to compare to.
Returns:: true iff the given objective is equal to this one.

Public Members

const layouts::layout_base::coordinate source¶: Source coordinate.

const layouts::layout_base::coordinate target¶: Target coordinate.

uint32_t input_index = {}¶: Logical input index at the target; geometric searches ignore this field.

class layout_coordinate_path : public std::vector<layouts::layout_base::coordinate>¶

A path in a layout defined as an ordered sequence of coordinates.

Public Functions

inline void append(const layouts::layout_base::coordinate &c)¶

Appends a coordinate.

Parameters:: c – Coordinate to append.
Throws:: std::bad_alloc – If storage allocation fails.

inline layouts::layout_base::coordinate source() const noexcept¶

Returns the first coordinate, or the origin for an empty path.

Returns:: Source coordinate.

inline layouts::layout_base::coordinate target() const noexcept¶

Returns the last coordinate, or the origin for an empty path.

Returns:: Target coordinate.

template<typename Path> class path_collection : public std::vector<Path>¶

An ordered collection of multiple paths in a layout.

Template Parameters:: Path – Path type.

Public Functions

inline void add(const Path &p)¶

Adds a path.

Parameters:: p – Path to add.
Throws:: std::bad_alloc – If storage allocation fails.

inline bool contains(const Path &p) const noexcept¶

Checks whether a given path is contained in the collection.

Parameters:: p – Path to search for.
Returns:: true iff p is contained in the collection.

template<typename Path> class path_set : public std::set<Path>¶

A set of multiple paths in a layout.

Template Parameters:: Path – Path type.

Public Functions

inline void add(const Path &p)¶

Adds a path.

Parameters:: p – Path to add.
Throws:: std::bad_alloc – If storage allocation fails.

template<typename Lyt> bool fiction::physical_design::is_crossable_wire(const Lyt &lyt, const fiction::layouts::layout_base::coordinate &src, const fiction::layouts::layout_base::coordinate &successor) noexcept¶

Checks whether a given coordinate successor hosts a crossable wire when coming from coordinate src in a given layout. A wire is said to be crossable if a potential cross-over would not result in running along the same information flow direction. For example, a wire segment hosted by successor that is horizontal and runs from west to east is crossable by a wire segment coming from src that is vertical and runs from north to south. However, if the wire segment coming from src were also horizontal and ran from west to east, the cross-over would be prohibited.

@Note This function can be called on layout types other than gate-level layouts, but will then always return false. This is helpful for general routing in, e.g., clocked layouts.

Template Parameters:

Lyt – Layout type.

Parameters:

lyt – The layout.
src – Source coordinate in lyt.
successor – Successor coordinate in lyt reachable from src.

Returns:

true iff successor hosts a wire that is crossable from src.

template<typename Geometry, typename Path> void fiction::physical_design::route_path(fiction::layouts::gate_level_layout<Geometry> &lyt, const Path &path, const typename fiction::layouts::gate_level_layout<Geometry>::input_port destination)¶

Routes a path to one explicit logical input without changing other input slots.

Occupied intermediate ground coordinates use their free crossing layer. Endpoints and all intermediate placements are checked before mutation. A failed allocation removes newly created wires.

Template Parameters:

Geometry – Coordinate geometry of the gate-level layout.
Path – Coordinate path type.

Parameters:

lyt – Layout to edit.
path – Path containing at least its occupied source and target coordinates.
destination – Ordered destination input.

Throws:

std::invalid_argument – If an endpoint or intermediate placement is unavailable.
std::out_of_range – If the destination input index is invalid.

template<typename Lyt> std::vector<routing_objective> fiction::physical_design::extract_routing_objectives(const Lyt &lyt)¶

Extracts connections between retained gates, fanouts, and terminals with destination input indices.

Intermediate single-sink wires are followed through declared topology. Missing inputs produce no objective; disconnected input slots keep their indices. Cycles of intermediate wires reject.

Template Parameters:: Lyt – Gate-level layout type.
Parameters:: lyt – Layout to inspect.
Throws:: std::invalid_argument – If an intermediate wire chain contains a cycle.
Returns:: Routing objectives that preserve logical input numbering.

template<typename Geometry> void fiction::physical_design::clear_routing(fiction::layouts::gate_level_layout<Geometry> &lyt)¶

Removes routing wires and disconnects retained objects while preserving identities and input indices.

Template Parameters:: Geometry – Coordinate geometry of the gate-level layout.
Parameters:: lyt – Layout to edit.

Python

is_crossable_wire(lyt: cartesian_gate_layout, src: coordinate | tuple[int, int] | tuple[int, int, int], successor: coordinate | tuple[int, int] | tuple[int, int, int]) → bool¶

is_crossable_wire(lyt: mnt.pyfiction.layouts.shifted_cartesian_gate_layout, src: coordinate | tuple[int, int] | tuple[int, int, int], successor: coordinate | tuple[int, int] | tuple[int, int, int]) → bool

is_crossable_wire(lyt: hexagonal_gate_layout, src: coordinate | tuple[int, int] | tuple[int, int, int], successor: coordinate | tuple[int, int] | tuple[int, int, int]) → bool

Parameters:

lyt – The layout.
src – Source coordinate in lyt.
successor – Successor coordinate in lyt reachable from src.

Template Args:

Lyt – Layout type.

Returns:

true iff successor hosts a wire that is crossable from src.

Note

This function can be called on layout types other than gate-level layouts, but will then always return false. This is helpful for general routing in, e.g., clocked layouts.

route_path(layout: cartesian_gate_layout, path: Sequence[coordinate | tuple[int, int] | tuple[int, int, int]], destination: mnt.pyfiction.layouts.layout_input_port) → None¶

route_path(layout: mnt.pyfiction.layouts.shifted_cartesian_gate_layout, path: Sequence[coordinate | tuple[int, int] | tuple[int, int, int]], destination: mnt.pyfiction.layouts.layout_input_port) → None

route_path(layout: hexagonal_gate_layout, path: Sequence[coordinate | tuple[int, int] | tuple[int, int, int]], destination: mnt.pyfiction.layouts.layout_input_port) → None

Routes a path to one explicit logical input without changing other input slots.

Occupied intermediate ground coordinates use their free crossing layer. Endpoints and all intermediate placements are checked before mutation. A failed allocation removes newly created wires.

Parameters:

lyt – Layout to edit.
path – Path containing at least its occupied source and target coordinates.
destination – Ordered destination input.

Template Args:

Geometry – Coordinate geometry of the gate-level layout.
Path – Coordinate path type.

Raises:

std::invalid_argument – If an endpoint or intermediate placement is unavailable.
std::out_of_range – If the destination input index is invalid.

extract_routing_objectives(layout: cartesian_gate_layout) → list[tuple[coordinate, coordinate, int]]¶

extract_routing_objectives(layout: mnt.pyfiction.layouts.shifted_cartesian_gate_layout) → list[tuple[coordinate, coordinate, int]]

extract_routing_objectives(layout: hexagonal_gate_layout) → list[tuple[coordinate, coordinate, int]]

Extracts connections between retained gates, fanouts, and terminals with destination input indices.

Intermediate single-sink wires are followed through declared topology. Missing inputs produce no objective; disconnected input slots keep their indices. Cycles of intermediate wires reject.

Parameters:: lyt – Layout to inspect.
Template Args:: Lyt – Gate-level layout type.
Returns:: Routing objectives that preserve logical input numbering.
Raises:: std::invalid_argument – If an intermediate wire chain contains a cycle.

clear_routing(lyt: cartesian_gate_layout) → None¶

clear_routing(lyt: mnt.pyfiction.layouts.shifted_cartesian_gate_layout) → None

clear_routing(lyt: hexagonal_gate_layout) → None

Removes routing wires and disconnects retained objects while preserving identities and input indices.

Parameters:: lyt – Layout to edit.
Template Args:: Geometry – Coordinate geometry of the gate-level layout.