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

This class relates the matrices and sub-matrices in the computation to imaginary "variables", such that we can think of the operations as operating on sets of individual variables, and we can then do analysis that lets us do optimization. More...

#include <nnet-analyze.h>

Collaboration diagram for ComputationVariables:

Public Member Functions

void Init (const NnetComputation &computation)
 
void RecordAccessForSubmatrix (int32 submatrix_index, AccessType access_type, CommandAttributes *ca) const
 
void AppendVariablesForMatrix (int32 matrix_index, std::vector< int32 > *variable_indexes) const
 Appends to variables_indexes the sorted list of variables corresponding to a matrix index. More...
 
void AppendVariablesForSubmatrix (int32 submatrix_index, std::vector< int32 > *variable_indexes) const
 
int32 NumVariables () const
 
int32 GetMatrixForVariable (int32 variable) const
 
std::string DescribeVariable (int32 variable) const
 

Private Member Functions

void ComputeSplitPoints (const NnetComputation &computation)
 
void ComputeVariablesForSubmatrix (const NnetComputation &computation)
 
void ComputeVariableToMatrix ()
 

Static Private Member Functions

static int32 FindIndexOf (const std::vector< int32 > &sorted_vec, int32 i)
 

Private Attributes

std::vector< std::vector< int32 > > column_split_points_
 
std::vector< std::vector< int32 > > row_split_points_
 
std::vector< int32 > matrix_to_variable_index_
 
std::vector< int32 > submatrix_to_matrix_
 
std::vector< bool > submatrix_is_whole_matrix_
 
std::vector< int32 > variable_to_matrix_
 
int32 num_variables_
 
std::vector< std::vector< int32 > > variables_for_submatrix_
 

Detailed Description

This class relates the matrices and sub-matrices in the computation to imaginary "variables", such that we can think of the operations as operating on sets of individual variables, and we can then do analysis that lets us do optimization.

In principle it might make sense to have those variables correspond to the elements of the matrices, but that would be very inefficient. On the other hand we could do a coarse-grained analysis making the variables correspond to the matrices, but that would cause the resulting analysis to be inaccurate.

What we do instead, which is accurate enough in the cases we envisage, is to make the variables correspond to the most specific row column ranges in the matrices that we ever access. We do this as follows: for each matrix in the computation we get a list of all the "split points" at which the row column ranges respectively ever start and end, and define a split_point_index as the index into the array. The variable could be defined as the triple (matrix_index, row_split_point_index, column_split_point_index), but we map it to a single integer index called variable_index. This is a zero-based index formed by listing all the existing variables iterating first over the matrix index, then the row split-point-index, then the column split-point-index. In the end, if we know the matrix-index, the row-split-point-index and the column-split-point-index, we can compute the variable-index using the expression variable-index = matrix_to_variable_index_[matrix-index] + row-split-point-index * num-column-variables-for-this-matrix + column-split-point-index where in code, num-column-variables-for-this-matrix equals column_split_points_[matrix-index].size()-1. The array matrix_to_variable_index_ is a precomputed array telling us at which variable index the variables for any given matrix begin.

Each sub-matrix in the computation will now correspond to a list of variables, and because these lists are always a contiguous range we can just store the row and column split-points corresponding to the start and end of the submatrix. In addition we note, for each submatrix, whether it spans the entirety of the underlying matrix. The reason we need to know this is that a write operation to just part of a matrix would have to be classed as a read-write operation on the underlying matrix because the final contents after the operation would in that case depend on the original contents.

Definition at line 122 of file nnet-analyze.h.

Member Function Documentation

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

Appends to variables_indexes the sorted list of variables corresponding to a matrix index.

Definition at line 156 of file nnet-analyze.cc.

References KALDI_ASSERT, and ComputationVariables::matrix_to_variable_index_.

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

158  {
159  KALDI_ASSERT(static_cast<size_t>(matrix_index + 1) <
161  int32 start = matrix_to_variable_index_[matrix_index],
162  end = matrix_to_variable_index_[matrix_index + 1];
163  variable_indexes->reserve(variable_indexes->size() + end - start);
164  for (int32 variable_index = start; variable_index < end; variable_index++)
165  variable_indexes->push_back(variable_index);
166 }
std::vector< int32 > matrix_to_variable_index_
Definition: nnet-analyze.h:197
#define KALDI_ASSERT(cond)
Definition: kaldi-error.h:169
void AppendVariablesForSubmatrix ( int32  submatrix_index,
std::vector< int32 > *  variable_indexes 
) const

Definition at line 146 of file nnet-analyze.cc.

References KALDI_ASSERT, and ComputationVariables::variables_for_submatrix_.

Referenced by DerivativeTimeLimiter::CanLimitMatrix(), ComputationAnalysis::DataInvalidatedCommand(), ComputationAnalysis::FirstAccess(), ComputationAnalysis::LastAccess(), ComputationAnalysis::LastWriteAccess(), VariableMergingOptimizer::MarkAsDirty(), VariableMergingOptimizer::MayBeMerged(), and ComputationVariables::RecordAccessForSubmatrix().

148  {
149  KALDI_ASSERT(static_cast<size_t>(submatrix_index) <
150  variables_for_submatrix_.size());
151  variable_indexes->insert(variable_indexes->end(),
152  variables_for_submatrix_[submatrix_index].begin(),
153  variables_for_submatrix_[submatrix_index].end());
154 }
std::vector< std::vector< int32 > > variables_for_submatrix_
Definition: nnet-analyze.h:213
#define KALDI_ASSERT(cond)
Definition: kaldi-error.h:169
void ComputeSplitPoints ( const NnetComputation computation)
private

Definition at line 25 of file nnet-analyze.cc.

References NnetComputation::SubMatrixInfo::col_offset, ComputationVariables::column_split_points_, KALDI_ASSERT, NnetComputation::matrices, NnetComputation::SubMatrixInfo::matrix_index, ComputationVariables::matrix_to_variable_index_, NnetComputation::SubMatrixInfo::num_cols, NnetComputation::SubMatrixInfo::num_rows, ComputationVariables::num_variables_, NnetComputation::SubMatrixInfo::row_offset, ComputationVariables::row_split_points_, kaldi::SortAndUniq(), and NnetComputation::submatrices.

Referenced by ComputationVariables::Init().

26  {
27  // note, these numbers are only valid if you include the empty zero-indexed
28  // matrix/submatrix as a matrix.
29  int32 num_matrices = computation.matrices.size(),
30  num_submatrices = computation.submatrices.size();
31  row_split_points_.resize(num_matrices);
32  column_split_points_.resize(num_matrices);
33  KALDI_ASSERT(computation.submatrices[0].num_rows == 0);
34  for (int32 submatrix_index = 1;
35  submatrix_index < num_submatrices;
36  submatrix_index++) {
37  const NnetComputation::SubMatrixInfo &s =
38  computation.submatrices[submatrix_index];
39  row_split_points_[s.matrix_index].push_back(s.row_offset);
40  row_split_points_[s.matrix_index].push_back(s.row_offset + s.num_rows);
41  column_split_points_[s.matrix_index].push_back(s.col_offset);
42  column_split_points_[s.matrix_index].push_back(s.col_offset + s.num_cols);
43  }
44  for (int32 matrix_index = 1; matrix_index < num_matrices; matrix_index++) {
45  // Because it's possible for matrices not to have any submatrices (after
46  // pruning), we need to make sure that the beginning and end dimensions are
47  // in the split points.
48  column_split_points_[matrix_index].push_back(0);
49  column_split_points_[matrix_index].push_back(
50  computation.matrices[matrix_index].num_cols);
51  row_split_points_[matrix_index].push_back(0);
52  row_split_points_[matrix_index].push_back(
53  computation.matrices[matrix_index].num_rows);
54  SortAndUniq(&(column_split_points_[matrix_index]));
55  SortAndUniq(&(row_split_points_[matrix_index]));
56  }
57  // note: the last split point of each matrix doesn't get its own variable index.
58  matrix_to_variable_index_.resize(num_matrices + 1);
61  for (int32 matrix_index = 1; matrix_index < num_matrices; matrix_index++) {
62  int32 num_row_variables = row_split_points_[matrix_index].size() - 1,
63  num_column_variables = column_split_points_[matrix_index].size() - 1,
64  num_variables = num_row_variables * num_column_variables;
65  KALDI_ASSERT(num_variables >= 1);
66  matrix_to_variable_index_[matrix_index+1] =
67  matrix_to_variable_index_[matrix_index] + num_variables;
68  }
70 }
void SortAndUniq(std::vector< T > *vec)
Sorts and uniq's (removes duplicates) from a vector.
Definition: stl-utils.h:39
std::vector< std::vector< int32 > > row_split_points_
Definition: nnet-analyze.h:188
std::vector< int32 > matrix_to_variable_index_
Definition: nnet-analyze.h:197
std::vector< std::vector< int32 > > column_split_points_
Definition: nnet-analyze.h:185
#define KALDI_ASSERT(cond)
Definition: kaldi-error.h:169
void ComputeVariablesForSubmatrix ( const NnetComputation computation)
private

Definition at line 81 of file nnet-analyze.cc.

References NnetComputation::SubMatrixInfo::col_offset, ComputationVariables::column_split_points_, ComputationVariables::FindIndexOf(), KALDI_ASSERT, NnetComputation::SubMatrixInfo::matrix_index, ComputationVariables::matrix_to_variable_index_, NnetComputation::SubMatrixInfo::num_cols, NnetComputation::SubMatrixInfo::num_rows, NnetComputation::SubMatrixInfo::row_offset, ComputationVariables::row_split_points_, NnetComputation::submatrices, ComputationVariables::submatrix_is_whole_matrix_, ComputationVariables::submatrix_to_matrix_, and ComputationVariables::variables_for_submatrix_.

Referenced by ComputationVariables::Init().

82  {
83  // note, these numbers are only valid if you include the empty zero-indexed
84  // matrix/submatrix as a matrix.
85  int32 num_submatrices = computation.submatrices.size();
86 
87  variables_for_submatrix_.resize(num_submatrices);
88 
89  submatrix_is_whole_matrix_.resize(num_submatrices, false);
90  submatrix_to_matrix_.resize(num_submatrices);
91  submatrix_to_matrix_[0] = 0;
92 
93  for (int32 submatrix_index = 1;
94  submatrix_index < num_submatrices;
95  submatrix_index++) {
96  const NnetComputation::SubMatrixInfo &s =
97  computation.submatrices[submatrix_index];
98  int32 matrix_index = s.matrix_index;
99  submatrix_to_matrix_[submatrix_index] = matrix_index;
100  int32 start_col = s.col_offset, end_col = start_col + s.num_cols,
101  start_row = s.row_offset, end_row = start_row + s.num_rows;
102  int32 row_start = FindIndexOf(row_split_points_[matrix_index], start_row),
103  row_end = FindIndexOf(row_split_points_[matrix_index], end_row),
104  col_start = FindIndexOf(column_split_points_[matrix_index], start_col),
105  col_end = FindIndexOf(column_split_points_[matrix_index], end_col),
106  num_column_variables = column_split_points_[matrix_index].size() - 1,
107  num_row_variables = row_split_points_[matrix_index].size() - 1,
108  matrix_start_variable = matrix_to_variable_index_[matrix_index];
109  KALDI_ASSERT(row_end > row_start && col_end > col_start &&
110  col_end <= num_column_variables);
111  std::vector<int32> &variables = variables_for_submatrix_[submatrix_index];
112  for (int32 r = row_start; r < row_end; r++)
113  for (int32 c = col_start; c < col_end; c++)
114  variables.push_back(matrix_start_variable + r*num_column_variables + c);
115  if (row_start == 0 && row_end == num_row_variables &&
116  col_start == 0 && col_end == num_column_variables)
117  submatrix_is_whole_matrix_[submatrix_index] = true;
118  }
119 }
std::vector< int32 > submatrix_to_matrix_
Definition: nnet-analyze.h:199
std::vector< std::vector< int32 > > row_split_points_
Definition: nnet-analyze.h:188
std::vector< std::vector< int32 > > variables_for_submatrix_
Definition: nnet-analyze.h:213
std::vector< int32 > matrix_to_variable_index_
Definition: nnet-analyze.h:197
static int32 FindIndexOf(const std::vector< int32 > &sorted_vec, int32 i)
Definition: nnet-analyze.cc:73
std::vector< std::vector< int32 > > column_split_points_
Definition: nnet-analyze.h:185
#define KALDI_ASSERT(cond)
Definition: kaldi-error.h:169
std::vector< bool > submatrix_is_whole_matrix_
Definition: nnet-analyze.h:203
void ComputeVariableToMatrix ( )
private

Definition at line 121 of file nnet-analyze.cc.

References rnnlm::i, ComputationVariables::matrix_to_variable_index_, ComputationVariables::NumVariables(), and ComputationVariables::variable_to_matrix_.

Referenced by ComputationVariables::Init().

121  {
122  variable_to_matrix_.clear();
124  int32 num_matrices = matrix_to_variable_index_.size() - 1;
125  for (int32 matrix_index = 1; matrix_index < num_matrices; matrix_index++) {
126  int32 start_variable = matrix_to_variable_index_[matrix_index],
127  end_variable = matrix_to_variable_index_[matrix_index + 1];
128  for (int32 i = start_variable; i < end_variable; i++)
129  variable_to_matrix_[i] = matrix_index;
130  }
131 }
std::vector< int32 > variable_to_matrix_
Definition: nnet-analyze.h:207
std::vector< int32 > matrix_to_variable_index_
Definition: nnet-analyze.h:197
std::string DescribeVariable ( int32  variable) const

Definition at line 208 of file nnet-analyze.cc.

References ComputationVariables::column_split_points_, KALDI_ASSERT, ComputationVariables::matrix_to_variable_index_, ComputationVariables::num_variables_, ComputationVariables::row_split_points_, and ComputationVariables::variable_to_matrix_.

Referenced by ComputationChecker::CheckComputationRewrite(), and ComputationChecker::CheckComputationUndefined().

208  {
209  KALDI_ASSERT(variable >= 0 && variable < num_variables_);
210  int32 matrix_index = variable_to_matrix_[variable],
211  offset = variable - matrix_to_variable_index_[matrix_index],
212  num_column_variables = column_split_points_[matrix_index].size() - 1,
213  num_row_variables = row_split_points_[matrix_index].size() - 1,
214  column_variable = offset % num_column_variables,
215  row_variable = offset / num_column_variables;
216  KALDI_ASSERT(column_variable >= 0 && row_variable >= 0 &&
217  row_variable < num_row_variables &&
218  column_variable < num_column_variables);
219  std::ostringstream os;
220  os << 'm' << matrix_index;
221  if (num_row_variables != 1 || num_column_variables != 1) {
222  os << '(';
223  if (num_row_variables == 1) {
224  os << ':';
225  } else {
226  os << row_split_points_[matrix_index][row_variable] << ':'
227  << row_split_points_[matrix_index][row_variable+1] - 1;
228  }
229  os << ',';
230  if (num_column_variables == 1) {
231  os << ':';
232  } else {
233  os << column_split_points_[matrix_index][column_variable] << ':'
234  << column_split_points_[matrix_index][column_variable+1] - 1;
235  }
236  os << ')';
237  }
238  return os.str();
239 }
std::vector< std::vector< int32 > > row_split_points_
Definition: nnet-analyze.h:188
std::vector< int32 > variable_to_matrix_
Definition: nnet-analyze.h:207
std::vector< int32 > matrix_to_variable_index_
Definition: nnet-analyze.h:197
std::vector< std::vector< int32 > > column_split_points_
Definition: nnet-analyze.h:185
#define KALDI_ASSERT(cond)
Definition: kaldi-error.h:169
int32 FindIndexOf ( const std::vector< int32 > &  sorted_vec,
int32  i 
)
staticprivate

Definition at line 73 of file nnet-analyze.cc.

References rnnlm::i, and KALDI_ASSERT.

Referenced by ComputationVariables::ComputeVariablesForSubmatrix().

73  {
74  // std::lower_bound does a binary search -> faster than std::find.
75  std::vector<int32>::const_iterator iter = std::lower_bound(
76  vec.begin(), vec.end(), i);
77  KALDI_ASSERT(*iter == i);
78  return iter - vec.begin();
79 }
#define KALDI_ASSERT(cond)
Definition: kaldi-error.h:169
int32 GetMatrixForVariable ( int32  variable) const

Definition at line 141 of file nnet-analyze.cc.

References KALDI_ASSERT, and ComputationVariables::variable_to_matrix_.

141  {
142  KALDI_ASSERT(static_cast<size_t>(variable) < variable_to_matrix_.size());
143  return variable_to_matrix_[variable];
144 }
std::vector< int32 > variable_to_matrix_
Definition: nnet-analyze.h:207
#define KALDI_ASSERT(cond)
Definition: kaldi-error.h:169
void Init ( const NnetComputation computation)

Definition at line 133 of file nnet-analyze.cc.

References ComputationVariables::ComputeSplitPoints(), ComputationVariables::ComputeVariablesForSubmatrix(), ComputationVariables::ComputeVariableToMatrix(), KALDI_ASSERT, and ComputationVariables::row_split_points_.

Referenced by Analyzer::Init(), kaldi::nnet3::MoveSizingCommands(), and NnetComputer::NnetComputer().

133  {
134  // don't call this twice on the same object..
136  ComputeSplitPoints(computation);
137  ComputeVariablesForSubmatrix(computation);
139 }
std::vector< std::vector< int32 > > row_split_points_
Definition: nnet-analyze.h:188
void ComputeSplitPoints(const NnetComputation &computation)
Definition: nnet-analyze.cc:25
#define KALDI_ASSERT(cond)
Definition: kaldi-error.h:169
void ComputeVariablesForSubmatrix(const NnetComputation &computation)
Definition: nnet-analyze.cc:81
void RecordAccessForSubmatrix ( int32  submatrix_index,
AccessType  access_type,
CommandAttributes ca 
) const

Definition at line 168 of file nnet-analyze.cc.

References ComputationVariables::AppendVariablesForSubmatrix(), KALDI_ASSERT, kaldi::nnet3::kReadAccess, kaldi::nnet3::kReadWriteAccess, kaldi::nnet3::kWriteAccess, CommandAttributes::matrices_read, CommandAttributes::matrices_written, CommandAttributes::submatrices_read, CommandAttributes::submatrices_written, ComputationVariables::submatrix_is_whole_matrix_, ComputationVariables::submatrix_to_matrix_, CommandAttributes::variables_read, and CommandAttributes::variables_written.

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

171  {
172  if (submatrix_index == 0)
173  return;
174  KALDI_ASSERT(static_cast<size_t>(submatrix_index) <
175  submatrix_to_matrix_.size());
176  int32 matrix_index = submatrix_to_matrix_[submatrix_index];
177  bool is_whole_matrix = submatrix_is_whole_matrix_[submatrix_index];
178  switch (access_type) {
179  case kReadAccess:
180  AppendVariablesForSubmatrix(submatrix_index,
181  &(ca->variables_read));
182  ca->matrices_read.push_back(matrix_index);
183  ca->submatrices_read.push_back(submatrix_index);
184  break;
185  case kWriteAccess:
186  AppendVariablesForSubmatrix(submatrix_index,
187  &(ca->variables_written));
188  ca->submatrices_written.push_back(submatrix_index);
189  ca->matrices_written.push_back(matrix_index);
190  // if submatrix does not span the full row range of the matrix,
191  // a write operation has to be considered a read/write operation
192  // on the underlying matrix
193  if (!is_whole_matrix)
194  ca->matrices_read.push_back(matrix_index);
195  break;
196  case kReadWriteAccess:
197  AppendVariablesForSubmatrix(submatrix_index,
198  &(ca->variables_written));
199  AppendVariablesForSubmatrix(submatrix_index,
200  &(ca->variables_read));
201  ca->submatrices_written.push_back(submatrix_index);
202  ca->submatrices_read.push_back(submatrix_index);
203  ca->matrices_written.push_back(matrix_index);
204  ca->matrices_read.push_back(matrix_index);
205  }
206 }
std::vector< int32 > submatrix_to_matrix_
Definition: nnet-analyze.h:199
void AppendVariablesForSubmatrix(int32 submatrix_index, std::vector< int32 > *variable_indexes) const
#define KALDI_ASSERT(cond)
Definition: kaldi-error.h:169
std::vector< bool > submatrix_is_whole_matrix_
Definition: nnet-analyze.h:203

Member Data Documentation

std::vector<std::vector<int32> > column_split_points_
private
std::vector<bool> submatrix_is_whole_matrix_
private
std::vector<int32> submatrix_to_matrix_
private
std::vector<int32> variable_to_matrix_
private
std::vector<std::vector<int32> > variables_for_submatrix_
private

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