This class is responsible for merging matrices, although you probably want to access it via the the function VariableMergingOptimization(). More...

#include <nnet-optimize-utils.h>

Collaboration diagram for VariableMergingOptimizer:

[legend]

Public Member Functions
	VariableMergingOptimizer (const NnetOptimizeOptions &config, const Nnet &nnet, NnetComputation *computation)

bool	MergeVariables ()

Private Member Functions
std::pair< bool, bool >	MayBeMerged (int32 command, int32 s1, int32 s2) const
	This function returns a pair of bools saying whether we can do a (left and/or right) merge respectively, based on the conditions defined in the header. More...

void	DoMerge (int32 command_index, int32 s_to_keep, int32 m_to_discard)

void	MarkAsDirty (int32 s)
	Marks the variables underlying submatrix 's' as dirty. More...

void	Initialize ()

Private Attributes
const NnetOptimizeOptions &	config_

const Nnet &	nnet_

NnetComputation *	computation_

Analyzer	analyzer_

std::vector< std::vector< int32 > >	matrix_to_submatrix_

std::vector< bool >	variable_dirty_

bool	already_called_merge_variables_

Detailed Description

This class is responsible for merging matrices, although you probably want to access it via the the function VariableMergingOptimization().

We identify pairs of submatrices which can potentially be merged into a single submatrix.

Suppose there are two different submatrices s1 != s2 that are submatrices of different respective matrices m1 != m2, and somewhere in the computation we have a command C, which is one of: (a) the assignment command "s2 = s1", or (b) a propagate command with s1 as input and s2 as output, with a component that supports propagate in place, or (c) a backprop command with s1 as output-deriv and s2 as input-deriv, with a component that supports backprop in place.

Then the triple (C, s1, s2) is a candidate for merging. We support two types of merging: 'right merging', in which we delete s1 and use s2 instead; and 'left merging' in which we delete s2 and use s1 instead. The two types of merging may seem to be essentially equivalent, but they they are not because in general s1 and s2 may be sub-matrices of larger matrices.

Note the following definitions:

Define last-access(submatrix) as the last command that accesses that submatrix for either read or write. [note: deallocation does not count as a read or write operation].
Define first-nontrivial-access(submatrix) as the first command other than zeroing (kSetConst with 0.0) that accessed that submatrix for either read or write.
Define last-write-access(submatrix) as the last command-index that accessed the submatrix in a write operation, or -1 if there is no such command (this could happen for inputs).
Define data-invalidated-command(c, submatrix) as the first command-index after 'c' that 'submatrix' is written to; or if there is no such command, then the command index of the deallocation command for 'submatrix'; or if this does not exist, then num-commands.

The conditions that must be satisfied for merges are as follows:

Condition c1: it cannot be the case that m1 and m2 are both inputs, or that they are both outputs.
Condition c2: If either m1 or m2 is an input or an output, then s1 must be the entirety of m1 and s2 must be the entirety of m2 (this is because inputs and outputs must be whole matrices).
Condition c3: if we are left-merging (deleting s2,m2), then s2 must be the entirety of m2.
Condition c4: If we are right-merging (deleting s1,m1), then s1 must be the entirety of m1.
Condition c5: None of the the variables underlying s1 and s2 may be marked as 'dirty' (implying that they were the subjects of a previous merge during the lifetime of this class).
Condition c6: if we are left-merging (deleting s2, m2) and m2 has stride_type == kStrideEqualNumCols, then s1 must be the entirety of m1. [note: because of condition c3, we can assume that s2 is the entirety of m2.]
Condition c7: if we are right-merging (deleting s1, m1) and m1 has stride_type == kStrideEqualNumCols, then s2 must be the entirety of m2. [note: because of condition c4, we can assume that s1 is the entirety of m1.]

If the command C is case (a), i.e. an assignment operation, then the following conditions must apply:

first-nontrivial-access(s2) == C
last-write-access(s1) < C
last-access(s1) < data-invalidated-command(C, s2) Otherwise (cases (b) and (c), in-place propagate or backprop), we insist that:
first-nontrivial-access(s2) == C
last-access(s1) == C Note: in either case, these conditions imply that m2/s2 is not an input and m1/s1 is not an output. [i.e. s1 *may* be an input and s2 *may* be an output].

We can explain the procedure for both left-merge and right-merge in one, because it's the same. Define s_to_keep and m_to_keep as s1 and m1 if we're left-merging and s2 and m2 if we're right-merging, and s_to_discard and m_to_discard the opposite way.

The procedure to merge in general is as follows:

All submatrices that reference m1, make them reference m2 instead. [later we'll renumber so that there are no duplicates.] This automatically takes care of making the input and output and allocation/deallocation commands refer to the right matrix, in most cases.
We need to get rid of duplicate or unnecessary allocation commands: If m_to_discard is an input then get rid of the allocation command for m_to_keep; otherwise get rid of the allocation command of m_to_discard.
We need to get rid of duplicate or unnecessary deallocation commands: If m_to_discard is an output then get rid of the deallocation command for m_to_keep; otherwise get rid of the deallocation command for m_to_discard.

At the end when we call RemoveOrphanMatrices(), the renumbering code will automatically detect that there are duplicate submatrices, and will merge them, as well as removing the now-unused matrix indexes. After merging, we will mark the variables (i.e. row-ranges) underlying s1 and s2 as being "dirty" so they can no longer be merged during the lifetime of this class– this is so we don't have to think to hard; we apply this optimization multiple times until it makes no change (see nnet-optimize.cc:VariableMerginOptimization()).

Definition at line 133 of file nnet-optimize-utils.h.

Constructor & Destructor Documentation

◆ VariableMergingOptimizer()

VariableMergingOptimizer	(	const NnetOptimizeOptions &	config,
		const Nnet &	nnet,
		NnetComputation *	computation
	)

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

References VariableMergingOptimizer::analyzer_, VariableMergingOptimizer::computation_, kaldi::nnet3::ComputeMatrixToSubmatrix(), Analyzer::Init(), VariableMergingOptimizer::matrix_to_submatrix_, ComputationVariables::NumVariables(), VariableMergingOptimizer::variable_dirty_, and Analyzer::variables.

                                  :
     config_(config), nnet_(nnet),
     computation_(computation),
     already_called_merge_variables_(false) {
   analyzer_.Init(nnet, *computation);
   ComputeMatrixToSubmatrix(*computation_, &matrix_to_submatrix_);
   variable_dirty_.resize(analyzer_.variables.NumVariables(), false);
 }

Member Function Documentation

◆ DoMerge()

void DoMerge	(	int32	command_index,
		int32	s_to_keep,
		int32	m_to_discard
	)

private

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

References NnetComputation::Command::alpha, VariableMergingOptimizer::analyzer_, NnetComputation::Command::arg1, NnetComputation::Command::arg2, NnetComputation::Command::command_type, NnetComputation::commands, VariableMergingOptimizer::computation_, ComputationAnalysis::FirstNontrivialMatrixAccess(), kaldi::nnet3::GetSubMatrixOfSubMatrix(), kaldi::nnet3::kAcceptInput, KALDI_ASSERT, kaldi::nnet3::kMatrixCopy, kaldi::nnet3::kNoOperation, kaldi::nnet3::kSetConst, kaldi::kStrideEqualNumCols, VariableMergingOptimizer::MarkAsDirty(), NnetComputation::matrices, Analyzer::matrix_accesses, VariableMergingOptimizer::matrix_to_submatrix_, and NnetComputation::submatrices.

Referenced by VariableMergingOptimizer::MergeVariables().

                                                            {
   // Prevent further optimizations touching either submatrix (we can try again
   // in a later round of optimization, with a new instance of this class).
   MarkAsDirty(s_to_keep);
   MarkAsDirty(s_to_discard);
 
   int32 m_to_keep = computation_->submatrices[s_to_keep].matrix_index,
       m_to_discard = computation_->submatrices[s_to_discard].matrix_index;
   KALDI_ASSERT(m_to_keep != m_to_discard && m_to_keep > 0 && m_to_discard > 0);
 
   { // modify submatrices of m_to_discard to effectively be sub-matrices of
     // s_to_keep instead (they will refer to m_to_keep as the matrix_index).
     std::vector<int32>::const_iterator iter =
         matrix_to_submatrix_[m_to_discard].begin(),
         end = matrix_to_submatrix_[m_to_discard].end();
     for (; iter != end; ++iter) {
       int32 submatrix_index = *iter;
       KALDI_ASSERT(computation_->submatrices[submatrix_index].matrix_index
                    == m_to_discard);
       computation_->submatrices[submatrix_index] =
           GetSubMatrixOfSubMatrix(*computation_, submatrix_index,
                                   s_to_keep);
     }
   }
 
   ComputationAnalysis analysis(*computation_, analyzer_);
   NnetComputation::Command &c = computation_->commands[command_index];
   const std::vector<MatrixAccesses> &matrix_accesses =
       analyzer_.matrix_accesses;
 
   //  - If it was a matrix-copy (assignment) with scale 1.0, replace the
   //    assignment command with a no-op.
   //    If it was matrix-copy with a scale, leave the command there;
   //    it will have the effect of scaling the matrix (it will be
   //    mapped so that arg1 == arg2, but that is OK).
   if (c.command_type == kMatrixCopy && c.alpha == 1.0) {
     // remove the command.
     c.command_type = kNoOperation;
     c.arg1 = -1;
     c.arg2 = -1;
   }
 
   //   We want to ensure that there is only one deallocation command.
   //   If neither matrix is an output, then there will be 2 deallocation
   //   commands and we keep the one for m_to_keep (which, if the sizes
   //   differ, will be the larger of the two, so it's the one whose
   //   submatrix index refers to the entirety of the matrix).
   //   If one of them is an output, then remove the deallocation command
   //   of whichever one is not an output.
   //   As a simplification to the logic above: if the 'discard' matrix
   //   has a deallocation command (i.e. if that matrix was not an output)
   //   then remove it; otherwise remove the deallocation command of
   //   the 'keep' matrix.
 
   int32 dealloc_keep = matrix_accesses[m_to_keep].deallocate_command,
       dealloc_discard = matrix_accesses[m_to_discard].deallocate_command;
   if (dealloc_discard != -1) {
     computation_->commands[dealloc_discard].command_type = kNoOperation;
   } else {
     KALDI_ASSERT(dealloc_keep != -1);
     computation_->commands[dealloc_keep].command_type = kNoOperation;
   }
 
   {
     //   - Both m_to_keep and m_to_discard will have commands that allocate
     //     them, as all matrices do (note, kAcceptInput counts as an allocation
     //     command).  If one of them is kAcceptInput, then delete the other one,
     //     because the position of the kAcceptInput commands is important.
     //     Otherwise delete the "discard" one.  As a simplification of the logic
     //     of the previous sentence: if the "discard" allocate command is
     //     kAcceptInput then delete the "keep" allocate command, else delete
     //     the "discard" allocate command.
     //     Note: after we renumber the submatrices, they both refer to the
     //     same underlying matrix, but we need to refer to them using a
     //     submatrix that refers to the entire matrix.  The one we keep will
     //     always refer to the entire matrix.  (In the case where one of
     //     them is an input, both submatrices are guaranteed to refer to the
     //     entire matrix, this is guaranteed by the logic we use to decide
     //     which matrices we can merge).
     int32 alloc_keep = matrix_accesses[m_to_keep].allocate_command,
         alloc_discard = matrix_accesses[m_to_discard].allocate_command;
 
     KALDI_ASSERT(alloc_keep != -1 && alloc_discard != -1);
     KALDI_ASSERT(analysis.FirstNontrivialMatrixAccess(m_to_discard) >
                  alloc_keep);
 
     NnetComputation::Command
         &keep_alloc_command = computation_->commands[alloc_keep],
         &discard_alloc_command = computation_->commands[alloc_discard];
     int32 matrix_whose_zeroing_to_discard;
     if (discard_alloc_command.command_type == kAcceptInput) {
       keep_alloc_command.command_type = kNoOperation;
       matrix_whose_zeroing_to_discard = m_to_keep;
     } else {
       discard_alloc_command.command_type = kNoOperation;
       matrix_whose_zeroing_to_discard = m_to_discard;
     }
     // Now remove the command that zeroed one of the matrices
     // (the one whose allocation command we just discarded).
     int32 zeroing_command_to_discard =
      matrix_accesses[matrix_whose_zeroing_to_discard].accesses[0].command_index;
     NnetComputation::Command &zeroing_command =
         computation_->commands[zeroing_command_to_discard];
     if (zeroing_command.command_type == kSetConst &&
         zeroing_command.alpha == 0.0) {
       // if 'zeroing_command' actually *was* a zeroing command, then remove it.
       zeroing_command.command_type = kNoOperation;
     }
   }
 
   //  If the matrix to discard had stride_type == kStrideEqualNumCols, set the
   //  stride type of the matrix we're keeping to kStrideEqualNumCols.
   if (computation_->matrices[m_to_discard].stride_type == kStrideEqualNumCols) {
     computation_->matrices[m_to_keep].stride_type = kStrideEqualNumCols;
     // ... and perform an additional check.
     KALDI_ASSERT(computation_->matrices[m_to_discard].num_rows ==
                  computation_->matrices[m_to_keep].num_rows &&
                  computation_->matrices[m_to_discard].num_cols ==
                  computation_->matrices[m_to_keep].num_cols);
   }
 }

◆ Initialize()

void Initialize ( )

private

◆ MarkAsDirty()

void MarkAsDirty ( int32 s )

private

Marks the variables underlying submatrix 's' as dirty.

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

References VariableMergingOptimizer::analyzer_, ComputationVariables::AppendVariablesForSubmatrix(), KALDI_ASSERT, VariableMergingOptimizer::variable_dirty_, and Analyzer::variables.

Referenced by VariableMergingOptimizer::DoMerge().

                                                   {
   std::vector<int32> variable_indexes;
   analyzer_.variables.AppendVariablesForSubmatrix(s, &variable_indexes);
   std::vector<int32>::const_iterator iter = variable_indexes.begin(),
       end = variable_indexes.end();
   for (; iter != end; ++iter) {
     int32 v = *iter;
     KALDI_ASSERT(static_cast<size_t>(v) < variable_dirty_.size());
     variable_dirty_[v] = true;
   }
 }

◆ MayBeMerged()

std::pair< bool, bool > MayBeMerged	(	int32	command,
		int32	s1,
		int32	s2
	)		const

private

This function returns a pair of bools saying whether we can do a (left and/or right) merge respectively, based on the conditions defined in the header.

Note: if one of the variables underlying s1 or s2 is marked as 'dirty' due to a previous merge, this function will return (false,false). The terms left-merge and right-merge are defined in the extended comment above this class. Note: left_merge will always be false if config.allow_left_merge == false, and the same respectively for right_merge.

Parameters

command	[in] The command-index that assigns s2 := s1 or does a forward or backprop with s1 as the input and s2 as the output
s1	[in] A submatrix-index s1 > 0.
s2	[in] A submatrix-index s2 > 0

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

References NnetOptimizeOptions::allow_left_merge, NnetOptimizeOptions::allow_right_merge, VariableMergingOptimizer::analyzer_, ComputationVariables::AppendVariablesForSubmatrix(), NnetComputation::commands, VariableMergingOptimizer::computation_, VariableMergingOptimizer::config_, ComputationAnalysis::DataInvalidatedCommand(), ComputationAnalysis::FirstNontrivialAccess(), MatrixAccesses::is_input, MatrixAccesses::is_output, NnetComputation::IsWholeMatrix(), KALDI_ASSERT, kaldi::nnet3::kMatrixCopy, kaldi::kStrideEqualNumCols, ComputationAnalysis::LastAccess(), ComputationAnalysis::LastWriteAccess(), NnetComputation::matrices, Analyzer::matrix_accesses, NnetComputation::submatrices, VariableMergingOptimizer::variable_dirty_, and Analyzer::variables.

Referenced by VariableMergingOptimizer::MergeVariables().

                                                    {
   KALDI_ASSERT(s1 > 0 && s2 > 0 && static_cast<size_t>(command_index) <
                computation_->commands.size());
   if (!config_.allow_left_merge && !config_.allow_right_merge)
     return std::pair<bool,bool>(false,false);
   int32 m1 = computation_->submatrices[s1].matrix_index,
       m2 = computation_->submatrices[s2].matrix_index;
   // we can't merge two different submatrices of the same matrix.
   if (m1 == m2) return std::pair<bool,bool>(false,false);
   std::vector<int32> variable_indexes;
   analyzer_.variables.AppendVariablesForSubmatrix(s1, &variable_indexes);
   analyzer_.variables.AppendVariablesForSubmatrix(s2, &variable_indexes);
   std::vector<int32>::iterator iter = variable_indexes.begin(),
       end = variable_indexes.end();
   // condition c5:
   for (; iter != end; ++iter)
     if (variable_dirty_[*iter])
       return std::pair<bool,bool>(false,false);
   const std::vector<MatrixAccesses> &matrix_accesses = analyzer_.matrix_accesses;
   const MatrixAccesses &m1_access = matrix_accesses[m1],
       &m2_access = matrix_accesses[m2];
   // condition c1:
   if ((m1_access.is_input && m2_access.is_input) ||
       (m1_access.is_output && m2_access.is_output))
     return std::pair<bool,bool>(false,false);
   // condition c2:
   if ((m1_access.is_input || m1_access.is_output ||
        m2_access.is_input || m2_access.is_output) &&
       (!computation_->IsWholeMatrix(s1) ||
        !computation_->IsWholeMatrix(s2)))
     return std::pair<bool,bool>(false,false);
   bool left = config_.allow_left_merge,
       right = config_.allow_right_merge;
   // condition c3:
   if (!computation_->IsWholeMatrix(s2)) left = false;
   // condition c4:
   if (!computation_->IsWholeMatrix(s1)) right = false;
   // condition c6:
   if (computation_->matrices[m2].stride_type == kStrideEqualNumCols &&
       !computation_->IsWholeMatrix(s1)) left = false;
   // condition c7:
   if (computation_->matrices[m1].stride_type == kStrideEqualNumCols &&
       !computation_->IsWholeMatrix(s2)) right = false;
 
 
   if (!left && !right)  // save some time.
     return std::pair<bool,bool>(false,false);
   bool is_assignment = (computation_->commands[command_index].command_type ==
                         kMatrixCopy &&
                         computation_->commands[command_index].alpha == 1.0);
   ComputationAnalysis analysis(*computation_, analyzer_);
   if (is_assignment) {
     if (analysis.FirstNontrivialAccess(s2) == command_index &&
         analysis.LastWriteAccess(s1) < command_index &&
         analysis.LastAccess(s1) <
         analysis.DataInvalidatedCommand(command_index, s2)) {
       return std::pair<bool,bool>(left, right);  // possible success.
     }
   } else {
     if (analysis.FirstNontrivialAccess(s2) == command_index &&
         analysis.LastAccess(s1) == command_index) {
       return std::pair<bool,bool>(left, right);  // possible success.
     }
   }
   // failure.
   return std::pair<bool,bool>(false,false);
 }

◆ MergeVariables()

bool MergeVariables ( )

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

References VariableMergingOptimizer::already_called_merge_variables_, NnetComputation::Command::arg1, NnetComputation::Command::arg2, NnetComputation::Command::arg3, NnetComputation::Command::arg4, NnetComputation::Command::arg5, NnetComputation::Command::arg6, NnetOptimizeOptions::backprop_in_place, NnetComputation::Command::command_type, NnetComputation::commands, VariableMergingOptimizer::computation_, VariableMergingOptimizer::config_, VariableMergingOptimizer::DoMerge(), Nnet::GetComponent(), KALDI_ASSERT, kaldi::nnet3::kBackprop, kaldi::nnet3::kBackpropInPlace, kaldi::nnet3::kBackpropNoModelUpdate, kaldi::nnet3::kMatrixCopy, kaldi::nnet3::kPropagate, kaldi::nnet3::kPropagateInPlace, VariableMergingOptimizer::MayBeMerged(), VariableMergingOptimizer::nnet_, NnetOptimizeOptions::optimize, NnetOptimizeOptions::propagate_in_place, Component::Properties(), NnetOptimizeOptions::remove_assignments, kaldi::nnet3::RemoveNoOps(), and kaldi::nnet3::RenumberComputation().

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

                                               {
   KALDI_ASSERT(!already_called_merge_variables_);
   already_called_merge_variables_ = true;
   if (!config_.optimize)
     return false;
   bool merged = false;
   int32 num_commands = computation_->commands.size();
   for (int32 command_index = 0; command_index < num_commands;
        command_index++) {
     // This loop looks for pairs of sub-matrix indexes s1,s2 that we could
     // potentially merge into a single variable.
     const NnetComputation::Command &c = computation_->commands[command_index];
     int32 s1 = -1, s2 = -1;
     if (c.command_type == kMatrixCopy &&
         config_.remove_assignments) {
       s2 = c.arg1;  // s2 is the written-to matrix.
       s1 = c.arg2;
     } else if (c.command_type == kPropagate &&
                config_.propagate_in_place) {
       const Component *component = nnet_.GetComponent(c.arg1);
       if (component->Properties() & kPropagateInPlace) {
         s1 = c.arg3;
         s2 = c.arg4;  // s2 is the written-to matrix.
       }
     } else if ((c.command_type == kBackprop ||
                 c.command_type == kBackpropNoModelUpdate) &&
                config_.backprop_in_place) {
       const Component *component = nnet_.GetComponent(c.arg1);
       if (component->Properties() & kBackpropInPlace) {
         s1 = c.arg5;
         s2 = c.arg6;  // s2 is the written-to matrix.
         if (s1 == c.arg3 || s2 == c.arg3 || s1 == c.arg4 || s2 == c.arg4) {
           // we don't think this should ever happen, but just out of an
           // abundance of caution: if either of these submatrix indexes are the
           // input-value or output-value args to Backprop, don't do the optimization.
           s1 = -1;
           s2 = -1;
         }
       }
     }
     if (s1 > 0 && s2 > 0) {
       std::pair<bool,bool> p = MayBeMerged(command_index, s1, s2);
       if (p.first) {
         DoMerge(command_index, s1, s2);
         merged = true;
       } else if (p.second) {
         DoMerge(command_index, s2, s1);
         merged = true;
       }
     }
   }
   if (merged) {
     RenumberComputation(computation_);
     RemoveNoOps(computation_);
   }
   return merged;
 }