  Parallelizing Gated Recurrent Unit (GRU) networks is a challenging task, as
the training procedure of GRU is inherently sequential. Prior efforts to
parallelize GRU have largely focused on conventional parallelization strategies
such as data-parallel and model-parallel training algorithms. However, when the
given sequences are very long, existing approaches are still inevitably
performance limited in terms of training time. In this paper, we present a
novel parallel training scheme (called parallel-in-time) for GRU based on a
multigrid reduction in time (MGRIT) solver. MGRIT partitions a sequence into
multiple shorter sub-sequences and trains the sub-sequences on different
processors in parallel. The key to achieving speedup is a hierarchical
correction of the hidden state to accelerate end-to-end communication in both
the forward and backward propagation phases of gradient descent. Experimental
results on the HMDB51 dataset, where each video is an image sequence,
demonstrate that the new parallel training scheme achieves up to 6.5$\times$
speedup over a serial approach. As efficiency of our new parallelization
strategy is associated with the sequence length, our parallel GRU algorithm
achieves significant performance improvement as the sequence length increases.
