执行“张量代数”的新系统提供更快的大数据分析

一个新的MIT计算机系统加快了涉及“稀疏张量”（主要由零组成的多维数据数组）的计算速度。

在计算机协会的系统，编程，语言和应用大会上：麻省理工学院，法国替代能源和原子能委员会的研究人员和人类研究软件（SPLASH）最近提出了一种新系统，该系统可以自动生成针对稀疏数据进行了优化的代码。

我们生活在大数据时代，但是大多数数据都是“稀疏的”。例如，想象一下一个庞大的表，该表将所有亚马逊客户映射到其所有产品，给定客户购买的每种产品都为“ 1”，否则为“ 0”。该表将大部分为零。

对于稀疏数据，解析算法最终会进行大量的零加法和乘法运算，这浪费了计算量。程序员通过编写自定义代码来避免出现零输入来解决此问题，但是该代码很复杂，并且通常仅适用于范围很窄的问题。

新代码比现有的未优化软件包提供了100倍的加速。它的性能可与针对特定稀疏数据操作的精心手工优化的代码相媲美，而程序员的工作量则要少得多。

该系统称为Taco，用于张量代数编译器。用计算机科学的话来说，像Amazon表这样的数据结构称为“矩阵”，张量只是矩阵的高维类似物。如果该Amazon表还根据客户在Amazon网站上的产品评分以及他们的产品评论中使用的字词来映射客户和产品，则结果将是一个四维张量。

麻省理工学院电气工程和计算机科学教授（EECS）以及新论文的高级作者萨曼·阿玛拉辛格（Saman Amarasinghe）说：“稀疏表示已经存在了60多年了。”“但是没人知道如何自动为他们生成代码。人们会进行一些非常具体的操作-稀疏矩阵-矢量乘法，稀疏矩阵-矢量乘法加矢量，稀疏矩阵-矩阵乘法，稀疏矩阵-矩阵-矩阵乘法。我们做出的最大贡献是当矩阵稀疏时能够为任何张量-代数表达式生成代码的能力。”

论文的第一作者弗雷德里克·科斯塔德（Fredrik Kjolstad）是麻省理工学院EECS的研究生，他与本文中的阿马拉辛格（Amarasinghe）并驾齐驱。周星驰（Stephen Chou），也是EECS的研究生；法国替代能源和原子能委员会的David Lugato；和Adobe Research的Shoaib Kamil。

自定义内核

近年来，张量的数学操作（张量代数）不仅对大数据分析而且对于机器学习也变得至关重要。自爱因斯坦时代以来，它一直是科学研究的主要内容。

传统上，为了处理张量代数，数学软件将张量运算分解为它们的组成部分。因此，例如，如果计算需要将两个张量相乘然后加到第三个张量，则该软件将在前两个张量上运行其标准张量乘法例程，存储结果，然后运行其标准张量加法例程。

但是，在大数据时代，这种方法太耗时了。为了在海量数据集上高效运行，Kjolstad解释说，张量操作的每个序列都需要有自己的“内核”或计算模板。

“如果您在一个内核中执行此操作，则可以一次完成所有操作，并且可以使其运行得更快，而不必将输出存储在内存中然后再读回以便可以将其添加到其他内容中，乔尔斯塔德说。“您可以只在同一循环中进行操作。”

计算机科学研究人员已经为机器学习和大数据分析中最常见的一些张量运算开发了内核，例如Amarasinghe列举的那些。但是可能的内核数量是无限的：例如，用于将三个张量相加的内核不同于用于将四个张量相加的内核，并且用于添加三个三维张量的内核与用于添加三个四维张量的内核不同。

许多张量运算涉及将一个张量的条目与另一个张量的条目相乘。如果任一项为零，那么它们的乘积也为零，并且操纵大型稀疏矩阵的程序可能会浪费大量时间加和乘以零。

手工优化的稀疏张量代码可识别零项并简化涉及它们的操作-要么继续加法非零项，要么完全忽略乘法。这使张量操纵快得多，但是它要求程序员做更多的工作。

例如，如果矩阵已满，则用于将两个矩阵相乘的代码（一种简单的张量类型，仅具有两个维，例如表格）可能需要12行（如果矩阵已满，则意味着不能省略任何条目）。但是，如果矩阵是稀疏的，则相同的操作可能需要100行或更多的代码行来跟踪遗漏和省略。

输入塔可

Taco会自动添加所有这些额外的代码。程序员只需指定张量的大小（无论是完整的还是稀疏的），以及应该从中导入其值的文件的位置。对于在两个张量上的任何给定操作，Taco构建一个层次结构图，该图首先指示两个张量中的哪些成对条目为非零，然后指示每个张量中的哪些条目与零成对。它简单地丢弃所有成对的零。

Taco还使用有效的索引方案来仅存储稀疏张量的非零值。包括零项在内的亚马逊公开发布的张量，将客户ID号与购买量以及从评论中剔除的描述性条款进行映射，占用107 EB的数据，大约是所有Google服务器的估计存储容量的10倍。但是使用Taco压缩方案时，它仅占用13 GB的数据，足够小以适合智能手机。

俄亥俄州立大学计算机科学与工程学教授Saday Sadayappan说：“过去二十年来，许多研究小组都试图解决稀疏矩阵计算的编译器优化和代码生成问题，但进展甚微。”没有参与研究。“弗雷德和萨曼的最新发展代表了这个长期存在的开放问题的根本突破。”

他继续说：“他们的编译器现在使应用程序开发人员能够以非常容易和方便的高级表示法指定非常复杂的稀疏矩阵或张量计算，然后编译器会从中自动生成非常有效的代码。”“对于几种稀疏计算，已证明从编译器生成的代码与精心开发的手动实现具有可比性或更好。这有可能成为真正的游戏规则改变者。这是最近在编译器优化领域最激动人心的进步之一。”

PDF纸本副本：张量代数编译器