Wiring Reduction in 2DDWave-clocked Cartesian Layouts

Header: fiction/algorithms/physical_design/wiring_reduction.hpp

This algorithm aims to minimize the number of wire segments, the area, and the length of the critical path in 2DDWave-clocked Cartesian gate-level layouts.

Initially, it constructs an equivalent layout where non-wire tiles are obstructed, and wire-tiles are obstructed selectively based on the search direction, either horizontal from left to right or vertical from top to bottom. Subsequently, it employs A* path-finding to identify cuts through the layout that are eligible for deletion.

The removal of these wire tiles creates gaps, which are then filled by shifting all gates located beneath the emptied spaces upward and subsequently reconnecting them. This iterative process continues until convergence is achieved.

Header: fiction/algorithms/physical_design/wiring_reduction.hpp

struct wiring_reduction_params

Parameters for the wiring reduction algorithm.

Public Members

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

Timeout limit (in ms). Specifies the maximum allowed time in milliseconds for the optimization process. For large layouts, the actual execution time may slightly exceed this limit because it’s impractical to check the timeout at every algorithm step and the functional correctness has to be ensured by completing essential algorithm steps.

struct wiring_reduction_stats

This struct stores statistics about the wiring reduction 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 = {0}

Runtime of the wiring reduction process.

uint64_t x_size_before = {0ull}

Layout width before the wiring reduction process.

uint64_t y_size_before = {0ull}

Layout height before the wiring reduction process.

uint64_t x_size_after = {0ull}

Layout width after the wiring reduction process.

uint64_t y_size_after = {0ull}

Layout height before the wiring reduction process.

uint64_t num_wires_before = {0ull}

Number of wire segments before the wiring reduction process.

uint64_t num_wires_after = {0ull}

Number of wire segments after the wiring reduction process.

double wiring_improvement = {0ull}

Improvement in the number wire segments.

double area_improvement = {0ull}

Improvement in layout area.

template<typename Lyt>
void fiction::wiring_reduction(const Lyt &lyt, wiring_reduction_params ps = {}, wiring_reduction_stats *pst = nullptr) noexcept

A scalable wiring reduction algorithm for 2DDWave-clocked layouts based on A* path finding.

The core concept revolves around the selective removal of excess wiring by cutting them from a layout, contingent upon the ability to restore functional correctness by realigning the remaining layout fragments. Given the complexity of identifying these cuts, obstructions are strategically inserted into the layout to safeguard against the inadvertent deletion of standard gates or wire segments essential for the layout’s integrity. Leveraging the obstructed layout as a basis, A* Search is employed to systematically identify feasible cuts either from left to right or top to bottom. Subsequently, these identified cuts are removed from the layout to minimize not only the number of wire segments, but also the area and critical path length.

Template Parameters:

Lyt – Cartesian gate-level layout type.

Parameters:

  • lyt – The 2DDWave-clocked layout whose wiring is to be reduced.

  • ps – Parameters.

  • pst – Statistics.