比现有软件包快100倍！新型计算系统成编译优化领域重磅突破

年度订阅用户可加入科技英语学习社区，每周科技英语直播讲堂，详情查看“阅读原文”

张量计算从爱因斯坦时代起就是科学研究的重要内容。大数据时代，大数据和机器学习对稀疏张量（绝大多数元素为 0 的稀疏数组）的计算要求越来越高。

近日，MIT 的一款新系统可以自动生成针对稀疏张量计算等操作的代码，比当前常用的软件包快 100 倍，被誉为“近年来在编译优化领域最令人激动的进步之一”。

我们生活在一个大数据的时代，但是绝大多数的数据都是“稀疏的”。想象一下，比如说，一个超大规模的表格，它存储着所有的亚马逊的顾客和所有商品的对应信息，如果一个顾客购买了某样商品，就存储一个“1”，否则为“0”。那么这个表格的绝大部分数据都会是 0。

面对这样稀疏的数据，分析算法最终要做大量有 0 参与的加法和乘法，这是对计算资源的一种浪费。

程序员可以通过编写特定的代码来躲开零实体来规避这样的问题，但是那样的代码是复杂的，而且只对非常有限的问题有效。

在 ACM 的 SPLASH（Systems, Programming, Languages and Applications: Software for Humanity）会议上，来自 MIT、法国的替代能源和原子能委员会和 Adobe Research 的研究者最近推出了一个新的系统，它可以自动产生针对稀疏数据的优化的代码。

这样的代码比现存的未优化的软件包快 100 倍。而且其性能可以与那些为特定稀疏数据操作而手动精心优化过的代码相媲美，却只需要程序编写者做极少的工作。

这个用于稀疏代数编译器的系统叫做 Taco。根据计算机科学界的说法，一个像上文提到的，亚马逊表格那样的数据结构称作矩阵，而一个张量仅仅是一个更高维的类似的东西。如果前面提到的亚马逊的表格也保存着客户、对应的商品、客户对商品的评级以及评论中使用到的词语，那么它将会是一个四维的张量。

“稀疏表示已经存在了超过 60 年”，MIT 电气工程与计算科学的教授，新论文的主要作者 Saman Amarasinghe 说道，“但是没有人知道如何为它们自动生成代码。人们想到一些非常具体的操作——稀疏矩阵与向量相乘，稀疏矩阵与向量相乘再加上一个向量，稀疏矩阵与稀疏矩阵相乘，稀疏矩阵与稀疏矩阵相乘再与稀疏矩阵相乘。我们所做的最大的贡献就是实现了，当矩阵是稀疏的时候，可以为任何张量代数表达式自动生成代码的能力。”

自定义核

近年来，对张量的数学操作——张量代数——对大数据分析和机器学习都变得至关重要。其实，从爱因斯坦时代起，它就成为科学研究中至关重要的部分。

在此之前，为了解决张量代数问题，数学软件已经将张量操作分解成它们的组成部分。比如说，如果一个计算需要将两个张量相乘然后再与第三个相加，软件将会在前两个张量上执行标准张量乘法操作，存储结果，然后执行标准张量相加操作。

然而，在大数据时代，这个方法太费时间了。Kjolstad 解释道，为了在数量庞大的数据集上执行高效的操作，张量的每个序列都需要它自己的“核”，或者说是计算模板。

“如果你在一个核中操作，你就能把所有操作一次完成，并且你可以让它执行的更快一点，而不需要先将结果保存到内存中然后再把它读回来以便和其他的东西相加”。Kjolstad 说，“你可以在一个循环中完成它。”

计算机科学的研究者已经研制出针对机器学习和大数据分析中常见张量操作的核，比如说上文中 Amarasinghe 列举的。但是这些可能需要的核的数量是无限的：比如说，将三个张量相加的核和将四个张量相加的核是不一样的。而将三个三维张量相加的核和将三个四维张量相加的核也是不一样的。

许多张量操作包括将来自一个张量的一个实体和来自另一个张量的一个实体相乘的操作。如果这两个实体都是 0，那么他们的结果也是 0。而操纵庞大而稀疏的矩阵的程序就会浪费大量的时间来对 0 进行加和乘操作。

为稀疏张量手动优化的代码识别出零实体并精简包含他们的操作——在加法中只关注非零的实体并完全省略零实体参与的乘法。这使得张量操作更快，但是需要程序编写者做大量的工作。

比如说，将两个矩阵相乘的代码，如果矩阵是稠密的（没有实体可以被省略）可能只有 12 行。但是如果矩阵是稀松的，相同的操作可能需要 100 行或者更多的代码来去处理应该被省略的部分。

引入 Taco

Taco 完全自动地添加额外的代码。编程者只需要指定张量的大小，是稀疏的还是稠密的，以及存储它的值的文件即可。对任何针对两个张量的操作，Taco 建立一个分层的映射地图指出，首先，两个张量哪一对相对的实体是非零的，其次，两个张量中哪个实体和零配对。而所有 0 与 0 的配对将被直接遗弃。

Taco 也使用一个高效的索引方案去存储稀疏张量的非零值。如果包含 0 值，一个亚马逊公开发布的，存储客户 ID、对应购买物品和从评论中提取的描述词语的张量，会占用 107 亿字节的数据，或者大说，约是估计出的的所有的谷歌服务器存储容量 10 倍。而使用 Taco 的压缩方案，它只占用 13 千兆字节，用一个智能手机就足够存储。

“在过去的二十年中，许多研究小组一直在尝试解决稀疏矩阵的编译优化和代码自动生成问题，但是收效甚微。”俄亥俄州立大学计算机科学和工程的教授 Saday Sadayappan 说道，“最近 Fred 和 Saman 取得的进展代表着在这一长期存在的问题上根本性的突破”，他并没有参与这项工作。

“他们的编译器通过自动生成高效的代码，现在已经可以让应用程序的开发者用非常简单，方便的高级符号来指定复杂的稀疏矩阵和张量计算”。他继续说道，“对一些稀疏计算，编译器生成的代码已经和手动精心改进的一样好甚至更好。它有望成为真正的游戏规则改变者，它是近年来在编译优化领域最令人激动的进步之一。”

-End-

编辑：王维莹 校审：黄珊

参考：

https://phys.org/news/2017-10-tensor-algebra-fold-speedups-previous.html