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

#include <nnet-optimize-utils.h>

Collaboration diagram for DerivativeTimeLimiter:

Classes

struct  MatrixPruneInfo
 

Public Member Functions

 DerivativeTimeLimiter (const Nnet &nnet, int32 min_deriv_time, int32 max_deriv_time, NnetComputation *computation)
 
void LimitDerivTimes ()
 

Private Member Functions

void ComputeMatrixPruneInfo ()
 
void ComputeSubmatrixMaps ()
 
void ModifyCommands ()
 
void PruneMatrices ()
 
void RemoveUnusedMemos ()
 
bool CanLimitMatrix (const Analyzer &analyzer, int32 matrix_index) const
 
void LimitMatrices (const std::vector< bool > &will_limit)
 
void MapSimpleMatrixCommand (NnetComputation::Command *c)
 
void MapIndexesCommand (NnetComputation::Command *c)
 
void MapIndexesMultiCommand (NnetComputation::Command *c)
 
void MapAddRowRangesCommand (NnetComputation::Command *c)
 
void ModifyCommand (NnetComputation::Command *command)
 
void ResizeMatrices ()
 
void GetPruneValues (int32 initial_submatrix, int32 new_submatrix, int32 *left_prune, int32 *right_prune) const
 
bool RowIsKept (int32 submatrix, int32 row_index) const
 

Private Attributes

const Nnetnnet_
 
int32 min_deriv_time_
 
int32 max_deriv_time_
 
NnetComputationcomputation_
 
std::vector< int32 > whole_submatrices_
 
std::vector< MatrixPruneInfomatrix_prune_info_
 
std::vector< int32 > submatrix_map_
 
std::vector< int32 > submatrix_map_if_deriv_
 
std::vector< MatrixPruneInfoprune_info_
 
std::unordered_set< int32 > memos_to_delete_
 

Detailed Description

Definition at line 223 of file nnet-optimize-utils.h.

Constructor & Destructor Documentation

DerivativeTimeLimiter ( const Nnet nnet,
int32  min_deriv_time,
int32  max_deriv_time,
NnetComputation computation 
)

Definition at line 1933 of file nnet-optimize-utils.cc.

1936  :
1937  nnet_(nnet),
1938  min_deriv_time_(min_deriv_time),
1939  max_deriv_time_(max_deriv_time),
1940  computation_(computation) { }

Member Function Documentation

bool CanLimitMatrix ( const Analyzer analyzer,
int32  matrix_index 
) const
inlineprivate

Definition at line 2073 of file nnet-optimize-utils.cc.

References ComputationVariables::AppendVariablesForSubmatrix(), NnetComputation::Command::command_type, NnetComputation::commands, DerivativeTimeLimiter::computation_, KALDI_ASSERT, KALDI_VLOG, kaldi::nnet3::kSetConst, DerivativeTimeLimiter::submatrix_map_, Analyzer::variable_accesses, Analyzer::variables, and DerivativeTimeLimiter::whole_submatrices_.

Referenced by DerivativeTimeLimiter::PruneMatrices().

2074  {
2075  int32 s_whole = whole_submatrices_[m]; // submatrix consisting of
2076  // all of the matrix m
2077  int32 s_mapped = submatrix_map_[s_whole]; // submatrix consisting of the time
2078  // range of the matrix m that we
2079  // plan to limit it to.
2080  KALDI_ASSERT(s_mapped != 0 && s_mapped != s_whole);
2081  std::vector<int32> whole_variables, mapped_variables;
2082  analyzer.variables.AppendVariablesForSubmatrix(s_whole,
2083  &whole_variables);
2084  analyzer.variables.AppendVariablesForSubmatrix(s_mapped,
2085  &mapped_variables);
2086  KALDI_ASSERT(whole_variables.size() > mapped_variables.size());
2087  std::vector<int32> excluded_variables(whole_variables.size() -
2088  mapped_variables.size());
2089  std::vector<int32>::iterator end_iter =
2090  std::set_difference(whole_variables.begin(), whole_variables.end(),
2091  mapped_variables.begin(), mapped_variables.end(),
2092  excluded_variables.begin());
2093  KALDI_ASSERT(end_iter == excluded_variables.end());
2094  // We want to make sure that none of the excluded variables are ever accessed,
2095  // except possibly for zeroing or setting to other constant value. If they
2096  // are, we cannot prune the matrix.
2097  for (std::vector<int32>::iterator iter = excluded_variables.begin();
2098  iter != end_iter; ++iter) {
2099  int32 variable_index = *iter;
2100  const std::vector<Access> &variable_accesses =
2101  analyzer.variable_accesses[variable_index];
2102  std::vector<Access>::const_iterator viter = variable_accesses.begin(),
2103  vend = variable_accesses.end();
2104  for (; viter != vend; ++viter) {
2105  // if a variable outside the pruned range of the matrix is ever accessed
2106  // apart from on allocation, we cannot prune.
2107  int32 command_index = viter->command_index;
2108  NnetComputation::Command &command = computation_->commands[command_index];
2109  if (command.command_type != kSetConst) {
2110  // we may one day want to look at this.. it's not really expected.
2111  KALDI_VLOG(3) << "Cannot prune matrix " << m;
2112  return false;
2113  }
2114  }
2115  }
2116  return true;
2117 }
std::vector< Command > commands
#define KALDI_ASSERT(cond)
Definition: kaldi-error.h:169
#define KALDI_VLOG(v)
Definition: kaldi-error.h:136
void ComputeMatrixPruneInfo ( )
private

Definition at line 1975 of file nnet-optimize-utils.cc.

References NnetComputation::MatrixDebugInfo::cindexes, DerivativeTimeLimiter::computation_, DerivativeTimeLimiter::MatrixPruneInfo::fully_inside_range, rnnlm::i, KALDI_ASSERT, NnetComputation::matrices, NnetComputation::matrix_debug_info, DerivativeTimeLimiter::matrix_prune_info_, DerivativeTimeLimiter::max_deriv_time_, DerivativeTimeLimiter::min_deriv_time_, DerivativeTimeLimiter::MatrixPruneInfo::partly_inside_range, DerivativeTimeLimiter::MatrixPruneInfo::row_begin, and DerivativeTimeLimiter::MatrixPruneInfo::row_end.

Referenced by DerivativeTimeLimiter::LimitDerivTimes().

1975  {
1977  computation_->matrices.size() &&
1978  "Limiting derivative times requires debug info.");
1979  const int32 num_matrices = computation_->matrices.size(),
1980  min_deriv_time = min_deriv_time_,
1981  max_deriv_time = max_deriv_time_;
1982  matrix_prune_info_.resize(num_matrices);
1983  // matrix_prune_info_[0] will remain undefined.
1984  for (int32 matrix_index = 1; matrix_index < num_matrices; matrix_index++) {
1985  NnetComputation::MatrixDebugInfo &debug_info =
1986  computation_->matrix_debug_info[matrix_index];
1987  MatrixPruneInfo &prune_info = matrix_prune_info_[matrix_index];
1988  const std::vector<Cindex> &cindexes = debug_info.cindexes;
1989  int32 num_rows = computation_->matrices[matrix_index].num_rows;
1990  KALDI_ASSERT(num_rows == static_cast<int32>(cindexes.size()));
1991  int32 first_row_within_range = num_rows,
1992  last_row_within_range = -1;
1993  for (int32 i = 0; i < num_rows; i++) {
1994  int32 t = cindexes[i].second.t;
1995  if (t >= min_deriv_time && t <= max_deriv_time) {
1996  if (i < first_row_within_range) first_row_within_range = i;
1997  if (i > last_row_within_range) last_row_within_range = i;
1998  }
1999  }
2000  if (last_row_within_range == -1) {
2001  prune_info.fully_inside_range = false;
2002  prune_info.partly_inside_range = false;
2003  } else if (last_row_within_range == num_rows - 1 &&
2004  first_row_within_range == 0) {
2005  prune_info.fully_inside_range = true;
2006  prune_info.partly_inside_range = false;
2007  } else {
2008  prune_info.fully_inside_range = false;
2009  prune_info.partly_inside_range = true;
2010  prune_info.row_begin = first_row_within_range;
2011  prune_info.row_end = last_row_within_range + 1;
2012  }
2013  }
2014 }
std::vector< MatrixDebugInfo > matrix_debug_info
std::vector< MatrixInfo > matrices
std::vector< MatrixPruneInfo > matrix_prune_info_
#define KALDI_ASSERT(cond)
Definition: kaldi-error.h:169
void ComputeSubmatrixMaps ( )
private

Definition at line 2016 of file nnet-optimize-utils.cc.

References DerivativeTimeLimiter::computation_, DerivativeTimeLimiter::MatrixPruneInfo::fully_inside_range, NnetComputation::matrix_debug_info, NnetComputation::SubMatrixInfo::matrix_index, DerivativeTimeLimiter::matrix_prune_info_, NnetComputation::NewSubMatrix(), NnetComputation::SubMatrixInfo::num_rows, DerivativeTimeLimiter::MatrixPruneInfo::partly_inside_range, DerivativeTimeLimiter::MatrixPruneInfo::row_begin, DerivativeTimeLimiter::MatrixPruneInfo::row_end, NnetComputation::SubMatrixInfo::row_offset, NnetComputation::submatrices, DerivativeTimeLimiter::submatrix_map_, and DerivativeTimeLimiter::submatrix_map_if_deriv_.

Referenced by DerivativeTimeLimiter::LimitDerivTimes().

2016  {
2017  int32 num_submatrices = computation_->submatrices.size();
2018  submatrix_map_.resize(num_submatrices);
2019  submatrix_map_if_deriv_.resize(num_submatrices);
2020  // index zero is for the empty submatrix.
2021  submatrix_map_[0] = 0;
2022  submatrix_map_if_deriv_[0] = 0;
2023  for (int32 s = 1; s < num_submatrices; s++) {
2024  NnetComputation::SubMatrixInfo &submatrix_info(computation_->submatrices[s]);
2025  int32 matrix_index = submatrix_info.matrix_index;
2026  int32 row_offset = submatrix_info.row_offset,
2027  num_rows = submatrix_info.num_rows;
2028  const MatrixPruneInfo &matrix_prune_info = matrix_prune_info_[matrix_index];
2029  if (matrix_prune_info.fully_inside_range) {
2030  submatrix_map_[s] = s;
2031  } else if (!matrix_prune_info.partly_inside_range) {
2032  // completely outside time range.
2033  submatrix_map_[s] = 0;
2034  } else {
2035  // the matrix is partly inside the time range.
2036  int32 pruned_row_begin = std::max(matrix_prune_info.row_begin,
2037  row_offset),
2038  pruned_row_end = std::min(matrix_prune_info.row_end,
2039  row_offset + num_rows);
2040  if (pruned_row_end <= pruned_row_begin) {
2041  // there was no overlap between the submatrix and the part
2042  // of the matrix that was inside the time range.
2043  submatrix_map_[s] = 0;
2044  } else {
2045  // caution: this invalidates the reference 'submatrix_info'.
2046  int32 row_offset_within_submatrix =
2047  pruned_row_begin - row_offset,
2048  new_num_rows = pruned_row_end - pruned_row_begin;
2049  submatrix_map_[s] =
2050  computation_->NewSubMatrix(s, row_offset_within_submatrix,
2051  new_num_rows, 0, -1);
2052  }
2053  }
2054  bool is_deriv = computation_->matrix_debug_info[matrix_index].is_deriv;
2055  submatrix_map_if_deriv_[s] = (is_deriv ?
2056  submatrix_map_[s] : s);
2057  }
2058 }
std::vector< MatrixDebugInfo > matrix_debug_info
int32 NewSubMatrix(int32 base_submatrix, int32 row_offset, int32 num_rows, int32 col_offset, int32 num_cols)
Convenience function used when adding new sub-matrices.
std::vector< MatrixPruneInfo > matrix_prune_info_
std::vector< SubMatrixInfo > submatrices
void GetPruneValues ( int32  initial_submatrix,
int32  new_submatrix,
int32 *  left_prune,
int32 *  right_prune 
) const
inlineprivate

Definition at line 1567 of file nnet-optimize-utils.cc.

References DerivativeTimeLimiter::computation_, KALDI_ASSERT, NnetComputation::SubMatrixInfo::matrix_index, NnetComputation::SubMatrixInfo::num_rows, NnetComputation::SubMatrixInfo::row_offset, and NnetComputation::submatrices.

Referenced by DerivativeTimeLimiter::MapAddRowRangesCommand(), DerivativeTimeLimiter::MapIndexesCommand(), DerivativeTimeLimiter::MapIndexesMultiCommand(), and DerivativeTimeLimiter::MapSimpleMatrixCommand().

1570  {
1571  KALDI_ASSERT(initial_submatrix > 0 && new_submatrix > 0);
1572  const NnetComputation::SubMatrixInfo
1573  initial_info = computation_->submatrices[initial_submatrix],
1574  new_info = computation_->submatrices[new_submatrix];
1575  KALDI_ASSERT(initial_info.matrix_index == new_info.matrix_index);
1576  *left_prune = new_info.row_offset - initial_info.row_offset;
1577  if (right_prune != NULL) {
1578  *right_prune = initial_info.num_rows - new_info.num_rows - *left_prune;
1579  KALDI_ASSERT(*left_prune >= 0 && *right_prune >= 0);
1580  }
1581 }
std::vector< SubMatrixInfo > submatrices
#define KALDI_ASSERT(cond)
Definition: kaldi-error.h:169
void LimitDerivTimes ( )

Definition at line 1942 of file nnet-optimize-utils.cc.

References DerivativeTimeLimiter::computation_, DerivativeTimeLimiter::ComputeMatrixPruneInfo(), DerivativeTimeLimiter::ComputeSubmatrixMaps(), NnetComputation::GetWholeSubmatrices(), KALDI_ASSERT, DerivativeTimeLimiter::max_deriv_time_, DerivativeTimeLimiter::min_deriv_time_, DerivativeTimeLimiter::ModifyCommands(), DerivativeTimeLimiter::PruneMatrices(), kaldi::nnet3::RemoveNoOps(), DerivativeTimeLimiter::RemoveUnusedMemos(), kaldi::nnet3::RenumberComputation(), and DerivativeTimeLimiter::whole_submatrices_.

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

1942  {
1944  if (min_deriv_time_ == std::numeric_limits<int32>::min() &&
1945  max_deriv_time_ == std::numeric_limits<int32>::max())
1946  return; // nothing to do.
1947 
1951  ModifyCommands();
1952  PruneMatrices();
1956 }
void RenumberComputation(NnetComputation *computation)
This function detects submatrices and matrices that are never used (e.g.
#define KALDI_ASSERT(cond)
Definition: kaldi-error.h:169
void RemoveNoOps(NnetComputation *computation)
Removes commands of type kNoOperation in the computation.
void GetWholeSubmatrices(std::vector< int32 > *whole_submatrices) const
void LimitMatrices ( const std::vector< bool > &  will_limit)
inlineprivate

Definition at line 2119 of file nnet-optimize-utils.cc.

References NnetComputation::MatrixDebugInfo::cindexes, NnetComputation::SubMatrixInfo::col_offset, DerivativeTimeLimiter::computation_, NnetComputation::IsWholeMatrix(), KALDI_ASSERT, NnetComputation::matrices, NnetComputation::matrix_debug_info, NnetComputation::SubMatrixInfo::matrix_index, DerivativeTimeLimiter::matrix_prune_info_, NnetComputation::SubMatrixInfo::num_cols, NnetComputation::MatrixInfo::num_rows, NnetComputation::SubMatrixInfo::num_rows, DerivativeTimeLimiter::MatrixPruneInfo::partly_inside_range, DerivativeTimeLimiter::MatrixPruneInfo::row_begin, DerivativeTimeLimiter::MatrixPruneInfo::row_end, NnetComputation::SubMatrixInfo::row_offset, and NnetComputation::submatrices.

Referenced by DerivativeTimeLimiter::PruneMatrices().

2119  {
2120  // first modify 'submatrices'.
2121  int32 num_submatrices = computation_->submatrices.size(),
2122  num_matrices = computation_->matrices.size();
2123  for (int32 s = 1; s < num_submatrices; s++) {
2124  NnetComputation::SubMatrixInfo &submat_info = computation_->submatrices[s];
2125  int32 m = submat_info.matrix_index;
2126  if (will_limit[m]) {
2127  // we need to do something...
2128  const MatrixPruneInfo &prune_info = matrix_prune_info_[m];
2129  int32 matrix_num_rows = prune_info.row_end - prune_info.row_begin;
2130  KALDI_ASSERT(matrix_num_rows > 0 &&
2131  matrix_num_rows < computation_->matrices[m].num_rows);
2132  KALDI_ASSERT(prune_info.partly_inside_range);
2133  int32 new_row_begin = submat_info.row_offset - prune_info.row_begin;
2134  if (new_row_begin >= 0 &&
2135  submat_info.num_rows + new_row_begin <= matrix_num_rows) {
2136  // If this submatrix is entirely inside the limited range of the matrix,
2137  // then we modify its row_offset to account for the truncation of
2138  // rows to the left.
2139  submat_info.row_offset = new_row_begin;
2140  } else {
2141  // This submatrix is not entirely inside the kept range of the matrix.
2142  // We assume that this submatrix is never accessed directly except (if
2143  // it was the whole matrix) for in allocation and deallocation commands,
2144  // since when we modified the computation we ensured this.
2145  if (computation_->IsWholeMatrix(s)) {
2146  // If it was the whole matrix then it may be used in allocation and
2147  // deallocation commands, so we should modify it to be the whole of the
2148  // new matrix, which will have fewer rows than before.
2149  submat_info.num_rows = matrix_num_rows;
2150  } else {
2151  // We believe this matrix should never be used. We give it a valid
2152  // but stupid size of num-rows=1, num-cols=1, so that if it ever does
2153  // get accessed it should produce an error.
2154  submat_info.row_offset = 0;
2155  submat_info.num_rows = 1;
2156  submat_info.col_offset = 0;
2157  submat_info.num_cols = 1;
2158  }
2159  }
2160  }
2161  }
2162  // next modify 'matrices'
2163  for (int32 m = 1; m < num_matrices; m++) {
2164  if (will_limit[m]) {
2165  const MatrixPruneInfo &prune_info = matrix_prune_info_[m];
2166  NnetComputation::MatrixInfo &matrix_info = computation_->matrices[m];
2167  if (!computation_->matrix_debug_info.empty()) {
2168  NnetComputation::MatrixDebugInfo &debug_info =
2170  std::vector<Cindex> &cindexes = debug_info.cindexes;
2171  KALDI_ASSERT(cindexes.size() == static_cast<size_t>(matrix_info.num_rows));
2172  cindexes.erase(cindexes.begin() + prune_info.row_end, cindexes.end());
2173  cindexes.erase(cindexes.begin(),
2174  cindexes.begin() + prune_info.row_begin);
2175  }
2176  matrix_info.num_rows = prune_info.row_end - prune_info.row_begin;
2177  // num_cols stays the same.
2178  }
2179  }
2180 }
std::vector< MatrixDebugInfo > matrix_debug_info
std::vector< MatrixInfo > matrices
bool IsWholeMatrix(int32 submatrix_index) const
std::vector< MatrixPruneInfo > matrix_prune_info_
std::vector< SubMatrixInfo > submatrices
#define KALDI_ASSERT(cond)
Definition: kaldi-error.h:169
void MapAddRowRangesCommand ( NnetComputation::Command c)
private

Definition at line 1863 of file nnet-optimize-utils.cc.

References NnetComputation::Command::arg1, NnetComputation::Command::arg2, NnetComputation::Command::arg3, NnetComputation::Command::command_type, DerivativeTimeLimiter::computation_, DerivativeTimeLimiter::GetPruneValues(), rnnlm::i, NnetComputation::indexes_ranges, KALDI_ASSERT, kaldi::nnet3::kNoOperation, DerivativeTimeLimiter::RowIsKept(), NnetComputation::submatrices, and DerivativeTimeLimiter::submatrix_map_if_deriv_.

Referenced by DerivativeTimeLimiter::ModifyCommand().

1864  {
1865  int32 dest_submatrix = c->arg1,
1866  src_submatrix = c->arg2,
1867  indexes_ranges_index = c->arg3;
1868  int32 dest_submatrix_mapped = submatrix_map_if_deriv_[dest_submatrix],
1869  src_submatrix_mapped = submatrix_map_if_deriv_[src_submatrix];
1870  if (dest_submatrix_mapped == dest_submatrix &&
1871  src_submatrix_mapped == src_submatrix)
1872  return;
1873  if (dest_submatrix_mapped == 0 || src_submatrix_mapped == 0) {
1874  c->command_type = kNoOperation;
1875  return;
1876  }
1877  int32 dest_num_rows = computation_->submatrices[dest_submatrix_mapped].num_rows,
1878  src_num_rows = computation_->submatrices[src_submatrix_mapped].num_rows,
1879  src_left_prune, dest_left_prune;
1880  GetPruneValues(dest_submatrix, dest_submatrix_mapped,
1881  &dest_left_prune, NULL);
1882  GetPruneValues(src_submatrix, src_submatrix_mapped,
1883  &src_left_prune, NULL);
1884  const std::vector<std::pair<int32,int32> > &old_indexes_ranges(
1885  computation_->indexes_ranges[indexes_ranges_index]);
1886  std::vector<std::pair<int32,int32> > new_indexes_ranges(dest_num_rows);
1887 
1888  bool must_keep_command = false;
1889  for (int32 i = 0; i < dest_num_rows; i++) {
1890  std::pair<int32, int32> &this_pair = new_indexes_ranges[i];
1891  this_pair = old_indexes_ranges[i + dest_left_prune];
1892 
1893  int32 start = this_pair.first, end = this_pair.second;
1894  if (!RowIsKept(dest_submatrix_mapped, i)) {
1895  start = -1;
1896  end = -1;
1897  } else if (start >= 0) {
1898  // no need to change start, end if they are (-1, -1).
1899  // Note: this code is not optimally efficient, as RowIsKept
1900  // has a bunch of statements that we could cache some variables
1901  // for, but this command is pretty rare so not worth to optimize
1902  // at this point.
1903  while (start < end && !RowIsKept(src_submatrix, start))
1904  start++;
1905  while (end > start && !RowIsKept(src_submatrix, end - 1))
1906  end--;
1907  if (start == end) {
1908  start = -1;
1909  end = -1;
1910  } else {
1911  start -= src_left_prune;
1912  end -= src_left_prune;
1913  must_keep_command = true;
1914  // the next assert is because if we were outside the 'kept' part of the
1915  // submatrix, RowIsKept() should have instructed us to modify the value.
1916  KALDI_ASSERT(start >= 0 && end <= src_num_rows && start < end);
1917  }
1918  }
1919  this_pair.first = start;
1920  this_pair.second = end;
1921  }
1922  if (must_keep_command) {
1923  c->arg1 = dest_submatrix_mapped;
1924  c->arg2 = src_submatrix_mapped;
1925  c->arg3 = computation_->indexes_ranges.size();
1926  computation_->indexes_ranges.push_back(new_indexes_ranges);
1927  } else {
1928  c->command_type = kNoOperation;
1929  }
1930 }
void GetPruneValues(int32 initial_submatrix, int32 new_submatrix, int32 *left_prune, int32 *right_prune) const
std::vector< SubMatrixInfo > submatrices
#define KALDI_ASSERT(cond)
Definition: kaldi-error.h:169
bool RowIsKept(int32 submatrix, int32 row_index) const
std::vector< std::vector< std::pair< int32, int32 > > > indexes_ranges
void MapIndexesCommand ( NnetComputation::Command c)
private

Definition at line 1738 of file nnet-optimize-utils.cc.

References NnetComputation::Command::arg1, NnetComputation::Command::arg2, NnetComputation::Command::arg3, NnetComputation::Command::command_type, DerivativeTimeLimiter::computation_, DerivativeTimeLimiter::GetPruneValues(), rnnlm::i, NnetComputation::indexes, KALDI_ASSERT, kaldi::nnet3::kNoOperation, DerivativeTimeLimiter::RowIsKept(), NnetComputation::submatrices, and DerivativeTimeLimiter::submatrix_map_if_deriv_.

Referenced by DerivativeTimeLimiter::ModifyCommand().

1738  {
1739  int32 output_submatrix = c->arg1,
1740  input_submatrix = c->arg2;
1741  int32 input_submatrix_mapped = submatrix_map_if_deriv_[input_submatrix],
1742  output_submatrix_mapped = submatrix_map_if_deriv_[output_submatrix];
1743  // input_submatrix_mapped and output_submatrix_mapped map both submatrices to
1744  // just the portion that we are treating as nonzero.
1745 
1746  if (input_submatrix_mapped == 0 ||
1747  output_submatrix_mapped == 0) {
1748  // Either input or output is all zeros; make the command a no-op.
1749  // It may not be obvious that in the case of kCopyRows it would
1750  // be valid to make this a no-op (because what if the existing
1751  // contents were nonzero?), but we insist that this optimization
1752  // come before optimizations, and we know that the originally
1753  // generated computation would not overwrite a nonzero value
1754  // (and there are no undefined values because we make sure to
1755  // initialize everything with zeros; ununitialized values are
1756  // allowed only at a later optimization stage.
1757  c->command_type = kNoOperation;
1758  return;
1759  }
1760  const std::vector<int32> &old_indexes = computation_->indexes[c->arg3];
1761 
1762  int32 left_prune_input, left_prune_output;
1763  GetPruneValues(input_submatrix, input_submatrix_mapped,
1764  &left_prune_input, NULL);
1765  GetPruneValues(output_submatrix, output_submatrix_mapped,
1766  &left_prune_output, NULL);
1767  int32 new_num_input_rows =
1768  computation_->submatrices[input_submatrix_mapped].num_rows,
1769  new_num_output_rows =
1770  computation_->submatrices[output_submatrix_mapped].num_rows;
1771  std::vector<int32> new_indexes(new_num_output_rows);
1772  bool must_keep_command = false;
1773  for (int32 i = 0; i < new_num_output_rows; i++) {
1774  // the index into the 'new_indexes' vector is the row of the output
1775  // submatrix; the value is the row of the input submatrix.
1776  int32 orig_index = old_indexes[i + left_prune_output];
1777  if (orig_index == -1 ||
1778  !RowIsKept(input_submatrix, orig_index) ||
1779  !RowIsKept(output_submatrix_mapped, i)) {
1780  new_indexes[i] = -1;
1781  } else {
1782  int32 mapped_index = orig_index - left_prune_input;
1783  // we can do the following assert because the RowIsKept command
1784  // would have turned it into a -1 if not.
1785  KALDI_ASSERT(mapped_index >= 0 && mapped_index < new_num_input_rows);
1786  new_indexes[i] = mapped_index;
1787  must_keep_command = true;
1788  }
1789  }
1790  if (!must_keep_command) {
1791  c->command_type = kNoOperation;
1792  return;
1793  }
1794  int32 new_indexes_index = computation_->indexes.size();
1795  computation_->indexes.push_back(new_indexes);
1796  c->arg1 = output_submatrix_mapped;
1797  c->arg2 = input_submatrix_mapped;
1798  c->arg3 = new_indexes_index;
1799 }
void GetPruneValues(int32 initial_submatrix, int32 new_submatrix, int32 *left_prune, int32 *right_prune) const
std::vector< SubMatrixInfo > submatrices
#define KALDI_ASSERT(cond)
Definition: kaldi-error.h:169
std::vector< std::vector< int32 > > indexes
bool RowIsKept(int32 submatrix, int32 row_index) const
void MapIndexesMultiCommand ( NnetComputation::Command c)
private

Definition at line 1801 of file nnet-optimize-utils.cc.

References NnetComputation::Command::arg1, NnetComputation::Command::arg2, NnetComputation::Command::command_type, DerivativeTimeLimiter::computation_, DerivativeTimeLimiter::GetPruneValues(), rnnlm::i, NnetComputation::indexes_multi, KALDI_ASSERT, kaldi::nnet3::kNoOperation, DerivativeTimeLimiter::RowIsKept(), NnetComputation::submatrices, and DerivativeTimeLimiter::submatrix_map_if_deriv_.

Referenced by DerivativeTimeLimiter::ModifyCommand().

1801  {
1802  int32 dest_submatrix = c->arg1,
1803  indexes_multi_arg = c->arg2;
1804  int32 dest_submatrix_mapped = submatrix_map_if_deriv_[dest_submatrix];
1805  if (dest_submatrix_mapped == 0) {
1806  // The destination matrix is completely outside the allowed time range.
1807  c->command_type = kNoOperation;
1808  return;
1809  }
1810  int32 left_prune;
1811  GetPruneValues(dest_submatrix, dest_submatrix_mapped, &left_prune, NULL);
1812  int32 new_num_rows = computation_->submatrices[dest_submatrix_mapped].num_rows;
1813  const std::vector<std::pair<int32, int32> > &old_indexes_multi(
1814  computation_->indexes_multi[indexes_multi_arg]);
1815  std::vector<std::pair<int32, int32> > new_indexes_multi(new_num_rows);
1816  bool must_keep_command = false;
1817  for (int32 i = 0; i < new_num_rows; i++) {
1818  std::pair<int32,int32> &this_pair = new_indexes_multi[i];
1819  this_pair = old_indexes_multi[i + left_prune];
1820  // note: 'this_submatrix' is the source submatrix, from where we copy or add
1821  // the the data; 'this_row' is the source row.
1822  int32 this_submatrix = this_pair.first,
1823  this_row = this_pair.second;
1824  if (this_submatrix == -1) // don't map the (-1, -1) pairs.
1825  continue;
1826  if (!RowIsKept(this_submatrix, this_row) ||
1827  !RowIsKept(dest_submatrix_mapped, i)) {
1828  this_pair.first = -1;
1829  this_pair.second = -1;
1830  continue;
1831  }
1832  int32 this_submatrix_mapped = submatrix_map_if_deriv_[this_submatrix];
1833 
1834  // Reason for the assert below: if this_submatrix_mapped was 0, then all the
1835  // values in it should be not-kept, but RowIsKept above returned true, so
1836  // this would be a code error.
1837  KALDI_ASSERT(this_submatrix_mapped != 0);
1838 
1839  int32 this_left_prune, this_num_rows =
1840  computation_->submatrices[this_submatrix_mapped].num_rows;
1841  GetPruneValues(this_submatrix, this_submatrix_mapped,
1842  &this_left_prune, NULL);
1843  int32 this_row_mapped = this_row - this_left_prune;
1844  // the above assert is there because if it was going to be outside the
1845  // kept range, RowIsKept should have returned false above.
1846  KALDI_ASSERT(this_row_mapped >= 0 && this_row_mapped < this_num_rows);
1847  this_pair.first = this_submatrix_mapped;
1848  this_pair.second = this_row_mapped;
1849  must_keep_command = true;
1850  }
1851  if (!must_keep_command) {
1852  c->command_type = kNoOperation;
1853  return;
1854  }
1855  if (dest_submatrix_mapped == dest_submatrix &&
1856  new_indexes_multi == old_indexes_multi) // nothing changed.
1857  return;
1858  c->arg1 = dest_submatrix_mapped;
1859  c->arg2 = computation_->indexes_multi.size();
1860  computation_->indexes_multi.push_back(new_indexes_multi);
1861 }
void GetPruneValues(int32 initial_submatrix, int32 new_submatrix, int32 *left_prune, int32 *right_prune) const
std::vector< std::vector< std::pair< int32, int32 > > > indexes_multi
std::vector< SubMatrixInfo > submatrices
#define KALDI_ASSERT(cond)
Definition: kaldi-error.h:169
bool RowIsKept(int32 submatrix, int32 row_index) const
void MapSimpleMatrixCommand ( NnetComputation::Command c)
private

Definition at line 1689 of file nnet-optimize-utils.cc.

References NnetComputation::Command::arg1, NnetComputation::Command::arg2, NnetComputation::Command::command_type, DerivativeTimeLimiter::computation_, DerivativeTimeLimiter::GetPruneValues(), kaldi::nnet3::kNoOperation, NnetComputation::NewSubMatrix(), NnetComputation::submatrices, and DerivativeTimeLimiter::submatrix_map_if_deriv_.

Referenced by DerivativeTimeLimiter::ModifyCommand().

1689  {
1690  int32 submatrix1 = c->arg1,
1691  submatrix2 = c->arg2;
1692  int32 submatrix1_mapped = submatrix_map_if_deriv_[submatrix1],
1693  submatrix2_mapped = submatrix_map_if_deriv_[submatrix2];
1694  if (submatrix1_mapped == submatrix1 &&
1695  submatrix2_mapped == submatrix2) {
1696  // nothing to do.
1697  return;
1698  }
1699  if (submatrix1_mapped == 0 || submatrix2_mapped == 0) {
1700  // remove the operation-- it has nothing to do.
1701  c->command_type = kNoOperation;
1702  return;
1703  }
1704  // left_prune1 is the number of rows pruned away on the left for submatrix1.
1705  int32 orig_num_rows = computation_->submatrices[submatrix1].num_rows,
1706  left_prune1, left_prune2, right_prune1, right_prune2;
1707  GetPruneValues(submatrix1, submatrix1_mapped, &left_prune1, &right_prune1);
1708  GetPruneValues(submatrix2, submatrix2_mapped, &left_prune2, &right_prune2);
1709  if (left_prune1 == left_prune2 && right_prune1 == right_prune2) {
1710  // we took the same number of rows away from the left and right for
1711  // both arguments; the normal mapped values will work in this case
1712  c->arg1 = submatrix1_mapped;
1713  c->arg2 = submatrix2_mapped;
1714  } else {
1715  // there is some kind of mismatch- we'll prune back to what remains
1716  // after applying the maximum pruning on the left and right.
1717  int32 left_prune = std::max(left_prune1, left_prune2),
1718  right_prune = std::max(right_prune1, right_prune2);
1719  if (left_prune + right_prune >= orig_num_rows) {
1720  // everything was pruned away; remove the operation.
1721  c->command_type = kNoOperation;
1722  return;
1723  } else {
1724  int32 num_rows = orig_num_rows - left_prune - right_prune;
1725  // note: the call NewSubMatrix effectively gives us a sub-matrix of a
1726  // sub-matrix.
1727  c->arg1 = computation_->NewSubMatrix(submatrix1,
1728  left_prune, num_rows, 0, -1);
1729  c->arg2 = computation_->NewSubMatrix(submatrix2,
1730  left_prune, num_rows, 0, -1);
1731  }
1732  }
1733 }
void GetPruneValues(int32 initial_submatrix, int32 new_submatrix, int32 *left_prune, int32 *right_prune) const
int32 NewSubMatrix(int32 base_submatrix, int32 row_offset, int32 num_rows, int32 col_offset, int32 num_cols)
Convenience function used when adding new sub-matrices.
std::vector< SubMatrixInfo > submatrices
void ModifyCommand ( NnetComputation::Command command)
private

Definition at line 1607 of file nnet-optimize-utils.cc.

References NnetComputation::Command::arg1, NnetComputation::Command::arg3, NnetComputation::Command::arg4, NnetComputation::Command::arg5, NnetComputation::Command::arg6, NnetComputation::Command::arg7, NnetComputation::Command::command_type, Nnet::GetComponent(), kaldi::nnet3::kAcceptInput, kaldi::nnet3::kAddRowRanges, kaldi::nnet3::kAddRows, kaldi::nnet3::kAddRowsMulti, kaldi::nnet3::kAddToRowsMulti, KALDI_ASSERT, KALDI_ERR, kaldi::nnet3::kAllocMatrix, kaldi::nnet3::kBackprop, kaldi::nnet3::kBackpropNoModelUpdate, kaldi::nnet3::kCopyRows, kaldi::nnet3::kCopyRowsMulti, kaldi::nnet3::kCopyToRowsMulti, kaldi::nnet3::kDeallocMatrix, kaldi::nnet3::kMatrixAdd, kaldi::nnet3::kMatrixCopy, kaldi::nnet3::kNoOperation, kaldi::nnet3::kNoOperationMarker, kaldi::nnet3::kNoOperationPermanent, kaldi::nnet3::kPropagate, kaldi::nnet3::kProvideOutput, kaldi::nnet3::kSetConst, kaldi::nnet3::kSimpleComponent, kaldi::nnet3::kSwapMatrix, kaldi::nnet3::kUsesMemo, DerivativeTimeLimiter::MapAddRowRangesCommand(), DerivativeTimeLimiter::MapIndexesCommand(), DerivativeTimeLimiter::MapIndexesMultiCommand(), DerivativeTimeLimiter::MapSimpleMatrixCommand(), DerivativeTimeLimiter::memos_to_delete_, DerivativeTimeLimiter::nnet_, Component::Properties(), and DerivativeTimeLimiter::submatrix_map_.

Referenced by DerivativeTimeLimiter::ModifyCommands().

1607  {
1608  CommandType command_type = command->command_type;
1609  switch (command_type) {
1610  case kAllocMatrix:
1611  case kDeallocMatrix:
1612  case kSetConst:
1613  case kSwapMatrix:
1614  break; // we'll deal with allocation and deallocation later on.
1615  case kPropagate:
1616  // Propagate commands are unchanged, except that if the output of the
1617  // propagate is completely outside the accepted time-range (only likely if
1618  // we're inside a recurrency), then we don't store stats; this is not
1619  // really important, and is mostly done to minimize the difference from an
1620  // older version of the code, to reduce the need for testing.
1621  if (submatrix_map_[command->arg4] == 0)
1622  command->arg6 = 0;
1623  break;
1624  case kBackpropNoModelUpdate: // we actually don't expect to encounter this,
1625  // but it's trivial to support as it's the
1626  // same as backprop.
1627  case kBackprop: {
1628  const Component *component = nnet_.GetComponent(command->arg1);
1629  int32 properties = component->Properties();
1630  if (!(properties & kSimpleComponent)) {
1631  // we don't (yet) do this optimization for non-simple Components...
1632  // it would be a bit more complicated as we'd have to recompute the
1633  // PrecomputedIndexes.
1634  break;
1635  }
1636  int32 input_submatrix = command->arg3,
1637  output_submatrix = command->arg4,
1638  output_deriv_submatrix = command->arg5,
1639  input_deriv_submatrix = command->arg6;
1640  int32 mapped_input_submatrix = submatrix_map_[input_submatrix],
1641  mapped_output_submatrix = submatrix_map_[output_submatrix],
1642  mapped_output_deriv_submatrix = submatrix_map_[output_deriv_submatrix],
1643  mapped_input_deriv_submatrix = submatrix_map_[input_deriv_submatrix];
1644 
1645  if (mapped_output_deriv_submatrix == 0) {
1646  // completely outside range..
1647  KALDI_ASSERT(mapped_input_deriv_submatrix == 0 &&
1648  mapped_input_submatrix == 0 &&
1649  mapped_output_submatrix == 0);
1650  // just delete the command.
1651  command->command_type = kNoOperation;
1652  if (command->arg7 > 0)
1653  memos_to_delete_.insert(command->arg7);
1654  } else if (mapped_output_deriv_submatrix !=
1655  output_deriv_submatrix &&
1656  !(properties & kUsesMemo)) {
1657  // we're operating on a range of the input or output.
1658  // we can't do this type of mapping of the component uses
1659  // a memo, though.
1660  command->arg3 = mapped_input_submatrix;
1661  command->arg4 = mapped_output_submatrix;
1662  command->arg5 = mapped_output_deriv_submatrix;
1663  command->arg6 = mapped_input_deriv_submatrix;
1664  }
1665  break;
1666  }
1667  case kMatrixCopy: case kMatrixAdd:
1668  MapSimpleMatrixCommand(command);
1669  break;
1670  case kCopyRows: case kAddRows:
1671  MapIndexesCommand(command);
1672  break;
1673  case kCopyRowsMulti: case kCopyToRowsMulti:
1674  case kAddRowsMulti: case kAddToRowsMulti:
1675  MapIndexesMultiCommand(command);
1676  break;
1677  case kAddRowRanges: {
1678  MapAddRowRangesCommand(command);
1679  break;
1680  }
1681  case kAcceptInput: case kProvideOutput:
1683  break;
1684  default:
1685  KALDI_ERR << "Un-handled command type.";
1686  }
1687 }
CommandType
CommandType is an enum that describes the category of the command used in the NnetComputation.
void MapAddRowRangesCommand(NnetComputation::Command *c)
virtual int32 Properties() const =0
Return bitmask of the component's properties.
void MapIndexesMultiCommand(NnetComputation::Command *c)
std::unordered_set< int32 > memos_to_delete_
#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 MapIndexesCommand(NnetComputation::Command *c)
#define KALDI_ASSERT(cond)
Definition: kaldi-error.h:169
void MapSimpleMatrixCommand(NnetComputation::Command *c)
void ModifyCommands ( )
private

Definition at line 2060 of file nnet-optimize-utils.cc.

References NnetComputation::commands, DerivativeTimeLimiter::computation_, and DerivativeTimeLimiter::ModifyCommand().

Referenced by DerivativeTimeLimiter::LimitDerivTimes().

2060  {
2061  std::vector<NnetComputation::Command>::iterator
2062  iter = computation_->commands.begin(),
2063  end = computation_->commands.end();
2064  for (; iter != end; ++iter)
2065  ModifyCommand(&(*iter));
2066 }
std::vector< Command > commands
void ModifyCommand(NnetComputation::Command *command)
void PruneMatrices ( )
private

Definition at line 2182 of file nnet-optimize-utils.cc.

References DerivativeTimeLimiter::CanLimitMatrix(), DerivativeTimeLimiter::computation_, DerivativeTimeLimiter::MatrixPruneInfo::fully_inside_range, Analyzer::Init(), MatrixAccesses::is_input, MatrixAccesses::is_output, KALDI_ASSERT, DerivativeTimeLimiter::LimitMatrices(), NnetComputation::matrices, Analyzer::matrix_accesses, NnetComputation::matrix_debug_info, DerivativeTimeLimiter::matrix_prune_info_, kaldi::nnet3::MatrixIsUnused(), DerivativeTimeLimiter::nnet_, DerivativeTimeLimiter::MatrixPruneInfo::partly_inside_range, kaldi::nnet3::RemoveCommandsForUnusedMatrix(), and DerivativeTimeLimiter::whole_submatrices_.

Referenced by DerivativeTimeLimiter::LimitDerivTimes().

2182  {
2183  Analyzer analyzer;
2184  analyzer.Init(nnet_, *computation_);
2186  int32 num_matrices = computation_->matrices.size();
2187  std::vector<bool> will_limit(num_matrices, false);
2188  bool will_limit_at_least_one = false;
2189  for (int32 m = 1; m < num_matrices; m++) {
2190  const MatrixAccesses &accesses = analyzer.matrix_accesses[m];
2191  const MatrixPruneInfo &matrix_prune_info = matrix_prune_info_[m];
2192  if (matrix_prune_info.fully_inside_range ||
2193  accesses.is_input || accesses.is_output ||
2194  !computation_->matrix_debug_info[m].is_deriv)
2195  continue; // nothing to do: it's inside the time-range or not a
2196  // derivative.
2197  // if we got here it's not completely inside the time range, not an input or
2198  // an output, and it's a derivative.
2199  if (!matrix_prune_info.partly_inside_range) {
2200  // completely outside time range. we can prune the matrix if it is not an
2201  // input or output, and is never accessed apart from allocation.
2202  if (MatrixIsUnused(analyzer, *computation_, m))
2204  } else {
2205  // the matrix is partly inside the time range, it's a derivative, and not
2206  // an input or an output.
2207  if (CanLimitMatrix(analyzer, m)) {
2208  will_limit[m] = true;
2209  will_limit_at_least_one = true;
2210  }
2211  }
2212  }
2213  if (will_limit_at_least_one)
2214  LimitMatrices(will_limit);
2215 }
bool MatrixIsUnused(const Analyzer &analyzer, const NnetComputation &computation, int32 m)
This function returns true if matrix 1 <= m < computation->matrices.size() is unused, defined as: it is not an input or an output, and is not accessed other than via commands of type kAllocMatrix, kDeallocMatrix, and kSetConst.
std::vector< MatrixDebugInfo > matrix_debug_info
std::vector< MatrixInfo > matrices
void LimitMatrices(const std::vector< bool > &will_limit)
std::vector< MatrixPruneInfo > matrix_prune_info_
#define KALDI_ASSERT(cond)
Definition: kaldi-error.h:169
void RemoveCommandsForUnusedMatrix(const Analyzer &analyzer, int32 m, NnetComputation *computation)
This function removes from 'computation' the commands accessing matrix 'm', which is assumed to be un...
bool CanLimitMatrix(const Analyzer &analyzer, int32 matrix_index) const
void RemoveUnusedMemos ( )
private

Definition at line 1958 of file nnet-optimize-utils.cc.

References NnetComputation::Command::arg5, NnetComputation::Command::command_type, NnetComputation::commands, DerivativeTimeLimiter::computation_, KALDI_ASSERT, kaldi::nnet3::kPropagate, and DerivativeTimeLimiter::memos_to_delete_.

Referenced by DerivativeTimeLimiter::LimitDerivTimes().

1958  {
1959  if (memos_to_delete_.empty())
1960  return;
1961  size_t num_commands = computation_->commands.size(),
1962  num_memos_removed = 0;
1963  for (size_t command_index = 0; command_index < num_commands;
1964  command_index++) {
1965  NnetComputation::Command &c = computation_->commands[command_index];
1966  if (c.command_type == kPropagate &&
1967  memos_to_delete_.count(c.arg5) != 0) {
1968  c.arg5 = 0;
1969  num_memos_removed++;
1970  }
1971  }
1972  KALDI_ASSERT(num_memos_removed == memos_to_delete_.size());
1973 }
std::vector< Command > commands
std::unordered_set< int32 > memos_to_delete_
#define KALDI_ASSERT(cond)
Definition: kaldi-error.h:169
void ResizeMatrices ( )
private
bool RowIsKept ( int32  submatrix,
int32  row_index 
) const
private

Definition at line 1583 of file nnet-optimize-utils.cc.

References NnetComputation::MatrixDebugInfo::cindexes, DerivativeTimeLimiter::computation_, NnetComputation::MatrixDebugInfo::is_deriv, KALDI_ASSERT, NnetComputation::matrix_debug_info, DerivativeTimeLimiter::max_deriv_time_, DerivativeTimeLimiter::min_deriv_time_, and NnetComputation::submatrices.

Referenced by DerivativeTimeLimiter::MapAddRowRangesCommand(), DerivativeTimeLimiter::MapIndexesCommand(), and DerivativeTimeLimiter::MapIndexesMultiCommand().

1585  {
1586  KALDI_ASSERT(submatrix > 0 && submatrix < computation_->submatrices.size());
1587  const NnetComputation::SubMatrixInfo &info =
1588  computation_->submatrices[submatrix];
1589  KALDI_ASSERT(row_index >= 0 &&
1590  row_index < computation_->submatrices[submatrix].num_rows);
1591  int32 matrix_index = info.matrix_index;
1592  const NnetComputation::MatrixDebugInfo
1593  &debug_info = computation_->matrix_debug_info[matrix_index];
1594  if (!debug_info.is_deriv) {
1595  // the derivative time limitation doesn't apply to things that aren't
1596  // derivatives.
1597  return true;
1598  }
1599  int32 t = debug_info.cindexes[row_index + info.row_offset].second.t;
1600  return (t >= min_deriv_time_ && t <= max_deriv_time_);
1601 }
std::vector< MatrixDebugInfo > matrix_debug_info
std::vector< SubMatrixInfo > submatrices
#define KALDI_ASSERT(cond)
Definition: kaldi-error.h:169

Member Data Documentation

std::unordered_set<int32> memos_to_delete_
private
const Nnet& nnet_
private
std::vector<MatrixPruneInfo> prune_info_
private

Definition at line 360 of file nnet-optimize-utils.h.

std::vector<int32> whole_submatrices_
private

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