-
摘要:
近年来,大模型推动自然语言处理、机器视觉等众多领域取得前所未有的进展. 混合专家(mixture of experts,MoE)凭借在模型参数扩展、计算成本控制和复杂任务处理等方面的独特优势成为大模型的主流架构之一. 然而,随着参数规模的持续增长,系统的执行效率和可扩展能力愈发难以满足需求,亟待解决. 系统优化方法是解决这一挑战的有效途径,日益成为研究热点. 故综述大模型时代MoE系统优化技术的研究现状,首先介绍MoE大模型的发展现状,并分析其在系统端面临的性能瓶颈;然后从内存占用、通信延迟、计算效率和并行扩展4个系统核心维度对最新的研究进展进行全面梳理和深入分析,并对其中涉及的关键技术、适用场景和待优化方向进行详细对比阐述;最后总结MoE系统优化的研究现状,并展望未来研究方向.
Abstract:In recent years, large models have made unprecedented progresses in variety of domains, such as natural language processing and machine vision. Mixture of experts (MoE) has emerged as one of the most popular architectures for large models due to its distinct advantages in model parameter scalability, computational cost control and complex task processing. However, with the continuous increase of the parameter scale, the execution efficiency and scalability of the system are becoming increasingly challenging to meet the demand, and must be addressed urgently. The system optimization approach is an effective solution to solve this problem, which has become a hot research area. In light of this, we review the present research status of MoE system optimization techniques in the era of large model in this paper. To begin, we describe the present development state of work for MoE large model, and analyze the performance bottlenecks it faces on the system side. Then, we comprehensively sort out and deeply analyze the most recent research progress from four system core dimensions, ranging from memory occupation, communication latency, computational efficiency to parallel scaling, and compare and elaborate on the key technologies, application scenarios and optimization directions; finally, we summarize the current research state of MoE system optimization and outline some future research directions as well.
-
动态二进制翻译技术可以实现程序的模拟执行. 被模拟执行的客户机程序通过动态二进制翻译器(dynamic binary translator,DBT)运行在宿主机之上. 当客户机和宿主机的指令集架构不同时,动态二进制翻译技术可以实现跨架构的程序模拟执行. 二进制翻译的基本原理是将客户机代码翻译成语义等价的宿主机代码,通常以代码块为单位进行翻译. 代码块由一段地址连续、顺序执行的代码组成,通常以控制转移指令为结尾. 一个客户机代码块通过二进制翻译生成一个语义等价的宿主机代码块,本文称之为翻译代码块. 软件代码缓存负责存储翻译代码块,以便后续重复利用,降低动态翻译开销.
根据程序模拟的层次,DBT可分为用户级和系统级2类,其代码缓存的实现相近,都是存储翻译代码块以便复用. 不同的是翻译时指令语义模拟的实现,如表1所示. 用户级DBT可以假设客户机永远处于用户态,只需支持用户态指令. 系统级DBT则需要考虑客户机的各种状态,需要支持所有指令. 为保证系统正确运行,客户机指令语义模拟需要正确的实现. 以1条特权指令为例,若客户机处于低特权级,则需要翻译生成触发客户机异常的操作,而不能直接生成该条特权指令的执行语义,否则不仅会运行出错,还可能造成安全问题.
表 1 指令语义模拟的因素Table 1. Factors in Instruction Semantics SimulationDBT 客户机状态 指令范围 用户级 单一 用户态 系统级 复杂 全部 系统级DBT中语义模拟方案有2种:一种是动态检测方案,该方案在翻译代码块中生成判断当前客户机状态的宿主机代码,从而在运行时进行检测;另一种是状态标签方案,该方案在翻译时仅依据当前客户机状态,并将生成的翻译代码块的状态标记为当前客户机状态. 在翻译代码块执行前需进行对比,确保待执行的翻译代码块的状态与客户机状态一致. 详细介绍请见本文第2节.
出于性能的考虑,目前的系统级DBT均采用了状态标签方案,避免运行时开销. 但状态标签方案也会给软件代码缓存引入额外的问题. 本文详细分析了状态标签方案,总结了2类问题:一类是冲突问题,源于不同状态的翻译代码块存储在同一个代码缓存空间,导致空间利用率的下降和不必要的刷新;一类是冗余问题,源于不同状态的翻译代码块可能包含相同的宿主机代码,意味着多余的翻译开销和额外的空间占用. 详细分析请见本文第4节.
本文的主要贡献和创新有3点:
1)深入分析了系统级动态二进制翻译器中已有的指令语义模拟方案给软件代码缓存管理带来的问题,并将其总结为冲突问题和冗余问题;
2)针对这2类问题,提出了基于细粒度状态标签的代码缓存优化方案. 其中多状态代码缓存方案可以解决代码块冲突问题,减少重复的动态翻译开销;弱状态标签方案可以解决代码块冗余问题,减少冗余的动态翻译开销;
3)在真实的系统级动态二进制翻译器 LATX-SYS 中实现了这2个方案,并进行了详细的测试与分析. LATX-SYS基于QEMU[1]开发,可以在LoongArch[2]宿主机上运行 x86 客户机操作系统.
1. 相关工作
软件代码缓存的研究如表2所示,大多集中于用户级DBT,仅有多线程共享机制是针对系统级DBT.
表 2 软件代码缓存相关研究Table 2. Relative Research on Software Code Cache1.1 缓存替换策略
文献[3]对软件代码缓存的替换策略进行了一个详细的对比分析,认为全刷新策略和先进先出(FIFO)策略都是最优的,二者的缺失率都很低并且没有碎片化问题. 文献[4-8]均提出了粗粒度的刷新方式,与FIFO策略的结合被认为是各方面权衡之下最优方案. 文献[9]提出了选择性刷新策略,平衡了内存占用和性能,但又引入了碎片化问题.
1.2 持久性缓存
持久性缓存可以在相同程序的多次执行或不同程序的执行之间进行代码缓存的共享,以降低翻译开销和内存占用. 文献[10]最早对此问题进行了分析,统计了相同程序多次运行和不同程序之间的代码复用率. 此后出现若干持久性缓存的具体实现,文献[11-12]是基于PIN的实现,主要针对相同程序多次运行. 文献[13]是基于DynamoRIO的实现,进一步研究了特权代码共享的安全问题. 文献[14]是基于QEMU的实现,总结了此前方案的不足,实现了范围更大的持久性缓存. 文献[15]进一步提出了累积式持久性缓存,在多次运行中不断增加缓存的代码块,从而不断提高持久性缓存的命中率.
1.3 工作集和热代码
根据局部性原理,程序运行期间通常会呈现出阶段性的特征,即某段时间内的工作集是有限的,这种特征可以被二进制翻译器识别. Dynamo[16]提出了抢先式刷新策略,当发现程序可能出现工作集变迁时,便主动进行1次缓存刷新. 文献[17]在FIFO策略的基础上进行工作集变迁的检测,并动态地调整软件代码缓存容量. 文献[18]结合了这2种方案,提出了静态缓存和动态缓存. 静态缓存容量固定,在工作集变迁时提前进行刷新. 动态缓存容量可变,在工作集变迁时调整容量. 文献[4, 19]依据代码块的执行热度,将热代码存储在一个独立的空间中,从而自适应地识别工作集的变迁. 但统计执行热度需要付出额外开销.
1.4 硬件辅助机制
软硬件结合是提高性能的方式之一. 文献[20-21]提出了相应的硬件缓存机制来加速指令解码. 文献[22-23]在利用了嵌入式系统中的片上便签存储器,来加速代码缓存的访问. 针对代码块查找过程的加速,文献[24]提出了基于CAM和RAM的硬件查找表. 文献[25]则利用了数据缓存的部分空间来存储代码块的映射关系,并使用特殊的指令来加速查找.
1.5 优化内存占用
软件代码缓存会占用内存空间,而内存资源是有限的,尤其在嵌入式环境中. 文献[26]优化了控制转移的翻译,减少了翻译产生的代码量. 文献[27]发现出口代码占很大空间,并提出若干方案进行优化. 文献[28]针对二进制翻译器的各类辅助代码进行优化,包括跳转、间接跳转查找、上下文切换等等,减少内存占用. 文献[29]则针对超级块的构建,提出了可以平衡内存占用和整体性能的路径选择算法. 文献[30]针对代码块重叠问题进行了研究,提出了相应的解决方案来降低内存占用.
1.6 多线程共享机制
系统级DBT中软件代码缓存的研究集中于多线程共享机制. 在多核客户机的场景下,每个客户机核心可以使用1个宿主机线程进行模拟. 文献[31]使用线程私有代码缓存来保证性能. 文献[32]则对比了线程私有代码缓存和线程共享代码缓存,研究了内存和性能之间的平衡. 在线程共享代码缓存基础上,文献[33]提出了一个更高效的共享哈希表来加速访问,文献[34]将共享代码缓存进行分区,来实现多线程并行地代码块翻译. 不同架构的存储一致性模型也不同[35],文献[33]研究了客户机和宿主机的存储一致性模型不同时的正确性问题.
1.7 本文工作
本文的贡献体现在缓存替换策略和优化内存占用2个方面:一方面,多状态代码缓存方案区分了不同状态的代码块,各自独立进行刷新,避免了互相的冲突,减少了重复的动态翻译开销;另一方面,弱状态标签方案消除了部分状态带来的冗余代码块,降低了内存占用,减少了冗余的动态翻译开销.
2. 二进制翻译和指令语义模拟
2.1 二进制翻译
根据程序模拟的层次,可将DBT分为用户级和系统级. 图1展示了DBT所在的软硬件层次结构. 最底层为处理器等真实硬件环境,其上是宿主机操作系统,再上面是宿主机应用程序. DBT作为宿主机应用程序,向上提供客户机所需的模拟环境. 用户级DBT可以模拟客户机用户态指令,并提供客户机系统调用,实现客户机应用程序的模拟执行. 系统级DBT可以模拟所有客户机指令,并提供客户机硬件环境的模拟,实现客户机操作系统的模拟执行.
动态二进制翻译的基本执行流程如图2所示. 代码块查找阶段会搜索软件代码缓存,寻找是否已经存在所需的翻译代码块. 若找到,则进入代码块执行阶段,执行这个翻译代码块. 若未找到,则进入代码块翻译阶段,读取客户机二进制,翻译产生对应的翻译代码块,并存储到软件代码缓存中,随后回到代码块查找阶段,便可以找到刚刚产生的翻译代码块,从而继续执行. 代码块执行完成后,回到代码块查找阶段,继续寻找下一个需要执行的翻译代码块.
软件代码缓存是一块用于存储翻译代码块的内存空间. 随着程序的持续运行,翻译代码块会不断产生,而软件代码缓存的空间有限,因此需要替换策略. 表3对比了三种常见的替换策略. 全刷新策略在代码缓存空间用尽时,会清空整个空间,然后继续存储新的翻译代码块. 全刷新的优势在于实现简单、刷新操作更快,劣势是复用率较低、动态翻译开销更大. 先进先出(FIFO)策略会优先把最老的翻译代码块无效掉,腾出空间给新的翻译代码块. FIFO的优势在于可以尽可能复用已有的翻译代码块,劣势在于无效翻译代码块的操作较为复杂,且由于代码块长度不一,可能需要多次刷新才能获取足够的空间. 这2种方案共同的优势是没有碎片化问题,有利于简化逻辑、降低刷新开销. 这2种方案结合,也被认为是目前最好的方案,即粗粒度的FIFO策略. 该策略的一次刷新操作会无效掉某个地址范围内的所有翻译代码块.
表 3 替换策略的比较Table 3. Comparison of Replace Strategy替换策略 复用率 碎片化 刷新操作 全刷新 低 无 简单 FIFO 高 无 复杂 粗粒度FIFO 较高 无 适中 代码块执行阶段中一个典型的优化是代码块链接. 如果每次执行完1个翻译代码块,都需要进行1次代码块查找,那么整体性能就会很低. 而客户机基本块的结尾常常是直接跳转指令,其跳转目标是确定的,意味着在当前翻译代码块(记为A)执行完后,下一个待执行的翻译代码块(记为B)也是确定的. 代码块链接会修改A的结尾处代码,使A执行完后不再退出执行,而是跳转到B继续执行. 若客户机基本块的结尾是间接跳转指令,此时跳转目标是不确定的,只有在每次执行后才可知,此时代码块查找是必要的.
2.2 指令语义模拟
为保证正确性,DBT需要模拟客户机指令的正确语义. 指令执行语义常常与执行时的处理器状态有关,若状态不同,则指令的行为可能完全不同. 在用户级DBT中,通常认为客户机一直处于用户态,此时用户态指令的行为一般是固定的. 而在系统级DBT中,则需要考虑客户机所有可能的状态,且需要模拟所有的客户机指令,包括用户态指令和特权态指令.
系统级DBT在模拟客户机指令语义时有2种方案,即动态检测方案和状态标签方案. 动态检测方案在翻译代码块运行时对客户机状态进行动态检测. 具体来说,代码块翻译阶段负责生成读取并判断当前客户机状态的宿主机代码,以及依据判断结果执行对应宿主机代码的选择逻辑. 代码块执行阶段负责执行翻译代码块,从而动态地检测客户机状态并执行对应的指令行为. 状态标签方案在进入执行阶段之前进行检测. 具体来说,在代码块翻译阶段中,依据当前客户机状态,在翻译代码块中仅生成当前状态下客户机指令的执行行为,并将翻译代码块的状态标记为当前客户机状态. 在代码块查找阶段中,将翻译代码块的状态与客户机状态进行对比,只有相同的情况下才能进入代码块执行阶段,否则便是查找失败,进入代码块翻译阶段,生成当前客户机状态下的翻译代码块.
本文以x86客户机指令FADD和客户机状态EM为例,描述2种方案的基本原理. 当客户机状态EM=1时,FADD触发浮点异常. 当客户机状态EM=0时,FADD执行浮点加法操作. 为了便于说明和理解,本例中客户机基本块仅包含1条客户机指令FADD,且仅考虑客户机的EM状态.
图3展示了指令语义模拟的动态检测方案. 首次执行时,在代码块查找阶段查询失败,进入代码块翻译阶段,随后生成的翻译代码块的开头位置包含了读取和判断客户机状态的代码,以及2种不同的执行行为. 在代码块执行阶段,根据客户机状态不同,该翻译代码块的执行行为不同. 当客户机状态EM=1时,读取和判断当前客户机状态后,执行触发客户机异常的操作. 相应地,当客户机状态EM=0时,执行浮点加法操作. 由此可见翻译代码块中的宿主机代码模拟了该指令在不同客户机状态下的不同行为,保证了正确的客户机指令语义.
图4展示了指令语义模拟的状态标签方案. 首次执行时代码块查找失败,进入代码块翻译阶段,此时客户机状态EM=1,翻译代码块A中仅包含触发客户机异常的宿主机代码,且翻译代码块A的状态标签中EM状态会被标记为1. 在代码块查找阶段,会依据当前客户机状态进行判断. 对于翻译代码块A,当客户机状态EM=1时,二者状态一致,认为查询成功,可以执行;当客户机状态EM=0时,二者状态不同,认为查询失败,则进入代码块翻译阶段. 此时在客户机状态EM=0时会翻译生成仅包含执行浮点加法操作的翻译代码块,且其状态标签中EM会被标记为0. 由此可见,翻译代码块的状态标签描述了其所需的执行条件,从而保证正确的客户机指令语义.
动态检测方案和状态标签方案均能实现指令语义的正确模拟,但也都存在不足之处. 在代码块翻译阶段,动态检测方案总是会生成该指令的所有行为,使得代码膨胀率较高,增加软件代码缓存和硬件指令缓存的压力. 状态标签方案仅在需要执行时才会生成相应的指令行为,消除了不必要代码,但代码块的数量会更多. 在代码块执行阶段,动态检测方案下,每次执行时都会至少进行1次读取和判断操作,意味着更多的运行时开销,从而降低整体的性能表现. 状态标签方案需要在运行前进行1次额外的检查逻辑,但运行时无需额外的检测,避免了翻译代码块的运行时开销,有利于提高整体性能.
二进制翻译器所面临的一个重要问题是性能问题,尤其是系统级DBT. 目前已有的系统级DBT均采用了状态标签方案.
3. 软件代码缓存问题分析
状态标签方案通过对翻译代码块添加对应的客户机状态标签,来避免动态检测的开销. 此时对于同一个客户机代码块,软件代码缓存中可能会存在多个状态标签互不相同的翻译代码块. 本文对该现象进行深入的研究分析,总结出了2个问题:一个是冲突问题,表现为不同状态的翻译代码块存储在同一个软件代码缓存空间中,在存储、链接和刷新时会互相冲突,降低空间利用率;一个是冗余问题. 对于来自同一个客户机代码块的多个翻译代码块,尽管它们的状态标签不同,但其内部的宿主机代码可能是相同的,意味着存在额外的翻译开销和冗余的内存占用.
3.1 代码块冲突问题
冲突问题源于不同状态标签的翻译代码块存储于同一个代码缓存空间中. 典型的客户机状态是特权级. 对于一个包含特权指令的客户机基本块,在客户机状态处于用户态时,生成的翻译代码块中应当包含触发客户机异常的行为. 当客户机处于特权态时,生成的翻译代码块中应当包含该特权指令的正常执行行为. 图5展示了 Ubuntu/x86 16.04 系统在启动阶段中代码缓存中2种状态的翻译代码块的分布. 横坐标是软件代码缓存FIFO区域的编号,每个FIFO区域容量为4 MB,共有32个,总容量128 MB. 纵坐标是翻译代码块数量. 系统启动阶段最初执行的是引导程序和内核初始化程序,客户机处于特权态,因此仅包含特权级翻译代码块. 当第一个用户程序开始运行后,逐渐出现用户级翻译代码块. 此时2种翻译代码块交错地存储在软件代码缓存中. 图6展示了系统启动阶段完成后,软件代码缓存中代码块的分布情况. 随着用户程序的执行和软件代码缓存的刷新,用户级翻译代码块和特权级翻译代码块交错地分布在整个软件代码缓存空间中.
从代码块分布的角度来看,同一状态的代码块是比较分散的. 而当客户机处于某个状态下时,只能执行该状态下的翻译代码块,但这些代码块分散地存储在整个软件代码缓存空间中,程序执行的局部性不够好,增加了硬件指令缓存的压力.
从软件代码缓存的容量限制来看,同一空间中存储不同状态的翻译代码块是低效的. 在部分架构下,受限于直接跳转指令的范围,如MIPS架构中直接跳转指令的范围是±128 MB,为了支持代码块链接机制,软件代码缓存的容量被限制在128 MB. 然而不同状态的翻译代码块之间并不能直接跳转,因此将它们存储在相同的空间中反而是不必要的.
从软件代码缓存的替换策略来看,对于粗粒度的刷新策略,1次刷新操作会无效掉若干翻译代码块,其中包含多种状态的翻译代码块. 如图6所示,一个FIFO区域内既有特权级翻译代码块,也有用户级翻译代码块. 2种翻译代码块的执行情况并不相同,共同进行刷新是不合理的. 实际上,客户机操作系统在运行中,执行的用户程序数量多、种类多,而操作系统始终只有一个,且部分系统代码会经常运行,如异常和中断处理程序.
我们将翻译代码块被无效后又重新翻译生成的行为称为代码块的重翻译,并在128 MB软件代码缓存中,基于4 MB粒度的FIFO刷新策略,统计了Ubuntu/x86 16.04系统启动过程中的重翻译情况,如图7所示. 总共收集了80次FIFO刷新时的数据,每10次进行合并统计,同时也对全部80次进行了合计. 我们进一步定义了重翻译距离. 对于一个翻译代码块的重翻译行为,重翻译距离为N表示:当它所在的FIFO区域刷新后,又经过了N次FIFO刷新,然后该翻译代码块被重新生成. 重翻译距离的范围是0~31,大于等于32意味着整个软件代码缓存都被刷新过,因此不予统计. 特别地,重翻译距离为0意味着该翻译代码块被刷新后,立刻在原FIFO区域内重新翻译生成.
图7(a)(b)展示了特权级翻译代码块的重翻译情况. 图7(a)为代码块的重翻译率. 总的来看,对于被刷新的特权级翻译代码块,高达60%会在后续运行中重新翻译生成. 图7(b)展示了重翻译距离的分布. 总的来看,重翻译距离为0的情况占比高达46%,也就是说有将近一半的特权级翻译代码块在被刷新后立刻就重新生成了. 重翻译距离为1~4的情况占比 24%,重翻译距离5~12的情况占比13%. 总的来说,重翻译距离在12以内的情况占比高达83%.
图7(c)(d)展示了用户级翻译代码块的重翻译情况. 由于系统启动最初阶段均是系统代码,因此第1列并没有用户态的数据. 图7(c)展示了重翻译率. 对于被刷新的用户级翻译代码块,总共有45%会重翻译,明显低于特权级翻译代码块的重翻译率. 图7(d)展示了重翻译距离的分布. 对于被刷新的用户级翻译代码块,重翻译距离为0的情况仅占22%,而大于12的情况占比高达 41%,也就是说用户级翻译代码块被刷新后往往不会立刻重翻译,而是运行一段时间后才可能会重翻译.
3.2 代码块冗余问题
冗余问题源于同一客户机基本块对应的多个状态标签不同的翻译代码块可能包含相同的宿主机指令. 完整的状态标签中包含了多种客户机状态信息,可能会导致代码块冗余问题.
我们发现了导致x86客户机出现大量代码块冗余的客户机状态. 在x86架构的处理器中有3个与浮点和向量指令的标志位,分别是MP,EM,TS. 为了便于描述,我们将这3个标志统称为浮点向量控制状态. 当该状态开启时,浮点和向量指令的执行会触发异常. 当该状态关闭时,浮点和向量指令可以正常执行. 如表4所示.
表 4 浮点向量控制状态Table 4. Floating and Vector Control Status浮点向量控制状态 浮点向量指令行为 开启 触发异常 关闭 正常执行 x86架构通过这个机制来提供针对浮点和向量上下文的延迟处理,当客户机使用该机制时,同一段客户机程序既可能会运行在该状态启动的情况下,也可能会运行该状态关闭的情况下. 而当一个客户机代码块不包含浮点和向量指令时,其执行行为与浮点向量控制状态是无关. 在状态标签方案下,同一个客户机代码块会对应多个浮点向量控制状态不同的翻译代码块,而它们的宿主机指令可能是相同的,因此造成了代码块的冗余.
我们将来自同一个客户机基本块的多个状态标签不同的翻译代码块定义为一个相似组. 更进一步的,我们将一个相似组中宿主机代码也相同的多个翻译代码块定义为一个冗余组. 一个相似组的相似数定义为该组内翻译代码块的数量,而一个冗余组的冗余数定义为该组内翻译代码块的数量减1,即认为至少有1个翻译代码块是必要的,其余的则是冗余的. 对于某个时刻下软件代码缓存,定义相似率为所有相似组的相似数的和与代码块总数的比值,定义冗余率为所有冗余组的冗余数的和与代码块总数的比值. 根据定义可知,冗余率的上限是相似率的一半. 相应地,非冗余率即为1减去冗余率,非相似率即为1减去相似率. 同时,相似非冗余率即为相似率减去冗余率.
表5展示了一个代码缓存的示例. 客户机代码块A产生了3个翻译代码块A1,A2,A3,对应一个相似组,其相似数为3. 客户机代码块B和C均仅产生了1个翻译代码块,因此不构成相似组. 翻译代码块A1和A2的宿主机指令完全相同,构成一个冗余组,且冗余数为1. 总的来说,代码缓存的冗余率为20%,非冗余率为80%,相似率为60%,相似非冗余率为40%.
表 5 冗余率示例Table 5. Example of Redundancy Ratio客户机代码块 翻译代码块 状态标签 宿主机指令 A A1 ST1 CS1 A2 ST2 CS1 A3 ST3 CS3 B B1 ST4 CS4 C C1 ST5 CS5 图8展示了Windows XP/x86系统在启动过程中某些时刻下,软件代码缓存中的相似和冗余情况. 横坐标使用FIFO刷新次数表示系统运行时间,纵坐标为代码块数量. 平均而言,软件代码缓存的相似率达到60%,冗余率则高达28%. 此处只统计了浮点向量控制状态带来的冗余,详细介绍见4.2节.
4. 设计与实现
我们总结了状态标签方案造成的2类问题:一类是冲突问题;一类是冗余问题. 本文针对这2类问题,分别提出了2种基于细粒度状态标签的解决方案. 这2种方案并不冲突,可以共存来同时解决这2类问题. 针对冲突问题,本文主要解决了由特权级状态带来的代码块冲突情况. 针对冗余问题,本文主要解决了由浮点向量控制状态带来的代码块冗余情况. 本质上来说,本文提出的方案并不局限于特权级状态和浮点向量控制状态,对客户机也不局限于x86架构. 对于任何带来代码块冲突和冗余的客户机状态,本文的方案均被使用来解决相应的问题.
4.1 多状态代码缓存
代码块冲突问题的根源在于不同状态的翻译代码块存储在同一个软件代码缓存中,因此解决的方式是将不同状态的翻译代码块存储于不同的软件代码缓存空间,避免互相冲突. 本文提出了多状态代码缓存,支持将特权级代码块和用户级代码块存储于不同的代码块缓存空间中. 区别于其他将代码缓存空间分割的方案,该方案设计的多个代码缓存空间考虑的是系统级DBT特有的代码块状态标签,依据状态的不同来分别存储. 因此该方案与其他代码缓存空间的方案是兼容的,例如文献[2]提出的根据代码块的执行热度来分别存储生命周期较短的代码块和生命周期较长的代码块,但该方案需要付出额外的开销来统计执行热度.
图9展示了针对特权级的多状态代码缓存方案. 针对 x86的0特权级和3特权级,分别设计了特权级缓存和用户级缓存. 特权级缓存用于存储特权级翻译代码块,对应客户机的操作系统代码. 用户级缓存用于存储用户级翻译代码块,对应客户机的用户程序代码. 在多状态代码缓存的基础实现中,2个代码缓存空间的容量都是128 MB,且均采用4 MB粒度的FIFO刷新策略. 当客户机运行操作系统时,代码块的执行、查找和翻译均发生在特权级缓存中. 当客户机运行用户程序时,代码块的执行、查找和翻译均发生在用户级缓存中.
需要注意的是,x86 的特权级并不只有0和3,还有1和2. 若客户机操作系统使用了1特权级和2特权级,也可以进一步增加相应特权级的代码缓存空间. 通常来说,x86操作系统只使用了3特权级和0特权级,分别对应特权态和用户态,因此本文只处理了0和3这2个特权级. 更进一步的说,支持Intel VT-X扩展的x86处理器还拥有一个特殊的non-root模式,属于x86架构的硬件虚拟化特性. 若x86架构的客户机操作系统中运行了使用硬件虚拟化的程序,此时也可能会存在状态为non-root的翻译代码块. 在多状态代码缓存方案下,可以将此类翻译代码块存储于独立的空间,与root状态的翻译代码块区分开.
从代码块执行的角度来看,处于某个特权级状态下的客户机,例如用户态,通常只会运行用户程序代码,即运行在用户级缓存中,此时缓存空间中全部都是用户级翻译代码块,因此有着更好的指令局部性,有利于硬件的指令预取. 此外,用户级缓存中不再负责存储特权级翻译代码块,也就有了更多的空间来存储用户级翻译代码块,有利于提高代码块查找命中率,降低动态翻译开销. 相应地,多状态代码缓存方案需要更多的内存空间来支持多个软件代码缓存空间. 若受限于内存容量,或设计了过多的软件代码缓存空间,使得单个代码缓存空间的容量过低,反而可能会造成大量的代码块查找缺失,进而产生更多的动态翻译开销,总体上反而会降低性能. 因此缓存空间的数量和各自的容量需要有着合理的设计.
4.2 弱状态标签
代码块冗余问题表现为不同状态的翻译代码块却有着相同的宿主机代码. 该问题的根源在于客户机状态的不同并不一定会导致客户机指令行为的不同. 本文提出了弱状态标签方案,并针对x86架构的浮点向量控制状态进行了的实现,消除了由该状态导致的冗余代码块.
图10展示了浮点向量控制状态导致冗余代码块的示意图. 客户机基本块A包含2条客户机指令,分别是定点指令和浮点指令. 在浮点向量控制状态关闭时,基本块A会生成翻译代码块A1并将状态标签中浮点向量控制状态记录为关闭. A1中的宿主机指令负责完成对应的定点和浮点操作. 在浮点向量控制状态开启时,基本块A会生成翻译代码块A0并将状态标签中浮点向量控制状态记录为开启. A0中的宿主机指令首先完成对应的定点操作,因为定点指令的行为不受影响,而浮点指令对应的则是触发客户机异常. 可见代码块状态标签发挥了作用,正确地处理了浮点指令在不同客户机状态下的不同行为,此时翻译代码块A1和A0都是必要的.
客户机基本块B包含2条客户机定点指令. 因为定点指令不受浮点向量控制状态的影响,因此无论客户机的浮点向量控制状态是开启还是关闭,定点指令的行为是不变的,因此对应的翻译代码块B1和B0中的宿主机指令便是相同的. 此时翻译代码块B1和B0只有状态标签不同,但却有着相同的宿主机指令,因此是存在冗余的. 对于客户机的某种状态S,若一个基本块中不包含受该状态影响的指令,我们将其称之为S无关基本块,反之则称为S相关基本块. 客户机基本块B便属于浮点向量控制状态无关基本块,客户机基本块A则属于浮点向量控制状态相关基本块.
针对代码块冗余问题,我们提出了弱状态标签方案,在保证客户机指令语义模拟的正确性的前提下,可以消除由特定状态导致的冗余代码块. 弱状态标签方案的基本思想是将导致冗余的状态S*在翻译代码块的状态标签中进行弱化,从而消除客户机状态S*对S*无关基本块的影响,进而避免冗余代码块的产生. 为保证客户机指令语义模拟的正确性,弱状态标签方案引入了额外的动态检测机制来避免出错. 根据检测的粒度不同,可以分为2种实现方案:一种是基于代码块的弱状态标签方案;一种是基于指令的弱状态标签方案. 本文实现了针对浮点向量控制状态进行弱化处理的弱状态标签方案.
图11描述了基于代码块的弱状态标签方案. 仍然以基本块A和基本块B为例. 对于基本块A的翻译,仍会生成翻译代码块A1和A0且状态标签中仍然包含客户机当前的浮点向量控制状态信息. 对于基本块B的翻译,则只会生成翻译代码块B2,其状态标签中不再包含浮点向量控制状态信息. 由此实现了冗余代码块的消除.
为保证正确性,此时翻译代码块会包含一个额外的标记,来记录对应的基本块与浮点向量控制状态是相关的还是无关的. 基本块A是浮点向量控制状态相关基本块,因此源于基本块A的翻译代码块,即翻译代码块A1和A0,都会被标记为相关. 相应地,源于基本块B的翻译代码块B2会被标记为无关. 在代码块查找阶段,根据此标记来决定是否需要检查浮点向量控制状态. 若相关,则需将翻译代码块的状态标签中记录的浮点向量控制状态与客户机当前的浮点向量控制状态进行比较,不一致时认为查询失败. 若无关,则不必进行该检查.
代码块链接允许执行流从一个翻译代码块直接跳转到另一个翻译代码块,可以减少上下文切换和代码块查找的开销,是二进制翻译器提高性能的关键. 在原本的代码块状态标签方案中,为保证正确性,只允许相同状态标签的翻译代码块进行链接. 而在基于代码块的弱状态标签方案中,部分翻译代码块被消除,状态标签的含义也有所改变,因此需要新的规则来指导代码块链接.
我们以A0*,A1*,B2*表示3类翻译代码块,类比于图11中的翻译代码块A0,A1,B2,这3类分别是:1)标记相关且状态标签为开启;2)标记相关且状态标签为关闭;3)标记无关的3类翻译代码块. 表6展示了所有的代码链接情况. 从A0*直接跳转到其他翻译代码块的情况是无需关心的,因为A0*会触发客户机异常进而退出代码块执行. A1*不能直接跳转到A0*的原因是二者的状态标签不同,此规则和原状态标签方案保持一致. 值得注意的是从B2*直接跳转到A0*,A1*是不允许的,因为当B2*正在运行时,当前客户机的浮点向量控制状态是不确定的. 若代码块链接使B2*直接跳转到A0*,那么在客户机浮点向量控制状态关闭时会出错,A0*对应的浮点指令本应正常执行却错误地触发了客户机异常. 相应地,若允许B2*直接跳转到A1*,则可能使A1*对应的浮点指令在本应触发客户机异常的时候却正常执行. 反之,A1*和B2*都是可以直接跳转到B2*的,因为B2*的行为与浮点向量控制状态无关.
表 6 代码块链接情况分析Table 6. Analysis of Code Block Link Cases直接跳转 跳转情况 无需关心 A0*→A0*,A0*→A1*,A0*→B2* 允许 A1*→A1*,B2*→B2*,A1*→B2* 不允许 A1*→A0*,B2*→A0*,B2*→A1* 为在代码块链接的情况下保证正确性,我们设计了基础方案和优化方案. 基础方案只是简单地不允许可能出错的代码块链接情况,尽管这可能会带来较高的性能损失. 优化方案如图12所示,我们引入了一定程度的动态检测机制,基本思想是在翻译代码块的起始位置生成一段检查客户机浮点向量控制状态的操作,若状态检测通过则继续执行,若失败则退出执行. 实际上,只有A1*和A0*这2类翻译代码块需要动态检测,B2*不需要,而且B2*无需在翻译代码块中生成检测代码,从而减少内存占用. 进一步地,我们只需要针对B2*到A0*,A1*这2种情况进行动态检查,从而尽可能地降低动态开销,为此每个翻译代码块设置了2个入口地址,检测入口对应状态检测代码,执行入口则跳过了状态检测.
图13描述了基于指令的弱状态标签方案. 此方案下所有翻译代码块的状态标签中都不再包含浮点向量控制状态的信息,从根本上消除了冗余代码块. 为确保正确性,我们需要修改受影响的浮点指令和向量指令的翻译过程. 对于客户机基本块A,浮点指令的翻译结果中会首先进行客户机状态检测,此时只需检测浮点向量控制状态即可. 根据检测结果,选择正常执行浮点操作,或者触发客户机异常,从而正确地完成指令语义模拟. 在代码块链接过程中,不再关心浮点向量控制状态,只需检查其他状态是否相同即可.
尽管翻译代码块中的状态标签不再包含浮点向量控制状态的信息,但对于当前客户机状态的维护上还是需要处理该状态,以便进行动态检测. 基础方案下,我们针对每条浮点和向量指令都生成了状态检测代码,实现简单,但会带来较大的内存占用和性能开销. 通过观察指令的行为,我们进一步实现了优化方案. 对于浮点向量控制状态,其只会导致受影响指令有2种行为,要么正常执行,要么触发客户机异常. 而在触发客户机异常时,执行流会直接退出代码块执行阶段. 对于同一个基本块中的多条指令,若前面的已经进行了状态检测,那么后续指令可以不必再进行检测,从而降低代码量和动态开销. 需要说明的是,实际上本文所述的浮点向量控制状态对应x86架构中MP,EM,TS这3个标记位,不同指令的状态检测行为也有所不同,具体实现中只能针对相同的状态检测行为进行处理,才能保证正确性.
从本质上讲,弱状态标签方案是原有的2种指令语义模拟方案的结合,即在动态检测和状态标签之间寻找平衡,引入一定的动态开销的同时,可以极大地降低由部分特殊的状态标签所导致的冗余代码块,从而减少不必要的动态翻译开销,减少内存占用,缓解软件代码缓存的压力. 我们发现x86架构下的浮点向量控制状态是非常适合该方案的一种场景. 一方面,用户程序的同一段代码既可以运行在该状态开启时,也可以运行在该状态关闭时,意味着同一个客户机基本块会对应多个不同状态的翻译代码块,其中可能存在冗余情况. 另一方面,很多用户程序没有或仅有少量的浮点和向量指令,且包含浮点和向量指令的代码所在的位置通常比较接近,这就有利于我们尽可能地降低所需的动态检测开销. 相对来说,客户机的特权级状态并不适合该方案,因为不同特权级下执行的通常是不同的程序,也就不存在冗余问题.
5. 实验测试
我们在系统级动态二进制翻译器LATX-SYS中实现并测试了本文提出的2种方案. LATX-SYS基于QEMU 6.0.0开发,自研了效率更高的LATX翻译引擎,能够在LoongArch[34]宿主机平台实现完整x86架构操作系统的模拟运行. 表7展示了实验配置信息.
表 7 实验配置Table 7. Experiment Configuration系统层次结构 实验配置 客户机测试程序 系统启动、SPEC CPU2000 客户机操作系统/x86 Windows XP,Ubuntu 16.04 系统级DBT LATX-SYS 宿主机操作系统 Loongnix(Linux 4.19内核) 宿主机硬件平台 3A5000 LoongArch 处理器 所有测试的基准配置是LATX-SYS配备单个容量为128 MB的软件代码缓存. 基准的替换策略是4 MB粒度的FIFO刷新策略,优于QEMU自身所使用的简单的全刷新方案. 基准的指令语义模拟采用状态标签方案,实现上与QEMU保持一致.
针对代码块冲突问题,我们主要观察了代码块分布情况,并对关键数据进行了统计. 针对代码块冗余问题,我们主要分析了软件代码缓存的冗余率. 我们选择了Windows XP/x86和 Ubuntu/x86 16.04这2种客户机操作系统,主要测试了系统启动阶段,因为启动阶段的代码量较大,会产生大量的翻译代码块,从而对软件代码缓存管理带来较大的压力. 此外,为了进一步测试弱状态标签方案带来的动态开销,我们基于SPEC CPU2000性能测试集进行了测试.
不同的客户机操作系统在是否使用浮点向量控制状态上有所区别. 在Linux系统上我们选择了3.10和4.14这2个版本. Linux 3.10版本可以使用内核参数来配置客户机使用该状态来实现延迟上下文切换. Ubuntu 16.04默认的Linux 4.14版本中删除了这个配置选项,即不再支持延迟上下文切换. 而Windows XP系统则默认使用了该状态来实现延迟上下文切换.
5.1 代码块分布
我们在基准配置的基础上,实现了针对特权级的多状态代码缓存,包含2个软件代码缓存空间,分别是用户代码缓存和特权代码缓存,容量均为128 MB且均采用4 MB粒度的FIFO刷新策略. 我们测试了Ubuntu 16.04在使用Linux 4.14内核的启动过程,代码块的分布情况见图14和图15.
相比于图5和图6所示的基准配置下代码块分布情况,多状态代码缓存中特权级翻译代码块和用户级翻译代码块互不干扰,各自拥有独立的空间. 随着系统运行,软件代码缓存的FIFO刷新也在各自的空间中进行. 当客户机执行用户程序时,软件代码缓存管理的刷新操作只会作用在用户代码缓存上,也就只会无效掉用户级翻译代码块,而不会无效掉特权级代码块. 根据前文的统计,特权级代码块具有更高的重翻译率,将其无效反而会带来额外的开销.
我们进一步统计了软件代码缓存的一些关键操作,包括刷新次数和翻译次数,详细数据见表8. 替换测试同为4 MB粒度的FIFO刷新策略,多状态代码缓存下总FIFO刷新次数降低了44%,刷新开销得到极大降低. 在翻译代码块的刷新次数上,总次数下降了43%,符合FIFO刷新次数的降低. 进一步看,用户级翻译代码块的刷新次数降低了20%,而特权级翻译代码块的刷新次数降低了100%. 因为多状态代码缓存下,用户程序执行时只会操作用户代码缓存,不会干扰特权代码缓存,且特权级翻译代码块总量不多,足以完全容纳在独立的128 MB空间中. 在代码块翻译次数上,总次数降低了18%. 得益于独立的空间,特权级翻译次数降低了48%. 用户级翻译次数只降低了6%,低于用户级刷新次数降低的20%,这是因为系统启动阶段有大量用户程序执行,因此更倾向于执行新的用户代码,被刷新的用户级翻译代码块更倾向于不被重翻译. 该结果也与图7中展示的翻译代码块的重翻译率相吻合,即特权级翻译代码块有更高的重翻译率,对其减少刷新会极大降低翻译次数,而用户级翻译代码块的重翻译率更低,对其减少刷新所带来的翻译次数的下降也会相对更少.
表 8 代码缓存操作的对比Table 8. Comparison of Code Cache Operations统计类别 基准 多状态代码缓存 降低比例/% FIFO刷新次数 87 49 44 代码块
刷新总次数 563 491 319 041 43 用户级 399 310 319 041 20 特权级 164 181 0 100 代码块
翻译总次数 769 473 633 962 18 用户级 563 021 526 799 6 特权级 206 452 107 163 48 软件代码缓存的容量是一个重要因素,而多状态代码缓存下相当于将总容量扩大了,从而极大地减少了刷新和翻译次数. 为了更好地体现不同状态代码块之间冲突降低带来的提升,我们进一步测试了在总容量相同的情况下,多状态代码缓存的具体情况. 总容量设置为128 MB与基准相同,特权代码缓存与用户代码缓存的容量比例是一个重要参数,容量调整的粒度是4 MB,与FIFO刷新的粒度一致.
图16展示了不同容量比例下,多状态代码缓存的代码块翻译次数. 横坐标为特权代码缓存的容量占比,纵坐标为代码块翻译次数. 最好的情况下,总翻译次数为728 979,此时特权代码缓存容量为40 MB,用户代码缓存容量为88 MB. 图16中2条横线来自表8,实线表示基准方案的翻译次数769 473,虚线表示多状态代码缓存的翻译次数633 962. 由此可见在总容量相同的情况下,合适比例的多状态代码缓存也会优于基准方案. 然而,如果任意一个代码缓存容量过低,都会造成严重的空间不足,进而导致代码块的刷新次数和翻译次数都很高.
5.2 代码块冗余
我们在基准配置的基础上实现了弱代码标签方案,针对浮点向量控制状态进行冗余代码块的消除. 在实际测试中,我们进一步区分了特权级翻译代码块和用户级翻译代码块,如表9所示. 在基准配置的基础上,仅针对用户级翻译代码块进行冗余消除的记为弱状态标签方案W1,而针对所有的翻译代码块进行冗余消除的记为弱状态标签方案W2.
表 9 代码块冗余测试方案Table 9. Testing Schemes for Code Block Redundancy测试方案 冗余消除范围 基准 未消除 弱状态标签方案W1 针对用户级代码块 弱状态标签方案W2 针对所有的代码块 图17展示了Windows XP系统启动过程中代码缓存的相似率,包括了3个运行阶段. 图17(a)初始阶段中,基准的相似率高达55%,其中特权级相似率达到了38%,因为初始阶段有大量系统代码. 弱状态标签方案W1下相似率降低至34%,弱状态标签方案W2进一步降低到13.73%. 因为具体实现中只处理了浮点向量控制状态,其他状态仍可能导致相似代码块,进而可能产生一定程度的冗余. 图17(b)启动桌面过程中,基准的相似率达到了60%,用户级和特权级都较高. 弱状态标签方案W1降低至18%,弱状态标签方案W2进一步降低至5%,此时用户级和系统级的相似率都很低,意味着大量的冗余是浮点向量控制状态所导致的. 图17(c)进入桌面后,用户进行的操作是点击开始菜单,此时基准的相似率达到30%,用户级,用户级相似率高达19%,意味着此时主要在执行用户程序. 弱状态标签方案W1降低至16%,用户级相似率降至1%. 弱状态标签方案W2进一步降低至3%,绝大部分冗余代码块被消除,只剩下少量由其他状态导致的相似代码块,其中存在些许冗余.
图18展示了Windows XP启动过程中代码缓存相似率的变化情况,记录了从系统启动到进入桌面的整个过程. 横坐标为运行时间,表现为FIFO刷新次数,从而体现软件代码缓存的变化. 特别地,横坐标为0指的是软件代码缓存首次存满的时候.
根据图18可知,基准方案共经历了124次FIFO刷新,代码缓存相似率明显很高,最高处接近70%. 弱状态标签方案W1已有大幅下降,共经历84次FIFO刷新,代码缓存相似率在30%左右,最终降至20%以下. 弱状态标签方案W2只在系统启动初始阶段较高,这是因为初始阶段有固件代码和初始化的系统代码,客户机状态更加复杂,而我们的实现只处理了浮点向量控制状态,其他状态仍可能导致代码块相似. 最终弱状态标签B的代码缓存相似率降低至不到5%,消除了绝大部分冗余代码块.
5.3 综合测试
多状态代码缓存可以避免不同状态代码块之间的冲突,减少不必要的刷新,从而减少了重复的翻译. 弱状态标签可以消除特定状态带来的冗余代码块,从而减少了冗余的翻译. 二者都可以减少动态翻译次数,降低软件代码缓存管理的压力,具体表现是在相同的客户机程序下,总的代码块翻译次数会有所下降. 我们对这2种方案,测试了单独和组合的情况下,系统启动过程中总的代码块翻译次数.
同时我们也统计了理想的最优情况,此时软件代码缓存的容量设定为无限大,不存在刷新,并且也不存在冗余代码块. 理想情况数据的获取方式是记录所有翻译代码块的相关操作,然后经过离线分析,从中去除因缓存刷新导致的重翻译记录,去除所有的冗余代码块的记录. 结果如图19所示.
图19(a)展示了Ubuntu 16.04系统启动过程中,不同方案的代码块翻译次数. 为了体现弱状态标签方案,我们使用了Linux 3.10内核并配置内核参数来使能浮点向量控制状态. 基准方案总翻译次数达到
1100 k. 仅采用多状态代码缓存时,总翻译次数下降至815 k,其中特权级翻译次数下降程度更高,源于独立空间带来的优势. 仅采用弱状态标签时,总翻译次数下降至669 k,用户级翻译次数有较大幅度下降,意味着大量冗余被消除了. 2种方案相结合时可以达到更好的效果,总翻译次数下降至559 k,比较接近理想的462 k. 此时系统级翻译次数已非常接近理想情况,相差的部分源于浮点向量控制状态之外的状态带来的冗余代码块. 用户级翻译次数还有一定距离,尽管消除了冗余代码块,但仍受限于缓存容量.图19(b)展示了Windows XP系统启动过程的测试结果,统计了从系统启动到关机的整个过程. 基准方案总翻译次数高达
1775 k,有大量的系统代码和用户代码,从而对缓存容量更为敏感. 因此,仅采用多状态代码缓存时总翻译次数为859 k,低于仅采用弱状态标签时的1167 k. 这2种方案的结合下总次数进一步降低至717 k,但与理想的545 k仍有较大距离,同样源于代码缓存的容量的不足.5.4 性能测试
本文所提出的2种方案均可以降低软件代码缓存管理的压力,表现为代码块刷新、翻译次数降低,减少内存占用. 多状态缓存方案具有更好的指令局部性,可以减少系统运行过程中的无效刷新,弱状态标签方案能够减少冗余代码块的翻译开销,从而提高系统的整体运行效率.
我们测试了Ubuntu 16.04系统的启动时间,内核使用的是Linux 3.10版本且使能了浮点向量控制状态. 图20展示了LATX-SYS在不同配置下相对于基准方案的运行时间. 横坐标为多状态代码缓存在总容量128 MB情况下不同容量比例. 图20(a)为原始的状态标签方案,图20(b)为弱状态标签方案. 总体趋势与图16相近,在合适的容量比例下,多状态代码缓存的运行时间更短. 图20(a)中,实线为基准方案,因此是100%. 虚线为使用了2个128 MB空间的多状态代码缓存方案,此时整体运行时间减少了10%. 图20(b)中,实线为弱状态标签方案,此时大量的冗余代码块被消除,使得翻译开销和刷新开销得到下降,整体运行时间降低了17%. 虚线为多状态代码缓存和弱状态标签的融合方案,代码块的刷新、翻译次数大大减少,使得整体运行时间降低了20%.
弱状态标签方案引入的动态检测机制,尽管可以降低冗余代码块的翻译和内存占用,但会带来更多的运行时开销,因此我们针对弱状态标签方案测试并分析了其动态开销. 如表10所示,根据动态检测的粒度不同,弱状态标签方案的具体实现可以分为2类:一类是基于代码块检测的方式;一类是基于指令检测的方式. 每种方式的实现又分为基础方案和优化方案,因此共有4种弱状态标签方案的具体实现. 我们在基准配置的基础上实现了这4种方案,针对客户机x86架构中的浮点向量控制状态进行冗余消除,而且都是针对所有的翻译代码块,包括特权级和用户级. 我们使用了SPEC CPU2000基准测试程序,客户机是Ubuntu 16.04系统,Linux 3.10内核版本使能了浮点向量控制状态. 我们将基准方案的性能表现作为基准,测试与其相对的性能表现.
表 10 4种弱状态标签方案的实现Table 10. Implement of Four Weak State Label Schemes弱状态标签 基于代码块 基于指令 基础方案 BN IC 优化方案 BC ICF 代码块无链接方案(block no-linking,BN);代码块检测方案(block checking,BC);指令检测方案(instruction checking,IC);指令融合检测方案(instruction checking fusion,ICF). 图21展示了基于代码块的弱状态标签方案的性能表现. 基础方案禁止了某些情况下的代码块链接,因此造成了严重的性能损失,根据测试结果,整数性能下降为78%,而浮点性能更是下降为55%. 因为浮点测试含有更多的浮点向量指令,因此有更多的代码块链接情况会被禁止,所以性能损失严重. 而大部分整数测试没有浮点向量指令,因此性能几乎不受影响. 优化方案下,整数性能97%,浮点性能99%,性能损失便非常低了.
图22展示了基于指令的弱状态标签方案的性能表现. 基础方案下整数性能91%,可见翻译代码块执行中的动态检测开销远低于代码块链接被禁止所带来的开销. 以整数测试175为例,其浮点向量指令并不多,因此动态检测开销不算高,但在禁止部分代码块链接时性能损失非常严重. 此外,浮点性能仍降低为55%,因为浮点测试含有大量的浮点向量指令,所以有很高的动态检测开销. 而在优化方案下,整数性能为99%,浮点性能97%,性能损失也是非常低.
针对浮点向量控制状态的弱状态标签方案,我们也在相同的环境配置下测试了该方案对SPEC CPU2000基准测试程序的冗余代码块消除情况. 由于测试均是用户程序,因此我们只统计了用户级翻译代码块的冗余消除情况. SPEC CPU2000通过控制输入数据集的大小来控制运行时间,但不同数据集使用的是同一个测试程序代码,因此从运行代码量的视角看来,小数据集与大数据集的差异并不大,因此我们基于test数据集进行测试和分析.
图23展示了弱状态标签方案的冗余消除效果. 图23上半为基准方案下冗余代码块的比例,平均来说,整数程序的冗余率为14%略高于浮点程序的冗余率13%. 整数程序中的最高冗余率为30%,而浮点程序最高为23%,这是因为只有包含定点指令的基本块才会产生冗余代码块,浮点测试包含大量的浮点向量指令,相对来说更不容易产生冗余. 图23下半为弱状态标签方案下总翻译代码块数与基准方案的总翻译代码块数的比值,平均来说,整数程序的代码块数量下降为86%,浮点测试的代码块数量下降为87%,这与基准方案中的非冗余代码块的比例基本一致,可见本文提出的弱状态标签方案充分发挥了作用,将冗余代码块全部消除.
总的来说,SPEC CPU2000这种处理器密集型程序在二进制翻译的运行环境中对代码块的翻译开销并不敏感,更容易受到动态运行时开销的影响. 测试结果表明,优化后的弱状态标签方案引入的运行时开销很低,仅有2%~3%.
6. 总结与展望
本文研究了系统级动态二进制翻译器的软件代码缓存,分析了指令语义模拟的状态标签方案,总结出状态标签对软件代码缓存管理带来的2类问题,即冲突问题和冗余问题. 冲突问题会导致重复的动态翻译开销,冗余问题会导致冗余的动态翻译开销. 针对这2类问题,提出了2种细粒度状态标签的代码缓存优化方法,分别是多状态代码缓存方案和弱状态标签方案,对于特定的客户机状态,解决由该状态导致的冲突问题和冗余问题. 测试结果表明,本文提出的方案可以减少代码块的翻译和刷新开销,有效降低了软件代码缓存管理的压力.
未来的工作包括2个方面:一方面是优化本文提出的方案. 对于多状态代码缓存,总容量一定时2类代码缓存的容量比例是一个关键参数,后续可以设计一个自适应算法进行动态调整. 对于弱状态标签,在不同的客户机架构和客户机系统下,定位哪种状态带来了冗余问题是十分关键的,后续可以设计一个自动化分析框架来进行冗余分析. 另一方面是进一步深入研究系统级动态二进制翻译器的软件代码缓存管理. 例如,相同的客户机可能会被多次启动和运行,后续可以研究一种软件代码缓存持久化方案,从而加快客户机系统的启动速度,提高系统运行效率.
作者贡献声明:牛根负责全文的设计和实现以及文章的撰写和修改;张福新提出实验设计和文章撰写的指导意见.
-
表 1 MoE与集成学习对比
Table 1 Comparison of MoE and Ensemble Learning
类别 MoE 集成学习 模型集成 都涉及整合多个模型结果以提高预测精度,都利用不同模型的优势来解决复杂问题. 应用目的 不仅提高模型预测精度和泛化能力,还提高模型收敛速度和执行效率. 提高模型预测精度和泛化能力. 模型结构 由多个专家和门控网络组成,每个专家负责处理模型的一部分子任务,门控网络决定专家和子任务的映射关系. 通常由多个独立训练的相同或不同算法模型构成. 任务分解 将复杂任务分解为相对简单的子任务,专家网络专注于处理特定子任务. 通常不涉及任务分解,多个学习器同时处理整个任务,通过投票、加权或平均等方法整合结果. 训练方法 门控网络学习将任务分配给相应专家网络,专家网络专注于特定任务学习. 各学习器独立训练,可使用不同的数据或算法,不涉及可学习的任务分配网络. 应用场景 适用于复杂且任务可以分解为不同子任务的场景. 适用于提升模型泛化能力和鲁棒性,尤其在数据或者特征有限的情况. 稀疏性 只有少量专家在给定的时间被激活,提高计算效率. 通常不具有稀疏性,所有模型都参与最终的预测. 动态性 根据输入数据动态激活最适合的专家网络. 通常不具有动态性,模型的集成是静态的,且在训练过程就已确定. 表 2 符号描述
Table 2 Description of Symbols
符号 描述 G 每个节点内GPU的数量 N 节点总数 P GPU设备总数(P=GN) 表 3 MoE系统优化的代表工作总结
Table 3 Summary of Representative Works on MoE System Optimization
类型 子类 适用场景 文献 [69] [56] [57] [58] [63] [78] [109] [96] [126] [94] [95] [101] 内存占用 内存卸载 设备内存有限、模型参数规模大、模型推理 √ √ √ 参数压缩 √ √ 通信延迟 分层通信 通用,特别适合小批量数据通信 √ √ √ √ √ 冗余消除 模型推理或通过张量并行训练、推理 √ √ 其他* 通用,Janus除外 √ √ √ √ 拓扑敏感路由 模型训练,特别是网络拓扑复杂的集群 √ 计算效率 动态容量 通用,特别是专家数量多且偏好差异大的模型 √ √ 专家负载 负载均衡损失用于训练,路由均衡门控均可 设备负载 专家负载差异明显、变化显著,设备数量多 √ √ √ √ 激活预测 模型推理,但通常需要训练过程的统计数据 √ √ √ 静态流水 非极致性能需求 √ √ 自适应流水 模型规模大、执行开销大、极致性能需求 √ √ 内核计算 通用 √ √ √ √ 并行扩展 静态并行 同一模型频繁使用,训练、推理开销不大 √ √ √ 自适应并行 极致性能需求、模型频繁变化、大规模训练推理 √ √ 注:“其他*”代表路由无关通信迟优化中的其他优化. -
[1] Kaplan J, McCandlish S, Henighan T, et al. Scaling laws for neural language models[J]. arXiv preprint, arXiv: 2001.08361, 2020
[2] Raffel C, Shazeer N, Roberts A, et al. Exploring the limits of transfer learning with a unified text-to-text transformer[J]. Journal of Machine Learning Research, 2020, 21(140): 1−67
[3] Brown T, Mann B, Ryder N, et al. Language models are few-shot learners[C] //Proc of the 34th Int Conf on Neural Information Processing Systems. New York: Curran Associates, 2020: 1877−1901
[4] Rae J W, Borgeaud S, Cai T, et al. Scaling language models: Methods, analysis & insights from training Gopher[J]. arXiv preprint, arXiv: 2112.11446, 2021
[5] Chowdhery A, Narang S, Devlin J, et al. PaLM: Scaling language modeling with pathways[J]. arXiv preprint, arXiv:2204.02311, 2022
[6] Jacobs R A, Jordan M I, Nowlan S J, et al. Adaptive mixtures of local experts[J]. Neural Computation, 1991, 3(1): 79−87 doi: 10.1162/neco.1991.3.1.79
[7] Riquelme C, Puigcerver J, Mustafa B, et al. Scaling vision with sparse mixture of experts[C] //Proc of the 35th Int Conf on Neural Information Processing Systems. New York: Curran Associates, 2021: 8583−8595
[8] Fan Zhiwen, Sarkar R, Jiang Ziyu, et al. M3ViT: Mixture-of-experts vision transformer for efficient multi-task learning with model-accelerator co-design[C] //Proc of the 36th Int Conf on Neural Information Processing Systems. New York: Curran Associates, 2022: 28441−28457
[9] Li Bo, Shen Yifei, Yang Jingkang, et al. Sparse mixture-of-experts are domain generalizable learners[J]. arXiv preprint, arXiv: 2206.04046, 2023
[10] Xue Fuzhao, Shi Ziji, Wei Futao, et al. Go wider instead of deeper[C] //Proc of the 36th AAAI Conf on Artificial Intelligence. Palo Alto, CA: AAAI, 2022: 8779−8787
[11] Shen Sheng, Yao Zhewei, Li Chunyuan, et al. Scaling vision-language models with sparse mixture of experts[J]. arXiv preprint, arXiv: 2303.07226, 2023
[12] Dai Yong, Tang Duyu, Liu Liangxin, et al. One model, multiple modalities: A sparsely activated approach for text, sound, image, video and code[J]. arXiv preprint, arXiv: 2205.06126, 2022
[13] Mustafa B, Riquelme C, Puigcerver J, et al. Multimodal contrastive learning with LIMoE: The language-image mixture of experts[C] //Proc of the 36th Int Conf on Neural Information Processing Systems. New York: Curran Associates, 2022: 9564−9576
[14] Kumatani K, Gmyr R, Salinas F C, et al. Building a great multi-lingual teacher with sparsely-gated mixture of experts for speech recognition[J]. arXiv preprint, arXiv: 2112.05820, 2022
[15] You Zhao, Feng Shulin, Su Dan, et al. SpeechMoE: Scaling to large acoustic models with dynamic routing mixture of experts[J]. arXiv preprint, arXiv: 2105.03036, 2021
[16] You Zhao, Feng Shulin, Su Dan, et al. Speechmoe2: Mixture-of-experts model with improved routing[C] //Proc of the 2022 IEEE Int Conf on Acoustics, Speech and Signal Processing. Piscataway, NJ: IEEE, 2022: 7217−7221
[17] Li Dingcheng, Li Xu, Wang Jun, et al. Video recommendation with multi-gate mixture of experts soft actor critic[C] //Proc of the 43rd Int ACM SIGIR Conf on Research and Development in Information Retrieval. New York: ACM, 2020: 1553−1556
[18] 曹泽麟,徐君,董振华,等. 基于多任务学习的位置倾向性得分预测算法[J]. 计算机研究与 发展,2023,60(1):85−94 Cao Zelin, Xu Jun, Dong Zhenhua, et al. Prediction of the positional propensity scores based on multi task learning[J]. Journal of Computer Research and Development, 2023, 60(1): 85−94 (in Chinese)
[19] Fedus W, Zoph B, Shazeer N. Switch Transformers: Scaling to trillion parameter models with simple and efficient sparsity[J]. arXiv preprint, arXiv: 2101.03961, 2021
[20] Shazeer N, Mirhoseini A, Maziarz K, et al. Outrageously large neural networks: The sparsely-gated mixture-of-experts layer[J]. arXiv preprint, arXiv: 1701.06538, 2017
[21] Zoph B, Bello I, Kumar S, et al. ST-MoE: Designing stable and transferable sparse expert models[J]. arXiv preprint, arXiv: 2202.08906, 2022
[22] Lee-Thorp J, Ainslie J. Sparse mixers: Combining MoE and mixing to build a more efficient bert[J]. arXiv preprint, arXiv: 2205.12399, 2022
[23] Kudugunta S, Huang Y, Bapna A, et al. Beyond distillation: Task-level mixture-of-experts for efficient inference[J]. arXiv preprint, arXiv: 2110.03742, 2021
[24] Du Nan, Huang Yanping, Dai A M, et al. GLaM: Efficient scaling of language models with mixture-of-experts[C] //Proc of the 39th Int Conf on Machine Learning. New York: PMLR, 2022: 5547−5569
[25] Lou Yuxuan, Xue Fuzhao, Zheng Zangwei, et al. Cross-token modeling with conditional computation[J]. arXiv preprint, arXiv: 2109.02008, 2022
[26] Lin Junyang, Men Rui, Yang An, et al. M6: A Chinese multimodal pretrainer[J]. arXiv preprint, arXiv: 2103.00823, 2021
[27] Lin Junyang, Yang An, Bai Jinze, et al. M6-10T: A sharing-delinking paradigm for efficient multi-trillion parameter pretraining[J]. arXiv preprint, arXiv: 2110.03888, 2021
[28] Ren Xiaozhe, Zhou Pingyi, Meng Xinfan, et al. PANGU-Σ: Towards trillion parameter language model with sparse heterogeneous computing[J]. arXiv preprint, arXiv: 2303.10845, 2023
[29] Jiang A Q, Sablayrolles A, Roux A, et al. Mixtral of experts[J]. arXiv preprint, arXiv: 2401.04088, 2024
[30] Nguyen H D, Chamroukhi F. Practical and theoretical aspects of mixture‐of‐experts modeling: An overview[J]. Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery, 2018, 8(4): e1246 doi: 10.1002/widm.1246
[31] Masoudnia S, Ebrahimpour R. Mixture of experts: A literature survey[J]. Artificial Intelligence Review, 2014, 42(2): 275−293 doi: 10.1007/s10462-012-9338-y
[32] Yuksel S E, Wilson J N, Gader P D. Twenty years of mixture of experts[J]. IEEE Transactions on Neural Networks and Learning Systems, 2012, 23(8): 1177−1193 doi: 10.1109/TNNLS.2012.2200299
[33] Fedus W, Dean J, Zoph B. A review of sparse expert models in deep learning[J]. arXiv preprint, arXiv: 2209.01667, 2022
[34] Liu Tianlin, Blondel M, Riquelme C, et al. Routers in vision mixture of experts: An empirical study[J]. arXiv preprint, arXiv: 2401.15969, 2024
[35] Cai Weilin, Jiang Juyong, Wang Fan, et al. A survey on mixture of experts[J]. arXiv preprint, arXiv: 2407.06204, 2024
[36] Lepikhin D, Lee H, Xu Yuandong, et al. GShard: Scaling giant models with conditional computation and automatic sharding [J]. arXiv preprint, arXiv: 2006.16668, 2020
[37] Zhang Zhengyan, Lin Yankai, Liu Zhiyuan, et al. MoEfication: Transformer feed-forward layers are mixtures of experts[J]. arXiv preprint, arXiv: 2110.01786, 2021
[38] Zuo Simiao, Zhang Qingru, Liang Chen, et al. MoEBERT: From BERT to mixture-of-experts via importance-guided adaptation[J]. arXiv preprint, arXiv: 2204.07675, 2022
[39] Zhu Tong, Qu Xiaoye, Dong Daize, et al. LLaMA-MoE: Building mixture-of-experts from LLaMA with continual pre-training[J]. arXiv preprint, arXiv: 2406.16554, 2024
[40] Dai Damai, Deng Chenqi, Zhao Chenggang, et al. DeepSeekMoE: Towards ultimate expert specialization in mixture-of-experts language models[J]. arXiv preprint, arXiv: 2401.06066, 2024
[41] Xue Fuzhao, Zheng Zian, Fu Yao, et al. OpenMoE: An early effort on open mixture-of-experts language models[J]. arXiv preprint, arXiv: 2402.01739, 2024
[42] xAI. Open release of Grok-1[EB/OL]. [2024-08-02]. https://x.ai/blog/ grok-os
[43] Reid M, Savinov N, Teplyashin D, et al. Gemini 1.5: Unlocking multimodal understanding across millions of tokens of context[J]. arXiv preprint, arXiv: 2403.05530, 2024
[44] Snowflake AI Research Team. Snowflake arctic: The best LLM for enterprise AI — Efficiently intelligent, truly open[EB/OL]. [2024-08-02]. https://www.snowflake.com/en/blog/arctic-open-efficient-foundation-language-models-snowflake/
[45] The Mosaic Research Team. Introducin DBRX: A new state-of-the-art open LLM[EB/OL]. 2024 [2024-08-02]. https://www.databricks.com/blog/introducing-dbrx-new-state-art-open-llm
[46] Choquette J, Gandhi W, Giroux O, et al. Nvidia A100 tensor core GPU: Performance and innovation[J]. IEEE Micro, 2021, 41(2): 29−35 doi: 10.1109/MM.2021.3061394
[47] Choquette J. Nvidia Hopper H100 GPU: Scaling performance[J]. IEEE Micro, 2023, 43(3): 9−17 doi: 10.1109/MM.2023.3256796
[48] Ren Jie, Rajbhandari S, Aminabadi R Y, et al. ZeRO-Offload: Democratizing billion-scale model training[C] //Proc of the 2021 USENIX Annual Technical Conf. Berkeley, CA: USENIX Association, 2021: 551−564
[49] Chen Xiaoming, Chen D Z, Hu X S. MoDNN: Memory optimal DNN training on GPUs[C] //Proc of the 21st Conf & Exhibition on Design, Automation & Test in Europe. Piscataway, NJ: IEEE, 2018: 13−18
[50] Shriram S B, Garg A, Kulkarni P. Dynamic memory management for GPU-based training of deep neural networks[C] //Proc of the 33rd IEEE Int Parallel and Distributed Processing Symp. Piscataway, NJ: IEEE, 2019: 200−209
[51] Ren Jie, Luo Jiaolin, Wu Kai, et al. Sentinel: Efficient tensor migration and allocation on heterogeneous memory systems for deep learning[C] //Proc of the 27th IEEE Transactions Symp on High Performance Computer Architecture. Piscataway, NJ: IEEE, 2021: 598−611
[52] Huang C C, Jin Gu, Li Jinyang. SwapAdvisor: Pushing deep learning beyond the GPU memory limit via smart swapping[C] //Proc of the 25th Int Conf on Architectural Support for Programming Languages and Operating Systems. New York: ACM, 2020: 1341−1355
[53] Huang Haiyang, Ardalani N, Sun Anna, et al. Towards MoE deployment: Mitigating inefficiencies in mixture-of-expert (MoE) inference[J]. arXiv preprint, arXiv: 2303.06182, 2023
[54] Eliseev A, Mazur D. Fast inference of mixture-of-experts language models with offloading[J]. arXiv preprint, arXiv: 2312.17238, 2023
[55] Kong Rui, Li Yuanchun, Feng Qingtian, et al. Serving MoE models on resource-constrained edge devices via dynamic expert swapping[J]. arXiv preprint, arXiv: 2308.15030, 2023
[56] Hwang R, Wei Jianyu, Cao Shijie, et al. Pre-gated MoE: An algorithm-system co-design for fast and scalable mixture-of-expert inference[J]. arXiv preprint, arXiv: 2308.12066, 2023
[57] Shen Liang, Wu Zhihua, Gong Weibao, et al. SE-MoE: A scalable and efficient mixture-of-experts distributed training and inference system[J]. arXiv preprint, arXiv: 2205.10034, 2023
[58] Liu Juncai, Wang J H, Jiang Yimin. Janus: A unified distributed training framework for sparse mixture-of-experts models[C] //Proc of the 37th ACM SIGCOMM 2023 Conf. New York: ACM, 2023: 486−498
[59] Kim Y, Lim H, Han D. Scaling beyond the GPU memory limit for large mixture-of-experts model training[C] //Proc of the 41st Int Conf on Machine Learning. New York: PMLR, 2024: 24342−24353
[60] Yi Rongjie, Guo Liwei, Wei Shiyun, et al. EdgeMoE: Fast on-device inference of MoE-based large language models[J]. arXiv preprint, arXiv: 2308.14352, 2023
[61] Xue Leyang, Fu Yao, Lu Zhan, et al. MoE-Infinity: Activation-aware expert offloading for efficient MoE serving[J]. arXiv preprint, arXiv: 2401.14361, 2024
[62] Kamahori K, Gu Yile, Zhu Kan, et al. Fiddler: CPU-GPU orchestration for fast inference of mixture-of-experts models[J]. arXiv preprint, arXiv: 2402.07033, 2024
[63] Zhang Zheng, Xia Yaqi, Wang Hulin, et al. MPipeMoE: Memory efficient MoE for pre-trained models with adaptive pipeline parallelism[C] //Proc of the 37th IEEE Parallel and Distributed Processing Symp. Piscataway, NJ: IEEE, 2023: 167−177
[64] Jain P, Jain A, Nrusimha A, et al. Checkmate: Breaking the memory wall with optimal tensor rematerialization[C/OL] //Proc of the 3rd Machine Learning and Systems. 2020 [2024-08-02]. https://proceedings.mlsys.org/paper_files/paper/2020/file/0b816ae8f06f8dd3543dc3d9ef196cab-Paper.pdf
[65] Chen Tianqi, Xu Bing, Zhang Chiyuan, et al. Training deep nets with sublinear memory cost[J]. arXiv preprint, arXiv: 1604.06174, 2016
[66] Peng Xuan, Shi Xuanhua, Dai Hulin, et al. Capuchin: Tensor-based GPU memory management for deep learning[C] //Proc of the 25th Int Conf on Architectural Support for Programming Languages and Operating Systems. New York: ACM, 2020: 891−905
[67] Wang Linnan, Ye Jinmian, Zhao Yiyang, et al. SuperNeurons: Dynamic GPU memory management for training deep neural networks[J]. ACM SIGPLAN Notices, 2018, 53(1): 41−53 doi: 10.1145/3200691.3178491
[68] Kim Y J, Awan A A, Muzio A, et al. Scalable and efficient MoE training for multitask multilingual models[J]. arXiv preprint, arXiv: 2109.10465, 2021
[69] Singh S, Ruwase O, Awan A A, et al. A hybrid tensor-expert-data parallelism approach to optimize mixture-of-experts training[C] //Proc of the 37th Int Conf on Supercomputing. New York: ACM, 2023: 203−214
[70] Heo T, Rashidi S, Man C, et al. Exploring memory expansion designs for training mixture-of-experts models[C/OL] //Proc of the 1st Workshop on Hot Topics in System Infrastructure. 2024 [2024-08-02]. https:// hotinfra23.github.io/papers/hotinfra23-paper4.pdf
[71] Hinton G, Vinyals O, Dean J. Distilling the knowledge in a neural network[J]. arXiv preprint, arXiv: 1503.02531, 2015
[72] Molchanov P, Tyree S, Karras T, et al. Pruning convolutional neural networks for resource efficient inference[J]. arXiv preprint, arXiv: 1611.06440, 2016
[73] Han Song, Mao Huizi, Dally W J. Deep compression: Compressing deep neural networks with pruning, trained quantization and Huffman coding[J]. arXiv preprint, arXiv: 1510.00149, 2016
[74] Dong Zhen, Yao Zhewei, Arfeen D, et al. HAWQ-V2: Hessian aware trace-weighted quantization of neural networks[C] //Proc of the 34th Int Conf on Neural Information Processing Systems. New York: Curran Associates, 2020: 18518−18529
[75] Micikevicius P, Narang S, Alben J, et al. Mixed precision training[J]. arXiv preprint, arXiv: 1710.03740, 2018
[76] Dabre R, Fujita A. Recurrent stacking of layers in neural networks: An application to neural machine translation[J]. arXiv preprint, arXiv: 2106.10002, 2021
[77] Lan Zhenzhong, Chen Mingda, Goodman S, et al. ALBERT: A lite BERT for self-supervised learning of language representations[J]. arXiv preprint, arXiv: 1909.11942, 2020
[78] Rajbhandari S, Li Conglong, Yao Zhewei, et al. DeepSpeed-MoE: Advancing mixture-of-experts inference and training to power next-generation AI scale[C] //Proc of the 39th Int Conf on Machine Learning. New York: PMLR, 2022: 18332−18346
[79] Koishekenov Y, Berard A, Nikoulina V. Memory-efficient NLLB−200: Language-specific expert pruning of a massively multilingual machine translation model[J]. arXiv preprint, arXiv: 2212.09811, 2022
[80] Lu Xudong, Liu Qi, Xu Yuhui, et al. Not all experts are equal: Efficient expert pruning and skipping for mixture-of-experts large language models[J]. arXiv preprint, arXiv: 2402.14800, 2024
[81] Muzio A, Sun A, He C. SEER-MoE: Sparse expert efficiency through regularization for mixture-of-experts[J]. arXiv preprint, arXiv: 2404.05089, 2024
[82] Chowdhury M N R, Wang Meng, Maghraoui K E, et al. A provably effective method for pruning experts in fine-tuned sparse mixture-of-experts[J]. arXiv preprint, arXiv: 2405.16646, 2024
[83] Liu Enshu, Zhu Junyi, Lin Zinan, et al. Efficient expert pruning for sparse mixture-of-experts language models: Enhancing performance and reducing inference costs[J]. arXiv preprint, arXiv: 2407.00945, 2024
[84] Kim Y J, Fahim R, Awadalla H H. Mixture of quantized experts (MoQE): Complementary effect of low-bit quantization and robustness[J]. arXiv preprint, arXiv: 2310.02410, 2023
[85] Frantar E, Alistarh D. QMoE: Practical sub−1-bit compression of trillion-parameter models[J]. arXiv preprint, arXiv: 2310.16795, 2023
[86] Kim Y J, Henry R, Fahim R, et al. Who says elephants can’t run: Bringing large scale MoE models into cloud scale production[J]. arXiv preprint, arXiv: 2211.10017, 2022
[87] Kim Y J, Henry R, Fahim R, et al. FineQuant: Unlocking efficiency with fine-grained weight-only quantization for LLMs[J]. arXiv preprint, arXiv: 2308.09723, 2023
[88] Imani H R, Amirany A, El-Ghazawi T. Mixture of experts with mixture of precisions for tuning quality of service[J]. arXiv preprint, arXiv: 2407.14417, 2024
[89] Gao Zefeng, Liu Peiyu, Zhao Xin, et al. Parameter-efficient mixture-of-experts architecture for pre-trained language models[J]. arXiv preprint, arXiv: 2203.01104, 2022
[90] He S, Fan R Z, Ding Liang, et al. Merging experts into one: Improving computational efficiency of mixture of experts[J]. arXiv preprint, arXiv: 2310.09832, 2023
[91] Zhang Rongyu, Luo Yulin, Liu Jiaming, et al. Efficient deweahter mixture-of-experts with uncertainty-aware feature-wise linear modulation[C] //Proc of the 38th AAAI Conf on Artificial Intelligence. Palo Alto, CA: AAAI, 2024: 16812−16820
[92] Chen Tianyu, Huang Shaohan, Xie Yuan, et al. Task-specific expert pruning for sparse mixture-of-experts[J]. arXiv preprint, arXiv: 2206.00277, 2022
[93] Xue Fuzhao, He Xiaoxin, Ren Xiaozhe, et al. One student knows all experts know: From sparse to dense[J]. arXiv preprint, arXiv: 2201.10890, 2022
[94] Li Jiamin, Jiang Yimin, Zhu Yibo, et al. Accelerating distributed MoE training and inference with Lina[C] //Proc of the 2023 USENIX Annual Technical Conf. Berkeley, CA: USENIX Association, 2023: 945−959
[95] Nie Xiaonan, Zhao Pinxue, Miao Xupeng, et al. HetuMoE: An efficient trillion-scale mixture-of-expert distributed training system[J]. arXiv preprint, arXiv: 2203.14685, 2022
[96] Hwang C, Cui Wei, Xiong Yifan, et al. Tutel: Adaptive mixture-of-experts at scale[C/OL] //Proc of the 6th Machine Learning and Systems. 2023 [2024-08-02]. https://proceedings.mlsys.org/paper_files/paper/2023/file/5616d34cf8ff73942cfd5aa922842556-Paper-mlsys2023.pdf
[97] He Chaoyang, Zheng Shuai, Zhang A, et al. SMILE: Scaling mixture-of-experts with efficient bi-level routing[J]. arXiv preprint, arXiv: 2212.05191, 2022
[98] Shoeybi M, Patwary M, Puri R, et al. Megatron-LM: Training multi-billion parameter language models using model parallelism[J]. arXiv preprint, arXiv: 1909.08053, 2020
[99] Yao Jinghan, Anthony Q, Shafi A, et al. Exploiting inter-layer expert affinity for accelerating mixture-of-experts model inference[C] //Proc of the 38th IEEE Int Parallel and Distributed Processing Symp. Piscataway, NJ: IEEE, 2024: 915−925
[100] Liu Rui, Kim Y J, Muzio A, et al. Gating Dropout: Communication-efficient regularization for sparsely activated transformers[C] //Proc of the 39th Int Conf on Machine Learning. New York: PMLR, 2022: 13782−13792
[101] He Jiaao, Zhai Jidong, Antunes T, et al. FasterMoE: Modeling and optimizing training of large-scale dynamic pre-trained models[C] //Proc of the 27th ACM SIGPLAN Symp on Principles and Practice of Parallel Programming. New York: ACM, 2022: 120−134
[102] Chen Chang, Li Min, Wu Zhihua, et al. TA-MoE: Topology-aware large scale mixture-of-expert training[C] //Proc of the 36th Int Conf on Neural Information Processing Systems. New York: Curran Associates, 2022: 22173−22186
[103] Zeng Zhiyuan, Xiong Deyi. SCoMoE: Efficient mixtures of experts with structured communication[C] //Proc of the 11th Int Conf on Learning Representations. Amherst, MA: OpenReview. net, 2023: 1−23
[104] Kossmann F, Jia Zhihao, Aiken A. Optimizing mixture of experts using dynamic recompilations[J]. arXiv preprint, arXiv: 2205.01848, 2022
[105] Zheng Bojian, Jiang Ziheng, Yu C H, et al. DietCode: Automatic optimization for dynamic tensor programs[C/OL] //Proc of the 5th Machine Learning and Systems. 2022 [2024-08-02]. https://proceedings.mlsys.org/paper_files/paper/2022/file/f89b79c9a28d4cae22ef9e557d9fa191-Paper.pdf
[106] Zheng Zhen, Pan Zaifeng, Wang Dalin, et al. BladeDISC: Optimizing dynamic shape machine learning workloads via compiler approach[J]. Proceedings of ACM on Management of Data, 2023, 1(3): 1−29
[107] Chen Simin, Wei Shiyi, Liu Cong, et al. DyCL: Dynamic neural network compilation via program rewriting and graph optimization[C] //Proc of the 32nd ACM SIGSOFT Int Symp on Software Testing and Analysis. New York: ACM, 2023: 614−626
[108] Yu Feng, Li Guanglin, Zhao Jiacheng, et al. Optimizing dynamic-shape neural networks on accelerators via on-the-fly micro-kernel polymerization[C] //Proc of the 29th ACM Int Conf on Architectural Support for Programming Languages and Operating Systems. New York: ACM, 2024: 797−812
[109] He Jiaao, Qiu Jiezhong, Zeng Aohan, et al. FastMoE: A fast mixture-of-expert training system[J]. arXiv preprint, arXiv: 2103.13262, 2021
[110] Gale T, Narayanan D, Young C, et al. MegaBlocks: Efficient sparse training with mixture-of-experts[C/OL] //Proc of the 6th Machine Learning and Systems. 2023 [2024-08-02]. https://proceedings.mlsys.org/paper_files/paper/2023/file/5a54f79333768effe7e8927bcccffe40-Paper-mlsys2023.pdf
[111] Zheng Ningxin, Jiang Huiqiang, Zhang Quanlu, et al. PIT: Optimization of dynamic sparse deep learning models via permutation invariant transformation[C] //Proc of the 29th Symp on Operating Systems Principles. New York: ACM, 2023: 331−347
[112] Tan S, Shen Yikang, Panda R, et al. Scattered mixture-of-experts implementation[J]. arXiv preprint, arXiv: 2403.08245, 2024
[113] Nie Xiaonan, Miao Xupeng, Cao Shijie, et al. EvoMoE: An evolutional mixture-of-experts training framework via dense-to-sparse gate[J]. arXiv preprint, arXiv: 2112.14397, 2022
[114] Zhou Yanqi, Lei Tao, Liu Hanxiao, et al. Mixture-of-experts with expert choice routing[C] //Proc of the 36th Int Conf on Neural Information Processing Systems. New York: Curran Associates, 2022: 7103−7114
[115] Zeng Zhiyuan, Guo Qipeng, Fei Zhaoye, et al. Turn waste into worth: Rectifying top-k router of MoE[J]. arXiv preprint, arXiv: 2402.12399, 2024
[116] Lewis M, Bhosale S, Dettmers T, et al. Base layers: Simplifying training of large, sparse models[C] //Proc of the 38th Int Conf on Machine Learning. New York: PMLR, 2021: 6265−6274
[117] Clark A, Casas D D L, Guy A, et al. Unified scaling laws for routed language models[C] //Proc of the 39th Int Conf on Machine Learning. New York: PMLR, 2022: 4057−4086
[118] Liu Tianlin, Puigcerver J, Blondel M. Sparsity-constrained optimal transport[J]. arXiv preprint, arXiv: 2209.15466, 2023
[119] Roller S, Sukhbaatar S, Weston J, et al. Hash layers for large sparse models[C] //Proc of the 35th Int Conf on Neural Information Processing Systems. New York: Curran Associates, 2021: 17555−17566
[120] Zuo Simiao, Liu Xiaodong, Jiao Jian, et al. Taming sparsely activated transformer with stochastic experts[J]. arXiv preprint, arXiv: 2110.04260, 2022
[121] Puigcerver J, Riquelme C, Mustafa B, et al. From sparse to soft mixtures of experts[J]. arXiv preprint, arXiv: 2308.00951, 2023
[122] Yu Ping, Artetxe M, Ott M, et al. Efficient language modeling with sparse all-MLP[J]. arXiv preprint, arXiv: 2203.06850, 2022
[123] Muqeeth M, Liu Haokun, Raffel C. Soft merging of experts with adaptive routing[J]. arXiv preprint, arXiv: 2306.03745, 2023
[124] Hazimeh H, Zhao Zhe, Chowdhery A, et al. DSelect-k: Differentiable selection in the mixture of experts with applications to multi-task learning[C] //Proc of the 35th Int Conf on Neural Information Processing Systems. New York: Curran Associates, 2021: 29335−29347
[125] Ibrahim S, Chen W, Hazimeh H, et al. COMET: Learning cardinality constrained mixture of experts with trees and local search[C] //Proc of the 29th ACM SIGKDD Conf on Knowledge Discovery and Data Mining. New York: ACM, 2023: 832−844
[126] Zhai Mingshu, He Jiaao, Ma Zixuan, et al. SmartMoE: Efficiently training sparsely-activated models through combining offline and online parallelization[C] //Proc of the 2023 USENIX Annual Technical Conf. Berkeley, CA: USENIX Association, 2023: 961−975
[127] Nie Xiaonan, Miao Xupeng, Wang Zilong, et al. FlexMoE: Scaling large-scale sparse pre-trained model training via dynamic device placement[J]. Proceedings of ACM on Management of Data, 2023, 1(1): 1−19
[128] Du Zhixu, Li Shiyu, Wu Yuhao, et al. SiDA: Sparsity-inspired data-aware serving for efficient and scalable large mixture-of-experts models[C/OL] //Proc of the 7th Machine Learning and Systems. 2024 [2024-08-02]. https://proceedings.mlsys.org/paper_files/paper/2024/file/698cfaf72a208aef2e78bcac55b74328-Paper-Conference.pdf
[129] Shazeer N, Cheng Youlong, Parmar N, et al. Mesh-Tensorflow: Deep learning for supercomputers[C] //Proc of the 32nd Int Conf on Neural Information Processing Systems. New York: Curran Associates, 2018: 10435−10444
[130] Rajbhandari S, Rasley J, Ruwase O, et al. ZeRO: Memory optimizations toward training trillion parameter models[C/OL] //Proc of Int Conf for High Performance Computing, Networking, Storage and Analysis. Piscataway, NJ: IEEE, 2020 [2024-09-10]. https://dl.acm.org/ doi/abs/10.5555/3433701.3433727
[131] Kosson A, Chiley V, Venigalla A, et al. Pipelined backpropagation at scale: Training large models without batches[C/OL] //Proc of the 4th Machine Learning and Systems. 2021 [2024-08-02]. https://proceedings.mlsys.org/paper_files/paper/2021/file/0c8abcf158ed12d0dd94480681186fda-Paper.pdf
[132] Huang Yanping, Cheng Youlong, Bapna A, et al. GPipe: Efficient training of giant neural networks using pipeline parallelism[C] //Proc of the 33rd Int Conf on Neural Information Processing Systems. New York: Curran Associates, 2019: 103−112
[133] Narayanan D, Harlap A, Phanishayee A, et al. PipeDream: Generalized pipeline parallelism for dnn training[C/OL] //Proc of the 27th ACM Symp on Operating Systems Principles. New York: ACM, 2019 [2024-09-10]. https://dl.acm.org/doi/abs/10.1145/3341301.3359646
[134] Narayanan D, Phanishayee A, Shi Kaiyu, et al. Memory-efficient pipeline-parallel DNN training[C] //Proc of the 38th Int Conf on Machine Learning. New York: PMLR, 2021: 7937−7947
[135] Fu Yichao, Yuhao Qing, Zhao Shixiong, et al. AMPipe: Accelerating MoE model training with intra-block pipelining[EB/OL]. 2024 [2024-08-02]. https://openreview.net/pdf?id=yLgr02IsXY
[136] Jiang Chenyu, Tian Ye, Jia Zhen, et al. Lancet: Accelerating mixture-of-experts training via whole graph computation-communication overlapping[J]. arXiv preprint, arXiv: 2404.19429, 2024
[137] Shi Shaohuai, Pan Xinglin, Chu Xiaowen, et al. PipeMoE: Accelerating mixture-of-experts through adaptive pipelining[C/OL] //Proc of the 2023 IEEE Conf on Computer Communications. Piscataway, NJ: IEEE, 2023 [2024-09-10]. https://ieeexplore.ieee.org/abstract/document/10228874
[138] Aminabadi R Y, Rajbhandari S, Awan A A, et al. DeepSpeed-Inference: Enabling efficient inference of transformer models at unprecedented scale[C/OL] //Proc of Int Conf for High Performance Computing, Networking, Storage and Analysis. New York: ACM, 2022 [2024-09-10]. https://dl.acm.org/doi/abs/10.5555/3571885.3571946
[139] Valiant L G. A bridging model for parallel computation[J]. Communications of the ACM, 1990, 33(8): 103−111 doi: 10.1145/79173.79181
[140] Narayanan D, Shoeybi M, Casper J, et al. Efficient large-scale language model training on GPU clusters using Megatron-LM[C/OL] //Proc of Int Conf for High Performance Computing, Networking, Storage and Analysis. New York: ACM, 2021 [2024-09-10]. https://dl.acm.org/doi/ abs/10.1145/3458817.3476209
[141] Wang Guanhua, Qin Heyang, Jacobs S A, et al. ZeRO++: Extremely efficient collective communication for giant model training[J]. arXiv preprint, arXiv: 2306.10209, 2023
[142] Rajbhandari S, Ruwase O, Rasley J, et al. ZeRO-infinity: Breaking the GPU memory wall for extreme scale deep learning[C/OL] //Proc of Int Conf for High Performance Computing, Networking, Storage and Analysis. New York: ACM, 2021 [2024-09-10]. https://dl.acm.org/doi/ abs/10.1145/3458817.3476205
[143] Jia Zhihao, Lin S, Qi C R, et al. Exploring hidden dimensions in parallelizing convolutional neural networks[C] // Proc of the 35th Int Conf on Machine Learning. New York: PMLR, 2018: 2279−2288
[144] Zheng Lianmin, Li Zhuohan, Zhang Hao, et al. Alpa: Automating inter-and intra-operator parallelism for distributed deep learning[C] //Proc of the 16th USENIX Symp on Operating Systems Design and Implementation. Berkeley, CA: USENIX Association, 2022: 559−578
[145] Li Zhuohan, Zheng Lianmin, Zhong Yinmin, et al. AlpaServe: Statistical multiplexing with model parallelism for deep learning serving[C] //Proc of the 17th USENIX Symp on Operating Systems Design and Implementation. Berkeley, CA: USENIX Association, 2023: 663−679
[146] Jia Zhihao, Zaharia M, Aiken A. Beyond data and model parallelism for deep neural networks[C/OL] //Proc of the 2nd Machine Learning and Systems. 2019 [2024-08-02]. https://proceedings.mlsys.org/paper_files/paper/2019/file/b422680f3db0986ddd7f8f126baaf0fa-Paper.pdf
[147] Artetxe M, Bhosale S, Goyal N, et al. Efficient large scale language modeling with mixtures of experts[J]. arXiv preprint, arXiv: 2112.10684, 2022
[148] Zhao Yanli, Gu A, Varma R, et al. Pytorch FSDP: Experiences on scaling fully sharded data parallel[J]. arXiv preprint, arXiv: 2304.11277, 2023