Scalable Orthogonal Physical Design

Header: fiction/algorithms/physical_design/orthogonal.hpp

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.

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 in 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.