本文由“大数据治理的理论与技术”专题特约编辑杜小勇教授、杨晓春教授和童咏昕教授推荐.
在大数据治理应用中, 数据分析是必不可少的一环, 且具有耗时长、计算资源需求大的特点, 因此, 优化其执行效率至关重要. 早期由于数据规模不大, 数据分析师可以利用传统的矩阵计算工具执行分析算法, 然而随着数据量的爆炸式增长, 诸如MATLAB等传统工具已无法满足应用需求的执行效率, 进而涌现出了一批面向大数据分析的分布式矩阵计算系统. 从技术、系统等角度综述了分布式矩阵计算系统的研究进展. 首先, 从发展成熟的数据管理领域的视角出发, 剖析分布式矩阵计算系统在编程接口、编译优化、执行引擎、数据存储这4个层面面临的挑战; 其次, 分别就这4个层面展开, 探讨、总结相关技术; 最后, 总体分析了典型的分布式矩阵计算系统, 并展望了未来研究的发展方向.
As an essential part of big data governance applications, data analysis is characterized by time-consuming and large hardware requirements, making it essential to optimize its execution efficiency. Earlier, data analysts could execute analysis algorithms using traditional matrix computation tools. However, with the explosive growth of data volume, the traditional tools can no longer meet the performance requirements of applications. Hence, distributed matrix computation systems for big data analysis have emerged. This study reviews the progress of distributed matrix computation systems from technical and system perspectives. First, this study analyzes the challenges faced by distributed matrix computation systems in four dimensions: programming interface, compilation optimization, execution engine, and data storage, from the perspective of the mature data management field. Second, this study discusses and summarizes the technologies in each of these four dimensions. Finally, the study investigates the future research and development directions of distributed matrix computation systems.
矩阵计算作为解决数据分析领域问题的有力工具, 具有悠久的发展历史. 最初, 矩阵的出现是用于求解方程组, 其概念最早可追溯到中国汉代时期的《九章算术》, 其中提到了使用数组来表达、求解线性代数方程组, 即类似于线性代数中矩阵求解的思路. 而“矩阵”这一正式专业术语, 最早则是由James Joseph Sylvester在1850年提出[
在20世纪末, 矩阵计算已成为数据分析算法中必不可少的一部分. 在诸多企业与科学研究领域, 数据分析师需要为他们的数据自行设计分析算法. 这些算法通常可以通过线性代数符号表示出来, 其中, 数据就成为矩阵, 而数据分析操作就由矩阵计算所组成. 如
矩阵计算解决方案
随着21世纪互联网行业的兴起, 数据的规模和潜在的价值均呈现出爆炸式增长. 为了充分管理、利用大数据, 经济决策、生物医药、图像处理、信息推送等诸多技术领域的大数据分析算法发展迅速, 相关大数据治理应用也逐渐渗透进了社会的方方面面. 由于这些应用需要管理、分析海量数据, 因此往往需要长时间的运行. 其中, 矩阵计算作为数据分析的基础工具, 其效率就成为关键问题[
现如今, 在大数据上支持统计和机器学习算法已成为现代矩阵计算系统的主流要求[
● 第1类系统(如TensorFlow[
● 第2类系统(如MADlib[
两类系统所考虑的上层应用和底层的计算框架均有显著的区别, 因此, 本文仅调研其中第2类分布式矩阵计算系统. 这类系统的出现, 让用户不再需要手动处理分布式数据的分配与通信. 通常, 它们会提供一种基于线性代数的语言或嵌入Python, Scala或SQL的接口, 用户通过简单的线性代数符号, 即可操作集群磁盘或内存中的大规模数据. 目前, 分布式矩阵计算系统相关研究技术已日趋成熟, 系统数量众多. 而现有矩阵计算相关综述中更关注于算法而非系统本身[
本文第1节将从数据管理系统的视角分析分布式矩阵计算系统面对的挑战及对应的相关技术. 第2节−第5节分别从编程接口、编译优化、执行引擎、数据存储介绍相关技术. 第6节探讨未来值得关注的研究方向. 第7节总结全文.
矩阵计算是一种特殊的数据处理任务, 本文将从数据管理系统的视角来剖析分布式矩阵计算系统. 本节首先从一个矩阵计算应用出发, 介绍分布式矩阵计算系统的相关技术分类.
矩阵计算应用的例子
(1) 系统通过词法、语法分析将用户脚本编译为便于系统处理的数据结构, 例如语法树, 并基于此生成执行计划.
(2) 为了避免数据分析的时间过长, 系统需要对执行计划进行优化, 例如调整计划中算子的执行顺序.
(3) 由执行引擎具体实施优化后的执行计划.
(4) 在执行引擎实施执行计划的过程中需要不断地访问、组织矩阵数据, 包括用户提供的数据以及脚本中新生成的中间数据.
由此可见, 从数据管理的角度来看, 分布式矩阵计算系统包括编程接口、编译优化、执行引擎、数据存储这4个层面.
值得注意的是, 这4个层面是紧密相关的: 编程接口作为编译优化的上层输入, 其抽象程度决定了优化规则的复杂程度; 编译优化中的决策判断则依赖于底层执行引擎的运行开销和数据存储的方式. 为了能够清晰地梳理、比较, 本文按照系统执行用户脚本的执行流程, 将编程接口、编译优化、执行引擎、数据存储这4个层面的相关技术独立出来, 分别介绍它们所面临的挑战和解决方案.
本节从编程接口、编译优化、执行引擎、数据存储这4个层面分析了分布式矩阵计算系统所面临的挑战.
● 在编程接口层面, 如何权衡编程难度以及表达能力.
影响一套编程接口是否好用的关键因素在于编程难度以及表达能力. 一方面, 编程接口越接近于线性代数表达式, 就意味着编程难度越小, 即用户的开发成本越低. 一个直观的、编程难度低的例子是, 用户可直接向系统提供单机的R语言脚本, 而无须考虑该脚本中的运算逻辑如何扩展到分布式环境下执行. 但是在追求编程难度低的同时, 高度抽象的编程接口会导致用户无法根据一些经验知识对脚本中部分地方的执行进行调整、设置, 也就更依赖系统本身在编译过程中的判断才能保障最终的执行效率. 另一方面, 编程接口要足够灵活, 让用户能够表达自己所需要的计算逻辑或数据组织方式, 但是这往往又会导致编程接口暴露过多关于分布式计算的细节, 用户需要自行了解分布式矩阵计算系统的相关原理, 加大了用户使用的门槛. 由此可见, 分布式矩阵系统的编程接口需要在编程难度以及表达能力这两者之间进行权衡.
● 在编译优化层面, 如何生成最优的执行计划.
编译优化技术对于提升系统性能至关重要. 尤其是在数据分析领域, 算法中往往包含复杂的运算逻辑, 用户难以在编写脚本程序时就采用最佳的执行顺序或方案. 因此, 直接根据该脚本生成的执行计划通常是次优的, 甚至会由于存储空间不足等问题导致系统崩溃. 此时, 系统就依赖于编译优化来解决执行效率问题. 然而, 不同于传统数据库中的查询优化, 复杂的线性代数算法导致生成的执行计划中算子数量多、类型多, 且计划的结构复杂. 因此, 执行计划的潜在优化空间更大, 相关技术也更为关键.
● 在执行引擎层面, 如何根据自身定位选择合适的执行引擎.
如今, 无论在高性能计算、云平台还是数据库等领域, 分布式通用计算框架都已发展成熟. 分布式矩阵计算系统大多无须自行重新设计执行引擎, 而是将已有的通用计算框架作为底层的执行引擎. 然而, 目前通用计算框架种类繁多, 各自的性能表现在不同情况下也截然不同. 故不同定位的分布式矩阵计算系统所需的执行引擎自然也有所不同. 举例来说, 系统需要考虑所面向的硬件环境(如高性能计算框架对硬件要求高)或用户的使用习惯与倾向(如用户工作流中数据存放在数据库中). 因此, 系统需要结合多方面因素来选择最合适的执行引擎.
● 在数据存储层面, 如何设置节省内存占用且提升性能的数据存储方式.
在分布式矩阵计算系统中, 数据存储方式直接决定了数据的内存占用, 同时, 该方式也会影响执行过程中产生的数据传输开销, 因此也间接决定了系统性能的优劣. 除此之外, 在矩阵计算应用中, 需要处理的数据(包括输入数据与中间数据)的特征情况复杂, 例如矩阵的长宽、稀疏度、非零项分布等. 不同特征的矩阵对应的最优存储方式也截然不同, 需要系统能够结合运行时情况自适应地选择合适的数据存储方式.
如
分布式矩阵计算系统相关技术
● 编程接口
数据管理系统已针对接口的编程难度提出了自己的解决方案, 其中最具代表性的包括公认最通用的SQL语言标准以及如JDBC这样的通用编程语言接口. 为了提高接口的表达能力, 不同的数据管理系统各自对SQL进行拓展(如可选择连接操作的实现方式), 供用户灵活调整查询的执行. 类似地, 为了降低编程难度, 分布式矩阵计算系统的编程接口要么是基于数据分析师所熟悉的R语言或SQL语言的, 要么是基于通用编程语言的, 并且同样有系统会通过拓展的方式提供更灵活的接口, 以提高表达能力.
● 编译优化
分布式矩阵计算系统中的编译优化问题可视作数据管理系统中传统查询优化问题的变种, 其解决方案的思路是共通的, 分为优化计划拓扑和优化算子两方面: 首先, 在计划拓扑方面的一个典型例子是多表连接, 数据管理系统需要调整查询计划中连接的顺序以提升执行效率, 类似的问题同样出现在矩阵计算中的矩阵连乘链上; 其次, 在算子方面的一个典型例子是数据管理系统领域中的连接算子, 其实现方式多样, 分别适用于不同的情形, 而在矩阵计算中, 矩阵乘法算子也与其类似, 不同的实现方式各有优劣.
● 执行引擎
根据自身定位的不同, 数据管理系统的执行引擎也具有不同的特点, 例如, 面向分析的系统执行引擎善于处理多谓词的复杂查询, 而面向事务的系统执行引擎则善于处理高并发的数据更新. 对应地, 分布式矩阵计算系统同样有不同的定位, 例如, 面向超级计算机的系统采用的执行引擎是高性能计算系统.
● 数据存储
在数据管理系统中, 往往要对大规模结构化数据进行分布式存储, 其中涉及分割结构化数据、设置分割后数据单元的存储格式以及对数据单元进行分区. 而矩阵就是一种特殊的结构化数据, 对应的相关技术即包括矩阵单元分割、矩阵单元格式和矩阵分区方式.
综上所述, 这4类相关技术分别着眼于解决一批相对独立的分布式矩阵计算系统的问题. 接下来, 本文将就这4项技术分类展开介绍目前的研究进展.
分布式矩阵计算系统的一项重要功能是向上层用户隐藏底层的并行运算逻辑, 降低利用集群资源实现矩阵计算的开发门槛与成本. 为此, 现有的分布式矩阵计算系统提供了一系列编程接口, 根据所依赖的编程语言可分为3类: 基于R语言、基于通用编程语言、基于SQL语言,
PageRank编程示例
基于R语言的编程接口是3类接口中最便捷、使用门槛最低的: 首先, 该类编程接口遵循R语言中原有的数学编程方式, 使得用户能够简单明了地按照数学公式实现算法脚本; 其次, R语言作为一种被广为使用的数学编程语言, 为数据工程师们所熟悉. 当面对要采用分布式矩阵计算的场景时, 用户仅需少量的代码改动(如添加依赖包)即可将原来单机的R语言脚本迁移至分布式环境中运行.
进一步地, 在一系列基于R语言的编程接口中, 存在声明式编程与命令式编程两类.
● 声明式编程[
● 而命令式编程接口[
基于通用编程语言的编程接口允许用户直接在项目工程中运行分布式矩阵计算, 其优势在于灵活, 能够自然地与其他代码逻辑(如数据预处理)整合在一起. 与此同时, 相较于R语言这种最为直接的数学编程方式, 通用编程语言的使用门槛更高, 所以基于这一类编程接口的算法实现成本也更高.
另一方面, 由于通用编程语言的灵活性, 这一系列编程接口对分布式矩阵计算的抽象程度也不尽相同. 其中, SystemDS[
SQL是基于关系模型所研发的一套规范语言, 几乎所有主流的数据管理系统和大数据系统均支持SQL[
这些编程接口是通过在SQL原有的语法上进行扩展而设计出来的, 其中, 扩展方式分为两类: 一类为SimSQL[
除了编程语言之外,
对系统的编程接口的总结
系统 | 编程语言 | 分布式计算逻辑的透明度 | 与线性代数的接近程度 | 惰式计算 |
SystemDS | R语言, 通用编程语言 | ※※※ | ※※※ | √ |
Presto | R语言 | ※※ | ※※※ | √ |
DPLASMA | R语言 | ※ | ※ | √ |
SparkR | R语言 | ※ | ※※ | × |
pbdR | R语言 | ※※ | ※※※ | × |
DataLog | 通用编程语言, SQL语言 | ※※※ | ※※※ | √ |
MadLINQ | 通用编程语言 | ※ | ※※ | × |
Mahout Samsara | 通用编程语言 | ※※ | ※※※ | √ |
DistArrays, MLI | 通用编程语言 | ※※ | ※※ | √ |
Spartan, MLlib | 通用编程语言 | ※ | ※※ | √ |
SLATE, Chameleon, Elemental | 通用编程语言 | ※ | ※ | × |
SimSQL, MRQL | SQL语言 | ※※※ | ※※※ | √ |
SciDB | SQL语言 | ※ | ※ | √ |
● 分布式计算逻辑的透明度
系统用户是否需要在编写脚本时处理分布式计算逻辑, 决定了透明度的高低. 透明度越高, 则表示系统编程接口的封装程度越高, 用户需要考虑分布式计算逻辑的地方越少. 基于此, 现有系统可分为3类. 其中,
➢ 透明度最高的一类系统包括SystemDS、DataLog、SimSQL、MRQL, 它们的编程接口允许用户编写的脚本中不涉及任何关于分布式计算的代码逻辑, 用户可专注于设计算法, 因此, 这类系统的使用门槛最低.
➢ 透明度仅次于此的一类系统包括Presto、pbdR、Mahout Samsara、DistArray、MLI, 它们的编程接口需要用户手动指定哪些矩阵需要进行分布式处理, 但不需要处理具体的分布式计算逻辑. 为此, 用户需要了解脚本中所有矩阵的规模, 根据集群的硬件条件自行判断何处生成分布式矩阵、何时将分布式矩阵转换为本地矩阵. 所以, 这类系统的使用门槛相对更高.
➢ 透明度最低的一类系统包括DPLASMA[
● 与线性代数的接近程度
最简单、直观地描述数据分析算法的方式就是通过线性代数表达式, 因此, 系统编程接口与线性代数的接近程度直接反映了使用该系统接口的编程难度. 与线性代数接近程度最高的一类系统包括SystemDS、DataLog、Presto、pbdR、Mahout Samsara、SimQL、MRQL, 它们的编程接口主要由线性代数符号组成, 用户所编写的代码即是线性代数表达式. 在接近程度上处于第二梯队的一类系统包括SparkR、MadLINQ、DistArrays、Spartan、MLlib, 它们的编程接口以函数的形式提供了部分线性代数操作, 用户所编写的脚本代码由线性代数符号和函数共同组成. 接近程度最低的一类系统包括DPLASMA、SLATE、Chameleon、Elemental、SciDB, 它们的用户无法直接用线性代数符号来编写脚本, 而需要先编写线性代数表达式, 再利用提供的封装函数编写脚本, 因此, 这类系统接口的编程难度最大, 相较于原线性表达式, 用户脚本的代码量高, 可读性低.
● 惰式计算
为便于优化用户脚本的执行计划, 大多数系统(包括SystemDS、DataLog、Presto、DPLASMA、Mahout Samsara、DistArrays、Spartan、MLlib、SimSQL、MRQL、SciDB)采用了惰式计算.这样可以让系统在得到完整的数据分析逻辑后进行全局的优化, 然而, 惰式计算在脚本有错误的情况下可能无法及时、准确地反映错误代码位置, 因而会加大用户编写脚本时的调试难度.相反地, 也有系统(包括SparkR、pbdR、MadLINQ、SLATE、Chameleon、Elemental)没有采用惰式计算, 牺牲性能以降低调试难度.
矩阵计算广泛应用于机器学习、统计等数据科学领域, 这些领域的应用中往往涉及极其复杂的算法逻辑, 其对应的矩阵计算执行计划也具有复杂的拓扑结构. 因此, 如何做好对计划拓扑的优化, 是提升分布式矩阵计算性能的关键因素. 此外, 不同于单机环境下的矩阵计算, 分布式矩阵计算的性能受制于网络通信的开销.在执行计划中, 不同的算子所引起的网络通信开销有显著不同, 因此, 如何对执行计算中的算子进行优化同样至关重要. 综上, 本节将从计划拓扑与算子这两个层面分析与分布式矩阵计算相关的编译优化技术.
针对计划拓扑的优化技术可分为两类: 第1类为静态优化技术, 即无须考虑运行时的负载情况, 总是能够提升性能的优化技术; 第2类为动态优化技术, 这类技术在有些运行负载下能够显著提升性能, 但在某些特定情况下也可能造成性能损失, 因此需要结合运行时的负载情况动态制定优化决策.
静态优化技术为一系列通用的表达式替换规则[
➢ 常数折叠. 即将多个常数项折叠、计算为单个常数项, 以简化计划拓扑, 例如1+1+
➢ 移除无效操作. 即消除对运算结果无影响的操作, 例如,
➢ 避免多元操作. 即将包含多个变量的操作简化为包含更少变量的操作, 例如,
不同于静态优化技术, 动态优化技术需要根据运行时的负载情况, 在多个计划拓扑间进行权衡, 以提升系统性能. 相关技术如下.
● 增量计算加速
利用增量计算提升系统性能的技术已广泛应用于并行计算系统(如GraphLab[
增量计算
然而, 在分布式矩阵计算中盲目地采用增量计算加速技术可能导致对性能提升的收效甚微, 甚至会造成性能降低. 首先, 增量计算中存在雪崩效应. 如
雪崩效应
其次, 增量计算本身存在额外的开销, 尤其在分布式环境下, 增量计算可能远慢于原本的全量计算. 例如在
➢ 第一, 增量的非零项往往位置分散, 导致在分布式环境中增量计算无法优化网络通信这一性能瓶颈.以
增量分散对分布式矩阵计算过程的影响
➢ 第二, 增量矩阵可能是稠密的, 即其中大部分元素均在发生变化, 此时采用增量计算反而会显著地拖慢系统性能.
为此, HyMAC进一步提出了结合全量计算与增量计算的混合计算. 在每轮迭代开始前, HyMAC会动态地基于增量地统计信息进行代价估计, 以判断当前迭代是否采用增量计算.
● 冗余子式消除
矩阵计算应用的算法表达式中可能存在冗余子式, 包括公共子式、循环常量子式. 以Davidon-Fletcher-Powell(DFP)算法解
其中,
首先, 为了消除冗余子式, 系统需要能够在编译优化阶段感知公共子式与循环常量子式. 一种简单的方法是在生成的执行计划中逐一对算子进行判断, 出现输入、操作均相同的算子则表示存在公共子式, 而出现输入为循环常量的算子则表示存在循环常量子式. 这种方法的缺陷在于, 可能无法找到所有冗余子式. 以
隐式冗余子式
为了搜索隐式冗余子式, 就需要不断地对执行计划做等价转换, 而其中面临的最大挑战是线性代数的转换规则过于繁杂. 鉴于此, SPORES[
尽管SPORES能够高效地生成冗余消除方案, 但是在面对矩阵连乘链时仍然会错过部分冗余子式. 为此, ReMac[
其次, 搜索到的冗余子式之间可能互相冲突, 例如在
● 算子合并
在矩阵计算中, 多个连续的算子之间存在诸多可进行合并优化的情况, 具体包含3种情况: (1) 避免物化中间结果, 例如, 将(
根据对算子合并的支持, 现有系统可分为两类: 第1类系统通过固定的模式匹配来寻找可合并优化的算子, 如SystemDS、Mahout Samsara、MATFAST[
● 矩阵连乘链优化
矩阵连乘链的计划拓扑优化问题类似于数据库中的多表连接顺序问题, 不同的矩阵乘法计算顺序会导致显著的性能差异. 以矩阵连乘链
矩阵连乘链顺序对性能的影响
然而, 随后的计算顺序决策依赖于对中间结果
● 重编译
上述技术均依赖于运行时的负载信息, 然而在脚本运行前的优化编译阶段, 系统往往无法获取足够的负载信息(例如条件分支、矩阵规模). 为此, SystemDS提出了重编译技术, 即在脚本运行过程中, 重新对计划拓扑进行优化编译. 具体来说, 该技术按照脚本中的逻辑语句将待运行脚本划分为多个部分, 系统在每个部分运行前, 会基于新获取的负载信息对执行计划再次进行优化, 从而进一步改善了编译优化技术提升系统性能的空间.
确定好计划拓扑后, 系统需要进一步对执行计划进行算子层面的优化. 接下来, 本文将从算子实现、算子选择、算子优先级这3个方面介绍相关工作.
● 算子实现
在分布式环境中, 如何高效地实现线性代数算子对系统性能至关重要. 算子主要分为执行聚合操作(如求元素平均值)的算子、执行按位操作(如按位加、按位乘)的算子、执行矩阵乘法操作的算子. 其中, 聚合操作最简单, 分布式系统中已有成熟的聚合技术支持(如allreduce); 类似地, 按位操作的算子实现仅需按行、列位置将两个矩阵中的元素连接起来, 因此可依赖于分布式系统中对连接操作的技术支持(如半连接); 而矩阵乘法算子实现最为复杂, 也往往是性能瓶颈.
如
分布式矩阵乘法的实现思路
➢ 第1种思路是对
➢ 第2种思路是对
CPMM与RMM有各自适用的情形. 具体来说, CPMM需要在单机内存中缓存中间结果, 并且其并行度依赖于
针对RMM中需要大量复制矩阵的问题, SystemDS进一步提出了BMM[
● 算子选择.
既然上述这些算子实现有不同的硬件要求以及性能, 那么系统自然需要根据实际情况对这些算子实现进行选择.
首先, 在分布式环境中, 性能瓶颈往往在于网络通信开销, 没有网络通信的单机实现可能要比分布式实现更快, 因此系统需要在分布式与单机之间做选择. 一种简单、通用的判断方式是将向量操作放在单机上完成[
其次, 在分布式算子实现上还需要进行选择: 一方面, 这些算子在不同数据规模、硬件条件下的表现各不相同, SystemDS、Mahout Samsara对此构建了代价模型, 逐一选择计划拓扑中的算子实现; 另一方面, 算子与算子的实现之间会互相影响. 尤其在分布式矩阵乘法中, 不同的算子适合不同的输入形式. 例如, 对于
● 算子优先级.
在计划拓扑中, 往往会存在多条并行的执行路径. 因此在确定计划拓扑后, 还需确定算子优先级, 才能最终生成明确的执行计划. 其中, 最为重要的是明确计划拓扑中的关键路径, 系统需要优先执行关键路径上的算子, 以提高整体的硬件利用率. SLATE、Chameleon、DPLASMA、COnfLUX/COnfCHUX[
对系统的编译优化的总结
系统 | 针对计划 |
针对算子的 |
技术 |
提高计算 |
提高传输 |
SystemDS | √ | √ | ※※※ | √ | √ |
Mahout Samsara | √ | √ | ※※※ | √ | √ |
LINVIEW, F-IVM, HyMAC | √ | ※ | √ | √ | |
SPORES, ReMac | √ | ※ | √ | √ | |
MATFAST | √ | √ | ※※ | √ | |
Cumulon, OptiML, BTO, Kasen, Tupleware, Weld, TC, SPOOF | √ | ※※ | √ | ||
Marlin | √ | ※※ | √ | × | |
DMac, Spartan | √ | ※ | √ | ||
SLATE, Chameleon, DPLASMA, COnfLUX/COnfCHUX | √ | ※ | √ |
● 针对计划拓扑或算子的优化
由于数据分析算法的逻辑复杂, 且分布式计算的执行方式也多种多样, 因此, 分布式矩阵计算系统的编译优化技术种类繁多. 总体来说, SystemDS、Mahout Samsara、MATFAST考虑了计划拓扑与算子两方面的优化, 因此, 采用的优化技术较为完备, 充分发挥了编译优化器的作用. 其余的系统则专门针对计划拓扑(包括LINVIEW、F-IVM、HyMAC、SPORES、ReMac、Cumulon、OptiML、BTO、Kasen、Tupleware、Weld、TC、SPOOF)或算子(包括Marlin、DMac、Spartan、SLATE、Chameleon、DPLASMA、COnfLUX/COnfCHUX)进行优化, 相对于前者, 采用的编译优化技术仅局限在某一方面. 以Marlin为例, 尽管其针对矩阵乘法算子进行了优化, 但是若要充分发挥这一优化技术的作用, 也依赖于系统能够在计划拓扑层面结合新的算子实现的开销进行对应的调整.
● 技术通用性
在上述系统中, SystemDS与Mahout Samsara采用的编译优化技术覆盖了多种多样的线性代数表达式的形式, 并不针对某种特定的数据分析算法, 因此编译优化技术通用, 可应用于几乎所有的数据分析算法. 通用性次之的系统则针对某些表达式形式进行优化. 具体来说, MATFAST、Cumulon、OptiML、BTO、Kasen、Tupleware、Weld、TC、SPOOF所采用的算子合并技术仅可优化多种固定的表达式, 而Marlin所提出的矩阵乘法算子实现仅可应用于需要计算两个大规模矩阵的乘积的情况. 最后一类系统的编译优化技术通用性则最低, 专门针对某一类算法进行编译优化. 其中, LINVIEW、F-IVM、HyMAC提出的增量计算优化技术仅针对迭代收敛的算法, SPORES与ReMac局限在一类存在冗余表达式的算法; DMac、Spartan则着眼于由大规模矩阵组成的连乘链, 往往仅局限在矩阵分解算法上; 类似地, SLATE、Chameleon、DPLASMA、COnfLUX/COnfCHUX所提出的算子优先级优化技术, 也专门用于优化矩阵分解算法的执行效率.
● 提高计算或传输效率
在分布式矩阵计算中, 计算复杂度往往很高; 同时, 盲目地进行分布式计算又会产生大量的数据传输开销, 因此, 大多数系统(包括SystemDS、Mahout Samsara、LINVIEW、F-IVM、HyMAC、SPORES、ReMac)采用的编译优化技术以提高计算与传输效率为目标. 当然, 在不同的算法和硬件环境上, 系统的性能瓶颈也有所不同, 由此对应地也出现了不同侧重的系统编译优化技术. 其中, MATFAST、Cumulon、OptiML、BTO、Kasen、Tupleware、Weld、TC、SPOOF、DMac、Spartan着重解决数据传输开销过大的问题; 而SLATE、Chameleon、DPLASMA、COnfLUX/COnfCHUX则致力于调整算子优先级, 以避免计算资源空闲, 从而提高计算效率; Marlin所考虑的情形更为极端, 即计算开销显著高于传输开销, 因此需要通过牺牲传输效率的方式换取更高的计算效率, 以在整体上提升系统性能.
在编译优化之后, 分布式矩阵计算系统依托于底层的执行引擎以完成最终的分布式计算. 而由于执行引擎的不同, 矩阵计算系统生成的执行计划形式也有所不同. 如
执行引擎概览
最为广泛使用的执行引擎为大数据处理系统, 包括MapReduce (Hadoop)[
现有的数据库执行引擎可分为两类: 第1类是通用数据库执行引擎, 包括PostgresQL[
高性能计算系统是一类专门针对高硬件配置的超级计算机集群进行设计的执行引擎, 如ScaLAPACK[
综上, 目前的执行引擎种类、特点繁多, 对应地, 目前的分布式矩阵计算系统可根据所面向的用户、硬件和应用, 针对性地选择合适的执行引擎.
对系统的执行引擎的总结
系统 | 软件栈生态 | 适用的硬件档次 | 容错能力 | 对稀疏矩阵操作的支持 |
SystemDS | ※※ | ※ | ※※※ | ※※※ |
MADlib | ※※ | ※ | ※※ | ※※※ |
SciDB | ※※ | ※※ | ※※ | ※※ |
pbdR | ※ | ※※ | ※ | ※ |
● 软件栈生态. 执行引擎的软件栈生态, 是影响用户开发成本的一项重要因素. 以SystemDS为例, 该系统以大数据系统Spark为执行引擎, 归功于开源社区的贡献, 其上下游的软件栈支持丰富, 包含从上层的数据分析工具到下层的文件系统和数据导入工具. SystemDS用户可通过这些工具方便地将SystemDS接入他们的工作流中. 类似地, MADlib以开源数据库PostgreSQL与Greenplum为执行引擎, 依托这两个数据库活跃的开源社区, MADlib同样拥有丰富的上下层软件工具, 便于数据库用户使用.相较之下, SciDB自研的执行引擎与pbdR所采用的ScaLAPACK的软件栈生态支持则略显不足, 用户需要自行开发上下层的对接工具, 加大了开发成本.
● 适用的硬件档次. 根据所面向的用户群体、应用场景的不同, 系统侧重的硬件环境也有所不同. 对应地, 系统应选择合适的执行引擎, 以充分利用各种档次的硬件的特点提升系统性能. 总体来说, 包含SystemDS、MADlib、SciDB在内的一类系统面向的是拥有大量廉价服务器或云平台资源的用户, 因此所选择的执行引擎拥有高扩展性, 且注重优化运行过程中的数据传输开销和内存占用等廉价硬件上常见的性能问题. 而包含pbdR在内的一类系统则面向的是拥有超级计算机集群资源的用户, 所以它们的执行引擎侧重于发挥高档硬件的优势, 例如利用内存空间大的优势采用纯内存计算, 以及优化缓存机制来提升对高档计算资源的利用率.
● 容错能力. 大数据分析应用往往需要长时间的运算处理, 在此期间更有可能发生故障. 而系统若要尽快地从故障中恢复以继续进行运算, 就需要具备一定的容错能力. 容错能力最高的一类系统包括SystemDS, 该系统依托Spark的容错机制, 能在分布式矩阵计算发生故障时, 针对当前的子任务进行重试, 避免了重新运行一遍完整的用户脚本. 而包含MADlib、SciDB在内的一类系统则依赖于执行引擎中的副本机制实现容错, 但是当所有副本均发生故障时, 这类系统需要重新运行脚本, 因此容错能力不如前者. 而最后, 包含pbdR在内的一类系统则缺乏成熟的容错机制, 更依赖于硬件本身的可靠性, 以避免故障的发生.
● 对稀疏矩阵操作的支持. 现有系统的执行引擎通常均支持稠密矩阵操作, 但是对稀疏矩阵操作的支持程度却不尽相同. 支持程度最高的一类系统包括SystemDS、MADlib, 所有矩阵操作均支持稀疏矩阵. 而SciDB仅对部分操作开放稀疏矩阵, 因此支持程度低于前者. pbdR等以ScaLAPACK为执行引擎的系统则只面向稠密矩阵计算, 即无论矩阵是否稀疏, 都将其视为稠密矩阵进行处理, 因此盲目地使用这类系统可能会碰到稀疏数据导致的内存占用过大或数据传输开销过大等性能问题.
如何在集群中组织、存储分布式矩阵, 对系统性能至关重要. 接下来, 本文将从矩阵单元分割、矩阵单元格式、矩阵分区方式这3个方面进行介绍.
作为组织数据的最小单位, 一个矩阵单元的大小从3个方面影响了系统的性能表现.
(1) 矩阵单元大小会直接影响内存占用: 单元设置得过大会导致内存溢出; 同时, 单元设置得过小也会导致系统需要维护大量结构数据(例如单元索引), 进而提高总内存占用.
(2) 单元大小决定了一个分布式矩阵会被分割为多少个单元: 单元设置得过小(即单元数过大), 会加剧分布式矩阵计算操作中的网络通信开销.
(3) 单元大小同时也决定了最大并行度: 单元设置得过大, 会导致单元数(即最大并行度)小于集群的并行度, 无法充分利用集群的计算资源.
基础的做法是, 系统预设一个固定的单元大小. 这类做法分为3种, 如
固定矩阵单元大小的基础分割方式
➢ 第1种做法是将一个分布式矩阵划分为多个固定的1000×1000的矩阵单元[
➢ 第2种做法是将矩阵中一(或多)行(或列)作为一个单元, 适用于仅需按行或按列访问的矩阵[
➢ 第3种做法则更加极端, 是将每个元素作为一个单元. 这样做能够加快某些特定的操作(例如三对角化操作)[
显然, 上述固定的分割方式得到的单元大小无法应对所有的数据规模和硬件环境, 因此往往不是最优的.为此, 目前已有不少工作针对运行环境和负载情况对自动单元大小进行调整.
➢ 一类工作以优化通信开销与内存占用为目标. 其中, SUMMA[
➢ 另一类工作则以权衡并行度与内存开销为目标. 为保障集群运算的最小并行度, DMac限制了单元的最小大小, 在此基础上最小化内存占用. 而MATFAST则将最小的单元大小设置为1 000, 在此基础上尽可能地提升并行度.
此外, 上述工作分割出的大部分矩阵单元的长宽是一样的. 然而, 在数据极度倾斜的稀疏矩阵上, 这种分割会导致有些矩阵单元内几乎没有非零项, 而有些单元则十分拥挤, 不利于批处理执行矩阵计算. 为此, 李亿渊等人[
为了最小化内存占用, 分布式矩阵计算系统需要为不同稀疏度的矩阵设置不同的矩阵单元格式, 其中, 稠密矩阵通过二维数组存放即可, 而稀疏矩阵的存储则更加复杂.
稀疏存储格式的基本思路是, 通过忽略单元中的零项以节省空间. 其中, 为分布式矩阵计算系统广泛采用的是稀疏行/列压缩格式(CSR/CSC). 以CSR为例, 该格式需要维护3个一维数组: 前两个数组按先行后列的顺序分别存放所有非零项数值与其对应的列号, 第3个数组则作为查询索引保留每行第1项在前两个数组中的位置(如
CSR示例
此外, 矩阵单元格式也可针对某些特殊的矩阵结构进行特定的优化. 具体来说, SLATE专门为梯形/三角矩阵和对称/厄米特矩阵设计了特定的存储格式. 具体来说, 在梯形/三角矩阵中, 虽然整体是稀疏矩阵, 但是矩阵的非零部分是稠密的, 因此仅非零部分按照稠密格式存储. 而在对称/厄米特矩阵中, 系统仅需存储一半的数据, 另一半可推算得到.
由于分布式矩阵计算中经常会出现连接、聚合矩阵元素的操作, 因此, 如何设置矩阵的单元分区方式至关重要. 一种合适的分区方式可以显著降低分布式矩阵计算的网络通信开销, 进而提升性能. 基础的分区方式包括:
(1) 乱序分区, 例如通过哈希函数分配单元所处分区[
分区数为4的基础分区方式示例
(2) 按行/列分区, 将行/列索引相同的单元分配到同一个分区上[
不同的分区方式适用于不同的算子操作, 例如, 按行分区适合统计行平均值的算子. 为了让系统能够自动选取最优的分区方式, DMac、MATFAST与BlockJoin[
对系统的数据存储的总结
系统 | 对执行效率的提升 | 对存储空间占用的优化 |
SystemDS | ※※ | ※※ |
SUMMA | ※※ | ※ |
CARMA | ※※ | ※※※ |
DMac | ※※※ | ※※※ |
MATFAST | ※※※ | ※※ |
SLATE | ※ | ※※※ |
BlockJoin, DistME | ※※※ | ※ |
● 对执行效率的提升. 上述系统按对执行效率的提升可分为3个档次: 提升最高的一类系统包括DMac、MATFAST、BlockJoin、DistME, 它们通过优化数据分区的方式, 显著提升了算子执行时的中间数据传输开销; 相较之下, SUMMA仅针对特定的集群架构优化数据存储方式, 有局限性, CARMA仅优化了矩阵的单元大小, 而SystemDS则仅采用了基础的数据存储方式来提升部分执行效率, 因此它们的提升档次居中; SLATE则并没有专门针对执行效率问题优化数据存储方式.
● 对存储空间占用的优化. 类似地, 上述系统按对存储空间占用的优化可分为3个档次: 优化最好的一类系统包括CARMA、DMac、SLATE, 它们自适应地调整矩阵单元以最小化对存储空间的占用; SystemDS则采取了相对基础、保守的方式设置数据存储方式, 故优化效果略逊于前者; SUMMA、BlockJoin、DistME则没有专门针对存储空间占用问题优化数据存储方式.
从整体来看, 分布式矩阵计算系统的相关工作致力于改进系统的两个方面, 也是用户最关心的, 即编程接口用起来是否方便和系统性能是否满足需求. 因此, 本节将从这两方面总结分析目前功能成熟且广泛使用的一批开源系统, 包括pbdR、MLlib、SystemDS、MADlib、SciDB. 此外, 如
对开源系统的总体分析
系统 | 易用性 | 性能 | 适用场景 |
pbdR | ※※ | ※※ | 轻量级矩阵计算应用/测试 |
MLlib | ※ | ※ | 与Spark生态紧密结合的工作流 |
SystemDS | ※※※ | ※※※ | 关注调优难度且有性能需求的应用 |
MADlib | ※ | ※ | 以数据库为数据源的应用 |
SciDB | ※ | ※※ | 大规模科学计算应用 |
● 首先, 从编程角度来看, SystemDS是最易使用的, 用户完全不用考虑分布式计算逻辑; pbdR也相对易用, 仅需要用户自行区别分布式矩阵和单机矩阵; 而剩余的系统就暴露了更多繁杂的分布式计算逻辑.
● 其次, 从性能角度来看, 根据现有的系统评测[
➢ SystemDS凭借其优化技术, 能够在几乎所有负载下取得最优或近优的性能.
➢ pbdR与SciDB能够在稠密矩阵计算负载中取得与SystemDS相近的性能, 但缺少对稀疏矩阵计算的支持.
➢ MADlib与MLlib的性能则相对不足, 其中, MADlib由于执行引擎的缘故, 需要通过读写磁盘的方式传递中间结果, 导致不必要的中间结果物化和磁盘读写开销; 而MLlib由于其复杂的调优选项(例如, 需要对每个矩阵调整其单元格式、分区方式或数量、缓存机制), 难以取得最优的性能.
因此, 总体上, SystemDS是目前较为易用且性能优异的分布式矩阵计算系统, 但其余系统也有其各自适用的场景: 归功于pbdR轻量级的部署与简便的编程接口, 用户可以通过pbdR快速扩展、运行/测试原本的单机算法; MLlib适用于原本就基于Spark生态构建的工作流; MADlib允许用户直接在数据库中用矩阵计算逻辑处理数据; 而SciDB则适合处理科学计算应用中的大规模多维张量.
分布式矩阵计算系统具有广泛的应用前景, 本节简要讨分布式矩阵计算系统未来可能的发展方向.
● 迎接深度学习应用对于矩阵计算的新型需求. 现有的分布式矩阵计算系统重视矩阵乘法等简单批量操作的优化, 然而, 时下最流行的深度学习应用中还涉及卷积计算等更复杂的操作, 矩阵计算系统目前还缺乏对这些操作的成熟支持[
● 挖掘与底层执行引擎深度融合的潜在动能. 现有的分布式矩阵计算系统主要侧重于如何发挥底层执行引擎的作用, 与执行引擎的耦合度相对较低. 本文中提到的诸多系统(如SystemDS、HyMAC、DMac、MATFAST)均依赖于底层Spark的接口来实现自身的优化技术. 然而, Spark作为一个独立的面向通用计算的平台, 无法感知矩阵计算应用的特点, 自然也无法针对性地优化底层的执行过程. 一个典型的例子是, 上层矩阵计算系统无法直接管理Spark中数据和算子的物理位置, 仅能通过接口管理其逻辑位置. 因此, 分布式矩阵计算系统仍然存在潜在的性能提升空间, 可通过深度融合矩阵计算应用与底层执行引擎进一步挖掘.
● 发挥硬件加速器为矩阵计算带来的强大算力. 目前, 新型硬件加速器层出不穷, 相较于CPU, 这些加速器提供了更高的计算并行度, 且更善于处理无分枝的运算逻辑, 十分贴合矩阵计算的应用场景. 尽管已有不少工作提出了基于新硬件加速器的优化技术[
本文首先回顾了矩阵计算系统的发展历程, 突出了新兴的分布式矩阵计算系统在大数据治理中的关键作用; 然后, 本文参考了数据管理领域的研究思路, 从数据管理视角分析了分布式矩阵计算系统面临的挑战以及相关技术分类; 随后, 详细介绍、总结了各个分类下的现有技术如何解决前述挑战; 最后, 本文总体分析了典型的分布式矩阵计算系统, 并展望了未来的研究方向.
Sylvester J. On a new class of theorems. The London, Edinburgh, and Dublin Philosophical Magazine and Journal of Science, 1850, 37: 363-370.
Cayley A. A memoir on the theory of matrices. Philosophical Trans. of the Royal Society of London, 1858, 31(148): 17-37.
Gu R, Qiu HJ, Yang WJ, Hu W, Yuan CF, Huang YH. Goldfish: A large scale semantic data store and query system based on Boolean matrix factorization. Chinese Journal of Computers, 2017, 40(10): 2212-2230 (in Chinese with English abstract).
顾荣, 仇红剑, 杨文家, 胡伟, 袁春风, 黄宜华. Goldfish: 基于矩阵分解的大规模RDF数据存储与查询系统. 计算机学报, 2017, 40(10): 2212-2230.
Shen XW, Ye XC, Wang D, Zhang H, Wang F, Tan X, Zhang ZM, Fan DR, Tang ZM, Sun NH. Optimizing dataflow architecture for scientific applications. Chinese Journal of Computers, 2017, 40(9): 2181-2196 (in Chinese with English abstract).
申小伟, 叶笑春, 王达, 张浩, 王飞, 谭旭, 张志敏, 范东睿, 唐志敏, 孙凝晖. 一种面向科学计算的数据流优化方法. 计算机学报, 2017, 40(9): 2181-2196.
Big data analytics market.
Abadi M, Barham P, Chen J, Chen Z, Davis A, Dean J, Devin M, Ghemawat S, Irving G, Isard M, Kudlur M. TensorFlow: A system for large-scale machine learning. In: Proc. of the 12th USENIX Symp. on Operating Systems Design and Implementation. Savannah: USENIX, 2016. 265-283.
PyTorch.
Hellerstein J, Re C, Schoppmann F, Wang DZ, Fratkin E, Gorajek A, Ng KS, Welton C, Feng X, Li K, Kumar A. The MADlib analytics library or MAD skills, the SQL. Proc. of the VLDB Endowment, 2012, 5(12): 1700-1711.
Boehm M, Dusenberry MW, Eriksson D, Evfimievski AV, Manshadi FM, Pansare N, Reinwald B, Reiss FR, Sen P, Surve AC, Tatikonda S. SystemML: Declarative machine learning on spark. Proc. of the VLDB Endowment, 2016, 9(13): 1425-1436.
Bosagh Zadeh R, Meng X, Ulanov A, Yavuz B, Pu L, Venkataraman S, Sparks ER, Staple A, Zaharia M. Matrix computations and optimization in apache spark. In: Proc. of the 22nd ACM SIGKDD Int'l Conf. on Knowledge Discovery and Data Mining. San Francisco: ACM, 2016. 31-38.
Schelter S, Palumbo A, Quinn S, Marthi S, Musselman A. Samsara: Declarative machine learning on distributed dataflow systems. In: Proc. of the 30th Conf. on Neural Information Processing Systems. Barcelona: Curran Associates Inc., 2016.
Chen L, Kumar A, Naughton J, Patel JM. Towards linear algebra over normalized data. Proc. of the VLDB Endowment, 2016, 10(11): 1214-1225.
Gan J, Liu T, Li L, Zhang J. Non-negative matrix factorization: A survey. The Computer Journal, 2021, 64(7): 1080-1092.
Gou P, Wang K, Luo AL, Xue MZ. Computational intelligence for big data analysis: Current status and future prospect. Ruan Jian Xue Bao/Journal of Software, 2015, 26(11): 3010-3025 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/4900.htm [doi: 10.13328/j.cnki.jos.004900]
郭平, 王可, 罗阿理, 薛明志. 大数据分析中的计算智能研究现状与展望. 软件学报, 2015, 26(11): 3010-3025. http://www.jos.org.cn/1000-9825/4900.htm [doi: 10.13328/j.cnki.jos.004900].
Qian Z, Chen, X, Kang N, Chen M, Yu Y, Moscibroda T, Zhang Z. MadLINQ: Large-scale distributed matrix computation for the cloud. In: Proc. of the 7th ACM European Conf. on Computer Systems. Bern: ACM, 2012. 197-210.
Venkataraman S, Bodzsar E, Roy I, AuYoung A, Schreiber RS. Presto: Distributed machine learning and graph processing with sparse matrices. In: Proc. of the 8th ACM European Conf. on Computer Systems. Prague: ACM, 2013. 197-210.
Bosilca G, Bouteiller A, Danalis A, Faverge M, Haidar A, Herault T, Kurzak J, Langou J, Lemarinier P, Ltaief H, Luszczek P, YarKhan A, Dongarra J. Flexible development of dense linear algebra algorithms on massively parallel architectures with DPLASMA. In: Proc. of the IEEE Int'l Symp. on Parallel and Distributed Processing Workshops and Phd Forum. Anchorage: IEEE, 2011. 1432-1441.
Chen Z, Xu C, Soto J, Markl V, Qian W, Zhou A. Hybrid evaluation for distributed iterative matrix computation. In: Proc. of the ACM Int'l Conf. on Management of Data. Xi'an: ACM, 2021. 300-312.
Das S, Sismanis Y, Beyer KS, Gemulla R, Haas PJ, McPherson J. Ricardo: Integrating R and hadoop. In: Proc. of the ACM Int'l Conf. on Management of Data. Indianapolis: ACM, 2010. 987-998.
Venkataraman S, Yang Z, Liu D, Liang E, Falaki H, Meng X, Xin R, Ghdsi A, Franklin M, Stoica I, Zaharia M. SparkR: Scaling R programs with spark. In: Proc. of the ACM Int'l Conf. on Management of Data. San Francisco: ACM, 2016. 1099-1104.
RHadoop.
Programming with big data in R.
Poulson J, Marker B, Van de Geijn RA, Hammond JR, Romero NA. Elemental: A new framework for distributed memory dense matrix computations. ACM Trans. on Mathematical Software, 2013, 39(2): 1-24.
Boehm M, Burdick DR, Evfimievski AV, Reinwald B, Reiss F, Sen P, Tatikonda S, Tian Y. SystemML's optimizer: Plan generation for large-scale machine learning programs. IEEE Data Engineering Bulletin, 2014, 37(3): 52-62.
Boehm M, Antonov I, Baunsgaard S, Dokter M, Ginthor R, Innerebner K, Lindstaedt SN, Phani A, Rath B, Reinwald B, Siddiqui S, Wrede SB. SystemDS: A declarative machine learning system for the end-to-end data science lifecycle. In: Proc. of the 10th Biennial Conf. on Innovative Data Systems Research. 2020.
Wang J, Wu J, Li M, Gu J, Das A, Zaniolo C. Formal semantics and high performance in declarative machine learning using datalog. The VLDB Journal, 2021, 30: 859-881.
DistArrays.
Huang CC, Chen Q, Wang Z, Power R, Ortiz J, Li J, Xiao Z. Spartan: A distributed array framework with smart tiling. In: Proc. of the USENIX Annual Technical Conf. Santa Clara: USENIX, 2015. 1-15.
Sparks ER, Talwalkar A, Smith V, Kottalam J, Pan X, Gonzalez JE, Franklin MJ, Jordan MI, Kraska T. MLI: An API for distributed machine learning. In: Proc. of the IEEE 13th Int'l Conf. on Data Mining. Dallas: IEEE, 2013. 1187-1192.
Yu L, Shao Y, Cui B. Exploiting matrix dependency for efficient distributed matrix computation. In: Proc. of the ACM Int'l Conf. on Management of Data. Melbourne: ACM, 2015. 93-105.
Gates M, Kurzak J, Charara A, YarKhan A, Dongarra J. SLATE: Design of a modern distributed and accelerated linear algebra library. In: Proc. of the Int'l Conf. for High Performance Computing, Networking, Storage and Analysis. Denver: ACM, 2019. 26: 1-26: 18.
Agullo E, Aumage O, Faverge M, Furmento N, Pruvost F, Sergent M, Thibault SP. Achieving high performance on supercomputers with a sequential task-based programming model. IEEE Trans. on Parallel and Distributed Systems, 2017.
Armbrust M, Xin RS, Lian C, Huai Y, Liu D, Bradley JK, Meng X, Kaftan T, Franklin MJ, Ghodsi A, Zaharia M. Spark SQL: Relational data processing in spark. In: Proc. of the ACM Int'l Conf. on Management of Data. Melbourne: ACM, 2015. 1383-1394.
MRQL.
Brown PG. Overview of SciDB: Large scale array storage, processing and analysis. In: Proc. of the ACM Int'l Conf. on Management of Data. Indianapolis: ACM, 2010. 963-968.
Alotaibi R, Cautis B, Deutsch A, Manolescu I. HADAD: A lightweight approach for optimizing hybrid complex analytics queries. In: Proc. of the ACM Int'l Conf. on Management of Data. Xi'an: ACM, 2021. 23-35.
Low Y, Gonzalez J, Kyrola A, Bickson D, Guestrin C, Hellerstein JM. Distributed GraphLab: A framework for machine learning in the cloud. Proc. of the VLDB Endowment, 2012, 5(8): 716-727.
Malewicz G, Austern MH, Bik AJ, Dehnert JC, Horn I, Leiser N, Czajkowski G. Pregel: A system for large-scale graph processing. In: Proc. of the ACM Int'l Conf. on Management of Data. Indianapolis: ACM, 2010. 135-146.
Carbone P, Katsifodimos A, Ewen S, Markl V, Haridi S, Tzoumas K. Apache Flink: Stream and batch processing in a single engine. Bulletin of the IEEE Computer Society Technical Committee on Data Engineering, 2015, 36(4): 28-38.
Ewen S, Tzoumas K, Kaufmann M, Markl V. Spinning fast iterative data flows. Proc. of the VLDB Endowment, 2012, 5(12): 1268-1279.
Mihaylov SR, Ives ZG, Guha S. REX: Recursive, delta-based data-centric computation. Proc. of the VLDB Endowment, 2012, 5(11): 1280-1291.
McSherry F, Murray DG, Isaacs R, Isard M. Differential dataflow. In: Proc. of the 6th Biennial Conf. on Innovative Data Systems Research. 2013.
Murray DG, McSherry F, Isaacs R, Isard M, Barham P, Abadi M. Naiad: A timely dataflow system. In: Proc. of the 24th ACM Symp. on Operating Systems Principles. Farmington: ACM, 2013. 439-455.
Nikolic M, Elseidy M, Koch C. LINVIEW: Incremental view maintenance for complex analytical queries. In: Proc. of the ACM Int'l Conf. on Management of Data. Snowbird: ACM, 2014. 253-264.
Nikolic M, Olteanu D. Incremental view maintenance with triple lock factorization benefits. In: Proc. of the ACM Int'l Conf. on Management of Data. Houston: ACM, 2018. 365-380.
Kunft A, Katsifodimos A, Schelter S, Breß S, Rabl T, Markl V. An intermediate representation for optimizing machine learning pipelines. Proc. of the VLDB Endowment, 2019, 12(11): 1553-1567.
Yu Y, Tang M, Aref WG, Malluhi QM, Abbas MM, Ouzzani M. In-memory distributed matrix computation processing and optimization. In: Proc. of the IEEE 33rd Int'l Conf. on Data Engineering. San Diego: IEEE, 2017. 1047-1058.
Wang YR, Hutchison S, Suciu D, Howe B, Leang J. SPORES: Sum-product optimization via relational equality saturation for large scale linear algebra. Proc. of the VLDB Endowment, 2020, 13(11): 1919-1932.
Green TJ, Karvounarakis G, Tannen V. Provenance semirings. In: Proc. of the 26th ACM-SIGACT-SIGART Symp. on Principles of Database Systems. Santa Barbara: ACM, 2007. 31-40.
Tate R, Stepp M, Tatlock Z, Lerner S. Equality saturation: A new approach to optimization. In: Proc. of the 36th Annual ACM SIGPLAN-SIGACT Symp. on Principles of Programming Languages. Savannah: ACM, 2009. 264-276.
Chen Z, Xu C, Qian W, Zhou A. Redundancy elimination in distributed matrix computation. In: Proc. of the ACM Int'l Conf. on Management of Data. Philadelphia: ACM, 2022. 573-586.
Karsavuran MO, Akbudak K, Aykanat C. Locality-aware parallel sparse matrix-vector and matrix-transpose-vector multiplication on many-core processors. IEEE Trans. on Parallel and Distributed Systems, 2015, 27(6): 1713-1726.
Han D, Lee J, Kim M. FuseME: Distributed matrix computation engine based on cuboid-based fused operator and plan generation. In: Proc. of the ACM Int'l Conf. on Management of Data. Philadelphia: ACM, 2022. 1891-1904.
Huang B, Babu S, Yang J. Cumulon: Optimizing statistical data analysis in the cloud. In: Proc. of the ACM Int'l Conf. on Management of Data. New York: ACM, 2013. 1-12.
Belter G, Jessup ER, Karlin I, Siek JG. Automating the generation of composed linear algebra kernels. In: Proc. of the Conf. on High Performance Computing Networking, Storage and Analysis. Portland: Association for Computing Machinery, 2009. 1-12.
Sujeeth AK, Lee HJ, Brown KJ, Rompf T, Chafi H, Wu M, Atreya AR, Odersky M, Olukotun K. OptiML: An implicitly parallel domain-specific language for machine learning. In: Proc. of the 28th Int'l Conf. on Machine Learning. Washington: Omnipress, 2011. 609-616.
Zhang M, Wu Y, Chen K, Ma T, Zheng W. Measuring and optimizing distributed array programs. Proc. of the VLDB Endowment, 2016, 9(12): 912-923.
Crotty A, Galakatos A, Dursun K, Kraska T, Binnig C, Cetintemel U, Zdonik S. An architecture for compiling UDF-centric workflows. Proc. of the VLDB Endowment, 2015, 8(12): 1466-1477.
Palkar S, Thomas JJ, Shanbhag A, Narayanan D, Pirk H, Schwarzkopf M, Amarasinghe S, Zaharia M. Weld: A common runtime for high performance data analytics. In: Proc. of the 8th Biennial Conf. on Innovative Data Systems Research. 2017.
Vasilache N, Zinenko O, Theodoridis T, Goyal P, DeVito Z, Moses WS, Verdoolaege S, Adams A, Cohen A. Tensor comprehensions: Framework-agnostic high-performance machine learning abstractions. arXiv: 1802.04730, 2018.
Elgamal T, Luo S, Boehm M, Evfimievski AV, Tatikonda S, Reinwald B, Sen P. SPOOF: Sum-product optimization and operator fusion for large-scale machine learning. In: Proc. of the 8th Biennial Conf. on Innovative Data Systems Research. 2017.
Boehm M, Reinwald B, Hutchison D, Hutchison D, Sen P, Evfimievski AV, Pansare N. On optimizing operator fusion plans for large-scale machine learning in SystemML. Proc. of the VLDB Endowment, 2018, 11(12): 1755-1768.
Matlab mmtimes function.
Sommer J, Boehm M, Evfimievski AV, Reinwald B, Haas PJ. MNC: Structure-exploiting sparsity estimation for matrix expressions. In: Proc. of the Int'l Conf. on Management of Data. Amsterdam: ACM, 2019. 1607-1623.
Ghoting A, Krishnamurthy R, Pednault EPD, Reinwald B, Sindhwani V, Tatikonda S, Tian Y, Vaithyanathan S. SystemML: Declarative machine learning on MapReduce. In: Proc. of the 27th IEEE Int'l Conf. on Data Engineering. Hannover: IEEE, 2011. 231-242.
Liao X, Li SG, Lu YT, Yang CQ. New 2.5D parallel matrix multiplication algorithm based on BLACS. Chinese Journal of Computers, 2020, 44(5): 1037-1050 (in Chinese with English abstract).
廖霞, 李胜国, 卢宇彤, 杨灿群. 基于BLACS的2.5D并行矩阵乘法. 计算机学报, 2020, 44(5): 1037-1050.
Feng J, Ni M, Zhao JB. Algorithm of distributed matrix multiplication based on hadoop. Computer Systems Applications, 2013, 22(12): 149-154 (in Chinese with English abstract).
冯健, 倪明, 赵建波. 一种基于分布式平台Hadoop的矩阵相乘算法. 计算机系统应用, 2013, 22(12): 149-154.
Gu R, Tang Y, Tian C, Zhou H, Li G, Zheng X, Huang Y. Improving execution concurrency of large-scale matrix multiplication on distributed data-parallel platforms. IEEE Trans. on Parallel and Distributed Systems, 2017, 28(9): 2539-2552.
Kwasniewski G, Kabic M, Ben-Nun T, Ziogas AN, Saether JE, Gaillard A, Schneider T, Besta M, Kozhevnikov A, VandeVondele J, Hoefler T. On the parallel I/O optimality of linear algebra kernels: Near-optimal matrix factorizations. In: Proc. of the Int'l Conf. for High Performance Computing, Networking, Storage and Analysis. St. Louis: ACM, 2021. 70: 1-70: 15.
Dean J, Ghemawat S. MapReduce: Simplified data processing on large clusters. Communications of the ACM, 2008, 51(1): 107-113.
Isard M, Budiu M, Yu Y, Birrell A, Fetterly D. Dryad: Distributed data-parallel programs from sequential building blocks. In: Proc. of the 2nd ACM SIGOPS/EuroSys European Conf. on Computer Systems. Lisbon: ACM, 2007. 59-72.
Zaharia M, Chowdhury M, Das T, Dave A, Ma J, McCualy M, Franklin MJ, Shenker S, Stoica I. Resilient distributed datasets: A fault-tolerant abstraction for in-memory cluster computing. In: Proc. of the 9th USENIX Symp. on Networked Systems Design and Implementation. San Jose: USENIX, 2012. 15-28.
H2O.
PostgreSQL.
MySQL.
GreenPlum.
Zhang Y, Herodotou H, Yang J. RIOT: I/O-efficient numerical computing without SQL. In: Proc. of the 4th Biennial Conf. on Innovative Data Systems Research. 2009.
ScaLAPACK.
PETSc.
Van De Geijn RA, Watts J. SUMMA: Scalable universal matrix multiplication algorithm. Concurrency: Practice and Experience, 1997, 9(4): 255-274.
Ballard G, Demmel J, Holtz O, Lipshitz B, Schwartz O. Communication-optimal parallel algorithm for Strassen's matrix multiplication. In: Proc. of the 24th Annual ACM Symp. on Parallelism in Algorithms and Architectures. Pittsburgh: ACM, 2012. 193-204.
Demmel J, Eliahu D, Fox A, Kamil S, Lipshitz B, Schwartz O, Spillinger O. Communication-optimal parallel recursive rectangular matrix multiplication. In: Proc. of the IEEE 27th Int'l Symp. on Parallel and Distributed Processing. Cambridge: IEEE, 2013. 261-272.
Li YY, Xue W, Chen DX, Wang XL, Xu P, Zhang WS, Yang GW. Performance optimization for sparse matrix-vector multiplication on sunway architecture. Chinese Journal of Computers, 2020, 43(6): 1010-1024 (in Chinese with English abstract).
李亿渊, 薛巍, 陈德训, 王欣亮, 许平, 张武生, 杨广文. 稀疏矩阵向量乘法在申威众核架构上的性能优化. 计算机学报, 2020, 43(6): 1010-1024.
Long GP, Fan DR. Parallelization of LU decomposition on the Godson-Tv1 many-core architecture. Chinese Journal of Computers, 2009, 32(11): 2157-2167 (in Chinese with English abstract).
龙国平, 范东睿. LU分解在Godson-Tv1众核体系结构上的并行化研究. 计算机学报, 2009, 32(11): 2157-2167.
Kunft A, Katsifodimos A, Schelter S, Rabl T, Markl V. Blockjoin: Efficient matrix partitioning through joins. Proc. of the VLDB Endowment, 2017, 10(13): 2061-2072.
Han D, Nam Y, Lee J, Park K, Kim H, Kim M. DistME: A fast and elastic distributed matrix computation engine using GPUs. In: Proc. of the Int'l Conf. on Management of Data. Amsterdam: ACM, 2019. 759-774.
Thomas A, Kumar A. A comparative evaluation of systems for scalable linear algebra-based analytics. Proc. of the VLDB Endowment, 2018, 11(13): 2168-2182.
Han B, Chen Z, Xu C, Zhou A. Efficient matrix computation for SGD-based algorithms on apache spark. In: Proc. of the 27th Database Systems for Advanced Applications. Springer, 2022. 309-324.
Parger M, Winter M, Mlakar D, Steinberger M. SpECK: Accelerating GPU sparse matrix-matrix multiplication through lightweight analysis. In: Proc. of the 25th ACM SIGPLAN Symp. on Principles and Practice of Parallel Programming. San Diego: ACM, 2020. 362-375.