MIT推出并行计算编程语言Milk:为大数据应用提速

Synced (180).jpg


在今天的计算机芯片中,内存管理(memory management)是基于计算机科学家所称的局部性原理(principle of locality):如果一个程序需要存储在某个内存位置的一个数据块,它可能也会需要这个数据块附近的数据。


但这种假设在大数据的时代已被打破,现在的程序常常需要在许多巨大的数据集上任意离散的少量数据上进行操作。因为从它们的主内存区块中读取数据是今天芯片的主要性能瓶颈,所以不得不进行的更为频繁的读取会极大地减慢程序的执行。


本周,在并行架构和编译技术国际会议(International Conference on Parallel Architectures and Compilation Techniques)上,来自 MIT 计算机科学和人工智能实验室(CSAIL)的研究者展示了一种名为 Milk 的新型编程语言,该语言可让开发者在需要处理大型数据集中离散数据点的程序中更高效地管理内存。研究人员在一些常用算法上对该语言进行了测试,发现使用这种新语言编写的程序的速度可达到用已有语言所编写的程序的 4 倍。但研究者相信进一步的工作可以让其速度得到更大的提升。


电气工程和计算机科学教授 Saman Amarasinghe 说,今天的大数据集给已有的内存管理技术带来问题的原因不仅仅是因为它们很大,更多的则是因为它们是稀疏的(sparse)。也就是说,解决方案的规模并不总是与问题的规模成正比。


「在社会环境中,我们习惯了应对更小的问题。」Amarasinghe 说,「如果你看看这栋楼(CSAIL)里面的人,你能看到我们全部是互连的。但如果你从整个行星的规模上来看,我的朋友的数量也不会扩大规模。这颗行星上有几十亿人,但我的朋友仍然只有几百人。突然你就有了一个非常稀疏的问题。」


Amarasinghe 说,类似地,比如说有一个有 1000 位客户的在线书店,可能会为其访客提供 20 本最受欢迎的书的清单。然而,这并不意味着,如果这家在线书店的客户达到 100 万了,它就会为其访客提供 20,000 本最受欢迎的书的清单。


本地思考(Thinking locally)


今天的计算机芯片并没有为稀疏数据进行优化——其实事实情况正好相反。因为从芯片的主内存区块读取数据的速度很慢,所以现代芯片的内核或处理器中都有自己的「缓存(cache)」——一种相对小的、本地的且高速的内存区块。内核不会一次只从主内存中读取单个数据项,而是会一次读取一整个数据块。而这个数据块是通过局部性原理进行选择的。


局部性原理(principle of locality)的工作方式很容易理解。以图像处理任务为例:如果一个程序的目的是在图像上应用一种视觉滤镜(visual filter)而且一次只能处理图像上的一块,那么当内核请求一个块时,它应该就还会收到其缓存所能容纳的所有相邻的块,这样它就可以一块接一块地处理,而不需要再取更多数据。


但如果该算法的目标是从在线零售商数据库的 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 通过优化常见编程架构中的内存访问来帮助解决这一鸿沟。这项成果将关于内存控制器设计的详细知识和关于编译器的知识结合了起来,能为当前的硬件实现良好的优化。」

入门MIT大数据并行计算编程工程