nnet-computation-graph.h

Go to the documentation of this file.

// nnet3/nnet-computation-graph.h

// Copyright 2015    Johns Hopkins University (author: Daniel Povey)

// See ../../COPYING for clarification regarding multiple authors
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//  http://www.apache.org/licenses/LICENSE-2.0
//
// THIS CODE IS PROVIDED *AS IS* BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
// KIND, EITHER EXPRESS OR IMPLIED, INCLUDING WITHOUT LIMITATION ANY IMPLIED
// WARRANTIES OR CONDITIONS OF TITLE, FITNESS FOR A PARTICULAR PURPOSE,
// MERCHANTABLITY OR NON-INFRINGEMENT.
// See the Apache 2 License for the specific language governing permissions and
// limitations under the License.

#ifndef KALDI_NNET3_NNET_COMPUTATION_GRAPH_H_
#define KALDI_NNET3_NNET_COMPUTATION_GRAPH_H_

#include "nnet3/nnet-component-itf.h"
#include "nnet3/nnet-nnet.h"
#include "nnet3/nnet-computation.h"

#include <iostream>
#include <deque>

namespace kaldi {
namespace nnet3 {

struct ComputationGraph {

  std::vector<Cindex> cindexes;

  std::vector<bool> is_input;

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

  std::vector<int32> segment_ends;

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

  int32 GetCindexId(const Cindex &cindex) const;

  // keeping only for which keep[c - start_cindex_id] is
  void Renumber(int32 start_cindex_id,
                const std::vector<bool> &keep);


  void Print(std::ostream &os, const std::vector<std::string> &node_names);

 private:
  unordered_map<Cindex, int32, CindexHasher> cindex_to_cindex_id_;
};


class ComputationGraphBuilder {
 public:
  ComputationGraphBuilder(const Nnet &nnet,
                          ComputationGraph *graph);

  // Does the initial computation (populating the graph and computing whether
  // each required cindex_id is computable), without the pruning.  In the normal
  // case you call this just once with one 'request', but in the 'online' case
  // you call Compute() [then maybe check AllOutputsAreComputable()] then
  // Prune() multiple times, with a sequence of different requests for
  // increasing time values.
  // Note: it sets the class member request_ to the address of 'request', so
  // you should not let 'request' go out of scope while this class might
  // still use it (e.g. until you call Compute() with a different
  void Compute(const ComputationRequest &request);

  // Returns true if all requested outputs are computable.  To be called after
  // Compute() but before Prune(().
  bool AllOutputsAreComputable() const;

  // Prints logging info to explain why all outputs are not computable.
  // To be called only if AllOutputsAreComputable() returned false.
  void ExplainWhyAllOutputsNotComputable() const;

  // This function outputs to "computable" information about whether each
  // requested element of each output was computable.  "computable" will have
  // the same size as request_->outputs, and each element will have the same
  // size as request_->outputs[i].indexes.size().  May only be called after
  // Compute() but before Prune().  If you have already called Prune(), you can
  // just assume everything was computable, or else Prune() would have crashed.
  void GetComputableInfo(std::vector<std::vector<bool> > *computable) const;

  // to be called after Compute(), this prunes away unused cindex_ids.
  // If not all the outputs are computable, this will die;
  // you can check the return status of AllOutputsAreComputable() first if
  // you want to avoid this.
  void Prune();

  // This enum says for each cindex_id, whether we can compute it from the given
  // inputs or not.  Note that there may be situations where before adding
  // dependencies of a particular cindex_id we realize that we won't be able to
  // use this cindex_id (i.e. it may be computable but it's not used) because
  // its usable_count is zero, and in those cases we change the status to
  // kWillNotCompute even though the cindex-id may be computable.  For most
  // purposes this status is treated the same as kNotComputable.
  enum ComputableInfo {
    kUnknown = 0,
    kComputable = 1,
    kNotComputable = 2,
    kWillNotCompute = 3
  };

  struct CindexInfo {
    ComputableInfo computable;  // kUnknown, kComputable, kNotComputable
    int32 usable_count;   // usable_count_[i] for a cindex_id i is defined as 1 if i is a requested
    // output, and otherwise as the number of other cindex_ids j such that
    // computable_info_[j] is not kNotComputable AND usable_count_[j] > 0 AND i is
    // a member of graph->dependencies[j].  A cindex_id is termed "usable"
    // (meaning it could potentially participate in the computation of the output)
    // if its usable_count_ is > 0.  This quantity is designed to be easy to keep
    // updated as we add cindex_ids.

    // True if in current_queue_ or next_queue_.
    bool queued;

    // True if we have created the cindexes that this cindex depends on.
    bool dependencies_computed;

    CindexInfo(const CindexInfo &other) = default;
    CindexInfo(): computable(kUnknown),
                  usable_count(0),
                  queued(false),
                  dependencies_computed(false) { }
  };

 private:
  // This function, called from ExplainWhyNotComputable(), prints to "os"
  // a human-readable form of a given cindex_id, that looks like
  // some_network_node(n, t, x), e.g. "final_logsoftmax(0, -4, 0)".
  void PrintCindexId(std::ostream &os, int32 cindex_id) const;

  // This function, typically to be called just before dying, prints logging
  // information to explain why the given cindex_id is not computable.
  void ExplainWhyNotComputable(int32 cindex_id) const;

  // called at the start of Compute(), this populates the graph (and member
  // variables) for all the inputs specified in the computation request.
  void AddInputs();

  // called at the start of Compute(), this populates the graph (and member
  // variables, including current_queue_) with all the outputs specified in the
  // computation request.
  void AddOutputs();

  // this does one iteration of building the graph, and increases
  // current_distance_ by one, i.e. it searches at one more remove from
  // the output.
  void BuildGraphOneIter();

  // (called from BuildGraphOneIter()); make sure the computable_info for
  // cindex_id is up to date.  Has side effects: may update usable_count
  // values and add things to next_queue_.
  void UpdateComputableInfo(int32 cindex_id);

  // (called from BuildGraphOneIter()), this function sets the cindex_id to
  // status kWillNotCompute and places members of depend_on_this_ into the
  // computable queue if needed.
  void SetAsWillNotCompute(int32 cindex_id);

  // compute and return the ComputableInfo for this cindex_id (kUnknown,
  // kComputable or kNotComputable).
  ComputableInfo ComputeComputableInfo(int32 cindex_id) const;

  // To be called when this cindex_id has just been newly added to graph_, this
  // function adds a couple default variables associated with it, to *this.
  inline void AddCindexId(int32 cindex_id);

  // Add cindex_ids that this cindex_id depends on.
  void AddDependencies(int32 cindex_id);

  // increment the "usable" value of this cindex_id.
  void IncrementUsableCount(int32 cindex_id);

  // decrement the "usable" value of this cindex_id.
  void DecrementUsableCount(int32 cindex_id);

  // This function, called from Prune(), modifies the members of
  // graph_->dependencies-- it removes those cindexes that are not used in the
  // computation for the current cindex_id.  This will only do something
  // interesting in cases where there are optional dependencies.
  // It also clears the dependencies of those cindexes that are not computable.
  void PruneDependencies(int32 cindex_id);

  // This function, called from Prune(), computes an array "required", with an
  // element for each cindex_id that says whether it is required to compute the
  // requested outputs.  This is similar in function to the "usable_count_"
  // array, but it's more exact because it's computed after we have done
  // PruneDependencies() to remove unused dependencies, so it will only say
  // something is required if it is really accessed in the computation.
  // We'll later use this to remove unnecessary cindexes.
  // 'start_cindex_id' is the cindex_id from which the 'required' array is
  // to start (normally zero, but may be nonzero in multi-segment computations);
  // so 'required' is indexed by cindex_id - start_cindex_id.
  void ComputeRequiredArray(int32 start_cindex_id,
                            std::vector<bool> *required) const;

  // this function, to be called from Compute(), does some sanity checks to
  // verify that the internal state is consistent.  It only does this for the
  // current 'segment' of the computation, starting from 'start_cindex_id' (this
  // will be 0 in normal, single-segment computations).
  void Check(int32 start_cindex_id) const;

  const Nnet &nnet_;
  const ComputationRequest *request_;
  ComputationGraph *graph_;

  // this is the transpose of graph_->dependencies; it tells us
  // for each cindex_id, which other cindex_ids depend on it.
  std::vector<std::vector<int32> > depend_on_this_;


  // this vector is  indexed by cindex_id
  std::vector<CindexInfo> cindex_info_;

  // current_distance_ >= 0 is the distance to the output, of the cindex_ids in
  // current_queue_.
  int32 current_distance_;
  // the cindex_ids in current_queue_ are at no more than distance
  // "current_distance" to the output
  std::vector<int32> current_queue_;
  // the cindex_ids in next_queue_ are at no more than distance current_distance
  // + 1 to the output
  std::vector<int32> next_queue_;
};

std::ostream& operator << (std::ostream &os,
                           const ComputationGraphBuilder::ComputableInfo &info);


class CindexSet {
 public:
  bool operator () (const Cindex &cindex) const;

  CindexSet(const ComputationGraph &graph);

  CindexSet(const ComputationGraph &graph,
            const std::vector<ComputationGraphBuilder::CindexInfo> &info,
            bool treat_unknown_as_computable);
 private:
  const ComputationGraph &graph_;
  const std::vector<ComputationGraphBuilder::CindexInfo> *info_;
  bool treat_unknown_as_computable_;
};


class IndexSet {
 public:
  bool operator () (const Index &index) const;

  IndexSet(const ComputationGraph &graph,
           const std::vector<ComputationGraphBuilder::CindexInfo> &info,
           int32 node_id,
           bool treat_unknown_as_computable);
 private:
  const ComputationGraph &graph_;
  const std::vector<ComputationGraphBuilder::CindexInfo> &info_;
  int32 node_id_;
  bool treat_unknown_as_computable_;
};




void ComputeComputationPhases(
    const Nnet &nnet,
    const ComputationGraph &computation_graph,
    std::vector<std::vector<std::vector<int32> > > *phases_per_segment);


class ComputationStepsComputer {
 public:
  ComputationStepsComputer(const Nnet &nnet,
                           ComputationGraph *graph,
                           std::vector<std::vector<int32> > *steps,
                           std::vector<std::pair<int32, int32> > *locations);

  void ComputeForSegment(const ComputationRequest &request,
                         const std::vector<std::vector<int32> > &phases);

  void Check() const;
 private:

  // Adds step(s) for one "sub-phase".  A sub-phase is the set of cindex_ids from
  // one phase that have the same node index.  Note: for nodes that are
  // component-input descriptors, we don't actually create the step here, we
  // create it just before creating the step for its component, and we recreate
  // the list of cindexes from those from the component.  The reason is that
  // there are situations where doing it directly from the raw_step would not do
  // the right thing (especially with non-simple components, it's possible that
  // the cindexes component-input descriptors could be used twice by two
  // different components)..
  void ProcessSubPhase(const ComputationRequest &request,
                       const std::vector<Cindex> &sub_phase);

  // Called from ProcessSubPhase- for the case where it's a DimRangeNode.
  void ProcessDimRangeSubPhase(const std::vector<Cindex> &sub_phase);

  // Called from ProcessSubPhase- for the case where it's an input or output node.
  void ProcessInputOrOutputStep(const ComputationRequest &request,
                                bool is_output,
                                const std::vector<Cindex> &sub_phase);

  // Called from ProcessSubPhase- for the case where it's a component node.
  void ProcessComponentStep(const std::vector<Cindex> &step);


  // Splits a phase up into multiple "sub-phases", which are just the cindexes
  // from a phase that are from a single node, sorted.  At this point we
  // represent them as Cindexes, not cindex_ids.  For efficiency and because it
  // would be discarded anyway, it discards any raw steps that correspond to
  // component-input descriptors because these are not processed inside
  // ProcessSubPhase().
  void SplitIntoSubPhases(const std::vector<int32> &phase,
                          std::vector<std::vector<Cindex> > *sub_phase) const;

  // This low-level function used by functions like ProcessComponentStep,
  // ProcessInputStep and so on, adds one step to 'steps_' (converting from
  // Cindex to cindex_ids), and updates 'locations' appropriately.  It returns
  // the step index that we just added (== size of steps_ at entry).
  // If you specify add_if_absent = true, it will add any Cindexes that were
  // not already present, to the graph.  [this option is only to be used
  // in processing dim-range nodes.
  int32 AddStep(const std::vector<Cindex> &cindexes,
                bool add_if_absent = false);

  // This is an alternative interface to AddStep() that takes a list of
  // cindex_ids instead of cindexes (it's destructive of that list).
  int32 AddStep(std::vector<int32> *cindex_ids);


  // This utility function uses graph_ to convert a vector of cindex_ids into
  // Cindexes.
  void ConvertToCindexes(const std::vector<int32> &cindex_ids,
                         std::vector<Cindex> *cindexes) const;

  // Converts a vector of Cindexes to a vector of Indexes, by
  // stripping out the node index.
  static void ConvertToIndexes(const std::vector<Cindex> &cindexes,
                               std::vector<Index> *indexes);

  // Converts a vector of Indexes to Cindexes, using a supplied
  // node index.
  static void ConvertToCindexes(const std::vector<Index> &indexes,
                                int32 node_index,
                                std::vector<Cindex> *cindexes);


  // This utility function uses graph_ to convert a vector of cindex_ids into
  // Cindexes.   It will crash if the cindexes were not present in the graph.
  void ConvertToCindexIds(const std::vector<Cindex> &cindexes,
                          std::vector<int32> *cindex_ids) const;

  // This utility function uses the 'locations_' array to convert the cindex_ids
  // in 'cindex_ids' into an array (of the same length) of locations, i.e. of
  // pairs (step, index-into-step), so that if cindex_ids[i] = c, then
  // (*locations)[i] will be set to (*locations_)[c].  It will die if
  // one of the locations was not defined, i.e. was the pair (-1, -1).
  void ConvertToLocations(
      const std::vector<int32> &cindex_ids,
      std::vector<std::pair<int32, int32> > *locations) const;


  const Nnet &nnet_;
  ComputationGraph *graph_;
  std::vector<std::vector<int32> > *steps_;
  std::vector<std::pair<int32, int32> > *locations_;


  std::unordered_set<std::pair<int32, int32>, PairHasher<int32> > dim_range_nodes_;
};



} // namespace nnet3
} // namespace kaldi


#endif