数据压缩算法:对于程序员来说,这项新技术特别实用

雷锋网注:【 图片来源: MIT CSAIL 所有者:MIT CSAIL 】

数据压缩技术之一,就是通过消除冗余来释放存储容量,提高计算速度,或是带来其他好处。

但是,在目前的计算机系统中,访问主存的成本很大。因此,在存储器中使用数据压缩技术有助于减少提取数据的频率和数量,提高设备的性能。

一般来说,现代设备以固定大小的块(chunk)来进行管理和传输数据,传统的压缩技术必须在这些块上运行。然而,软件存储数据并不使用固定大小的块,而是使用对象(object),这种数据结构可以容纳各种类型的数据,它的规模的也可大可小。

因此,传统的数据压缩技术很难处理对象。

首次亮相

本周ACM国际编程语言和操作系统架构支持会议上发表的一篇论文中,MIT的研究人员描述了第一种“跨存储层次压缩对象”的技术。这种技术可以降低内存使用率,同时也可以提高性能和效率。

研究人员用改进后的Java虚拟机做了实验,结果表明,与传统压缩方法相比,这种新技术可以多压缩两倍的数据,还减少了一半的内存使用率。

CSAIL的研究生Po-An Tsai是这篇论文的第一作者,她表示,“我们试图提出一种新的存储层次结构,能够进行对象压缩,因为大部分现代编程语言都是以对象的形式管理数据的。”

合著者Daniel Sanchez是计算机科学和电子工程专业的教授,同时也是CSAIL的研究员,他补充道,“所有计算机系统都将从这项新技术中受益,程序的运行将变得更快,因为不再受制于内存带宽。”

由于Java、Python和Go这些现代编程语言以对象的形式管理数据,所以对于程序员来说,这项新技术特别实用。在不久的将来,我们就会看到设备拥有更快的速度,或者能在同一时间运行更多应用程序。

存在局限

传统的结构以块的形式将数据存储到缓存存储器(Cache)中,最近受访的块会上升到这里(上图黄色层),虽然这里空间小,但访问速度快。而旧块则会下降,最终回到主存(上图蓝色层)中。

虽然这种数据之间的调动十分灵活,但成本也不低。

在数据调动的过程中,如果目标数据不再Cache中,Cache就要访问主存,并大范围搜索数据的地址。入下图所示,Cache访问主存并返回的时间大约是100~300个周期。耗时太长,存在局限性。

推陈出新

Sanchez发现了传统模式的局限性,他思考着,“既然现代编程语言中数据管理的单位是对象,那我们为什么不建一个处理对象的存储层次结构呢?”

于是,研究人员在之前的传统存储层次结构上进行改进,便于直接处理对象。

1.Hotpad/pad

在去年10月发表的一篇论文中,研究人员详细介绍了一个名为Hotpad的系统,可以用来存储对象。由于这个系统的各个层次之间关系紧密,也可称为pad。

这整个结构基于一个芯片存储器,效率高且不需要进行复杂的搜索,因为程序可以直接引用整个pad所有对象的位置。新分配的,或最近引用的对象,以及它们指向的对象,都停留在速度最快的层次,以便快速访问。

当这个层被填满时,系统就会开始“筛查”。筛查的过程会保留最近引用的对象,但较旧的对象会被下放到较慢的层,除此之外,系统还会删除不再有用的对象,以释放空间。随后,每个对象的指针都会更新,指向新对象的位置。通过这种方式,程序访问对象的成本比通过缓存层来搜索要低得多。

2.Zippad

研究人员还设计了一种名为Zippad的技术,利用Hotpad系统来压缩对象。当对象第一次在较快的层次启动时,它们会被解压,但当它们被下放时又会被压缩。另一方面,跨级别的所有对象都指向那些压缩的对象,这使得它们很容易恢复到更快的级别,并且比传统技术下存储得更紧凑。

3.基础对象

与以前的技术相比,这种新技术还提供了更多的压缩机会,因为以前的技术仅限于在固定大小的块中查找冗余。首先,该算法会选取几个具有代表性的对象作为基础对象。然后,只要有新对象加入,算法就会对比基础对象和新对象,然后把它们的之间不同的数据存储起来。

卡耐基梅隆大学电子和计算机工程助教Brandon Lucia十分赞赏这个新技术,因为它利用编程语言的特性,更好地进行压缩工作。他说:“这项工作的有趣之处在于,它利用对象的抽象性让内存压缩更有效,从而使系统更快、更高效,具有新的计算机体系结构特性。”

雷锋网注:本文编译自 MIT CSAIL ,部分内容来自网络,由雷锋网 (公众号:雷锋网) 整合

雷锋网版权文章,未经授权禁止转载。详情见 转载须知

我来评几句
登录后评论

已发表评论数()

相关站点

+订阅
热门文章