All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Modules Pages
ComputationGraphBuilder Class Reference

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

#include <nnet-computation-graph.h>

Collaboration diagram for ComputationGraphBuilder:

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 UpdateAllComputableInfo ()
 
void UpdateComputableInfo (int32 cindex_id)
 
void SetAsWillNotCompute (int32 cindex_id)
 
ComputableInfo ComputeComputableInfo (int32 cindex_id) const
 
void AddCindexId (int32 cindex_id, bool is_input, bool is_output)
 
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 Nnetnnet_
 
const ComputationRequestrequest_
 
ComputationGraphgraph_
 
std::vector< std::vector< int32 > > depend_on_this_
 
std::vector< char > computable_info_
 
std::deque< int32 > computable_queue_
 
std::vector< bool > computable_queued_
 
std::vector< int32 > usable_count_
 
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

Constructor & Destructor Documentation

ComputationGraphBuilder ( const Nnet nnet,
ComputationGraph graph 
)

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

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

454  :
455  nnet_(nnet), request_(NULL), graph_(graph),
456  current_distance_(-1) {
457  KALDI_ASSERT(graph_->cindexes.empty() &&
458  "ComputationGraphBuilder initialized with nonempty graph.");
459 }
std::vector< Cindex > cindexes
The mapping of cindex_id to Cindex.
#define KALDI_ASSERT(cond)
Definition: kaldi-error.h:169

Member Function Documentation

void AddCindexId ( int32  cindex_id,
bool  is_input,
bool  is_output 
)
inlineprivate

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

References ComputationGraphBuilder::computable_info_, ComputationGraphBuilder::computable_queued_, ComputationGraphBuilder::depend_on_this_, KALDI_PARANOID_ASSERT, ComputationGraphBuilder::kComputable, ComputationGraphBuilder::kUnknown, ComputationGraphBuilder::next_queue_, and ComputationGraphBuilder::usable_count_.

Referenced by ComputationGraphBuilder::AddDependencies(), ComputationGraphBuilder::AddInputs(), and ComputationGraphBuilder::AddOutputs().

228  {
229  // If this cindex_id has just now been added to the graph, the following
230  // assert should succeed.
231  KALDI_PARANOID_ASSERT(cindex_id == computable_queued_.size() &&
232  cindex_id == computable_info_.size() &&
233  cindex_id == depend_on_this_.size() &&
234  cindex_id == usable_count_.size());
235  if (is_input) {
236  computable_info_.push_back(kComputable);
237  computable_queued_.push_back(false);
238  } else {
239  computable_info_.push_back(kUnknown);
240  // add to the queue of things for which we need to compute their computable
241  // status.
242  computable_queued_.push_back(false);
243  next_queue_.push_back(cindex_id);
244  }
245  depend_on_this_.push_back(std::vector<int32>());
246  usable_count_.push_back(is_output ? 1 : 0);
247 }
std::vector< std::vector< int32 > > depend_on_this_
#define KALDI_PARANOID_ASSERT(cond)
Definition: kaldi-error.h:182
void AddDependencies ( int32  cindex_id)
private

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

References ComputationGraphBuilder::AddCindexId(), ComputationGraph::cindexes, NetworkNode::component_index, ComputationGraphBuilder::computable_info_, ComputationGraphBuilder::computable_queue_, ComputationGraphBuilder::computable_queued_, ComputationGraphBuilder::depend_on_this_, ComputationGraph::dependencies, NetworkNode::descriptor, ComputationGraph::GetCindexId(), Nnet::GetComponent(), Descriptor::GetDependencies(), Component::GetInputIndexes(), Nnet::GetNode(), ComputationGraphBuilder::graph_, rnnlm::i, ComputationGraphBuilder::IncrementUsableCount(), KALDI_ASSERT, KALDI_ERR, kaldi::nnet3::kComponent, kaldi::nnet3::kDescriptor, kaldi::nnet3::kDimRange, kaldi::nnet3::kInput, ComputationGraphBuilder::kUnknown, ComputationRequest::misc_info, ComputationGraphBuilder::nnet_, NetworkNode::node_index, NetworkNode::node_type, ComputationGraphBuilder::request_, kaldi::RoundUpToNearestPowerOfTwo(), kaldi::SortAndUniq(), and NetworkNode::u.

Referenced by ComputationGraphBuilder::BuildGraphOneIter().

635  {
636  if (static_cast<int32>(graph_->dependencies.size()) <= cindex_id) {
637  graph_->dependencies.resize(2 * cindex_id + 1);
638  }
639 
640  Cindex cindex = graph_->cindexes[cindex_id];
641 
642  // find the dependencies of this cindex.
643  int32 node_index = cindex.first;
644  const Index &index = cindex.second;
645  const NetworkNode &node = nnet_.GetNode(node_index);
646 
647  std::vector<Cindex> input_cindexes;
648 
649  // the following switch statement sets up "input_cindexes".
650  switch (node.node_type) {
651  case kDescriptor: {
652  // desc describes how this node obtains its input from other nodes.
653  const Descriptor &desc = node.descriptor;
654  desc.GetDependencies(index, &input_cindexes);
655  break;
656  }
657  case kComponent: {
658  int32 c = node.u.component_index;
659  const Component *component = nnet_.GetComponent(c);
660  std::vector<Index> input_indexes;
661  component->GetInputIndexes(request_->misc_info, index,
662  &input_indexes);
663  input_cindexes.resize(input_indexes.size());
664  for (size_t i = 0; i < input_indexes.size(); i++) {
665  input_cindexes[i].first = node_index - 1; // preceding node
666  input_cindexes[i].second = input_indexes[i];
667  }
668  break;
669  }
670  case kDimRange: {
671  input_cindexes.resize(1);
672  input_cindexes[0] = Cindex(node.u.node_index, index);
673  break;
674  }
675  case kInput:
676  break; // There will be no dependencies.
677  default:
678  KALDI_ERR << "Invalid node type";
679  }
680 
681  int32 num_dependencies = input_cindexes.size();
682  // this "reserve" statement is to make sure the reference
683  // we declare below does not become invalid in the loop below
684  // (the call to graph_->GetCindexId() could add up to
685  // num_dependencies elements to the graph_->dependencies array
686  // and we want to avoid allocation).
687  // the RoundUpToNearestPowerOfTwo is for efficiency, to
688  // avoid too-frequent resizes.
690  graph_->dependencies.size() + num_dependencies));
691  std::vector<int32> &this_dep = graph_->dependencies[cindex_id];
692 
693  this_dep.resize(num_dependencies);
694  for (size_t i = 0; i < num_dependencies; i++) {
695  bool is_input = false, is_new;
696  int32 dep_cindex_id = graph_->GetCindexId(input_cindexes[i],
697  is_input, &is_new);
698  this_dep[i] = dep_cindex_id;
699  if (is_new)
700  AddCindexId(dep_cindex_id, false, false);
701  // we will keep dependent's usable_count_ up to date below
702  }
703  // remove duplicates of dependencies.
704  SortAndUniq(&this_dep);
705  // set up the "depend_on_this_" array.
706  std::vector<int32>::const_iterator iter = this_dep.begin(),
707  end = this_dep.end();
708 
709  // Populate the "depend_on_this_" array, and append the
710  // usable_count_ of things we depend on (see the definition
711  // of this quantity next to where it is declared).
712  // Note: before calling AddDependencies() we verified the following:
713  // computable_info_[cindex_id] == kUnknown
714  // and
715  // usable_count_[cindex_id] != 0
716  // which ensures that the conditions to increment the dependency's
717  // usable_count_ are satisfied.
718  for (; iter != end; ++iter) {
719  int32 dep_cindex_id = *iter;
720  depend_on_this_[dep_cindex_id].push_back(cindex_id);
721  IncrementUsableCount(dep_cindex_id);
722  }
723 
724  // Now that we've added the dependencies, we can put this into
725  // the computable_queue_ to assess whether it's computable
726  KALDI_ASSERT(computable_info_[cindex_id] == kUnknown &&
727  !computable_queued_[cindex_id]);
728  // we think it'll be faster in the next line to do push_front instead of
729  // push_back; either one would be correct.
730  computable_queue_.push_front(cindex_id);
731  computable_queued_[cindex_id] = true;
732 }
virtual void GetInputIndexes(const MiscComputationInfo &misc_info, const Index &output_index, std::vector< Index > *desired_indexes) const
This function only does something interesting for non-simple Components.
MiscComputationInfo misc_info
misc_info is for extensibility to things that don't easily fit into the framework.
int32 RoundUpToNearestPowerOfTwo(int32 n)
Definition: kaldi-math.cc:31
void SortAndUniq(std::vector< T > *vec)
Sorts and uniq's (removes duplicates) from a vector.
Definition: stl-utils.h:39
std::pair< int32, Index > Cindex
Definition: nnet-common.h:115
const NetworkNode & GetNode(int32 node) const
returns const reference to a particular numbered network node.
Definition: nnet-nnet.h:146
std::vector< Cindex > cindexes
The mapping of cindex_id to Cindex.
std::vector< std::vector< int32 > > dependencies
dependencies[cindex_id] gives you the list of other cindex_ids that this particular cindex_id directl...
int32 GetCindexId(const Cindex &cindex, bool is_input, bool *is_new)
Maps a Cindex to an integer cindex_id.
std::vector< std::vector< int32 > > depend_on_this_
#define KALDI_ERR
Definition: kaldi-error.h:127
void AddCindexId(int32 cindex_id, bool is_input, bool is_output)
Component * GetComponent(int32 c)
Return component indexed c. Not a copy; not owned by caller.
Definition: nnet-nnet.cc:150
#define KALDI_ASSERT(cond)
Definition: kaldi-error.h:169
void AddInputs ( )
private

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

References ComputationGraphBuilder::AddCindexId(), ComputationGraph::GetCindexId(), Nnet::GetNode(), Nnet::GetNodeIndex(), ComputationGraphBuilder::graph_, rnnlm::i, ComputationRequest::inputs, rnnlm::j, KALDI_ASSERT, KALDI_ERR, kaldi::nnet3::kComponent, kaldi::nnet3::kInput, rnnlm::n, ComputationGraphBuilder::nnet_, NetworkNode::node_type, and ComputationGraphBuilder::request_.

Referenced by ComputationGraphBuilder::Compute().

250  {
251  int32 num_added = 0;
252  for (int32 i = 0; i < request_->inputs.size(); i++) {
253  int32 n = nnet_.GetNodeIndex(request_->inputs[i].name);
254  if (n == -1)
255  KALDI_ERR << "Network has no input with name "
256  << request_->inputs[i].name;
258  KALDI_ASSERT((t == kInput || t == kComponent) &&
259  "Inputs to graph only allowed for Input and Component nodes.");
260 
261  for (int32 j = 0; j < request_->inputs[i].indexes.size(); j++) {
262  Cindex cindex(n, request_->inputs[i].indexes[j]);
263  bool is_input = true, is_new;
264  int32 cindex_id = graph_->GetCindexId(cindex, is_input, &is_new);
265  KALDI_ASSERT(is_new && "Input index seems to be listed more than once");
266  AddCindexId(cindex_id, true, false);
267  num_added++;
268  }
269  }
270  KALDI_ASSERT(num_added > 0 && "AddInputToGraph: nothing to add.");
271 }
std::vector< IoSpecification > inputs
std::pair< int32, Index > Cindex
Definition: nnet-common.h:115
const NetworkNode & GetNode(int32 node) const
returns const reference to a particular numbered network node.
Definition: nnet-nnet.h:146
int32 GetCindexId(const Cindex &cindex, bool is_input, bool *is_new)
Maps a Cindex to an integer cindex_id.
struct rnnlm::@11::@12 n
#define KALDI_ERR
Definition: kaldi-error.h:127
void AddCindexId(int32 cindex_id, bool is_input, bool is_output)
#define KALDI_ASSERT(cond)
Definition: kaldi-error.h:169
int32 GetNodeIndex(const std::string &node_name) const
returns index associated with this node name, or -1 if no such index.
Definition: nnet-nnet.cc:466
void AddOutputs ( )
private

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

References ComputationGraphBuilder::AddCindexId(), ComputationGraphBuilder::current_distance_, ComputationGraphBuilder::current_queue_, ComputationGraph::GetCindexId(), Nnet::GetNodeIndex(), ComputationGraphBuilder::graph_, rnnlm::i, rnnlm::j, KALDI_ASSERT, KALDI_ERR, rnnlm::n, ComputationGraphBuilder::next_queue_, ComputationGraphBuilder::nnet_, ComputationRequest::outputs, and ComputationGraphBuilder::request_.

Referenced by ComputationGraphBuilder::Compute().

273  {
274  int32 num_added = 0;
275  for (int32 i = 0; i < request_->outputs.size(); i++) {
276  int32 n = nnet_.GetNodeIndex(request_->outputs[i].name);
277  if (n == -1)
278  KALDI_ERR << "Network has no output with name "
279  << request_->outputs[i].name;
280  for (int32 j = 0; j < request_->outputs[i].indexes.size(); j++) {
281  Cindex cindex(n, request_->outputs[i].indexes[j]);
282  bool is_input = false, is_new;
283  int32 cindex_id = graph_->GetCindexId(cindex, is_input, &is_new);
284  KALDI_ASSERT(is_new && "Output index seems to be listed more than once");
285  AddCindexId(cindex_id, false, true);
286  num_added++;
287  }
288  }
289  if (num_added == 0) {
290  KALDI_ERR << "Cannot process computation request with no outputs";
291  }
292  current_distance_ = 0;
293  // the calls to AddCindexId in this function will have added to next_queue_.
294  KALDI_ASSERT(current_queue_.empty());
296 }
std::pair< int32, Index > Cindex
Definition: nnet-common.h:115
int32 GetCindexId(const Cindex &cindex, bool is_input, bool *is_new)
Maps a Cindex to an integer cindex_id.
struct rnnlm::@11::@12 n
#define KALDI_ERR
Definition: kaldi-error.h:127
void AddCindexId(int32 cindex_id, bool is_input, bool is_output)
#define KALDI_ASSERT(cond)
Definition: kaldi-error.h:169
std::vector< IoSpecification > outputs
int32 GetNodeIndex(const std::string &node_name) const
returns index associated with this node name, or -1 if no such index.
Definition: nnet-nnet.cc:466
bool AllOutputsAreComputable ( ) const

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

References ComputationGraph::cindexes, ComputationGraphBuilder::computable_info_, ComputationGraphBuilder::graph_, Nnet::IsOutputNode(), ComputationGraphBuilder::kComputable, and ComputationGraphBuilder::nnet_.

Referenced by Compiler::CreateComputation().

298  {
299  char is_computable_char = static_cast<char>(kComputable);
300  std::vector<char>::const_iterator iter = computable_info_.begin(),
301  end = computable_info_.end();
302  for (int32 cindex_id = 0; iter != end; ++iter, ++cindex_id) {
303  if (*iter != is_computable_char) { // is not computable.
304  int32 network_node = graph_->cindexes[cindex_id].first;
305  if (nnet_.IsOutputNode(network_node))
306  return false;
307  }
308  }
309  return true;
310 }
bool IsOutputNode(int32 node) const
Returns true if this is an output node, meaning that it is of type kDescriptor and is not directly fo...
Definition: nnet-nnet.cc:112
std::vector< Cindex > cindexes
The mapping of cindex_id to Cindex.
void BuildGraphOneIter ( )
private

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

References ComputationGraphBuilder::AddDependencies(), ComputationGraphBuilder::computable_info_, ComputationGraphBuilder::current_distance_, ComputationGraphBuilder::current_queue_, KALDI_ASSERT, ComputationGraphBuilder::kUnknown, ComputationGraphBuilder::next_queue_, ComputationGraphBuilder::SetAsWillNotCompute(), and ComputationGraphBuilder::usable_count_.

Referenced by ComputationGraphBuilder::Compute().

923  {
924  while (!current_queue_.empty()) {
925  int32 cindex_id = current_queue_.back();
926  current_queue_.pop_back();
927  KALDI_ASSERT(computable_info_[cindex_id] == kUnknown);
928  if (usable_count_[cindex_id] == 0)
929  SetAsWillNotCompute(cindex_id);
930  else
931  AddDependencies(cindex_id);
932  }
933  current_queue_.swap(next_queue_); // now next_queue_ will be empty.
935 }
#define KALDI_ASSERT(cond)
Definition: kaldi-error.h:169
void Check ( int32  start_cindex_id) const
private

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

References ComputationGraph::cindexes, ComputationGraphBuilder::computable_info_, ComputationGraphBuilder::computable_queue_, ComputationGraphBuilder::computable_queued_, 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::kWillNotCompute, ComputationGraphBuilder::next_queue_, ComputationGraphBuilder::nnet_, kaldi::RandInt(), and ComputationGraphBuilder::usable_count_.

Referenced by ComputationGraphBuilder::Compute().

494  {
495  int32 num_cindex_ids = graph_->cindexes.size();
496  for (int32 cindex_id = start_cindex_id; cindex_id < num_cindex_ids;
497  cindex_id += 1 + RandInt(0, num_cindex_ids / 100)) {
498  { // check depend_on_this.
499  std::vector<int32> depend_on_this = depend_on_this_[cindex_id];
500  int32 size = depend_on_this.size();
501  std::sort(depend_on_this.begin(), depend_on_this.end());
502  KALDI_ASSERT(IsSortedAndUniq(depend_on_this));
503  for (size_t j = 0; j < size; j++) {
504  int32 other_cindex_id = depend_on_this[j];
505  // make sure appears in appropriate dependencies array.
506  const std::vector<int32> &dep = graph_->dependencies[other_cindex_id];
507  KALDI_ASSERT(std::count(dep.begin(), dep.end(), cindex_id) == 1);
508  }
509  }
510  { // check dependencies.
511  std::vector<int32> dependencies = graph_->dependencies[cindex_id];
512  int32 size = dependencies.size();
513  std::sort(dependencies.begin(), dependencies.end());
514  KALDI_ASSERT(IsSortedAndUniq(dependencies));
515  for (size_t j = 0; j < size; j++) {
516  int32 dep_cindex_id = dependencies[j];
517  if (dep_cindex_id >= start_cindex_id) {
518  // make sure appears in appropriate depend_on_this_ array.
519  const std::vector<int32> &dep = depend_on_this_[dep_cindex_id];
520  KALDI_ASSERT(std::count(dep.begin(), dep.end(), cindex_id) == 1);
521  }
522  }
523  }
524 
525  {
526  // check usable_count_
527  int32 node_index = graph_->cindexes[cindex_id].first;
528  int32 usable_count = usable_count_[cindex_id],
529  usable_count_recomputed = nnet_.IsOutputNode(node_index) ? 1 : 0;
530  std::vector<int32> depend_on_this = depend_on_this_[cindex_id];
531  int32 size = depend_on_this.size();
532  for (size_t j = 0; j < size; j++) {
533  int32 other_cindex_id = depend_on_this[j];
534  if (usable_count_[other_cindex_id] != 0 &&
535  computable_info_[other_cindex_id] != kNotComputable)
536  usable_count_recomputed++;
537  }
538  KALDI_ASSERT(usable_count == usable_count_recomputed);
539  }
540  // check computable_info_. note: this will not be accurate
541  // if the cindex_id is still queued to have dependencies added
542  // (in cur_queue_ or next_queue_).
543  if (computable_queue_.empty()) {
545  ComputeComputableInfo(cindex_id);
546  // the status doesn't have to be correct if it's kWillNotCompute,
547  // because these are cindex-ids that we chose not to compute
548  // because we determined they would not be useful, and
549  // ComputeComputableInfo() will never return this value.
550  if (c != computable_info_[cindex_id] &&
551  computable_info_[cindex_id] != kWillNotCompute) {
552  int32 count_cur = std::count(current_queue_.begin(),
553  current_queue_.end(), cindex_id),
554  count_next = std::count(next_queue_.begin(),
555  next_queue_.end(), cindex_id);
556  // if it wasn't queued, then something is wrong.
557  if (count_cur + count_next == 0)
558  KALDI_ERR << "Mismatch in computable status";
559  }
560  }
561  // check computable_queued_.
562  // note, the following checks might be a bit slow.
563  if (computable_queued_[cindex_id]) {
565  computable_queue_.end(),
566  cindex_id) == 1);
567  } else {
569  computable_queue_.end(),
570  cindex_id) == 0);
571  }
572  }
573 }
bool IsOutputNode(int32 node) const
Returns true if this is an output node, meaning that it is of type kDescriptor and is not directly fo...
Definition: nnet-nnet.cc:112
const size_t count
std::vector< Cindex > cindexes
The mapping of cindex_id to Cindex.
std::vector< std::vector< int32 > > dependencies
dependencies[cindex_id] gives you the list of other cindex_ids that this particular cindex_id directl...
std::vector< std::vector< int32 > > depend_on_this_
#define KALDI_ERR
Definition: kaldi-error.h:127
#define KALDI_ASSERT(cond)
Definition: kaldi-error.h:169
ComputableInfo ComputeComputableInfo(int32 cindex_id) const
bool IsSortedAndUniq(const std::vector< T > &vec)
Returns true if the vector is sorted and contains each element only once.
Definition: stl-utils.h:63
int32 RandInt(int32 min_val, int32 max_val, struct RandomState *state)
Definition: kaldi-math.cc:94
void Compute ( const ComputationRequest request)

Definition at line 462 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::RandInt(), ComputationGraphBuilder::request_, ComputationGraph::segment_ends, and ComputationGraphBuilder::UpdateAllComputableInfo().

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

462  {
463  if (request_ != NULL && graph_->segment_ends.empty()) {
464  // this check is relevant to multi-segment (i.e. online) computations.
465  KALDI_ERR << "You are calling things in the wrong order: should be "
466  << "Compute(), Prune(), Compute, Prune(), ...";
467  }
468  int32 cur_segment_start = graph_->cindexes.size();
469  request_ = &request;
470  AddInputs();
471  AddOutputs(); // sets current_distance_ to 0.
472  // max_distance for debugging, to detect infinite recursion.
473  int32 max_distance = 10000;
474  while (current_distance_ < max_distance) {
476  // only check rarely if we're running at low verbose level.
477  if (GetVerboseLevel() >= 3 || RandInt(1, (current_distance_ + 1)) == 1)
478  Check(cur_segment_start);
479  // TODO: come up with a scheme to delay when we call
480  // UpdateAllComputableInfo().
482  if (current_queue_.empty()) // we're done.
483  break;
484  }
485  if (current_distance_ == max_distance)
486  KALDI_ERR << "Loop detected while building computation graph (bad "
487  << "network topology?)";
488 
489  if (RandInt(1, 2 * (graph_->segment_ends.size() + 1)) == 1)
490  Check(cur_segment_start);
491 }
int32 GetVerboseLevel()
Definition: kaldi-error.h:69
std::vector< Cindex > cindexes
The mapping of cindex_id to Cindex.
std::vector< int32 > segment_ends
This variable is only of particular interest in a 'multi-segment' computation, which is used while cr...
#define KALDI_ERR
Definition: kaldi-error.h:127
void Check(int32 start_cindex_id) const
int32 RandInt(int32 min_val, int32 max_val, struct RandomState *state)
Definition: kaldi-math.cc:94
ComputationGraphBuilder::ComputableInfo ComputeComputableInfo ( int32  cindex_id) const
private

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

References ComputationGraph::cindexes, NetworkNode::component_index, ComputationGraphBuilder::computable_info_, 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().

737  {
738  const Cindex &cindex = graph_->cindexes[cindex_id];
739  int32 node_id = cindex.first;
740  const Index &index = cindex.second;
741  const NetworkNode &node = nnet_.GetNode(node_id);
742  switch (node.node_type) {
743  case kDescriptor: {
744  const Descriptor &desc = node.descriptor;
745  {
746  CindexSet cindex_set(*graph_, computable_info_, false);
747  if (desc.IsComputable(index, cindex_set, NULL)) {
748  // it's computable even without counting kUnknown inputs as computable
749  // [treat_unknown_as_computable = false] -> definitely computable.
750  return kComputable;
751  }
752  }
753  CindexSet cindex_set2(*graph_, computable_info_, true);
754  if (!desc.IsComputable(index, cindex_set2, NULL)) {
755  // it's not computable even when counting kUnknown inputs as
756  // computable [treat_unknown_as_computable = true] -> definitely not
757  // computable.
758  return kNotComputable;
759  }
760  return kUnknown;
761  }
762  case kComponent: {
763  const Component *c = nnet_.GetComponent(node.u.component_index);
764  const int32 input_node_id = node_id - 1;
765  {
766  IndexSet index_set(*graph_, computable_info_, input_node_id, false);
767  if (c->IsComputable(request_->misc_info, index, index_set, NULL)) {
768  // it's computable even without counting kUnknown inputs as computable
769  // [treat_unknown_as_computable = false] -> definitely computable.
770  return kComputable;
771  }
772  }
773  IndexSet index_set2(*graph_, computable_info_, input_node_id, true);
774  if (!c->IsComputable(request_->misc_info, index, index_set2, NULL)) {
775  // it's not computable even when counting kUnknown inputs as computable
776  // [treat_unknown_as_computable = true] -> definitely not computable.
777  return kNotComputable;
778  }
779  return kUnknown;
780  }
781  case kDimRange: {
782  Cindex input_cindex(node.u.node_index, index);
783  int32 input_cindex_id = graph_->GetCindexId(input_cindex);
784  if (input_cindex_id != -1)
785  return ComputableInfo(computable_info_[input_cindex_id]);
786  else
787  return kUnknown;
788  }
789  case kInput: {
790  // cindexes for input nodes that are part of the computation request will
791  // have graph_->is_input[cindex_id] == true; others will have
792  // graph_->is_input[cindex_id] == true.
793  return graph_->is_input[cindex_id] ? kComputable : kNotComputable;
794  }
795  default:
796  KALDI_ERR << "Invalid node type.";
797  return kUnknown; // suppress compiler warning.
798  }
799 }
MiscComputationInfo misc_info
misc_info is for extensibility to things that don't easily fit into the framework.
std::pair< int32, Index > Cindex
Definition: nnet-common.h:115
const NetworkNode & GetNode(int32 node) const
returns const reference to a particular numbered network node.
Definition: nnet-nnet.h:146
std::vector< Cindex > cindexes
The mapping of cindex_id to Cindex.
int32 GetCindexId(const Cindex &cindex, bool is_input, bool *is_new)
Maps a Cindex to an integer cindex_id.
std::vector< bool > is_input
For each Cindex this tells us whether it was provided as an input to the network. ...
#define KALDI_ERR
Definition: kaldi-error.h:127
Component * GetComponent(int32 c)
Return component indexed c. Not a copy; not owned by caller.
Definition: nnet-nnet.cc:150
void ComputeRequiredArray ( int32  start_cindex_id,
std::vector< bool > *  required 
) const
private

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

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

Referenced by ComputationGraphBuilder::Prune().

939  {
940 
941  int32 num_cindex_ids = graph_->cindexes.size();
942  KALDI_ASSERT(num_cindex_ids >= start_cindex_id);
943  KALDI_ASSERT(computable_info_.size() == num_cindex_ids);
944  required->clear();
945  required->resize(num_cindex_ids - start_cindex_id, false);
946 
947  // would be bool, but indexing c++ bool may be slow.
948  std::vector<char> is_output_node(nnet_.NumNodes());
949  for (int32 n = 0; n < nnet_.NumNodes(); n++)
950  is_output_node[n] = (char)(nnet_.IsOutputNode(n) ? 1 : 0);
951 
952  std::vector<int32> queue;
953  for (int32 c = start_cindex_id; c < num_cindex_ids; c++) {
954  // First put the output cindex_ids into the queue.
955  int32 node_id = graph_->cindexes[c].first;
956  if (is_output_node[node_id]) {
957  (*required)[c - start_cindex_id] = true;
958  queue.push_back(c);
959  }
960  }
961  while (!queue.empty()) {
962  int32 c = queue.back();
963  queue.pop_back();
964  const std::vector<int32> &dependencies = graph_->dependencies[c];
965  std::vector<int32>::const_iterator iter = dependencies.begin(),
966  end = dependencies.end();
967  for (; iter != end; ++iter) {
968  int32 d = *iter;
969  if (d >= start_cindex_id && !(*required)[d - start_cindex_id]){
970  (*required)[d - start_cindex_id] = true;
971  queue.push_back(d);
972  }
973  }
974  }
975  // just check that we don't have any cindex_ids which are required but have
976  // usable_count_ == 0; this would indicate a bug somewhere.
977  for (int32 c = start_cindex_id; c < num_cindex_ids; c++)
978  KALDI_ASSERT(!((*required)[c - start_cindex_id] &&
979  (usable_count_[c] == 0)));
980 
981 }
bool IsOutputNode(int32 node) const
Returns true if this is an output node, meaning that it is of type kDescriptor and is not directly fo...
Definition: nnet-nnet.cc:112
int32 NumNodes() const
Definition: nnet-nnet.h:126
std::vector< Cindex > cindexes
The mapping of cindex_id to Cindex.
std::vector< std::vector< int32 > > dependencies
dependencies[cindex_id] gives you the list of other cindex_ids that this particular cindex_id directl...
struct rnnlm::@11::@12 n
#define KALDI_ASSERT(cond)
Definition: kaldi-error.h:169
void DecrementUsableCount ( int32  cindex_id)
private

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

References ComputationGraphBuilder::computable_info_, ComputationGraph::dependencies, ComputationGraphBuilder::graph_, KALDI_PARANOID_ASSERT, ComputationGraphBuilder::kNotComputable, and ComputationGraphBuilder::usable_count_.

Referenced by ComputationGraphBuilder::UpdateComputableInfo().

907  {
908  KALDI_PARANOID_ASSERT(static_cast<size_t>(cindex_id)<usable_count_.size());
909  KALDI_PARANOID_ASSERT(usable_count_[cindex_id] > 0);
910  if (--usable_count_[cindex_id] == 0 &&
911  computable_info_[cindex_id] != kNotComputable) {
912  std::vector<int32>::const_iterator
913  iter = graph_->dependencies[cindex_id].begin(),
914  end = graph_->dependencies[cindex_id].end();
915  for (; iter != end; ++iter) {
916  int32 dep_cindex_id = *iter;
917  DecrementUsableCount(dep_cindex_id);
918  }
919  }
920 }
std::vector< std::vector< int32 > > dependencies
dependencies[cindex_id] gives you the list of other cindex_ids that this particular cindex_id directl...
#define KALDI_PARANOID_ASSERT(cond)
Definition: kaldi-error.h:182
void ExplainWhyAllOutputsNotComputable ( ) const

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

References ComputationGraph::cindexes, ComputationGraphBuilder::computable_info_, ComputationGraphBuilder::ExplainWhyNotComputable(), ComputationGraphBuilder::graph_, rnnlm::i, Nnet::IsOutputNode(), KALDI_ASSERT, KALDI_LOG, ComputationGraphBuilder::kComputable, ComputationGraphBuilder::nnet_, ComputationRequest::Print(), and ComputationGraphBuilder::request_.

Referenced by Compiler::CreateComputation().

330  {
331  std::vector<int32> outputs_not_computable;
332  int32 num_outputs_total = 0;
333 
334  std::vector<Cindex>::const_iterator iter = graph_->cindexes.begin(),
335  end = graph_->cindexes.end();
336  for (int32 cindex_id = 0; iter != end; ++iter,++cindex_id) {
337  int32 network_node = iter->first;
338  ComputableInfo c = static_cast<ComputableInfo>(computable_info_[cindex_id]);
339  if (nnet_.IsOutputNode(network_node)) {
340  num_outputs_total++;
341  if (c != kComputable)
342  outputs_not_computable.push_back(cindex_id);
343  }
344  }
345  KALDI_ASSERT(!outputs_not_computable.empty() &&
346  "You called this function when everything was computable.");
347  int32 num_print = 10, num_not_computable = outputs_not_computable.size();
348  KALDI_LOG << num_not_computable << " output cindexes out of "
349  << num_outputs_total << " were not computable.";
350  std::ostringstream os;
351  request_->Print(os);
352  KALDI_LOG << "Computation request was: " << os.str();
353  if (num_not_computable > num_print)
354  KALDI_LOG << "Printing the reasons for " << num_print << " of these.";
355  for (int32 i = 0; i < num_not_computable && i < num_print; i++)
356  ExplainWhyNotComputable(outputs_not_computable[i]);
357 }
bool IsOutputNode(int32 node) const
Returns true if this is an output node, meaning that it is of type kDescriptor and is not directly fo...
Definition: nnet-nnet.cc:112
std::vector< Cindex > cindexes
The mapping of cindex_id to Cindex.
void Print(std::ostream &os) const
This function is for printing info about the computation request in a human-readable way...
#define KALDI_ASSERT(cond)
Definition: kaldi-error.h:169
void ExplainWhyNotComputable(int32 cindex_id) const
#define KALDI_LOG
Definition: kaldi-error.h:133
void ExplainWhyNotComputable ( int32  cindex_id) const
private

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

References ComputationGraph::cindexes, ComputationGraphBuilder::computable_info_, ComputationGraph::dependencies, ComputationGraphBuilder::graph_, KALDI_ASSERT, KALDI_LOG, ComputationGraphBuilder::kComputable, and ComputationGraphBuilder::PrintCindexId().

Referenced by ComputationGraphBuilder::ExplainWhyAllOutputsNotComputable().

135  {
136  int32 max_lines_print = 100;
137  std::deque<int32> cindexes_to_explain;
138  cindexes_to_explain.push_back(first_cindex_id);
139  KALDI_ASSERT(graph_->cindexes.size() == graph_->dependencies.size());
140  std::ostringstream os;
141  os << "*** cindex ";
142  PrintCindexId(os, first_cindex_id);
143  os << " is not computable for the following reason: ***\n";
144  for (int32 num_lines_printed = 0;
145  num_lines_printed < max_lines_print && !cindexes_to_explain.empty();
146  num_lines_printed++) {
147  int32 cindex_id = cindexes_to_explain.front();
148  cindexes_to_explain.pop_front();
149  KALDI_ASSERT(static_cast<size_t>(cindex_id) < graph_->cindexes.size());
150  PrintCindexId(os, cindex_id);
151  os << " is " << static_cast<ComputableInfo>(
152  computable_info_[cindex_id]) << ", dependencies: ";
153  const std::vector<int32> dependencies = graph_->dependencies[cindex_id];
154  std::vector<int32>::const_iterator iter = dependencies.begin(),
155  end = dependencies.end();
156  for (; iter != end; iter++) {
157  int32 dep_cindex_id = *iter;
158  PrintCindexId(os, dep_cindex_id);
159  ComputableInfo status = static_cast<ComputableInfo>(
160  computable_info_[cindex_id]);
161  if (status != kComputable) {
162  os << '[' << status << ']';
163  cindexes_to_explain.push_back(dep_cindex_id);
164  }
165  if (iter+2 != end)
166  os << ", ";
167  }
168  os << "\n";
169  }
170  os << "\n";
171  KALDI_LOG << os.str();
172 }
std::vector< Cindex > cindexes
The mapping of cindex_id to Cindex.
std::vector< std::vector< int32 > > dependencies
dependencies[cindex_id] gives you the list of other cindex_ids that this particular cindex_id directl...
#define KALDI_ASSERT(cond)
Definition: kaldi-error.h:169
void PrintCindexId(std::ostream &os, int32 cindex_id) const
#define KALDI_LOG
Definition: kaldi-error.h:133
void GetComputableInfo ( std::vector< std::vector< bool > > *  computable) const

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

References ComputationGraph::cindexes, ComputationGraphBuilder::computable_info_, 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().

802  {
803  KALDI_ASSERT(!graph_->cindexes.empty() &&
804  "You need to call this after Compute()!");
805  KALDI_ASSERT(!computable_info_.empty() &&
806  "You need to call this before Prune()!");
807  computable->clear();
808  computable->resize(request_->outputs.size());
809  for (size_t i = 0; i < request_->outputs.size(); i++) {
810  const IoSpecification &output = request_->outputs[i];
811  int32 n = nnet_.GetNodeIndex(output.name);
812  KALDI_ASSERT(n != -1);
813  int32 size = output.indexes.size();
814  std::vector<bool> &this_vec = (*computable)[i];
815  this_vec.resize(size);
816  for (size_t j = 0; j < size; j++) {
817  Cindex cindex(n, output.indexes[j]);
818  int32 cindex_id = graph_->GetCindexId(cindex);
819  KALDI_ASSERT(cindex_id != -1);
820  this_vec[j] = (computable_info_[cindex_id] == kComputable);
821  }
822  }
823 }
std::pair< int32, Index > Cindex
Definition: nnet-common.h:115
std::vector< Cindex > cindexes
The mapping of cindex_id to Cindex.
int32 GetCindexId(const Cindex &cindex, bool is_input, bool *is_new)
Maps a Cindex to an integer cindex_id.
struct rnnlm::@11::@12 n
#define KALDI_ASSERT(cond)
Definition: kaldi-error.h:169
std::vector< IoSpecification > outputs
int32 GetNodeIndex(const std::string &node_name) const
returns index associated with this node name, or -1 if no such index.
Definition: nnet-nnet.cc:466
void IncrementUsableCount ( int32  cindex_id)
private

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

References ComputationGraphBuilder::computable_info_, ComputationGraph::dependencies, ComputationGraphBuilder::graph_, KALDI_PARANOID_ASSERT, ComputationGraphBuilder::kNotComputable, and ComputationGraphBuilder::usable_count_.

Referenced by ComputationGraphBuilder::AddDependencies().

891  {
892  KALDI_PARANOID_ASSERT(static_cast<size_t>(cindex_id)<usable_count_.size());
893  // the next line post-increments the reachable count.
894  if (usable_count_[cindex_id]++ == 0 &&
895  computable_info_[cindex_id] != kNotComputable) {
896  std::vector<int32>::const_iterator
897  iter = graph_->dependencies[cindex_id].begin(),
898  end = graph_->dependencies[cindex_id].end();
899  for (; iter != end; ++iter) {
900  int32 dep_cindex_id = *iter;
901  IncrementUsableCount(dep_cindex_id);
902  }
903  }
904 }
std::vector< std::vector< int32 > > dependencies
dependencies[cindex_id] gives you the list of other cindex_ids that this particular cindex_id directl...
#define KALDI_PARANOID_ASSERT(cond)
Definition: kaldi-error.h:182
void PrintCindexId ( std::ostream &  os,
int32  cindex_id 
) const
private

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

References ComputationGraph::cindexes, Nnet::GetNodeName(), ComputationGraphBuilder::graph_, KALDI_ASSERT, and ComputationGraphBuilder::nnet_.

Referenced by ComputationGraphBuilder::ExplainWhyNotComputable().

126  {
127  KALDI_ASSERT(static_cast<size_t>(cindex_id) < graph_->cindexes.size());
128  const Cindex &cindex = graph_->cindexes[cindex_id];
129  const std::string &node_name = nnet_.GetNodeName(cindex.first);
130  os << node_name << '(' << cindex.second.n << ", " << cindex.second.t
131  << ", " << cindex.second.x << ')';
132 }
std::pair< int32, Index > Cindex
Definition: nnet-common.h:115
std::vector< Cindex > cindexes
The mapping of cindex_id to Cindex.
const std::string & GetNodeName(int32 node_index) const
returns individual node name.
Definition: nnet-nnet.cc:684
#define KALDI_ASSERT(cond)
Definition: kaldi-error.h:169
void Prune ( )

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

References ComputationGraph::cindexes, ComputationGraphBuilder::computable_info_, ComputationGraphBuilder::computable_queue_, ComputationGraphBuilder::computable_queued_, ComputationGraphBuilder::ComputeRequiredArray(), ComputationGraphBuilder::depend_on_this_, ComputationGraphBuilder::graph_, ComputationGraph::is_input, KALDI_ASSERT, ComputationGraphBuilder::kComputable, ComputationGraphBuilder::PruneDependencies(), ComputationGraph::Renumber(), ComputationGraph::segment_ends, and ComputationGraphBuilder::usable_count_.

Referenced by Compiler::CreateComputation().

575  {
576  // Since Prune() is called for each segment in turn [note: there
577  // will be only 1 segment in the normal non-online case], we
578  // only prune for the current, just-added segment.
579  int32 start_cindex_id = (graph_->segment_ends.empty() ? 0 :
580  graph_->segment_ends.back());
581  int32 num_cindex_ids = graph_->cindexes.size();
582  // Prune the dependencies to just those that are used (to remove
583  // optional dependencies that don't end up getting used).
584 
585  for (int32 cindex_id = start_cindex_id;
586  cindex_id < num_cindex_ids; cindex_id++)
587  PruneDependencies(cindex_id);
588  // the following clears the elements of depend_on_this from start_cindex_id to
589  // num_cindex_ids - 1, without touching the entire array.
590  depend_on_this_.resize(start_cindex_id);
591  depend_on_this_.resize(num_cindex_ids);
592  std::vector<bool> required;
593  ComputeRequiredArray(start_cindex_id, &required);
594 
595  std::vector<bool> keep(num_cindex_ids - start_cindex_id, false);
596  for (int32 c = start_cindex_id; c < num_cindex_ids; c++) {
597  if (required[c - start_cindex_id] || graph_->is_input[c]) {
599  "You are calling Prune when not everything is computable.");
600  keep[c - start_cindex_id] = true;
601  }
602  }
603  graph_->Renumber(start_cindex_id, keep);
604  // We also need to renumber computable_info_ and usable_count_, which
605  // graph_->Renumber doesn't do for us, but we can make some shortcuts. We set
606  // all computable_info_ to kComputable because actually it all was kComputable
607  // (we checked when deciding what to keep); and we set the usable_count_ to 1
608  // for all the cindex_ids we just added... this is not 100% accurate
609  // according to the way we defined usable_count_, but it prevents additional
610  // computation since it is > 0 (notice that IncrementUsableCount and
611  // DecrementUsableCount may do some work when the usable_count goes to zero or
612  // from zero. Anyway, the usable-count for these cindex_ids for those "older
613  // segments" is not critical. [this information only gets used if we process
614  // additional segments as part of the compilation of an online computation.]
615  int32 new_num_cindex_ids = graph_->cindexes.size();
616  computable_info_.resize(start_cindex_id);
617  computable_info_.resize(new_num_cindex_ids, (char)kComputable);
618  usable_count_.resize(start_cindex_id);
619  usable_count_.resize(new_num_cindex_ids, 1);
620  // depend_on_this_ is a vector of vectors-- keeping track of the reverse of
621  // the dependencies-- and I believe we won't be needing this information any
622  // more past this point.
623  depend_on_this_.resize(start_cindex_id);
624  depend_on_this_.resize(new_num_cindex_ids);
625  // computable_queued_ also shouldn't be queried past this point, but
626  // I believe they should all be false at this point anyway (note that
627  // we assert below that computable_queue_ is empty).
628  computable_queued_.resize(new_num_cindex_ids);
629 
631  graph_->segment_ends.push_back(new_num_cindex_ids);
632 }
std::vector< Cindex > cindexes
The mapping of cindex_id to Cindex.
std::vector< bool > is_input
For each Cindex this tells us whether it was provided as an input to the network. ...
std::vector< std::vector< int32 > > depend_on_this_
std::vector< int32 > segment_ends
This variable is only of particular interest in a 'multi-segment' computation, which is used while cr...
void Renumber(int32 start_cindex_id, const std::vector< bool > &keep)
This function renumbers the cindex-ids (but only those with index c >= start_cindex_id,.
void ComputeRequiredArray(int32 start_cindex_id, std::vector< bool > *required) const
#define KALDI_ASSERT(cond)
Definition: kaldi-error.h:169
void PruneDependencies ( int32  cindex_id)
private

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

References ComputationGraph::cindexes, NetworkNode::component_index, ComputationGraphBuilder::computable_info_, ComputationGraph::dependencies, NetworkNode::descriptor, ComputationGraph::GetCindexId(), Nnet::GetComponent(), Nnet::GetNode(), ComputationGraphBuilder::graph_, rnnlm::i, Component::IsComputable(), Descriptor::IsComputable(), KALDI_ASSERT, KALDI_ERR, kaldi::nnet3::kComponent, ComputationGraphBuilder::kComputable, kaldi::nnet3::kDescriptor, kaldi::nnet3::kDimRange, kaldi::nnet3::kInput, ComputationGraphBuilder::kNotComputable, ComputationGraphBuilder::kUnknown, ComputationGraphBuilder::kWillNotCompute, ComputationRequest::misc_info, ComputationGraphBuilder::nnet_, NetworkNode::node_type, ComputationGraphBuilder::request_, kaldi::SortAndUniq(), and NetworkNode::u.

Referenced by ComputationGraphBuilder::Prune().

364  {
365  ComputableInfo c = static_cast<ComputableInfo>(computable_info_[cindex_id]);
366  // by the time this is called, there should be no cindexes with unknown state.
367  KALDI_ASSERT(c != kUnknown);
368  if (c == kNotComputable || c == kWillNotCompute) {
369  // if something is not computable, there is no point
370  // keeping around its dependencies.
371  graph_->dependencies[cindex_id].clear();
372  return;
373  }
375  const Cindex &cindex = graph_->cindexes[cindex_id];
376  int32 node_id = cindex.first;
377  const Index &index = cindex.second;
378  const NetworkNode &node = nnet_.GetNode(node_id);
379 
380  std::vector<int32> &dependencies = graph_->dependencies[cindex_id];
381  std::sort(dependencies.begin(), dependencies.end());
382  std::vector<int32> used_cindex_ids;
383 
384  switch (node.node_type) {
385  case kDescriptor: {
386  const Descriptor &desc = node.descriptor;
387  bool dont_care = false; // there should be no kUnknown, and we check this
388  CindexSet cindex_set(*graph_, computable_info_, dont_care);
389  std::vector<Cindex> used_cindexes;
390  bool ans = desc.IsComputable(index, cindex_set, &used_cindexes);
391  // If the next assert fails it could be a failure in the assumption that
392  // making more inputs available will never change something from not being
393  // computable to being computable; or it could be a bug elsewhere.
394  KALDI_ASSERT(ans);
395  size_t size = used_cindexes.size();
396  used_cindex_ids.resize(size);
397  for (size_t i = 0; i < size; i++) {
398  int32 dep_cindex_id = graph_->GetCindexId(used_cindexes[i]);
399  KALDI_ASSERT(dep_cindex_id != -1);
400  used_cindex_ids[i] = dep_cindex_id;
401  KALDI_ASSERT(std::binary_search(dependencies.begin(),
402  dependencies.end(),
403  dep_cindex_id));
404  }
405  break;
406  }
407  case kComponent: {
408  const Component *c = nnet_.GetComponent(node.u.component_index);
409  bool dont_care = false; // there should be no kUnknown, and we check this
410  // In the line below, node_id - 1 is the index of the component-input
411  // node-- the descriptor at the input to the component. We are interested
412  // in the set of inputs to the component that are computable.
413  IndexSet index_set(*graph_, computable_info_, node_id - 1, dont_care);
414  std::vector<Index> used_indexes;
415  bool ans = c->IsComputable(request_->misc_info, index, index_set,
416  &used_indexes);
417  // If the next assert fails it could be a failure in the assumption that
418  // making more inputs available will never change something from not being
419  // computable to being computable; or it could be a bug elsewhere.
420  KALDI_ASSERT(ans);
421  size_t size = used_indexes.size();
422  used_cindex_ids.resize(size);
423  for (size_t i = 0; i < size; i++) {
424  Cindex dep_cindex(node_id - 1, used_indexes[i]);
425  int32 dep_cindex_id = graph_->GetCindexId(dep_cindex);
426  KALDI_ASSERT(dep_cindex_id != -1);
427  used_cindex_ids[i] = dep_cindex_id;
428  KALDI_ASSERT(std::binary_search(dependencies.begin(),
429  dependencies.end(),
430  dep_cindex_id));
431  }
432  break;
433  }
434  case kDimRange:
435  KALDI_ASSERT(dependencies.size() == 1);
436  // there should be exactly one dependency and it is required, not
437  // optional, so there is nothing to do here. Return.
438  return;
439  case kInput:
440  KALDI_ASSERT(dependencies.empty());
441  // there is nothing to do; return.
442  return;
443  default:
444  KALDI_ERR << "Invalid node type";
445  }
446  SortAndUniq(&used_cindex_ids);
447 
448  // the next statement modifies the graph.
449  dependencies.swap(used_cindex_ids);
450 }
MiscComputationInfo misc_info
misc_info is for extensibility to things that don't easily fit into the framework.
void SortAndUniq(std::vector< T > *vec)
Sorts and uniq's (removes duplicates) from a vector.
Definition: stl-utils.h:39
std::pair< int32, Index > Cindex
Definition: nnet-common.h:115
const NetworkNode & GetNode(int32 node) const
returns const reference to a particular numbered network node.
Definition: nnet-nnet.h:146
std::vector< Cindex > cindexes
The mapping of cindex_id to Cindex.
std::vector< std::vector< int32 > > dependencies
dependencies[cindex_id] gives you the list of other cindex_ids that this particular cindex_id directl...
int32 GetCindexId(const Cindex &cindex, bool is_input, bool *is_new)
Maps a Cindex to an integer cindex_id.
#define KALDI_ERR
Definition: kaldi-error.h:127
Component * GetComponent(int32 c)
Return component indexed c. Not a copy; not owned by caller.
Definition: nnet-nnet.cc:150
#define KALDI_ASSERT(cond)
Definition: kaldi-error.h:169
void SetAsWillNotCompute ( int32  cindex_id)
private

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

References ComputationGraphBuilder::computable_info_, ComputationGraphBuilder::computable_queue_, ComputationGraphBuilder::computable_queued_, ComputationGraphBuilder::depend_on_this_, KALDI_ASSERT, ComputationGraphBuilder::kUnknown, ComputationGraphBuilder::kWillNotCompute, and ComputationGraphBuilder::usable_count_.

Referenced by ComputationGraphBuilder::BuildGraphOneIter().

865  {
866  KALDI_ASSERT(usable_count_[cindex_id] == 0);
867  computable_info_[cindex_id] = kWillNotCompute;
868  std::vector<int32>::const_iterator iter = depend_on_this_[cindex_id].begin(),
869  end = depend_on_this_[cindex_id].end();
870  for (; iter != end; ++iter) {
871  int32 other_cindex_id = *iter;
872  if (computable_info_[other_cindex_id] == kUnknown &&
873  !computable_queued_[other_cindex_id]) {
874  computable_queue_.push_back(other_cindex_id);
875  computable_queued_[other_cindex_id] = true;
876  }
877  }
878 }
std::vector< std::vector< int32 > > depend_on_this_
#define KALDI_ASSERT(cond)
Definition: kaldi-error.h:169
void UpdateAllComputableInfo ( )
private

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

References ComputationGraphBuilder::computable_queue_, ComputationGraphBuilder::computable_queued_, and ComputationGraphBuilder::UpdateComputableInfo().

Referenced by ComputationGraphBuilder::Compute().

881  {
882  while (!computable_queue_.empty()) {
883  int32 cindex_id = computable_queue_.front();
884  computable_queue_.pop_front();
885  computable_queued_[cindex_id] = false;
886  UpdateComputableInfo(cindex_id);
887  }
888 }
void UpdateComputableInfo ( int32  cindex_id)
private

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

References ComputationGraphBuilder::computable_info_, ComputationGraphBuilder::computable_queue_, ComputationGraphBuilder::computable_queued_, ComputationGraphBuilder::ComputeComputableInfo(), ComputationGraphBuilder::DecrementUsableCount(), ComputationGraphBuilder::depend_on_this_, ComputationGraph::dependencies, ComputationGraphBuilder::graph_, KALDI_ASSERT, ComputationGraphBuilder::kNotComputable, ComputationGraphBuilder::kUnknown, and ComputationGraphBuilder::usable_count_.

Referenced by ComputationGraphBuilder::UpdateAllComputableInfo().

826  {
827  // if the current computable_info_ for cindex_id value is not kUnknown, this
828  // cindex_id should not have been in the queue.
829  KALDI_ASSERT(static_cast<size_t>(cindex_id) < computable_info_.size());
830  char &output = computable_info_[cindex_id];
831  KALDI_ASSERT(output == kUnknown);
832 
833  output = static_cast<char>(ComputeComputableInfo(cindex_id));
834 
835  if (output != kUnknown) {
836  // The computable status of cindexes that depend on this cindex and whose
837  // status is currently kUnknown might now change, so if they are not in the
838  // computable queue, put them there.
839  std::vector<int32>::const_iterator iter = depend_on_this_[cindex_id].begin(),
840  end = depend_on_this_[cindex_id].end();
841  for (; iter != end; ++iter) {
842  int32 other_cindex_id = *iter;
843  if (computable_info_[other_cindex_id] == kUnknown &&
844  !computable_queued_[other_cindex_id]) {
845  computable_queue_.push_back(other_cindex_id);
846  computable_queued_[other_cindex_id] = true;
847  }
848  }
849  if (output == kNotComputable && usable_count_[cindex_id] != 0) {
850  // If we have just changed the computable state from kUnknown to
851  // kNotComputable, then given the way the usable_count_ is defined (see
852  // the declaration), this means that we must decrement the
853  // usable_count_ of all cindex_ids that we depend on.
854  std::vector<int32>::const_iterator
855  iter = graph_->dependencies[cindex_id].begin(),
856  end = graph_->dependencies[cindex_id].end();
857  for (; iter != end; ++iter) {
858  int32 dep_cindex_id = *iter;
859  DecrementUsableCount(dep_cindex_id);
860  }
861  }
862  }
863 }
std::vector< std::vector< int32 > > dependencies
dependencies[cindex_id] gives you the list of other cindex_ids that this particular cindex_id directl...
std::vector< std::vector< int32 > > depend_on_this_
#define KALDI_ASSERT(cond)
Definition: kaldi-error.h:169
ComputableInfo ComputeComputableInfo(int32 cindex_id) const

Member Data Documentation


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