MIT最新发布编程语言Milk，加速大数据时代并行运算

在当下的计算机芯片中，内存管理是基于计算机科学家所称的局部性原理（principle of locality）来实现的：

如果一个程序需要某个内存位置的数据块，它可能也需要数据块临近位置的数据。

但是在大数据时代，这种假设已不再成立。如今的计算机程序更多地是在大型数据集中离散地获取一点点数据。由于从主要内存位中获取数据已成了当下芯片的最大性能瓶颈，所以不得不更加频繁地获取数据，这也明显拖慢了程序运行的速度。

本周在国际并行体系结构和编译技术会议（International Conference on Parallel Architectures and Compilation Techniques）上，来自麻省理工学院计算机科学与人工智能实验室（CSAIL）的研究人员发布了一种新的编程语言——Milk，它能让应用程序开发者在处理大数据集里的离散数据点问题中更有效率地管理内存。

通过测试几种通用的算法，使用新语言Milk编写的程序实现了比现有编程语言快4倍的速度。但是研究者相信通过更进一步的研究可以实现更好地结果。

电气工程和计算机科学教授Saman Amarasinghe 说，当下大数据集给已有的内存管理技术带来问题的原因不仅在于因为它们的规模巨大，更多的是因为它们是稀疏的（sparse）。也就是说，问题解决方案的规模并不一定是与问题的规模成正比增加。

“在社交环境中，我们通常倾向于注重更小的问题。” Amarasinghe说“如果你只关注在这种建筑[CSAIL]内的人的话，你能发现我们都是朋友的。但是如果你以地球的层面来看待的话，朋友的数量并不会增加。整个地球有几十亿人口，但是我也仅仅只有几百个朋友。这就是一个很明显的稀疏性问题。”

同样Amarasinghe提到，一个在线书店可能为其1000名顾客提供最流行的20本书籍的书单。但是但其顾客数增加到100万时，它并不会相应地提供最流行的20000本书籍的书单。

局部思考（Thinking locally）

当下的计算机芯片并没有专门针对稀疏数据进行优化，而且可以说是完全相反。因为从芯片的主要内存位读取数据是缓慢的，当下的芯片中每个内核或者每个处理器都有自己的“缓存”，一个相关的小型、本地、高速的内存位。芯片中的内核会一次读取一个完整的数据块，而不是在主内存中每次提取一个单独的数据。而读取的数据块是通过局部性原理来进行选择的。

通过图像处理的例子可以很容易看清局部性原理的本质：

如果一个程序的目的是将视觉过滤器应用到图像中，且它每次只作用在图像的一个数据块上。那么每次芯片内核请求一个区块数据时，它应该收到自身缓存能接受的所有临近区块数据。因此它可以一个一个区块处理，且不再获取更多的数据。

但是如果该算法的兴趣是在线书店200万数据库中的20本书的话，该方式将不再适用。如果它请求与某一本书相邻的数据，很有可能其相邻的100种书的数据都是没有关联的。

从主内存中每次只读取一个数据是非常低效的，这篇论文的第一作者Vladimir Kiriansky 提到

就像是每次你想要一勺食品时，你都需要打开冰箱、打开牛奶盒、倒出一勺牛奶、盖上牛奶盒、将它放回冰箱。

他是电气工程和计算机科学的博士生。Amarasinghe 和 Yunming Zhang 是他的论文合作者，Zhang 也是一位电气工程和计算机科学的博士生。

批处理（Batch processing）

Milk简单地增加了一些命令到OpenMP中。其中OpenMP 是一种能够用在C或Fortran等语言中的扩展，可以用来更轻松地为多核处理器编写代码。使用Milk的话，程序员可以在任何指令附近插入几行代码，其可以在整个大数据集中进行迭代，寻找相对较少数量的项。Milk 的编译器（将高级代码转换成低级指令的程序）可以据此找到管理内存的方法。

使用 Milk 程序时，如果一个内核发现它需要一项数据时，它并不会请求从主内存中读取它（以及相邻的数据）。它会将该数据的地址添加到一个本地存储的地址列表中。当这个列表足够长时

芯片所有内核将会池化（pool）它们的列表

将这些地址按临近排布的形式组合到一起

重新分配给内核

这样一来，每个内核都只请求了自己所需要的数据项，并且可以有效地进行检索。

这样描述的话层级较高，但实际上细节会复杂得多。事实上大部分现代计算机芯片都有多级缓存，且一级比一级大（但效率也因此更低）。Milk编译器不仅必须跟踪内存地址表，还要跟踪这些地址中存储的数据，而且它常常将这两者在各级缓存之间进行切换。它也必须决定哪些地址应当被保留（可能需要再次访问），哪些应当被丢弃。研究学者希望能够进一步提升这种编排复杂数据的算法，从而进一步提升性能表现。

「当下许多重要的应用都是数据密集型的，但不幸的是，内存和CPU之间的性能差距越来越大，这意味着当前的硬件还没有发挥出它们的全部潜力。」斯坦福大学计算机科学助理教授 Matei Zaharia 说，「Milk 通过优化常见编程架构中的内存访问来帮助解决这一差距。这项成果结合了内存控制器设计的详细知识和相关编译器的知识，能为当前的硬件实现良好的优化。」

本文转自d1net（转载）