嵌入式系统中的内存压缩技术(2)

压缩内存控制器必须根据长度格式的不同将系统总线上的实际地址翻译成物理内存的中的物理地址。实际地址是出现在处理器外部总线上常规地址。篁 址用来录十压缩内存的256字节区域。实际地址空间存在于L1/L2/L3高速缓冲中，用于立即访问。而其余的内存内容部分以压缩形式存在于物理内存中。内存控制器通过查询压缩翻译表（CTT）执行从实际地址到物理地址的翻译，这个表被保留在物理内存的某个位置。图2是CTT表的格式及内存控制器的寻址模式。

每个1KB内存块的实际地址映射到CTT的一项，而CTT每项共16字节，包括四个物理区域地址，每个地址指向物理内存听一个256字节区域。对于少于120位的块，如一个全为零的块，则使用一种特殊的CTT格式，称为通用行格式。在这种格式中，压缩数据全部存放在CTT项中，代替了四个地址指针。因此，一个1KB的通用块仅占用物理内存中的16字节，其压缩比率达到64：1。

压缩内存控制器中有一系列的寄存器用于监控物理内存使用。Sectors Used Register(SUR)向操作系统报告压缩内存的使用情况。The Sectors Used Threshold Registers,SUTHR和SUTLR，用于设置内存耗尽情况的中断入口点。SUTLR寄存器是PCI中断电路INTA的入口，而SUTHR寄存器是NMI中断的入口。当SUR超过了SUTLR的值，内存控制器产生一个中断，则操作系统采取措施来阻止内存消耗。

在实际地址到物理地址的转换中，一个有用的方法是快速页操作。它允许控制器仅修改CTT项的四个指针，从而将4KB的页面内容换出或清空。快速页操作通过将与4KB页面相关的CTT项全部修改通用行格式（即全为零），从而将这4KB页面的内容全部清空。同样，一对页面可以通过交换它们相关的CTT项的区域指针来交换页面内容。由于没有大量的数据移动发生，快速页面操作速度相当快。

压缩内存控制器的压缩/解压功能是基于LempelZiv算法来进行的，因此下一节将简单介绍一下该算法的思想。

3 内存压缩算法Lempel-Ziv

绝大多数的压缩算法，包括用得特别流行的Lempel-Ziv压缩算法家庭，都是基于对原子记录（Token）字符串的完全重复检测。这个算法虽然不是最好的算法，但是，Lempel-Ziv算法强调的是算法的简单与取得高压缩率的速率，因此它还是在内存压缩中得到了广泛的应用。

Lemple-