// doc/dnn3_code_compilation.dox


// Copyright 2015   Johns Hopkins University (author: Daniel Povey)

// See ../../COPYING for clarification regarding multiple authors
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at

//  http://www.apache.org/licenses/LICENSE-2.0

// THIS CODE IS PROVIDED *AS IS* BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
// KIND, EITHER EXPRESS OR IMPLIED, INCLUDING WITHOUT LIMITATION ANY IMPLIED
// WARRANTIES OR CONDITIONS OF TITLE, FITNESS FOR A PARTICULAR PURPOSE,
// MERCHANTABLITY OR NON-INFRINGEMENT.
// See the Apache 2 License for the specific language governing permissions and
// limitations under the License.

namespace kaldi {
namespace nnet3 {

/**
  \page dnn3_code_compilation Compilation in the "nnet3" setup

  \section dnn3_code_compilation_intro Introduction

  This page covers the compilation process in the "nnet3" setup.  It will
  generally only be of interest to those who want to understand the internals of
  the framework.

  - Up: \ref dnn3.
  - Previous: \ref dnn3_code_data_types
  - Next: \ref dnn3_code_optimization

  \section dnn3_compile_overview Overview of compilation

   We assume that the reader is familiar with the data types introduced in
   \ref dnn3_code_data_types.  The compilation process is something that
   takes as input an Nnet and a ComputationRequest, and outputs a
   NnetComputation.  The ComputationRequest includes a representation of
   what output indexes are requested and what input indexes are available;
   the reason why we don't just supply the output indexes and let the compiler
   work out what input indexes are required, is that some networks such as RNNs
   may consume an arbitrary amount of input to produce a given output.

   Something that might be considered a part of the compilation process, but
   which we discuss in a separate page, is code optimization: see \ref dnn3_code_optimization.

 This page covers:
   - \ref dnn3_compile_graph
   - \ref dnn3_compile_steps
   - \ref dnn3_compile_compiler

  \section dnn3_compile_graph Creating the computation graph


   \subsection dnn3_compile_graph_graph Details of ComputationGraph

   We previously gave a brief introduction to struct ComputationGraph, but
  here we provide a few more details.  Remember that the ComputationGraph
  maps back and forth between Cindexes and integer cindex_ids for efficiency.
  We show just the data members of ComputationGraph here (remember that
in C++, a struct is just a class whose members are public by default):
\verbatim
struct ComputationGraph {
  // The mapping of cindex_id to Cindex.
  std::vector<Cindex> cindexes;

  // For each Cindex this tells us whether it was provided as an input to the
  // computation.
  std::vector<bool> is_input;

  // dependencies[cindex_id] gives you the list of other cindex_ids that this
  // particular cindex_id directly depends on to compute it.
  std::vector<std::vector<int32> > dependencies;
private:
  // Maps each Cindex to an integer cindex_id: reverse mapping of "cindexes".
  // Must be accessed via the GetCindexId() function.
  unordered_map<Cindex, int32, CindexHasher> cindex_to_cindex_id_;
};
\endverbatim
 The most important thing is that a ComputationGraph maps back and forth
 between Cindexes and cindex_ids (integers), and stores a list of "dependencies",
 saying for each cindex_id which other cindex_ids are required to compute it.
 The exact meaning of "dependencies" depends on the stage of the compilation.
 At early stages it contains all cindex_ids corresponding to Cindexes that
 were returned by the \ref Descriptor::GetDependencies() "GetDependencies()"
 function of class Descriptor.  Later on it is pruned back to only those dependencies
 that are actually used in the computation.
 Note that Components also have a similar \ref Component::GetDependencies() "GetDependencies()"
 function, and an \ref Component::IsComputable() "IsComputable()" function, like Descriptors.
 However, this only does someathing interesting in the case of non-simple Components.


 The ComputationGraph also has a vector "is_input", saying whether each cindex_id
 is an input to the computation.  This might seem redundant, because we could just
 look up whether its node is of type kInput.  It is needed because we have actually
 designed the framework so that you can provide previously computed values of nodes
 of type kComponent: this has an envisaged use in online decoding for speech
 recognition with things like RNNs.

 \subsection dnn3_compile_graph_building  Building the ComputationGraph


  \subsubsection dnn3_compile_graph_building_intro Introduction

 Class ComputationGraphBuilder is responsible for building the ComputationGraph.
 In the simple case where there are no optional dependencies, the process is
 quite simple.   (By optional dependencies, we mean descriptors
 with <code>Failover(X,Y)</code> or <code>IfDefined(X)</code>, or certain non-simple
 Components).  The simple version of the process is that we start with requested outputs
 of the network, compute their dependencies and add them to the ComputationGraph,
 and keep working backward adding dependencies until we hit input nodes.  At that
 point, hopefully all Cindexes we require at input nodes are ones that have been
 supplied in the ComputationRequest; if they are not supplied, we would have to
 say that the computation is not possible.


 \subsubsection dnn3_compile_graph_building_basic  Basic algorithm

 Here we describe a basic algorithm which is <em>not</em> what we use but which
 serves to motivate the actual algorithm.  While building the computation graph
 we need to be able to work out whether each Cindex is computable from supplied
 inputs.  (We will use the terms Cindex and cindex_id fairly interchangeably,
 because there is a one-to-one mapping).  One simple and natural and algorithm
 would be as follows:
    - First follow back all possible dependencies from the
      output using the <code>GetDependencies()</code> functions of Descriptors and Components.
    - In the opposite direction, starting from the input, work out which Cindexes are
      computable (using <code>IsComputable()</code>), and prune back the dependencies to just those that
      participate in the computation.
    - Check that all requested outputs were computable.
    - Prune away all cindex_ids that are not actually necessary to compute the
      outputs.
    .
 However, this algorithm wouldn't work in all cases of interest, for instance
 RNNs.  The problem is that the first phase (following back all possible dependencies)
 would run forever, with t approaching -\infin.

 \subsubsection dnn3_compile_graph_building_idea Motivation for the algorithm we use

 Instead we need a slightly more sophisticated algorithm.  We haven't proven that this algorithm
 would always terminate in all possible cases of interest, but it seems likely to terminate in all
 the cases we have in mind.  Consider the case of an RNN where some recurrent layer has a
 dependency that goes back to time t-1, and the input starts at t = 0.  Following dependencies
 will take t all the way back to -\infin, but we should be able to figure out that
 those hidden-layer Cindexes for negative t are never going to participate in the computation,
 because if we follow <em>their</em> dependencies back to the input we will see that the
 corresponding inputs were not supplied, so they are not computable.  The way we make use
 of this to avoid recursing to -\infin is to note that if a Cindex is not computable,
 there is no point following its dependencies back because we know they will never be used.
 The problem is that this is a chicken-and-egg situation because before we process the
 dependencies of a Cindex we don't <em>know</em> that it's not computable.

 \subsubsection dnn3_compile_graph_building_real The algorithm we use

 The way we solve this problem is as follows.  We assign to each Cindex an enum
 \ref ComputationGraphBuilder::ComputableInfo "ComputableInfo", defined as:
\verbatim
  enum ComputableInfo {
    kUnknown = 0,
    kComputable = 1,
    kNotComputable = 2,
    kWillNotCompute = 3
  };
\endverbatim
 whose meaning is as follows:
  - kUnknown: we are not yet sure whether this Cindex is computable
  - kComputable: we know that this Cindex is computable
  - kNotComputable: we know that this Cindex is not computable
  - kWillNotCompute: we are not going to compute this Cindex regardless of whether
    it's computable, because we have determined that it is not usable.  Treated the same
    as kNotComputable for most purposes.
    .
The way we determine whether a Cindex is usable is as follows.
We assign to each Cindex an integer \ref ComputationGraphBuilder::usable_count_ "usable_count" which functions
a little like a reference-count in memory management.  If the \ref ComputationGraphBuilder::usable_count_ "usable_count" for a Cindex
is >0, it means that that that Cindex might possibly partipate in the final computation.
We ensure that the \ref ComputationGraphBuilder::usable_count_ "usable_count" always has
a value determined by the following rules:
  - 1 if this Cindex is a requested output in the ComputationRequest.  Otherwise..
  - The number of other Cindexes j such that:
     - The ComputableInfo of j is not kNotComputable, and
     - The usable_count of j is greater than zero, and
     - This Cindex is a dependency of j in the computation graph.
     .
  .
The way we avoid infinitely recursing in the processing of dependencies is that
if the usable_count of a Cindex is zero we set its state to kWillNotCompute and
then we refrain from adding its dependencies to the computation graph.
For this to work, we make sure to process the dependencies in breadth-first
order: that is, we process dependencies at one hop from the output, then two
hops from the output, and so on.  This avoids the case where, in the RNN, we might
process the hidden layer all the way back to t = -\infin before noticing that
the corresponding inputs were not available.

Class ComputationGraphBuilder maintains two queues: one for Cindexes that
we haven't yet added their dependencies to the graph, and one
(\ref ComputationGraphBuilder::computable_queue_ "computable_queue_") for
Cindexes such that we need to re-evaluate whether they are computable
(i.e. update their ComputableInfo).  When the ComputableInfo of a Cindex
changes, we need to re-check the ComputableInfo of Cindexes that depend on it,
and to do so we add them to \ref ComputationGraphBuilder::computable_queue_ "computable_queue_".


 \subsubsection dnn3_compile_graph_building_interface Interface of ComputationGraphBuilder

We list the most important parts of the public interface of ComputationGraph Builder below;
it should be quite self-explanatory.
\verbatim
class ComputationGraphBuilder {
 public:
  ComputationGraphBuilder(const Nnet &nnet,
                          const ComputationRequest &request,
                          ComputationGraph *graph);
  // Does the initial computation (populating the graph and computing
  // whether each required cindex_id is computable), without the pruning.
  void Compute();
  // Returns true if all requested outputs are computable.  To be called after
  // Compute() but before Prune(().
  bool AllOutputsAreComputable();
  // Removed unused Cinndexes from the graph.
  void Prune();
  ...
};
\endverbatim


\section dnn3_compile_steps  Organizing the computation into steps

 \subsection dnn3_compile_steps_intro Introduction to steps

Once we have the computation graph, we have enough information in principle to
execute the computation without doing much more work.  We could sort the
Cindexes in topological order in the computation graph, and individually
evaluate each Cindex using its dependencies as inputs.  Unfortunately this
wouldn't be very efficient because matrix operations don't reach their full
efficiency unless they are operating on quite large matrices; this is
particularly true when using GPUs.  So what we want to do is to group
the Cindexes into batches such that the Cindexes in the same batch can
all be computed at the same time.  This batch is going to be called a "step",
and it will roughly correspond to one command in the NnetComputation.

We are going to arrange the set of all cindex_ids in the computation into a sequence
of steps, with the following properties:
  - All cindex_ids within a given step correspond to the same node in the graph
  - All dependencies of cindex_ids within a given step have been computed in
    earlier steps.
  .
There are also some extra, more obscure properties that the sequence of steps
must satisfy:
  - (a) Any input or output in the ComputationRequest must be in one step, with the
    Indexes in the same order as specified in the ComputationRequest.  (Note:
    inputs can be for nodes of type kComponent as well as kInput).
  - (b) If a step corresponds to a node of type kComponent (and does not correspond to
    an input in the ComputationRequest), then the immediately
    preceding step must correspond to a node of type kDescriptor, and the sequence of
    Indexes in the two steps must be identical.
  - (c) If a step corresponds to a node of type kDimRange, then there must
    be another step corresponding to the source node, with exactly the same
    Indexes appearing in the same order.  (This lets us use a sub-matrix for
    the kDimRange node).
   .
The reason for rule (b) is to ensure that the Component can use the output
of the Descriptor directly as its input, without any additional reordering or
regrouping (since such reordering and regrouping is, by design, the
responsibility of the Descriptors).  Because of this rule, it is possible
in principle for a cindex_id from a node of type kDescriptor to appear
separately in more than one different step, although this could only happen if
we were using non-simple Components.  Also, to ensure that rule (c) is satisfied
we may occasionally have to add new cindex_ids to the computation graph.

 \subsection dnn3_compile_steps_creating  Creating the sequence of steps (basic algorithm)

Here we describe a basic algorithm for creating the sequence of steps
that we <em>do not use</em>, but will serve to motivate the actual algorithm that
we'll describe later.
This basic algorithm would be:
  - First put aside Cindexes corresponding to input and output nodes,
    separate them by node-index, order within each of those steps
    to the same order as the ComputationRequests, and put them on the side.
  - Next process the intermediate Cindexes that are not inputs or outputs as follows:
    - Take the remaining Cindexes and arrange them into sets called "phases"
      where the first phase contains all Cindexes that depend only on inputs;
      and in general the n'th phase contains all remaining Cindexes that depend
      only on quantities present in phases less than n.
    - Remove from each phase all Cindexes not corresponding to nodes of type kComponent
      (we'll handle kDimRange and component-input nodes  later).
    - Order the steps by using the ordering operator of struct Index.
    - Create the steps for component-input nodes as follows:
       - For each step of type kComponent, compute the set of all its
         dependencies using the "dependencies" member of the ComputationGraph.
       - Order them using the ordering operator of struct Index.  (for simple
         Components this ensures they are in the same order as the output
         of the Component).
       - (Obscure feature): non-simple Components that want to reorder their
         inputs are allowed to do so at this point; see Component::ReorderIndexes().
       - Place this step immediately before the corresponding step of the Component.
    - Create the steps for dim-range nodes as follows:
       - Take all the Cindexes in the graph corresponding to dim-range nodes, and
         work out the step that their input comes from.
       - Note for each existing step the set of dim-range nodes that have an existing
         Cindex that gets input from that step.
       - For each existing step s, for each dim-range node that has an existing
         Cindex getting input from that step, create a step containing the same
         sequence of Indexes as step s, and place the new step immediately after step s.

  - Order all the steps so that inputs come first, intermediate steps come next,
    and output-steps come last.

 The problem with the algorithm described above is that it would end up
 splitting things into to many steps.  For instance, imagine that we have a recurrent
 layer followed by a standard feedforward layer.  The recurrent layer has to be
 split up into as many steps as there are time indexes, but the above algorithm
 would also split up the computation of the the fully-connected layer into many steps
 because those Cindexes become computable immediately after the corresponding Cindexes
 for the recurrent layer.  What we want it for it to do all computation of the
 recurrent layer, then do the computation for the fully-connected layer in one step.

 \subsection dnn3_compile_steps_creating_actual  Creating the sequence of steps (actual algorithm)

 In order to handle architectures like RNNs without creating an excessive number
 of computation steps, we first do some graph-theoretic processing on the neural
 network itself to determine the order in which we can process nodes in the
 graph.  We can express the neural network itself as a directed graph on nodes,
 where there is an arc from node A to node B if node B ever refers to quantities
 from node A (see \ref NnetToDirectedGraph()).

 The function \ref ComputeNnetComputationEpochs() produces a mapping from nodes
 to epoch indexes, where nodes that are part of the same strongly connected
 component (SCC) in the graph (e.g. nodes that are part of the recurrency in an
 RNN) go to the same epoch, but nodes that are in an earlier epoch can always
 be computed first.  That is, roughly the epoch will correspond to the layer index
 in the neural net.

 The actual algorithm, then, produces three progressively more specific orderings
 of Cindexes: first epochs, then phases, then steps.  We use essentially the algorithm
 described in the previous section, except modified to respect the division into
 epochs.   We first call \ref ComputeComputationPhases() to divide the cindexes
 into phases, and then \ref ComputeComputationSteps() which works out the actual
 steps.


\section dnn3_compile_compiler Class Compiler

\subsection dnn3_compile_compiler_intro  Introduction to class Compiler

The Compiler class has overall responsibility for turning the
ComputationRequest, together with an Nnet, into a NnetComputation.  Internally
it first creates a ComputationGraph and a sequence of steps using the classes
and functions we have introduced above.

Its public interface is very simple:
\verbatim
class Compiler {
 public:
  Compiler(const ComputationRequest &request,
           const Nnet &nnet);

  void CreateComputation(const CompilerOptions &opts,
                         NnetComputation *computation);
  ...
};
\endverbatim

\subsection dnn3_compile_compiler_creating Creating the computation

Most of the work of this class happens in its \ref Compiler::CreateComputation "CreateComputation()"
function, and the implementation of this function is below.
\verbatim
void Compiler::CreateComputation(const CompilerOptions &opts,
                                 NnetComputation *computation) {
  ComputationGraphBuilder builder(nnet_, request_, &graph_);
  builder.Compute();
  builder.Prune();

  // see function declaration's comment for meaning of "phases".
  std::vector<std::vector<int32> > phases;
  ComputeComputationPhases(nnet_, graph_, &phases);
  std::vector<std::vector<int32> > steps;
  ComputeComputationSteps(nnet_, request_, phases, &graph_, &steps);
  phases.clear();
  CreateLocationInfo(steps);
  std::vector<bool> deriv_needed;
  ComputeDerivNeeded(steps, &deriv_needed);
  CreateStepInfo(deriv_needed, &steps, computation);
  AddCommands(deriv_needed, computation);
  if (opts.output_debug_info)
    OutputDebugInfo(computation);
}
\endverbatim
The commands up to ComputeComputationSteps() correspond to things that we have
discussed above, and should be clear.  Below we will discuss some of the remaining
commands, and use them to give an overview of the compilation process.


\subsection dnn3_compile_compiler_location Setting up the location information

The function
\ref Compiler::CreateLocationInfo() "CreateLocationInfo()"
sets up a mapping \ref Compiler::cindex_id_to_location_ "cindex_id_to_location_"
that maps each cindex_id to a <em>location</em>, where a location defined as a
pair (step-index, matrix-row-index).  The matrix-row-index corresponds to the
position of the cindex_id in the vector of cindex_ids for that step.  We
previously mentioned that it's possible in principle for cindex_ids
corresponding to network-nodes of type kDescriptor that represent
\ref Nnet::IsComponentInputNode() "component inputs", to exist in more than one step; this doesn't matter here, because we
won't be relying on this information for component-input nodes.

We will be dealing with "location information" in a couple of different formats.
The  \ref Compiler::cindex_id_to_location_ "cindex_id_to_location_" vector contains
locations as pair (step-index, matrix-row-index).  Elsewhere, and later on in the
compilation process, we sometimes
deal with what we call "submat-locations" which are pairs (submatrix-index, row-index).
A submatrix-index is an index into the "submatrices" vector of the Computation.
Once we have decided where the values and derivatives for each of the steps live,
we will be able to compute the "submat-locations".

\subsection dnn3_compile_compiler_deriv_needed Checking whether derivatives are needed

Continuing to step line by line through the function \ref Compiler::CreateComputation "CreateComputation()",
we next encounter the lines:
\verbatim
  std::vector<bool> deriv_needed;
  ComputeDerivNeeded(steps, &deriv_needed);
\endverbatim
These compute an array that says for each step, whether we need to allocate the matrix of
derivatives for the <em>output</em> of that step.  The logic for the function
\ref Compiler::ComputeDerivNeeded "ComputeDerivNeeded()" is a little complicated, and
we will try to explain it.  Firstly, we will remind the user of the relevant aspects of
struct ComputationRequest:
\verbatim
struct ComputationRequest {
  std::vector<IoSpecification> inputs;
  std::vector<IoSpecification> outputs;
  bool need_model_derivative;
  ...
};

struct IoSpecification {
  std::string name;
  std::vector<Index> indexes;
  bool has_deriv;
  ...
};
\endverbatim
If <code>need_model_derivative</code> is false, and <code>has_deriv</code> is false for all inputs and outputs,
then we won't be needing to allocate matrices for any derivatives at all.  The detailed procedure follows.
First we initialize the whole <code>need_deriv</code> vector to false.  Then for each step counting upward,
we use roughly the following logic.  First define the steps we depend on as those that are listed in
dependencies of cindex_ids in this step (we can work this out from the computation graph).  Now,
   - If any step we depend on needs the derivative, this step needs the derivative.
   - If this step is an input to the computation and its corresponding <code>has_deriv</code> is true
     (an input-derivative was requested), then we need the derivative.
   - If this step is an output of the computation and its corresponding <code>has_deriv</code> is true
     (an output-derivative was requested), then we need the derivative.  (We need somewhere to put it,
     even if it will never be used).
   - If this is an updatable Component node (i.e. for a Component whose \ref Component::Properties() "Properties()"
     returns a number with the kUpdatable flag set) and the <code>need_model_derivative</code> flag of
     the ComputationRequest is true, then we need the derivative.
   .

\subsection dnn3_compile_compiler_step_info Computing the StepInfo

The next line in \ref Compiler::CreateComputation "CreateComputation()", is:
\verbatim
  CreateStepInfo(deriv_needed, &steps, computation);
\endverbatim
This sets up a variety of information associated with each step.  Class Compiler
has a member \ref Compiler::steps_ "steps_", of type <code>std::vector<StepInfo></code>,
which stores all this information:
\verbatim
class Compiler {
   ...
  struct StepInfo {
    int32 node_index;  // network-node index
    bool is_input;  // true if step corresponds to an input to the computation.
    int32 value;  // sub-matrix index of value that this step outputs.
    int32 deriv;  // sub-matrix index of derivative at the output of this step (or zero).
    int32 precomputed_indexes_index;  // ignore; only relevant for non-simple Components
    std::vector<Index> output_indexes;      // Indexes that this step outputs.
    std::vector<int32> output_cindex_ids;   // cindex_ids corresponding to the above.

    // If this component is of type kDescriptor (and note that the top-level
    // Descriptor is a concatenation over >= 1 parts), then we set value_parts
    // to a list of submatrix-indexes, each for the corresponding part of the
    // value.  If there is only one part, it will have one element which will be
    // the same as "value".
    std::vector<int32> value_parts;
    // deriv_parts is as "value_parts", but for parts of the derivative (only
    // set up if deriv != 0.
    std::vector<int32> deriv_parts;

    // for nodes corresponding to descriptors, input_locations_list will contain
    // information about the inputs to this descriptor, telling us for each row
    // of the matrix what other matrix rows it is a summation over.  this is a
    // quantity indexed[part-index][row-index], then a list of pairs (step,
    // row-index), that we store here to avoid computing it twice in forward and
    // backprop.
    std::vector<std::vector<std::vector<std::pair<int32,int32> > > > input_locations_list;
  };
  std::vector<StepInfo> steps_;
  ...
};
\endverbatim
We will discuss some of the members of struct \ref Compiler::StepInfo "StepInfo"o
here.  The quantities <code>node_index</code> and
<code>is_input</code> can be immediately computed from the ComputationGraph and
computation request.  Likewise, <code>output_cindex_ids</code> is just a copy of
the cindex_ids that this step consists of; and <code>output_indexes</code> can
be immediately computed from the <code>output_cindex_ids</code> and the
ComputationGraph.  The members <code>value</code> and <code>deriv</code>
are sub-matrix ids that we need to allocate for this step.

 \subsubsection dnn3_compile_compiler_allocating  Allocating matrices and submatrices (background)

 Now is a good time to discuss matrix and sub-matrix indexes, and how we allocate matrix
 and sub-matrix indexes.  A matrix index is an index into the
 \ref NnetComputer::matrices_ "matrices_" array of class NnetComputer, and also
 into the \ref NnetComputation::matrices "matrices" array of class NnetComputation,
 (where only the size information is stored).  We reserve matrix index zero for
 the empty matrix, or for the NULL matrix (depending on context).  A submatrix
 index is an index \ref NnetComputation::submatrices "submatrices" array of class NnetComputation,
 and represents a particular row and column range of a particular numbered matrix.
 Whenever possible we prefer to use the submatrix index instead of the matrix index
 even if we know that it will correspond to a whole matrix, to avoid possible confusion
 between the two types of index.

 Struct NnetComputation has the following two functions which are used when allocating
 matrices and submatrices:
\verbatim
struct NnetComputation {
  ...
  int32 NewMatrix(int32 num_rows, int32 num_cols);
  int32 NewSubMatrix(int32 base_matrix, int32 dim_offset, int32 dim);
  ...
};
\endverbatim
The \ref NnetComputation::NewMatrix() "NewMatrix()" function allocates a new matrix
and a sub-matrix referring to its entirety, and returns the sub-matrix index; the
\ref NnetComputation::NewSubMatrix() "NewSubMatrix()" function returns
a new sub-matrix corresponding to a column range of an existing matrix.

\subsubsection dnn3_compile_compiler_parts  Allocating matrices and submatrices for StepInfo

All steps except those of type kDimRange have a matrix allocated to store their
value, and if <code>has_deriv[step_index]</code> is true they also have a matrix allocated
to store their derivative.   The code that allocates the value matrix looks like this:
\verbatim
  this_info.value = computation->NewMatrix(num_rows, num_cols);
\endverbatim
(where <code>this_info</code> is of type \ref Compiler::StepInfo "StepInfo").
For steps of type kDimRange, the command that sets up the "value" matrix looks like this:
\verbatim
  this_info.value = computation->NewSubMatrix(steps_[input_step].value,
                                              node.dim_offset, node.dim);
\endverbatim
For steps of type kDescriptor, we also need to set up sub-matrices for the different
"parts" of the value and (if applicable) the derivative.  Recall that a "part"
corresponds to the term in the top-level <code>Append(...)</code> expression in the
Descriptor; if there is no <code>Append(...)</code> then there is just one part.
If there are multiple parts, the command to set up one sub-matrix looks like this:
\verbatim
  this_info.value_parts[p] = computation->NewSubMatrix(this_info.value,
                                                       cur_dim_offset,
                                                       this_dim);
\endverbatim


\subsubsection dnn3_compile_compiler_locations  The input locations list

For each part of a Descriptor, we also call a member-function \ref Compiler::ComputeInputLocationsList "ComputeInputLocationsList()"
of class Compiler:
\verbatim
  ComputeInputLocationsList(step, p,
                            &(this_info.input_locations_list[p]));
\endverbatim
The output of this function, <code>this_info.input_locations_list[p]</code> (<code>p</code>
is the part index), is of type
<code>std::vector<std::vector<std::pair<int32, int32> > ></code>.  It is a vector
that tells us where we get the data from to compute this part of the Descriptor.
It is indexed first by the row-index of the matrix (which is the same as the index
into the Cindexes/cindex_ids for the step), and then is a list of locations, which
we defined above as (step-index, row-index).
Because a Descriptor can only represent an unweighted sum over matrix rows, the
<code>input_locations_list</code> actually contains all the information we need
to generate the forward and backward code for it.  So we won't have to deal directly
with the Descriptor once we compute this quantity.  Inside the code for
\ref Compiler::ComputeInputLocationsList "ComputeInputLocationsList()", you'll see the
following lines:
\verbatim
    std::vector<Cindex> input_cindexes;
    CindexSet cindex_set(graph_);
    bool ans = descriptor.IsComputable(index, cindex_set, &input_cindexes);
    KALDI_ASSERT(ans);
\endverbatim
As you might recall, the \ref Descriptor::IsComputable() "IsComputable()" function
outputs the Cindexes that were actually used in the computation.  It might seem
surprising that we have to call this, instead of just relying on the dependencies
listed in the computation graph.  The reason is that the dependencies are listed for
each Cindex, but we want only the dependencies for one <em>part</em> of a Cindex,
and in the graph they are not broken down in that way.


\subsection dnn3_compile_compiler_input_output_info Computing the input_output_info

The next step in the code of \ref Compiler::CreateComputation() "CreateComputation()" is:
\verbatim
  AddCommands(deriv_needed, computation);
\endverbatim
However, a lot of things happen inside  \ref Compiler::AddCommands() "AddCommands()", so
we'll go through some lines of that function.  It starts off this way:
\verbatim
void Compiler::AddCommands(const std::vector<bool> &deriv_needed,
                           NnetComputation *computation) {
  SetInputOutputInfo(computation);
  ...
\endverbatim
The function \ref Compiler::SetInputOutputInfo "SetInputOutputInfo" is responsible
for setting up the following member of struct NnetComputation:
\verbatim
  unordered_map<int32, std::pair<int32, int32> > input_output_info;
\endverbatim
This contains information about where the inputs and outputs of the network live
(and their corresponding derivatives, if applicable).  It is a map from
node-index to pair (value-matrix-index, derivative-matrix-index).


\subsection dnn3_compile_compiler_allocate  Allocating the matrices

Skipping a couple of minor things, the next function call in
\ref Compiler::AddCommands() "AddCommands()" is:
\verbatim
  AllocateMatrices(computation);
\endverbatim
This function adds commands to the computation, to allocate and zero
all the matrices we declared in the "matrices" member of class Computation
(Except those corresponding to inputs; those will be set up when the user
provides the input).
The commands will be of type kAllocateMatrixZeroed, with one argument
corresponding to the matrix index.  Later, in the optimization phase, we will
replace some of these commands with kAllocateMatrixUndefined, if we determine
that zeroing the newly allocated matrix was not necessary.


\subsection dnn3_compile_compiler_forward  The forward computation

The next stage of \ref Compiler::AddCommands() "AddCommands()" is the following:
\verbatim
  int32 num_steps = steps_.size();
  for (int32 step = 0; step < num_steps; step++)
    DoForwardComputation(step, computation);
\endverbatim
\ref Compiler::DoForwardComputation() "DoForwardComputation()" adds the commands
for the forward part of the computation.  The code for this function,
with a couple of checks removed, is below:
\verbatim
void Compiler::DoForwardComputation(int32 step,
                                    NnetComputation *computation) const {
  const StepInfo &step_info = steps_[step];
  const NetworkNode &node = nnet_.GetNode(step_info.node_index);
  switch (node.node_type) {
    case kInput: case kDimRange: break;  // Nothing to do.
    case kComponent:
      AddPropagateStep(step, computation);
      break;
    case kDescriptor:
      DoForwardComputationDescriptor(step, computation);
      break;
  }
}
\endverbatim

\subsubsection dnn3_compile_compiler_forward_component  Forward computation for Components

If the step is of type kComponent, setting up the forward computation is quite simple.
The function \ref Compiler::AddPropagateStep() "AddPropagateStep()" adds a single command
of type kPropagate, of which the key part is this:
\verbatim
  NnetComputation::Command c(NnetComputation::kPropagate,
                             node.u.component_index,
                             step_info.precomputed_indexes_index,
                             input_submatrix_index,
                             output_submatrix_index);
  computation->commands.push_back(c);
\endverbatim
This function is also responsible for adding the command to store the
per-component stats (i.e. to call the function Component::StoreStats()), if
this is requested.  The purpose of these stats is to detect nonlinearities
that are oversaturated.  The code is:
\verbatim
  if (request_.store_component_stats) {
    const Component *c = nnet_.GetComponent(node.u.component_index);
    if (c->Properties() & kStoresStats) {
      NnetComputation::Command c(NnetComputation::kStoreStats,
                                 node.u.component_index,
                                 output_submatrix_index);
      computation->commands.push_back(c);
    }
  }
\endverbatim

\subsubsection dnn3_compile_compiler_forward_descriptor  Forward computation for Descriptors (top-level)

Setting up the forward computation for Descriptors is a little more complicated.
The function call <code>DoForwardComputationDescriptor(step, computation)</code>
calls the following code:
\verbatim
void Compiler::DoForwardComputationDescriptor(
    int32 step, NnetComputation *computation) const {
  int32 num_parts = steps_[step].value_parts.size();
  for (int32 part = 0; part < num_parts; part++)
    DoForwardComputationSumDescriptor(step, part, computation);
}
\endverbatim
\ref Compiler::DoForwardComputationSumDescriptor() "DoForwardComputationSumDescriptor()"
is defined as follows:
\verbatim
void Compiler::DoForwardComputationSumDescriptor(
    int32 step, int32 part_index, NnetComputation *computation) const {
  const StepInfo &step_info = steps_[step];
  std::vector<std::vector<std::pair<int32, int32> > > submat_locations_list;
  ComputeValueSubmatLocationsList(step_info.input_locations_list[part_index],
                                  &submat_locations_list);
  int32 value_submatrix_index = step_info.value_parts[part_index];
  DoForwardComputationFromSubmatLocationsList(
      value_submatrix_index,
      submat_locations_list,
      computation);
}
\endverbatim
The call to \ref Compiler::ComputeValueSubmatLocationsList()
"ComputeValueSubmatLocationsList()" turns the previously discussed
input_locations_list in the standard location format with pairs
(step-index, row-index) into
submat-location format with pairs (submatrix-index, row-index).
Stepping into \ref Compiler::DoForwardComputationFromSubmatLocationsList()
"DoForwardComputationFromSubmatLocationsList()", we see the following code:
\verbatim
void Compiler::DoForwardComputationFromSubmatLocationsList(
    int32 value_submatrix_index,
    const std::vector<std::vector<std::pair<int32, int32> > > &submat_lists,
    NnetComputation *computation) const {
  std::vector<std::vector<std::pair<int32, int32> > > split_lists;
  SplitLocations(submat_lists, &split_lists);
  for (int32 i = 0; i < split_lists.size(); i++)
    DoForwardComputationFromSubmatLocations(
        value_submatrix_index, (i == 0),
        split_lists[i],
        computation);
}
\endverbatim

\subsubsection dnn3_compile_compiler_split_locations  Forward computation for Descriptors (SplitLocations)

The function SplitLocations() is important.  Its input and output is of the same
type (<code>std::vector<std::pair<int32, int32> ></code>, but it performs a change
of format.  The input <code>submat_lists</code> is indexed by matrix-row and is then a list
of input locations to be summed over.  SplitLocations() pads all
those lists with (-1, -1) so they are all the same length and then turns the
vector of lists into a list of vectors (<code>split_lists</code>).  For example, if we had a matrix with 1000
rows and the input submat_lists were all of length not exceeding 2, the SplitLocations()
would output a vector of length 2, each element being a vector of length 1000; and there
would be (-1, -1) pairs in one or both of those output lists, if not all of the
input vectors had size exactly 2.

In fact, SplitLocations() tries to be a bit clever about how it splits things up, to
try to ensure that inputs from the same submatrix are allocated as much as possible
to the same vector in the output.  This will enable us to use slightly more efficient
commands in the compiled computation.  SplitLocations() may end up outputting
a slightly larger number of vectors in order to achieve this.

\subsubsection dnn3_compile_compiler_forward_submat  Forward computation with DoForwardComputationFromSubmatLocations

After splitting up the submat-location lists using SplitLocations(), we give each
vector in the resulting list
to \ref Compiler::DoForwardComputationFromSubmatLocations() "DoForwardComputationFromSubmatLocations()".
The main input to this function is a vector of submat-locations, i.e. a vector
of pairs (submatrix-index, row-index), where the length of the vector corresponds to the
number of matrix rows (or equivalently, the number of cindex_ids in the step).
This function works out the appropriate command to use in the forward propagation,
trying to figure out which one will be the most efficient.  The code for this
function is quite simple so we show it:
\verbatim
void Compiler::DoForwardComputationFromSubmatLocations(
    int32 value_submatrix_index,
    bool is_first_term_in_sum,
    const std::vector<std::pair<int32, int32> > &submat_locations,
    NnetComputation *computation) const {

  int32 input_submatrix_index = -1;
  std::vector<int32> indexes;

  if (ConvertToIndexes(submat_locations, &input_submatrix_index, &indexes)) {
    DoForwardComputationFromIndexes(value_submatrix_index,
                                    input_submatrix_index,
                                    is_first_term_in_sum,
                                    indexes,
                                    computation);
    return;
  } else {
    // There are multiple source matrices.
    NnetComputation::CommandType ctype =
        (is_first_term_in_sum ?
         NnetComputation::kCopyRowsMulti : NnetComputation::kAddRowsMulti);
    int32 indexes_multi_index = computation->indexes_multi.size();
    computation->indexes_multi.push_back(submat_locations);
    computation->commands.push_back(
        NnetComputation::Command(ctype, value_submatrix_index,
                                 indexes_multi_index));
    return;
  }
}
\endverbatim
The function ConvertToIndexes() is detecting for us the case where all inputs
come from the same submatrix, and if so, converts the submat-locations vector to
a single submatrix index a vector of row indexes, which will contain -1's corresponding
to any (-1, -1) values in the input submat_locations.  In this case we
call \ref Compiler::DoForwardComputationFromIndexes() "DoForwardComputationFromIndexes()",
which if possible creates a command for a simple matrix copy or add (commands kMatrixCopy
and kMatrixAdd), and otherwise into a command of type kCopyRows or kAddRows, which will
call the functions \ref CuMatrix::CopyRows() "CopyRows()" \ref CuMatrix::AddRows() "AddRows()"
of class CuMatrix.

If there were multiple source sub-matrices, then we generate a command of type
kCopyRowsMulti or kAddRowsMulti, calling the functions
\ref CuMatrix::CopyRowsMulti() "CopyRowsMulti()" \ref CuMatrix::AddRowsMulti() "AddRowsMulti()"
of class CuMatrix.  These functions take pointer arguments, pointing to the row-address
of the source data for each row of the destination matrix.  We prefer not to call those
functions, because to use them we transfer the addresses to the GPU card for each minibatch
(we reallocate the matrices each time, so the addresses might change).  This is a minor
issue, though.

\subsubsection dnn3_compile_compiler_forward_end Marking the end of the forward computation

After we are finished setting up the commands for the forward computation, we mark
that it's over.  This is done as follows:
\verbatim
  computation->commands.push_back(
      NnetComputation::Command(NnetComputation::kNoOperationMarker));
\endverbatim
The execution code will later detect this marker to know when the forward part
of the computation ends and the backward part begins.

\subsection dnn3_compile_compiler_backward   The backward computation

The backward computation is created in the following statements
from \ref Compiler::AddCommands() "AddCommands()":
\verbatim
  for (int32 step = num_steps - 1; step >= 0; step--)
    if (deriv_needed[step])
      DoBackwardComputation(step, computation);
\endverbatim
The code for \ref Compiler::DoBackwardComputation() "DoBackwardComputation()" mostly mirrors
that of "DoForwardComputation()", so we won't go into it in detail.  However, we
would like to point out that
\ref Compiler::DoBackwardComputationFromSubmatLocationsList() "DoBackwardComputationSubmatLocationsList()"
differs from
\ref Compiler::DoForwardComputationSubmatLocationsList() "DoForwardComputationSubmatLocationsList()"
in that it calls the function \ref SplitLocationsBackward()
instead of SplitLocations().  The issue is that when splitting the submatrix-locations, we need to
be a little more careful to ensure we generate valid commands.  In the forward computation,
if multiple locations of the matrix are copied (or added-to) from the same input location, it
is not a problem.  However, in the backward computation, this would be a problem because it
could lead to different CUDA kernels attempting to update the same location at the same time.
While there are solutions to this synchronization problem, they have a cost and we prefer
to avoid the issue.

Our solution is essentially as follows, and see the documentation of SplitLocationsBackward() for
more details.  We first split the locations into separate vectors as for SplitLocations().  Then
we split further as needed in order to ensure that either one of the two following properties
holds: that for each vector, either:
   - All pairs (submatrix-index, row-index) in the vector are unique, except possibly
     the special pair (-1, -1) may be repeated
   - The .first values (submatrix-index) in the list are all the same, and the .second
     have a special property (see the function HasContiguousProperty()) that allows
     us to call CuMatrix::AddRowRanges().  The property is that each unique
     row-index must appear only in a single contiguous run.
   .


\subsection dnn3_compile_compiler_deallocating the matrices  Deallocating the matrices

The last command of \ref Compiler::AddCommands() "AddCommands()" adds commands to
deallocate the matrices:
\verbatim
  DeallocateMatrices(computation);
\endverbatim
We add commands (kDeallocMatrix) to deallocate each of the matrices in the computation,
except those that are outputs of the computation (including requested derivatives
at the inputs).

\subsection dnn3_compile_compiler_debug  Adding debug information

\ref Compiler::AddCommands() "AddCommands()" terminates, the last command remaining
in the function \ref Compiler::CreateComputation() "CreateComputation()" is to
output the debug information, if requested:
\verbatim
  if (opts.output_debug_info)
    OutputDebugInfo(computation);
\endverbatim
This information is intended mostly for diagnostics and to help
users interpret the meaning of matrices in a compiler computation, and consists of the following:
\verbatim
  struct MatrixDebugInfo {
    bool is_deriv;  // true if this represents a derivative, not a value.
    int32 node_index;  // network-node index.
    std::vector<Index> indexes;
    MatrixDebugInfo(): is_deriv(false), node_index(-1) {}
  };
\endverbatim
We won't go into further detail on this, since it's quite obvious what this function
would do.  We note that in the optimization phase, we sometimes merge matrices together
as an optimization.  In this case the associated \ref NnetComputation::debug_info "debug_info"
will correspond to the debug information of one of the matrices that we merged.


\subsection dnn3_compile_compiler_shortcut Shortcut compilation

A feature available from Kaldi version 5.1 is 'shortcut' compilation (enabled
by default).  This is done only when the ComputationRequest has a suitably
regular structure; this basically means that there are more than two different
"n" indexes in the computation, they are numbered consecutively from zero,
nd for each "n" index, the requested set of "t" and "x" indexes is the same
and in a regular order.  What the shortcut compilation does is reduce the
computation request down to just two distinct "n" indexes (zero and one),
compile the mini-request, and then expand the resulting compilation-- basically,
it extrapolates the compiled computation to what it would have been if
the entire original computation request had been supplied.  Shortcut
compilation significantly cuts down compilation time.


 - Up: \ref dnn3
 - Previous: \ref dnn3_code_data_types
 - Next: \ref dnn3_code_optimization

*/

}
}