Graph-oriented Layout Design

Generates FCN gate-level layouts from logic network specifications by spanning a search space graph where each placement event can be represented as a search space vertex characterized by a partial layout at that instance. Edges between a partial layout \(a\) and \(b\) exist iff \(a\) can be transformed into \(b\) via a single placement event. Similar to navigating through a maze, A*-search can be employed to discover a path from the starting vertex (the empty layout) to the exit of the maze (a layout with all gates placed). This approach is scalable but requires that the input network is restricted to a 3-graph. At the same time, the output layout will always be 2DDWave-clocked and is not always optimal.

C++Python

Header: fiction/algorithms/physical_design/graph_oriented_layout_design.hpp

struct graph_oriented_layout_design_params

Parameters for the graph-oriented layout design algorithm.

Public Types

enum class effort_mode : std::uint8_t

The effort_mode enum defines different levels of computational effort for generating and exploring search space graphs for during the graph-oriented layout design process. Each mode varies in the number of search space graphs generated and the strategies employed, balancing between runtime efficiency and the likelihood of finding optimal solutions.

Values:

enumerator HIGH_EFFICIENCY

HIGH_EFFICIENCY mode generates 2 search space graphs. This option minimizes runtime but may not always yield the optimal results.

enumerator HIGH_EFFORT

HIGH_EFFORT mode generates 12 search space graphs using various fanout substitution strategies, PI placements, and other parameters. This wider exploration increases the chance of finding optimal layouts but also extends runtime. When a solution is found in any graph, its cost is used to prune the remaining graphs.

enumerator HIGHEST_EFFORT

HIGHEST_EFFORT mode builds upon HIGH_EFFORT by duplicating the 12 search space graphs for different cost objectives. If the cost objective involves layout area, number of crossings, number of wire segments, or a combination of area and crossings, a total of 48 search space graphs are generated. For a custom cost objective, an additional 12 graphs are created, resulting in 60 graphs in total.

enumerator MAXIMUM_EFFORT

MAXIMUM_EFFORT mode builds upon HIGHEST_EFFORT by duplicating the 48 (60) search space graphs using randomized fanout substitution strategies and topological orderings. If the cost objective involves layout area, number of crossings, number of wire segments, or a combination of area and crossings, a total of 96 search space graphs are generated. For a custom cost objective, an additional 12 graphs are created, resulting in 120 graphs in total. This mode has a higher chance of finding optimal solutions but significantly increases runtime.

enum class cost_objective : std::uint8_t

The cost_objective enum defines various cost objectives that can be used in the graph-oriented layout design process. Each cost objective represents a different metric used to expand a vertex in the search space graph.

Values:

enumerator AREA

AREA: Optimizes for the total area of the layout, aiming to minimize the space required for the design.

enumerator WIRES

WIRES: Optimizes for the number of wire segments in the layout, reducing the delay and increasing throughput.

enumerator CROSSINGS

CROSSINGS: Optimizes for the number of wire crossings in the layout.

enumerator ACP

ACP (Area-Crossings Product): Optimizes for a combination of layout area and the number of crossings.

enumerator CUSTOM

CUSTOM: Allows for a user-defined cost objective, enabling optimization based on specific criteria outside the predefined options.

Public Members

effort_mode mode = effort_mode::HIGH_EFFORT

The effort mode used. Defaults to HIGH_EFFORT.

uint64_t num_vertex_expansions = 4u

Number of expansions for each vertex that should be explored. For each partial layout, num_vertex_expansions positions will be checked for the next node/gate to be placed. A lower value requires less runtime, but the layout might have a larger area or it could also lead to no solution being found. A higher value might lead to better solutions, but also requires more runtime. Defaults to 4 expansions for each vertex.

bool return_first = false

Return the first found layout, which might still have a high cost but can be found fast.

uint64_t timeout = std::numeric_limits<uint64_t>::max()

Timeout limit (in ms).

bool planar = false

Disable the creation of crossings during layout generation. If set to true, gates will only be placed if a crossing-free wiring is found. Defaults to false.

cost_objective cost = cost_objective::AREA

The cost objective used. Defaults to AREA

bool enable_multithreading = false

BETA feature: Flag to enable or disable multithreading during the execution of the layout design algorithm.

When set to true, the algorithm will utilize multiple threads to process different search space graphs in parallel, improving performance by distributing the workload across available CPU cores. If set to false, the algorithm will run sequentially on a single thread.

Only recommended for HIGH_EFFORT and HIGHEST_EFFORT modes and complex networks (> 100 nodes).

Enabling multithreading can significantly speed up the algorithm, especially when using multiple search space graphs and dealing with complex networks, by concurrently expanding them. However, it may introduce additional overhead for thread synchronization and can increase memory usage. It is therefore not recommended for small input networks.

Default value: false

bool verbose = false

Verbosity.

std::optional<uint32_t> seed = std::nullopt

Random seed used for random fanout substitution and random topological ordering in maximum-effort mode, generated randomly if not specified.

bool straight_inverters = false

Enforce NOT gates to be routed non-bending only.

uint64_t tiles_to_skip_between_pis = 0

For each primary input (PI) considered during placement, reserve this many empty tiles after the current frontier:

• Top edge (row 0): leave tiles_to_skip_between_pis empty tiles to the right of the rightmost occupied tile before proposing a new PI position.

• Left edge (column 0): leave tiles_to_skip_between_pis empty tiles below the bottommost occupied tile before proposing a new PI position.

This soft margin can reduce local congestion and increase the probability of finding a routable layout at the expense of a temporarily larger footprint, which post-layout optimization may later shrink. Defaults to 0.

bool randomize_tiles_to_skip_between_pis = false

When enabled, randomizes the tiles_to_skip_between_pis value for each PI placement. The random value will be chosen from 0 to tiles_to_skip_between_pis (inclusive). This can help explore different placement strategies and potentially find better layouts. Uses the same random seed as other randomization features for reproducibility. Defaults to false.

struct graph_oriented_layout_design_stats

This struct stores statistics about the graph-oriented layout design process.

Public Functions

inline void report(std::ostream &out = std::cout) const

Reports the statistics to the given output stream.

Parameters:

out – Output stream.

Public Members

mockturtle::stopwatch::duration time_total = {}

Runtime of the graph-oriented layout design process.

uint64_t x_size = {0ull}

Layout width.

uint64_t y_size = {0ull}

Layout height.

uint64_t num_gates = {0ull}

Number of gates.

uint64_t num_wires = {0ull}

Number of wires.

uint64_t num_crossings = {0ull}

Number of crossings.

template<typename Lyt, typename Ntk>
std::optional<Lyt> fiction::graph_oriented_layout_design(Ntk &ntk, graph_oriented_layout_design_params ps = {}, graph_oriented_layout_design_stats *pst = nullptr, std::function<uint64_t(const Lyt&)> custom_cost_objective = nullptr)

A scalable and efficient placement & routing approach based on spanning a search space graph of partial layouts and finding a path to one of its leaves, i.e., a complete layout.

The search space graph starts with an empty layout and then expands it based on where the first node in a topological sort of the logic network can be placed. Based on the position of this first node, a cost is assigned to each expansion based on the position of the placed node. The vertex with the lowest cost, which is the smallest layout w.r.t. the cost objective (e.g. area), is then chosen for the next expansion. This iterative process continues until a leaf node is found, which is a layout with all nodes placed. The algorithm then continues to backtrack through the search space graph to find other complete layouts with lower cost.

Exclusively generates 2DDWave-clocked layouts.

This algorithm was proposed in “A* is Born: Efficient and Scalable Physical Design for Field-coupled Nanocomputing” by S. Hofmann, M. Walter, and R. Wille in IEEE NANO 2024 (https://ieeexplore.ieee.org/document/10628808) and extended in “Physical Design for Field-coupled Nanocomputing with Discretionary Cost Objectives” by S. Hofmann, M. Walter, and R. Wille in LASCAS 2025 (https://ieeexplore.ieee.org/document/10966234).

Template Parameters:

• Lyt – Cartesian gate-level layout type.

• Ntk – Network type.

Parameters:

• ntk – The network to be placed and routed.

• ps – The parameters for the A* priority routing algorithm. Defaults to an empty parameter set.

• pst – A pointer to a statistics object to record execution details. Defaults to nullptr.

• custom_cost_objective – A custom cost objective that is evaluated at every expansion of the search space graph. Should be a function that can be calculated based on the current partial layout and returns an uint64_t that should be minimized.

Returns:

The smallest layout yielded by the graph-oriented layout design algorithm under the given parameters.