黎明灰烬 博客 +

Transmeta CMS:采用推断、恢复和可适性重翻译解决实际问题

review on The Transmeta Code Morphing™ Software: using speculation, recovery, and adaptive retranslation to address real-life challenges.

Abstract

Transmeta 将基于 VLIW 的处理器 Crusoe 和软件层 Code Morphing Software (CMS) 深入结合,构造了一个系统级的 X86 兼容系统。CMS 包含诸多功能:解释器、翻译器、优化器和运行时系统。CMS 和很多其他的二进制翻译软件类似,又有很多独特之处。在构造过程中,CMS 解决了很多其他类似软件没有处理过的,模拟现实 PC 所面临的问题,如例外(又称「异常」)、终端、IO、DMA、自修改代码等。本文将主要讨论 Crusoe 和 CMS 在解决这些问题时采用的——激进的推测范例、基于「提交-回滚」硬件支持的一致性 x86 状态恢复、解释执行频繁例外代码的可适性重翻译。

引言

Transmeta 的 Crusoe 处理器和 CMS 构造了一种独特的商用体系结构——「内部 ISA」和「外部 ISA」截然不同。由于内部 ISA 不公开给用户,因此可以在每一代产品升级时自由地升级,而外部 ISA (x86) 则是一种通用的兼容传统软件的 ISA 。这种架构使得处理器设计可以变得简单紧凑低功耗。为了提供稳定的具有竞争性的商业产品级别的性能和兼容性,CMS 要解决在传统的二进制翻译和动态优化中被忽略的话题:

Crusoe 和 CMS

Crusoe 内容可参考另一篇文章,这里不再赘述。值得注意的是,每一代 Crusoe 处理器都真正的在「内部 ISA」层面进行了升级,如 TM5000 增加了 x86 段、16bit 操作、间接跳转等支持。

CMS 的大体结构和其他动态翻译系统都是先解释后执行。不过,CMS 谨慎地处理了访存顺序、精确错误重现。CMS 最复杂的模块是翻译器,要解决 x86 指令译码、翻译域(region)筛选、域内数据流和控制流分析、翻译的优化和代码调度。翻译器的设计要权衡代价和性能,而 CMS 还包含一个用户处理设备、终端、例外、功耗管理、垃圾收集的运行时。

cms control flow

推断、恢复、可适性的重翻译

和 Intel IA-32 EL 类似,Transmeta CMS 的翻译器采用了推断设计来减少翻译后代码的规模(CMS 应当更早一些,不过论文是同一年刊出的)。这种推断主要基于对程序行为的观察,比如几条访存指令的地址是否是相互覆盖的。推断始终是推断,当推断在运行时被打破时,CMS 要有特殊的「推断例外」处理机制。

作为协同设计虚拟机(Co-Design Virtual Machind),当推某些特殊类型的推断例外发生时,Crusoe 处理器将例外信息传递给 CMS。CMS 可以像常规操作系统处理例外那样处理推断例外。对于不常见的例外,CMS 用解释器来处理。解释器虽然拥有指令级的精确状态,但性能还是比较低。当这种不常见例外也经常发生时,CMS 会进入「保守翻译」状态,为这部分代码生成更小的 region 但状态更精确的执行翻译。

Crusoe 的硬件支持使得 CMS 的速度更快,但 CMS 的重翻译机制还是面临一系列挑战。首先,CMS 要在不过度约束翻译后代码调度的前提下精确重现 x86 例外。其次,当系统要求一致的目标机器状态时,CMS 要响应精确到指令级别的中断。再次,CMS 要高效地处理内存映射 IO 等系统级操作,又不能降低常规存储器引用的性能。最后,CMS 还要跑支持游戏这样的传统 PC 软件经常有性能敏感的子修改代码,Windows/9X 驱动常常包含代码数据混合的页,BIOS 和 QNX 这样的实时操作系统。

下面将详细介绍 CMS 的机制,其中部分数据在 TM5800 系统上收集,其他的则用 Crusoe 模拟器收集。

【私货】如曾经提到过的,Transmeta 将 VLIW 处理和动态优化技术的整合,CMS 可以实现激进的指令重排,完全打破了原始程序的执行流。不仅如此,CMS 和传统二进制翻译器或动态优化器最大的区别在于,其底层处理器对其暴露的「内部 ISA」使得 CMS 可以实现由其自身维护的,类似于现代体系结构设计中「多发射」和「动态流水线」的功能。正是这种软硬件功能的分工,使得低功耗高性能的处理器平台成为可能。而这种设计给错误恢复带来了更大的挑战,因为 VLIW 中具体是哪一条 atom 指令发生了错误,需要进一步精确定位。此时,Transmeta 的工程师们又为 Crusoe/CMS 系统增加了额外的专门用于提高错误定位精确性和性能的硬件支持。

推断和恢复的硬件支持

编译器对代码的动态调度也依赖于推断,往往需要增加额外的用于错误恢复的「补偿」代码。采用这种设计后,需要将潜在的错误指令调度到(错误检测)分支之前。Crusoe 处理器提供了「提交」(commit) 操作机制来支持精确的机器状态。主要包括影子寄存器(shadowed register)和存储闸门缓冲(gated store buffer)。

Crusoe 的寄存器有两份拷贝——活动寄存器和影子寄存器。影子寄存器中保存的是上一个提交点(通常是 region 结束时)时活动寄存器的数据。当本次(region)执行没有发生错误时,才将活动寄存器拷贝到影子寄存器中,然后继续执行。这种拷贝过程称作提交(commit)。当错误发生时,CMS 启动回滚(rollback)操作,从影子寄存器中恢复数据,进入解释器精确执行(如有必要会启动 x86 软件的例外处理机制)。

数据都直接写入存储闸门缓冲,在提交时才真正同步到存储系统。如果错误发生,回滚时直接放弃存储闸门缓存的数据。Crusoe 经过精心设计,提交操作几乎没有任何开销,而回滚操作的开销不过和分支预测失败相当。

精确例外

精确例外由 Crusoe 的硬件支持和 CMS 的可适性重翻译共同达成。

对于 x86 这样精确例外且有序执行的 ISA 而言,纯软件模拟的代价是极高的:不能采用激进的翻译策略,要插入大量的「错误恢复」代码,即使不发生例外开销也比较高。不过有了「提交-回滚」硬件支持,CMS 可以非常灵活地调度翻译后代码。CMS 像传统控制推动那样记录信息,也无需生成大量的补偿代码,就能随意调度指令,甚至是分支指令。

由于指令调度,当处理器报告发生了例外时,存在两种情况——原始指令触发的例外和由指令调度引发的例外。CMS 只需要用解释器再次执行这段代码就能鉴别出是那种例外。如果是指令调度例外,且频度很低,CMS 可以直接忽略它(直接解释执行,不做特殊处理)。

对于频繁例外,CMS 根据例外的原因分情况处理。对于原始指令例外,CMS 不断减小该段代码的翻译规模,从而减少回滚的代价,同时其他部分指令依然可以是高度优化的。当例外持续发生,这跟过程持续迭代,最后,代码翻译会以例外指令为分界,而例外指令由解释器执行。对于推断引起的例外,CMS 在减小 region 的同时会采用较为保守的翻译策略(减少指令调度、生成补偿代码),这样例外会大大减少。CMS 会持续监测这类例外,为代码翻译采用恰当的翻译策略。

中断

「提交-回滚」的目的和中断类似。但中断不触发可适性重翻译,因为当中断发生时它们往往和翻译没有直接关系。

内存映射 IO

Crusoe 系统的目标是允许各种 x86 代码,包括系统和应用。和物理设备进行底层交互的一个原则是指令必须按照 x86 原始顺序执行,因为外部设备的状态是不可恢复的(无法使用「提交-回滚」策略)。

在 x86 架构中,有两种方法访问设备:in/out 这类显式指令、内存映射访问。前者在翻译阶段就可以轻易识别,而后者即使是在翻译阶段也无法和常规访存行为区分。应用往往不会特别关注访存指令访问的是设备还是内存。禁用内存指令重排的代价非常之高。如下图所示,系统级别从 5% 到 25% 都有,应用的性能损失就更大了。

mem-reorder

为了解决这一问题,Crusoe 处理器的访存指令带有,能分辨该指令是否经过了指令重排的标记。当这样的指令访问了一个映射了 IO 设备的内存页时,Crusoe 会触发例外。CMS 对这类例外启动「提交-回滚」及可适性重翻译机制。

数据推断

对于内存访问而言,翻译器无法检查访存地址是否重叠,这对指令重排也是一大挑战。基于经验,我们可以说:如果程序没有明显的地址重叠,那么重叠往往不会发生,所以指令重排是比较安全的。Crusoe 的「硬件别名」即使让 CMS 可以重排指定的内存引用,由硬件检查地址是否重叠。如果重叠发生,CMS 将使用「提交-回滚」及可适性重翻译机制。下图是相关的测试结果。

alias-hardware

Crusoe 比其他的要在乱序执行中确保内存约束的处理器简单得多,也比内存冲突缓冲(memory conflic buffer)或 IA-64 ALAT 简单。这些处理器往往要使用带有全相联的硬件机制来检查乱序指令是否重写了某个被保护的地址。在本套系统中,CMS 的翻译器负责处理这种问题。

自修改代码

自修改代码处理一直是二进制翻译的一大难题,因为要维护翻译缓冲和原始代码的一致性。CMS 现有的策略是假设原始代码不变,这种略显「奇怪」的假设就很有意思了……CMS 早期处理自修改代码就是简单的以页为粒度的写保护,当发生页错误时,丢弃所有受影响的翻译缓存。但页毕竟还是太粗放了,很难处理代码数据混合的页,这种方法的性能非常低,无法满足游戏类的图形性能需求(虽然采用现代编程技术后,这类问题变少了)。自修改代码主要有两点开销:对写保护的处理和无效掉相关的翻译缓存、重新翻译该页。本节介绍 CMS 的处理机制。

细粒度保护

Crusoe 处理器以小余页大小的粒度施行写保护。它基于这样的一个事实——在某段时间内只有有限的几个页需要这种细粒度保护。Crusoe 处理器内部有一个缓存用于记录需要保护的地址域,而 CMS 负责记录所有的保护和及时更新该缓存。这种机制的工作方式和 TLB/Cache 类似。同时,当 DMA 操作会无效掉所有被写数据的处于保护状态的页相关的翻译代码,从而避免多余的执行检测处理。如下表所示,这种技术大大减少了在处理自修改代码时,发生相关写保护的情形。

fine-grain-protect

自重验翻译

CMS 在遇到数据代码混合段的写操作时,可以在翻译代码执行前插入「序言」( prologue) 来降低自修改代码带来的开销。序言用于临时的代码监测,可以随时启用/关闭而不影响翻译后代码(只是修改块间跳转)。这种技术称为「自重验翻译」,主要是为了减少自修改代码被重新翻译的频度,从而提高系统性能。

CMS 为潜在的代码数据混合的自修改代码打上标记,下次遇到时将其重新翻译,从而能够捕获 x86 代码。之后,如果细粒错误处理认为翻译后代码可能受到了影响,它会启用序言、关闭写保护(避免二次开销)。当翻译后代码被执行时,序言检查翻译后代码对应的 x86 代码是否发生了变化,重启保护、重验 x86 代码、关闭序言,再执行翻译后代码。(这个过程很绕,没看懂……)

这种技术不消除写操作引发的保护错误。由于每次写操作和翻译后代码执行最多只有一次错误处理和检查,如果写操作相比翻译后代码执行频率较低,性能还是很可观的。采用这种技术后 Quake Demo2 的帧率提高了 28%。然而如果保护错误太频繁,错误处理和检测的开销就比较高了,因为重验至少和执行翻译代码开销相似。并且,它不适用于翻译后代码修改自身对应的 x86 代码的情况,因为此时序言已经结束了,会触发新的保护错误。

自检查翻译

另一种解决自修改代码的技术是自检查翻译——在翻译后代码中插入检查 x86 代码是否被修改过的指令(计算内存区域特征值?)。自检查翻译可以融合到常规翻译中,当检查失败时回滚即可。不过这种检查对代码调度有一定的约束,所有存储操作之后都必须立即检查,并且要包含存储操作以及同一控制流路径上的操作。所幸 Crusoe 的硬件别名消除了这种约束。自检查翻译单次检查的开销要比自重验翻译低很多,但如果执行次数增大,它就没有什么优势了。

测试表明,自检查翻译会增加约 83%(58~ 100%) 的代码体积,执行的的 VLIW 指令多大约 51%(11~124%),开销太大。尽管这比重翻译要块,但长期运行还是远不如可适性翻译。

程式化的自修改代码

以上技术的优化效果只有在代码没有真正被修改(修改的是同一页的数据)时才会生效。自重验翻译和自检查翻译主要是为了解决当代码真正被修改过的情况。

很多 PC 应用使用自修改代码的方法比较程式化,例如一个外部循环在内部循环开始前修改某个立即数或偏移值。这种情况下,代码逻辑没有变化,只要修改翻译后代码对应的数据,无需重新翻译。这种推断技术必须和自重验翻译和自检查翻译同时使用,以确保代码裸机没有真正变化。

翻译后代码组

某些情况下,自修改代码被修改成几个有限的重复出现的版本。CMS 能识别这种特性,将一段 x86 地址域的翻译后代码组织成翻译后代码组(translation groups)。结合自检查翻译,只有在代码组中都找不到匹配的翻译后代码时才真正重新翻译。

REVIEW

几乎同时期的 X86 二进制翻译器 CMS 和 IA32 EL 都致力于解决大量的现实的应用问题,尽管他们的目的差异很大。CMS 采用的协同设计方法大大简化了处理器设计,而且使其具有很高的灵活性。Crusoe 提供的几种特殊的硬件支持又使得 CMS 可以极大地降低 ISA 模拟开销,很多在其他系统中极端难以解决且开销极大的问题在这里却「轻而易举」。在这种情况下,CMS 可以将精力放在其独特的可适性翻译器和自修改代码处理上。可适性翻译高效地解决了精确例外、终端等问题,并且其性能是动态收敛的。自修改代码处理机制极为复杂,细粒度等策略应该能有效地提振二进制翻译器中原本低下的自修改代码性能。实在是了不起的设计。

不过值得注意的是,这篇文章着重介绍单个方法的性能,并没有给出相似处理器频率下全系统 x86 模拟与真实 x86 处理器的性能对比数据。或许,没有达到他们的商业目标吧……

黎明灰烬 博客

Creative Commons License 信箱:i(at)jackwish.net

计算机

清 谈