AQFP buffer insertion and verification

Header: mockturtle/algorithms/aqfp/buffer_insertion.hpp

Technology assumptions

Warning

doxygenstruct: Cannot find class “mockturtle::aqfp_assumptions” in doxygen xml output for project “mockturtle” from directory: doxyxml/xml

Buffer insertion algorithms

template<typename Ntk> class 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.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)

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
Returns:: The number of buffers in the resulting network

template<class BufNtk> inline uint32_t run(BufNtk &bufntk, std::vector<uint32_t> &pi_lvls)

Insert buffers and obtain a buffered network.

It is suggested to write the pi_levels information into a dumped file for easier recovery of the scheduled phase assignment.

Parameters:

bufntk – An empty network of an appropriate buffered network type to to store the buffer-insertion result
pi_lvls – A vector which will store the PI level assignment (it is recommended to store this information together with the buffered network)

Returns:

The number of buffers in the resulting network

inline uint32_t dry_run()

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.

pLevels and pPOLevels can be used to create another buffer_insertion instance of the same state (current schedule), which also define a unique buffered network. (Set ps.scheduling = provided and ps.optimization_effort = none)

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 po_level(uint32_t idx) const: Level of the idx-th PO (imaginary dummy PO node, not counted in depth).

inline uint32_t depth() const

Network depth considering AQFP buffers/splitters.

Should be equal to max( po_level(i) - 1 ).

This is the number of phases from the previous-stage register to the next-stage register, including the depth of the previous-stage register (i.e., from one register input to the next register input).

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 bool is_scheduled_ASAP() const: The chosen schedule is ASAP.

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 ASAP_depth(fanout_view<Ntk> const &f_ntk, bool try_regular)

ASAP optimal-depth scheduling.

ASAP_depth should follow right after ALAP_depth (i.e., initialization).

Parameters:: try_regular – tries to insert balanced trees when sufficient slack.

inline void ALAP()

ALAP scheduling.

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

inline void ALAP_depth(fanout_view<Ntk> const &f_ntk): ALAP depth-optimal sheduling.

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.

Parameters

struct buffer_insertion_params

Parameters for (AQFP) buffer insertion.

Public Types

enum scheduling_policy

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
ASAP_depth = As-Soon-As-Possible scheduling with depth optimality
ALAP = ASAP (to obtain depth) followed by As-Late-As-Possible scheduling
ALAP_depth = As-Late-As-Possible scheduling with depth optimality
better = ASAP followed by ALAP, then count buffers for both assignments and choose the better one
better_depth = ALAP_depth followed by ASAP_depth, then count buffers for both assignments and choose the better one

Values:

enumerator provided

enumerator ASAP

enumerator ASAP_depth

enumerator ALAP

enumerator ALAP_depth

enumerator better

enumerator better_depth

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_realistic assume: Technology assumptions.

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

The results of this algorithm can be dumped into an appropriate :ref:buffered_network type and written out in the Verilog format.

Verification of buffered networks

Header: mockturtle/algorithms/aqfp/buffer_verification.hpp

Warning

doxygenfunction: Unable to resolve function “mockturtle::verify_aqfp_buffer” with arguments (Ntk const&, aqfp_assumptions const&) in doxygen xml output for project “mockturtle” from directory: doxyxml/xml. Potential matches:

- template<class Ntk, typename Asmp = aqfp_assumptions> bool verify_aqfp_buffer(Ntk const &ntk, Asmp const &ps, std::vector<uint32_t> const &pi_levels)
- template<class Ntk> bool verify_aqfp_buffer(Ntk const &ntk, aqfp_assumptions_legacy const &ps, node_map<uint32_t, Ntk> const &levels)
- template<class Ntk> bool verify_aqfp_buffer(Ntk const &ntk, aqfp_assumptions_realistic const &ps, node_map<uint32_t, Ntk> const &levels)

Warning

doxygenfunction: Cannot find function “mockturtle::schedule_buffered_network” in doxygen xml output for project “mockturtle” from directory: doxyxml/xml

Warning

doxygenfunction: Unable to resolve function “mockturtle::verify_aqfp_buffer” with arguments (Ntk const&, aqfp_assumptions const&, node_map<uint32_t, Ntk> const&) in doxygen xml output for project “mockturtle” from directory: doxyxml/xml. Potential matches:

- template<class Ntk, typename Asmp = aqfp_assumptions> bool verify_aqfp_buffer(Ntk const &ntk, Asmp const &ps, std::vector<uint32_t> const &pi_levels)
- template<class Ntk> bool verify_aqfp_buffer(Ntk const &ntk, aqfp_assumptions_legacy const &ps, node_map<uint32_t, Ntk> const &levels)
- template<class Ntk> bool verify_aqfp_buffer(Ntk const &ntk, aqfp_assumptions_realistic const &ps, node_map<uint32_t, Ntk> const &levels)