Loongson Instruction Set Architecture Technology
-
摘要:
介绍了统筹考虑先进性和兼容性要求的龙芯指令系统架构——龙架构(LoongArch). LoongArch吸纳了近年来指令系统设计领域诸多先进的技术发展成果，易于高性能低功耗的实现和编译优化;融合了各种国际主流指令系统的主要功能特性，不仅能够确保现有龙芯电脑上应用二进制的无损迁移，而且能够实现多种国际主流指令系统的高效二进制翻译.LoongArch已经被实现于龙芯中科技术股份有限公司研制的3A5000四核CPU.SPEC CPU2006的实验结果表明，在相同微结构下，LoongArch性能比龙芯CPU原指令系统MIPS平均提升超过7%.在硬件辅助支持下，SPEC CPU2000程序从MIPS翻译到LoongArch可以实现无损翻译，其定点程序子集和浮点程序子集从x86翻译到LoongArch的效率分布达QEMU二进制翻译器的3.6倍和47.0倍.LoongArch有望消除指令系统之间的壁垒，使得不同指令集的软件能够融合到统一的LoongArch平台上，不加区别地高效运行.
Abstract:In this paper, the Loongson instruction set architecture (LoongArch) is introduced, which takes care of both advancement and software compatibility. LoongArch absorbs new features of recent ISA development to improve performance and reduce power consumption. New instructions, runtime environments, system states are added to LoongArch to accelerate binary translation from x86, ARM and MIPS binary code to LoongArch binary code. Binary translation systems are built on top of LoongArch to run MIPS Linux applications, x86 Linux and Windows applications, and ARM Android applications. LoongArch is implemented in the 3A5000 four-core CPU product of Loongson Technology Corporation Limited. Performance evaluation of SPEC CPU2006 with the 3A5000 and its FPGA system shows that, with the same micro-architecture, LoongArch performs on average 7% better than MIPS. With the hardware support, the binary translation from MIPS to LoongArch can be done without performance loss, and that from x86 to LoongArch performs 3.6(int) and 47.0(fp) times better than QEMU system. LoongArch has the potential to remove the barrier between different ISAs and provides a unified platform for a new eco-system.
-
Keywords:
- Loongson CPU /
- MIPS architecture /
- LoongArch /
- binary translation /
- compatibility /
- software eco-system
-
ZNS SSD （Zoned Namespaces SSD）[1-7]是2019年由西部数据公司和三星公司推出的新一代固态硬盘（solid state drive，SSD），目前受到了工业界和学术界的广泛关注. 由于基于闪存的SSD只有在块被完全擦除以后才能重写，传统的 SSD 通过使用闪存转换层（flash translation layer，FTL）[8] 来适应这一特性，但由于闪存块存在物理限制 （擦除操作以块大小进行，而读写操作以页大小进行），因此经常需要进行垃圾回收（garbage collection，GC）[5,9]，同时也带来了预留空间 （over provisioning，OP）[10]和写放大（write amplification，WA）[11] 等问题，ZNS SSD可以有效提升SSD的读写吞吐，降低写入时的写放大，减少SSD本身的预留空间，并且还能解决传统SSD在空间占用达到一定程度时由于内部垃圾回收导致的性能不稳定的问题[12-13]，因此利用ZNS SSD来构建数据库系统是一个趋势[3].
图1展示了ZNS SSD 和传统 SSD 数据放置对比，在ZNS SSD上数据由主机程序显式地控制放置. 虽然ZNS SSD具有如此多优点，但它同样带来了一些挑战[3,7]. 与传统基于闪存的SSD相比，ZNS SSD移除了FTL，将分区（Zone）的空间直接交由主机程序控制管理，由主机程序来处理垃圾回收、磨损均衡、数据放置等，这扩大了用户数据布局的设计空间. 由用户程序来决定数据的放置、生命周期和垃圾回收时机，通过有效合理地组织数据，可以提高系统的性能. 但 ZNS SSD 同样给主机程序的设计带来了新的要求，比如一个Zone内有一个写指针只能进行顺序写、不同Zone性能有差异、何时进行Zone-Reset操作等[7,14].
![]()
图 1 ZNS SSD和传统SSD数据放置对比Figure 1. Comparison of ZNS SSD and conventional SSD data placementB+-tree是数据库中经典的索引结构，以往研究者已经提出了多种针对SSD、持久性内存等新型存储的B+-tree优化方法[15-26]. 但是，已有的SSD索引设计重点在于减少对SSD的随机写操作. 虽然ZNS SSD的底层介质仍是闪存，但由于Zone内只能顺序写，因此随机写的问题不再是ZNS SSD上B+-tree索引优化的第一目标. B+-tree如何在没有FTL的情况下适应ZNS SSD的分区特性以及Zone内顺序写要求，是ZNS SSD感知的B+-tree索引需要解决的关键问题. 针对传统SSD设计的索引由于没有考虑ZNS SSD的特性，所以都无法直接运行在ZNS SSD上. 此外，根据我们的调研，目前也还没有提出ZNS SSD感知的索引结构.
本文提出了一种ZNS SSD感知的新型索引结构——ZB+-tree（ZNS-aware B+-tree）. 我们发现，虽然ZNS SSD上要求Zone内顺序写，但是实际的分区块设备 （zoned block device，ZBD）中除了只允许顺序写的顺序Zone （sequential zone，Seq-Zone），还存在着少量允许随机写的常规Zone （conventional zone，Cov-Zone）. 因此，我们结合了ZNS SSD内部这2类Zone的特性设计了ZB+-tree的结构来适配ZNS SSD. 具体而言，本文的主要工作和贡献可总结为3个方面：
1）提出了一种ZNS SSD感知的新型索引结构ZB+-tree. ZB+-tree利用了ZNS SSD内部的Cov-Zone来吸收对Zone的随机写操作，并将索引节点分散存储在Cov-Zone和Seq-Zone中，通过设计不同的节点结构来管理不同Zone上的节点，在保证Zone内顺序写要求的同时提高空间效率.
2）设计了ZB+-tree上的相关操作，包括Sync，Search，Insert，Delete等，在保证索引性能的同时减少操作过程中的读写次数.
3）利用null_blk[27]和libzbd[28]模拟ZNS SSD设备开展实验，并将传统的CoW B+-tree修改后作为对比索引. 结果表明，ZB+-tree能有效阻断级联更新，减少读写次数，在运行时间、空间利用率上均优于CoW B+-tree.
1. 背景与相关工作
本节主要介绍目前业界对于ZNS SSD的相关研究和SSD 感知的B+-tree索引的相关工作，同时也介绍本文用于对比实验的CoW B+-tree.
1.1 ZNS SSD相关工作
ZNS SSD将其空间划分为许多的Zones，在一个Zone内可以随机读，但是只能顺序写，当一个Zone写满时会触发Zone-Reset和GC操作. 图2显示了Zone的大致结构，每个Zone内有一个写指针，Zone内有严格的顺序写限制.
传统SSD由于FTL的存在，会给主机程序提供块接口[1]，各类任务都交由FTL来处理，SSD通过FTL提供给上层应用的接口是支持随机读写的，在程序设计时可以视为硬盘. FTL的存在使得之前为硬盘设计的各类应用程序可以几乎不用修改而直接迁移到SSD上，但同时也导致了SSD需要预留空间、需要进行内部的垃圾回收、在空间占比达到一定程度时会发生性能抖动等问题[1,12].
ZNS SSD相比于传统块接口的SSD有以下优点：首先在ZNS SSD上减少甚至移除了FTL，将映射表的管理、垃圾回收和顺序写的限制都交给主机端进行控制，节约了成本，同时解决了预留空间的问题. 其次由于主机程序能控制ZNS SSD上数据的放置、垃圾回收时机，通过将不同特性的数据放置在不同的Zone，选择合理的垃圾回收时机等策略将有助于提高系统性能、延长SSD使用寿命.
由于在Zone内只能顺序写，因此很多基于传统SSD抽象接口开发的应用和系统不能直接应用在ZNS SSD上[1-6]. 此外，由于ZNS SSD移除了设备内的垃圾回收，因此需要用户自行设计垃圾回收机制，带来了额外的复杂性. Stavrinos等人[3]分析了ZNS SSD的各项优势，并通过调研发现一旦行业因为ZNS SSD的成本和性能优势开始转向ZNS SSD，则之前大多数SSD上的工作都需要重新审视，因此呼吁研究者转向ZNS SSD的研究. Shin等人[7]通过在ZNS SSD原型硬件上进行各种性能测试，为ZNS SSD上的软件设计提供了有效思路. Choi等人[5]提出了一种在ZNS SSD上的LSM（log-structured merge）风格的垃圾回收机制，他们建议针对ZNS SSD进行细粒度的垃圾回收，并根据数据热度将细粒度数据存储在不同的分区内. 西部数据的Bjørling等人[1]基于ZNS SSD开发出了ZenFS文件系统来适配 RocksDB的文件接口，目前已经成功提交到 RocksDB的社区. Han等人[2]在ZNS接口的基础上更进一步，提出了ZNS+接口. ZNS+是一种对日志结构文件系统（log-structured file system，LFS）感知的ZNS接口，将用户定义的垃圾回收产生的有效数据拷贝放到设备内部进行，从而减少I/O操作，提升文件系统垃圾回收的效率.
虽然ZNS SSD具有如此多优点，但它同样带来了一些挑战. 与传统SSD相比，ZNS SSD移除了FTL，将Zone的空间直接交由主机程序控制管理，由主机程序来处理垃圾回收、磨损均衡、数据放置等，这扩大了用户数据存储管理的设计空间，也带来了设计上的困难. 总体而言，ZNS SSD的顺序写和Zone划分等限制对现有的数据存储管理机制提出了诸多新的挑战，包括存储分配、垃圾回收、索引结构等.
1.2 SSD感知的B+-tree相关工作
在过去的10多年里，由于闪存技术的快速发展，学术界针对闪存感知的B+-tree优化方法开展了广泛的研究. Roh等人[15]利用SSD内部的并行性来优化B+-tree索引. Na等人[16]提出了一种动态页内日志风格的B+-tree索引. Agrawal等人[17]设计了一种惰性更新的机制来使B+-tree更适合SSD特性. Ahn等人[18]利用CoW B+-tree的性质对SSD上的B+-tree进行了优化. Fang等人[19]提出一种感知SSD持久度的B+-tree方案. Jin等人[20]则利用布隆过滤器（Bloom filter）和节点的更新缓存实现了不降低读性能的同时减少SSD写操作. Lv等人[21]通过日志的方式将随机写转为顺序写来优化SSD上的R-tree的读写操作. Jin等人[22]通过利用SSD内部的并行来批量处理小的写入，提出了一种flash感知的线性散列索引. Ho和Park[23]通过在内存中设计一个写模式转换器，将随机写转换为顺序写，以此来充分利用SSD的特性. 文献[24]使用IPL （in-page logging）和写缓存等技术设计符合SSD特性的LSB+-tree，同时提高了索引的时间和空间效率.
总体而言，SSD感知的B+-tree索引的设计重点在于减少对SSD的随机写操作. 这是因为B+-tree本身是一种写不友好的索引，因此对于SSD上的写密集应用性能较差. ZNS SSD的介质仍是闪存，因此同样需要考虑减少随机写操作. 但由于Zone内只能顺序写，随机写的问题不再是ZNS SSD上B+-tree索引优化的第一目标. 如何适应数据的分区存储和顺序写特性，是设计ZNS SSD感知的B+-tree索引需要重点考虑的问题. 就目前的研究进展，还没有一种已有的SSD索引能够直接运行在ZNS SSD上.
1.3 CoW B+-tree
目前学术界还没有提出针对ZNS SSD的索引结构. 与本文工作较相关的已有工作主要是CoW B+-tree. CoW B+-tree是一种追加写（append-only write）的B+树结构[25]. 这刚好适应了ZNS SSD的Zone内顺序写要求，因此如果不考虑Zone内数据存储分配的话，可以将CoW B+-tree修改后运行在ZNS SSD上. 图3给出了CoW B+-tree的数据更新过程.
文献[18]对Cow B+-tree针对SSD特性做了一些优化以减少写放大，但是却无法保证B+-tree节点大小相同，因此本文还是选择传统CoW B+-tree[25]进行对比，CoW B+-tree算法流程和传统的B+-tree基本一样，只是修改叶节点时由于不能原地更新，因此需要把修改后的节点直接附加在写指针处，由于叶节点的地址发生了改变，因此还需要修改其父节点中指向叶节点的指针. 这一修改会级联往上传递，直到根节点.
但是，直接将CoW B+-tree的所有节点都写在一个Zone中将会很快耗尽Zone的空间，从而频繁触发Zone-Reset操作. 因此，在本文后续的对比实验中，我们对CoW B+-tree进行了修改使其能够利用所有的Zone，并减少频繁的Zone-Reset操作. 由于主机程序可以得知Zone的使用情况，我们总是将CoW B+-tree节点写入剩余空间最多的Zone，并根据当前Zone的使用情况动态选择Zone而不是固定写入一个Zone. 这样可以在使用该索引时尽量减少Zone-Reset，同时充分利用ZNS SSD的空间.
2. ZB+-tree 索引结构
2.1 设计思路
由于ZNS SSD具有多分区特性，不同的Zone性能有所差异，在频繁访问的磨损较多的Zone会有更高的访问延迟[7]，且在Seq-Zone中有严格的顺序写要求. 当Zone写满时会触发Zone-Reset操作和垃圾回收，这2个操作非常耗时，会带来性能的抖动. 因此ZB+-tree主要针对4个目标进行设计：1）索引要能充分利用ZNS SSD的多分区特性；2）要满足在Seq-Zone中的严格顺序写限制；3）将频繁访问的数据尽量放置在磨损较少的Zone以降低访问延迟；4）尽量减少在运行过程中的GC和Zone-Reset操作，以避免性能抖动.
针对上述目标，ZB+-tree进行了全新设计，主要设计思路总结为5个方面：
1）将索引节点分散在多个Zone中，允许节点在不同Zone之间进行移动. 由于Cov-Zone中允许进行原地更新，如果能充分利用这一特性，就能将对索引的原地更新吸收在Cov-Zone中. 当节点写满时则整体移动到Seq-Zone中，既保证不会有太大的写放大，而同时也能保证在Seq-Zone中的顺序写要求.
2）将对Seq-Zone中节点的更新也吸收在Cov-Zone中，为Seq-Zone中不可原地更新的节点设计了日志节点结构，日志节点放置在Cov-Zone中以进行原地更新，减少写放大. 同时为避免日志节点过多而影响整体的读写性能，需要将日志与节点合并，可通过设计新的Sync操作来实现.
3）为不同类型的节点动态选择不同的Zone进行放置，由于叶节点和内部节点更新频率不同，叶节点频繁更新而内部节点相对更新较少，因此我们提出一种动态选择Zone的策略，将频繁更新的叶节点放置在空间占用较少、磨损较少的Zone中，而将内部节点放置于空间占用和磨损相对较多的Zone中，以充分利用ZNS SSD的多分区特性，并降低访问延迟.
4）为管理分散在不同Zone的节点和对应的日志节点，我们为叶节点和内部节点都设计相应的head节点，以记录节点的状态、地址、日志情况，并将head节点存储于Cov-Zone中，以阻断级联更新.
5）由于不同分层的节点处于不同类型的Zone中，对节点的合并控制也将采用不同的策略，对于都在Cov-Zone中的节点，采用严格控制合并策略；对于节点分散在Cov-Zone和Seq-Zone中的节点，则采用机会主义合并策略. 通过不同的控制合并策略，在保证索引性能的同时尽量减少级联更新和写放大.
2.2 ZB+-tree总体结构
在本文的设计中，ZB+-tree总共分为4层，从上到下分别是IH层、Interior层、LH层、Leaf层，其中IH层由interior-head节点组成，LH层由leaf-head节点组成，Interior层由interior节点和interior-log节点组成，Leaf层由leaf节点和leaf-log节点组成. 由于通常来说B+-tree为3~4层，我们设计的IH可以视为B+-tree的根节点. IH层和LH层的节点既可以作为B+-tree的内部节点（里面存着key值和子节点地址），同时又记录着下一层的节点状态和日志情况. 图4展示了ZB+-tree的逻辑结构，其中F代表key值为First（key无法取到的最小值），K代表普通key值.
由于主机程序可以随时知道ZNS SSD上各个Zone的使用情况，这里提出一种动态选择Zone的方法，即当有节点需要从Cov-Zone移入到Seq-Zone中时，如果是leaf节点，则动态选择当前剩余容量最多的Zone（称为Hot-Seq-Zone）放置，如果是interior节点，则动态选择当前剩余容量最少的Zone（称为Cold-Seq-Zone）放置. 之所以这么区分，是因为叶节点和内部节点的更新频率不同，把更新频率高的叶节点往剩余空间最大的Zone内放置可以避免由于Zone空间被迅速占满而导致的Zone-Reset操作. 同时剩余容量多、磨损较少的Zone的读写性能也更好，可以便于leaf的频繁读写.
图5显示了ZB+-tree节点在ZNS SSD上的具体分布情况，其中IH和LH层都位于Cov-Zone中，而interior节点和leaf节点则分布在Cov-Zone和Seq-Zone中. 在本文中，我们约定：白色代表Cov-Zone，深灰色代表Hot-Seq-Zone，浅灰色代表Cold-Seq-Zone，灰色渐变代表处于Seq-Zone中可能是Hot状态也可能是Cold状态.
对于interior节点和leaf节点，设计了相应的状态转换机制，如图6所示. ZB+-tree的interior节点和leaf节点有4种可能的状态.
1）change_state. 处于change_state的节点都位于Cov-Zone中，并且节点未满，可以就地插入、删除、更新. 处于change_state的节点一旦满了，如果是叶节点，则整体移动到Hot-Seq-Zone中；如果是内部节点，则整体移动到Cold-Seq-Zone中，这刚好符合ZNS SSD的顺序写限制.
2）steady_state_hot. 节点位于Hot-Seq-Zone中，且为叶节点，节点一定是满的，并且不可就地更改. 对此状态的节点进行插入将导致其分裂成2个change_state的叶节点，对此状态节点的更新和删除将记录在leaf-log节点中.
3）steady_state_cold. 节点位于Cold-Seq-Zone中，且是内部节点，节点一定是满的，并且不可就地更改. 对此状态的节点进行插入将导致其分裂成2个change_state的内部节点，对此状态节点的更新和删除将记录在interior-log节点中.
4）after_state. 处于该状态的节点一定带有log节点，并且log节点中有删除记录，表示该节点在steady_state经过了删除. 对此状态的节点进行插入会首先触发Sync操作，将节点和对应的log节点合并之后再进行插入，对此状态节点的更新和删除将记录在log节点中.
处于steady_state的节点可能带log节点也可能不带log节点，log节点都位于Cov-Zone中以吸收对Seq-Zone中节点的原地更新，对steady_state的节点进行的更新和删除操作会直接写到对应的log节点里（如果该节点原本不带log节点则为其分配一个log节点）. 处于steady_state的节点可以进行3种操作：
1）Sync操作. 将节点与对应的log节点进行合并，Sync操作完成之后节点还是处于steady_state.
2）Delete操作. 在log节点中增加删除记录，Delete操作完成之后节点转换为after_state表示节点已经经过了删除.
3）Split操作. 节点分裂成2个，Split操作完成之后节点转化为2个change_state的节点并移动到Cov-Zone中.
处于after_state的节点可以进行Sync操作，将节点与对应的log节点进行合并. 由于必然经过了删除操作，实际上after_state的节点在逻辑上代表一个未满的节点，因此合并后节点状态转换为change_state.
2.3 ZB+-tree节点结构设计
leaf节点设置为n 个key值和n个value值，leaf-log节点的结构与leaf节点的结构完全相同，之所以设置为结构相同，是因为在Sync操作中需要将leaf-log节点直接转化为leaf节点（具体细节见3. 1节Sync操作），在leaf-log节点中通过位置与leaf节点中的键值对应，如图7所示.
对于leaf-head节点，结构为n+1个key值和n+1个ptr结构，如图8所示. ptr结构中包括3个值：
1）state. 表示子节点所处的状态.
2）addr. 表示子节点所在的位置.
3）log_addr. 表示子节点对应的日志节点所处的位置.
leaf-head节点的第1个key值一定是First（key无法取到的最小值）.
interior节点的结构为n+1个key和n+1个addr（子节点的地址），interior-log和interior结构完全相同（同样是因为Sync操作的要求），interior-head的结构和leaf-head的结构相同. 在interior和interior-head节点中，第1个key值同样设置为First. 之所以在interior节点中引入First值是因为在ZB+-tree中的Sync操作需要让日志节点和interior节点保持相同结构以便于log节点与正常的内部节点之间直接进行转化，而日志节点又是通过位置与原内部节点进行对应，所以需要给第1个位置一个key值，代表这是第1个子节点. 之所以在leaf-head和interior-head中引入First值，是因为对于每一个leaf节点或者是interior节点，都需要相应的ptr结构来指示其状态、位置和日志情况. 即使树中只有一个leaf节点或只有一个interior节点也要有对应的ptr结构，因此，需要为第1个ptr结构设置key值为First，表示这是子树中第1个interior节点或者第1个leaf节点，而其他的key值则与正常B+-tree中的key值含义相同，代表对应子树中的最小key值.
3. ZB+-tree 索引操作
本节主要介绍ZB+-tree的Sync，Search，Insert，Delete等操作，并给出了时间性能和空间代价分析.
3.1 Sync
在ZB+-tree中无论是interior-log节点还是leaf-log节点都只记录更新和删除操作，其结构和对应的interior节点或leaf节点相同，当树中存在的日志节点过多时会对Cov-Zone有较大的占用而且会影响整体的查找性能，因为读一个节点之后还需要再读一次日志节点来重建最新的节点. 因此需要将日志节点和对应的节点进行合并，构建最新的节点并释放日志节点空间，我们称之为Sync操作. 在日志节点写满时同样需要将日志与节点进行合并. 在ZB+-tree中，我们设计了2种方式的合并，当日志节点未满时的合并称之为Normal_apply，当日志节点满了时的合并称之为Switch_apply.
1）Normal_apply. 图9给出了Normal_apply的过程. 当节点对应的log节点还未满时，如果节点处于steady_state，表示节点还未进行过删除操作，log节点中无删除记录，因此根据log节点进行更新后的节点仍然处于steady_state，此时将新的节点写回Seq-Zone并释放Cov-Zone上log节点的空间. 如果节点处于after_state，则表示节点经过了删除操作，log节点中一定有删除记录，根据log节点进行更新后的节点转换成change_state并写到Cov-Zone中原log节点的位置. 算法1给出了Normal_apply操作流程.
算法1. Normal_apply_leaf （&leaf, &leaf_log, &leaf_ptr）.
输入： 叶节点leaf，对应的日志节点leaf_log，叶节点对应的ptr结构leaf_ptr；
输出： 无.
① if leaf_ptr. state == after_state then
② for each 〈key, value〉 in leaf_log
③ if key ≠ delete_key then
④ update 〈key, value〉 in leaf；
⑤ else delete 〈key, value〉 in leaf ；
⑥ end if
⑦ end for
⑧ write_leaf （leaf_ptr. log_addr, leaf）；
⑨ leaf_ptr. state = change_state；
⑩ leaf_ptr. addr = leaf_ptr. log_addr；
⑪ leaf_ptr. log_addr = Null；
⑫ end if
⑬ if leaf_ptr. state == steady_state_hot then
⑭ for each 〈key, value〉 in leaf_log
⑮ update 〈key, value〉 in leaf ；
⑯ end for
⑰ reclaim leaf-log ；
⑱ addr = select the Zone with minimum capacity；
⑲ write_leaf （addr, leaf）；
⑳ leaf_ptr. addr = addr；
㉑ leaf_ptr. log_addr = Null；
㉒ end if
2）Switch_apply. 图10给出了Switch_apply的过程. 当节点对应的log节点已经写满时，将发生Switch_apply，与Normal_apply不同的是，Switch_apply不需要读原节点，而只需要读其log节点，因为日志已满说明原节点中所有键值对都已经经过了更新或者删除. 如果原节点处于steady_state，说明对节点的所有键值对都进行过更新操作，因此直接将log节点作为新的节点写入Seq-Zone中 ，并释放在Cov-Zone中log节点的空间. 如果原节点处于after_state，说明其除了进行过更新操作之外还有删除操作，因此把log节点中有删除标记（delete_key）的键值对去除后，转化为change_state的节点，直接写回Cov-Zone中原log节点位置. 算法2给出了Switch_apply.
算法2. Switch_apply_leaf（&leaf_log, &leaf_ptr）.
输入： 叶节点对应的日志节点leaf_log，叶节点对应的ptr结构leaf_ptr；
输出： 重建的leaf .
① if leaf_ptr. state == steady_state_hot then
② addr = select the Zone with minimum capacity；
③ write_leaf （addr, leaf_log）；
④ reclaim leaf-log；
⑤ leaf_ptr. addr = addr；
⑥ leaf_ptr. log_addr = Null；
⑦ return leaf-log；
⑧ end if
⑨ if leaf_ptr. state == after_state then
⑩ for each 〈key, value〉 in leaf_log
⑪ if key == delete_key then
⑫ delete 〈key, value〉 in leaf-log；
⑬ end if
⑭ end for
⑮ write_leaf （leaf_ptr. log_addr, leaf_log）；
⑯ leaf_ptr. state = change_state；
⑰ leaf_ptr. addr = leaf_ptr. log_addr；
⑱ leaf_ptr. log_addr = Null；
⑲ return leaf-log；
⑳ end if
Sync操作（见算法3）对于interior节点和leaf节点都类似，唯一区别在于interior节点中为n+1个键值对而leaf节点中为n个键值对. 对leaf节点的操作为Sync，对于interior节点也有相应的in_Sync操作.
算法3. Sync（&leaf, &leaf_log, &leaf_ptr）.
输入： 叶节点leaf，对应的日志节点leaf_log，叶节点对应的ptr结构leaf_ptr；
输出： 重建的leaf.
① if leaf_log is full then
② return Switch_apply_leaf （leaf_log, leaf_ptr）；
③ else
④ Normal_apply_leaf （leaf, leaf_log, leaf_ptr）；
⑤ return leaf；
⑥ end if
3.2 Search
在ZB+-tree上的Search过程如算法4所示，如果ZB+-tree中还没有IH层，也就是整棵树只有2层（LH层和Leaf层）时，只有一个leaf-head节点，此时直接从leaf-head开始进行搜索. 如果树中存在IH层，则根据要搜索的key值，先从IH中得到interior节点对应的ptr结构，如果interior节点没有log节点，则直接读出interior节点；如果interior节点有log节点，则会触发apply_innner_log（）操作，这个操作只是在内存中重建最新的interior节点，并不会对ZNS SSD上的interior节点和日志节点进行修改. 这样做的目的是避免在Search过程中触发写操作. 得到了最新的interior节点之后，在其中根据key值搜索得到leaf-head节点的地址，并读出leaf-head节点，再从leaf-head开始搜索，即触发Search_leaf_head（）操作，具体见算法5. 其过程与从IH搜索interior节点的过程类似，其中apply_leaf_log（）也只是在内存中建立最新的leaf节点，并不修改ZNS SSD上的leaf节点和log节点. 得到最新的leaf节点之后，再根据key值进行搜索，如果搜到则返回value值，否则返回Null，表示没有搜到.
算法4. Search（key）.
输入： 要搜索的key值；
输出： 搜到返回对应的value值，否则返回Null.
① if IH is empty then
② return Search_leaf_head（leaf_head_last, key）；
③ else
④ inter_ptr = search IH to get the interior_ptr；
⑤ if inter_ptr. log_addr == Null then
⑥ inter = read_interior（inter_ptr. addr）；
⑦ else
⑧ get the log and old_inter；
⑨ inter = apply_inner_log（old_inter,log）；
⑩ end if
⑪ leaf_head_addr = search the inter to get the address of leaf_head node；
⑫ leaf_head = read_LH（leaf_head_addr）；
⑬ return Search_leaf_head（leaf_head, key）；
⑭ end if
算法5. Search_leaf_head （leaf_head, key）.
输入： 要搜索的leaf_head节点，要搜索的key值；
输出： 搜到返回对应的value值，否则返回Null.
① leaf_ptr = get the ptr struct of leaf node from leaf_head；
② if leaf_ptr. log_addr == Null then
③ leaf = read_leaf（leaf_ptr. addr）；
④ else
⑤ log = read_leaf_log（leaf_ptr. log_addr）；
⑥ old_leaf = read_leaf （leaf_ptr. addr）；
⑦ leaf = apply_leaf_log（old_leaf, log）；
⑧ end if
⑨ for each 〈KEY, VALUE〉 in leaf do
⑩ if key == KEY then
⑪ return VALUE；
⑫ end if
⑬ end for
⑭ return Null.
3.3 Insert
在ZB+-tree上的Insert操作会先根据要插入的key值从根节点一路搜索到叶节点对应的leaf-head节点，搜索过程与Search相同，从leaf-head节点中得到对应的ptr结构，如果叶节点处于change_state，则直接往叶节点中插入键值对，如果满了则移动到Seq-Zone中. 而对于steady_state的叶节点，如果不带log节点，则直接进行Split操作，分裂成2个Cov-Zone上的change_state的节点，如果带log节点，则先进行Sync操作，合并leaf节点和log节点之后再插入键值对，Insert具体细节见算法6，ZB+-tree上的Split操作和正常B+-tree的操作类似，唯一需要注意的是对树中First值的维护.
算法6. Insert（key, value）.
输入： key, value 是要插入的键值对；
输出： 无.
① leaf_head = find the leaf_head node of the corres ponding leaf node；
② leaf_ptr = get the ptr struct of the leaf node；
③ leaf = get the leaf node；
④ if leaf_ptr. state == change_state then
⑤ insert 〈key, value〉 in leaf ；
⑥ if leaf is full then
⑦ move leaf to Seq-Zone；
⑧ leaf_ptr. state = steady_state_hot；
⑨ leaf_ptr. addr = new_addr；
⑩ end if
⑪ else
⑫ if leaf_ptr. log_addr == Null then
⑬ Split（leaf, key, value）；
⑭ else
⑮ log = get the leaf_log node of the leaf；
⑯ leaf = Sync（leaf, log, leaf_ptr）；
⑰ if leaf_ptr. state == change_state then
⑱ insert 〈key, value〉 to leaf；
⑲ if leaf is full then
⑳ move leaf to Seq-Zone；
㉑ leaf_ptr. state = steady_state_hot；
㉒ leaf_ptr. addr = new_addr；
㉓ end if
㉔ end if
㉕ if leaf_ptr. state == steady_state_hot then
㉖ Split（leaf, key, value）；
㉗ end if
㉘ end if
㉙ end if
3.4 Delete
ZB+-tree上的删除操作与经典B+-tree算法有许多不同之处，由于不同层的节点所处的Zone性质是不同的，对于不同层的节点在进行Delete操作时，也将采用不同的控制合并的策略.
对于IH层，由于所有的leaf-head节点都处于Cov-Zone中，可以发生原地更新，因此在删除时当节点容量达到下限（lower_bound），我们采取严格控制合并的策略，即leaf-head节点的容量严格控制在lower_bound和full之间（整棵树只有一个leaf-head节点时例外）. 而对于Leaf层，在进行删除时我们采取的是机会主义策略控制合并，即查看邻居节点，能合并就合并（二者容量之和小于n），不能合并就不作处理，能满足合并条件则意味着二者必然都处于change_state，即都在Cov-Zone中. 之所以采取不同策略，是因为Leaf层的节点分散在Seq-Zone和Cov-Zone中，且节点可能带log节点也可能不带log节点. 如果不能发生合并，从steady_state的邻居借一个键值对，并不会减少空间的占用，反而将引发级联的修改，还要处理log节点. 在机会主义策略控制下，leaf节点的容量范围为1~n.
对于Interior层的节点我们同样采取机会主义控制合并的策略，理由和Leaf层相同，interior节点的容量范围为1~n+1，当节点只有一个key值时必然是First，算法7展示了对Leaf层的Delete操作.
算法7. Delete（key）.
输入： key是要删除的键值对的key值；
输出： 删除成功返回true，删除失败返回false.
① leaf_head = find the leaf_head node of the corresp onding leaf node；
② leaf_ptr = get the ptr struct of the leaf node；
③ leaf = get the leaf node；
④ if find_in_leaf（key, leaf_ptr） == false then
⑤ return false；
⑥ else
⑦ if leaf_ptr. state == change_state then
⑧ delete_in_leaf （leaf, key）；
⑨ if leaf is empty then
⑩ LH_delete（LH, key）；
⑪ reclaim leaf in Cov-Zone；
⑫ return true；
⑬ else do opportunism merge；
⑭ end if
⑮ end if
⑯ if leaf_ptr. state == after_state then
⑰ log = get the log of leaf；
⑱ Insert delete_key to log；
⑲ return true；
⑳ else
㉑ if leaf_ptr. log_addr == Null then
㉒ Allocate a new log for leaf；
㉓ Insert delete_key to log；
㉔ leaf_ptr. state = after_state；
㉕ leaf_ptr. log_addr = log_addr；
㉖ return true；
㉗ else
㉘ log = get the log of leaf；
㉙ Insert delete_key to log；
㉚ leaf_ptr. state = after_state；
㉛ return true；
㉜ end if
㉝ end if
㉞ end if
3.5 理论代价分析
3.5.1 时间性能
4层的ZB+-tree在查询时最坏情况下需要读6次，即读interior-head节点、读interior节点和interior-log节点、读leaf-head节点、再读leaf节点和leaf-log节点，如果Interior层和Leaf层没有log节点，则与4层的CoW B+-tree一样，需要读4次. 在进行插入操作时，CoW B+-tree需要先4次读出根到叶节点的路径，如果不发生分裂需要4次写操作，在最坏情况下除了根节点外每层节点都分裂，则需要7次写操作. 而ZB+-tree插入时同样需要先进行4~6次读，如果不发生分裂则只需要1次写操作（即直接往Cov-Zone中就地插入），如果发生分裂，最坏情况下需要7次写操作，但大多数情况下不会出现每一层都恰好分裂，因此往往只需要1~2次写操作即可，即将级联的更新阻断在Cov-Zone中. 对CoW B+-tree的删除操作，同样需要先进行4次读，随后如果没发生合并，最好情况下需要4次写操作，如果发生合并或者向邻居借键值对则需要更多的读写. 而ZB+-tree在进行4~6次读操作之后，如果没发生合并，则只需要1次写操作（change_state的节点就地删除后只需要1次写；steady_state的节点则往log节点中插入删除记录，也只需要1次写），如果发生合并，则在机会主义策略控制合并的2层进行的合并操作会更少，并且在这2层不会发生向邻居借键值对的操作，而在LH层和IH层与CoW B+-tree一样都采用了严格控制合并的策略，因此总体上的读写次数也会少于CoW B+-tree. 结合上述分析，可知ZB+-tree在查询性能上与CoW B+-tree接近，在插入时会减少写操作，而在删除时会同时减少读写操作.
3.5.2 空间代价
CoW B+-tree的每次更新都至少需要将从根到叶节点的路径重新写回到ZNS SSD中；而ZB+-tree则将更新吸收在Cov-Zone中，往往只需要在Cov-Zone中进行一次原地更新. 因此，相比于CoW B+-tree，ZB+-tree会大大减少对Seq-Zone的占用.
假设一个节点大小为m，一个4层的ZB+-tree，阶数为n，最坏情况下，每个leaf节点都带有leaf-log节点，且每个interior节点都带有interior-log节点，此时有效节点总大小可估计为
[2(n+1)3+(n+1)2+2(n+1)+1]×m. (1) 1棵4层的CoW B+-tree 有效节点所占空间大小即正常B+-tree所占空间大小，总空间大小可估计为
[(n+1)3+(n+1)2+(n+1)+1]×m. (2) 随着对索引的修改，CoW B+-tree会不断将修改过的节点以及到根节点的路径上的节点写入SSD中. 上述分析仅仅针对其有效节点部分，实际运行中CoW B+-tree还会产生大量无效节点，进一步增加空间占用率. 而ZB+-tree将原地更新吸收在Cov-Zone中，实际运行时虽然也会在Seq-Zone中产生无效节点，但数量会远远少于CoW B+-tree，且其有效节点部分在最坏情况下也和CoW B+-tree处于同一个量级. 因此，总体上，ZB+-tree的空间代价低于CoW B+-tree.
ZB+-tree相比于CoW B+-tree在LH层和IH层增加了一些数据结构用于管理下一层的节点，由于IH层和LH层都是内部节点，相对较少，因此额外的空间代价并不会特别高. ZB+-tree对Cov-Zone的占用情况则主要和工作负载有关，需要通过实验来进行验证.
4. 实验与分析
4.1 实验设置
服务器操作系统为Ubuntu20. 04. 1LTS，内核版本5. 4. 0，gcc版本为 9. 4. 0 . 由于目前还没有商用ZNS SSD，因此我们使用了null_blk来模拟ZNS SSD设备，并使用西部数据的ZBD操作库libzbd进行实验. 具体的实验配置如表1所示.
表 1 实验配置Table 1. Experimental Configuration服务器组件 说明 OS Ubuntu 20.04.1 LTS CPU AMD EPYC 7742 64-Core@2.60GHz DRAM 256GB DDR4 （2666 MHz） GCC version 9.4.0 libzbd version 2.0.3 由于目前还没有提出ZNS SSD感知的索引，因此我们将CoW B+-tree进行了修改使其能够运行在ZNS SSD上. 具体而言，总是将CoW B+-tree节点写入剩余空间最多的Zone，并根据当前Zone的使用情况动态选择要写入的Zone，以尽量减少Zone-Reset操作，同时充分利用ZNS SSD的空间.
实验使用YCSB[29]作为测试负载. YCSB是目前在存储和数据库领域广泛使用的测试负载，它也允许用户自行配置读写比例和访问倾斜性. 在实验中我们利用YCSB生成了5个测试负载，说明如下：
1）Workload1是写密集的负载，包含插入、删除、查找操作，并且3类操作的占比分别为插入40%、删除30%、查找30%.
2）Workload2是读密集的负载，包含插入、删除、查找操作，并且3类操作的占比分别为插入10%、删除10%、查找80%.
3）Workload3是读写均衡的负载，包含插入、删除、查找操作，并且3类操作的占比分别为插入25%、删除25%、查找50%.
4）Workload4是纯写负载，包含插入、删除操作，并且2类操作的占比分别为插入50%、删除50%.
5）Workload5是纯读负载，只包含查找操作.
我们在5种负载上分别测试不同数据量和不同数据分布下的性能. 数据量分别设置为50万、150万、250万键值记录对，数据分布采用了文献[29]中的3类分布，包括Zipfian分布、uniform分布、latest分布. 在YCSB中执行测试前会先加载数据，以下的实验数据都是指在数据加载完成之后再进行各种操作时统计的数据. CoW B+-tree实验中模拟的ZBD设备为40个Seq-Zone以及1个Cov-Zone（为保证实验对比公平，我们把Cov-Zone按照Seq-Zone的顺序写模式来使用），每个Zone大小为2 GB；ZB+-tree实验中模拟的ZBD设备为40个Seq-Zone以及1个Cov-Zone，大小都为2GB. 在模拟器中块大小统一设置为4 KB.
4.2 实验结果分析
4.2.1 运行时间比较
图11~13给出了ZB+-tree和CoW B+-tree的运行时间对比. 可以看到，在不同数据规模和不同工作负载下，ZB+-tree运行时间都要小于CoW B+-tree. 虽然ZB+-tree相对于CoW B+-tree在查询时可能要多读1~2次log节点，但由于在插入和删除操作中减少了读写次数，且SSD读操作比写操作要快[7]，因此ZB+-tree总体性能要好于CoW B+-tree，与理论分析相符.
![]()
图 11 Zipfian分布下运行时间对比Figure 11. Running time comparison under the Zipfian distribution![]()
图 12 uniform分布下运行时间对比Figure 12. Running time comparison under the uniform distribution4.2.2 读写次数比较
图14~16和图17~19分别显示了ZB+-tree和CoW B+-tree的读操作次数和写操作次数对比. ZB+-tree比CoW B+-tree在读操作次数上减少了25%左右，这是因为在删除操作时，相比于CoW B+-tree需要级联的读写，ZB+-tree在机会主义策略控制的2层减少了合并操作并去除了从邻居借键值对的操作. 在写操作次数方面，ZB+-tree在不同数据规模时平均节约了75%的写，这主要是因为ZB+-tree通过LH层和IH层的独特设计将级联的更新进行了2次阻断. 由于LH和IH都位于Cov-Zone中，允许进行原地更新，因此节点修改后的地址不发生改变，所以级联的更新被阻断在了Cov-Zone中. 相比于CoW B+-tree每次更新至少需要4次写操作，ZB+-tree只需要1~2次写操作即可.
![]()
图 17 Zipfian分布下写次数对比Figure 17. Write counts comparison under the Zipfian distribution![]()
图 18 uniform分布下写次数对比Figure 18. Write counts comparison under the uniform distribution4.2.3 空间占用率比较
表2~6分别显示了在Zipfian分布下，5种工作负载和3种数据规模下ZB+-tree和CoW B+-tree对于所有Seq-Zone的平均占用情况，其他数据分布下实验结果类似. 可以看出，随着数据规模的增加，CoW B+-tree将快速占用Seq-Zone的空间. 在当数据规模为250万时，CoW B+-tree对Seq-Zone的占用率最大达到了0.739822（Workload4），最小也有0.450943（Workload5）. 因此，在大规模写入负载下，CoW B+-tree的Seq-Zone将被快速写满，从而触发耗时的Zone垃圾回收和Zone-Reset操作，导致系统性能出现急剧下降.
表 2 不同数据规模下Workload1下对Seq-Zone的占用率Table 2. Occupancy Rate of Seq-Zone Under Workload1 at Different Data Scales方案 50万 150万 250万 ZB+-tree 0.000469 0.001543 0.002439 CoW B+-tree 0.120431 0.402918 0.678303 表 3 不同数据规模下Workload2下对Seq-Zone的占用率Table 3. Occupancy Rate of Seq-Zone Under Workload2 at Different Data Scales方案 50万 150万 250万 ZB+-tree 0.000385 0.001161 0.001882 CoW B+-tree 0.086633 0.300859 0.513317 表 4 不同数据规模下Workload3下对Seq-Zone的占用率Table 4. Occupancy Rate of Seq-Zone Under Workload3 at Different Data Scales方案 50万 150万 250万 ZB+-tree 0.000417 0.001371 0.002141 CoW B+-tree 0.103262 0.353144 0.599624 表 5 不同数据规模下Workload4下对Seq-Zone的占用率Table 5. Occupancy Rate of Seq-Zone Under Workload4 at Different Data Scales方案 50万 150万 250万 ZB+-tree 0.000498 0.001617 0.002613 CoW B+-tree 0.132233 0.432777 0.739822 表 6 不同数据规模下Workload5下对Seq-Zone的占用率Table 6. Occupancy Rate of Seq-Zone Under Workload5 at Different Data Scales方案 50万 150万 250万 ZB+-tree 0.000363 0.001025 0.001729 CoW B+-tree 0.073475 0.262106 0.450943 此外，ZB+-tree对于所有Seq-Zone的平均占用率在5种不同负载下均低于0.0027，远远低于CoW B+-tree. 而且ZB+-tree的Seq-Zone占用率不会因为数据规模的增大而出现Seq-Zone被快速写满的情况. 因此，在系统运行过程中，ZB+-tree一般不会频繁触发Zone垃圾回收和Zone-Reset操作，从而可以在保证系统性能和稳定性的同时节省较多的Seq-Zone空间，提升空间效率.
4.2.4 Cov-Zone和Seq-Zone的不同比例
由于当前还没有ZNS SSD的真实设备，因此Cov-Zone和Seq-Zone的比例可能会发生变化，因此，我们改变Cov-Zone和Seq-Zone的比例来测试ZB+-tree的效果.
在本节实验中，我们测试了3种不同的Cov-Zone和Seq-Zone的比例，分别是1∶32，1∶48，1∶64，数据分布为Zipfian分布，数据量设置为100万键值对，测试的负载为Workload1和Workload2，如图20所示.
![]()
图 20 Cov-Zone和Seq-Zone不同比例下运行时间对比Figure 20. Comparison of running time under different ratios of Cov-Zone and Seq-Zone从图20可以看出，在不同比例下，ZB+-tree的运行时间都要少于CoW B+-tree，更改Cov-Zone与Seq-Zone的比例并不影响读写次数，只会影响对Seq-Zone的占用率大小，具体结果如表7和表8所示.
表 7 不同比例下Workload1下对Seq-Zone的占用率Table 7. Occupancy Rate of Seq-Zone Under Workload1 at Different Ratios方案 1∶32 1∶48 1∶64 ZB+-tree 0.001125 0.000751 0.000562 CoW B+-tree 0.321145 0.216282 0.163043 表 8 不同比例下Workload2下对Seq-Zone的占用率Table 8. Occupancy Rate of Seq-Zone Under Workload2 at Different Ratios方案 1∶32 1∶48 1∶64 ZB+-tree 0.000959 0.000638 0.000478 CoW B+-tree 0.240339 0.161861 0.122018 由表7和表8可知，在不同比例下，ZB+-tree对Seq-Zone的占用率都远小于CoW B+-tree. 同时，我们发现更改Seq-Zone和Cov-Zone的比例对ZB+-tree的空间效率影响不大，表明ZB+-tree能够适应不同的Zone配置.
4.2.5 Zone-Reset次数比较
在4.2.1~4.2.4节的实验中，ZB+-tree和CoW B+-tree都采用了动态选择Zone的策略. 该策略将叶子节点和内部节点分开存放以充分利用ZNS SSD内部各个Zone的空间，并且尽量减少Zone-Reset操作，同时将不同特性的节点放在不同的Zone来降低访问延迟.
本节的实验旨在进一步验证ZB+-tree在不采用动态选择Zone策略时的性能. 为了保证实验的公平性，CoW B+-tree同样不采用动态选择Zone的策略. 此外，为了体现实验完整性，本实验中我们通过统计Zone-Reset的次数来对比ZB+-tree和CoW B+-tree.
对于ZB+-tree，设置1个Seq-Zone和1个Cov-Zone，大小都为2 GB，然后统计Zone-Reset次数. 对于CoW B+-tree，设置1个Seq-Zone和1个Cov-Zone（按顺序写模式使用），大小都为2 GB，当某一个Zone写满时，读出有效节点写到另一个Zone，然后进行Zone-Reset操作并统计次数. 实验数据量分别为250万、500万、750万键值对，数据分布设置为Zipfian，测试负载为Workload1和Workload2.
实验结果表明，在Workload1下，在数据量分别为250万、500万、750万键值对时，ZB+-tree均没有触发Zone-Reset操作；而CoW B+-tree则分别触发了10，22，37次Zone-Reset操作. 在Workload2下，ZB+-tree在数据量为250万、500万、750万键值对时依然没有触发Zone-Reset操作；而CoW B+-tree则分别触发了2，6，9次Zone-Reset操作.
因此，CoW B+-tree比ZB+-tree会更容易触发Zone-Reset操作，而ZB+-tree即使不进行动态选择优化，也能够在插入大量键值时不触发Zone-Reset操作. 由于Zone-Reset和Zone垃圾回收操作的时间延迟高，因此ZB+-tree相对于CoW B+-tree具有更好的时间性能，尤其是在写密集型负载下，这种优势更加明显.
4.2.6 对Cov-Zone的占用分析
在本节实验中，我们创建了40个Seq-Zone和1个Cov-Zone（每个Zone大小都为2 GB），并分别在100万、250万、500万、750万、1000万键值对的数据集上运行在Zipfian分布下的Workload1和Workload2，然后统计ZB+-tree对Cov-Zone的空间占用率.
实验结果如图21所示. 随着数据规模的增大，ZB+-tree对Cov-Zone的空间占用率呈线性增长趋势，这是因为数据规模越大，负载中涉及更新的键值越多，因此对Cov-Zone的使用量也增大. 但是，即使数据规模达到了1000万，对Cov-Zone的占用率也没有超过0.50，这表明Cov-Zone的空间不会用满，因此可以满足绝大部分应用的需要.
![]()
图 21 ZB+-tree对Cov-Zone的占用率变化Figure 21. Changes in the occupancy rate of Cov-Zone by ZB+-tree5. 结束语
本文提出了一种ZNS SSD感知的新型索引结构ZB+-tree，通过合理利用ZNS SSD中的常规Zone和顺序Zone的特性来吸收对Zone的随机写操作、阻断级联更新、减少读写次数. 我们为2种Zone内的节点设计了不同的节点结构，并通过将不同访问频率的节点分散在不同Zone中以降低访问延迟，并且满足ZNS SSD顺序写的限制. 我们利用ZNS SSD模拟器展开了实验，并对比了ZB+-tree和传统CoW B+-tree，结果表明ZB+-tree在运行时间和读写次数上均优于CoW B+-tree. 同时，ZB+-tree具有更低的Seq-Zone空间占用率，可以有效减少系统运行过程中进行的垃圾回收和Zone-Reset操作，提高系统性能，并且对Cov-Zone的占用率也能够在数据规模增大时始终保持在0.50以下，可以满足大多数应用的需要.
未来的工作将主要集中在3个方向：1）为ZB+-tree增加合理的GC机制；2）在选择节点放置时设置更加合理的Zone选择方案；3）在真实的ZNS SSD设备上进行实验.
作者贡献声明：刘扬提出算法思路，完成实验并撰写论文初稿；金培权提出指导意见并修改论文.
-
表 1 MIPS N64 定点寄存器使用约定
Table 1 MIPS N64 Integer Register Usage Convention
寄存器编号 MIPS N64助记符 使用约定 0 zero 总是为0 1 at 汇编暂存寄存器 2~3 v0,v1 子程序返回值 4~11 a0~a7 子程序的前8个参数 12~15 t0~t3 不需要保存的寄存器 16~23 s0~s7 保存寄存器，子程序使用需要保存和恢复 24~25 t8,t9 寄存器 26~27 k0,k1 为异常处理保留 28 gp 全局指针 29 sp 栈指针 30 s8/fp 保存寄存器，或作为帧指针 31 ra 子程序返回地址 
下载: 导出CSV
表 2 LoongArch64 定点寄存器使用约定
Table 2 LoongArch64 Integer Register Usage Convention
寄存器编号 LA64助记符 使用约定 0 zero 总是为0 1 ra 子程序返回地址 2 tp thread pointer，指向TLS 3 sp 栈指针 4~11 a0~a7 子程序的前8个参数 4~5 v0~v1 v0/v1是a0/a1的别名，用于表示返回值 12~20 t0~t8 不需要保存的寄存器 21 reserved 暂时保留不用 22 fp frame pointer，栈帧指针 23~31 s0~s8 保存寄存器，子程序使用需要保存和恢复
下载: 导出CSV
表 3 3A4000和3A5000的SPEC CPU2006性能对比
Table 3 SPEC CPU2006 Performance Comparison of 3A4000 and 3A5000
SPEC2006 程序 3A4000单核分值 3A5000单核分值 提升幅度/% 3A4000四核分值 3A5000四核分值 提升幅度/% 400.perlbench 14.4 25.9 79.7 52.7 94.4 79.2 401.bzip2 10.7 17.2 59.9 35.9 66.1 84.0 403.gcc 12.4 21.3 71.3 40.6 69.9 72.2 429.mcf 12.7 27.2 115.0 30.0 49.6 65.4 445.gobmk 15.3 23.9 56.2 58.7 91.8 56.3 456.hmmer 24.0 42.9 78.9 87.0 169.1 94.4 458.sjeng 14.0 21.3 52.3 55.1 84.1 52.5 462.libquantum 31.8 58.6 84.7 55.6 89.2 60.5 464.h264ref 21.2 34.7 63.5 82.6 137.7 66.6 471.omnetpp 9.1 16.7 83.4 24.5 43.5 77.9 473.astar 10.7 18.0 68.4 33.4 54.6 63.6 483.xalancbmk 14.6 28.2 93.7 37.0 69.8 88.5 定点几何平均 14.9 26.0 74.8 46.0 78.8 71.3 410.bwaves 39.9 57.8 45.0 52.8 84.5 60.0 416.gamess 14.5 23.1 58.6 58.0 91.7 58.2 433.milc 11.5 17.2 48.8 31.1 44.8 43.9 434.zeusmp 16.2 28.8 77.8 56.3 94.0 67.1 435.gromacs 10.4 15.4 47.7 40.8 61.0 49.4 436.cactusADM 31.8 58.4 83.5 78.9 130.0 64.8 437.leslie3d 23.8 39.1 64.2 41.9 72.5 73.0 444.namd 13.7 19.7 44.1 54.1 78.2 44.4 447.dealII 23.8 36.9 55.4 85.4 133.2 55.9 450.soplex 14.1 26.0 84.4 36.7 58.8 60.4 453.povray 21.8 34.2 56.8 86.8 136.0 56.6 454.calculix 11.3 23.7 109.6 40.8 90.5 121.4 459.GemsFDTD 18.3 30.0 63.5 33.0 54.7 65.6 465.tonto 16.1 27.9 73.3 59.9 106.9 78.5 470.lbm 18.5 31.9 72.5 35.9 51.5 43.3 481.wrf 15.0 33.1 121.1 50.6 99.7 97.0 482.sphinx3 18.9 33.9 79.2 41.1 83.0 101.9 浮点几何平均 17.6 29.7 68.7 49.5 82.1 65.9
下载: 导出CSV
表 4 3A4000和3A5000的Stream带宽对比
Table 4 Stream Bandwidth Comparison of 3A4000 and 3A5000
Stream 3A4000单核 3A5000单核 提升幅度/% 3A4000四核 3A5000四核 提升幅度/% Copy 9466.9 27649.1 192.1 17056.7 39896.4 133.9 Scale 10438.0 15219.1 45.8 18059.9 25073.3 38.8 Add 10033.4 18032.4 79.7 15658.6 29768.5 90.1 Triad 10060.9 17883.1 77.7 15977.2 29146.8 82.4
下载: 导出CSV
表 5 3A4000和3A5000的UnixBench对比
Table 5 UnixBench Comparison of 3A4000 and 3A5000
基准程序 3A4000单线程 3A5000单线程 提升幅度/% 3A4000四线程 3A5000四线程 提升幅度/% Dhrystone 2 using register variables 1373.3 2707.2 97.1 5473.9 10664.2 94.8 Double-Precision Whetstone 425.8 801.9 88.3 1703.5 3156.1 85.3 Execl Throughput 545.1 1183.6 117.1 2014.3 4334.7 115.2 File Copy 1024 bufsize 2000 maxblocks 1094.2 2321.6 112.2 1288.9 3212.9 149.3 File Copy 256 bufsize 500 maxblocks 688.9 1541.3 123.7 795 2022.6 154.4 File Copy 4096 bufsize 8000 maxblocks 1988.1 4197.4 111.1 2926.4 6794.8 132.2 Pipe Throughput 644.3 1324.7 105.6 2566 5160.1 101.1 Pipe-based Context Switching 294.5 808.9 174.7 1435.6 3025.1 110.7 Process Creation 469.4 948.6 102.1 1181.8 3300.8 179.3 Shell Scripts (1 concurrent) 1370.5 2650.7 93.4 3410.3 6175.6 81.1 Shell Scripts (8 concurrent) 2955.3 5300.6 79.4 3088.9 6613.4 114.1 System Call Overhead 508.3 1435.3 182.4 1812.5 4247.1 134.3 基准程序几何平均得分 816.4 1743.9 113.6 2022.4 4432.9 119.2
下载: 导出CSV
表 6 LoongArch和MIPS的SPEC CPU2006性能比较
Table 6 Performance Comparison of LoongArch and MIPS SPEC CPU2006
程序 LoongArch MIPS MIPSLoongArch/% 周期数 指令数 周期数 指令数 指令数 周期数 400.perlbench 5.44E+10 1.35E+11 5.80E+10 1.46E+11 106.66 107.44 401.bzip2 1.11E+11 1.95E+11 1.13E+11 2.00E+11 102.55 102.45 403.gcc 2.10E+09 3.40E+09 2.18E+09 3.93E+09 104.10 115.61 429.mcf 4.59E+10 1.67E+10 4.67E+10 2.14E+10 101.64 128.20 445.gobmk 2.07E+11 3.30E+11 2.15E+11 3.48E+11 103.94 105.43 456.hmmer 5.88E+10 1.82E+11 6.83E+10 1.75E+11 116.22 96.19 458.sjeng 2.97E+11 5.75E+11 3.04E+11 5.85E+11 102.19 101.66 462.libquantum 3.46E+09 7.24E+09 3.45E+09 8.46E+09 99.65 116.81 464.h264ref 1.71E+11 4.82E+11 1.75E+11 5.10E+11 102.25 105.94 471.omnetpp 9.45E+10 1.88E+11 1.04E+11 2.16E+11 110.37 114.73 473.astar 2.09E+11 1.89E+11 2.12E+11 2.05E+11 101.57 108.55 483.xalancbmk 1.06E+11 2.11E+11 1.53E+11 3.06E+11 145.16 145.20 定点算术平均 1.13E+11 2.10E+11 1.21E+11 2.27E+11 108.02 112.35 410.bwaves 4.01E+10 6.29E+10 4.29E+10 6.44E+10 106.82 102.42 416.gamess 2.77E+11 9.00E+11 2.83E+11 8.86E+11 102.23 98.46 433.milc 4.20E+10 1.95E+10 3.96E+10 1.75E+10 94.47 89.86 434.zeusmp 4.93E+10 6.29E+10 5.66E+10 7.32E+10 114.76 116.53 435.gromacs 2.49E+11 3.23E+11 2.49E+11 3.10E+11 100.23 95.94 436.cactusADM 2.95E+10 2.88E+10 3.13E+10 2.73E+10 106.19 95.10 437.leslie3d 7.88E+10 9.00E+10 8.40E+10 9.44E+10 106.53 104.81 444.namd 2.73E+10 4.59E+10 2.75E+10 4.69E+10 100.52 102.29 447.dealII 4.62E+10 8.07E+10 4.80E+10 8.72E+10 103.95 108.12 450.soplex 1.17E+10 1.52E+10 1.20E+10 1.66E+10 102.65 109.10 453.povray 1.28E+10 2.65E+10 1.32E+10 2.90E+10 103.03 109.63 454.calculix 2.72E+09 4.70E+09 3.24E+09 5.18E+09 119.09 110.36 459.GemsFDTD 6.64E+10 6.07E+10 6.58E+10 6.46E+10 99.16 106.52 465.tonto 3.46E+11 8.62E+11 3.75E+11 9.12E+11 108.26 105.79 470.lbm 9.43E+10 7.50E+10 1.03E+11 7.40E+10 109.68 98.64 481.wrf 9.12E+10 1.60E+11 1.13E+11 2.08E+11 123.40 130.45 482.sphinx3 1.77E+10 2.67E+10 2.25E+10 2.95E+10 126.98 110.60 浮点算术平均 8.72E+10 1.67E+11 9.23E+10 1.73E+11 105.57 107.53
下载: 导出CSV
表 7 3A5000的UnixBench优化
Table 7 Optimization of 3A5000 UnixBench
基准程序 单线程优化前 单线程优化后 提升幅度/% 四线程优化前 四线程优化后 提升幅度/% Dhrystone 2 using register variables 2702.2 2707.2 0.2 10636.6 10664.2 0.3 Double-Precision Whetstone 801.8 801.9 0.0 3150.7 3156.1 0.2 Execl Throughput 1101.9 1183.6 7.4 3818.3 4334.7 13.5 File Copy 1024 bufsize 2000 maxblocks 1867.9 2321.6 24.3 2585.3 3212.9 24.3 File Copy 256 bufsize 500 maxblocks 1215.0 1541.3 26.9 1638.4 2022.6 23.4 File Copy 4096 bufsize 8000 maxblocks 3606.4 4197.4 16.4 5796.2 6794.8 17.2 Pipe Throughput 930.5 1324.7 42.4 3631.2 5160.1 42.1 Pipe-based Context Switching 461.5 808.9 75.3 2183.6 3025.1 38.5 Process Creation 748.4 948.6 26.8 2119.4 3300.8 55.7 Shell Scripts (1 concurrent) 2470.9 2650.7 7.3 5851.0 6175.6 5.5 Shell Scripts (8 concurrent) 4936.7 5300.6 7.4 6172.0 6613.4 7.2 System Call Overhead 1027.2 1435.3 39.7 3435.2 4247.1 23.6 基准程序几何平均得分 1438.8 1743.9 21.2 3698.4 4432.9 19.9
下载: 导出CSV
表 8 SPEC CINT2000 Train的运行时间比较
Table 8 Runtime Comparison of SPEC CINT2000 Train
测试程序 MIPS/s LATM/s LoongArch/s LoongArchLATM/% MIPSLATM/% 164.gzip 2063.2 1991.8 1695.1 85 104 300.twolf 691.2 670.9 549.0 82 103 255.vortex 416.1 431.9 437.5 101 96 176.gcc 156.4 182.1 161.5 89 86 253.perlbmk 1013.6 1007.5 922.6 92 101 253.perlbmk 1032.3 813.6 634.3 78 127 253.perlbmk 613.0 697.0 618.6 89 88 186.crafty 765.9 789.6 760.5 96 97 256.bzip2 1292.2 1196.7 1413.8 118 108 252.eon 38.2 39.5 32.1 81 97 252.eon 53.8 54.5 46.1 85 99 252.eon 206.7 214.3 179.1 84 96 197.parser 393.8 394.4 354.2 90 100 181.mcf 1474.5 1510.2 1553.7 103 98 175.vpr 575.0 570.3 466.4 82 101 175.vpr 605.5 529.5 502.9 95 114 254.gap 295.0 309.1 300.8 97 95 算术平均 687.4 670.7 625.2 91 101
下载: 导出CSV
表 9 QEMU和LATX翻译运行SPEC CPU2000的性能
Table 9 QEMU and LATX Performance of SPEC CPU2000
SPEC程序 QEMU分值 LATX分值 原生分值 QEMU原生/% LATX原生/% LATXQEMU/% 164.gzip 522 1122 1332 39.2 84.23 214.9 175.vpr 259 1454 2351 11.0 61.85 561.4 176.gcc 605 1982 3120 19.4 63.53 327.6 181.mcf 1990 3272 3567 55.8 91.73 164.4 186.crafty 425 1743 3017 14.1 57.77 410.1 197.parser 492 1537 2103 23.4 73.09 312.4 252.eon 81 1834 4194 1.9 43.73 2264.2 253.perlbmk 498 1676 2922 17.0 57.36 336.5 254.gap 497 1686 2512 19.8 67.12 339.2 255.vortex 537 2083 3550 15.1 58.68 387.9 256.bzip2 567 1466 2130 26.6 68.83 258.6 300.twolf 822 2012 2815 29.2 71.47 244.8 定点几何平均 485 1763 2692 18.0 65.50 363.5 168.wupwise 42 1883 2921 1.4 64.46 4483.3 171.swim 83 3462 5637 1.5 61.42 4171.1 172.mgrid 22 2158 3230 0.7 66.81 9809.1 173.applu 42 2255 2482 1.7 90.85 5369.0 177.mesa 104 1514 3451 3.0 43.87 1455.8 178.galgel 70 6739 6552 1.1 102.85 9627.1 179.art 187 6336 8962 2.1 70.70 3388.2 183.equake 72 3370 4606 1.6 73.17 4680.6 187.facerec 105 3279 4959 2.1 66.12 3122.9 188.ammp 44 2051 2748 1.6 74.64 4661.4 189.lucas 63 2521 3560 1.8 70.81 4001.6 191.fma3d 58 2427 3431 1.7 70.74 4184.5 200.sixtrack 10 905 1433 0.7 63.15 9095.0 301.apsi 57 2948 3569 1.6 82.60 5171.9 浮点几何平均 56 2630 3740 1.5 70.30 4697.0
下载: 导出CSV
-
[1] Loongson Technology Corp. Ltd. LoongArch architecture manual[EB/OL]. [2022-06-28]. https://www.loongson.cn/loongArch
[2] Loongson Technology Corp. Ltd. Loong3A5000 processor[EB/OL]. [2022-06-28]. https://www.loongson.cn/productShow/32
[3] Bellard F. QEMU, a fast and portable dynamic translator[C] //Proc of the 2005 USENIX Annual Technical Conf. Berkeley, CA: USENIX Association, 2005: 41−47
[4] Loongson Technology Corp. Ltd. Loongnix-20. LoongArch64[EB/OL]. [2021-03-31]. http://loongnix.cn
[5] Chernoff A, Herdeg M, Hookway R, et al. FX!32: A profile-directed binary translator[J]. IEEE Micro, 1998, 18(2): 56−64
[6] Baraz L, Devor T, Etzion O, et al. IA-32 execution layer: A two-phase dynamic translator designed to support IA-32 applications on Itanium-based systems[C] //Proc of the 36th Annual IEEE/ACM Int Symp on Microarchitecture. Piscataway, NJ: IEEE, 2003: 191−201
[7] Dehnert J C, Grant B K, Banning J P, et al. The Transmeta Code Morphing(TM) software: Using speculation, recovery, and adaptive retranslation to address real-life challenges[C] //Proc of the Int Symp on Code Generation and Optimization: Feedback-directed and Runtime Optimization. Piscataway, NJ: IEEE, 2003: 15−24
[8] Ebcioglu K, Altman E. DAISY: Dynamic compilation for 100% architectural compatibility[C] //Proc of the 24th Annual Int Symp on Computer Architecture. New York: ACM, 1997: 26−37
[9] Moore R W, Baiocchi J A, Hisor J D, et al. Addressing the challenges of DBT for the ARM architecture [C] //Proc of the 2009 ACM SIGPLAN/SIGBED Conf on Languages, Compilers, and Tools for Embedded System. New York: ACM, 2009: 147−156
[10] Mittal A, Bansal A, Sethi V, et al. Efficient virtualization on embedded power architecture platforms[C] //Proc of the 8th Int Conf on Architectural Support for Programming Languages and Operating Systems. New York: ACM, 2013: 445−458
[11] Ottoni G, Hartin T, Weaver C, et al. Harmonia: A transparent, efficient, and harmonious dynamic binary translator targeting the Intel architecture[C] //Proc of the 8th ACM Int Conf on Computing Frontiers. New York: ACM, 2011: 26:1−26:10
[12] Hu Weiwu, Wang Jian, Gao Xiang, et al. Godson-3: A scalable multicore RISC processor with x86 emulation[J]. IEEE Micro, 2009, 29(2): 17−29
[13] Hu Weiwu, Liu Qi, Wang Jian, et al. Efficient binary translation system with low hardware cost[C] //Proc of the IEEE Int Conf on Computer Design. Piscataway, NJ: IEEE, 2009: 305−312
[14] 胡伟武, 靳国杰, 汪文祥, 等, 龙芯指令系统融合技术[J]. 中国科学: 信息科学, 2015, 45(4): 459−479 Hu Weiwu, Jin Guojie, Wang Wenxiang, et al. Fusion technology of Loongson instruction set architecture[J]. SCIENTIA SINICA Informationis, 2015, 45(4): 459−479 (in Chinese)
[15] Wine. Wine[EB/OL]. [2021-03-21]. https://www.winehq.org
[16] Spink T, Wagstaff H, Frank B. A retargetable system-level DBT hypervisor[C/OL] //Proc of the 2019 USENIX Annual Technical Conf. USENIX Association, 2019: 505−520 [2022-03-01]. https://www. usenix.org/conference/atc19/presentation/spink
[17] Huang Kele, Zhang Fuxin, Li Cun. BTMMU: An efficient and versatile cross-ISA memory virtualization[C] //Proc of the 17th ACM SIGPLAN/SIGOPS Int Conf on Virtual Execution Environments. New York: ACM, 2021: 71−83
[18] SPEC. SPEC CPU benchmarks[EB/OL]. [2021-03-21]. https://www.spec.org
[19] McCalpin J. Stream v5.10[EB/OL]. [2021-03-01]. https://cs.virginia.edu/stream
[20] UnixBench. UnixBench v5.1.3[EB/OL]. [2021-03-21]. https://github.com/kdlucas/byte-unixbench/tree/master/UnixBench
-
期刊类型引用(1)
1. LUO Haoran，HU Shuisong，WANG Wenyong，TANG Yuke，ZHOU Junwei. Research on Multi-Core Processor Analysis for WCET Estimation. ZTE Communications. 2024(01): 87-94 . 
必应学术
其他类型引用(4)
计量
- 文章访问数: 1141
- HTML全文浏览量: 346
- PDF下载量: 512
- 被引次数: 5
