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
NnetComputation::SubMatrixInfo	VariableInfo (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 and 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 and 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 121 of file nnet-analyze.h.

Member Function Documentation

AppendVariablesForMatrix()

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().

                                              {
  KALDI_ASSERT(static_cast<size_t>(matrix_index + 1) <
               matrix_to_variable_index_.size());
  int32 start = matrix_to_variable_index_[matrix_index],
      end = matrix_to_variable_index_[matrix_index + 1];
  variable_indexes->reserve(variable_indexes->size() + end - start);
  for (int32 variable_index = start; variable_index < end; variable_index++)
    variable_indexes->push_back(variable_index);
}

AppendVariablesForSubmatrix()

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(), VariableMergingOptimizer::MarkAsDirty(), VariableMergingOptimizer::MayBeMerged(), and ComputationVariables::RecordAccessForSubmatrix().

                                              {
  KALDI_ASSERT(static_cast<size_t>(submatrix_index) <
               variables_for_submatrix_.size());
  variable_indexes->insert(variable_indexes->end(),
                           variables_for_submatrix_[submatrix_index].begin(),
                           variables_for_submatrix_[submatrix_index].end());
}

ComputeSplitPoints()

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().

                                        {
  // note, these numbers are only valid if you include the empty zero-indexed
  // matrix/submatrix as a matrix.
  int32 num_matrices = computation.matrices.size(),
      num_submatrices = computation.submatrices.size();
  row_split_points_.resize(num_matrices);
  column_split_points_.resize(num_matrices);
  KALDI_ASSERT(computation.submatrices[0].num_rows == 0);
  for (int32 submatrix_index = 1;
       submatrix_index < num_submatrices;
       submatrix_index++) {
    const NnetComputation::SubMatrixInfo &s =
        computation.submatrices[submatrix_index];
    row_split_points_[s.matrix_index].push_back(s.row_offset);
    row_split_points_[s.matrix_index].push_back(s.row_offset + s.num_rows);
    column_split_points_[s.matrix_index].push_back(s.col_offset);
    column_split_points_[s.matrix_index].push_back(s.col_offset + s.num_cols);
  }
  for (int32 matrix_index = 1; matrix_index < num_matrices; matrix_index++) {
    // Because it's possible for matrices not to have any submatrices (after
    // pruning), we need to make sure that the beginning and end dimensions are
    // in the split points.
    column_split_points_[matrix_index].push_back(0);
    column_split_points_[matrix_index].push_back(
        computation.matrices[matrix_index].num_cols);
    row_split_points_[matrix_index].push_back(0);
    row_split_points_[matrix_index].push_back(
        computation.matrices[matrix_index].num_rows);
    SortAndUniq(&(column_split_points_[matrix_index]));
    SortAndUniq(&(row_split_points_[matrix_index]));
  }
  // note: the last split point of each matrix doesn't get its own variable index.
  matrix_to_variable_index_.resize(num_matrices + 1);
  matrix_to_variable_index_[0] = 0;
  matrix_to_variable_index_[1] = 0;
  for (int32 matrix_index = 1; matrix_index < num_matrices; matrix_index++) {
    int32 num_row_variables = row_split_points_[matrix_index].size() - 1,
        num_column_variables = column_split_points_[matrix_index].size() - 1,
        num_variables = num_row_variables * num_column_variables;
    KALDI_ASSERT(num_variables >= 1);
    matrix_to_variable_index_[matrix_index+1] =
        matrix_to_variable_index_[matrix_index] + num_variables;
  }
  num_variables_ = matrix_to_variable_index_.back();
}

ComputeVariablesForSubmatrix()

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().

                                        {
  // note, these numbers are only valid if you include the empty zero-indexed
  // matrix/submatrix as a matrix.
  int32 num_submatrices = computation.submatrices.size();

  variables_for_submatrix_.resize(num_submatrices);

  submatrix_is_whole_matrix_.resize(num_submatrices, false);
  submatrix_to_matrix_.resize(num_submatrices);
  submatrix_to_matrix_[0] = 0;

  for (int32 submatrix_index = 1;
       submatrix_index < num_submatrices;
       submatrix_index++) {
    const NnetComputation::SubMatrixInfo &s =
        computation.submatrices[submatrix_index];
    int32 matrix_index = s.matrix_index;
    submatrix_to_matrix_[submatrix_index] = matrix_index;
    int32 start_col = s.col_offset, end_col = start_col + s.num_cols,
        start_row = s.row_offset, end_row = start_row + s.num_rows;
    int32 row_start = FindIndexOf(row_split_points_[matrix_index], start_row),
        row_end = FindIndexOf(row_split_points_[matrix_index], end_row),
        col_start = FindIndexOf(column_split_points_[matrix_index], start_col),
        col_end = FindIndexOf(column_split_points_[matrix_index], end_col),
        num_column_variables = column_split_points_[matrix_index].size() - 1,
        num_row_variables = row_split_points_[matrix_index].size() - 1,
        matrix_start_variable = matrix_to_variable_index_[matrix_index];
    KALDI_ASSERT(row_end > row_start && col_end > col_start &&
                 col_end <= num_column_variables);
    std::vector<int32> &variables = variables_for_submatrix_[submatrix_index];
    for (int32 r = row_start; r < row_end; r++)
      for (int32 c = col_start; c < col_end; c++)
        variables.push_back(matrix_start_variable + r*num_column_variables + c);
    if (row_start == 0 && row_end == num_row_variables &&
        col_start == 0 && col_end == num_column_variables)
      submatrix_is_whole_matrix_[submatrix_index] = true;
  }
}

ComputeVariableToMatrix()

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().

                                                   {
  variable_to_matrix_.clear();
  variable_to_matrix_.resize(NumVariables());
  int32 num_matrices = matrix_to_variable_index_.size() - 1;
  for (int32 matrix_index = 1; matrix_index < num_matrices; matrix_index++) {
    int32 start_variable = matrix_to_variable_index_[matrix_index],
        end_variable = matrix_to_variable_index_[matrix_index + 1];
    for (int32 i = start_variable; i < end_variable; i++)
      variable_to_matrix_[i] = matrix_index;
  }
}

DescribeVariable()

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().

                                                                     {
  KALDI_ASSERT(variable >= 0 && variable < num_variables_);
  int32 matrix_index = variable_to_matrix_[variable],
      offset = variable - matrix_to_variable_index_[matrix_index],
      num_column_variables = column_split_points_[matrix_index].size() - 1,
      num_row_variables = row_split_points_[matrix_index].size() - 1,
      column_variable = offset % num_column_variables,
      row_variable = offset / num_column_variables;
  KALDI_ASSERT(column_variable >= 0 && row_variable >= 0 &&
               row_variable < num_row_variables &&
               column_variable < num_column_variables);
  std::ostringstream os;
  os << 'm' << matrix_index;
  if (num_row_variables != 1 || num_column_variables != 1) {
    os << '(';
    if (num_row_variables == 1) {
      os << ':';
    } else {
      os << row_split_points_[matrix_index][row_variable] << ':'
         << row_split_points_[matrix_index][row_variable+1] - 1;
    }
    os << ',';
    if (num_column_variables == 1) {
      os << ':';
    } else {
      os << column_split_points_[matrix_index][column_variable] << ':'
         << column_split_points_[matrix_index][column_variable+1] - 1;
    }
    os << ')';
  }
  return os.str();
}

FindIndexOf()

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().

                                                                            {
  // std::lower_bound does a binary search -> faster than std::find.
  std::vector<int32>::const_iterator iter = std::lower_bound(
      vec.begin(), vec.end(), i);
  KALDI_ASSERT(*iter == i);
  return iter - vec.begin();
}

GetMatrixForVariable()

int32 GetMatrixForVariable

(

int32

variable

)

const

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

References KALDI_ASSERT, and ComputationVariables::variable_to_matrix_.

                                                                     {
  KALDI_ASSERT(static_cast<size_t>(variable) < variable_to_matrix_.size());
  return variable_to_matrix_[variable];
}

Init()

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 NnetComputer::Init(), and kaldi::nnet3::MoveSizingCommands().

                                                                  {
  // don't call this twice on the same object..
  KALDI_ASSERT(row_split_points_.empty());
  ComputeSplitPoints(computation);
  ComputeVariablesForSubmatrix(computation);
  ComputeVariableToMatrix();
}

NumVariables()

int32 NumVariables ( ) const

inline

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

References rnnlm::i.

Referenced by kaldi::nnet3::ComputeVariableAccesses(), ComputationVariables::ComputeVariableToMatrix(), and VariableMergingOptimizer::VariableMergingOptimizer().

{ return num_variables_; }

RecordAccessForSubmatrix()

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().

                                 {
  if (submatrix_index == 0)
    return;
  KALDI_ASSERT(static_cast<size_t>(submatrix_index) <
               submatrix_to_matrix_.size());
  int32 matrix_index = submatrix_to_matrix_[submatrix_index];
  bool is_whole_matrix = submatrix_is_whole_matrix_[submatrix_index];
  switch (access_type) {
    case kReadAccess:
      AppendVariablesForSubmatrix(submatrix_index,
                                  &(ca->variables_read));
      ca->matrices_read.push_back(matrix_index);
      ca->submatrices_read.push_back(submatrix_index);
      break;
    case kWriteAccess:
      AppendVariablesForSubmatrix(submatrix_index,
                                  &(ca->variables_written));
      ca->submatrices_written.push_back(submatrix_index);
      ca->matrices_written.push_back(matrix_index);
      // if submatrix does not span the full row range of the matrix,
      // a write operation has to be considered a read/write operation
      // on the underlying matrix
      if (!is_whole_matrix)
        ca->matrices_read.push_back(matrix_index);
      break;
    case kReadWriteAccess:
      AppendVariablesForSubmatrix(submatrix_index,
                                  &(ca->variables_written));
      AppendVariablesForSubmatrix(submatrix_index,
                                  &(ca->variables_read));
      ca->submatrices_written.push_back(submatrix_index);
      ca->submatrices_read.push_back(submatrix_index);
      ca->matrices_written.push_back(matrix_index);
      ca->matrices_read.push_back(matrix_index);
  }
}

VariableInfo()

NnetComputation::SubMatrixInfo VariableInfo

(

int32

variable

)

const

Definition at line 241 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::CheckComputationUndefined().

                          {
  KALDI_ASSERT(variable >= 0 && variable < num_variables_);
  int32 matrix_index = variable_to_matrix_[variable],
      offset = variable - matrix_to_variable_index_[matrix_index],
      num_column_variables = column_split_points_[matrix_index].size() - 1,
      column_variable = offset % num_column_variables,
      row_variable = offset / num_column_variables;
  int32 row_offset = row_split_points_[matrix_index][row_variable],
      num_rows = row_split_points_[matrix_index][row_variable+1] - row_offset,
      col_offset = column_split_points_[matrix_index][column_variable],
      num_cols = column_split_points_[matrix_index][column_variable+1] -
                  col_offset;
  return NnetComputation::SubMatrixInfo(matrix_index, row_offset, num_rows,
                                        col_offset, num_cols);
}

Member Data Documentation

column_split_points_

std::vector<std::vector<int32> > column_split_points_

private

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

Referenced by ComputationVariables::ComputeSplitPoints(), ComputationVariables::ComputeVariablesForSubmatrix(), ComputationVariables::DescribeVariable(), and ComputationVariables::VariableInfo().

matrix_to_variable_index_

std::vector<int32> matrix_to_variable_index_

private

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

Referenced by ComputationVariables::AppendVariablesForMatrix(), ComputationVariables::ComputeSplitPoints(), ComputationVariables::ComputeVariablesForSubmatrix(), ComputationVariables::ComputeVariableToMatrix(), ComputationVariables::DescribeVariable(), and ComputationVariables::VariableInfo().

num_variables_

int32 num_variables_

private

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

Referenced by ComputationVariables::ComputeSplitPoints(), ComputationVariables::DescribeVariable(), and ComputationVariables::VariableInfo().

row_split_points_

std::vector<std::vector<int32> > row_split_points_

private

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

Referenced by ComputationVariables::ComputeSplitPoints(), ComputationVariables::ComputeVariablesForSubmatrix(), ComputationVariables::DescribeVariable(), ComputationVariables::Init(), and ComputationVariables::VariableInfo().

submatrix_is_whole_matrix_

std::vector<bool> submatrix_is_whole_matrix_

private

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

Referenced by ComputationVariables::ComputeVariablesForSubmatrix(), and ComputationVariables::RecordAccessForSubmatrix().

submatrix_to_matrix_

std::vector<int32> submatrix_to_matrix_

private

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

Referenced by ComputationVariables::ComputeVariablesForSubmatrix(), and ComputationVariables::RecordAccessForSubmatrix().

variable_to_matrix_

std::vector<int32> variable_to_matrix_

private

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

Referenced by ComputationVariables::ComputeVariableToMatrix(), ComputationVariables::DescribeVariable(), ComputationVariables::GetMatrixForVariable(), and ComputationVariables::VariableInfo().

variables_for_submatrix_

std::vector<std::vector<int32> > variables_for_submatrix_

private

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

Referenced by ComputationVariables::AppendVariablesForSubmatrix(), and ComputationVariables::ComputeVariablesForSubmatrix().

---

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

• nnet3/nnet-analyze.h
• nnet3/nnet-analyze.cc