From 3930a6154730dd24e5bee9201ec301a49944b912 Mon Sep 17 00:00:00 2001 From: Martin Braun Date: Wed, 6 Apr 2022 22:03:27 +0200 Subject: rfnoc: Modify prop. propagation algorithm (back-edge resolution) Previously, the property propagation algorithm would first forward and resolve properties only along forward edges. Then, we would check that properties also align across back-edges. The assumption is that graphs are always structured in a way such that back-edges would align when the resolution is done. However, for the following graph, this would fail: Radio ---> Replay ^ | +---------+ The reason is that the radio block and the replay block both have an "atomic_item_size" property, which needs to be resolved both ways. If the default atomic_item_size is 4 for the radio, and 8 for the replay block, then the input atomic_item_size on the radio will never be aligned with the output atomic_item_size of the replay block, and there is no other mechanism to align those. The solution is to run the edge property propagation and resolution twice, first for the forward edges, then for the back-edges. For graphs that would previously work, this makes no difference: The additional step of propagation properties across the back-edges will not dirty any properties. However, for graphs like the one above, it will provide an additional resolution path for properties that are otherwise not connected. --- host/lib/include/uhdlib/rfnoc/graph.hpp | 11 +++++++++-- host/lib/rfnoc/graph.cpp | 34 ++++++++++++++++----------------- 2 files changed, 25 insertions(+), 20 deletions(-) (limited to 'host/lib') diff --git a/host/lib/include/uhdlib/rfnoc/graph.hpp b/host/lib/include/uhdlib/rfnoc/graph.hpp index 9667f4817..2cbf5fb9d 100644 --- a/host/lib/include/uhdlib/rfnoc/graph.hpp +++ b/host/lib/include/uhdlib/rfnoc/graph.hpp @@ -166,14 +166,21 @@ private: /************************************************************************** * The Algorithm *************************************************************************/ - /*! Implementation of the property propagation algorithm - */ void resolve_all_properties(uhd::rfnoc::resolve_context context, rfnoc_graph_t::vertex_descriptor initial_node); void resolve_all_properties(uhd::rfnoc::resolve_context context, node_ref_t initial_node); + /*! This is the real implementation of the property propagation algorithm. + * + * This method must only be called from resolve_all_properties(). It assumes + * that sanity checks have run, and that the graph mutex is being held. + */ + void _resolve_all_properties(uhd::rfnoc::resolve_context context, + rfnoc_graph_t::vertex_descriptor initial_node, + const bool forward); + /************************************************************************** * Action API *************************************************************************/ diff --git a/host/lib/rfnoc/graph.cpp b/host/lib/rfnoc/graph.cpp index 3584a1c2a..9ce100ec7 100644 --- a/host/lib/rfnoc/graph.cpp +++ b/host/lib/rfnoc/graph.cpp @@ -287,7 +287,6 @@ void graph_t::resolve_all_properties( return; } - node_accessor_t node_accessor{}; // We can't release during property propagation, so we lock this entire // method to make sure that a) different threads can't interfere with each // other, and b) that we don't release the graph while this method is still @@ -297,6 +296,7 @@ void graph_t::resolve_all_properties( return; } if (_release_count) { + node_accessor_t node_accessor{}; node_ref_t current_node = boost::get(vertex_property_t(), _graph, initial_node); UHD_LOG_TRACE(LOG_ID, "Only resolving node " << current_node->get_unique_id() @@ -308,6 +308,19 @@ void graph_t::resolve_all_properties( return; } + UHD_LOG_TRACE(LOG_ID, "Running forward edge property propagation..."); + _resolve_all_properties(context, initial_node, true); + UHD_LOG_TRACE(LOG_ID, "Running backward edge property propagation..."); + _resolve_all_properties(context, initial_node, false); +} + + +void graph_t::_resolve_all_properties(resolve_context context, + rfnoc_graph_t::vertex_descriptor initial_node, + const bool forward) +{ + node_accessor_t node_accessor{}; + // First, find the node on which we'll start. auto initial_dirty_nodes = _find_dirty_nodes(); if (initial_dirty_nodes.size() > 1) { @@ -364,7 +377,7 @@ void graph_t::resolve_all_properties( // Forward all edge props in all directions from current node. We make // sure to skip properties if the edge is flagged as // !property_propagation_active - _forward_edge_props(*node_it, true); + _forward_edge_props(*node_it, forward); // Now mark all properties on this node as clean node_accessor.clean_props(current_node); @@ -412,7 +425,7 @@ void graph_t::resolve_all_properties( } // Post-iteration sanity checks: - // First, we make sure that there are no dirty properties left. If there are, + // Make sure that there are no dirty properties left. If there are, // that means our algorithm couldn't converge and we have a problem. auto remaining_dirty_nodes = _find_dirty_nodes(); if (!remaining_dirty_nodes.empty()) { @@ -429,21 +442,6 @@ void graph_t::resolve_all_properties( } throw uhd::resolve_error("Could not resolve properties."); } - - // Second, go through edges marked !property_propagation_active and make - // sure that they match up - BackEdgePredicate back_edge_filter(_graph); - auto e_iterators = - boost::edges(boost::filtered_graph( - _graph, back_edge_filter)); - bool back_edges_valid = true; - for (auto e_it = e_iterators.first; e_it != e_iterators.second; ++e_it) { - back_edges_valid = back_edges_valid && _assert_edge_props_consistent(*e_it); - } - if (!back_edges_valid) { - throw uhd::resolve_error( - "Error during property resolution: Back-edges inconsistent!"); - } } void graph_t::resolve_all_properties( -- cgit v1.2.3