Scalable Orthogonal Physical Design

Utilizes approximations to the graph-theoretical problem of Orthogonal Graph Drawing to generate FCN gate-level layouts from logic network specifications. 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 has a large area overhead.

Header: fiction/algorithms/physical_design/orthogonal.hpp

struct orthogonal_physical_design_params

Parameters for the orthogonal physical design algorithm.

Public Members

num_clks number_of_clock_phases = num_clks::FOUR: Number of clock phases to use. 3 and 4 are supported.

struct orthogonal_physical_design_stats

template<typename Lyt, typename Ntk> Lyt fiction::orthogonal(const Ntk &ntk, orthogonal_physical_design_params ps = {}, orthogonal_physical_design_stats *pst = nullptr)

A scalable placement & routing approach based on orthogonal graph drawing as originally proposed in “Scalable Design for Field-coupled Nanocomputing Circuits” by M. Walter, R. Wille, F. Sill Torres, D. Große, and R. Drechsler in ASP-DAC 2019. A more extensive description can be found in “Design Automation for Field-coupled Nanotechnologies” by M. Walter, R. Wille, F. Sill Torres, and R. Drechsler published by Springer Nature in 2022.

Via certain restrictions to the degrees of freedom in FCN physical design, this algorithm achieves a polynomial time complexity. However, these restrictions lead to an overall approximation of optimal layout quality within several factors. Therefore, this algorithm produces valid layouts within a short amount of time, its results are far from being optimal in terms of area.

The imposed restrictions are that the input logic network has to be a 3-graph, i.e., cannot have any node exceeding degree 3 (combined input and output), and that the resulting layout is always 2DDWave-clocked.

This algorithm is based on a modification of “Improved orthogonal drawings of 3-graphs” by Therese C. Biedl in Canadian Conference on Computational Geometry 1996. Biedl’s original algorithm works for undirected graphs only while this modification respects information flow of directed logic networks. To this end, the edge directions of the logic network directly used instead of relabeling the edges according to its DFS tree, ordering the vertices using topological sorting instead of DFS, and adding an extra placement rule for nodes without predecessors.

The algorithm works in polynomial time \(\mathcal{O}(3|N| + |L|)\) where \(|N|\) is the number of nodes the given network and \(|L|\) is the resulting layout size given by \(x \cdot y\), which approaches \((\frac{|N|}{2})^2\) asymptotically.

May throw a high_degree_fanin_exception if ntk contains any node with a fan-in larger than 2.

Template Parameters:

Lyt – Desired gate-level layout type.
Ntk – Network type that acts as specification.

Parameters:

ntk – The network that is to place and route.
ps – Parameters.
pst – Statistics.

Returns:

A gate-level layout of type Lyt that implements ntk as an FCN circuit.

class mnt.pyfiction.orthogonal_params: Parameters for the orthogonal physical design algorithm.

mnt.pyfiction.orthogonal(network: mnt.pyfiction.pyfiction.technology_network, parameters: mnt.pyfiction.pyfiction.orthogonal_params = <mnt.pyfiction.pyfiction.orthogonal_params object at 0x7b94bc73e230>, statistics: mnt.pyfiction.pyfiction.orthogonal_stats = None) → mnt.pyfiction.pyfiction.cartesian_gate_layout

A scalable placement & routing approach based on orthogonal graph drawing as originally proposed in "Scalable Design for Field-coupled Nanocomputing Circuits" by M. Walter, R. Wille, F. Sill Torres, D. Große, and R. Drechsler in ASP-DAC 2019. A more extensive description can be found in "Design Automation for Field-coupled Nanotechnologies" by M. Walter, R. Wille, F. Sill Torres, and R. Drechsler published by Springer Nature in 2022.

Via certain restrictions to the degrees of freedom in FCN physical design, this algorithm achieves a polynomial time complexity. However, these restrictions lead to an overall approximation of optimal layout quality within several factors. Therefore, this algorithm produces valid layouts within a short amount of time, its results are far from being optimal in terms of area.

The imposed restrictions are that the input logic network has to be a 3-graph, i.e., cannot have any node exceeding degree 3 (combined input and output), and that the resulting layout is always 2DDWave-clocked.

This algorithm is based on a modification of "Improved orthogonal drawings of 3-graphs" by Therese C. Biedl in Canadian Conference on Computational Geometry 1996. Biedl’s original algorithm works for undirected graphs only while this modification respects information flow of directed logic networks. To this end, the edge directions of the logic network directly used instead of relabeling the edges according to its DFS tree, ordering the vertices using topological sorting instead of DFS, and adding an extra placement rule for nodes without predecessors.

The algorithm works in polynomial time \(\mathcal{O}(3|N| + |L|)\) where \(|N|\) is the number of nodes the given network and \(|L|\) is the resulting layout size given by \(x \cdot y\), which approaches \((\frac{|N|}{2})^2\) asymptotically.

May throw a high_degree_fanin_exception if ntk contains any node with a fan-in larger than 2.

Template parameter Lyt:: Desired gate-level layout type.
Template parameter Ntk:: Network type that acts as specification.
Parameter ntk:: The network that is to place and route.
Parameter ps:: Parameters.
Parameter pst:: Statistics.
Returns:: A gate-level layout of type Lyt that implements ntk as an FCN circuit.