An abstract representation of a set of Cindexes. More...

#include <nnet-computation-graph.h>

Collaboration diagram for ComputationGraphBuilder:

[legend]

Classes
struct	CindexInfo

Public Types
enum	ComputableInfo { kUnknown = 0, kComputable = 1, kNotComputable = 2, kWillNotCompute = 3 }

Public Member Functions
	ComputationGraphBuilder (const Nnet &nnet, ComputationGraph *graph)

void	Compute (const ComputationRequest &request)

bool	AllOutputsAreComputable () const

void	ExplainWhyAllOutputsNotComputable () const

void	GetComputableInfo (std::vector< std::vector< bool > > *computable) const

void	Prune ()

Private Member Functions
void	PrintCindexId (std::ostream &os, int32 cindex_id) const

void	ExplainWhyNotComputable (int32 cindex_id) const

void	AddInputs ()

void	AddOutputs ()

void	BuildGraphOneIter ()

void	UpdateComputableInfo (int32 cindex_id)

void	SetAsWillNotCompute (int32 cindex_id)

ComputableInfo	ComputeComputableInfo (int32 cindex_id) const

void	AddCindexId (int32 cindex_id)

void	AddDependencies (int32 cindex_id)

void	IncrementUsableCount (int32 cindex_id)

void	DecrementUsableCount (int32 cindex_id)

void	PruneDependencies (int32 cindex_id)

void	ComputeRequiredArray (int32 start_cindex_id, std::vector< bool > *required) const

void	Check (int32 start_cindex_id) const

Private Attributes
const Nnet &	nnet_

const ComputationRequest *	request_

ComputationGraph *	graph_

std::vector< std::vector< int32 > >	depend_on_this_

std::vector< CindexInfo >	cindex_info_

int32	current_distance_

std::vector< int32 >	current_queue_

std::vector< int32 >	next_queue_

Detailed Description

An abstract representation of a set of Cindexes.

See Building the ComputationGraph.

Definition at line 117 of file nnet-computation-graph.h.

Member Enumeration Documentation

◆ ComputableInfo

enum ComputableInfo

Enumerator
kUnknown
kComputable
kNotComputable
kWillNotCompute

Definition at line 162 of file nnet-computation-graph.h.

                       {
     kUnknown = 0,
     kComputable = 1,
     kNotComputable = 2,
     kWillNotCompute = 3
   };

Constructor & Destructor Documentation

◆ ComputationGraphBuilder()

ComputationGraphBuilder	(	const Nnet &	nnet,
		ComputationGraph *	graph
	)

Definition at line 456 of file nnet-computation-graph.cc.

References ComputationGraph::cindexes, ComputationGraphBuilder::graph_, and KALDI_ASSERT.

                             :
     nnet_(nnet), request_(NULL), graph_(graph),
     current_distance_(-1) {
   KALDI_ASSERT(graph_->cindexes.empty() &&
                "ComputationGraphBuilder initialized with nonempty graph.");
 }

Member Function Documentation

◆ AddCindexId()

void AddCindexId ( int32 cindex_id )

inlineprivate

Definition at line 227 of file nnet-computation-graph.cc.

References KALDI_PARANOID_ASSERT.

Referenced by ComputationGraphBuilder::AddDependencies().

                                                          {
   // If this cindex_id has just now been added to the graph, the following
   // assert should succeed.
   KALDI_PARANOID_ASSERT(cindex_id == depend_on_this_.size() &&
                         cindex_id == cindex_info_.size());
   depend_on_this_.push_back(std::vector<int32>());
   cindex_info_.push_back(CindexInfo());
 }

◆ AddDependencies()

void AddDependencies ( int32 cindex_id )

private

Definition at line 626 of file nnet-computation-graph.cc.

Referenced by ComputationGraphBuilder::BuildGraphOneIter().

                                                              {
   if (static_cast<int32>(graph_->dependencies.size()) <= cindex_id) {
     graph_->dependencies.resize(2 * cindex_id + 1);
   }
   Cindex cindex = graph_->cindexes[cindex_id];
 
   // find the dependencies of this cindex.
   int32 node_index = cindex.first;
   const Index &index = cindex.second;
   const NetworkNode &node = nnet_.GetNode(node_index);
 
   std::vector<Cindex> input_cindexes;
 
   // the following switch statement sets up "input_cindexes".
   switch (node.node_type) {
     case kDescriptor: {
       // desc describes how this node obtains its input from other nodes.
       const Descriptor &desc = node.descriptor;
       desc.GetDependencies(index, &input_cindexes);
       break;
     }
     case kComponent: {
       int32 c = node.u.component_index;
       const Component *component = nnet_.GetComponent(c);
       std::vector<Index> input_indexes;
       component->GetInputIndexes(request_->misc_info, index,
                                  &input_indexes);
       input_cindexes.resize(input_indexes.size());
       for (size_t i = 0; i < input_indexes.size(); i++) {
         input_cindexes[i].first = node_index  - 1;  // preceding node
         input_cindexes[i].second = input_indexes[i];
       }
       break;
     }
     case kDimRange: {
       input_cindexes.resize(1);
       input_cindexes[0] = Cindex(node.u.node_index, index);
       break;
     }
     case kInput:
       break;  // There will be no dependencies.
     default:
       KALDI_ERR << "Invalid node type";
   }
 
   int32 num_dependencies = input_cindexes.size();
   // this "reserve" statement is to make sure the reference
   // we declare below does not become invalid in the loop below
   // (the call to graph_->GetCindexId() could add up to
   // num_dependencies elements to the graph_->dependencies array
   // and we want to avoid allocation).
   // the RoundUpToNearestPowerOfTwo is for efficiency, to
   // avoid too-frequent resizes.
   graph_->dependencies.reserve(RoundUpToNearestPowerOfTwo(
       graph_->dependencies.size() +  num_dependencies));
   std::vector<int32> &this_dep = graph_->dependencies[cindex_id];
 
   this_dep.resize(num_dependencies);
   for (size_t i = 0; i < num_dependencies; i++) {
     bool is_input = false, is_new;
     int32 dep_cindex_id = graph_->GetCindexId(input_cindexes[i],
                                               is_input, &is_new);
     this_dep[i] = dep_cindex_id;
     if (is_new) {
       AddCindexId(dep_cindex_id);
       cindex_info_.back().queued = true;
       next_queue_.push_back(dep_cindex_id);
     }
     // we will keep dependent's usable_count_ up to date below
   }
   // remove duplicates of dependencies.
   SortAndUniq(&this_dep);
   // set up the "depend_on_this_" array.
   std::vector<int32>::const_iterator iter = this_dep.begin(),
       end = this_dep.end();
 
   // Populate the "depend_on_this_" array, and append the
   // usable_count_ of things we depend on (see the definition
   // of this quantity next to where it is declared).
   // Note: before calling AddDependencies() we verified the following:
   //  computable_info_[cindex_id] == kUnknown
   // and
   //  usable_count_[cindex_id] != 0
   // which ensures that the conditions to increment the dependency's
   // usable_count_ are satisfied.
   for (; iter != end; ++iter) {
     int32 dep_cindex_id = *iter;
     depend_on_this_[dep_cindex_id].push_back(cindex_id);
     IncrementUsableCount(dep_cindex_id);
   }
 }

◆ AddInputs()

void AddInputs ( )

private

Definition at line 254 of file nnet-computation-graph.cc.

References rnnlm::i, ComputationGraph::is_input, rnnlm::j, KALDI_ASSERT, KALDI_ERR, kaldi::nnet3::kComponent, kaldi::nnet3::kInput, and rnnlm::n.

Referenced by ComputationGraphBuilder::Compute().

                                         {
   int32 num_added = 0;
   for (int32 i = 0; i < request_->inputs.size(); i++) {
     int32 n = nnet_.GetNodeIndex(request_->inputs[i].name);
     if (n == -1)
       KALDI_ERR << "Network has no input with name "
                 << request_->inputs[i].name;
     NodeType t = nnet_.GetNode(n).node_type;
     KALDI_ASSERT((t == kInput || t == kComponent) &&
                  "Inputs to graph only allowed for Input and Component nodes.");
 
     for (int32 j = 0; j < request_->inputs[i].indexes.size(); j++) {
       Cindex cindex(n, request_->inputs[i].indexes[j]);
       bool is_input = true, is_new;
       int32 cindex_id = graph_->GetCindexId(cindex, is_input, &is_new);
       KALDI_ASSERT(is_new && "Input index seems to be listed more than once");
       AddCindexId(cindex_id);
       cindex_info_.back().computable = kComputable;
       num_added++;
     }
   }
   KALDI_ASSERT(num_added > 0 && "AddInputToGraph: nothing to add.");
 }

◆ AddOutputs()

void AddOutputs ( )

private

Definition at line 278 of file nnet-computation-graph.cc.

References rnnlm::i, ComputationGraph::is_input, rnnlm::j, KALDI_ASSERT, KALDI_ERR, and rnnlm::n.

Referenced by ComputationGraphBuilder::Compute().

                                          {
   int32 num_added = 0;
   for (int32 i = 0; i < request_->outputs.size(); i++) {
     int32 n = nnet_.GetNodeIndex(request_->outputs[i].name);
     if (n == -1)
       KALDI_ERR << "Network has no output with name "
                 << request_->outputs[i].name;
     for (int32 j = 0; j < request_->outputs[i].indexes.size(); j++) {
       Cindex cindex(n, request_->outputs[i].indexes[j]);
       bool is_input = false, is_new;
       int32 cindex_id = graph_->GetCindexId(cindex, is_input, &is_new);
       KALDI_ASSERT(is_new && "Output index seems to be listed more than once");
       AddCindexId(cindex_id);
       cindex_info_.back().usable_count = 1;
       cindex_info_.back().queued = true;
       next_queue_.push_back(cindex_id);
       num_added++;
     }
   }
   if (num_added == 0) {
     KALDI_ERR << "Cannot process computation request with no outputs";
   }
   current_distance_ = 0;
   KALDI_ASSERT(current_queue_.empty());
   current_queue_.swap(next_queue_);
 }

◆ AllOutputsAreComputable()

bool AllOutputsAreComputable ( ) const

Definition at line 305 of file nnet-computation-graph.cc.

Referenced by Compiler::CreateComputation().

                                                             {
   auto iter = cindex_info_.begin(),
       end = cindex_info_.end();
   for (int32 cindex_id = 0; iter != end; ++iter, ++cindex_id) {
     if (iter->computable != kComputable) {
       int32 network_node = graph_->cindexes[cindex_id].first;
       if (nnet_.IsOutputNode(network_node))
         return false;
     }
   }
   return true;
 }

◆ BuildGraphOneIter()

void BuildGraphOneIter ( )

private

Definition at line 896 of file nnet-computation-graph.cc.

References ComputationGraphBuilder::AddDependencies(), ComputationGraphBuilder::cindex_info_, ComputationGraphBuilder::current_distance_, ComputationGraphBuilder::current_queue_, ComputationGraphBuilder::kUnknown, ComputationGraphBuilder::next_queue_, and ComputationGraphBuilder::UpdateComputableInfo().

Referenced by ComputationGraphBuilder::Compute().

                                                 {
   while (!current_queue_.empty()) {
     int32 cindex_id = current_queue_.back();
     current_queue_.pop_back();
     cindex_info_[cindex_id].queued = false;
     if (!cindex_info_[cindex_id].dependencies_computed &&
         cindex_info_[cindex_id].usable_count != 0) {
       cindex_info_[cindex_id].dependencies_computed = true;
       AddDependencies(cindex_id);
       // Add to the queue so we can check whether it's computable.
       if (!cindex_info_[cindex_id].queued) {
         cindex_info_[cindex_id].queued = true;
         next_queue_.push_back(cindex_id);
       }
     } else if (cindex_info_[cindex_id].computable == kUnknown) {
       UpdateComputableInfo(cindex_id);
     }
   }
   current_queue_.swap(next_queue_);  // now next_queue_ will be empty.
   current_distance_++;
 }

◆ Check()

void Check ( int32 start_cindex_id ) const

private

Definition at line 496 of file nnet-computation-graph.cc.

References ComputationGraphBuilder::cindex_info_, ComputationGraph::cindexes, ComputationGraphBuilder::ComputeComputableInfo(), count, ComputationGraphBuilder::current_queue_, ComputationGraphBuilder::depend_on_this_, ComputationGraph::dependencies, ComputationGraphBuilder::graph_, Nnet::IsOutputNode(), kaldi::IsSortedAndUniq(), rnnlm::j, KALDI_ASSERT, KALDI_ERR, ComputationGraphBuilder::kNotComputable, ComputationGraphBuilder::kUnknown, ComputationGraphBuilder::nnet_, and kaldi::RandInt().

Referenced by ComputationGraphBuilder::Compute().

                                                                {
   int32 num_cindex_ids = graph_->cindexes.size();
   for (int32 cindex_id = start_cindex_id; cindex_id < num_cindex_ids;
        cindex_id += 1 + RandInt(0, num_cindex_ids / 100)) {
     { // check depend_on_this.
       std::vector<int32> depend_on_this = depend_on_this_[cindex_id];
       int32 size = depend_on_this.size();
       std::sort(depend_on_this.begin(), depend_on_this.end());
       KALDI_ASSERT(IsSortedAndUniq(depend_on_this));
       for (size_t j = 0; j < size; j++) {
         int32 other_cindex_id = depend_on_this[j];
         // make sure appears in appropriate dependencies array.
         const std::vector<int32> &dep = graph_->dependencies[other_cindex_id];
         KALDI_ASSERT(std::count(dep.begin(), dep.end(), cindex_id) == 1);
       }
     }
     if (cindex_info_[cindex_id].dependencies_computed) {
       // check dependencies.
       std::vector<int32> dependencies = graph_->dependencies[cindex_id];
       int32 size = dependencies.size();
       std::sort(dependencies.begin(), dependencies.end());
       KALDI_ASSERT(IsSortedAndUniq(dependencies));
       for (size_t j = 0; j < size; j++) {
         int32 dep_cindex_id = dependencies[j];
         if (dep_cindex_id >= start_cindex_id) {
           // make sure appears in appropriate depend_on_this_ array.
           const std::vector<int32> &dep = depend_on_this_[dep_cindex_id];
           KALDI_ASSERT(std::count(dep.begin(), dep.end(), cindex_id) == 1);
         }
       }
     }
 
     {
       // check usable_count_
       int32 node_index = graph_->cindexes[cindex_id].first;
       int32 usable_count = cindex_info_[cindex_id].usable_count,
           usable_count_recomputed = nnet_.IsOutputNode(node_index) ? 1 : 0;
       std::vector<int32> depend_on_this = depend_on_this_[cindex_id];
       int32 size = depend_on_this.size();
       for (size_t j = 0; j < size; j++) {
         int32 other_cindex_id = depend_on_this[j];
         if (cindex_info_[other_cindex_id].usable_count != 0 &&
             cindex_info_[other_cindex_id].computable != kNotComputable)
           usable_count_recomputed++;
       }
       KALDI_ASSERT(usable_count == usable_count_recomputed);
     }
     // check `computable`.
     if (cindex_info_[cindex_id].dependencies_computed) {
       ComputationGraphBuilder::ComputableInfo c =
           ComputeComputableInfo(cindex_id);
       // the status doesn't have to match if the stored info is kUnknown.
       if (c != cindex_info_[cindex_id].computable &&
           cindex_info_[cindex_id].computable != kUnknown) {
         KALDI_ERR << "Mismatch in computable status";
       }
     }
     // check `queued`.
     // note, the following checks might be a bit slow.
     if (RandInt(0, cindex_id) == 0) {
       if (cindex_info_[cindex_id].queued) {
         KALDI_ASSERT(std::count(current_queue_.begin(),
                                 current_queue_.end(),
                                 cindex_id) == 1);
       } else {
         KALDI_ASSERT(std::count(current_queue_.begin(),
                                 current_queue_.end(),
                                 cindex_id) == 0);
       }
     }
   }
 }

◆ Compute()

void Compute ( const ComputationRequest & request )

Definition at line 466 of file nnet-computation-graph.cc.

References ComputationGraphBuilder::AddInputs(), ComputationGraphBuilder::AddOutputs(), ComputationGraphBuilder::BuildGraphOneIter(), ComputationGraphBuilder::Check(), ComputationGraph::cindexes, ComputationGraphBuilder::current_distance_, ComputationGraphBuilder::current_queue_, kaldi::GetVerboseLevel(), ComputationGraphBuilder::graph_, KALDI_ERR, KALDI_VLOG, kaldi::RandInt(), ComputationGraphBuilder::request_, and ComputationGraph::segment_ends.

Referenced by Compiler::CreateComputation(), and kaldi::nnet3::EvaluateComputationRequest().

                                                                        {
   if (request_ != NULL && graph_->segment_ends.empty()) {
     // this check is relevant to multi-segment (i.e. online) computations.
     KALDI_ERR << "You are calling things in the wrong order: should be "
               << "Compute(), Prune(), Compute, Prune(), ...";
   }
   int32 cur_segment_start = graph_->cindexes.size();
   request_ = &request;
   AddInputs();
   AddOutputs();  // sets current_distance_ to 0.
   // max_distance for debugging, to detect infinite recursion.
   int32 max_distance = 10000;
   while (current_distance_ < max_distance) {
     BuildGraphOneIter();
     // only check rarely if we're running at low verbose level.
     if (GetVerboseLevel() >= 3 || RandInt(1,  (current_distance_ + 1)) == 1)
       Check(cur_segment_start);
     if (current_queue_.empty()) // we're done.
       break;
   }
   KALDI_VLOG(6) << "current_distance = " << current_distance_; // TEMP
   if (current_distance_ == max_distance)
     KALDI_ERR << "Loop detected while building computation graph (bad "
               << "network topology?)";
 
   if (RandInt(1, 2 * (graph_->segment_ends.size() + 1)) == 1)
     Check(cur_segment_start);
 }

◆ ComputeComputableInfo()

ComputationGraphBuilder::ComputableInfo ComputeComputableInfo ( int32 cindex_id ) const

private

Definition at line 720 of file nnet-computation-graph.cc.

References ComputationGraphBuilder::cindex_info_, ComputationGraph::cindexes, NetworkNode::component_index, NetworkNode::descriptor, ComputationGraph::GetCindexId(), Nnet::GetComponent(), Nnet::GetNode(), ComputationGraphBuilder::graph_, ComputationGraph::is_input, Component::IsComputable(), Descriptor::IsComputable(), KALDI_ERR, kaldi::nnet3::kComponent, ComputationGraphBuilder::kComputable, kaldi::nnet3::kDescriptor, kaldi::nnet3::kDimRange, kaldi::nnet3::kInput, ComputationGraphBuilder::kNotComputable, ComputationGraphBuilder::kUnknown, ComputationRequest::misc_info, ComputationGraphBuilder::nnet_, NetworkNode::node_index, NetworkNode::node_type, ComputationGraphBuilder::request_, and NetworkNode::u.

Referenced by ComputationGraphBuilder::Check(), and ComputationGraphBuilder::UpdateComputableInfo().

           {
   const Cindex &cindex = graph_->cindexes[cindex_id];
   int32 node_id = cindex.first;
   const Index &index = cindex.second;
   const NetworkNode &node = nnet_.GetNode(node_id);
   switch (node.node_type) {
     case kDescriptor: {
       const Descriptor &desc = node.descriptor;
       {
         CindexSet cindex_set(*graph_, cindex_info_, false);
         if (desc.IsComputable(index, cindex_set, NULL)) {
           // it's computable even without counting kUnknown and kWillNotCompute
           // inputs as computable [treat_unknown_as_computable = false] ->
           // definitely computable.
           return kComputable;
         }
       }
       CindexSet cindex_set2(*graph_, cindex_info_, true);
       if (!desc.IsComputable(index, cindex_set2, NULL)) {
         // it's not computable even when counting kUnknown
         // inputs as computable [treat_unknown_as_computable = true] ->
         // definitely not computable.
         return kNotComputable;
       }
       return kUnknown;
     }
     case kComponent: {
       const Component *c = nnet_.GetComponent(node.u.component_index);
       const int32 input_node_id = node_id - 1;
       {
         IndexSet index_set(*graph_, cindex_info_, input_node_id, false);
         if (c->IsComputable(request_->misc_info, index, index_set, NULL)) {
           // it's computable even without counting kUnknown
           // inputs as computable [treat_unknown_as_computable = false] ->
           // definitely computable.
           return kComputable;
         }
       }
       IndexSet index_set2(*graph_, cindex_info_, input_node_id, true);
       if (!c->IsComputable(request_->misc_info, index, index_set2, NULL)) {
         // it's not computable even when counting kUnknown inputs as computable
         // [treat_unknown_as_computable = true] -> definitely not computable.
         return kNotComputable;
       }
       return kUnknown;
     }
     case kDimRange: {
       Cindex input_cindex(node.u.node_index, index);
       int32 input_cindex_id = graph_->GetCindexId(input_cindex);
       if (input_cindex_id != -1)
         return cindex_info_[input_cindex_id].computable;
       else
         return kUnknown;
     }
     case kInput: {
       // cindexes for input nodes that are part of the computation request will
       // have graph_->is_input[cindex_id] == true; others will have
       // graph_->is_input[cindex_id] == true.
       return graph_->is_input[cindex_id] ? kComputable : kNotComputable;
     }
     default:
       KALDI_ERR << "Invalid node type.";
       return kUnknown;  // suppress compiler warning.
   }
 }

◆ ComputeRequiredArray()

void ComputeRequiredArray	(	int32	start_cindex_id,
		std::vector< bool > *	required
	)		const

private

Definition at line 918 of file nnet-computation-graph.cc.

References ComputationGraphBuilder::cindex_info_, ComputationGraph::cindexes, rnnlm::d, ComputationGraph::dependencies, ComputationGraphBuilder::graph_, Nnet::IsOutputNode(), KALDI_ASSERT, rnnlm::n, ComputationGraphBuilder::nnet_, and Nnet::NumNodes().

Referenced by ComputationGraphBuilder::Prune().

                                      {
 
   int32 num_cindex_ids = graph_->cindexes.size();
   KALDI_ASSERT(num_cindex_ids >= start_cindex_id);
   KALDI_ASSERT(cindex_info_.size() == num_cindex_ids);
   required->clear();
   required->resize(num_cindex_ids - start_cindex_id, false);
 
   // would be bool, but indexing c++ bool may be slow.
   std::vector<char> is_output_node(nnet_.NumNodes());
   for (int32 n = 0; n < nnet_.NumNodes(); n++)
     is_output_node[n] = (char)(nnet_.IsOutputNode(n) ? 1 : 0);
 
   std::vector<int32> queue;
   for (int32 c = start_cindex_id; c < num_cindex_ids; c++) {
     // First put the output cindex_ids into the queue.
     int32 node_id = graph_->cindexes[c].first;
     if (is_output_node[node_id]) {
       (*required)[c - start_cindex_id] = true;
       queue.push_back(c);
     }
   }
   while (!queue.empty()) {
     int32 c = queue.back();
     queue.pop_back();
     const std::vector<int32> &dependencies = graph_->dependencies[c];
     std::vector<int32>::const_iterator iter = dependencies.begin(),
         end = dependencies.end();
     for (; iter != end; ++iter) {
       int32 d = *iter;
       if (d >= start_cindex_id && !(*required)[d - start_cindex_id]){
         (*required)[d - start_cindex_id] = true;
         queue.push_back(d);
       }
     }
   }
   // just check that we don't have any cindex_ids which are required but have
   // usable_count_ == 0; this would indicate a bug somewhere.
   for (int32 c = start_cindex_id; c < num_cindex_ids; c++)
     KALDI_ASSERT(!((*required)[c - start_cindex_id] &&
                    (cindex_info_[c].usable_count == 0)));
 
 }

◆ DecrementUsableCount()

void DecrementUsableCount ( int32 cindex_id )

private

Definition at line 881 of file nnet-computation-graph.cc.

References ComputationGraphBuilder::cindex_info_, ComputationGraph::dependencies, ComputationGraphBuilder::graph_, KALDI_PARANOID_ASSERT, and ComputationGraphBuilder::kNotComputable.

Referenced by ComputationGraphBuilder::UpdateComputableInfo().

                                                                   {
   KALDI_PARANOID_ASSERT(cindex_info_[cindex_id].usable_count > 0);
   if (--cindex_info_[cindex_id].usable_count == 0 &&
       cindex_info_[cindex_id].computable != kNotComputable) {
     std::vector<int32>::const_iterator
         iter = graph_->dependencies[cindex_id].begin(),
         end = graph_->dependencies[cindex_id].end();
     for (; iter != end; ++iter) {
       int32 dep_cindex_id = *iter;
       DecrementUsableCount(dep_cindex_id);
     }
   }
 }

◆ ExplainWhyAllOutputsNotComputable()

void ExplainWhyAllOutputsNotComputable ( ) const

Definition at line 334 of file nnet-computation-graph.cc.

References rnnlm::i, KALDI_ASSERT, and KALDI_LOG.

Referenced by Compiler::CreateComputation().

                                                                       {
   std::vector<int32> outputs_not_computable;
   int32 num_outputs_total = 0;
 
   std::vector<Cindex>::const_iterator iter = graph_->cindexes.begin(),
       end = graph_->cindexes.end();
   for (int32 cindex_id = 0; iter != end; ++iter,++cindex_id) {
     int32 network_node = iter->first;
     if (nnet_.IsOutputNode(network_node)) {
       num_outputs_total++;
       if (cindex_info_[cindex_id].computable != kComputable)
         outputs_not_computable.push_back(cindex_id);
     }
   }
   KALDI_ASSERT(!outputs_not_computable.empty() &&
                "You called this function when everything was computable.");
   int32 num_print = 10, num_not_computable = outputs_not_computable.size();
   KALDI_LOG << num_not_computable << " output cindexes out of "
             << num_outputs_total << " were not computable.";
   std::ostringstream os;
   request_->Print(os);
   KALDI_LOG << "Computation request was: " << os.str();
   if (num_not_computable > num_print)
     KALDI_LOG << "Printing the reasons for " << num_print << " of these.";
   for (int32 i = 0; i < num_not_computable && i < num_print; i++)
     ExplainWhyNotComputable(outputs_not_computable[i]);
 }

◆ ExplainWhyNotComputable()

void ExplainWhyNotComputable ( int32 cindex_id ) const

private

Definition at line 134 of file nnet-computation-graph.cc.

References ComputationGraphBuilder::CindexInfo::computable, ComputationGraph::dependencies, KALDI_ASSERT, and KALDI_LOG.

                                  {
   int32 max_lines_print = 100;
   std::deque<int32> cindexes_to_explain;
   std::vector<bool> added_to_queue(graph_->cindexes.size(), false);
   cindexes_to_explain.push_back(first_cindex_id);
   added_to_queue[first_cindex_id] = true;
   KALDI_ASSERT(graph_->cindexes.size() == graph_->dependencies.size());
   std::ostringstream os;
   os << "*** cindex ";
   PrintCindexId(os, first_cindex_id);
   os << " is not computable for the following reason: ***\n";
   for (int32 num_lines_printed = 0;
        num_lines_printed < max_lines_print && !cindexes_to_explain.empty();
        num_lines_printed++) {
     int32 cindex_id = cindexes_to_explain.front();
     cindexes_to_explain.pop_front();
     KALDI_ASSERT(static_cast<size_t>(cindex_id) < graph_->cindexes.size());
     PrintCindexId(os, cindex_id);
     os << " is " << cindex_info_[cindex_id].computable << ", dependencies: ";
     const std::vector<int32> dependencies = graph_->dependencies[cindex_id];
     std::vector<int32>::const_iterator iter = dependencies.begin(),
         end = dependencies.end();
     for (; iter != end; iter++) {
       int32 dep_cindex_id = *iter;
       PrintCindexId(os, dep_cindex_id);
       const CindexInfo &dep_info = cindex_info_[dep_cindex_id];
       os << '[' << dep_info.computable << ']';
       if (dep_info.computable != kComputable && !added_to_queue[dep_cindex_id]) {
         added_to_queue[dep_cindex_id] = true;
         cindexes_to_explain.push_back(dep_cindex_id);
       }
       if (iter+2 != end)
         os << ", ";
     }
     os << "\n";
   }
   os << "\n";
   KALDI_LOG << os.str();
 }

◆ GetComputableInfo()

void GetComputableInfo ( std::vector< std::vector< bool > > * computable ) const

Definition at line 787 of file nnet-computation-graph.cc.

References ComputationGraphBuilder::cindex_info_, ComputationGraph::cindexes, ComputationGraph::GetCindexId(), Nnet::GetNodeIndex(), ComputationGraphBuilder::graph_, rnnlm::i, IoSpecification::indexes, rnnlm::j, KALDI_ASSERT, ComputationGraphBuilder::kComputable, rnnlm::n, IoSpecification::name, ComputationGraphBuilder::nnet_, ComputationRequest::outputs, and ComputationGraphBuilder::request_.

Referenced by kaldi::nnet3::EvaluateComputationRequest().

                                                    {
   KALDI_ASSERT(!graph_->cindexes.empty() &&
                "You need to call this after Compute()!");
   KALDI_ASSERT(!cindex_info_.empty() &&
                "You need to call this before Prune()!");
   computable->clear();
   computable->resize(request_->outputs.size());
   for (size_t i = 0; i < request_->outputs.size(); i++) {
     const IoSpecification &output = request_->outputs[i];
     int32 n = nnet_.GetNodeIndex(output.name);
     KALDI_ASSERT(n != -1);
     int32 size = output.indexes.size();
     std::vector<bool> &this_vec = (*computable)[i];
     this_vec.resize(size);
     for (size_t j = 0; j < size; j++) {
       Cindex cindex(n, output.indexes[j]);
       int32 cindex_id = graph_->GetCindexId(cindex);
       KALDI_ASSERT(cindex_id != -1);
       this_vec[j] = (cindex_info_[cindex_id].computable == kComputable);
     }
   }
 }

◆ IncrementUsableCount()

void IncrementUsableCount ( int32 cindex_id )

private

Definition at line 859 of file nnet-computation-graph.cc.

References ComputationGraphBuilder::cindex_info_, ComputationGraphBuilder::CindexInfo::computable, ComputationGraph::dependencies, ComputationGraphBuilder::graph_, ComputationGraphBuilder::kNotComputable, ComputationGraphBuilder::kUnknown, ComputationGraphBuilder::next_queue_, ComputationGraphBuilder::CindexInfo::queued, and ComputationGraphBuilder::CindexInfo::usable_count.

Referenced by ComputationGraphBuilder::AddDependencies().

                                                                   {
   CindexInfo &info = cindex_info_[cindex_id];
   if (info.usable_count++ == 0 &&
       info.computable != kNotComputable) {
     std::vector<int32>::const_iterator
         iter = graph_->dependencies[cindex_id].begin(),
         end = graph_->dependencies[cindex_id].end();
     for (; iter != end; ++iter) {
       int32 dep_cindex_id = *iter;
       IncrementUsableCount(dep_cindex_id);
     }
     if (info.computable == kUnknown &&
         !info.queued) {
       // It's become usable, so make sure it's queued to process whether it is
       // computable or not.
       info.queued = true;
       next_queue_.push_back(cindex_id);
     }
   }
 }

◆ PrintCindexId()

void PrintCindexId	(	std::ostream &	os,
		int32	cindex_id
	)		const

private

Definition at line 125 of file nnet-computation-graph.cc.

References KALDI_ASSERT.

                                                                    {
   KALDI_ASSERT(static_cast<size_t>(cindex_id) < graph_->cindexes.size());
   const Cindex &cindex = graph_->cindexes[cindex_id];
   const std::string &node_name = nnet_.GetNodeName(cindex.first);
   os << node_name << '(' << cindex.second.n << ", " << cindex.second.t
      << ", " << cindex.second.x << ')';
 }

◆ Prune()

void Prune ( )

Definition at line 569 of file nnet-computation-graph.cc.

References ComputationGraphBuilder::cindex_info_, ComputationGraph::cindexes, ComputationGraphBuilder::ComputeRequiredArray(), ComputationGraphBuilder::depend_on_this_, ComputationGraphBuilder::graph_, rnnlm::i, ComputationGraph::is_input, KALDI_ASSERT, ComputationGraphBuilder::kComputable, ComputationGraphBuilder::PruneDependencies(), ComputationGraph::Renumber(), and ComputationGraph::segment_ends.

Referenced by Compiler::CreateComputation().

                                     {
   // Since Prune() is called for each segment in turn [note: there
   // will be only 1 segment in the normal non-online case], we
   // only prune for the current, just-added segment.
   int32 start_cindex_id = (graph_->segment_ends.empty() ? 0 :
                            graph_->segment_ends.back());
   int32 num_cindex_ids = graph_->cindexes.size();
   // Prune the dependencies to just those that are used (to remove
   // optional dependencies that don't end up getting used).
 
   for (int32 cindex_id = start_cindex_id;
        cindex_id < num_cindex_ids; cindex_id++)
     PruneDependencies(cindex_id);
   // the following clears the elements of depend_on_this from start_cindex_id to
   // num_cindex_ids - 1, without touching the entire array.
   depend_on_this_.resize(start_cindex_id);
   depend_on_this_.resize(num_cindex_ids);
   std::vector<bool> required;
   ComputeRequiredArray(start_cindex_id, &required);
 
   std::vector<bool> keep(num_cindex_ids - start_cindex_id, false);
   for (int32 c = start_cindex_id; c < num_cindex_ids; c++) {
     if (required[c - start_cindex_id] || graph_->is_input[c]) {
       KALDI_ASSERT(cindex_info_[c].computable == kComputable &&
                    "You are calling Prune when not everything is computable.");
       keep[c - start_cindex_id] = true;
     }
   }
   graph_->Renumber(start_cindex_id, keep);
   // We also need to renumber cindex_info_ b,
   // graph_->Renumber doesn't do for us, but we can make some shortcuts.  We set
   // all computable_info_ to kComputable because actually it all was kComputable
   // (we checked when deciding what to keep); and we set the usable_count_ to 1
   // for all the cindex_ids we just added...  this is not 100% accurate
   // according to the way we defined usable_count_, but it prevents additional
   // computation since it is > 0 (notice that IncrementUsableCount and
   // DecrementUsableCount may do some work when the usable_count goes to zero or
   // from zero.  Anyway, the usable-count for these cindex_ids for those "older
   // segments" is not critical.  [this information only gets used if we process
   // additional segments as part of the compilation of an online computation.]
   int32 new_num_cindex_ids = graph_->cindexes.size();
   cindex_info_.resize(start_cindex_id);
   cindex_info_.resize(new_num_cindex_ids);
   for (int32 i = start_cindex_id; i < new_num_cindex_ids; i++) {
     cindex_info_[i].computable = kComputable;
     cindex_info_[i].usable_count = 1;
   }
   // depend_on_this_ is a vector of vectors-- keeping track of the reverse of
   // the dependencies-- and I believe we won't be needing this information any
   // more past this point.
   depend_on_this_.resize(start_cindex_id);
   depend_on_this_.resize(new_num_cindex_ids);
 
   graph_->segment_ends.push_back(new_num_cindex_ids);
 }

◆ PruneDependencies()

void PruneDependencies ( int32 cindex_id )

private

Definition at line 367 of file nnet-computation-graph.cc.

References NetworkNode::component_index, ComputationGraphBuilder::CindexInfo::computable, ComputationGraph::dependencies, NetworkNode::descriptor, rnnlm::i, Component::IsComputable(), Descriptor::IsComputable(), KALDI_ASSERT, KALDI_ERR, kaldi::nnet3::kComponent, kaldi::nnet3::kDescriptor, kaldi::nnet3::kDimRange, kaldi::nnet3::kInput, NetworkNode::node_type, kaldi::SortAndUniq(), NetworkNode::u, and ComputationGraphBuilder::CindexInfo::usable_count.

Referenced by ComputationGraphBuilder::Prune().

                                                                {
   const CindexInfo &info = cindex_info_[cindex_id];
   // by the time this is called, there should be no cindexes with unknown state
   // that are usable.
   KALDI_ASSERT(!(info.computable == kUnknown && info.usable_count != 0));
   if (info.computable == kNotComputable || info.usable_count == 0) {
     // if something is not computable or is not usable, there is no point
     // keeping around its dependencies.
     graph_->dependencies[cindex_id].clear();
     return;
   }
   KALDI_ASSERT(info.computable == kComputable);
   const Cindex &cindex = graph_->cindexes[cindex_id];
   int32 node_id = cindex.first;
   const Index &index = cindex.second;
   const NetworkNode &node = nnet_.GetNode(node_id);
 
   std::vector<int32> &dependencies = graph_->dependencies[cindex_id];
   std::sort(dependencies.begin(), dependencies.end());
   std::vector<int32> used_cindex_ids;
 
   switch (node.node_type) {
     case kDescriptor: {
       const Descriptor &desc = node.descriptor;
       bool dont_care = false;  // there should be no kUnknown, and we check this
       CindexSet cindex_set(*graph_, cindex_info_, dont_care);
       std::vector<Cindex> used_cindexes;
       bool ans = desc.IsComputable(index, cindex_set, &used_cindexes);
       // If the next assert fails it could be a failure in the assumption that
       // making more inputs available will never change something from not being
       // computable to being computable; or it could be a bug elsewhere.
       KALDI_ASSERT(ans);
       size_t size = used_cindexes.size();
       used_cindex_ids.resize(size);
       for (size_t i = 0; i < size; i++) {
         int32 dep_cindex_id = graph_->GetCindexId(used_cindexes[i]);
         KALDI_ASSERT(dep_cindex_id != -1);
         used_cindex_ids[i] = dep_cindex_id;
         KALDI_ASSERT(std::binary_search(dependencies.begin(),
                                         dependencies.end(),
                                         dep_cindex_id));
       }
       break;
     }
     case kComponent: {
       const Component *c = nnet_.GetComponent(node.u.component_index);
       bool dont_care = false;  // there should be no kUnknown, and we check this
       // In the line below, node_id - 1 is the index of the component-input
       // node-- the descriptor at the input to the component.  We are interested
       // in the set of inputs to the component that are computable.
       IndexSet index_set(*graph_, cindex_info_, node_id - 1, dont_care);
       std::vector<Index> used_indexes;
       bool ans = c->IsComputable(request_->misc_info, index, index_set,
                                  &used_indexes);
       // If the next assert fails it could be a failure in the assumption that
       // making more inputs available will never change something from not being
       // computable to being computable; or it could be a bug elsewhere.
       KALDI_ASSERT(ans);
       size_t size = used_indexes.size();
       used_cindex_ids.resize(size);
       for (size_t i = 0; i < size; i++) {
         Cindex dep_cindex(node_id - 1, used_indexes[i]);
         int32 dep_cindex_id = graph_->GetCindexId(dep_cindex);
         KALDI_ASSERT(dep_cindex_id != -1);
         used_cindex_ids[i] = dep_cindex_id;
         KALDI_ASSERT(std::binary_search(dependencies.begin(),
                                         dependencies.end(),
                                         dep_cindex_id));
       }
       break;
     }
     case kDimRange:
       KALDI_ASSERT(dependencies.size() == 1);
       // there should be exactly one dependency and it is required, not
       // optional, so there is nothing to do here.  Return.
       return;
     case kInput:
       KALDI_ASSERT(dependencies.empty());
       // there is nothing to do; return.
       return;
     default:
       KALDI_ERR << "Invalid node type";
   }
   SortAndUniq(&used_cindex_ids);
 
   // the next statement modifies the graph.
   dependencies.swap(used_cindex_ids);
 }

◆ SetAsWillNotCompute()

void SetAsWillNotCompute ( int32 cindex_id )

private

◆ UpdateComputableInfo()

void UpdateComputableInfo ( int32 cindex_id )

private

Definition at line 812 of file nnet-computation-graph.cc.

References ComputationGraphBuilder::cindex_info_, ComputationGraphBuilder::ComputeComputableInfo(), ComputationGraphBuilder::DecrementUsableCount(), ComputationGraphBuilder::depend_on_this_, ComputationGraph::dependencies, ComputationGraphBuilder::graph_, KALDI_ASSERT, ComputationGraphBuilder::kNotComputable, ComputationGraphBuilder::kUnknown, and ComputationGraphBuilder::next_queue_.

Referenced by ComputationGraphBuilder::BuildGraphOneIter().

                                                                   {
   // if the current computable_info_ for cindex_id value is not kUnknown, this
   // cindex_id should not have been in the queue.
   KALDI_ASSERT(static_cast<size_t>(cindex_id) < cindex_info_.size());
 
   // We don't need to update the computable info of this node since it's
   // not usable (i.e. not currently reachable from any node that is not
   // kNotComputable).
   if (cindex_info_[cindex_id].usable_count == 0)
     return;
 
   ComputableInfo &output = cindex_info_[cindex_id].computable;
   KALDI_ASSERT(output == kUnknown);
 
   output = ComputeComputableInfo(cindex_id);
 
   if (output != kUnknown) {
     // The computable status of cindexes that depend on this cindex and whose
     // status is currently kUnknown might now change, so if they are not in the
     // computable queue, put them there.
     std::vector<int32>::const_iterator iter = depend_on_this_[cindex_id].begin(),
         end = depend_on_this_[cindex_id].end();
     for (; iter != end; ++iter) {
       int32 other_cindex_id = *iter;
       if (cindex_info_[other_cindex_id].computable == kUnknown &&
           !cindex_info_[other_cindex_id].queued) {
         cindex_info_[other_cindex_id].queued = true;
         next_queue_.push_back(other_cindex_id);
       }
     }
     if (output == kNotComputable && cindex_info_[cindex_id].usable_count != 0) {
       // If we have just changed the computable state from kUnknown to
       // kNotComputable, then given the way the usable_count is defined (see
       // the declaration), this means that we must decrement the
       // usable_count_ of all cindex_ids that we depend on.
       std::vector<int32>::const_iterator
           iter = graph_->dependencies[cindex_id].begin(),
           end = graph_->dependencies[cindex_id].end();
       for (; iter != end; ++iter) {
         int32 dep_cindex_id = *iter;
         DecrementUsableCount(dep_cindex_id);
       }
     }
   }
 }

Member Data Documentation

◆ cindex_info_

std::vector<CindexInfo> cindex_info_

private

Definition at line 279 of file nnet-computation-graph.h.

Referenced by ComputationGraphBuilder::AddDependencies(), ComputationGraphBuilder::BuildGraphOneIter(), ComputationGraphBuilder::Check(), ComputationGraphBuilder::ComputeComputableInfo(), ComputationGraphBuilder::ComputeRequiredArray(), ComputationGraphBuilder::DecrementUsableCount(), ComputationGraphBuilder::GetComputableInfo(), ComputationGraphBuilder::IncrementUsableCount(), ComputationGraphBuilder::Prune(), and ComputationGraphBuilder::UpdateComputableInfo().

◆ current_distance_

int32 current_distance_

private

Definition at line 283 of file nnet-computation-graph.h.

Referenced by ComputationGraphBuilder::BuildGraphOneIter(), and ComputationGraphBuilder::Compute().

◆ current_queue_

std::vector<int32> current_queue_

private

Definition at line 286 of file nnet-computation-graph.h.

Referenced by ComputationGraphBuilder::BuildGraphOneIter(), ComputationGraphBuilder::Check(), and ComputationGraphBuilder::Compute().

◆ depend_on_this_

std::vector<std::vector<int32> > depend_on_this_

private

Definition at line 275 of file nnet-computation-graph.h.

Referenced by ComputationGraphBuilder::AddDependencies(), ComputationGraphBuilder::Check(), ComputationGraphBuilder::Prune(), and ComputationGraphBuilder::UpdateComputableInfo().

◆ graph_

ComputationGraph* graph_

private

Definition at line 271 of file nnet-computation-graph.h.

◆ next_queue_

std::vector<int32> next_queue_

private

Definition at line 289 of file nnet-computation-graph.h.

Referenced by ComputationGraphBuilder::AddDependencies(), ComputationGraphBuilder::BuildGraphOneIter(), ComputationGraphBuilder::IncrementUsableCount(), and ComputationGraphBuilder::UpdateComputableInfo().

◆ nnet_

const Nnet& nnet_

private

Definition at line 269 of file nnet-computation-graph.h.

Referenced by ComputationGraphBuilder::AddDependencies(), ComputationGraphBuilder::Check(), ComputationGraphBuilder::ComputeComputableInfo(), ComputationGraphBuilder::ComputeRequiredArray(), and ComputationGraphBuilder::GetComputableInfo().

◆ request_

const ComputationRequest* request_

private

Definition at line 270 of file nnet-computation-graph.h.

Referenced by ComputationGraphBuilder::AddDependencies(), ComputationGraphBuilder::Compute(), ComputationGraphBuilder::ComputeComputableInfo(), and ComputationGraphBuilder::GetComputableInfo().

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

nnet3/nnet-computation-graph.h
nnet3/nnet-computation-graph.cc

Classes

Public Types

Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

Member Enumeration Documentation

◆ ComputableInfo

Constructor & Destructor Documentation

◆ ComputationGraphBuilder()

Member Function Documentation

◆ AddCindexId()

◆ AddDependencies()

◆ AddInputs()

◆ AddOutputs()

◆ AllOutputsAreComputable()

◆ BuildGraphOneIter()

◆ Check()

◆ Compute()

◆ ComputeComputableInfo()

◆ ComputeRequiredArray()

◆ DecrementUsableCount()

◆ ExplainWhyAllOutputsNotComputable()

◆ ExplainWhyNotComputable()

◆ GetComputableInfo()

◆ IncrementUsableCount()

◆ PrintCindexId()

◆ Prune()

◆ PruneDependencies()

◆ SetAsWillNotCompute()

◆ UpdateComputableInfo()

Member Data Documentation

◆ cindex_info_

◆ current_distance_

◆ current_queue_

◆ depend_on_this_

◆ graph_

◆ next_queue_

◆ nnet_

◆ request_