nnet-analyze.h

Go to the documentation of this file.

// nnet3/nnet-analyze.h

// Copyright 2015-2017    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_ANALYZE_H_
#define KALDI_NNET3_NNET_ANALYZE_H_

#include "nnet3/nnet-compile.h"

#include <iostream>

namespace kaldi {
namespace nnet3 {


// This struct contains the attributes for a single command.  See class
// ComputationVariables for the meaning of a variable, which can be identified
// with a sub-part of a matrix.  Note, variables may be both read and written in
// the same command; e.g. for operations that do += or that write to only some
// elements of a variable (we can think of these as, for purposes of analysis,
// reading the remaining elements and writing them back.
struct CommandAttributes {
  // All of the vector variables below are made sorted and uniq by
  // ComputeCommandAttributes.

  // variables read
  std::vector<int32> variables_read;
  // variables written
  std::vector<int32> variables_written;

  // sub-matrices read (i.e. the submatrix appears in the command directly)
  std::vector<int32> submatrices_read;
  // sub-matrices written (i.e. the submatrix appears in the command directly)
  std::vector<int32> submatrices_written;

  // matrices read
  std::vector<int32> matrices_read;
  // matrices written
  std::vector<int32> matrices_written;

  // true if this command has side effects e.g. on the model (such as
  // Backprop on an updatable component, or StoreStats).
  bool has_side_effects;
  CommandAttributes(): has_side_effects(false) { }
};


void PrintCommandAttributes(std::ostream &os,
                            const std::vector<CommandAttributes> &attributes);


enum AccessType {
  kReadAccess,
  kWriteAccess,
  kReadWriteAccess
};


class ComputationVariables {
 public:
  // This function must only be called once per object.
  void Init(const NnetComputation &computation);

  // This function updates the CommandAttributes object to record an access of
  // type read, write or read-write on the variables that this sub-matrix
  // corresponds to, and also updates the matrices_accessed variable by adding
  // the number of the underlying matrix.  The slightly non-obvious thing it
  // does is that if the access type is given as write, and the sub-matrix does
  // not span the full row range of the matrix it belongs to (and hence does not
  // span the full extent of the variables that we defined), the access is
  // recorded as both read and write (because the result of the operation on
  // those depends on the pre-existing contents, so it would not be correct to
  // consider it just a write operation).
  void RecordAccessForSubmatrix(
      int32 submatrix_index,
      AccessType access_type,
      CommandAttributes *ca) const;

  void AppendVariablesForMatrix(
      int32 matrix_index,
      std::vector<int32> *variable_indexes) const;


  // Appends to variable_indexes the sorted list of variables corresponding to a
  // submatrix index.
  void AppendVariablesForSubmatrix(
      int32 submatrix_index,
      std::vector<int32> *variable_indexes) const;

  // note: variables are zero-indexed.
  int32 NumVariables() const { return num_variables_; }

  int32 GetMatrixForVariable(int32 variable) const;

  // returns a string that describes a variable in Matlab-like format (but with
  // zero indexing): something like "m1" or "m1(0:99,:)" or "m1(0:19,10:49)"
  std::string DescribeVariable(int32 variable) const;

  NnetComputation::SubMatrixInfo VariableInfo(int32 variable) const;
 private:
  // sets up split_points_, matrix_to_variable_index_, and num_variables_.
  // called from constructor.
  void ComputeSplitPoints(const NnetComputation &computation);
  // sets up variables_for_submatrix_, is_full_matrix_, and submatrix_to_matrix_.  called
  // from constructor.
  void ComputeVariablesForSubmatrix(const NnetComputation &computation);
  // sets up variable_to_matrix_.  called from constructor.
  void ComputeVariableToMatrix();

  // This function assumes that 'sorted_vec' is sorted and unique, and that
  // 'i' is an element of 'sorted_vec'; it returns the index of 'i' in vec,
  // i.e. the k such that sorted_vec[k] == i.
  static int32 FindIndexOf(const std::vector<int32> &sorted_vec, int32 i);


  // Indexed first by matrix-index and then a list, this gives us all the split
  // points at which column ranges start and end.  For instance, if the 3'rd
  // matrix has 20 columns and is split into ranges 0:9 and 10:19,
  // split_points_[3] would equal [0, 10, 20].  column_split_points_[0] will
  // always be empty because matrix-index zero is reserved for the empty matrix.
  std::vector<std::vector<int32> > column_split_points_;
  // This is as column_split_points_, except for row indexes instead of column
  // indexes.
  std::vector<std::vector<int32> > row_split_points_;

  // Maps from the matrix-index (note, zero is invalid as it corresponds to the
  // empty matrix) to the variable-index for its first split point.  for coding
  // convenience there is one extra element at the end, which is equal to the
  // total number of variables.
  // For each matrix m, the matrix has num-row-variables * num-column-variables
  // variables in total, where num-row-variables = row_split_points_[m].size() - 1, and
  // num-column-variables = column_split_points_[m].size() - 1.
  std::vector<int32> matrix_to_variable_index_;

  std::vector<int32> submatrix_to_matrix_;
  // indexed by submatrix index, this is true if the submatrix spans the full
  // row and column range of the underlying matrix.  Affects whether write operations
  // should be classed as write operations or as read-write operations.
  std::vector<bool> submatrix_is_whole_matrix_;


  // records the matrix index underlying each variable.
  std::vector<int32> variable_to_matrix_;

  int32 num_variables_;


  // For each submatrix, a list of the variables underlying it.
  std::vector<std::vector<int32> > variables_for_submatrix_;


};


// This struct records an access to a variable (i.e. a row and column range of a
// matrix).
struct Access {
  int32 command_index;
  AccessType access_type;
  Access(int32 command_index, AccessType access_type):
      command_index(command_index), access_type(access_type) { }
  bool operator < (const Access &other) const {
    return command_index < other.command_index;
  }
};


void ComputeVariableAccesses(
    const ComputationVariables &variables,
    const std::vector<CommandAttributes> &command_attributes,
    std::vector<std::vector<Access> > *variable_accesses);


struct MatrixAccesses {
  int32 allocate_command;
  int32 deallocate_command;
  std::vector<Access> accesses;
  bool is_input;
  bool is_output;
  MatrixAccesses(): allocate_command(-1), deallocate_command(-1),
                    is_input(false), is_output(false) { }
};

void ComputeMatrixAccesses(
    const Nnet &nnet,
    const NnetComputation &computation,
    const ComputationVariables &variables,
    const std::vector<CommandAttributes> &command_attributes,
    std::vector<MatrixAccesses> *matrix_accesses);

void PrintMatrixAccesses(std::ostream &os,
                         const std::vector<MatrixAccesses> &matrix_accesses);

struct Analyzer {
  ComputationVariables variables;
  std::vector<CommandAttributes> command_attributes;
  std::vector<std::vector<Access> > variable_accesses;
  std::vector<MatrixAccesses> matrix_accesses;
  void Init(const Nnet &nnet, const NnetComputation &computation);
};


class ComputationAnalysis {
 public:
  ComputationAnalysis(const NnetComputation &computation,
                      const Analyzer &analyzer): computation_(computation),
                                                 analyzer_(analyzer) { }

  int32 FirstNontrivialAccess(int32 s) const;

  int32 FirstAccess(int32 s) const;

  int32 LastAccess(int32 s) const;

  int32 LastWriteAccess(int32 s) const;

  int32 DataInvalidatedCommand(int32 c, int32 s) const;

  int32 FirstNontrivialMatrixAccess(int32 m) const;

  int32 LastMatrixAccess(int32 m) const;

 private:
  const NnetComputation &computation_;
  const Analyzer &analyzer_;
};


void ComputeMatrixToSubmatrix(const NnetComputation &computation,
                              std::vector<std::vector<int32> > *mat_to_submat);


int32 MaxMemoryUsage(const NnetComputation &computation);


// computes a vector of attributes, one for each Command in the computation.
void ComputeCommandAttributes(
    const Nnet &nnet,
    const NnetComputation &computation,
    const ComputationVariables &variables,
    std::vector<CommandAttributes> *attributes);


struct CheckComputationOptions {
  // do the check_rewrite check only for a non-optimized computation, it may
  // legitimately fail after optimization.  see code for details.
  bool check_rewrite;
  // If 'check_unused_variables' is true, it checks for unused variables
  // (e.g. unused parts of matrices).  We only set it false for online
  // computations, where there can be instances where a part of a matrix is
  // apparently never accessed (until we consider that the matrix is swapped
  // with another).
  bool check_unused_variables;

  CheckComputationOptions():
      check_rewrite(false), check_unused_variables(true) { }
};


// Note: this checker class does not work for online computations (that have a
// kGoto statement), but the function CheckComputation() is able to detect such
// computations and modify them in such a way that they can be checked by this
// class (and then do extra checks).
class ComputationChecker {
 public:
  ComputationChecker(const CheckComputationOptions &config,
                     const Nnet &nnet,
                     const NnetComputation &computation);
  void Check();  // call this only once.
 private:
  // Various dimension consistency checks and checks on properties.
  void CheckComputationIndexes() const;
  // Checks for a situation where an undefined variable is read.
  void CheckComputationUndefined() const;
  // Checks that all writes are done before reads.  details with implementation.
  void CheckComputationRewrite() const;
  // Check matrix accesses make sense.
  void CheckComputationMatrixAccesses() const;
  // Some checks related to the kCompressMatrix and kDecompressMatrix commands.
  void CheckComputationCompression() const;
  // Check debug_info has the correct size, if used.
  void CheckComputationDebugInfo() const;

  const CheckComputationOptions &config_;
  const Nnet &nnet_;
  const NnetComputation &computation_;
  Analyzer a_;
};


void GetCommandsOfType(const NnetComputation &computation,
                       CommandType t,
                       std::vector<int32> *command_indexes);

void CheckComputation(const Nnet &nnet,
                      const NnetComputation &computation,
                      bool check_rewrite = false);

// This function returns the maximum amount of memory (in bytes) that the
// computation uses at any point (this would be GPU memory if the computation
// were using a GPU).  This is based on allocations and deallocations of
// matrices, and input commands; it ignores any temporary allocation done inside
// Propagate() and Backprop() or other similar functions; it ignores precomputed
// indexes and other things residing in the computation; and of course it
// ignores things you might do with the output, such as the forward-backward
// code for chain computation.
int64 GetMaxMemoryUse(const NnetComputation &computation);


} // namespace nnet3
} // namespace kaldi


#endif