[onert] Introduce use-def chains into TrainableGraph

[ragmani]

What

Let's introduce use-def chains and new index types for training into TrainableGraph and apply it for memory optimization.

Why

There was no use-def chains that could directly know dependencies between operations and operands in a TrainableGraph. So we were not even verifying whether TrainableGraph is a dag graph, and we were also unable to optimize memory for training.

Ways to support new index types for training

New types : TrainingOperationIndex, TrainingOperandIndex

1. A way of distinguishing whether an operand or an operation is in forwarding and backwarding by using an existing index number and the information on whether it is in forwarding or in backwarding within the new index types.

• An example

template <typename Index> class TrainingIndex
class TrainingIndex
{
...
private:
  Index _index;
  bool _is_forward;
}

using TrainingOperationIndex = TrainingIndex<OperationIndex>;
using TrainingOperandIndex = TrainingIndex<OperandIndex>;

2. A way of distinguishing whether an operand or an operation is in forwarding and backwarding only by using an new index number within the new index types.

• An example

using TrainingOperationIndex = ::onert::util::Index<uint32_t, TrainingOperationIndexTag>;
using TrainingOperandIndex = ::onert::util::Index<uint32_t, TrainingOperandIndexTag>;

I'm trying with the first way.

• Training Index
  • [onert] Introduce index types for training #13318
• Use-Def Chain
  • [onert] Introduce UseDefChain #13338
  • [onert] Add use-def chains to TrainableGraph #13353
  • [onert] Add disabling backward to TrainableGraph #13372
  • [onert] Add missing definition in TrainableGraph #13373
  • [onert] Introduce UseDefGenerator #13374
  • [onert] Add a comment about multiple defs #13429
  • [onert] Add generating training usedefs for BinaryArithmetic op #13452
  • [onert] Add generating training usedefs for Conv2D op #13453
  • [onert] Add generating training usedefs for DepthwiseConv2D op #13454
  • [onert] Add generating training usedefs for ElementwiseActivation op #13455
  • [onert] Add generating training usedefs for FullyConnected op #13456
  • [onert] Add generating training usedefs for Pad op #13457
  • [onert] Add generating training usedefs for Pool2D op #13458
  • [onert] Add generating training usedefs for Reduce op #13459
  • [onert] Add generating training usedefs for Reshape op #13460
  • [onert] Add generating training usedefs for Softmax op #13461
  • [onert] Apply usedef chains for training #13462
  • [onert] Add unit tests for UseDefGenerator #13547
• Backwarding Order
  • [onert] Add essentialBackwardOrder to TrainableGraph #13352
  • [onert] Replace btopolSortOperations with essentialBackwardOrder #13375
• Memory optimization
  • [onert] Introduce GradientMemoryManager #13379
  • [onert] Extract planning tensors #13428
  • [onert/training] Store disposable tensor indices in TensorBuilder #13432
  • [onert/training] Introduce TensorPlanner #13433
  • [onert] Plan non-const tensors on train backend #13470
  • [onert] Plan trainable tensors on train backend #13471
  • [onert] Add notifyBackwardLastUse() to TensorBuilder #13476
  • [onert] Plan back-propagated tensors on train backend #13522
  • [onert] Plan gradient tensors on train backend #13523
  • [onert] Plan disposable tensors on train backend #13552
  • [onert] Implement notifyLastUse in training TensorBuilder #13553
  • [onert] Generate BackPropAccumulator only if necessary #13570
  • [onert] Revise generating tensors for training #13571
  • [onert] Use default cpu planner for training #13600
  • [onert] Fix wrong allocation of optimizer variables #13601
• Etc
  • [onert] Fix wrong applied shape in backward of MeanLayer #13351
  • [onert] Add missing allocation in train BinaryArithmeticLayer #13376
  • [onert] Add some more branching model tests for training #13377
  • [onert] Move assertion in loss layers #13378

Draft : #13305

[ragmani]

I'm closing this issue because memory usage for training reduces as #13282 (comment) on master branch(08cfdf5) now.

There are still parts that can be further optimized for memory.
For example,

• Unifying planning of tensors for gradient, disposable, and extra.
• Unifying planning of tensors for non-const and back-prop.

However, I won't proceed them unless there is any request since their effects are not expected to reduce memory usage dramatically.