论文标题
关于简化依赖性多面体还原
On Simplifying Dependent Polyhedral Reductions
论文作者
论文摘要
\ emph {降低}将输入值的集合与关联（通常也是交换性）运算符共同生成单个输出或集合。它们在计算中无处不在，尤其是大数据和深度学习。当\ emph {same}输入值有助于多个输出值，就有很大的机会来减少（双关语意图）计算工作。这称为\ emph {简化}。 \ emph {多面体还原}是降低，其中输入和输出数据收集是（密集）多维阵列（即\ emph {tensors}），并使用工具的线性/仿率函数访问。 ％\ emph {广义张量收缩} gautam和rajopadhye \ cite {sanjay-popl06}展示了如何自动简化多面体降低（通过编译时间分析）和最佳（所得的程序具有最小的渐近复杂性）。 Yang，Atkinson和Carbin \ cite {yang2020simplifying}将其扩展到（某些）输入值取决于（某些）输出的情况。具体而言，他们展示了如何将最佳简化问题作为双线性编程问题提出，并且对于减少操作员承认逆的情况，他们给出了保留最佳性的启发式解决方案。 在本说明中，我们表明，可以简化依赖减少的简化，以作为Gautam-rajopadhye回溯搜索算法的简单扩展。
\emph{Reductions} combine collections of input values with an associative (and usually also commutative) operator to produce either a single, or a collection of outputs. They are ubiquitous in computing, especially with big data and deep learning. When the \emph{same} input value contributes to multiple output values, there is a tremendous opportunity for reducing (pun intended) the computational effort. This is called \emph{simplification}. \emph{Polyhedral reductions} are reductions where the input and output data collections are (dense) multidimensional arrays (i.e., \emph{tensors}), accessed with linear/affine functions of the indices. % \emph{generalized tensor contractions} Gautam and Rajopadhye \cite{sanjay-popl06} showed how polyhedral reductions could be simplified automatically (through compile time analysis) and optimally (the resulting program had minimum asymptotic complexity). Yang, Atkinson and Carbin \cite{yang2020simplifying} extended this to the case when (some) input values depend on (some) outputs. Specifically, they showed how the optimal simplification problem could be formulated as a bilinear programming problem, and for the case when the reduction operator admits an inverse, they gave a heuristic solution that retained optimality. In this note, we show that simplification of dependent reductions can be formulated as a simple extension of the Gautam-Rajopadhye backtracking search algorithm.
