Transformer computations in parallel and hierarchical machines

Transformers are the dominant architecture in modern AI. Their expressiveness derives from the attention module, which, however, has quadratic complexity. This complexity poses a challenge for achieving efficient computation of the transformer when training and doing inference. This thesis analyzes transformer inference computation on parallel and hierarchical machines under the assumption that the communication speed is finite, both between two processors and between a processor and its local memory. We design and analyze algorithms for transformer inference, in particular the self-attention can be computed in O(n) time on a n × d mesh with constant memory per node, which is optimal with respect to the work bound. Then we generalize this computation on a n/b × d/b mesh; in this case, there is a gap between the upper and lower bounds. In addition, we develop a general framework for divide-and-conquer recurrences in HMM. This framework considers memory access costs for arbitrary cost functions. We apply this framework to the standard matrix multiplication to confirm the asymptotic bounds when the cost functions are the threshold function, which can be associated with I/O complexity, and the polynomial cost functions, that represent a more realistic scenario.