Optimal DNN Primitive Selection with Partitioned Boolean Quadratic Programming
This addresses the computational inefficiency in DNN deployment for practitioners in embedded and general-purpose computing, offering a principled optimization method that is incremental over existing vendor solutions.
The paper tackles the problem of selecting optimal deep neural network primitives and data layouts to improve computational efficiency, showing that it is NP-hard and proposing an analytic solution via a partitioned Boolean quadratic programming solver, which achieves significant gains over state-of-the-art vendor libraries on embedded and general-purpose platforms.
Deep Neural Networks (DNNs) require very large amounts of computation both for training and for inference when deployed in the field. Many different algorithms have been proposed to implement the most computationally expensive layers of DNNs. Further, each of these algorithms has a large number of variants, which offer different trade-offs of parallelism, data locality, memory footprint, and execution time. In addition, specific algorithms operate much more efficiently on specialized data layouts and formats. We state the problem of optimal primitive selection in the presence of data format transformations, and show that it is NP-hard by demonstrating an embedding in the Partitioned Boolean Quadratic Assignment problem (PBQP). We propose an analytic solution via a PBQP solver, and evaluate our approach experimentally by optimizing several popular DNNs using a library of more than 70 DNN primitives, on an embedded platform and a general purpose platform. We show experimentally that significant gains are possible versus the state of the art vendor libraries by using a principled analytic solution to the problem of layout selection in the presence of data format transformations.