AQFP buffer insertion and verification¶

Header: mockturtle/algorithms/aqfp/buffer_insertion.hpp

Technology assumptions¶

struct mockturtle::aqfp_assumptions¶

AQFP technology assumptions.

POs count toward the fanout sizes and always have to be branched. If PIs need to be balanced, then they must also need to be branched.

Public Members

bool branch_pis = {false}¶: Whether PIs need to be branched with splitters.

bool balance_pis = {false}¶: Whether PIs need to be path-balanced.

bool balance_pos = {true}¶: Whether POs need to be path-balanced.

uint32_t splitter_capacity = {3u}¶: The maximum number of fanouts each splitter (buffer) can have.

Buffer insertion algorithms¶

template<typename Ntk> class mockturtle::buffer_insertion¶

Insert buffers and splitters for the AQFP technology.

In the AQFP technology, (1) logic gates can only have one fanout. If more than one fanout is needed, a splitter has to be inserted in between, which also takes one clocking phase (counted towards the network depth). (2) All fanins of a logic gate have to arrive at the same time (be at the same level). If one fanin path is shorter, buffers have to be inserted to balance it. Buffers and splitters are essentially the same component in this technology.

With a given level assignment to all gates in the network, the minimum number of buffers needed is determined. This class implements algorithms to count such “irredundant buffers” and to insert them to obtain a buffered network. Moreover, as buffer optimization is essentially a problem of obtaining a good level assignment, this class also implements algorithms to obtain an initial, legal assignment using scheduling algorithms and to further adjust and optimize it.

This class provides two easy-to-use top-level functions which wrap all the above steps together: run and dry_run. In addition, the following interfaces are kept for more fine-grained usage:

Query the current level assignment (level, depth)
Count irredundant buffers based on the current level assignment (count_buffers, num_buffers)
Optimize buffer count by scheduling (schedule, ASAP, ALAP) and by adjusting the level assignment with chunked movement (optimize)
Dump the resulting network into a network type which provides representation for buffers (dump_buffered_network)

Example

mig_network mig = ...

buffer_insertion_params ps;
ps.assume.branch_pis = true;
ps.assume.balance_pis = false;
ps.assume.balance_pos = true;
ps.assume.splitter_capacity = 3u;
ps.scheduling = buffer_insertion_params::ALAP;
ps.optimization_effort = buffer_insertion_params::one_pass;

buffer_insertion buffering( mig, ps );
buffered_mig_network buffered_mig;
auto const num_buffers = buffering.run( buffered_mig );

std::cout << num_buffers << std::endl;
assert( verify_aqfp_buffer( buffered_mig, ps.assume ) );
write_verilog( buffered_mig, "buffered.v" );

Required network functions:

foreach_node
foreach_gate
foreach_pi
foreach_po
foreach_fanin
is_pi
is_constant
get_node
fanout_size
size
set_visited
set_value

Public Functions

template<class BufNtk> inline uint32_t run(BufNtk &bufntk, node_map<uint32_t, Ntk> *pLevels = nullptr)¶

Insert buffers and obtain a buffered network.

Parameters

bufntk – An empty network of an appropriate buffered network type to to store the buffer-insertion result
pLevels – A pointer to a node map which will store the resulting level assignment

Returns

The number of buffers in the resulting network

inline uint32_t dry_run(node_map<uint32_t, Ntk> *pLevels = nullptr)¶

Count the number of buffers without dumping the result into a buffered network.

This function saves some runtime for dumping the resulting network and allows users to experiment on the algorithms with new network types whose corresponding buffered_network are not implemented yet.

Parameters: pLevels – A pointer to a node map which will store the resulting level assignment
Returns: The number of buffers in the resulting network

inline uint32_t level(node const &n) const¶: Level of node n considering buffer/splitter insertion.

inline uint32_t depth() const¶

Network depth considering AQFP buffers/splitters.

Note that when neither PIs nor POs are balanced, there can be different schedulings for the same buffered network (i.e. having the same number of buffers), thus this number may be different from the depth obtained by dumping the buffered network and wrapping depth_view around it.

inline uint32_t num_buffers() const¶: The total number of buffers in the network under the current level assignment.

inline uint32_t num_buffers(node const &n) const¶: The number of buffers between n and all of its fanouts under the current level assignment.

inline void count_buffers()¶

Count the number of buffers needed at the fanout of each gate according to the current level assignment.

This function must be called after level (re-)assignment and before querying num_buffers.

inline void schedule()¶: Obtain the initial level assignment using the specified scheduling policy.

inline void ASAP()¶: ASAP scheduling.

inline void ALAP()¶

ALAP scheduling.

ALAP should follow right after ASAP (i.e., initialization) without other optimization in between.

template<class BufNtk> inline void dump_buffered_network(BufNtk &bufntk) const¶

Dump buffered network.

After level assignment, (optimization), and buffer counting, this method can be called to dump the resulting buffered network.

inline void optimize()¶

Optimize with chunked movement using the specified optimization policy.

For more information, please refer to [1].

[1] Irredundant Buffer and Splitter Insertion and Scheduling-Based Optimization for AQFP Circuits. Siang-Yun Lee et. al. IWLS 2021.

Parameters¶

struct mockturtle::buffer_insertion_params¶

Parameters for (AQFP) buffer insertion.

Public Types

enum [anonymous]¶

The scheduling strategy to get the initial depth assignment.

provided = An initial level assignment is given in the constructor, thus no scheduling is performed. It is the user’s responsibility to ensure that the provided assignment is legal.
ASAP = Classical As-Soon-As-Possible scheduling
ALAP = ASAP (to obtain depth) followed by As-Late-As-Possible scheduling
better = ASAP followed by ALAP, then count buffers for both assignments and choose the better one

Values:

enumerator provided¶

enumerator ASAP¶

enumerator ALAP¶

enumerator better¶

enum [anonymous]¶

The level of optimization effort.

none = No optimization
one_pass = Try to form a chunk starting from each gate, once for all gates
until_sat = Iterate over all gates until no more beneficial chunk movement can be found
optimal = Use an SMT solver to find the global optimal

Values:

enumerator none¶

enumerator one_pass¶

enumerator until_sat¶

enumerator optimal¶

Public Members

aqfp_assumptions assume¶: Technology assumptions.

enum mockturtle::buffer_insertion_params::[anonymous] scheduling = ASAP ¶

The scheduling strategy to get the initial depth assignment.

provided = An initial level assignment is given in the constructor, thus no scheduling is performed. It is the user’s responsibility to ensure that the provided assignment is legal.
ASAP = Classical As-Soon-As-Possible scheduling
ALAP = ASAP (to obtain depth) followed by As-Late-As-Possible scheduling
better = ASAP followed by ALAP, then count buffers for both assignments and choose the better one

enum mockturtle::buffer_insertion_params::[anonymous] optimization_effort = none ¶

The level of optimization effort.

none = No optimization
one_pass = Try to form a chunk starting from each gate, once for all gates
until_sat = Iterate over all gates until no more beneficial chunk movement can be found
optimal = Use an SMT solver to find the global optimal

uint32_t max_chunk_size = {100u}¶: The maximum size of a chunk.

Buffered network data structure¶

Header: mockturtle/networks/buffered.hpp

Two buffered network types are implemented: buffered_aig_network and buffered_mig_network. They inherit from aig_network and mig_network, respectively, and are supplemented with representations for buffers.

Verification of buffered networks¶

Header: mockturtle/algorithms/aqfp/buffer_verification.hpp

template<class Ntk> bool mockturtle::verify_aqfp_buffer(Ntk const &ntk, aqfp_assumptions const &ps)¶

Verify a buffered network according to AQFP assumptions.

Parameters

ntk – Buffered network
ps – AQFP constraints

Returns

Whether ntk is path-balanced and properly-branched

template<class Ntk> node_map<uint32_t, Ntk> mockturtle::schedule_buffered_network(Ntk const &ntk, aqfp_assumptions const &ps)¶

Find a reasonable level assignment for a buffered network.

Parameters

ntk – Buffered network
ps – AQFP constraints

Returns

Level assignment to all nodes

template<class Ntk> bool mockturtle::verify_aqfp_buffer(Ntk const &ntk, aqfp_assumptions const &ps, node_map<uint32_t, Ntk> const &levels)¶

Verify a buffered network according to AQFP assumptions with provided level assignment.

Parameters

ntk – Buffered network
ps – AQFP constraints
levels – Level assignment for all nodes

Returns

Whether ntk is path-balanced and properly-branched

Simulation of buffered networks¶

Header: mockturtle/algorithms/simulation.hpp

template<uint32_t NumPIs, class Ntk> std::vector<kitty::static_truth_table<NumPIs>> mockturtle::simulate_buffered(Ntk const &ntk)¶

Simulates a buffered network.

The implementation is only slightly different from simulate by replacing foreach_gate with foreach_node and checking fanin_size because buffers are not counted as gates but still need to be simulated.