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
anddry_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
andpPOLevels
can be used to create anotherbuffer_insertion
instance of the same state (current schedule), which also define a unique buffered network. (Setps.scheduling = provided
andps.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 schedulingASAP_depth
= As-Soon-As-Possible scheduling with depth optimalityALAP
= ASAP (to obtain depth) followed by As-Late-As-Possible schedulingALAP_depth
= As-Late-As-Possible scheduling with depth optimalitybetter
= ASAP followed by ALAP, then count buffers for both assignments and choose the better onebetter_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 optimizationone_pass
= Try to form a chunk starting from each gate, once for all gatesuntil_sat
= Iterate over all gates until no more beneficial chunk movement can be foundoptimal
= 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 optimizationone_pass
= Try to form a chunk starting from each gate, once for all gatesuntil_sat
= Iterate over all gates until no more beneficial chunk movement can be foundoptimal
= Use an SMT solver to find the global optimal
-
uint32_t max_chunk_size = {100u}
The maximum size of a chunk.
-
enum scheduling_policy
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)