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< Cindex >	cindexes
	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

GetCindexId() [1/2]

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(), kaldi::nnet3::computation_graph::AddInputToGraph(), kaldi::nnet3::computation_graph::AddOutputToGraph(), ComputationStepsComputer::AddStep(), ComputationGraphBuilder::ComputeComputableInfo(), kaldi::nnet3::ComputeComputationGraph(), Compiler::ComputeInputLocationsList(), ComputationStepsComputer::ConvertToCindexIds(), ComputationGraphBuilder::GetComputableInfo(), CindexSet::operator()(), IndexSet::operator()(), ComputationGraph::Print(), and ComputationStepsComputer::ProcessInputOrOutputStep().

                                                              {
  typedef unordered_map<Cindex, int32, CindexHasher> map_type;
  int32 new_index = cindexes.size();  // we'll add this if we don't find it.
  std::pair<map_type::iterator, bool> p = cindex_to_cindex_id_.insert(
      std::pair<Cindex, int32>(cindex, new_index));
  if (p.second == true) {  // We added something to the hash.
    *is_new = true;
    KALDI_ASSERT(is_input.size() == cindexes.size());
    cindexes.push_back(cindex);
    is_input.push_back(input);
    // make room for this "dependencies" entry.
    dependencies.resize(new_index + 1);
    return new_index;
  } else { // We did not add anything.
    *is_new = false;
    return p.first->second;
  }
}

GetCindexId() [2/2]

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_.

                                                              {
  typedef unordered_map<Cindex, int32, CindexHasher> map_type;
  map_type::const_iterator iter = cindex_to_cindex_id_.find(cindex);
  if (iter == cindex_to_cindex_id_.end())
    return -1;
  else
    return iter->second;
}

Print()

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 176 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().

                                                                     {
  int32 max_cindexes_per_line = 50, max_dependencies = 5,
      num_cindexes = cindexes.size();

  std::vector<std::pair<Cindex, std::vector<Cindex> > > pairs;
  pairs.reserve(num_cindexes);
  for (int32 cindex_id = 0; cindex_id < num_cindexes; cindex_id++) {
    int32 size = dependencies[cindex_id].size();
    std::vector<Cindex> deps(size);
    for (size_t i = 0; i < size; i++)
      deps[i] = cindexes[dependencies[cindex_id][i]];
    std::sort(deps.begin(), deps.end());
    pairs.push_back(std::pair<Cindex, std::vector<Cindex> >(cindexes[cindex_id],
                                                            deps));
  }
  std::sort(pairs.begin(), pairs.end());
  int32 cur_start = 0;
  for (int32 i = 0; i < num_cindexes; i++) {
    if (pairs[i].first.first != pairs[cur_start].first.first) {
      cur_start = i;
      os << "\n";
    }
    if (i - cur_start < max_cindexes_per_line) {
      os << "[ ";
      PrintCindex(os, pairs[i].first, node_names);
      if (! is_input[GetCindexId(pairs[i].first)]) {
        // only print out dependences for cindexes that
        // were not provided as inputs.
        os << " -> ";
        for (int32 j = 0; j < pairs[i].second.size(); j++) {
          if (j < max_dependencies) {
            PrintCindex(os, pairs[i].second[j], node_names);
            if (j + 1 < pairs[i].second.size())
              os << ", ";
          } else if (j == max_dependencies) {
            os << "...";
          }
        }
      }
      os << " ] ";
    } else if (i - cur_start == max_cindexes_per_line) {
      os << "...";
    }
  }
  os << "\n";

}

Renumber()

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().

                                                             {
  int32 old_num_cindex_ids = cindexes.size();
  KALDI_ASSERT(keep.size() == old_num_cindex_ids - start_cindex_id);
  // count_before_renumbering is the number of cindex_ids >= start_cindex_id,
  // before renumbering.
  int32 count_before_renumbering = old_num_cindex_ids - start_cindex_id;
  std::vector<int32> old2new(count_before_renumbering, -1), new2old;
  new2old.reserve(old_num_cindex_ids);
  for (int32 j = 0; j < count_before_renumbering; j++) {
    if (keep[j]) {
      old2new[j] = new2old.size() + start_cindex_id;
      new2old.push_back(j + start_cindex_id);
    }
  }
  // count_after_renumbering is the number of cindex_ids >= start_cindex_id,
  // after renumbering.
  int32 count_after_renumbering = new2old.size(),
      new_num_cindex_ids = start_cindex_id + count_after_renumbering;
  if (count_after_renumbering == count_before_renumbering) {
    // this is an optimization for when we are not deleting any
    // cindex-ids.
    return;
  }

  for (int32 old_cindex_id = start_cindex_id;
       old_cindex_id < old_num_cindex_ids; old_cindex_id++) {
    int32 new_cindex_id = old2new[old_cindex_id - start_cindex_id];
    Cindex &cindex = cindexes[old_cindex_id];
    if (new_cindex_id == -1) {
      cindex_to_cindex_id_.erase(cindex);
    } else if (new_cindex_id != old_cindex_id) {
      cindex_to_cindex_id_[cindex] = new_cindex_id;
    }
  }

  std::vector<int32> temp;
  for (int32 c = start_cindex_id; c < new_num_cindex_ids; c++) {
    int32 d = new2old[c - start_cindex_id];
    // note: d >= c, which is why we do not overwrite data here.
    KALDI_PARANOID_ASSERT(d >= c);
    cindexes[c] = cindexes[d];
    is_input[c] = is_input[d];
    // if c == d, we need to create a temporary copy.
    const std::vector<int32> &src_dependencies =
        (c == d ? (temp = dependencies[d]) : dependencies[d]);
    std::vector<int32>::const_iterator
        iter = src_dependencies.begin(), end = src_dependencies.end();
    dependencies[c].clear();
    for (; iter != end; ++iter) {
      int32 old_dep = *iter;
      if (old_dep < start_cindex_id) {
        dependencies[c].push_back(old_dep);
      } else {
        int32 new_dep = old2new[old_dep - start_cindex_id];
        if (new_dep != -1)
          dependencies[c].push_back(new_dep);
        else
          KALDI_ERR << "Dependency on nonexistent cindex-id";
      }
    }
  }

  cindexes.resize(new_num_cindex_ids);
  is_input.resize(new_num_cindex_ids);
  dependencies.resize(new_num_cindex_ids);
}

Member Data Documentation

cindex_to_cindex_id_

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().

cindexes

std::vector<Cindex> cindexes

The mapping of cindex_id to Cindex.

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

Referenced by ComputationGraphBuilder::AddDependencies(), ComputationStepsComputer::AddStep(), ComputationGraphBuilder::Check(), ComputationStepsComputer::Check(), ComputationGraphBuilder::ComputationGraphBuilder(), ComputationStepsComputer::ComputationStepsComputer(), ComputationGraphBuilder::Compute(), ComputationGraphBuilder::ComputeComputableInfo(), kaldi::nnet3::ComputeComputationGraph(), kaldi::nnet3::ComputeComputationPhases(), kaldi::nnet3::computation_graph::ComputeDependenciesSubset(), Compiler::ComputeDerivNeeded(), kaldi::nnet3::computation_graph::ComputeEpochInfo(), ComputationGraphBuilder::ComputeRequiredArray(), Compiler::ComputeStepDependencies(), ComputationStepsComputer::ConvertToCindexes(), Compiler::CreateStepInfo(), ComputationGraph::GetCindexId(), ComputationGraphBuilder::GetComputableInfo(), ComputationGraph::Print(), ComputationStepsComputer::ProcessComponentStep(), ComputationGraphBuilder::Prune(), and ComputationGraph::Renumber().

dependencies

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 to 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().

is_input

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 ComputationGraphBuilder::AddInputs(), ComputationGraphBuilder::AddOutputs(), Compiler::AllocateMatrices(), ComputationGraphBuilder::ComputeComputableInfo(), kaldi::nnet3::ComputeComputationGraph(), Compiler::ComputeDerivNeeded(), kaldi::nnet3::computation_graph::ComputeEpochInfo(), ComputationGraph::GetCindexId(), ComputationGraph::Print(), ComputationGraphBuilder::Prune(), and ComputationGraph::Renumber().

segment_ends

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:

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