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

Constructor & Destructor Documentation

ComputationLoopedOptimizer ( const Nnet nnet,
NnetComputation computation 
)
inline

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

3298  :
3299  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 3826 of file nnet-optimize-utils.cc.

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

Referenced by ComputationLoopedOptimizer::Optimize().

3829  {
3830  std::vector<std::pair<int32, int32> > swaps;
3831  // Note: in 'easy' cases where matrices1 and matrices2 are disjoint,
3832  // 'swaps' will just be the vector { (matrices1[0],matrices2[0]),
3833  // (matrices1[1],matrices2[1]), ... },
3834  // but in some cases these may need to get reordered.
3835  GetMatrixSwapOrder(matrices1, matrices2, &swaps);
3836 
3837  NnetComputation::Command goto_label_command = computation->commands.back();
3838  KALDI_ASSERT(goto_label_command.command_type == kGotoLabel);
3839  computation->commands.pop_back();
3840 
3841  // the following vector gives us, for each matrix index, a submatrix index
3842  // that covers the whole of that matrix (needed because the commands
3843  // require submatrix indexes)
3844  std::vector<int32> whole_submatrices;
3845  computation->GetWholeSubmatrices(&whole_submatrices);
3846  size_t num_matrices = whole_submatrices.size();
3847 
3848  for (size_t i = 0; i < swaps.size(); i++) {
3849  int32 m1 = swaps[i].first, m2 = swaps[i].second;
3850  KALDI_ASSERT(static_cast<size_t>(m1) < num_matrices &&
3851  static_cast<size_t>(m2) < num_matrices);
3852  int32 s1 = whole_submatrices[m1], s2 = whole_submatrices[m2];
3853  computation->commands.push_back(
3854  NnetComputation::Command(
3855  kAllocMatrixFromOther, s1, s2));
3856  }
3857  computation->commands.push_back(goto_label_command);
3858 }
#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 3738 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().

3742  {
3743  KALDI_ASSERT(time_difference > 0);
3744  KALDI_ASSERT(list1.size() == list2.size());
3745  KALDI_ASSERT(!computation.matrix_debug_info.empty());
3746  for (size_t i = 0; i < list1.size(); i++) {
3747  int32 m1 = list1[i], m2 = list2[i];
3748  const NnetComputation::MatrixInfo
3749  &matrix_info1 = computation.matrices[m1],
3750  &matrix_info2 = computation.matrices[m2];
3751  KALDI_ASSERT(matrix_info1.num_rows == matrix_info2.num_rows &&
3752  matrix_info1.num_cols == matrix_info2.num_cols &&
3753  matrix_info1.stride_type == matrix_info2.stride_type);
3754  const NnetComputation::MatrixDebugInfo
3755  &debug_info1 = computation.matrix_debug_info[m1],
3756  &debug_info2 = computation.matrix_debug_info[m2];
3757  KALDI_ASSERT(debug_info1.is_deriv == debug_info2.is_deriv);
3758  KALDI_ASSERT(debug_info1.cindexes.size() == debug_info2.cindexes.size());
3759  std::vector<Cindex>::const_iterator iter1 = debug_info1.cindexes.begin(),
3760  end1 = debug_info1.cindexes.end(),
3761  iter2 = debug_info2.cindexes.begin();
3762  for (; iter1 != end1; iter1++,iter2++) {
3763  KALDI_ASSERT(iter2->first == iter1->first &&
3764  iter2->second.n == iter1->second.n &&
3765  ((iter1->second.t == kNoTime && iter2->second.t == kNoTime) ||
3766  iter2->second.t == iter1->second.t + time_difference) &&
3767  iter2->second.x == iter1->second.x);
3768  }
3769  }
3770 }
#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 3596 of file nnet-optimize-utils.cc.

References KALDI_ASSERT.

Referenced by ComputationLoopedOptimizer::Optimize().

3599  {
3600  active_pairs->clear();
3601  active_pairs->resize(active_matrices.size());
3602  int32 num_matrices = matrix_to_pair.size();
3603  for (size_t seg = 0; seg < active_matrices.size(); seg++) {
3604  const std::vector<int32> &this_active_matrix_list = active_matrices[seg];
3605  std::vector<std::pair<int32, int32> > &this_active_pair_list =
3606  (*active_pairs)[seg];
3607  this_active_pair_list.resize(this_active_matrix_list.size());
3608  std::vector<int32>::const_iterator iter = this_active_matrix_list.begin(),
3609  end = this_active_matrix_list.end();
3610  std::vector<std::pair<int32, int32> >::iterator
3611  out_iter = this_active_pair_list.begin();
3612  for (; iter != end; ++iter, ++out_iter) {
3613  KALDI_ASSERT(*iter > 0 && *iter < num_matrices);
3614  *out_iter = matrix_to_pair[*iter];
3615  }
3616  }
3617 }
#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 3551 of file nnet-optimize-utils.cc.

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

Referenced by ComputationLoopedOptimizer::Optimize().

3553  {
3554  typedef unordered_map<std::vector<Cindex>, int32,
3555  CindexVectorHasher> MapType;
3556  int32 cur_vector_id = 1;
3557  // Note: cindex_map just maps the vector<Cindex> to a unique value,
3558  // and then we manually work out a unique id that takes into
3559  // account the 'is_deriv' values.
3560  MapType cindex_map;
3561  int32 num_matrices = computation.matrices.size();
3562  matrix_to_pair->resize(num_matrices);
3563  KALDI_ASSERT(computation.matrix_debug_info.size() == num_matrices);
3564  for (int32 m = 1; m < num_matrices; m++) {
3565  KALDI_ASSERT(!computation.matrix_debug_info[m].cindexes.empty());
3566  std::vector<Cindex> cindexes = computation.matrix_debug_info[m].cindexes;
3567  int32 t_offset = NormalizeCindexes(&cindexes);
3568  MapType::const_iterator iter = cindex_map.find(cindexes);
3569  int32 vector_id;
3570  if (iter != cindex_map.end()) {
3571  vector_id = iter->second;
3572  } else {
3573  vector_id = cur_vector_id++;
3574  cindex_map[cindexes] = vector_id;
3575  }
3576  bool is_deriv = computation.matrix_debug_info[m].is_deriv;
3577  int32 unique_id = 2 * vector_id + (is_deriv ? 1 : 0);
3578  (*matrix_to_pair)[m].first = unique_id;
3579  (*matrix_to_pair)[m].second = t_offset;
3580  }
3581 }
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 3700 of file nnet-optimize-utils.cc.

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

Referenced by ComputationLoopedOptimizer::Optimize().

3704  {
3705  int32 num_matrices = computation.matrices.size();
3706  int32 num_splice_points = splice_point_commands.size();
3707  active_matrices->clear();
3708  active_matrices->resize(num_splice_points);
3709  // this object just makes available some extra functions, vs. the Analyzer
3710  // object.
3711  ComputationAnalysis analysis(computation, analyzer);
3712  KALDI_ASSERT(IsSortedAndUniq(splice_point_commands));
3713 
3714  // the following vector gives us, for each matrix index, a submatrix index
3715  // that covers the whole of that matrix (needed by interface of 'analysis' object).
3716  std::vector<int32> whole_submatrices;
3717  computation.GetWholeSubmatrices(&whole_submatrices);
3718  for (int32 m = 1; m < num_matrices; m++) {
3719  // the following are command indexes, comparable with the indexes
3720  // in 'splice_point_commands'.
3721  int32 s = whole_submatrices[m], // submatrix consisting of the whole of
3722  // 'm'.
3723  first_access = analysis.FirstAccess(s),
3724  last_access = analysis.LastAccess(s);
3725  for (int32 i = 0; i < num_splice_points; i++) {
3726  int32 splice_point = splice_point_commands[i];
3727  if (first_access < splice_point && last_access > splice_point) {
3728  // If the block of time during which the matrix is accessed, includes
3729  // this command index, then the matrix is considered 'active' at this
3730  // time.
3731  (*active_matrices)[i].push_back(m);
3732  }
3733  }
3734  }
3735 }
#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 3639 of file nnet-optimize-utils.cc.

References KALDI_ASSERT, and ComputationLoopedOptimizer::ListsAreEqualExceptForPossibleShift().

Referenced by ComputationLoopedOptimizer::Optimize().

3642  {
3643  int32 num_segments = active_pairs.size();
3644  // This algorithm may seem like it would be very slow, but the number of
3645  // segments will normally be quite small (e.g. 10), and the comparison of
3646  // elements of 'active_pairs' should be fast in cases where they
3647  // differ.
3648  KALDI_ASSERT(num_segments >= 2);
3649 
3650  for (int32 s = 0; s < num_segments; s++) {
3651  for (int32 t = s + 1; t < num_segments; t++) {
3652  if (ListsAreEqualExceptForPossibleShift(active_pairs[s],
3653  active_pairs[t],
3654  (t - s) * time_shift_per_segment)) {
3655  *seg1 = s;
3656  *seg2 = t;
3657  return true;
3658  }
3659  }
3660  }
3661  return false;
3662 }
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 3477 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().

3478  {
3479  std::vector<int32> segment_ends;
3480  GetCommandsOfType(computation, kNoOperationMarker, &segment_ends);
3481  KALDI_ASSERT(segment_ends.size() >= 3);
3482  // Ignore the first segment as it tends to be a special case
3483  // (it has more left context),
3484  int32 second_segment_begin = segment_ends[0],
3485  third_segment_begin = segment_ends[1],
3486  fourth_segment_begin = segment_ends[2];
3487  int32 first_output_command_seg2 = -1,
3488  first_output_command_seg3 = -1;
3489  for (int32 c = second_segment_begin; c < third_segment_begin; c++)
3490  if (computation.commands[c].command_type == kProvideOutput &&
3491  first_output_command_seg2 < 0)
3492  first_output_command_seg2 = c;
3493  for (int32 c = third_segment_begin; c < fourth_segment_begin; c++)
3494  if (computation.commands[c].command_type == kProvideOutput &&
3495  first_output_command_seg3 < 0)
3496  first_output_command_seg3 = c;
3497  if (first_output_command_seg2 < 0 ||
3498  first_output_command_seg3 < 0)
3499  KALDI_ERR << "Could not locate output commands for segments 2 and 3.";
3500  const NnetComputation::Command
3501  &command2 = computation.commands[first_output_command_seg2],
3502  &command3 = computation.commands[first_output_command_seg3];
3503  int32 seg2_node = command2.arg2, seg3_node = command3.arg2;
3504  KALDI_ASSERT(seg2_node == seg3_node);
3505  int32 seg2_submatrix = command2.arg1,
3506  seg3_submatrix = command3.arg1;
3507  KALDI_ASSERT(computation.IsWholeMatrix(seg2_submatrix) &&
3508  computation.IsWholeMatrix(seg3_submatrix));
3509  int32 seg2_matrix = computation.submatrices[seg2_submatrix].matrix_index,
3510  seg3_matrix = computation.submatrices[seg3_submatrix].matrix_index;
3511  KALDI_ASSERT(computation.matrices[seg2_matrix].num_rows ==
3512  computation.matrices[seg3_matrix].num_rows);
3513  KALDI_ASSERT(!computation.matrix_debug_info.empty());
3514  const NnetComputation::MatrixDebugInfo
3515  &debug_info2 = computation.matrix_debug_info[seg2_matrix],
3516  &debug_info3 = computation.matrix_debug_info[seg3_matrix];
3517  int32 t_offset = debug_info3.cindexes[0].second.t -
3518  debug_info2.cindexes[0].second.t;
3519  int32 num_rows = debug_info2.cindexes.size();
3520  for (int32 r = 0; r < num_rows; r++) {
3521  KALDI_ASSERT(debug_info3.cindexes[r].second.t ==
3522  debug_info2.cindexes[r].second.t + t_offset);
3523  }
3524  return t_offset;
3525 }
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 3861 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().

3863  {
3864  KALDI_ASSERT(static_cast<int32>(computation->commands.size()) >=
3865  command2 + 1 && command1 < command2);
3866  KALDI_ASSERT(
3867  computation->commands[command1].command_type == kNoOperationPermanent &&
3868  computation->commands[command2].command_type == kNoOperationPermanent);
3869  // Remove any commands after 'command2'.
3870  computation->commands.resize(command2 + 1);
3871  computation->commands[command2].command_type = kGotoLabel;
3872  computation->commands[command2].arg1 = command1;
3873  NnetComputation::Command c(kNoOperationLabel);
3874  computation->commands.insert(computation->commands.begin() + command1,
3875  c);
3876  // Now the kNoOperationLabel command is at position 'command1'.
3877 }
#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 3665 of file nnet-optimize-utils.cc.

References KALDI_ASSERT, and KALDI_ERR.

Referenced by ComputationLoopedOptimizer::Optimize().

3670  {
3671  size_t size = pair_list1.size();
3672  KALDI_ASSERT(pair_list2.size() == size);
3673  matrix_list1->clear();
3674  matrix_list2->clear();
3675  matrix_list1->reserve(size);
3676  matrix_list2->reserve(size);
3677  std::vector<std::pair<int32, int32> >::const_iterator
3678  iter1 = pair_list1.begin(), end1 = pair_list1.end(),
3679  iter2 = pair_list2.begin();
3680  for (; iter1 != end1; ++iter1, ++iter2) {
3681  if (iter1->second == iter2->second)
3682  continue;
3683  // skip those that have no time shift, we won't have to do any swapping for
3684  // those.
3685  unordered_map<std::pair<int32, int32>, int32,
3686  PairHasher<int32> >::const_iterator
3687  map_iter1 = pair_to_matrix.find(*iter1),
3688  map_iter2 = pair_to_matrix.find(*iter2);
3689  if (map_iter1 == pair_to_matrix.end() ||
3690  map_iter2 == pair_to_matrix.end())
3691  KALDI_ERR << "Could not find pair in map (code error)";
3692  matrix_list1->push_back(map_iter1->second);
3693  matrix_list2->push_back(map_iter2->second);
3694  }
3695 }
#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 3774 of file nnet-optimize-utils.cc.

References rnnlm::i, and KALDI_ASSERT.

Referenced by ComputationLoopedOptimizer::AddMatrixSwapCommands().

3777  {
3778  KALDI_ASSERT(matrices1.size() == matrices2.size());
3779  swaps->clear();
3780  int32 num_matrices = matrices1.size();
3781  std::vector<bool> processed(num_matrices, false);
3782  std::vector<int32> queue;
3783 
3784  // num_loops is just for infinite-loop detection.
3785  int32 num_loops = 0;
3786  for (; static_cast<int32>(swaps->size()) < num_matrices; num_loops++) {
3787  for (int32 i = 0; i < num_matrices; i++) {
3788  if (processed[i])
3789  continue;
3790  int32 m1 = matrices1[i], m2 = matrices2[i];
3791  std::vector<int32>::const_iterator iter =
3792  std::lower_bound(matrices2.begin(), matrices2.end(), m1);
3793  if (iter == matrices2.end() || *iter != m1) {
3794  // Matrix m1 does not appear in the list 'matrices2', so
3795  // we are safe to process it at any time.
3796  swaps->push_back(std::pair<int32,int32>(m1, m2));
3797  processed[i] = true;
3798  } else {
3799  int32 m1_pos_in_matrices2 = iter - matrices2.begin();
3800  if (processed[m1_pos_in_matrices2]) {
3801  // We're safe to do this swap now, because the matrix m1 has already
3802  // appeared on the RHS of a swap, and by this point has been
3803  // deallocated, in effect.
3804  swaps->push_back(std::pair<int32,int32>(m1, m2));
3805  processed[i] = true;
3806  }
3807  // else do nothing, we cannot process m1 yet because
3808  // at this point in the computation it is still allocated.
3809  }
3810  }
3811  // The following assert is to check that we don't loop infinitely. We can
3812  // prove that infinite looping won't happen, after on proving that there can
3813  // be no cycles like (m1, m2), (m2, m3), (m3, m1) (the length of 3 is chosen
3814  // arbitrarily as an example). If such a cycle existed, we can reach a
3815  // contradiction based on the time-index (t) of the first cindex in m1.
3816  // Define t1 = that time index, t2 the same for m2, t3 the same for m3. The
3817  // existence of the three pairs [as pairs like (matrices1[i], matrices2[i])]
3818  // implies that t2 > t1, t3 > t2, and t1 > t3 respectively, but this is
3819  // impossible.
3820  // This shows that all chains of dependencies must terminate.
3821  KALDI_ASSERT(num_loops <= num_matrices);
3822  }
3823 }
#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 3584 of file nnet-optimize-utils.cc.

Referenced by ComputationLoopedOptimizer::Optimize().

3586  {
3587  int32 num_matrices = matrix_to_pair.size();
3588  // actually there are one fewer matrices than num_matrices.
3589  pair_to_matrix->clear();
3590  for (int32 m = 1; m < num_matrices; m++)
3591  (*pair_to_matrix)[matrix_to_pair[m]] = m;
3592 }
bool ListsAreEqualExceptForPossibleShift ( const std::vector< std::pair< int32, int32 > > &  a,
const std::vector< std::pair< int32, int32 > > &  b,
int32  shift 
)
staticprivate

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

References rnnlm::i.

Referenced by ComputationLoopedOptimizer::FindFirstRepeat().

3623  {
3624  size_t size = a.size();
3625  if (b.size() != size)
3626  return false;
3627  for (size_t i = 0; i < size; i++) {
3628  const std::pair<int32, int32> &p1 = a[i],
3629  &p2 = b[i];
3630  if (p1.first != p2.first)
3631  return false;
3632  if (p2.second != p1.second + shift && p2.second != p1.second)
3633  return false;
3634  }
3635  return true;
3636 }
int32 NormalizeCindexes ( std::vector< Cindex > *  cindexes)
inlinestaticprivate

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

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

Referenced by ComputationLoopedOptimizer::CreateMatrixPairs().

3529  {
3530  std::vector<Cindex>::iterator iter = cindexes->begin(),
3531  end = cindexes->end();
3532  int32 ans;
3533  for (; iter != end; iter++) {
3534  if (iter->second.t != kNoTime) {
3535  ans = iter->second.t;
3536  break;
3537  }
3538  }
3539  if (iter == end) {
3540  // this should not happen.
3541  KALDI_ERR << "All t values are kNoTime in matrix.";
3542  }
3543  iter = cindexes->begin();
3544  for (; iter != end; iter++)
3545  if (iter->second.t != kNoTime)
3546  iter->second.t -= ans;
3547  return ans;
3548 }
#define KALDI_ERR
Definition: kaldi-error.h:127
const int kNoTime
Definition: nnet-common.cc:554
bool Optimize ( )

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

3881  {
3884  "You must request matrix debug info when compiling "
3885  "looped computations.");
3886 
3887  // get the indexes of potential splice points, one per segment of the
3888  // computation. We locate the splice points where kNoOperationPermanent is.
3889  // This is guaranteed to be after the inputs have been received, and before
3890  // the bulk of the computation in the segment, and of course before we provide
3891  // the output. It happens that by choosing this as the splice point we avoid
3892  // certain problems that would arise, for instance, if we chose the segment
3893  // boundaries (kNoOperationMarker).
3894  std::vector<int32> splice_points;
3896  &splice_points);
3897  int32 time_shift_per_segment = FindTimeShift(*computation_);
3898 
3899 
3900  std::vector<std::vector<int32> > active_matrices;
3901  // Find the list of matrices active at each of the potential splice points.
3902  FindActiveMatrices(*computation_, analyzer_, splice_points,
3903  &active_matrices);
3904 
3905  // Find a representation of the matrices of the computation as pairs
3906  // (unique_id, time_offset) that are more amenable to finding
3907  // matrices that represet lists of Cindexes that differ only by
3908  // a time offset.
3909  std::vector<std::pair<int32, int32> > matrix_to_pair;
3910  CreateMatrixPairs(*computation_, &matrix_to_pair);
3911 
3912  // Create the reverse map from pair to matrix index; we'll need it later.
3913  unordered_map<std::pair<int32, int32>, int32, PairHasher<int32> > pair_to_matrix;
3914  GetPairToMatrixMap(matrix_to_pair, &pair_to_matrix);
3915 
3916  // get lists of matrix per splice-point in the pair representation.
3917  std::vector<std::vector<std::pair<int32, int32> > > pair_lists;
3918  ConvertListsToPairLists(active_matrices, matrix_to_pair,
3919  &pair_lists);
3920 
3921  // Note: seg1 and seg2 are indexes into 'splice_points', representing
3922  // potential splice points (located near the beginnings of segments).
3923  int32 seg1, seg2;
3924  if (!FindFirstRepeat(pair_lists,
3925  time_shift_per_segment,
3926  &seg1, &seg2)) {
3927  KALDI_VLOG(2) << "Could not find repeats of variables.";
3928  return false;
3929  }
3930 
3931  std::vector<int32> seg1_matrices, seg2_matrices;
3932  GetIdentifiedMatrices(pair_lists[seg1], pair_lists[seg2],
3933  pair_to_matrix,
3934  &seg1_matrices, &seg2_matrices);
3935 
3936  int32 time_difference = time_shift_per_segment * (seg2 - seg1);
3937  CheckIdentifiedMatrices(*computation_, seg1_matrices, seg2_matrices,
3938  time_difference);
3939 
3940  FormInfiniteLoop(splice_points[seg1], splice_points[seg2], computation_);
3941 
3942  AddMatrixSwapCommands(seg1_matrices, seg2_matrices, computation_);
3943 
3945 
3947 
3948  return true;
3949 }
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 3470 of file nnet-optimize-utils.cc.

Referenced by ComputationLoopedOptimizer::Optimize().

NnetComputation* computation_
private

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

Referenced by ComputationLoopedOptimizer::Optimize().

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

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

const Nnet& nnet_
private

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

Referenced by ComputationLoopedOptimizer::Optimize().

std::vector<int32> splice_point_commands_
private

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


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