recti::DMEAlgorithm Class Reference

Implements the Deferred Merge Embedding (DME) algorithm for clock tree synthesis. More...

#include <dme_algorithm.hpp>

Public Member Functions
	DMEAlgorithm (const std::vector< Sink > &sinks, std::unique_ptr< DelayCalculator > calculator)
	Constructs a DMEAlgorithm object.
	DMEAlgorithm (const std::vector< Sink > &sinks, std::unique_ptr< DelayCalculator > calculator, Point< int > source_position)
	Constructs a DMEAlgorithm with a specified clock source position.
NodeIdx	build_clock_tree ()
	Builds the clock tree for the given sinks.
const Tree &	get_tree () const
	Returns a const reference to the internal tree arena.
Tree &	get_tree_mut ()
	Returns a mutable reference to the internal tree arena.
SkewAnalysis	analyze_skew (NodeIdx root) const
	Analyzes clock skew of the constructed tree.

Detailed Description

Implements the Deferred Merge Embedding (DME) algorithm for clock tree synthesis.

Uses an arena-allocated node representation (Tree) for cache efficiency. Supports both linear and Elmore delay models via the DelayCalculator interface.

Three phases:

1. Topology construction (build_merging_tree): balanced bipartitioning by coordinates.
2. Bottom-up merging (compute_merging_segments): compute Manhattan arc merging segments.
3. Top-down embedding (embed_tree): select physical positions for internal nodes.

Constructor & Destructor Documentation

DMEAlgorithm() [1/2]

recti::DMEAlgorithm::DMEAlgorithm ( const std::vector< Sink > &  sinks, std::unique_ptr< DelayCalculator >  calculator  )

inline

Constructs a DMEAlgorithm object.

Parameters

sinks	A vector of clock sinks.
calculator	A unique pointer to a DelayCalculator implementation.

Exceptions

std::invalid_argument

if sinks is empty.

DMEAlgorithm() [2/2]

recti::DMEAlgorithm::DMEAlgorithm ( const std::vector< Sink > &  sinks, std::unique_ptr< DelayCalculator >  calculator, Point< int >  source_position  )

inline

Constructs a DMEAlgorithm with a specified clock source position.

Parameters

sinks	A vector of clock sinks.
calculator	A unique pointer to a DelayCalculator implementation.
source_position	The clock source position.

Exceptions

std::invalid_argument

if sinks is empty.

Member Function Documentation

analyze_skew()

SkewAnalysis recti::DMEAlgorithm::analyze_skew

(

NodeIdx

root

)

const

Analyzes clock skew of the constructed tree.

Traverses the clock tree to collect delays at all sink nodes, then calculates the maximum delay, minimum delay, and the overall skew. Also reports the total wirelength and the delay model used.

Parameters

root	The root index of the clock tree.

Returns

A SkewAnalysis struct containing the analysis results.

Exceptions

std::runtime_error

if no sink delays are collected (e.g., empty tree).

build_clock_tree()

NodeIdx recti::DMEAlgorithm::build_clock_tree

(

)

Builds the clock tree for the given sinks.

Orchestrates the three phases of the DME algorithm: topology construction, merging segment computation, and top-down embedding. Also computes the final delays and wire lengths after embedding.

Returns

The root NodeIdx of the constructed and embedded clock tree.

get_tree()

const Tree & recti::DMEAlgorithm::get_tree ( ) const

inline

Returns a const reference to the internal tree arena.

get_tree_mut()

Tree & recti::DMEAlgorithm::get_tree_mut ( )

inline

Returns a mutable reference to the internal tree arena.

---

The documentation for this class was generated from the following file:

• recti/dme_algorithm.hpp