研究人员设计了一种新型编程语言,让应用程序开发人员更加高效地管理程序使用的内存。这些程序通常用于处理大数据集合中的散乱数据点。使用新型编程语言编写的程序,经几种普通算法的测试,速度是现有编程语言的4倍。

(图片来源于: Christine Daniloff/MIT)


引言

如今的计算机体系结构中,内存管理基于“局部性原理”。但是,随着大数据时代到来,局部性原理不能应对“稀疏数据”问题,所以MIT研究人员发明了新编程语言Milk。

局部性原理

在如今的计算机芯片体系结构中,内存管理基于一条原则,计算机科学家所称之为“局部性原理”:CPU访问存储器时,无论是存取指令还是存取数据,所访问的存储单元都趋于聚集在一个较小的连续区域中。所以,如果程序需要某些内存位置的数据块,它也同样需要相邻的数据块。


局部性原理的工作方式很简单。比如说图像处理,如果程序是给图片应用视觉过滤器,它每次处理图片的一块数据。当内核请求一个数据块,它应该接受缓存可以处理的所有相邻数据块,所以它可以访问连续访问这些数据块,而无须再次获取内存数据。


大数据对于局部性原理的冲击

不过在大数据年代,这条假设被打破了。现在,计算机程序更加频繁地访问大数据集中随意分散的几个数据项。因为从主存储器获取数据是当代芯片主要性能瓶颈,所以更加频繁地访问数据,会动态地降低程序执行效率。


大数据带来的“数据稀疏”问题


电气工程和计算机科学系教授Saman Amarasinghe认为,如今的大数据集为现有的内存管理技术带来一些问题,因为数量很大,专业说法叫“稀疏”。在大数据的条件下,解决方案的规模并不需要随着问题的规模而增加。

“在社交设置中,我们通常习惯于看到更小的问题,”Amarasinghe说,“如果你观察在CSAIL建筑中的人们,我们都是相互熟悉的。但是,如果你以行星的规模观察,我不能轻易的找到我的朋友。地球上具有几十亿人口,但是我只有几百个朋友。突然,你遇到了一个十分稀疏的问题。”同样,Amarasinghe说,一个拥有1千客户的在线书商,可能要向访问者提供20本最流行的书籍。但是这并不代表,一个有百万客户的在线书商,想要给顾客提供2万本最流行的书籍。


如今的计算机芯片,并没有为稀疏数据而进行优化。事实上,情况恰恰相反。因为,从芯片的主存储器获取数据很慢,现代芯片中每个内核或者处理器,都有自己的“缓存”,一种相对较小,本地,高速的内存块。所以,内核并不是每次都从主存储器中获取单个数据项,而是将获取整块数据。同时,数据块通过局部性原理选择。

但是局部性原理的方案并不是所有情况下都可行的,比如说,算法只对在线书商200万数据规模的数据库中20本书感兴趣。如果,它请求和一本书相关的数据,很可相邻的100本数据中的数据都是不相干的。

新编程语言Milk诞生

在这周的并行体系结构和编译技术的国际会议上,MIT计算机科学和人工智能实验室(CSAIL)的研究人员,展示一种称为“Milk”的新编程语言,让应用程序开发人员更加高效地管理内存,以处理大数据集中的散乱数据点。

使用新型编程语言编写的程序,经过几种普通算法的测试,速度是现有编程语言的4倍。但是研究人员相信,未来的研究会带来更大的成果。

Milk的原理和工作方式介绍

Milk,在OpenMP中加入了一些指令。OpenMP是支持的编程语言包括C和Fortran,更加方便地为多内核处理器编写代码。通过Milk,程序员可以在任何指令周围加入几行额外的代码,用于遍历一个大数据系,寻找相对少量的数据项。Milk编译器,将高级语言转化成低级指令,然后搞清楚如何相应地管理内存

通过Milk程序,当一个内核发现它需要一片数据,它并不去内存请求相关的相邻数据。相反,它将数据项的地址增加到本地存储地址的列表中。当列表足够长的时候,所有芯片内核查询列表,将这些相邻的地址放在一起成为一组,并且重新分配给内核。这样,每个内核只请求它需要的数据项,也方便高效检索数据项。

上面是对于Milk的高级描述,但是细节却是更复杂。事实上,大多数的现代计算机芯片具有不同级别的缓存,缓存越大的效率也略低。Milk编译器必须不仅追踪内存地址列表,也包括存储在这些地址的数据。它经常在不同级别的缓存上重新整理这些。它也必须决定哪个地址能够被保留,因为他们必须被重新访问,并且哪个需要丢弃。未来,研究人员希望提高处理这些数据的算法,以提高程序性能。

研究意义

斯坦福大学计算机科学专业的助理教授Matei Zaharia认为,如今许多重要的应用都是数据密集型的,但是不幸地是,CPU和内存之间的性能间隙越来越大,这样无法有效的利用目前的硬件。Milk帮助减小这种间隙,通过优化通用内存结构中的内存访问。这项研究将内存控制器设计的具体知识和编译器的知识相结合,从而优化目前的硬件。

参考资料

【1】http://news.mit.edu/2016/faster-parallel-computing-big-data-0913


新编程语言Milk:更加快速高效处理大数据问题
Tagged on: