SystemML大规模机器学习，优化算子融合方案的研究

SystemML大规模机器学习，优化算子融合方案的研究
摘要
许多大规模机器学习（ML）系统允许通过线性代数程序指定定制的ML算法，然后自动生成有效的执行计划。在这种情况下，优化的机会融合基本算子的熔合链的算子是无处不在的。这些机会包括
（1）更少的物化中间表示
（2）更少的输入数据扫描，以及
（3）利用算子链上的稀疏性。
自动算子融合消除了手写的需要
融合运算符并显著提高
复杂的或以前看不见的算子链。然而，现有的融合启发式算法，很难找到好的融合方法。
复杂DAG计划或局部分布式算子的混合计划。
本文提出了一种融合方案的系统推理优化框架
综合了DAGs中的物化点、稀疏性利用、不同的融合模板类型，局部性
和分布式算子。提出了
（1）有效融合方案的候选探索算法
（2）基于成本的候选选择，以及
（3）在密集、稀疏和压缩数据上生成本地和分布式算子的代码。
在SystemML中的实验表明，通过优化融合方案，端到端性能得到了改善
与手写熔合运算符相比，高达21倍，可忽略的优化和代码生成开销。
1．引论
大规模机器学习（ML）的目的，是从大量的数据收集和通常的数据中，建立依赖于数据并行框架的预测模型，如MapReduce。
Spark在商品硬件上实现了经济高效的并行化。大规模的ML应用范围从数据密集型的、传统的分类、回归和集群用例，到计算密集型的矩阵分解和聚类的深度学习架构。在这种情况下，最先进的ML系统，允许数据科学家用线性代数和统计函数，来表达他们的ML算法，并自动高效地编译执行计划。这个高级规范简化了开发定制的ML算法，并允许执行计划适应不同的部署以及不同的数据、硬件和集群特征。

融合机会：执行产生计划有很多机会，其中融合算子-基本算子链的复合算子项-
可以提高性能。图1显示了融合潜在的主要类别。
首先，融合可以消除物化的中间表示

算子融合的现有工作：考虑到无处不在的机会和高性能影响，在数据库和高性能计算文献中，算子融合和代码生成受到了广泛的关注。
例如，SystemML使用手工编码的融合算子，为了消除中间表示，不必要的扫描，以及利用算子间的稀疏性。同样，Cumulon和常见问题，分别通过屏蔽算子和半连接减少（最坏情况下的最佳连接）。然而，这样的方法需要定制的算子，通常仅限于少数算子的固定模式，并且对于密集算子和稀疏输入。自动算子融合解决了这些问题：访问模式感知融合和后续代码的问题生成。
现有的研究大多忽略了稀疏和压缩。除了BTO中的节点局部优化或微优化（如Tupleware中的预测和循环平铺一样，不要考虑算子融合计划的优化。
一个优化融合计划的案例：随着代码生成器变得越来越复杂（例如，通过覆盖更多操作），优化融合计划的原则性方法变得越来越成问题。在这方面，关键的挑战是算子重叠访问模式，以及稀疏性开发的目标，创建需要自动优化的搜索空间：
• Materialization points (e.g., for multiple consumers)
• Sparsity exploitation and ordering of sparse inputs
• Decisions on fusion patterns (e.g., template types), and
• Constraints (e.g., memory budget and blocksizes) and costs for local and/or distributed operations.
例如，关于物化点的决策，考虑了冗余计算与物化和需求，比较指数级的计划。基本解决方案是启发式的，例如fuse all或fuse no redundancy，这些启发式算法很难为复杂的问题找到好本地和分布式操作的DAG或混合计划的解决方案。
贡献：拨我介绍了一种基于cost-based，基于DAGs的算子融合方案优化框架，对线性代数运算进行了描述，并将其集成到SystemML。用下列公式来描述优化问题。
分为三个阶段候选探索，候选选择，以及代码生成。
设计了新颖高效的算法。详细技术贡献如下
从论文的结构来看：
• System Architecture: We describe the integration into SystemML in Section 2. This overview includes the compiler integration, our optimization framework, code generation plans, and their runtime integration.
• Candidate Exploration: In Section 3, we introduce a novel bottom-up algorithm for the efficient exploration of valid partial fusion plans. We also discuss our memoization data structure and basic pruning rules.
• Candidate Selection: In Section 4, we then present strategies for selecting the optimal candidate plans. We formulate the problem, describe heuristics, and introduce our novel cost-based plan selection, including its search space, cost model, and enumeration algorithm.
• Experiments: In Section 5, we then report on extensive experiments in SystemML. These cover micro benchmarks for code generation, end-to-end performance in local and distributed environments, as well as comparisons with Julia,