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 213 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 1653 of file nnet-optimize-utils.cc.

1656  :
1657  nnet_(nnet),
1658  min_deriv_time_(min_deriv_time),
1659  max_deriv_time_(max_deriv_time),
1660  computation_(computation) { }

Member Function Documentation

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

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

References ComputationVariables::AppendVariablesForSubmatrix(), KALDI_ASSERT, KALDI_VLOG, Analyzer::matrix_accesses, DerivativeTimeLimiter::submatrix_map_, Analyzer::variable_accesses, Analyzer::variables, and DerivativeTimeLimiter::whole_submatrices_.

Referenced by DerivativeTimeLimiter::PruneMatrices().

1794  {
1795  int32 s_whole = whole_submatrices_[m]; // submatrix consisting of
1796  // all of the matrix.
1797  int32 s_mapped = submatrix_map_[s_whole]; // the matrix limited in time.
1798  KALDI_ASSERT(s_mapped != 0 && s_mapped != s_whole);
1799  std::vector<int32> whole_variables, mapped_variables;
1800  analyzer.variables.AppendVariablesForSubmatrix(s_whole,
1801  &whole_variables);
1802  analyzer.variables.AppendVariablesForSubmatrix(s_mapped,
1803  &mapped_variables);
1804  KALDI_ASSERT(whole_variables.size() > mapped_variables.size());
1805  std::vector<int32> excluded_variables(whole_variables.size() -
1806  mapped_variables.size());
1807  std::vector<int32>::iterator end_iter =
1808  std::set_difference(whole_variables.begin(), whole_variables.end(),
1809  mapped_variables.begin(), mapped_variables.end(),
1810  excluded_variables.begin());
1811  KALDI_ASSERT(end_iter == excluded_variables.end());
1812  // We want to make sure that none of the excluded variables are
1813  // ever accessed. If they are, we cannot prune the matrix.
1814  int32 allocate_command = analyzer.matrix_accesses[m].allocate_command;
1815  for (std::vector<int32>::iterator iter = excluded_variables.begin();
1816  iter != end_iter; ++iter) {
1817  int32 variable_index = *iter;
1818  const std::vector<Access> &variable_accesses =
1819  analyzer.variable_accesses[variable_index];
1820  std::vector<Access>::const_iterator viter = variable_accesses.begin(),
1821  vend = variable_accesses.end();
1822  for (; viter != vend; ++viter) {
1823  // if a variable outside the pruned range of the matrix is ever accessed
1824  // apart from on allocation, we cannot prune.
1825  if (viter->command_index != allocate_command) {
1826  // we may one day want to look at this.. it's not really expected.
1827  KALDI_VLOG(4) << "Cannot prune matrix " << m;
1828  return false;
1829  }
1830  }
1831  }
1832  return true;
1833 }
#define KALDI_ASSERT(cond)
Definition: kaldi-error.h:169
#define KALDI_VLOG(v)
Definition: kaldi-error.h:136
void ComputeMatrixPruneInfo ( )
private

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

1695  {
1697  computation_->matrices.size() &&
1698  "Limiting derivative times requires debug info.");
1699  const int32 num_matrices = computation_->matrices.size(),
1700  min_deriv_time = min_deriv_time_,
1701  max_deriv_time = max_deriv_time_;
1702  matrix_prune_info_.resize(num_matrices);
1703  // matrix_prune_info_[0] will remain undefined.
1704  for (int32 matrix_index = 1; matrix_index < num_matrices; matrix_index++) {
1705  NnetComputation::MatrixDebugInfo &debug_info =
1706  computation_->matrix_debug_info[matrix_index];
1707  MatrixPruneInfo &prune_info = matrix_prune_info_[matrix_index];
1708  const std::vector<Cindex> &cindexes = debug_info.cindexes;
1709  int32 num_rows = computation_->matrices[matrix_index].num_rows;
1710  KALDI_ASSERT(num_rows == static_cast<int32>(cindexes.size()));
1711  int32 first_row_within_range = num_rows,
1712  last_row_within_range = -1;
1713  for (int32 i = 0; i < num_rows; i++) {
1714  int32 t = cindexes[i].second.t;
1715  if (t >= min_deriv_time && t <= max_deriv_time) {
1716  if (i < first_row_within_range) first_row_within_range = i;
1717  if (i > last_row_within_range) last_row_within_range = i;
1718  }
1719  }
1720  if (last_row_within_range == -1) {
1721  prune_info.fully_inside_range = false;
1722  prune_info.partly_inside_range = false;
1723  } else if (last_row_within_range == num_rows - 1 &&
1724  first_row_within_range == 0) {
1725  prune_info.fully_inside_range = true;
1726  prune_info.partly_inside_range = false;
1727  } else {
1728  prune_info.fully_inside_range = false;
1729  prune_info.partly_inside_range = true;
1730  prune_info.row_begin = first_row_within_range;
1731  prune_info.row_end = last_row_within_range + 1;
1732  }
1733  }
1734 }
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 1736 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().

1736  {
1737  int32 num_submatrices = computation_->submatrices.size();
1738  submatrix_map_.resize(num_submatrices);
1739  submatrix_map_if_deriv_.resize(num_submatrices);
1740  // index zero is for the empty submatrix.
1741  submatrix_map_[0] = 0;
1742  submatrix_map_if_deriv_[0] = 0;
1743  for (int32 s = 1; s < num_submatrices; s++) {
1744  NnetComputation::SubMatrixInfo &submatrix_info(computation_->submatrices[s]);
1745  int32 matrix_index = submatrix_info.matrix_index;
1746  int32 row_offset = submatrix_info.row_offset,
1747  num_rows = submatrix_info.num_rows;
1748  const MatrixPruneInfo &matrix_prune_info = matrix_prune_info_[matrix_index];
1749  if (matrix_prune_info.fully_inside_range) {
1750  submatrix_map_[s] = s;
1751  } else if (!matrix_prune_info.partly_inside_range) {
1752  // completely outside time range.
1753  submatrix_map_[s] = 0;
1754  } else {
1755  // the matrix is partly inside the time range.
1756  int32 pruned_row_begin = std::max(matrix_prune_info.row_begin,
1757  row_offset),
1758  pruned_row_end = std::min(matrix_prune_info.row_end,
1759  row_offset + num_rows);
1760  if (pruned_row_end <= pruned_row_begin) {
1761  // there was no overlap between the submatrix and the part
1762  // of the matrix that was inside the time range.
1763  submatrix_map_[s] = 0;
1764  } else {
1765  // caution: this invalidates the reference 'submatrix_info'.
1766  int32 row_offset_within_submatrix =
1767  pruned_row_begin - row_offset,
1768  new_num_rows = pruned_row_end - pruned_row_begin;
1769  submatrix_map_[s] =
1770  computation_->NewSubMatrix(s, row_offset_within_submatrix,
1771  new_num_rows, 0, -1);
1772  }
1773  }
1774  bool is_deriv = computation_->matrix_debug_info[matrix_index].is_deriv;
1775  submatrix_map_if_deriv_[s] = (is_deriv ?
1776  submatrix_map_[s] : s);
1777  }
1778 }
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 1283 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().

1286  {
1287  KALDI_ASSERT(initial_submatrix > 0 && new_submatrix > 0);
1288  const NnetComputation::SubMatrixInfo
1289  initial_info = computation_->submatrices[initial_submatrix],
1290  new_info = computation_->submatrices[new_submatrix];
1291  KALDI_ASSERT(initial_info.matrix_index == new_info.matrix_index);
1292  *left_prune = new_info.row_offset - initial_info.row_offset;
1293  if (right_prune != NULL) {
1294  *right_prune = initial_info.num_rows - new_info.num_rows - *left_prune;
1295  KALDI_ASSERT(*left_prune >= 0 && *right_prune >= 0);
1296  }
1297 }
std::vector< SubMatrixInfo > submatrices
#define KALDI_ASSERT(cond)
Definition: kaldi-error.h:169
void LimitDerivTimes ( )

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

1662  {
1664  if (min_deriv_time_ == std::numeric_limits<int32>::min() &&
1665  max_deriv_time_ == std::numeric_limits<int32>::max())
1666  return; // nothing to do.
1667 
1671  ModifyCommands();
1672  PruneMatrices();
1676 }
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 1835 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().

1835  {
1836  // first modify 'submatrices'.
1837  int32 num_submatrices = computation_->submatrices.size(),
1838  num_matrices = computation_->matrices.size();
1839  for (int32 s = 1; s < num_submatrices; s++) {
1840  NnetComputation::SubMatrixInfo &submat_info = computation_->submatrices[s];
1841  int32 m = submat_info.matrix_index;
1842  if (will_limit[m]) {
1843  // we need to do something...
1844  const MatrixPruneInfo &prune_info = matrix_prune_info_[m];
1845  int32 matrix_num_rows = prune_info.row_end - prune_info.row_begin;
1846  KALDI_ASSERT(matrix_num_rows > 0 &&
1847  matrix_num_rows < computation_->matrices[m].num_rows);
1848  KALDI_ASSERT(prune_info.partly_inside_range);
1849  int32 new_row_begin = submat_info.row_offset - prune_info.row_begin;
1850  if (new_row_begin >= 0 &&
1851  submat_info.num_rows + new_row_begin <= matrix_num_rows) {
1852  // If this submatrix is entirely inside the limited range of the matrix,
1853  // then we modify its row_offset to account for the truncation of
1854  // rows to the left.
1855  submat_info.row_offset = new_row_begin;
1856  } else {
1857  // This submatrix is not entirely inside the kept range of the matrix.
1858  // We assume that this submatrix is never accessed directly except (if
1859  // it was the whole matrix) for in allocation and deallocation commands,
1860  // since when we modified the computation we ensured this.
1861  if (computation_->IsWholeMatrix(s)) {
1862  // If it was the whole matrix then it may be used in allocation and
1863  // deallocation commands, so we should modify it to be the whole of the
1864  // new matrix, which will have fewer rows than before.
1865  submat_info.num_rows = matrix_num_rows;
1866  } else {
1867  // We believe this matrix should never be used. We give it a valid
1868  // but stupid size of num-rows=1, num-cols=1, so that if it ever does
1869  // get accessed it should produce an error.
1870  submat_info.row_offset = 0;
1871  submat_info.num_rows = 1;
1872  submat_info.col_offset = 0;
1873  submat_info.num_cols = 1;
1874  }
1875  }
1876  }
1877  }
1878  // next modify 'matrices'
1879  for (int32 m = 1; m < num_matrices; m++) {
1880  if (will_limit[m]) {
1881  const MatrixPruneInfo &prune_info = matrix_prune_info_[m];
1882  NnetComputation::MatrixInfo &matrix_info = computation_->matrices[m];
1883  if (!computation_->matrix_debug_info.empty()) {
1884  NnetComputation::MatrixDebugInfo &debug_info =
1886  std::vector<Cindex> &cindexes = debug_info.cindexes;
1887  KALDI_ASSERT(cindexes.size() == static_cast<size_t>(matrix_info.num_rows));
1888  cindexes.erase(cindexes.begin() + prune_info.row_end, cindexes.end());
1889  cindexes.erase(cindexes.begin(),
1890  cindexes.begin() + prune_info.row_begin);
1891  }
1892  matrix_info.num_rows = prune_info.row_end - prune_info.row_begin;
1893  // num_cols stays the same.
1894  }
1895  }
1896 }
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 1583 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().

1584  {
1585  int32 dest_submatrix = c->arg1,
1586  src_submatrix = c->arg2,
1587  indexes_ranges_index = c->arg3;
1588  int32 dest_submatrix_mapped = submatrix_map_if_deriv_[dest_submatrix],
1589  src_submatrix_mapped = submatrix_map_if_deriv_[src_submatrix];
1590  if (dest_submatrix_mapped == dest_submatrix &&
1591  src_submatrix_mapped == src_submatrix)
1592  return;
1593  if (dest_submatrix_mapped == 0 || src_submatrix_mapped == 0) {
1594  c->command_type = kNoOperation;
1595  return;
1596  }
1597  int32 dest_num_rows = computation_->submatrices[dest_submatrix_mapped].num_rows,
1598  src_num_rows = computation_->submatrices[src_submatrix_mapped].num_rows,
1599  src_left_prune, dest_left_prune;
1600  GetPruneValues(dest_submatrix, dest_submatrix_mapped,
1601  &dest_left_prune, NULL);
1602  GetPruneValues(src_submatrix, src_submatrix_mapped,
1603  &src_left_prune, NULL);
1604  const std::vector<std::pair<int32,int32> > &old_indexes_ranges(
1605  computation_->indexes_ranges[indexes_ranges_index]);
1606  std::vector<std::pair<int32,int32> > new_indexes_ranges(dest_num_rows);
1607 
1608  bool must_keep_command = false;
1609  for (int32 i = 0; i < dest_num_rows; i++) {
1610  std::pair<int32, int32> &this_pair = new_indexes_ranges[i];
1611  this_pair = old_indexes_ranges[i + dest_left_prune];
1612 
1613  int32 start = this_pair.first, end = this_pair.second;
1614  if (!RowIsKept(dest_submatrix_mapped, i)) {
1615  start = -1;
1616  end = -1;
1617  } else if (start >= 0) {
1618  // no need to change start, end if they are (-1, -1).
1619  // Note: this code is not optimally efficient, as RowIsKept
1620  // has a bunch of statements that we could cache some variables
1621  // for, but this command is pretty rare so not worth to optimize
1622  // at this point.
1623  while (start < end && !RowIsKept(src_submatrix, start))
1624  start++;
1625  while (end > start && !RowIsKept(src_submatrix, end - 1))
1626  end--;
1627  if (start == end) {
1628  start = -1;
1629  end = -1;
1630  } else {
1631  start -= src_left_prune;
1632  end -= src_left_prune;
1633  must_keep_command = true;
1634  // the next assert is because if we were outside the 'kept' part of the
1635  // submatrix, RowIsKept() should have instructed us to modify the value.
1636  KALDI_ASSERT(start >= 0 && end <= src_num_rows && start < end);
1637  }
1638  }
1639  this_pair.first = start;
1640  this_pair.second = end;
1641  }
1642  if (must_keep_command) {
1643  c->arg1 = dest_submatrix_mapped;
1644  c->arg2 = src_submatrix_mapped;
1645  c->arg3 = computation_->indexes_ranges.size();
1646  computation_->indexes_ranges.push_back(new_indexes_ranges);
1647  } else {
1648  c->command_type = kNoOperation;
1649  }
1650 }
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 1458 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().

1458  {
1459  int32 output_submatrix = c->arg1,
1460  input_submatrix = c->arg2;
1461  int32 input_submatrix_mapped = submatrix_map_if_deriv_[input_submatrix],
1462  output_submatrix_mapped = submatrix_map_if_deriv_[output_submatrix];
1463  // input_submatrix_mapped and output_submatrix_mapped map both submatrices to
1464  // just the portion that we are treating as nonzero.
1465 
1466  if (input_submatrix_mapped == 0 ||
1467  output_submatrix_mapped == 0) {
1468  // Either input or output is all zeros; make the command a no-op.
1469  // It may not be obvious that in the case of kCopyRows it would
1470  // be valid to make this a no-op (because what if the existing
1471  // contents were nonzero?), but we insist that this optimization
1472  // come before optimizations, and we know that the originally
1473  // generated computation would not overwrite a nonzero value
1474  // (and there are no undefined values because we make sure to
1475  // initialize everything with zeros; ununitialized values are
1476  // allowed only at a later optimization stage.
1477  c->command_type = kNoOperation;
1478  return;
1479  }
1480  const std::vector<int32> &old_indexes = computation_->indexes[c->arg3];
1481 
1482  int32 left_prune_input, left_prune_output;
1483  GetPruneValues(input_submatrix, input_submatrix_mapped,
1484  &left_prune_input, NULL);
1485  GetPruneValues(output_submatrix, output_submatrix_mapped,
1486  &left_prune_output, NULL);
1487  int32 new_num_input_rows =
1488  computation_->submatrices[input_submatrix_mapped].num_rows,
1489  new_num_output_rows =
1490  computation_->submatrices[output_submatrix_mapped].num_rows;
1491  std::vector<int32> new_indexes(new_num_output_rows);
1492  bool must_keep_command = false;
1493  for (int32 i = 0; i < new_num_output_rows; i++) {
1494  // the index into the 'new_indexes' vector is the row of the output
1495  // submatrix; the value is the row of the input submatrix.
1496  int32 orig_index = old_indexes[i + left_prune_output];
1497  if (orig_index == -1 ||
1498  !RowIsKept(input_submatrix, orig_index) ||
1499  !RowIsKept(output_submatrix_mapped, i)) {
1500  new_indexes[i] = -1;
1501  } else {
1502  int32 mapped_index = orig_index - left_prune_input;
1503  // we can do the following assert because the RowIsKept command
1504  // would have turned it into a -1 if not.
1505  KALDI_ASSERT(mapped_index >= 0 && mapped_index < new_num_input_rows);
1506  new_indexes[i] = mapped_index;
1507  must_keep_command = true;
1508  }
1509  }
1510  if (!must_keep_command) {
1511  c->command_type = kNoOperation;
1512  return;
1513  }
1514  int32 new_indexes_index = computation_->indexes.size();
1515  computation_->indexes.push_back(new_indexes);
1516  c->arg1 = output_submatrix_mapped;
1517  c->arg2 = input_submatrix_mapped;
1518  c->arg3 = new_indexes_index;
1519 }
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 1521 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().

1521  {
1522  int32 dest_submatrix = c->arg1,
1523  indexes_multi_arg = c->arg2;
1524  int32 dest_submatrix_mapped = submatrix_map_if_deriv_[dest_submatrix];
1525  if (dest_submatrix_mapped == 0) {
1526  // The destination matrix is completely outside the allowed time range.
1527  c->command_type = kNoOperation;
1528  return;
1529  }
1530  int32 left_prune;
1531  GetPruneValues(dest_submatrix, dest_submatrix_mapped, &left_prune, NULL);
1532  int32 new_num_rows = computation_->submatrices[dest_submatrix_mapped].num_rows;
1533  const std::vector<std::pair<int32, int32> > &old_indexes_multi(
1534  computation_->indexes_multi[indexes_multi_arg]);
1535  std::vector<std::pair<int32, int32> > new_indexes_multi(new_num_rows);
1536  bool must_keep_command = false;
1537  for (int32 i = 0; i < new_num_rows; i++) {
1538  std::pair<int32,int32> &this_pair = new_indexes_multi[i];
1539  this_pair = old_indexes_multi[i + left_prune];
1540  // note: 'this_submatrix' is the source submatrix, from where we copy or add
1541  // the the data; 'this_row' is the source row.
1542  int32 this_submatrix = this_pair.first,
1543  this_row = this_pair.second;
1544  if (this_submatrix == -1) // don't map the (-1, -1) pairs.
1545  continue;
1546  if (!RowIsKept(this_submatrix, this_row) ||
1547  !RowIsKept(dest_submatrix_mapped, i)) {
1548  this_pair.first = -1;
1549  this_pair.second = -1;
1550  continue;
1551  }
1552  int32 this_submatrix_mapped = submatrix_map_if_deriv_[this_submatrix];
1553 
1554  // Reason for the assert below: if this_submatrix_mapped was 0, then all the
1555  // values in it should be not-kept, but RowIsKept above returned true, so
1556  // this would be a code error.
1557  KALDI_ASSERT(this_submatrix_mapped != 0);
1558 
1559  int32 this_left_prune, this_num_rows =
1560  computation_->submatrices[this_submatrix_mapped].num_rows;
1561  GetPruneValues(this_submatrix, this_submatrix_mapped,
1562  &this_left_prune, NULL);
1563  int32 this_row_mapped = this_row - this_left_prune;
1564  // the above assert is there because if it was going to be outside the
1565  // kept range, RowIsKept should have returned false above.
1566  KALDI_ASSERT(this_row_mapped >= 0 && this_row_mapped < this_num_rows);
1567  this_pair.first = this_submatrix_mapped;
1568  this_pair.second = this_row_mapped;
1569  must_keep_command = true;
1570  }
1571  if (!must_keep_command) {
1572  c->command_type = kNoOperation;
1573  return;
1574  }
1575  if (dest_submatrix_mapped == dest_submatrix &&
1576  new_indexes_multi == old_indexes_multi) // nothing changed.
1577  return;
1578  c->arg1 = dest_submatrix_mapped;
1579  c->arg2 = computation_->indexes_multi.size();
1580  computation_->indexes_multi.push_back(new_indexes_multi);
1581 }
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 1409 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().

1409  {
1410  int32 submatrix1 = c->arg1,
1411  submatrix2 = c->arg2;
1412  int32 submatrix1_mapped = submatrix_map_if_deriv_[submatrix1],
1413  submatrix2_mapped = submatrix_map_if_deriv_[submatrix2];
1414  if (submatrix1_mapped == submatrix1 &&
1415  submatrix2_mapped == submatrix2) {
1416  // nothing to do.
1417  return;
1418  }
1419  if (submatrix1_mapped == 0 || submatrix2_mapped == 0) {
1420  // remove the operation-- it has nothing to do.
1421  c->command_type = kNoOperation;
1422  return;
1423  }
1424  // left_prune1 is the number of rows pruned away on the left for submatrix1.
1425  int32 orig_num_rows = computation_->submatrices[submatrix1].num_rows,
1426  left_prune1, left_prune2, right_prune1, right_prune2;
1427  GetPruneValues(submatrix1, submatrix1_mapped, &left_prune1, &right_prune1);
1428  GetPruneValues(submatrix2, submatrix2_mapped, &left_prune2, &right_prune2);
1429  if (left_prune1 == left_prune2 && right_prune1 == right_prune2) {
1430  // we took the same number of rows away from the left and right for
1431  // both arguments; the normal mapped values will work in this case
1432  c->arg1 = submatrix1_mapped;
1433  c->arg2 = submatrix2_mapped;
1434  } else {
1435  // there is some kind of mismatch- we'll prune back to what remains
1436  // after applying the maximum pruning on the left and right.
1437  int32 left_prune = std::max(left_prune1, left_prune2),
1438  right_prune = std::max(right_prune1, right_prune2);
1439  if (left_prune + right_prune >= orig_num_rows) {
1440  // everything was pruned away; remove the operation.
1441  c->command_type = kNoOperation;
1442  return;
1443  } else {
1444  int32 num_rows = orig_num_rows - left_prune - right_prune;
1445  // note: the call NewSubMatrix effectively gives us a sub-matrix of a
1446  // sub-matrix.
1447  c->arg1 = computation_->NewSubMatrix(submatrix1,
1448  left_prune, num_rows, 0, -1);
1449  c->arg2 = computation_->NewSubMatrix(submatrix2,
1450  left_prune, num_rows, 0, -1);
1451  }
1452  }
1453 }
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 1323 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::kAllocMatrixFromOther, kaldi::nnet3::kAllocMatrixFromOtherZeroed, kaldi::nnet3::kAllocMatrixUndefined, kaldi::nnet3::kAllocMatrixZeroed, 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::kSimpleComponent, 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().

1323  {
1324  CommandType command_type = command->command_type;
1325  switch (command_type) {
1326  case kAllocMatrixUndefined:
1327  case kAllocMatrixFromOther:
1329  KALDI_ERR << "No undefined initialization or initialization-from-other "
1330  << "is allowed before LimitDerivativeTimes";
1331  break;
1332  case kAllocMatrixZeroed:
1333  case kDeallocMatrix:
1334  break; // we'll deal with allocation and deallocation later on.
1335  case kPropagate:
1336  // Propagate commands are unchanged, except that if the output of the
1337  // propagate is completely outside the accepted time-range (only likely if
1338  // we're inside a recurrency), then we don't store stats; this is not
1339  // really important, and is mostly done to minimize the difference from an
1340  // older version of the code, to reduce the need for testing.
1341  if (submatrix_map_[command->arg4] == 0)
1342  command->arg6 = 0;
1343  break;
1344  case kBackpropNoModelUpdate: // we actually don't expect to encounter this,
1345  // but it's trivial to support as it's the
1346  // same as backprop.
1347  case kBackprop: {
1348  const Component *component = nnet_.GetComponent(command->arg1);
1349  int32 properties = component->Properties();
1350  if (!(properties & kSimpleComponent)) {
1351  // we don't (yet) do this optimization for non-simple Components...
1352  // it would be a bit more complicated as we'd have to recompute the
1353  // PrecomputedIndexes.
1354  break;
1355  }
1356  int32 input_submatrix = command->arg3,
1357  output_submatrix = command->arg4,
1358  output_deriv_submatrix = command->arg5,
1359  input_deriv_submatrix = command->arg6;
1360  int32 mapped_input_submatrix = submatrix_map_[input_submatrix],
1361  mapped_output_submatrix = submatrix_map_[output_submatrix],
1362  mapped_output_deriv_submatrix = submatrix_map_[output_deriv_submatrix],
1363  mapped_input_deriv_submatrix = submatrix_map_[input_deriv_submatrix];
1364 
1365  if (mapped_output_deriv_submatrix == 0) {
1366  // completely outside range..
1367  KALDI_ASSERT(mapped_input_deriv_submatrix == 0 &&
1368  mapped_input_submatrix == 0 &&
1369  mapped_output_submatrix == 0);
1370  // just delete the command.
1371  command->command_type = kNoOperation;
1372  if (command->arg7 > 0)
1373  memos_to_delete_.insert(command->arg7);
1374  } else if (mapped_output_deriv_submatrix !=
1375  output_deriv_submatrix &&
1376  !(properties & kUsesMemo)) {
1377  // we're operating on a range of the input or output.
1378  // we can't do this type of mapping of the component uses
1379  // a memo, though.
1380  command->arg3 = mapped_input_submatrix;
1381  command->arg4 = mapped_output_submatrix;
1382  command->arg5 = mapped_output_deriv_submatrix;
1383  command->arg6 = mapped_input_deriv_submatrix;
1384  }
1385  break;
1386  }
1387  case kMatrixCopy: case kMatrixAdd:
1388  MapSimpleMatrixCommand(command);
1389  break;
1390  case kCopyRows: case kAddRows:
1391  MapIndexesCommand(command);
1392  break;
1393  case kCopyRowsMulti: case kCopyToRowsMulti:
1394  case kAddRowsMulti: case kAddToRowsMulti:
1395  MapIndexesMultiCommand(command);
1396  break;
1397  case kAddRowRanges: {
1398  MapAddRowRangesCommand(command);
1399  break;
1400  }
1401  case kAcceptInput: case kProvideOutput:
1403  break;
1404  default:
1405  KALDI_ERR << "Un-handled command type.";
1406  }
1407 }
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 1780 of file nnet-optimize-utils.cc.

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

Referenced by DerivativeTimeLimiter::LimitDerivTimes().

1780  {
1781  std::vector<NnetComputation::Command>::iterator
1782  iter = computation_->commands.begin(),
1783  end = computation_->commands.end();
1784  for (; iter != end; ++iter)
1785  ModifyCommand(&(*iter));
1786 }
std::vector< Command > commands
void ModifyCommand(NnetComputation::Command *command)
void PruneMatrices ( )
private

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

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

Referenced by DerivativeTimeLimiter::LimitDerivTimes().

1898  {
1899  Analyzer analyzer;
1900  analyzer.Init(nnet_, *computation_);
1902  int32 num_matrices = computation_->matrices.size();
1903  std::vector<bool> will_limit(num_matrices, false);
1904  bool will_limit_at_least_one = false;
1905  for (int32 m = 1; m < num_matrices; m++) {
1906  const MatrixAccesses &accesses = analyzer.matrix_accesses[m];
1907  const MatrixPruneInfo &matrix_prune_info = matrix_prune_info_[m];
1908  if (matrix_prune_info.fully_inside_range ||
1909  accesses.is_input || accesses.is_output ||
1910  !computation_->matrix_debug_info[m].is_deriv)
1911  continue; // nothing to do: it's inside the time-range or not a
1912  // derivative.
1913  // if we got here it's not completely inside the time range, not an input or
1914  // an output, and it's a derivative.
1915  if (!matrix_prune_info.partly_inside_range) {
1916  // completely outside time range. we can prune the matrix if it is not an
1917  // input or output, and is never accessed apart from allocation.
1918  if (accesses.accesses.empty() ||
1919  (accesses.accesses.size() == 1 &&
1920  accesses.accesses[0].command_index == accesses.allocate_command)) {
1921  // we prune the matrix away. the only thing we need to do here is
1922  // to remove the allocation and deallocation commands.
1923  // they should exist, because we just checked that it's not an input
1924  // or an output.
1925  KALDI_ASSERT(accesses.allocate_command >= 0 &&
1926  accesses.deallocate_command >= 0);
1927  computation_->commands[accesses.allocate_command].command_type =
1928  kNoOperation;
1929  computation_->commands[accesses.deallocate_command].command_type =
1930  kNoOperation;
1931  }
1932  } else {
1933  // the matrix is partly inside the time range, it's a derivative, and not
1934  // an input or an output.
1935  if (CanLimitMatrix(analyzer, m)) {
1936  will_limit[m] = true;
1937  will_limit_at_least_one = true;
1938  }
1939  }
1940  }
1941  if (will_limit_at_least_one)
1942  LimitMatrices(will_limit);
1943 }
std::vector< MatrixDebugInfo > matrix_debug_info
std::vector< MatrixInfo > matrices
std::vector< Command > commands
void LimitMatrices(const std::vector< bool > &will_limit)
std::vector< MatrixPruneInfo > matrix_prune_info_
#define KALDI_ASSERT(cond)
Definition: kaldi-error.h:169
bool CanLimitMatrix(const Analyzer &analyzer, int32 matrix_index) const
void RemoveUnusedMemos ( )
private

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

1678  {
1679  if (memos_to_delete_.empty())
1680  return;
1681  size_t num_commands = computation_->commands.size(),
1682  num_memos_removed = 0;
1683  for (size_t command_index = 0; command_index < num_commands;
1684  command_index++) {
1685  NnetComputation::Command &c = computation_->commands[command_index];
1686  if (c.command_type == kPropagate &&
1687  memos_to_delete_.count(c.arg5) != 0) {
1688  c.arg5 = 0;
1689  num_memos_removed++;
1690  }
1691  }
1692  KALDI_ASSERT(num_memos_removed == memos_to_delete_.size());
1693 }
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 1299 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().

1301  {
1302  KALDI_ASSERT(submatrix > 0 && submatrix < computation_->submatrices.size());
1303  const NnetComputation::SubMatrixInfo &info =
1304  computation_->submatrices[submatrix];
1305  KALDI_ASSERT(row_index >= 0 &&
1306  row_index < computation_->submatrices[submatrix].num_rows);
1307  int32 matrix_index = info.matrix_index;
1308  const NnetComputation::MatrixDebugInfo
1309  &debug_info = computation_->matrix_debug_info[matrix_index];
1310  if (!debug_info.is_deriv) {
1311  // the derivative time limitation doesn't apply to things that aren't
1312  // derivatives.
1313  return true;
1314  }
1315  int32 t = debug_info.cindexes[row_index + info.row_offset].second.t;
1316  return (t >= min_deriv_time_ && t <= max_deriv_time_);
1317 }
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 350 of file nnet-optimize-utils.h.

std::vector<int32> whole_submatrices_
private

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