All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Modules Pages
ComputationLoopedOptimizer Class Reference
Collaboration diagram for ComputationLoopedOptimizer:

Public Member Functions

 ComputationLoopedOptimizer (const Nnet &nnet, NnetComputation *computation)
 
bool Optimize ()
 

Static Private Member Functions

static int32 FindTimeShift (const NnetComputation &computation)
 
static void CreateMatrixPairs (const NnetComputation &computation, std::vector< std::pair< int32, int32 > > *matrix_to_pair)
 
static int32 NormalizeCindexes (std::vector< Cindex > *cindexes)
 
static void GetPairToMatrixMap (std::vector< std::pair< int32, int32 > > &matrix_to_pair, unordered_map< std::pair< int32, int32 >, int32, PairHasher< int32 > > *pair_to_matrix)
 
static void ConvertListsToPairLists (const std::vector< std::vector< int32 > > &active_matrices, const std::vector< std::pair< int32, int32 > > &matrix_to_pair, std::vector< std::vector< std::pair< int32, int32 > > > *active_pairs)
 
static bool ListsAreEqualExceptForPossibleShift (const std::vector< std::pair< int32, int32 > > &a, const std::vector< std::pair< int32, int32 > > &b, int32 shift)
 
static bool FindFirstRepeat (const std::vector< std::vector< std::pair< int32, int32 > > > &active_pairs, int32 time_shift_per_segment, int32 *seg1, int32 *seg2)
 
static void GetIdentifiedMatrices (const std::vector< std::pair< int32, int32 > > &pair_list1, const std::vector< std::pair< int32, int32 > > &pair_list2, const unordered_map< std::pair< int32, int32 >, int32, PairHasher< int32 > > &pair_to_matrix, std::vector< int32 > *matrix_list1, std::vector< int32 > *matrix_list2)
 
static void CheckIdentifiedMatrices (const NnetComputation &computation, const std::vector< int32 > &list1, const std::vector< int32 > &list2, int32 time_difference)
 
static void FormInfiniteLoop (int32 command1, int32 command2, NnetComputation *computation)
 
static void AddMatrixSwapCommands (const std::vector< int32 > &matrices1, const std::vector< int32 > &matrices2, NnetComputation *computation)
 
static void GetMatrixSwapOrder (const std::vector< int32 > &matrices1, const std::vector< int32 > &matrices2, std::vector< std::pair< int32, int32 > > *swaps)
 
static void FindActiveMatrices (const NnetComputation &computation, const Analyzer &analyzer, const std::vector< int32 > &splice_point_commands, std::vector< std::vector< int32 > > *active_matrices)
 Given a list of command indexes ('splice_point_commands') which are expected to be command indexes of the kNoOperationMarker at segment boundaries, this function outputs for each of these command indexes a list of matrices which are 'active' at that point in time. More...
 

Private Attributes

const Nnetnnet_
 
NnetComputationcomputation_
 
Analyzer analyzer_
 
std::vector< std::pair< int32,
int32 > > 
matrix_to_pair_
 
std::vector< int32 > splice_point_commands_
 

Detailed Description

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

Constructor & Destructor Documentation

ComputationLoopedOptimizer ( const Nnet nnet,
NnetComputation computation 
)
inline

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

3311  :
3312  nnet_(nnet), computation_(computation) { }

Member Function Documentation

void AddMatrixSwapCommands ( const std::vector< int32 > &  matrices1,
const std::vector< int32 > &  matrices2,
NnetComputation computation 
)
staticprivate

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

References NnetComputation::Command::command_type, NnetComputation::commands, ComputationLoopedOptimizer::GetMatrixSwapOrder(), NnetComputation::GetWholeSubmatrices(), rnnlm::i, KALDI_ASSERT, kaldi::nnet3::kGotoLabel, and kaldi::nnet3::kSwapMatrix.

Referenced by ComputationLoopedOptimizer::Optimize().

3841  {
3842  std::vector<std::pair<int32, int32> > swaps;
3843  // Note: in 'easy' cases where matrices1 and matrices2 are disjoint,
3844  // 'swaps' will just be the vector { (matrices1[0],matrices2[0]),
3845  // (matrices1[1],matrices2[1]), ... },
3846  // but in some cases these may need to get reordered.
3847  GetMatrixSwapOrder(matrices1, matrices2, &swaps);
3848 
3849  NnetComputation::Command goto_label_command = computation->commands.back();
3850  KALDI_ASSERT(goto_label_command.command_type == kGotoLabel);
3851  computation->commands.pop_back();
3852 
3853  // the following vector gives us, for each matrix index, a submatrix index
3854  // that covers the whole of that matrix (needed because the commands
3855  // require submatrix indexes)
3856  std::vector<int32> whole_submatrices;
3857  computation->GetWholeSubmatrices(&whole_submatrices);
3858  size_t num_matrices = whole_submatrices.size();
3859 
3860  for (size_t i = 0; i < swaps.size(); i++) {
3861  int32 m1 = swaps[i].first, m2 = swaps[i].second;
3862  KALDI_ASSERT(static_cast<size_t>(m1) < num_matrices &&
3863  static_cast<size_t>(m2) < num_matrices);
3864  int32 s1 = whole_submatrices[m1], s2 = whole_submatrices[m2];
3865  computation->commands.push_back(
3866  NnetComputation::Command(kSwapMatrix, s1, s2));
3867  }
3868  computation->commands.push_back(goto_label_command);
3869 }
#define KALDI_ASSERT(cond)
Definition: kaldi-error.h:169
static void GetMatrixSwapOrder(const std::vector< int32 > &matrices1, const std::vector< int32 > &matrices2, std::vector< std::pair< int32, int32 > > *swaps)
void CheckIdentifiedMatrices ( const NnetComputation computation,
const std::vector< int32 > &  list1,
const std::vector< int32 > &  list2,
int32  time_difference 
)
staticprivate

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

References NnetComputation::MatrixDebugInfo::cindexes, rnnlm::i, NnetComputation::MatrixDebugInfo::is_deriv, KALDI_ASSERT, kaldi::nnet3::kNoTime, NnetComputation::matrices, NnetComputation::matrix_debug_info, NnetComputation::MatrixInfo::num_cols, NnetComputation::MatrixInfo::num_rows, and NnetComputation::MatrixInfo::stride_type.

Referenced by ComputationLoopedOptimizer::Optimize().

3754  {
3755  KALDI_ASSERT(time_difference > 0);
3756  KALDI_ASSERT(list1.size() == list2.size());
3757  KALDI_ASSERT(!computation.matrix_debug_info.empty());
3758  for (size_t i = 0; i < list1.size(); i++) {
3759  int32 m1 = list1[i], m2 = list2[i];
3760  const NnetComputation::MatrixInfo
3761  &matrix_info1 = computation.matrices[m1],
3762  &matrix_info2 = computation.matrices[m2];
3763  KALDI_ASSERT(matrix_info1.num_rows == matrix_info2.num_rows &&
3764  matrix_info1.num_cols == matrix_info2.num_cols &&
3765  matrix_info1.stride_type == matrix_info2.stride_type);
3766  const NnetComputation::MatrixDebugInfo
3767  &debug_info1 = computation.matrix_debug_info[m1],
3768  &debug_info2 = computation.matrix_debug_info[m2];
3769  KALDI_ASSERT(debug_info1.is_deriv == debug_info2.is_deriv);
3770  KALDI_ASSERT(debug_info1.cindexes.size() == debug_info2.cindexes.size());
3771  std::vector<Cindex>::const_iterator iter1 = debug_info1.cindexes.begin(),
3772  end1 = debug_info1.cindexes.end(),
3773  iter2 = debug_info2.cindexes.begin();
3774  for (; iter1 != end1; iter1++,iter2++) {
3775  KALDI_ASSERT(iter2->first == iter1->first &&
3776  iter2->second.n == iter1->second.n &&
3777  ((iter1->second.t == kNoTime && iter2->second.t == kNoTime) ||
3778  iter2->second.t == iter1->second.t + time_difference) &&
3779  iter2->second.x == iter1->second.x);
3780  }
3781  }
3782 }
#define KALDI_ASSERT(cond)
Definition: kaldi-error.h:169
const int kNoTime
Definition: nnet-common.cc:554
void ConvertListsToPairLists ( const std::vector< std::vector< int32 > > &  active_matrices,
const std::vector< std::pair< int32, int32 > > &  matrix_to_pair,
std::vector< std::vector< std::pair< int32, int32 > > > *  active_pairs 
)
staticprivate

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

References KALDI_ASSERT.

Referenced by ComputationLoopedOptimizer::Optimize().

3611  {
3612  active_pairs->clear();
3613  active_pairs->resize(active_matrices.size());
3614  int32 num_matrices = matrix_to_pair.size();
3615  for (size_t seg = 0; seg < active_matrices.size(); seg++) {
3616  const std::vector<int32> &this_active_matrix_list = active_matrices[seg];
3617  std::vector<std::pair<int32, int32> > &this_active_pair_list =
3618  (*active_pairs)[seg];
3619  this_active_pair_list.resize(this_active_matrix_list.size());
3620  std::vector<int32>::const_iterator iter = this_active_matrix_list.begin(),
3621  end = this_active_matrix_list.end();
3622  std::vector<std::pair<int32, int32> >::iterator
3623  out_iter = this_active_pair_list.begin();
3624  for (; iter != end; ++iter, ++out_iter) {
3625  KALDI_ASSERT(*iter > 0 && *iter < num_matrices);
3626  *out_iter = matrix_to_pair[*iter];
3627  }
3628  }
3629 }
#define KALDI_ASSERT(cond)
Definition: kaldi-error.h:169
void CreateMatrixPairs ( const NnetComputation computation,
std::vector< std::pair< int32, int32 > > *  matrix_to_pair 
)
staticprivate

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

References KALDI_ASSERT, NnetComputation::matrices, NnetComputation::matrix_debug_info, and ComputationLoopedOptimizer::NormalizeCindexes().

Referenced by ComputationLoopedOptimizer::Optimize().

3565  {
3566  typedef unordered_map<std::vector<Cindex>, int32,
3567  CindexVectorHasher> MapType;
3568  int32 cur_vector_id = 1;
3569  // Note: cindex_map just maps the vector<Cindex> to a unique value,
3570  // and then we manually work out a unique id that takes into
3571  // account the 'is_deriv' values.
3572  MapType cindex_map;
3573  int32 num_matrices = computation.matrices.size();
3574  matrix_to_pair->resize(num_matrices);
3575  KALDI_ASSERT(computation.matrix_debug_info.size() == num_matrices);
3576  for (int32 m = 1; m < num_matrices; m++) {
3577  KALDI_ASSERT(!computation.matrix_debug_info[m].cindexes.empty());
3578  std::vector<Cindex> cindexes = computation.matrix_debug_info[m].cindexes;
3579  int32 t_offset = NormalizeCindexes(&cindexes);
3580  MapType::const_iterator iter = cindex_map.find(cindexes);
3581  int32 vector_id;
3582  if (iter != cindex_map.end()) {
3583  vector_id = iter->second;
3584  } else {
3585  vector_id = cur_vector_id++;
3586  cindex_map[cindexes] = vector_id;
3587  }
3588  bool is_deriv = computation.matrix_debug_info[m].is_deriv;
3589  int32 unique_id = 2 * vector_id + (is_deriv ? 1 : 0);
3590  (*matrix_to_pair)[m].first = unique_id;
3591  (*matrix_to_pair)[m].second = t_offset;
3592  }
3593 }
static int32 NormalizeCindexes(std::vector< Cindex > *cindexes)
#define KALDI_ASSERT(cond)
Definition: kaldi-error.h:169
void FindActiveMatrices ( const NnetComputation computation,
const Analyzer analyzer,
const std::vector< int32 > &  splice_point_commands,
std::vector< std::vector< int32 > > *  active_matrices 
)
staticprivate

Given a list of command indexes ('splice_point_commands') which are expected to be command indexes of the kNoOperationMarker at segment boundaries, this function outputs for each of these command indexes a list of matrices which are 'active' at that point in time.

By 'active' we mean that the matrix has been written to before that time (note, we don't count initialization with zeros as being written to); and will be read after that time. These is the list of matrices that 'need to be in scope' at those points in time. '*active_matrices' is indexed by the same index as 'splice_point_commands', and is then a list of active matrices, in numerical order of matrix index. Note: for each i, (*active_matrices)[i] will be sorted and unique.

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

References ComputationAnalysis::FirstNontrivialAccess(), NnetComputation::GetWholeSubmatrices(), rnnlm::i, kaldi::IsSortedAndUniq(), KALDI_ASSERT, ComputationAnalysis::LastAccess(), and NnetComputation::matrices.

Referenced by ComputationLoopedOptimizer::Optimize().

3716  {
3717  int32 num_matrices = computation.matrices.size();
3718  int32 num_splice_points = splice_point_commands.size();
3719  active_matrices->clear();
3720  active_matrices->resize(num_splice_points);
3721  // this object just makes available some extra functions, vs. the Analyzer
3722  // object.
3723  ComputationAnalysis analysis(computation, analyzer);
3724  KALDI_ASSERT(IsSortedAndUniq(splice_point_commands));
3725 
3726  // the following vector gives us, for each matrix index, a submatrix index
3727  // that covers the whole of that matrix (needed by interface of 'analysis' object).
3728  std::vector<int32> whole_submatrices;
3729  computation.GetWholeSubmatrices(&whole_submatrices);
3730  for (int32 m = 1; m < num_matrices; m++) {
3731  // the following are command indexes, comparable with the indexes
3732  // in 'splice_point_commands'.
3733  int32 s = whole_submatrices[m], // submatrix consisting of the whole of
3734  // 'm'.
3735  first_access = analysis.FirstNontrivialAccess(s),
3736  last_access = analysis.LastAccess(s);
3737  for (int32 i = 0; i < num_splice_points; i++) {
3738  int32 splice_point = splice_point_commands[i];
3739  if (first_access < splice_point && last_access > splice_point) {
3740  // If the block of time during which the matrix is accessed, includes
3741  // this command index, then the matrix is considered 'active' at this
3742  // time.
3743  (*active_matrices)[i].push_back(m);
3744  }
3745  }
3746  }
3747 }
#define KALDI_ASSERT(cond)
Definition: kaldi-error.h:169
bool IsSortedAndUniq(const std::vector< T > &vec)
Returns true if the vector is sorted and contains each element only once.
Definition: stl-utils.h:63
bool FindFirstRepeat ( const std::vector< std::vector< std::pair< int32, int32 > > > &  active_pairs,
int32  time_shift_per_segment,
int32 *  seg1,
int32 *  seg2 
)
staticprivate

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

References KALDI_ASSERT, and ComputationLoopedOptimizer::ListsAreEqualExceptForPossibleShift().

Referenced by ComputationLoopedOptimizer::Optimize().

3654  {
3655  int32 num_segments = active_pairs.size();
3656  // This algorithm may seem like it would be very slow, but the number of
3657  // segments will normally be quite small (e.g. 10), and the comparison of
3658  // elements of 'active_pairs' should be fast in cases where they
3659  // differ.
3660  KALDI_ASSERT(num_segments >= 2);
3661 
3662  for (int32 s = 0; s < num_segments; s++) {
3663  for (int32 t = s + 1; t < num_segments; t++) {
3664  if (ListsAreEqualExceptForPossibleShift(active_pairs[s],
3665  active_pairs[t],
3666  (t - s) * time_shift_per_segment)) {
3667  *seg1 = s;
3668  *seg2 = t;
3669  return true;
3670  }
3671  }
3672  }
3673  return false;
3674 }
static bool ListsAreEqualExceptForPossibleShift(const std::vector< std::pair< int32, int32 > > &a, const std::vector< std::pair< int32, int32 > > &b, int32 shift)
#define KALDI_ASSERT(cond)
Definition: kaldi-error.h:169
int32 FindTimeShift ( const NnetComputation computation)
staticprivate

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

References NnetComputation::Command::arg1, NnetComputation::Command::arg2, NnetComputation::commands, kaldi::nnet3::GetCommandsOfType(), NnetComputation::IsWholeMatrix(), KALDI_ASSERT, KALDI_ERR, kaldi::nnet3::kNoOperationMarker, kaldi::nnet3::kProvideOutput, NnetComputation::matrices, NnetComputation::matrix_debug_info, and NnetComputation::submatrices.

Referenced by ComputationLoopedOptimizer::Optimize().

3490  {
3491  std::vector<int32> segment_ends;
3492  GetCommandsOfType(computation, kNoOperationMarker, &segment_ends);
3493  KALDI_ASSERT(segment_ends.size() >= 3);
3494  // Ignore the first segment as it tends to be a special case
3495  // (it has more left context),
3496  int32 second_segment_begin = segment_ends[0],
3497  third_segment_begin = segment_ends[1],
3498  fourth_segment_begin = segment_ends[2];
3499  int32 first_output_command_seg2 = -1,
3500  first_output_command_seg3 = -1;
3501  for (int32 c = second_segment_begin; c < third_segment_begin; c++)
3502  if (computation.commands[c].command_type == kProvideOutput &&
3503  first_output_command_seg2 < 0)
3504  first_output_command_seg2 = c;
3505  for (int32 c = third_segment_begin; c < fourth_segment_begin; c++)
3506  if (computation.commands[c].command_type == kProvideOutput &&
3507  first_output_command_seg3 < 0)
3508  first_output_command_seg3 = c;
3509  if (first_output_command_seg2 < 0 ||
3510  first_output_command_seg3 < 0)
3511  KALDI_ERR << "Could not locate output commands for segments 2 and 3.";
3512  const NnetComputation::Command
3513  &command2 = computation.commands[first_output_command_seg2],
3514  &command3 = computation.commands[first_output_command_seg3];
3515  int32 seg2_node = command2.arg2, seg3_node = command3.arg2;
3516  KALDI_ASSERT(seg2_node == seg3_node);
3517  int32 seg2_submatrix = command2.arg1,
3518  seg3_submatrix = command3.arg1;
3519  KALDI_ASSERT(computation.IsWholeMatrix(seg2_submatrix) &&
3520  computation.IsWholeMatrix(seg3_submatrix));
3521  int32 seg2_matrix = computation.submatrices[seg2_submatrix].matrix_index,
3522  seg3_matrix = computation.submatrices[seg3_submatrix].matrix_index;
3523  KALDI_ASSERT(computation.matrices[seg2_matrix].num_rows ==
3524  computation.matrices[seg3_matrix].num_rows);
3525  KALDI_ASSERT(!computation.matrix_debug_info.empty());
3526  const NnetComputation::MatrixDebugInfo
3527  &debug_info2 = computation.matrix_debug_info[seg2_matrix],
3528  &debug_info3 = computation.matrix_debug_info[seg3_matrix];
3529  int32 t_offset = debug_info3.cindexes[0].second.t -
3530  debug_info2.cindexes[0].second.t;
3531  int32 num_rows = debug_info2.cindexes.size();
3532  for (int32 r = 0; r < num_rows; r++) {
3533  KALDI_ASSERT(debug_info3.cindexes[r].second.t ==
3534  debug_info2.cindexes[r].second.t + t_offset);
3535  }
3536  return t_offset;
3537 }
void GetCommandsOfType(const NnetComputation &computation, CommandType t, std::vector< int32 > *command_indexes)
This utility function works out from a computation, the command-indexes of the commands of the given ...
#define KALDI_ERR
Definition: kaldi-error.h:127
#define KALDI_ASSERT(cond)
Definition: kaldi-error.h:169
void FormInfiniteLoop ( int32  command1,
int32  command2,
NnetComputation computation 
)
staticprivate

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

References NnetComputation::commands, KALDI_ASSERT, kaldi::nnet3::kGotoLabel, kaldi::nnet3::kNoOperationLabel, and kaldi::nnet3::kNoOperationPermanent.

Referenced by ComputationLoopedOptimizer::Optimize().

3874  {
3875  KALDI_ASSERT(static_cast<int32>(computation->commands.size()) >=
3876  command2 + 1 && command1 < command2);
3877  KALDI_ASSERT(
3878  computation->commands[command1].command_type == kNoOperationPermanent &&
3879  computation->commands[command2].command_type == kNoOperationPermanent);
3880  // Remove any commands after 'command2'.
3881  computation->commands.resize(command2 + 1);
3882  computation->commands[command2].command_type = kGotoLabel;
3883  computation->commands[command2].arg1 = command1;
3884  NnetComputation::Command c(kNoOperationLabel);
3885  computation->commands.insert(computation->commands.begin() + command1,
3886  c);
3887  // Now the kNoOperationLabel command is at position 'command1'.
3888 }
#define KALDI_ASSERT(cond)
Definition: kaldi-error.h:169
void GetIdentifiedMatrices ( const std::vector< std::pair< int32, int32 > > &  pair_list1,
const std::vector< std::pair< int32, int32 > > &  pair_list2,
const unordered_map< std::pair< int32, int32 >, int32, PairHasher< int32 > > &  pair_to_matrix,
std::vector< int32 > *  matrix_list1,
std::vector< int32 > *  matrix_list2 
)
staticprivate

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

References KALDI_ASSERT, and KALDI_ERR.

Referenced by ComputationLoopedOptimizer::Optimize().

3682  {
3683  size_t size = pair_list1.size();
3684  KALDI_ASSERT(pair_list2.size() == size);
3685  matrix_list1->clear();
3686  matrix_list2->clear();
3687  matrix_list1->reserve(size);
3688  matrix_list2->reserve(size);
3689  std::vector<std::pair<int32, int32> >::const_iterator
3690  iter1 = pair_list1.begin(), end1 = pair_list1.end(),
3691  iter2 = pair_list2.begin();
3692  for (; iter1 != end1; ++iter1, ++iter2) {
3693  if (iter1->second == iter2->second)
3694  continue;
3695  // skip those that have no time shift, we won't have to do any swapping for
3696  // those.
3697  unordered_map<std::pair<int32, int32>, int32,
3698  PairHasher<int32> >::const_iterator
3699  map_iter1 = pair_to_matrix.find(*iter1),
3700  map_iter2 = pair_to_matrix.find(*iter2);
3701  if (map_iter1 == pair_to_matrix.end() ||
3702  map_iter2 == pair_to_matrix.end())
3703  KALDI_ERR << "Could not find pair in map (code error)";
3704  matrix_list1->push_back(map_iter1->second);
3705  matrix_list2->push_back(map_iter2->second);
3706  }
3707 }
#define KALDI_ERR
Definition: kaldi-error.h:127
#define KALDI_ASSERT(cond)
Definition: kaldi-error.h:169
void GetMatrixSwapOrder ( const std::vector< int32 > &  matrices1,
const std::vector< int32 > &  matrices2,
std::vector< std::pair< int32, int32 > > *  swaps 
)
staticprivate

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

References rnnlm::i, and KALDI_ASSERT.

Referenced by ComputationLoopedOptimizer::AddMatrixSwapCommands().

3789  {
3790  KALDI_ASSERT(matrices1.size() == matrices2.size());
3791  swaps->clear();
3792  int32 num_matrices = matrices1.size();
3793  std::vector<bool> processed(num_matrices, false);
3794  std::vector<int32> queue;
3795 
3796  // num_loops is just for infinite-loop detection.
3797  int32 num_loops = 0;
3798  for (; static_cast<int32>(swaps->size()) < num_matrices; num_loops++) {
3799  for (int32 i = 0; i < num_matrices; i++) {
3800  if (processed[i])
3801  continue;
3802  int32 m1 = matrices1[i], m2 = matrices2[i];
3803  std::vector<int32>::const_iterator iter =
3804  std::lower_bound(matrices2.begin(), matrices2.end(), m1);
3805  if (iter == matrices2.end() || *iter != m1) {
3806  // Matrix m1 does not appear in the list 'matrices2', so
3807  // we are safe to process it at any time.
3808  swaps->push_back(std::pair<int32,int32>(m1, m2));
3809  processed[i] = true;
3810  } else {
3811  int32 m1_pos_in_matrices2 = iter - matrices2.begin();
3812  if (processed[m1_pos_in_matrices2]) {
3813  // We're safe to do this swap now, because the matrix m1 has already
3814  // appeared on the RHS of a swap, and by this point has been
3815  // deallocated, in effect.
3816  swaps->push_back(std::pair<int32,int32>(m1, m2));
3817  processed[i] = true;
3818  }
3819  // else do nothing, we cannot process m1 yet because
3820  // at this point in the computation it is still allocated.
3821  }
3822  }
3823  // The following assert is to check that we don't loop infinitely. We can
3824  // prove that infinite looping won't happen, after on proving that there can
3825  // be no cycles like (m1, m2), (m2, m3), (m3, m1) (the length of 3 is chosen
3826  // arbitrarily as an example). If such a cycle existed, we can reach a
3827  // contradiction based on the time-index (t) of the first cindex in m1.
3828  // Define t1 = that time index, t2 the same for m2, t3 the same for m3. The
3829  // existence of the three pairs [as pairs like (matrices1[i], matrices2[i])]
3830  // implies that t2 > t1, t3 > t2, and t1 > t3 respectively, but this is
3831  // impossible.
3832  // This shows that all chains of dependencies must terminate.
3833  KALDI_ASSERT(num_loops <= num_matrices);
3834  }
3835 }
#define KALDI_ASSERT(cond)
Definition: kaldi-error.h:169
void GetPairToMatrixMap ( std::vector< std::pair< int32, int32 > > &  matrix_to_pair,
unordered_map< std::pair< int32, int32 >, int32, PairHasher< int32 > > *  pair_to_matrix 
)
staticprivate

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

Referenced by ComputationLoopedOptimizer::Optimize().

3598  {
3599  int32 num_matrices = matrix_to_pair.size();
3600  // actually there are one fewer matrices than num_matrices.
3601  pair_to_matrix->clear();
3602  for (int32 m = 1; m < num_matrices; m++)
3603  (*pair_to_matrix)[matrix_to_pair[m]] = m;
3604 }
bool ListsAreEqualExceptForPossibleShift ( const std::vector< std::pair< int32, int32 > > &  a,
const std::vector< std::pair< int32, int32 > > &  b,
int32  shift 
)
staticprivate

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

References rnnlm::i.

Referenced by ComputationLoopedOptimizer::FindFirstRepeat().

3635  {
3636  size_t size = a.size();
3637  if (b.size() != size)
3638  return false;
3639  for (size_t i = 0; i < size; i++) {
3640  const std::pair<int32, int32> &p1 = a[i],
3641  &p2 = b[i];
3642  if (p1.first != p2.first)
3643  return false;
3644  if (p2.second != p1.second + shift && p2.second != p1.second)
3645  return false;
3646  }
3647  return true;
3648 }
int32 NormalizeCindexes ( std::vector< Cindex > *  cindexes)
inlinestaticprivate

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

References KALDI_ERR, and kaldi::nnet3::kNoTime.

Referenced by ComputationLoopedOptimizer::CreateMatrixPairs().

3541  {
3542  std::vector<Cindex>::iterator iter = cindexes->begin(),
3543  end = cindexes->end();
3544  int32 ans;
3545  for (; iter != end; iter++) {
3546  if (iter->second.t != kNoTime) {
3547  ans = iter->second.t;
3548  break;
3549  }
3550  }
3551  if (iter == end) {
3552  // this should not happen.
3553  KALDI_ERR << "All t values are kNoTime in matrix.";
3554  }
3555  iter = cindexes->begin();
3556  for (; iter != end; iter++)
3557  if (iter->second.t != kNoTime)
3558  iter->second.t -= ans;
3559  return ans;
3560 }
#define KALDI_ERR
Definition: kaldi-error.h:127
const int kNoTime
Definition: nnet-common.cc:554
bool Optimize ( )

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

References ComputationLoopedOptimizer::AddMatrixSwapCommands(), ComputationLoopedOptimizer::analyzer_, ComputationLoopedOptimizer::CheckIdentifiedMatrices(), ComputationLoopedOptimizer::computation_, ComputationLoopedOptimizer::ConvertListsToPairLists(), ComputationLoopedOptimizer::CreateMatrixPairs(), ComputationLoopedOptimizer::FindActiveMatrices(), ComputationLoopedOptimizer::FindFirstRepeat(), ComputationLoopedOptimizer::FindTimeShift(), kaldi::nnet3::FixGotoLabel(), ComputationLoopedOptimizer::FormInfiniteLoop(), kaldi::nnet3::GetCommandsOfType(), ComputationLoopedOptimizer::GetIdentifiedMatrices(), ComputationLoopedOptimizer::GetPairToMatrixMap(), Analyzer::Init(), KALDI_ASSERT, KALDI_VLOG, kaldi::nnet3::kNoOperationPermanent, NnetComputation::matrix_debug_info, ComputationLoopedOptimizer::nnet_, and kaldi::nnet3::RenumberComputation().

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

3892  {
3895  "You must request matrix debug info when compiling "
3896  "looped computations.");
3897 
3898  // get the indexes of potential splice points, one per segment of the
3899  // computation. We locate the splice points where kNoOperationPermanent is.
3900  // This is guaranteed to be after the inputs have been received, and before
3901  // the bulk of the computation in the segment, and of course before we provide
3902  // the output. It happens that by choosing this as the splice point we avoid
3903  // certain problems that would arise, for instance, if we chose the segment
3904  // boundaries (kNoOperationMarker).
3905  std::vector<int32> splice_points;
3907  &splice_points);
3908  int32 time_shift_per_segment = FindTimeShift(*computation_);
3909 
3910 
3911  std::vector<std::vector<int32> > active_matrices;
3912  // Find the list of matrices active at each of the potential splice points.
3913  FindActiveMatrices(*computation_, analyzer_, splice_points,
3914  &active_matrices);
3915 
3916  // Find a representation of the matrices of the computation as pairs
3917  // (unique_id, time_offset) that are more amenable to finding
3918  // matrices that represet lists of Cindexes that differ only by
3919  // a time offset.
3920  std::vector<std::pair<int32, int32> > matrix_to_pair;
3921  CreateMatrixPairs(*computation_, &matrix_to_pair);
3922 
3923  // Create the reverse map from pair to matrix index; we'll need it later.
3924  unordered_map<std::pair<int32, int32>, int32, PairHasher<int32> > pair_to_matrix;
3925  GetPairToMatrixMap(matrix_to_pair, &pair_to_matrix);
3926 
3927  // get lists of matrix per splice-point in the pair representation.
3928  std::vector<std::vector<std::pair<int32, int32> > > pair_lists;
3929  ConvertListsToPairLists(active_matrices, matrix_to_pair,
3930  &pair_lists);
3931 
3932  // Note: seg1 and seg2 are indexes into 'splice_points', representing
3933  // potential splice points (located near the beginnings of segments).
3934  int32 seg1, seg2;
3935  if (!FindFirstRepeat(pair_lists,
3936  time_shift_per_segment,
3937  &seg1, &seg2)) {
3938  KALDI_VLOG(2) << "Could not find repeats of variables.";
3939  return false;
3940  }
3941 
3942  std::vector<int32> seg1_matrices, seg2_matrices;
3943  GetIdentifiedMatrices(pair_lists[seg1], pair_lists[seg2],
3944  pair_to_matrix,
3945  &seg1_matrices, &seg2_matrices);
3946 
3947  int32 time_difference = time_shift_per_segment * (seg2 - seg1);
3948  CheckIdentifiedMatrices(*computation_, seg1_matrices, seg2_matrices,
3949  time_difference);
3950 
3951  FormInfiniteLoop(splice_points[seg1], splice_points[seg2], computation_);
3952 
3953  AddMatrixSwapCommands(seg1_matrices, seg2_matrices, computation_);
3954 
3956 
3958 
3959  return true;
3960 }
static void ConvertListsToPairLists(const std::vector< std::vector< int32 > > &active_matrices, const std::vector< std::pair< int32, int32 > > &matrix_to_pair, std::vector< std::vector< std::pair< int32, int32 > > > *active_pairs)
void GetCommandsOfType(const NnetComputation &computation, CommandType t, std::vector< int32 > *command_indexes)
This utility function works out from a computation, the command-indexes of the commands of the given ...
std::vector< MatrixDebugInfo > matrix_debug_info
void RenumberComputation(NnetComputation *computation)
This function detects submatrices and matrices that are never used (e.g.
static void AddMatrixSwapCommands(const std::vector< int32 > &matrices1, const std::vector< int32 > &matrices2, NnetComputation *computation)
static void GetIdentifiedMatrices(const std::vector< std::pair< int32, int32 > > &pair_list1, const std::vector< std::pair< int32, int32 > > &pair_list2, const unordered_map< std::pair< int32, int32 >, int32, PairHasher< int32 > > &pair_to_matrix, std::vector< int32 > *matrix_list1, std::vector< int32 > *matrix_list2)
static void GetPairToMatrixMap(std::vector< std::pair< int32, int32 > > &matrix_to_pair, unordered_map< std::pair< int32, int32 >, int32, PairHasher< int32 > > *pair_to_matrix)
static void CheckIdentifiedMatrices(const NnetComputation &computation, const std::vector< int32 > &list1, const std::vector< int32 > &list2, int32 time_difference)
void Init(const Nnet &nnet, const NnetComputation &computation)
static void FindActiveMatrices(const NnetComputation &computation, const Analyzer &analyzer, const std::vector< int32 > &splice_point_commands, std::vector< std::vector< int32 > > *active_matrices)
Given a list of command indexes ('splice_point_commands') which are expected to be command indexes of...
static void CreateMatrixPairs(const NnetComputation &computation, std::vector< std::pair< int32, int32 > > *matrix_to_pair)
static bool FindFirstRepeat(const std::vector< std::vector< std::pair< int32, int32 > > > &active_pairs, int32 time_shift_per_segment, int32 *seg1, int32 *seg2)
void FixGotoLabel(NnetComputation *computation)
This function ensures that the arg1 of a final command of type kGotoLabel is the same as the command ...
static void FormInfiniteLoop(int32 command1, int32 command2, NnetComputation *computation)
#define KALDI_ASSERT(cond)
Definition: kaldi-error.h:169
#define KALDI_VLOG(v)
Definition: kaldi-error.h:136
static int32 FindTimeShift(const NnetComputation &computation)

Member Data Documentation

Analyzer analyzer_
private

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

Referenced by ComputationLoopedOptimizer::Optimize().

NnetComputation* computation_
private

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

Referenced by ComputationLoopedOptimizer::Optimize().

std::vector<std::pair<int32, int32> > matrix_to_pair_
private

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

const Nnet& nnet_
private

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

Referenced by ComputationLoopedOptimizer::Optimize().

std::vector<int32> splice_point_commands_
private

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


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