论文标题
用于矩阵乘法的恒定深度和亚立方体大小的阈值电路
Constant-Depth and Subcubic-Size Threshold Circuits for Matrix Multiplication
论文作者
论文摘要
McCulloch-Pitts阈值门的布尔电路是20世纪后期对神经计算的经典模型，作为一般计算的模型。大规模神经计算硬件的最新进展使他们的实际实施成为了近期的可能性。我们描述了一种将两个$ n $乘以$ n $矩阵的理论方法，该方法将阈值门逻辑与常规快速矩阵乘法算法集成在一起，该算法可以执行$ o（n^ω）$ arithmetic操作，用于正常数$ω<3 $。我们的方法将这样的快速矩阵乘法算法转换为大约$ o（n^ω）$门的恒定深度阈值电路。在我们工作之前，尚不知道$θ（n^3）$ - 矩阵乘法的门屏障是否可以通过恒定深度阈值电路来克服。 密集矩阵乘法是卷积神经网络训练中的核心操作。在神经体系结构上执行这项工作，而不是将其卸载到GPU上可能是一个吸引人的选择。
Boolean circuits of McCulloch-Pitts threshold gates are a classic model of neural computation studied heavily in the late 20th century as a model of general computation. Recent advances in large-scale neural computing hardware has made their practical implementation a near-term possibility. We describe a theoretical approach for multiplying two $N$ by $N$ matrices that integrates threshold gate logic with conventional fast matrix multiplication algorithms, that perform $O(N^ω)$ arithmetic operations for a positive constant $ω< 3$. Our approach converts such a fast matrix multiplication algorithm into a constant-depth threshold circuit with approximately $O(N^ω)$ gates. Prior to our work, it was not known whether the $Θ(N^3)$-gate barrier for matrix multiplication was surmountable by constant-depth threshold circuits. Dense matrix multiplication is a core operation in convolutional neural network training. Performing this work on a neural architecture instead of off-loading it to a GPU may be an appealing option.
