All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Modules Pages
ComputationGraph Struct Reference

The first step in compilation is to turn the ComputationSpecification into a ComputationGraph, where for each Cindex we have a list of other Cindexes that it depends on. More...

#include <nnet-computation-graph.h>

Collaboration diagram for ComputationGraph:

Public Member Functions

int32 GetCindexId (const Cindex &cindex, bool is_input, bool *is_new)
 Maps a Cindex to an integer cindex_id. More...
 
int32 GetCindexId (const Cindex &cindex) const
 Const version of GetCindexId that does not add CindexIds. More...
 
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,. More...
 
void Print (std::ostream &os, const std::vector< std::string > &node_names)
 This function, useful for debugging/visualization purposes, prints out a summary of the computation graph (which will take up multiple lines). More...
 

Public Attributes

std::vector< Cindexcindexes
 The mapping of cindex_id to Cindex. More...
 
std::vector< bool > is_input
 For each Cindex this tells us whether it was provided as an input to the network. More...
 
std::vector< std::vector< int32 > > dependencies
 dependencies[cindex_id] gives you the list of other cindex_ids that this particular cindex_id directly depends on to compute it. More...
 
std::vector< int32 > segment_ends
 This variable is only of particular interest in a 'multi-segment' computation, which is used while creating computations for 'online' operation (for the kind of situation where you provide some input; run the computation; get some output, provide some more input for larger 't' values, etc.). More...
 

Private Attributes

unordered_map< Cindex, int32,
CindexHasher
cindex_to_cindex_id_
 Maps each Cindex to an integer cindex_id: reverse mapping of "cindexes". More...
 

Detailed Description

The first step in compilation is to turn the ComputationSpecification into a ComputationGraph, where for each Cindex we have a list of other Cindexes that it depends on.

All the stages of compilation use the ComputationGraph representation; they are mostly manipulations of it.

For efficiency, we give each Cindex its own integer identifier, called a "cindex_id". A cindex_id is only interpretable relative to a ComputationGraph; it's an index into the "cindexes" array of the ComputationGraph. The GetCindexId() functions perform the reverse mapping.

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

Member Function Documentation

int32 GetCindexId ( const Cindex cindex,
bool  is_input,
bool *  is_new 
)

Maps a Cindex to an integer cindex_id.

If not present, then add it (with the corresponding "is_input" flag set to the value "input") and set *is_new to true. If present, set is_new to false and return the existing cindex_id.

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

References ComputationGraph::cindex_to_cindex_id_, ComputationGraph::cindexes, ComputationGraph::dependencies, ComputationGraph::is_input, and KALDI_ASSERT.

Referenced by ComputationGraphBuilder::AddDependencies(), ComputationGraphBuilder::AddInputs(), kaldi::nnet3::computation_graph::AddInputToGraph(), ComputationGraphBuilder::AddOutputs(), kaldi::nnet3::computation_graph::AddOutputToGraph(), ComputationStepsComputer::AddStep(), ComputationGraphBuilder::ComputeComputableInfo(), kaldi::nnet3::ComputeComputationGraph(), Compiler::ComputeInputLocationsList(), ComputationStepsComputer::ConvertToCindexIds(), ComputationGraphBuilder::GetComputableInfo(), CindexSet::operator()(), IndexSet::operator()(), ComputationGraph::Print(), ComputationStepsComputer::ProcessInputOrOutputStep(), and ComputationGraphBuilder::PruneDependencies().

29  {
30  typedef unordered_map<Cindex, int32, CindexHasher> map_type;
31  int32 new_index = cindexes.size(); // we'll add this if we don't find it.
32  std::pair<map_type::iterator, bool> p = cindex_to_cindex_id_.insert(
33  std::pair<Cindex, int32>(cindex, new_index));
34  if (p.second == true) { // We added something to the hash.
35  *is_new = true;
36  KALDI_ASSERT(is_input.size() == cindexes.size());
37  cindexes.push_back(cindex);
38  is_input.push_back(input);
39  // make room for this "dependencies" entry.
40  dependencies.resize(new_index + 1);
41  return new_index;
42  } else { // We did not add anything.
43  *is_new = false;
44  return p.first->second;
45  }
46 }
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...
unordered_map< Cindex, int32, CindexHasher > cindex_to_cindex_id_
Maps each Cindex to an integer cindex_id: reverse mapping of "cindexes".
std::vector< bool > is_input
For each Cindex this tells us whether it was provided as an input to the network. ...
#define KALDI_ASSERT(cond)
Definition: kaldi-error.h:169
int32 GetCindexId ( const Cindex cindex) const

Const version of GetCindexId that does not add CindexIds.

It will return -1 if the Cindex is not present, and the user should check for this.

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

References ComputationGraph::cindex_to_cindex_id_.

47  {
48  typedef unordered_map<Cindex, int32, CindexHasher> map_type;
49  map_type::const_iterator iter = cindex_to_cindex_id_.find(cindex);
50  if (iter == cindex_to_cindex_id_.end())
51  return -1;
52  else
53  return iter->second;
54 }
unordered_map< Cindex, int32, CindexHasher > cindex_to_cindex_id_
Maps each Cindex to an integer cindex_id: reverse mapping of "cindexes".
void Print ( std::ostream &  os,
const std::vector< std::string > &  node_names 
)

This function, useful for debugging/visualization purposes, prints out a summary of the computation graph (which will take up multiple lines).

Format is: [ cindex1 -> dep-cindex1 dep-cindex2 ] [ cindex2 -> dep-cindex3 dep-cindex4 ] showing each Cindex and the Cindexes it depends on. cindexes from different network nodes are shown on different lines.

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

References ComputationGraph::cindexes, ComputationGraph::dependencies, ComputationGraph::GetCindexId(), rnnlm::i, ComputationGraph::is_input, rnnlm::j, and kaldi::nnet3::PrintCindex().

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

176  {
177  int32 max_cindexes_per_line = 50, max_dependencies = 5,
178  num_cindexes = cindexes.size();
179 
180  std::vector<std::pair<Cindex, std::vector<Cindex> > > pairs;
181  pairs.reserve(num_cindexes);
182  for (int32 cindex_id = 0; cindex_id < num_cindexes; cindex_id++) {
183  int32 size = dependencies[cindex_id].size();
184  std::vector<Cindex> deps(size);
185  for (size_t i = 0; i < size; i++)
186  deps[i] = cindexes[dependencies[cindex_id][i]];
187  std::sort(deps.begin(), deps.end());
188  pairs.push_back(std::pair<Cindex, std::vector<Cindex> >(cindexes[cindex_id],
189  deps));
190  }
191  std::sort(pairs.begin(), pairs.end());
192  int32 cur_start = 0;
193  for (int32 i = 0; i < num_cindexes; i++) {
194  if (pairs[i].first.first != pairs[cur_start].first.first) {
195  cur_start = i;
196  os << "\n";
197  }
198  if (i - cur_start < max_cindexes_per_line) {
199  os << "[ ";
200  PrintCindex(os, pairs[i].first, node_names);
201  if (! is_input[GetCindexId(pairs[i].first)]) {
202  // only print out dependences for cindexes that
203  // were not provided as inputs.
204  os << " -> ";
205  for (int32 j = 0; j < pairs[i].second.size(); j++) {
206  if (j < max_dependencies) {
207  PrintCindex(os, pairs[i].second[j], node_names);
208  if (j + 1 < pairs[i].second.size())
209  os << ", ";
210  } else if (j == max_dependencies) {
211  os << "...";
212  }
213  }
214  }
215  os << " ] ";
216  } else if (i - cur_start == max_cindexes_per_line) {
217  os << "...";
218  }
219  }
220  os << "\n";
221 
222 }
void PrintCindex(std::ostream &os, const Cindex &cindex, const std::vector< std::string > &node_names)
Definition: nnet-common.cc:427
std::pair< int32, Index > Cindex
Definition: nnet-common.h:115
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< bool > is_input
For each Cindex this tells us whether it was provided as an input to the network. ...
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,.

true. The "keep" array must be the same size as this->cindexes.size() - start_cindex_id.

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

References ComputationGraph::cindex_to_cindex_id_, ComputationGraph::cindexes, rnnlm::d, ComputationGraph::dependencies, ComputationGraph::is_input, rnnlm::j, KALDI_ASSERT, KALDI_ERR, and KALDI_PARANOID_ASSERT.

Referenced by ComputationGraphBuilder::Prune().

58  {
59  int32 old_num_cindex_ids = cindexes.size();
60  KALDI_ASSERT(keep.size() == old_num_cindex_ids - start_cindex_id);
61  // count_before_renumbering is the number of cindex_ids >= start_cindex_id,
62  // before renumbering.
63  int32 count_before_renumbering = old_num_cindex_ids - start_cindex_id;
64  std::vector<int32> old2new(count_before_renumbering, -1), new2old;
65  new2old.reserve(old_num_cindex_ids);
66  for (int32 j = 0; j < count_before_renumbering; j++) {
67  if (keep[j]) {
68  old2new[j] = new2old.size() + start_cindex_id;
69  new2old.push_back(j + start_cindex_id);
70  }
71  }
72  // count_after_renumbering is the number of cindex_ids >= start_cindex_id,
73  // after renumbering.
74  int32 count_after_renumbering = new2old.size(),
75  new_num_cindex_ids = start_cindex_id + count_after_renumbering;
76  if (count_after_renumbering == count_before_renumbering) {
77  // this is an optimization for when we are not deleting any
78  // cindex-ids.
79  return;
80  }
81 
82  for (int32 old_cindex_id = start_cindex_id;
83  old_cindex_id < old_num_cindex_ids; old_cindex_id++) {
84  int32 new_cindex_id = old2new[old_cindex_id - start_cindex_id];
85  Cindex &cindex = cindexes[old_cindex_id];
86  if (new_cindex_id == -1) {
87  cindex_to_cindex_id_.erase(cindex);
88  } else if (new_cindex_id != old_cindex_id) {
89  cindex_to_cindex_id_[cindex] = new_cindex_id;
90  }
91  }
92 
93  std::vector<int32> temp;
94  for (int32 c = start_cindex_id; c < new_num_cindex_ids; c++) {
95  int32 d = new2old[c - start_cindex_id];
96  // note: d >= c, which is why we do not overwrite data here.
97  KALDI_PARANOID_ASSERT(d >= c);
98  cindexes[c] = cindexes[d];
99  is_input[c] = is_input[d];
100  // if c == d, we need to create a temporary copy.
101  const std::vector<int32> &src_dependencies =
102  (c == d ? (temp = dependencies[d]) : dependencies[d]);
103  std::vector<int32>::const_iterator
104  iter = src_dependencies.begin(), end = src_dependencies.end();
105  dependencies[c].clear();
106  for (; iter != end; ++iter) {
107  int32 old_dep = *iter;
108  if (old_dep < start_cindex_id) {
109  dependencies[c].push_back(old_dep);
110  } else {
111  int32 new_dep = old2new[old_dep - start_cindex_id];
112  if (new_dep != -1)
113  dependencies[c].push_back(new_dep);
114  else
115  KALDI_ERR << "Dependency on nonexistent cindex-id";
116  }
117  }
118  }
119 
120  cindexes.resize(new_num_cindex_ids);
121  is_input.resize(new_num_cindex_ids);
122  dependencies.resize(new_num_cindex_ids);
123 }
std::pair< int32, Index > Cindex
Definition: nnet-common.h:115
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...
unordered_map< Cindex, int32, CindexHasher > cindex_to_cindex_id_
Maps each Cindex to an integer cindex_id: reverse mapping of "cindexes".
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
#define KALDI_PARANOID_ASSERT(cond)
Definition: kaldi-error.h:182
#define KALDI_ASSERT(cond)
Definition: kaldi-error.h:169

Member Data Documentation

unordered_map<Cindex, int32, CindexHasher> cindex_to_cindex_id_
private

Maps each Cindex to an integer cindex_id: reverse mapping of "cindexes".

Must be accessed via the GetCindexId() functions.

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

Referenced by ComputationGraph::GetCindexId(), and ComputationGraph::Renumber().

std::vector<std::vector<int32> > dependencies

dependencies[cindex_id] gives you the list of other cindex_ids that this particular cindex_id directly depends on to compute it.

No repeats will be present. Note, some of these dependencies may be optional dependencies; in early stages of compilation this will contain all "desired" inputs and later we will prune the dependencies contain just those that are used (which will vary depending on availability).

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

Referenced by ComputationGraphBuilder::AddDependencies(), ComputationGraphBuilder::Check(), kaldi::nnet3::ComputeComputationGraph(), kaldi::nnet3::computation_graph::ComputeDependenciesSubset(), ComputationGraphBuilder::ComputeRequiredArray(), Compiler::ComputeStepDependencies(), Compiler::CreateStepInfo(), ComputationGraphBuilder::DecrementUsableCount(), ComputationGraphBuilder::ExplainWhyNotComputable(), ComputationGraph::GetCindexId(), ComputationGraphBuilder::IncrementUsableCount(), ComputationGraph::Print(), ComputationStepsComputer::ProcessComponentStep(), ComputationGraphBuilder::PruneDependencies(), ComputationGraph::Renumber(), and ComputationGraphBuilder::UpdateComputableInfo().

std::vector<bool> is_input

For each Cindex this tells us whether it was provided as an input to the network.

This is necessary for a couple of reasons: firstly, the framework allows users to provide values for nodes of type kComponent (e.g. for RNN context). Also, Cindexes for input nodes that were not provided by the user may be created during computation graph creation (although they will not be computable), and we need to distinguish these from the provided Cindexes.

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

Referenced by Compiler::AllocateMatrices(), ComputationGraphBuilder::ComputeComputableInfo(), kaldi::nnet3::ComputeComputationGraph(), Compiler::ComputeDerivNeeded(), kaldi::nnet3::computation_graph::ComputeEpochInfo(), ComputationGraph::GetCindexId(), ComputationGraph::Print(), ComputationGraphBuilder::Prune(), and ComputationGraph::Renumber().

std::vector<int32> segment_ends

This variable is only of particular interest in a 'multi-segment' computation, which is used while creating computations for 'online' operation (for the kind of situation where you provide some input; run the computation; get some output, provide some more input for larger 't' values, etc.).

In this context, a 'segment' is a continuous range of cindex_ids, and a segment_end is one past the end of each segment, which is the same as the beginning of the next segment, if there is one. In the case of a fully-created computation graph with only one segment, this will contain just one value which equals the number of cindex_ids. This information is needed to correctly order the computation, because

the computation graph itself does not contain dependencies that encode the ordering of segments (and even if it did contain those dependencies, it's not really compatible with the way we use the scc's in the graph structure of the network to order the computation).

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

Referenced by ComputationGraphBuilder::Compute(), kaldi::nnet3::ComputeComputationPhases(), kaldi::nnet3::computation_graph::ComputeEpochInfo(), and ComputationGraphBuilder::Prune().


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