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 226 of file nnet-optimize-utils.h.

Constructor & Destructor Documentation

◆ DerivativeTimeLimiter()

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

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

1933  :
1934  nnet_(nnet),
1935  min_deriv_time_(min_deriv_time),
1936  max_deriv_time_(max_deriv_time),
1937  computation_(computation) { }

Member Function Documentation

◆ CanLimitMatrix()

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

Definition at line 2070 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().

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

◆ ComputeMatrixPruneInfo()

void ComputeMatrixPruneInfo ( )
private

Definition at line 1972 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().

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

◆ ComputeSubmatrixMaps()

void ComputeSubmatrixMaps ( )
private

Definition at line 2013 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().

2013  {
2014  int32 num_submatrices = computation_->submatrices.size();
2015  submatrix_map_.resize(num_submatrices);
2016  submatrix_map_if_deriv_.resize(num_submatrices);
2017  // index zero is for the empty submatrix.
2018  submatrix_map_[0] = 0;
2019  submatrix_map_if_deriv_[0] = 0;
2020  for (int32 s = 1; s < num_submatrices; s++) {
2021  NnetComputation::SubMatrixInfo &submatrix_info(computation_->submatrices[s]);
2022  int32 matrix_index = submatrix_info.matrix_index;
2023  int32 row_offset = submatrix_info.row_offset,
2024  num_rows = submatrix_info.num_rows;
2025  const MatrixPruneInfo &matrix_prune_info = matrix_prune_info_[matrix_index];
2026  if (matrix_prune_info.fully_inside_range) {
2027  submatrix_map_[s] = s;
2028  } else if (!matrix_prune_info.partly_inside_range) {
2029  // completely outside time range.
2030  submatrix_map_[s] = 0;
2031  } else {
2032  // the matrix is partly inside the time range.
2033  int32 pruned_row_begin = std::max(matrix_prune_info.row_begin,
2034  row_offset),
2035  pruned_row_end = std::min(matrix_prune_info.row_end,
2036  row_offset + num_rows);
2037  if (pruned_row_end <= pruned_row_begin) {
2038  // there was no overlap between the submatrix and the part
2039  // of the matrix that was inside the time range.
2040  submatrix_map_[s] = 0;
2041  } else {
2042  // caution: this invalidates the reference 'submatrix_info'.
2043  int32 row_offset_within_submatrix =
2044  pruned_row_begin - row_offset,
2045  new_num_rows = pruned_row_end - pruned_row_begin;
2046  submatrix_map_[s] =
2047  computation_->NewSubMatrix(s, row_offset_within_submatrix,
2048  new_num_rows, 0, -1);
2049  }
2050  }
2051  bool is_deriv = computation_->matrix_debug_info[matrix_index].is_deriv;
2052  submatrix_map_if_deriv_[s] = (is_deriv ?
2053  submatrix_map_[s] : s);
2054  }
2055 }
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

◆ GetPruneValues()

void GetPruneValues ( int32  initial_submatrix,
int32  new_submatrix,
int32 *  left_prune,
int32 *  right_prune 
) const
inlineprivate

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

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

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

◆ LimitDerivTimes()

void LimitDerivTimes ( )

Definition at line 1939 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().

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

◆ LimitMatrices()

void LimitMatrices ( const std::vector< bool > &  will_limit)
inlineprivate

Definition at line 2116 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().

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

◆ MapAddRowRangesCommand()

void MapAddRowRangesCommand ( NnetComputation::Command c)
private

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

References NnetComputation::Command::arg1, NnetComputation::Command::arg2, NnetComputation::Command::arg3, NnetComputation::Command::command_type, ModelUpdateConsolidator::computation_, rnnlm::i, NnetComputation::indexes_ranges, KALDI_ASSERT, kaldi::nnet3::kNoOperation, and NnetComputation::submatrices.

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

◆ MapIndexesCommand()

void MapIndexesCommand ( NnetComputation::Command c)
private

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

References NnetComputation::Command::arg1, NnetComputation::Command::arg2, NnetComputation::Command::arg3, NnetComputation::Command::command_type, ModelUpdateConsolidator::computation_, rnnlm::i, NnetComputation::indexes, KALDI_ASSERT, kaldi::nnet3::kNoOperation, and NnetComputation::submatrices.

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

◆ MapIndexesMultiCommand()

void MapIndexesMultiCommand ( NnetComputation::Command c)
private

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

References NnetComputation::Command::arg1, NnetComputation::Command::arg2, NnetComputation::Command::command_type, ModelUpdateConsolidator::computation_, rnnlm::i, NnetComputation::indexes_multi, KALDI_ASSERT, kaldi::nnet3::kNoOperation, and NnetComputation::submatrices.

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

◆ MapSimpleMatrixCommand()

void MapSimpleMatrixCommand ( NnetComputation::Command c)
private

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

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

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

◆ ModifyCommand()

void ModifyCommand ( NnetComputation::Command command)
private

Definition at line 1604 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, ModelUpdateConsolidator::nnet_, and Component::Properties().

Referenced by DerivativeTimeLimiter::ModifyCommands().

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

◆ ModifyCommands()

void ModifyCommands ( )
private

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

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

Referenced by DerivativeTimeLimiter::LimitDerivTimes().

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

◆ PruneMatrices()

void PruneMatrices ( )
private

Definition at line 2179 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().

2179  {
2180  Analyzer analyzer;
2181  analyzer.Init(nnet_, *computation_);
2183  int32 num_matrices = computation_->matrices.size();
2184  std::vector<bool> will_limit(num_matrices, false);
2185  bool will_limit_at_least_one = false;
2186  for (int32 m = 1; m < num_matrices; m++) {
2187  const MatrixAccesses &accesses = analyzer.matrix_accesses[m];
2188  const MatrixPruneInfo &matrix_prune_info = matrix_prune_info_[m];
2189  if (matrix_prune_info.fully_inside_range ||
2190  accesses.is_input || accesses.is_output ||
2191  !computation_->matrix_debug_info[m].is_deriv)
2192  continue; // nothing to do: it's inside the time-range or not a
2193  // derivative.
2194  // if we got here it's not completely inside the time range, not an input or
2195  // an output, and it's a derivative.
2196  if (!matrix_prune_info.partly_inside_range) {
2197  // completely outside time range. we can prune the matrix if it is not an
2198  // input or output, and is never accessed apart from allocation.
2199  if (MatrixIsUnused(analyzer, *computation_, m))
2201  } else {
2202  // the matrix is partly inside the time range, it's a derivative, and not
2203  // an input or an output.
2204  if (CanLimitMatrix(analyzer, m)) {
2205  will_limit[m] = true;
2206  will_limit_at_least_one = true;
2207  }
2208  }
2209  }
2210  if (will_limit_at_least_one)
2211  LimitMatrices(will_limit);
2212 }
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)
bool CanLimitMatrix(const Analyzer &analyzer, int32 matrix_index) const
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 &#39;computation&#39; the commands accessing matrix &#39;m&#39;, which is assumed to be un...

◆ RemoveUnusedMemos()

void RemoveUnusedMemos ( )
private

Definition at line 1955 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().

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

◆ ResizeMatrices()

void ResizeMatrices ( )
private

◆ RowIsKept()

bool RowIsKept ( int32  submatrix,
int32  row_index 
) const
private

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

References NnetComputation::MatrixDebugInfo::cindexes, ModelUpdateConsolidator::computation_, NnetComputation::MatrixDebugInfo::is_deriv, KALDI_ASSERT, NnetComputation::matrix_debug_info, and NnetComputation::submatrices.

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

Member Data Documentation

◆ computation_

◆ matrix_prune_info_

◆ max_deriv_time_

int32 max_deriv_time_
private

◆ memos_to_delete_

std::unordered_set<int32> memos_to_delete_
private

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

Referenced by DerivativeTimeLimiter::RemoveUnusedMemos().

◆ min_deriv_time_

int32 min_deriv_time_
private

◆ nnet_

◆ prune_info_

std::vector<MatrixPruneInfo> prune_info_
private

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

◆ submatrix_map_

std::vector<int32> submatrix_map_
private

◆ submatrix_map_if_deriv_

std::vector<int32> submatrix_map_if_deriv_
private

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

Referenced by DerivativeTimeLimiter::ComputeSubmatrixMaps().

◆ whole_submatrices_

std::vector<int32> whole_submatrices_
private

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