Practical Performance Guarantees for Pipelined DNN Inference

arXiv:2311.03703v2 Announce Type: replace
Abstract: We optimize pipeline parallelism for deep neural network (DNN) inference by partitioning model graphs into $k$ stages and minimizing the running time of the bottleneck stage, including communication. We give practical and effective algorithms for this NP-hard problem, but our emphasis is on tackling the practitioner's dilemma of deciding when a solution is good enough. To this end, we design novel mixed-integer programming (MIP) relaxations for proving lower bounds. Applying these methods to a diverse …

abstract algorithms arxiv communication cs.dc cs.lg deep neural network dnn graphs inference network neural network np-hard partitioning performance pipeline practical running stage type