  Batching has a fundamental influence on the efficiency of deep neural network
(DNN) execution. However, for dynamic DNNs, efficient batching is particularly
challenging as the dataflow graph varies per input instance. As a result,
state-of-the-art frameworks use heuristics that result in suboptimal batching
decisions. Further, batching puts strict restrictions on memory adjacency and
can lead to high data movement costs. In this paper, we provide an approach for
batching dynamic DNNs based on finite state machines, which enables the
automatic discovery of batching policies specialized for each DNN via
reinforcement learning. Moreover, we find that memory planning that is aware of
the batching policy can save significant data movement overheads, which is
automated by a PQ tree-based algorithm we introduce. Experimental results show
that our framework speeds up state-of-the-art frameworks by on average 1.15x,
1.39x, and 2.45x for chain-based, tree-based, and lattice-based DNNs across CPU
and GPU.
