Multi-Path Routing (Color Routing)

Utilizes graph coloring to determine non-conflicting paths between multiple given routing objectives in an FCN gate-level layout. This approach can be parameterized to tradeoff completeness (full path enumeration and SAT-based coloring) and runtime (limited path exploration and/or heuristic coloring). This algorithm is suitable for all clocking schemes and layout topologies and will apply all determined paths directly to the given layout. In case heuristic settings have been specified, the conduct_partial_routing parameter must be set to apply a non-complete set of paths to the layout.

C++Python

Header: fiction/algorithms/physical_design/color_routing.hpp

struct color_routing_params

Parameters for the color routing algorithm.

Public Members

bool conduct_partial_routing = false

Do not abort if some objectives cannot be fulfilled, but partially route the layout as much as possible.

bool crossings = false

Enable crossings.

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.

graph_coloring_engine engine = graph_coloring_engine::SAT

The engine to use.

bool partial_sat = false

Allow partial solutions when the SAT engine is used.

struct color_routing_stats

Public Members

mockturtle::stopwatch::duration time_total = {0}

Runtime measurement.

std::size_t number_of_unsatisfied_objectives = {0}

For each routing objective that was not fulfilled by the coloring engine, this counter is incremented.

generate_edge_intersection_graph_stats epg_stats = {}

Statistics of the edge intersection graph generation.

determine_vertex_coloring_stats color_stats = {}

Statistics of the vertex coloring.

template<typename Lyt>
bool fiction::color_routing(Lyt &lyt, const std::vector<routing_objective<Lyt>> &objectives, color_routing_params ps = {}, color_routing_stats *pst = nullptr)

A multi-path signal routing approach based on coloring of edge intersection graphs as originally proposed in “Efficient Multi-Path Signal Routing for Field-coupled Nanotechnologies” by M. Walter and R. Wille in NANOARCH 2022.

Given a gate-level layout and a set of routing objectives, this algorithm tries to fulfill all objectives by routing several conflict-free wire paths. To this end, a plethora of possible paths are enumerated in the given layout and an edge-intersection graph of paths on a grid (EPG) created from them. In an EPG, each vertex represents a path and each edge conflicts between them. When two vertices are connected by an edge, they cannot be routed together conflict-free in the layout. To determine a (maximum) set of routable paths, a vertex coloring is computed on the EPG. Finally, all vertices that are colored identically can be routed together. The biggest such set is applied to the layout.

Multiple parameters can be set to specify the behavior of the algorithm. For instance, whether crossings should be enabled and whether a partial routing should be conducted if not all objectives could be fulfilled. Furthermore, the path enumeration and the coloring can be parameterized in the first place. By default, all paths are enumerated for each objective. While this guarantees completeness on small layouts, it quickly becomes intractable. Therefore, a path limit can be set that restricts the number of paths to the \(k\) shortest. Additionally, for the coloring process, SAT solving is used by default, which, again, guarantees completeness, but becomes infeasible rather quickly. However, powerful symmetry breaking is applied that assists the solving process, e.g., it is known that all vertices that are belonging to the same objective are forming a clique, which can be pre-colored. Additionally, lexicographical orderings are enforced. For a more scalable (yet incomplete) approach, several coloring heuristics are available, from which can be chosen (see determine_vertex_coloring).

This function will return true if all objectives could be satisfied or if the partial routing parameter was set. In the case of true being returned, all determined paths have been routed in the given layout.

Template Parameters:

Lyt – The gate-level layout type to route.

Parameters:

• lyt – A gate-level layout to route.

• objectives – The routing objectives as source-target pairs to fulfill.

• ps – Parameters.

• pst – Statistics.

Returns:

true iff routing was successful, i.e., iff all objectives could be satisfied.