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

Constructor & Destructor Documentation

◆ ComputationLoopedOptimizer()

ComputationLoopedOptimizer ( const Nnet nnet,
NnetComputation computation 
)
inline

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

References kaldi::nnet3::Optimize().

3893  :
3894  nnet_(nnet), computation_(computation) { }

Member Function Documentation

◆ AddMatrixSwapCommands()

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

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

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

4422  {
4423  std::vector<std::pair<int32, int32> > swaps;
4424  // Note: in 'easy' cases where matrices1 and matrices2 are disjoint,
4425  // 'swaps' will just be the vector { (matrices1[0],matrices2[0]),
4426  // (matrices1[1],matrices2[1]), ... },
4427  // but in some cases these may need to get reordered.
4428  GetMatrixSwapOrder(matrices1, matrices2, &swaps);
4429 
4430  NnetComputation::Command goto_label_command = computation->commands.back();
4431  KALDI_ASSERT(goto_label_command.command_type == kGotoLabel);
4432  computation->commands.pop_back();
4433 
4434  // the following vector gives us, for each matrix index, a submatrix index
4435  // that covers the whole of that matrix (needed because the commands
4436  // require submatrix indexes)
4437  std::vector<int32> whole_submatrices;
4438  computation->GetWholeSubmatrices(&whole_submatrices);
4439  size_t num_matrices = whole_submatrices.size();
4440 
4441  for (size_t i = 0; i < swaps.size(); i++) {
4442  int32 m1 = swaps[i].first, m2 = swaps[i].second;
4443  KALDI_ASSERT(static_cast<size_t>(m1) < num_matrices &&
4444  static_cast<size_t>(m2) < num_matrices);
4445  int32 s1 = whole_submatrices[m1], s2 = whole_submatrices[m2];
4446  computation->commands.push_back(
4447  NnetComputation::Command(kSwapMatrix, s1, s2));
4448  }
4449  computation->commands.push_back(goto_label_command);
4450 }
#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)

◆ CheckIdentifiedMatrices()

void CheckIdentifiedMatrices ( const NnetComputation computation,
const std::vector< int32 > &  list1,
const std::vector< int32 > &  list2,
int32  time_difference 
)
staticprivate

Definition at line 4331 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.

4335  {
4336  KALDI_ASSERT(time_difference > 0);
4337  KALDI_ASSERT(list1.size() == list2.size());
4338  KALDI_ASSERT(!computation.matrix_debug_info.empty());
4339  for (size_t i = 0; i < list1.size(); i++) {
4340  int32 m1 = list1[i], m2 = list2[i];
4341  const NnetComputation::MatrixInfo
4342  &matrix_info1 = computation.matrices[m1],
4343  &matrix_info2 = computation.matrices[m2];
4344  KALDI_ASSERT(matrix_info1.num_rows == matrix_info2.num_rows &&
4345  matrix_info1.num_cols == matrix_info2.num_cols &&
4346  matrix_info1.stride_type == matrix_info2.stride_type);
4347  const NnetComputation::MatrixDebugInfo
4348  &debug_info1 = computation.matrix_debug_info[m1],
4349  &debug_info2 = computation.matrix_debug_info[m2];
4350  KALDI_ASSERT(debug_info1.is_deriv == debug_info2.is_deriv);
4351  KALDI_ASSERT(debug_info1.cindexes.size() == debug_info2.cindexes.size());
4352  std::vector<Cindex>::const_iterator iter1 = debug_info1.cindexes.begin(),
4353  end1 = debug_info1.cindexes.end(),
4354  iter2 = debug_info2.cindexes.begin();
4355  for (; iter1 != end1; iter1++,iter2++) {
4356  KALDI_ASSERT(iter2->first == iter1->first &&
4357  iter2->second.n == iter1->second.n &&
4358  ((iter1->second.t == kNoTime && iter2->second.t == kNoTime) ||
4359  iter2->second.t == iter1->second.t + time_difference) &&
4360  iter2->second.x == iter1->second.x);
4361  }
4362  }
4363 }
#define KALDI_ASSERT(cond)
Definition: kaldi-error.h:169
const int kNoTime
Definition: nnet-common.cc:568

◆ ConvertListsToPairLists()

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

References KALDI_ASSERT.

4192  {
4193  active_pairs->clear();
4194  active_pairs->resize(active_matrices.size());
4195  int32 num_matrices = matrix_to_pair.size();
4196  for (size_t seg = 0; seg < active_matrices.size(); seg++) {
4197  const std::vector<int32> &this_active_matrix_list = active_matrices[seg];
4198  std::vector<std::pair<int32, int32> > &this_active_pair_list =
4199  (*active_pairs)[seg];
4200  this_active_pair_list.resize(this_active_matrix_list.size());
4201  std::vector<int32>::const_iterator iter = this_active_matrix_list.begin(),
4202  end = this_active_matrix_list.end();
4203  std::vector<std::pair<int32, int32> >::iterator
4204  out_iter = this_active_pair_list.begin();
4205  for (; iter != end; ++iter, ++out_iter) {
4206  KALDI_ASSERT(*iter > 0 && *iter < num_matrices);
4207  *out_iter = matrix_to_pair[*iter];
4208  }
4209  }
4210 }
#define KALDI_ASSERT(cond)
Definition: kaldi-error.h:169

◆ CreateMatrixPairs()

void CreateMatrixPairs ( const NnetComputation computation,
std::vector< std::pair< int32, int32 > > *  matrix_to_pair 
)
staticprivate

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

References KALDI_ASSERT, NnetComputation::matrices, and NnetComputation::matrix_debug_info.

4146  {
4147  typedef unordered_map<std::vector<Cindex>, int32,
4148  CindexVectorHasher> MapType;
4149  int32 cur_vector_id = 1;
4150  // Note: cindex_map just maps the vector<Cindex> to a unique value,
4151  // and then we manually work out a unique id that takes into
4152  // account the 'is_deriv' values.
4153  MapType cindex_map;
4154  int32 num_matrices = computation.matrices.size();
4155  matrix_to_pair->resize(num_matrices);
4156  KALDI_ASSERT(computation.matrix_debug_info.size() == num_matrices);
4157  for (int32 m = 1; m < num_matrices; m++) {
4158  KALDI_ASSERT(!computation.matrix_debug_info[m].cindexes.empty());
4159  std::vector<Cindex> cindexes = computation.matrix_debug_info[m].cindexes;
4160  int32 t_offset = NormalizeCindexes(&cindexes);
4161  MapType::const_iterator iter = cindex_map.find(cindexes);
4162  int32 vector_id;
4163  if (iter != cindex_map.end()) {
4164  vector_id = iter->second;
4165  } else {
4166  vector_id = cur_vector_id++;
4167  cindex_map[cindexes] = vector_id;
4168  }
4169  bool is_deriv = computation.matrix_debug_info[m].is_deriv;
4170  int32 unique_id = 2 * vector_id + (is_deriv ? 1 : 0);
4171  (*matrix_to_pair)[m].first = unique_id;
4172  (*matrix_to_pair)[m].second = t_offset;
4173  }
4174 }
static int32 NormalizeCindexes(std::vector< Cindex > *cindexes)
#define KALDI_ASSERT(cond)
Definition: kaldi-error.h:169

◆ FindActiveMatrices()

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 (including zeroing), 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 4293 of file nnet-optimize-utils.cc.

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

4297  {
4298  int32 num_matrices = computation.matrices.size();
4299  int32 num_splice_points = splice_point_commands.size();
4300  active_matrices->clear();
4301  active_matrices->resize(num_splice_points);
4302  // this object just makes available some extra functions, vs. the Analyzer
4303  // object.
4304  ComputationAnalysis analysis(computation, analyzer);
4305  KALDI_ASSERT(IsSortedAndUniq(splice_point_commands));
4306 
4307  // the following vector gives us, for each matrix index, a submatrix index
4308  // that covers the whole of that matrix (needed by interface of 'analysis' object).
4309  std::vector<int32> whole_submatrices;
4310  computation.GetWholeSubmatrices(&whole_submatrices);
4311  for (int32 m = 1; m < num_matrices; m++) {
4312  // the following are command indexes, comparable with the indexes
4313  // in 'splice_point_commands'.
4314  int32 s = whole_submatrices[m], // submatrix consisting of the whole of
4315  // 'm'.
4316  first_access = analysis.FirstNontrivialAccess(s),
4317  last_access = analysis.LastAccess(s);
4318  for (int32 i = 0; i < num_splice_points; i++) {
4319  int32 splice_point = splice_point_commands[i];
4320  if (first_access < splice_point && last_access > splice_point) {
4321  // If the block of time during which the matrix is accessed, includes
4322  // this command index, then the matrix is considered 'active' at this
4323  // time.
4324  (*active_matrices)[i].push_back(m);
4325  }
4326  }
4327  }
4328 }
#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

◆ FindFirstRepeat()

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

References KALDI_ASSERT.

4235  {
4236  int32 num_segments = active_pairs.size();
4237  // This algorithm may seem like it would be very slow, but the number of
4238  // segments will normally be quite small (e.g. 10), and the comparison of
4239  // elements of 'active_pairs' should be fast in cases where they
4240  // differ.
4241  KALDI_ASSERT(num_segments >= 2);
4242 
4243  for (int32 s = 0; s < num_segments; s++) {
4244  for (int32 t = s + 1; t < num_segments; t++) {
4245  if (ListsAreEqualExceptForPossibleShift(active_pairs[s],
4246  active_pairs[t],
4247  (t - s) * time_shift_per_segment)) {
4248  *seg1 = s;
4249  *seg2 = t;
4250  return true;
4251  }
4252  }
4253  }
4254  return false;
4255 }
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

◆ FindTimeShift()

int32 FindTimeShift ( const NnetComputation computation)
staticprivate

Definition at line 4070 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.

4071  {
4072  std::vector<int32> segment_ends;
4073  GetCommandsOfType(computation, kNoOperationMarker, &segment_ends);
4074  KALDI_ASSERT(segment_ends.size() >= 3);
4075  // Ignore the first segment as it tends to be a special case
4076  // (it has more left context),
4077  int32 second_segment_begin = segment_ends[0],
4078  third_segment_begin = segment_ends[1],
4079  fourth_segment_begin = segment_ends[2];
4080  int32 first_output_command_seg2 = -1,
4081  first_output_command_seg3 = -1;
4082  for (int32 c = second_segment_begin; c < third_segment_begin; c++)
4083  if (computation.commands[c].command_type == kProvideOutput &&
4084  first_output_command_seg2 < 0)
4085  first_output_command_seg2 = c;
4086  for (int32 c = third_segment_begin; c < fourth_segment_begin; c++)
4087  if (computation.commands[c].command_type == kProvideOutput &&
4088  first_output_command_seg3 < 0)
4089  first_output_command_seg3 = c;
4090  if (first_output_command_seg2 < 0 ||
4091  first_output_command_seg3 < 0)
4092  KALDI_ERR << "Could not locate output commands for segments 2 and 3.";
4093  const NnetComputation::Command
4094  &command2 = computation.commands[first_output_command_seg2],
4095  &command3 = computation.commands[first_output_command_seg3];
4096  int32 seg2_node = command2.arg2, seg3_node = command3.arg2;
4097  KALDI_ASSERT(seg2_node == seg3_node);
4098  int32 seg2_submatrix = command2.arg1,
4099  seg3_submatrix = command3.arg1;
4100  KALDI_ASSERT(computation.IsWholeMatrix(seg2_submatrix) &&
4101  computation.IsWholeMatrix(seg3_submatrix));
4102  int32 seg2_matrix = computation.submatrices[seg2_submatrix].matrix_index,
4103  seg3_matrix = computation.submatrices[seg3_submatrix].matrix_index;
4104  KALDI_ASSERT(computation.matrices[seg2_matrix].num_rows ==
4105  computation.matrices[seg3_matrix].num_rows);
4106  KALDI_ASSERT(!computation.matrix_debug_info.empty());
4107  const NnetComputation::MatrixDebugInfo
4108  &debug_info2 = computation.matrix_debug_info[seg2_matrix],
4109  &debug_info3 = computation.matrix_debug_info[seg3_matrix];
4110  int32 t_offset = debug_info3.cindexes[0].second.t -
4111  debug_info2.cindexes[0].second.t;
4112  int32 num_rows = debug_info2.cindexes.size();
4113  for (int32 r = 0; r < num_rows; r++) {
4114  KALDI_ASSERT(debug_info3.cindexes[r].second.t ==
4115  debug_info2.cindexes[r].second.t + t_offset);
4116  }
4117  return t_offset;
4118 }
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

◆ FormInfiniteLoop()

void FormInfiniteLoop ( int32  command1,
int32  command2,
NnetComputation computation 
)
staticprivate

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

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

4455  {
4456  KALDI_ASSERT(static_cast<int32>(computation->commands.size()) >=
4457  command2 + 1 && command1 < command2);
4458  KALDI_ASSERT(
4459  computation->commands[command1].command_type == kNoOperationPermanent &&
4460  computation->commands[command2].command_type == kNoOperationPermanent);
4461  // Remove any commands after 'command2'.
4462  computation->commands.resize(command2 + 1);
4463  computation->commands[command2].command_type = kGotoLabel;
4464  computation->commands[command2].arg1 = command1;
4465  NnetComputation::Command c(kNoOperationLabel);
4466  computation->commands.insert(computation->commands.begin() + command1,
4467  c);
4468  // Now the kNoOperationLabel command is at position 'command1'.
4469 }
#define KALDI_ASSERT(cond)
Definition: kaldi-error.h:169

◆ GetIdentifiedMatrices()

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

References KALDI_ASSERT, and KALDI_ERR.

4263  {
4264  size_t size = pair_list1.size();
4265  KALDI_ASSERT(pair_list2.size() == size);
4266  matrix_list1->clear();
4267  matrix_list2->clear();
4268  matrix_list1->reserve(size);
4269  matrix_list2->reserve(size);
4270  std::vector<std::pair<int32, int32> >::const_iterator
4271  iter1 = pair_list1.begin(), end1 = pair_list1.end(),
4272  iter2 = pair_list2.begin();
4273  for (; iter1 != end1; ++iter1, ++iter2) {
4274  if (iter1->second == iter2->second)
4275  continue;
4276  // skip those that have no time shift, we won't have to do any swapping for
4277  // those.
4278  unordered_map<std::pair<int32, int32>, int32,
4279  PairHasher<int32> >::const_iterator
4280  map_iter1 = pair_to_matrix.find(*iter1),
4281  map_iter2 = pair_to_matrix.find(*iter2);
4282  if (map_iter1 == pair_to_matrix.end() ||
4283  map_iter2 == pair_to_matrix.end())
4284  KALDI_ERR << "Could not find pair in map (code error)";
4285  matrix_list1->push_back(map_iter1->second);
4286  matrix_list2->push_back(map_iter2->second);
4287  }
4288 }
#define KALDI_ERR
Definition: kaldi-error.h:127
#define KALDI_ASSERT(cond)
Definition: kaldi-error.h:169

◆ GetMatrixSwapOrder()

void GetMatrixSwapOrder ( const std::vector< int32 > &  matrices1,
const std::vector< int32 > &  matrices2,
std::vector< std::pair< int32, int32 > > *  swaps 
)
staticprivate

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

References rnnlm::i, and KALDI_ASSERT.

4370  {
4371  KALDI_ASSERT(matrices1.size() == matrices2.size());
4372  swaps->clear();
4373  int32 num_matrices = matrices1.size();
4374  std::vector<bool> processed(num_matrices, false);
4375  std::vector<int32> queue;
4376 
4377  // num_loops is just for infinite-loop detection.
4378  int32 num_loops = 0;
4379  for (; static_cast<int32>(swaps->size()) < num_matrices; num_loops++) {
4380  for (int32 i = 0; i < num_matrices; i++) {
4381  if (processed[i])
4382  continue;
4383  int32 m1 = matrices1[i], m2 = matrices2[i];
4384  std::vector<int32>::const_iterator iter =
4385  std::lower_bound(matrices2.begin(), matrices2.end(), m1);
4386  if (iter == matrices2.end() || *iter != m1) {
4387  // Matrix m1 does not appear in the list 'matrices2', so
4388  // we are safe to process it at any time.
4389  swaps->push_back(std::pair<int32,int32>(m1, m2));
4390  processed[i] = true;
4391  } else {
4392  int32 m1_pos_in_matrices2 = iter - matrices2.begin();
4393  if (processed[m1_pos_in_matrices2]) {
4394  // We're safe to do this swap now, because the matrix m1 has already
4395  // appeared on the RHS of a swap, and by this point has been
4396  // deallocated, in effect.
4397  swaps->push_back(std::pair<int32,int32>(m1, m2));
4398  processed[i] = true;
4399  }
4400  // else do nothing, we cannot process m1 yet because
4401  // at this point in the computation it is still allocated.
4402  }
4403  }
4404  // The following assert is to check that we don't loop infinitely. We can
4405  // prove that infinite looping won't happen, after on proving that there can
4406  // be no cycles like (m1, m2), (m2, m3), (m3, m1) (the length of 3 is chosen
4407  // arbitrarily as an example). If such a cycle existed, we can reach a
4408  // contradiction based on the time-index (t) of the first cindex in m1.
4409  // Define t1 = that time index, t2 the same for m2, t3 the same for m3. The
4410  // existence of the three pairs [as pairs like (matrices1[i], matrices2[i])]
4411  // implies that t2 > t1, t3 > t2, and t1 > t3 respectively, but this is
4412  // impossible.
4413  // This shows that all chains of dependencies must terminate.
4414  KALDI_ASSERT(num_loops <= num_matrices);
4415  }
4416 }
#define KALDI_ASSERT(cond)
Definition: kaldi-error.h:169

◆ GetPairToMatrixMap()

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

4179  {
4180  int32 num_matrices = matrix_to_pair.size();
4181  // actually there are one fewer matrices than num_matrices.
4182  pair_to_matrix->clear();
4183  for (int32 m = 1; m < num_matrices; m++)
4184  (*pair_to_matrix)[matrix_to_pair[m]] = m;
4185 }

◆ ListsAreEqualExceptForPossibleShift()

bool ListsAreEqualExceptForPossibleShift ( const std::vector< std::pair< int32, int32 > > &  a,
const std::vector< std::pair< int32, int32 > > &  b,
int32  shift 
)
staticprivate

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

References rnnlm::i.

4216  {
4217  size_t size = a.size();
4218  if (b.size() != size)
4219  return false;
4220  for (size_t i = 0; i < size; i++) {
4221  const std::pair<int32, int32> &p1 = a[i],
4222  &p2 = b[i];
4223  if (p1.first != p2.first)
4224  return false;
4225  if (p2.second != p1.second + shift && p2.second != p1.second)
4226  return false;
4227  }
4228  return true;
4229 }

◆ NormalizeCindexes()

int32 NormalizeCindexes ( std::vector< Cindex > *  cindexes)
inlinestaticprivate

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

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

4122  {
4123  std::vector<Cindex>::iterator iter = cindexes->begin(),
4124  end = cindexes->end();
4125  int32 ans;
4126  for (; iter != end; iter++) {
4127  if (iter->second.t != kNoTime) {
4128  ans = iter->second.t;
4129  break;
4130  }
4131  }
4132  if (iter == end) {
4133  // this should not happen.
4134  KALDI_ERR << "All t values are kNoTime in matrix.";
4135  }
4136  iter = cindexes->begin();
4137  for (; iter != end; iter++)
4138  if (iter->second.t != kNoTime)
4139  iter->second.t -= ans;
4140  return ans;
4141 }
#define KALDI_ERR
Definition: kaldi-error.h:127
const int kNoTime
Definition: nnet-common.cc:568

◆ Optimize()

bool Optimize ( )

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

References DerivativeTimeLimiter::computation_, kaldi::nnet3::FixGotoLabel(), kaldi::nnet3::GetCommandsOfType(), KALDI_ASSERT, KALDI_VLOG, kaldi::nnet3::kNoOperationPermanent, NnetComputation::matrix_debug_info, DerivativeTimeLimiter::nnet_, and kaldi::nnet3::RenumberComputation().

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

4473  {
4476  "You must request matrix debug info when compiling "
4477  "looped computations.");
4478 
4479  // get the indexes of potential splice points, one per segment of the
4480  // computation. We locate the splice points where kNoOperationPermanent is.
4481  // This is guaranteed to be after the inputs have been received, and before
4482  // the bulk of the computation in the segment, and of course before we provide
4483  // the output. It happens that by choosing this as the splice point we avoid
4484  // certain problems that would arise, for instance, if we chose the segment
4485  // boundaries (kNoOperationMarker).
4486  std::vector<int32> splice_points;
4488  &splice_points);
4489  int32 time_shift_per_segment = FindTimeShift(*computation_);
4490 
4491 
4492  std::vector<std::vector<int32> > active_matrices;
4493  // Find the list of matrices active at each of the potential splice points.
4494  FindActiveMatrices(*computation_, analyzer_, splice_points,
4495  &active_matrices);
4496 
4497  // Find a representation of the matrices of the computation as pairs
4498  // (unique_id, time_offset) that are more amenable to finding
4499  // matrices that represet lists of Cindexes that differ only by
4500  // a time offset.
4501  std::vector<std::pair<int32, int32> > matrix_to_pair;
4502  CreateMatrixPairs(*computation_, &matrix_to_pair);
4503 
4504  // Create the reverse map from pair to matrix index; we'll need it later.
4505  unordered_map<std::pair<int32, int32>, int32, PairHasher<int32> > pair_to_matrix;
4506  GetPairToMatrixMap(matrix_to_pair, &pair_to_matrix);
4507 
4508  // get lists of matrix per splice-point in the pair representation.
4509  std::vector<std::vector<std::pair<int32, int32> > > pair_lists;
4510  ConvertListsToPairLists(active_matrices, matrix_to_pair,
4511  &pair_lists);
4512 
4513  // Note: seg1 and seg2 are indexes into 'splice_points', representing
4514  // potential splice points (located near the beginnings of segments).
4515  int32 seg1, seg2;
4516  if (!FindFirstRepeat(pair_lists,
4517  time_shift_per_segment,
4518  &seg1, &seg2)) {
4519  KALDI_VLOG(2) << "Could not find repeats of variables.";
4520  return false;
4521  }
4522 
4523  std::vector<int32> seg1_matrices, seg2_matrices;
4524  GetIdentifiedMatrices(pair_lists[seg1], pair_lists[seg2],
4525  pair_to_matrix,
4526  &seg1_matrices, &seg2_matrices);
4527 
4528  int32 time_difference = time_shift_per_segment * (seg2 - seg1);
4529  CheckIdentifiedMatrices(*computation_, seg1_matrices, seg2_matrices,
4530  time_difference);
4531 
4532  FormInfiniteLoop(splice_points[seg1], splice_points[seg2], computation_);
4533 
4534  AddMatrixSwapCommands(seg1_matrices, seg2_matrices, computation_);
4535 
4537 
4539 
4540  return true;
4541 }
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 (&#39;splice_point_commands&#39;) 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 analyzer_
private

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

◆ computation_

NnetComputation* computation_
private

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

◆ matrix_to_pair_

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

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

◆ nnet_

const Nnet& nnet_
private

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

◆ splice_point_commands_

std::vector<int32> splice_point_commands_
private

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


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