high performance computing on graphics processing units: hgpu.org

Shift Reduce Parsing is a common algorithm used in compilers and natural language processing, and can be used to compose a sequence of fixed-length vectors into a single vector of equal length. Previous versions are implemented using predetermined computational graphs that trade excessive memory and computation to minimize transfers of memory from the device to the host. In this paper, I present a version of Shift Reduce Parsing that uses only the necessary memory and computation, show that the memory transfer is insignificant when implemented properly, and analyze how the sequence of transitions can effect computation when running a batched version of this algorithm, as is common in deep learning programs.