Empowering System Software with Machine Learning Methods: Challenges, Practice, and Prospects
-
摘要:
机器学习方法为构建系统软件带来了新的机遇. 为充分利用硬件资源支撑新型应用，系统软件的设计与实现需要不断改进与演化，以适应不同场景的需求. 机器学习方法具有从数据中提取规律并自动优化系统性能的潜力. 然而，使用机器学习方法赋能系统软件面临一些挑战，包括设计面向系统软件的定制化模型、获取足量且高质量的训练数据、降低模型开销对系统性能的影响，以及消除模型误差对系统正确性的影响等. 介绍了上海交通大学并行与分布式系统研究所在索引结构、键值存储系统、并发控制协议等方面应用机器学习方法优化系统软件的实践，并从模型设计、系统集成和实践者自身知识储备等方面总结了经验与教训. 此外，还回顾了国内外相关研究，并对此研究方向提出了展望与建议，希望为未来的研究提供参考与帮助.
Abstract:Machine learning methods have brought new opportunities for building system software that fully utilizes hardware resources to support emerging applications. However, in order to adapt to the demands of various application scenarios, system software design and implementation need continuous improvement and evolution. Meanwhile, machine learning methods have the potential to extract patterns from data and automatically optimize system performance. Despite this potential, applying machine learning methods to empower system software faces several challenges, such as customizing models for system software, obtaining training data with sufficient quality and quantity, reducing the impact of model execution costs on system performance, and avoiding the hindrance of model errors on system correctness. We present the practical experience of the Institute of Parallel and Distributed Systems (IPADS) at Shanghai Jiao Tong University in applying machine learning methods to optimize system software for index structures, key-value storage systems, and concurrency control protocols. The lessons learned from the practice in model design, system integration, and practitioner knowledge are summarized. Additionally, we briefly review relevant research at home and abroad, and propose prospects and suggestions for this line of research, including collaboration between systems and machine learning experts, building modular, reusable system prototypes, and exploring model optimization techniques dedicated to systems context. The aim is to offer references and help for future work.
-
Keywords:
- machine learning /
- system software /
- index structure /
- key-value store /
- concurrency control
-
如今，无论是生产软件还是科学计算应用都变得越来越复杂，其中软件包含的大量库依赖项以及复杂的控制和数据流使得软件效率难以得到保证. 并且，如此高的复杂性很容易导致意料之外的低执行效率，从而阻碍软件达到最佳性能. 软件效率低下往往涉及冗余操作，例如从内存中反复加载相同的值[1]、写入从未使用过的值[2]、使用从未使用过的中间值来覆盖同一位置的值[3]以及重复计算相同的值[4-5]. 此外，大量的应用将稀疏数据作为输入，而使用稠密数据结构处理该稀疏数据将会导致资源的大量浪费[6-8]. 以往的研究已经证明上述低效率的根本原因之一是一些指令和数据结构经常处理冗余零[9].
目前已经有大量的真实应用报告了大量冗余零的存在并对其进行针对性优化来达到更好的效果. 例如在深度神经网络领域，研究人员[7-8]已经提出了软件或者硬件的优化方法来实现对神经网络中稀疏性的自动检测以及特定的稀疏优化来达到更好的性能；在视频编码领域，研究人员[6]提出了一些全0块（all-zero block）检测方法来跳过这些块的计算从而达到更高的性能. 而这些方法都是针对特定领域上的工作，并不能对其他领域的应用提供冗余零的检测或优化指导.
此外，现代编译器优化无法识别访存和计算操作中涉及的冗余零以进行进一步的代码优化. 而诸如perf[10], HPCToolkit[11], VTune[12], Gprof[13], CrayPat[14], Oprofile[15]这些性能分析工具也不会识别与冗余零相关的低效率行为，从而无法提供相应的优化指导. ZeroSpy[9]虽然能够正确识别冗余零相关的低效行为并给出相应的指导建议，其检测方法仍然局限于Intel平台，且不支持目前逐渐流行的ARM计算平台. 此外，ZeroSpy的高性能开销也大大加剧了真实应用的性能分析开销. 而目前ARM架构在高性能领域已经越来越受到重视，在Top500中取得世界第一性能的富岳超级计算机[16]的中央处理器就是基于ARMv8架构设计的，而目前并没有一款编译器或性能分析工具可以在ARM平台识别冗余零相关的低效行为，从而错失大量潜在的性能优化机会.
因此，本文提出了DrZero[17]，它是一款基于冗余零检测的可跨平台的、具有更低分析开销的性能分析工具. DrZero实现了一种检测应用程序执行过程中冗余零的方法，包括：1）识别由于数据结构使用不当、数据宽度过大以及无用计算造成的冗余零；2）提示冗余零发生的源代码行与执行上下文来提供直观的优化指导；3）依据应用检测出的冗余零信息进行针对性优化显著提高应用的执行性能或能效. 此外，DrZero基于Dynamorio二进制动态插桩框架[18]实现，并通过基于数据流分析的数据类型推断来识别ARM访存指令读取的数据类型，以及实现在线细粒度缓存迹分析方法来进一步减少性能开销. 相较于ZeroSpy，DrZero支持跨平台的冗余零检测，并拥有更低的开销以及更加友好的报告界面来提示足够充分的冗余零信息以及对应的优化建议.
1. 冗余零的定义与来源
类似文献[9]中所提出的冗余零定义，本文也使用冗余映射（redmap）以及冗余零比例（redundant zeros fraction）作为冗余零的检测目标. 其中，冗余零为指令读取值的高位0值，因此理论上完全消除冗余零对值的表达与计算的正确性不会造成任何影响. 因此高冗余零比例表示具有较大的优化空间，冗余映射则展现读取值的模式，从而为优化策略的设计提供参考. 其中，冗余零主要来自3个方面：数据宽度过大、数据结构使用不当以及0值相关的无用计算.
1）数据宽度过大是造成访存过程中某个指令或者从某个数据对象读取的值中高位字节总是为0 的主要原因之一. 例如，访存指令频繁地从内存读取64b 整型值（占8B），且该值的高7B总是为0，即该访存指令访问了大量的冗余零. 造成该冗余零现象的主要原因就是数据宽度过大，该数据使用8b整型（占1B）即可保证数值的等价性，而不必使用过长的64b整型来存储、访问该数据. 这些冗余零会造成有限的多级缓存资源的浪费，从而造成潜在的性能损失.
2）使用不当的数据结构也会造成大量的冗余零，从而造成大量的资源浪费. 如图1所示，使用稠密数据结构与稠密算法对该稀疏数据进行处理会造成大量的完全冗余零. 而如果应用稀疏数据结构以及对应的稀疏算法会大幅度减少存储、访存开销，并避免大量无用的0值相关的计算，从而得到更好的性能.
![]()
图 1 使用不当的数据结构导致的软件低效行为示例Figure 1. An illustration of software inefficiency by inappropriate use of data structure3）0值相关的无用计算则是另一类常见的冗余零来源. 图2展示了bwaves应用程序中0值相关的无用计算示例代码. 通过DrZero检测以及人工插桩等细致分析后，该示例代码中u,v,w这3个变量常常读取完全冗余零（0值），从而进一步造成在计算mu变量值时引入繁重的0值相关的无用计算. 0值相关的无用计算并不是所有的冗余零都值得进行优化，原则上高冗余零比例的、复杂且高计算开销的操作更加值得进一步优化.
2. 相关工作
值得注意的是，传统的基于硬件计数器的性能分析工具[10-15,18]往往由于其中存在的大量冗余访存与计算反而会充分利用硬件资源，从而得到较好的性能结果. 因此，若含有大量冗余零的访存、计算操作浪费了大量资源，基于硬件计数器的性能分析工具并不能有效地识别类似冗余零的资源浪费导致的软件低效行为，从而无法给出有效的优化建议.
值分析器（value profiler）的开发是为了查明软件中含有的冗余计算. 值分析器最早由Calder等人[19]提出，它可以检测程序代码并查明存储在寄存器或存储器中的不变变量或半不变变量. 其后续研究提出了此值分析器的一种变体[20]. Wen等人[4]开发了一种细粒度的探查器（RedSpy）来识别静默写入（scilent writes）并给出相关指导优化. RedSpy不但检测到计算结果以及数据移动中的冗余，还可以通过报告调用上下文及其在源代码中的位置来报告冗余，从而精确定位冗余代码区域. 此外，Su等人[1]开发了另一个细粒度的探查器LoadSpy，以识别软件中的冗余负载，他们声称，在软件的指令中加载相同的值效率很低. LoadSpy跟踪每个加载指令以查明这些冗余负载，并报告涉及冗余负载的指令对. 此外，Tan等人[21]开发了CIDetector，并证明即使使用现代的优化编译器，无效操作和冗余操作仍然存在. ZeroSpy[9]可以查明与零相关的冗余算术和内存操作，但ZeroSpy基于Intel Pin[22]实现，且ARM指令集与x86指令集不同，访存与计算是分离的，所以不能通过指令来识别访问内存数据的类型. 因此，ZeroSpy的检测方法与实现手段都局限在Intel平台，不能直接应用在跨平台冗余零检测中.
另外，有一些方法致力于通过减少数据类型的长度来利用冗余零. Stephenson等人[23]提出了一种位宽分析方法来静态标识变量的最大所需位宽，从而尽可能减少数据类型的长度. 当在目标FPGA平台上进行评估时，他们的方法可能对面积、速度和功耗产生积极影响. 另一方面，Precimonious[24]工具可用来权衡浮点精度和性能. 这些方法与工具都只能检测数据长度中的冗余，而DrZero还可以检测不适当的数据结构以及零相关导致的冗余计算. 此外，DrZero也不需要任何源代码即可进行冗余零检测.
3. 冗余零检测方法
本文提出并实现了针对冗余零的跨平台细粒度性能分析工具DrZero. 具体来讲，DrZero基于Dynamorio动态二进制插桩框架[25]实现. 相较ZeroSpy选用的Intel Pin[22]，Dynamorio具有可跨平台（支持x86与ARM）、支持细粒度的分析与插桩、开源等特性，从而可以支持跨平台更加细粒度的插桩、分析工具. Dynamorio框架是基于事件来触发分析与插桩过程，例如线程启动和终止、基础块载入等事件. 当事件发生时，Dynamorio会触发初始化时注册的回调函数来对目标事件进行分析、插桩. 其中，当基础块载入事件发生时，Dynamorio可以获取该基础块将要执行的所有指令，因此DrZero基于各个基础块对所有包含内存读取操作的指令进行分析，并进行基础块级别的动态二进制插桩. DrZero的跨平台冗余零检测技术总览如图3所示，包含：①基于数据流分析的数据类型推断；②细粒度缓存迹插桩与在线分析. 其中，根据检测目标的不同，在线分析又分为以代码为中心的分析模式和以数据为中心的分析模式. 在目标程序执行完毕后，DrZero会生成一系列报告文件，并通过定制的VSCode扩展来将冗余零报告可视化，并基于检测结果提供优化建议. 下文将对DrZero的各个核心技术进行详细讲解.
![]()
图 3 DrZero跨平台冗余零检测技术总览Figure 3. An overview of the cross-platform redundant zeros detection techniques of DrZero3.1 基于数据流的数据类型推断
与x86指令集不同，ARM指令集集中访存与计算为不同的指令，即计算操作不能直接访问内存，而同一访存指令可能读取整型值或浮点值. 此外，通用寄存器除了保存整型值以外，也可能保存浮点值并在计算时移动到浮点寄存器来进行浮点计算，因此也不能只通过内存读取操作的目标寄存器类型来判断读取值是浮点值还是整型值. 为了解决上述挑战，DrZero采用基于数据流的数据类型推断来尽可能推断出读取值的数据类型，从而可以采用对应的冗余零分析策略来获取冗余映射以及冗余零比例.
基于数据流的数据类型推断算法如算法1所示. 由于数据类型中的数据宽度可以直接由访存宽度直接获取，因此算法1的主要目的在于推断该指令读取值是否为浮点数. 首先，算法1根据目标寄存器类型推断是否为浮点指令（行①）. 如果目标寄存器为浮点寄存器则推断为浮点指令，返回真值. 由于本文主要关注访存指令中存在的冗余零现象，因此只在指令读取内存中的值时才进一步基于数据流进行推断（行②）. 若该指令读取内存值，算法则枚举所有目标寄存器对象，并对每个目标寄存器对象查找该基础代码块中在该指令后执行的所有指令的源寄存器中是否存在定义-使用关系（行③~⑫），若存在，则返回使用目标寄存器的指令的类型（行⑬）. 如果上述数据流分析过程都没有找到定义-使用关系，则返回先前推断的instr指令类型（行⑳）.
算法1. 数据类型推断算法.
输入：目标访存指令instr；
输出：是否为浮点指令.
① bool is_float = instr_is_floating_self（instr）；
② if（!is_float && instr_reads_memory（instr））
③ int num_dsts = instr_num_dsts（instr）；
④ for（int i=0；i<num_dsts；++i）
⑤ opnd_t opnd = instr_get_dst（instr, i）；
⑥ if（opnd_is_reg（opnd））
⑦ reg_id_t reg_def = opnd_get_reg（opnd）；
⑧ for （instr_t* ins = instr；ins != NULL； ins = instr_get_next（ins））
⑨ int num_srcs = instr_num_srcs（ins）；
⑩ for（int j=0；j<num_srcs；++j）
⑪ opnd_t opnd = instr_get_src（ins, j）；
⑫ if （opnd_is_reg（opnd） &&
opnd_get_reg（opnd） == reg_def）
⑬ return instr_is_floating_self（ins）；
⑭ end if
⑮ end for
⑯ end for
⑰ end if
⑱ end for
⑲ end if
⑳ return is_float.
在ARM平台上，算法1可以有效地识别大部分浮点数内存访问指令，从而应用适当的冗余零分析方法来建立冗余映射并识别冗余零. 但由于程序执行过程的不确定性，基础代码块最后的跳转指令的目标地址往往无法静态确定，因此基于数据流的数据类型推断仅受限于单个基础代码块，从而某些存在跨基础代码块的定义-使用关系的浮点值读取指令时可能仍会推断为读取整型值. 然而，由于时空局部性的存在，这些推断错误依旧可以认为是较少的，不会影响最终报告的冗余映射与冗余零比例.
3.2 在线细粒度缓存迹分析
为了分析得到所有访存操作读取内存值的冗余映射与冗余零信息，本文提出了在线细粒度缓存迹分析在细粒度缓存区中缓存一定量的访存操作信息并基于该缓存区进行针对冗余零的在线分析来检测冗余零导致的软件低效行为. 具体来讲，该过程主要分为4步：细粒度缓存区的创建、细粒度缓存迹插桩、细粒度缓存迹更新以及在线冗余零分析.
在工具初始化时，DrZero需要创建细粒度缓存区来保存程序运行过程中内存读取操作的信息，包括目标地址、调用上下文以及读取的值. 为了避免插桩后的代码执行时频繁检查读取值的数据类型从而造成繁重的分支操作，DrZero对每个可能的数据类型都建立缓存区，包括1b，2b，4b，8b整型值，单、双精度浮点值以及128b，256b整型向量，单、双精度浮点向量. 对于每个缓冲区，DrZero分配大小为4096个元素的缓冲区.
在目标应用程序执行时，Dynamorio会触发基础代码块载入事件. 在经过3.1节所述的数据类型推断后，DrZero向基础代码块中插入细粒度缓存迹更新以及在线冗余零分析代码. 由于读取内存值的数据类型可静态推断，DrZero根据推断的数据类型来插入相应的指令，向对应缓存区存储目标内存地址、调用上下文句柄（通过DrCCTProf[26]获取）以及读取值. 例如，图3中内存读取操作被推断为32b浮点类型（FP32），然后插入指令将相应信息缓存到FP32对应的细粒度缓存迹中以便后续在线分析. 此外，在每个基础代码块级别都需要静态推断各个细粒度缓存迹将要填充的数量，并对每个将要填充的细粒度缓存迹都在基础代码块入口进行插桩：
1） 插入指令，检查是否将满或溢出；
2） 插入条件跳转指令与函数调用，从而保证在将满或溢出时调用在线冗余零分析代码；
3） 在在线冗余零分析后清空该缓存迹.
在插桩完成后，Dynamorio将会负责执行插桩后的代码，因此所有内存读取操作的信息都会被记录到细粒度缓存迹中，并及时更新细粒度缓存迹，以及在将满或溢出时触发在线冗余零分析. 该过程也称为细粒度缓存迹更新. 在线冗余零分析过程根据检测模式的不同分为以代码为中心的在线分析和以数据为中心的在线分析. 由于具体DrZero的冗余零检测算法与ZeroSpy[9]中的冗余零检测算法类似，本文仅介绍在线分析的核心思想.
1） 以代码为中心（code-centric）的在线分析. 该分析过程旨在发现指令级别的冗余零现象，可以检测冗余零导致的无用计算以及数据宽度过长导致的资源浪费. 由于触发在线分析的细粒度缓存迹都已经静态确定其数据类型，在线分析过程中便不用检查其类型并直接进行冗余零检测. 在冗余零检测后，所有检测数据都被记录、累计在以调用上下文句柄为键值的散列映射表中.
2） 以数据对象为中心（data-centric）的在线分析.该分析过程旨在发现数据对象级别的冗余零现象，可以检测数据结构使用不当以及数据宽度过长的问题. 类似以代码为中心的在线分析，在线分析过程中不用检查其数据类型. 数据对象信息则在在线分析过程中通过缓存迹中的目标内存地址从DrCCTProf获取数据对象信息，包括静态数据对象的变量名以及动态数据对象分配时的调用上下文. 由于只有静态数据对象与动态数据对象可以获取到足够的调试信息以供后续优化，本文只对静态与动态数据对象进行冗余零检测与报告.
相较ZeroSpy[9]的检测方法，在线细粒度缓存迹分析拥有3点优势：1）尽可能避免频繁、高开销的算数状态保存操作；2）避免对每次内存读取的值进行分析、记录，从而减轻工具对应用的缓存污染；3）集中批处理冗余零检测与记录操作，具有更好的时空局部性.
3.3 冗余零报告与性能优化指导的可视化界面
为了更好地展示冗余零检测结果，DrZero提供基于VSCode的插件来将检测结果可视化. DrZero的性能报告分为总览（metric overview）和按线程划分的详细报告（detailed metrics）. 如图4所示，ZeroSpy用户界面的总览页面分为全局整数冗余零字节（total integer redundant byte）以及全局浮点数冗余零字节（total floating point redundant byte）两个部分，并分别列出了冗余零与总访问字节. 此外，各个线程所统计的冗余零数量以及冗余零比例也可以在此页面查看. 按线程划分的详细报告则可通过图4中“detail”链接查看. DrZero可以分别生成以代码为中心的分析模式与以数据对象为中心的分析模式报告，其线程详细报告页面如图5所示.
1） 以代码为中心的分析模式. 如图5所示，各个线程的以代码为中心模式的报告页面分为整数冗余信息以及浮点冗余信息2个部分. 对于以代码为中心的模式报告，页面将会显示发生冗余的程序指令的记录，且每条记录是按照检测到的冗余字节数量从高到低排列. 对于每条记录，“Redundancy”是该指令的冗余零在所有检测到的冗余零中的比例，“local redundancy”则是该指令的冗余零在所有执行该特定指令检测到的冗余零中的比例. 使用者可以进一步点击每条记录以显示更多冗余零信息，包括完全冗余零占比、指令的冗余映射（从最低到最高）. 此外，每条记录会给出包含源代码行号与文件路径的调用上下文信息，从而指导开发者进一步的代码优化.
2） 以数据对象为中心的分析模式. 如图5所示，各个线程的以数据对象为中心的模式报告页面同样分为整数冗余信息以及浮点冗余信息2个部分. 对于以数据对象为中心的模式报告，页面将会显示发生冗余的静态或动态数据对象的记录，且每条记录是按照检测到的冗余字节数量从高到低排列. 对于静态数据对象，每一条记录都会显示对象的名称，以帮助使用者在源代码中定位该静态数据对象. 对于动态分配的数据对象，报告会提供其调用上下文信息（CCT info）指示其动态数据对象创建的位置. 每条记录均会显示静态或动态数据对象的数据大小、以字节为单位的未访问数据比例信息以及冗余零比例信息. 此外，使用者还可以点击“redmap”字样以跳转到链接的数据对象的以字节为单位的冗余映射热力图，如图6所示.
![]()
图 6 NPB-IS程序中报告大量冗余零的动态数据对象的热力图Figure 6. The heatmap of the dynamic data object with significant redundant zeros in NPB-IS program4. 实验结果与分析
4.1 实验设置
本文使用如表1所示的x86和ARM实验平台对DrZero进行评测. 为了检验DrZero的跨平台冗余零检测的性能开销以及检测效果，本文选用NAS Parallel Benchmarks（NPB-3.4）[27]和Rodinia[28]基准测试程序集进行评测. 其中NPB基准测试使用C CLASS输入问题规模. 此外，为了评测实际应用规模的冗余零检测能力，本文也选用SPEC CPU2017[29]中的NAB生命科学应用（ref输入大小）以及Fotonik3D计算电磁学应用（ref输入大小）作为案例研究来详细讲解DrZero的冗余零检测结果以及优化流程. 所有程序都使用GCC 11.0-O3-g-fopenmp编译，并在单个CPU上（x86平台上14线程，ARM平台上32线程）并行执行.
表 1 x86和ARM评测平台详细软硬件配置信息Table 1. The Detailed Software and Hardware Configurations of Evaluated X86 and ARM Platform平台 x86 ARM 处理器 Xeon E5-2680v4@2.40GHz Cavium ThunderX2@2.50GHz 核数 14 32 内存 256GB DDR4 128GB DDR4 编译器 GCC 11.0 GCC 11.0 系统 Linux 5.8.0-55-generic #62~20.04.1-Ubuntu Linux 5.4.0-74-generic #83-Ubuntu 4.2 冗余零识别效果
DrZero在x86和ARM平台上的冗余零检测结果分别如表2和表3所示. 其中，CC表示以代码为中心的冗余零分析模式，其冗余零比例按照所有整数或浮点数累计的冗余零数量除以总访问字节数得到，CC数值越大表明执行过程中冗余零相关的冗余计算、资源浪费越严重；DC表示以数据为中心的冗余零分析模式，其冗余零比例按照所有数据对象中含有的冗余零数量除以所有数据对象的数量大小之和得到，DC数值越大表明数据对象的稀疏性越高或潜在的数据宽度过长问题越严重. 此外，在x86和ARM平台上DrZero使用以代码为中心（CC）以及以数据为中心（DC）的冗余零分析模式的评测，结果对比分别如图7、图8所示. 评测结果证明DrZero拥有跨平台检测冗余零导致的软件低效行为的能力. 此外，本文还展示了在x86平台上ZeroSpy与DrZero报告的冗余零比例的比较，如图7所示. 其中，由于ZeroSpy报告中冗余零比例在CC与DC模式下的计算方式相同，本文仅展示CC模式下的冗余零比例检测比较. DrZero在大部分测试程序中检测的冗余零比例与ZeroSpy相当. 然而，有些程序的冗余零比例则有较明显的差距（如heartwall）. 通过细致分析发现，DrZero与ZeroSpy所检测的冗余零数量差别不大. 而由于Dynamorio不能完全识别所有的指令，DrZero可能会将有些特殊的访存指令识别为空指令（nop），从而大大低估了总访问字节数. 此外，通过图7所示的同一代码在不同平台上的冗余零比例对比，本文发现虽然某些代码在不同平台上展现一定的冗余零比例的一致性，但仍然有一些基准测试程序在同样的代码、不同平台下的冗余零情况具有较大的差异性（例如LU）. 这表明x86和ARM指令集对程序的针对冗余零的低效行为拥有不同的敏感度. 不同指令集之间的冗余零发散现象需要进一步详细研究.
表 2 DrZero报告在x86平台上的冗余零比例以及检测分析开销Table 2. Fraction of Redundant Zero and Profiling Overheads Reported by DrZero on x86 Platform模式 名称及统计项 冗余零比例/% 时间开销 内存开销 模式 名称及统计项 冗余零比例/% 时间开销 内存开销 整数 浮点数 整数 浮点数 NPB CC BT 2.02 20.30 54.83 1.25 NPB DC BT 0.00 0.01 32.15 29.52 CG 10.38 0.00 19.33 1.14 CG 0.86 0.00 57.04 28.68 EP 5.44 0.00 15.61 6.88 EP 0.44 0.00 6.57 135.49 FT 2.46 0.00 18.18 1.02 FT 0.00 0.00 18.46 25.88 IS 22.96 0.00 14.40 1.17 IS 9.28 0.00 47.76 28.46 LU 6.06 12.11 24.94 1.28 LU 0.00 0.01 29.36 31.01 MG 10.33 7.38 4.45 1.03 MG 0.00 0.03 23.05 25.93 SP 4.09 1.64 23.10 1.22 SP 0.00 0.01 39.74 29.32 UA 23.54 5.08 33.98 1.47 UA 1.07 0.07 27.94 31.92 中位数 6.06 1.64 19.33 1.22 中位数 0.00 0.01 29.36 29.32 最大值 23.54 20.30 54.83 6.88 最大值 9.28 0.07 57.04 135.49 平均值 9.70 5.17 23.20 1.83 平均值 1.29 0.01 31.34 40.69 Rodinia CC 中位数 38.41 0.13 64.76 3.4 Rodinia DC 中位数 34.17 0.01 64.98 82.42 最大值 56.15 11.58 111.58 99.76 最大值 91.14 10.23 157.45 2480.46 CC 中位数 23.25 0.17 40.32 2.95 DC 中位数 21.72 0.01 44.02 58.91 平均值 24.47 2.83 45.31 7.96 平均值 27.14 2.71 54.20 188.40 表 3 DrZero报告在ARM平台上的冗余零比例以及检测分析开销Table 3. Fraction of Redundant Zero and Profiling Overheads Reported by DrZero on ARM Platform模式 名称及统计项 冗余零比例/% 时间开销 内存开销 模式 名称及统计项 冗余零比例/% 时间开销 内存开销 整数 浮点数 整数 浮点数 NPB CC BT 1.85 25.95 12.49 1.34 NPB DC BT 0.00 0.01 2.82 32.64 CG 12.74 0.00 4.29 1.16 CG 0.30 0.00 4.80 31.61 EP 3.65 0.00 5.65 4.65 EP 1.57 0.00 4.03 151.07 FT 0.44 0.00 7.96 1.03 FT OOM IS 28.15 0.00 6.04 1.08 IS 7.25 0.00 24.84 31.61 LU 70.53 1.69 4.47 1.39 LU 0.00 0.00 2.67 34.68 MG 7.61 11.51 4.90 1.05 MG 0.01 0.01 21.99 26.85 SP 3.99 1.52 5.23 1.30 SP 0.00 0.01 5.31 32.48 UA 29.74 2.14 6.86 1.68 UA 0.25 0.01 7.09 38.40 中位数 7.61 1.52 5.65 1.30 中位数 0.13 0.01 5.06 32.56 最大值 70.53 25.95 12.49 4.65 最大值 7.25 0.01 24.84 151.07 平均值 17.63 4.76 6.43 1.63 平均值 1.17 0.01 9.20 47.42 Rodinia CC 中位数 40.94 0.00 12.33 3.28 Rodinia DC 中位数 0.66 0.00 13.07 111.69 最大值 58.09 10.59 60.47 47.75 最大值 8.63 0.01 36.86 2794.66 CC 中位数 32.02 0.00 8.76 2.74 DC 中位数 0.53 0.00 10.20 55.68 平均值 30.21 2.51 14.12 6.06 平均值 1.28 0.00 13.40 265.52 ![]()
图 7 DrZero CC模式下分别在x86和ARM平台上检测的整型（INT）以及浮点（FP）类型的冗余零含量Figure 7. Fraction of integer （INT） and floating point （FP） redundant zeros reported by DrZero CC mode on x86 and ARM platforms![]()
图 8 DrZero DC模式下分别在x86和ARM平台上检测的整型（INT）以及浮点（FP）类型的冗余零含量Figure 8. Fraction of integer （INT） and floating point （FP） redundant zeros reported by DrZero DC mode on x86 and ARM platforms4.3 性能与内存开销
本文评测的DrZero的性能与内存开销如表2与表3所示. 实验结果表明DrZero在x86平台上的以CC与DC性能开销的中位数分别为40.32倍与44.02倍. 与ZeroSpy所报告的性能开销的中位数64.17倍（CC）与99.52倍（DC）相比[9]，DrZero的平均性能开销分别降低了37.2%和55.8%. 此外，在ARM平台，DrZero的CC和DC的平均性能开销仅为14.12倍和13.40倍，性能开销中位数则仅分别为8.76倍和10.20倍. DrZero的性能开销与常见的二进制插装工具[1-4]持平甚至更低，因此具有良好的应用前景.
ZeroSpy（x86平台运行）、DrZero-x86（x86平台上运行）以及DrZero-ARM（x86平台上运行）之间在以代码为中心的和以数据对象为中心的分析模式下的详细性能开销对比分别如图9与图10所示. 实验结果表明，本文提出的DrZero在大部分程序下CC和DC的性能开销都优于ZeroSpy，并且DrZero在ARM平台上相较在x86平台具有更低的性能开销. 更低的性能开销主要来自2个方面：1）DrZero调用上下文采集基于DrCCTProf实现，使用性能开销更低的指令内联方式来获取调用上下文，且DrCCTProf也针对ARM平台进行高度优化，因此DrZero调用上下文采集开销相较依赖Intel Pin的CCTLib[30]更低；2）DrZero的在线细粒度缓存迹分析方法可以有效避免冗余且高开销的频繁算数、寄存器状态缓存操作，从而带来可观的性能提升.
![]()
图 9 在CC模式下ZeroSpy，DrZero-x86，DrZero-ARM上的性能开销对比Figure 9. Comparison of the performance overhead of CC mode caused by ZeroSpy, DrZero-x86, and DrZero-ARM![]()
图 10 在DC模式下ZeroSpy，DrZero-x86，DrZero-ARM上的性能开销对比Figure 10. Comparison of the performance overhead of DC mode caused by ZeroSpy, DrZero-x86, and DrZero-ARM如图11所示，DrZero在CC模式下，在x86平台和ARM平台上内存开销都普遍低于ZeroSpy. 然而，如图12所示，DrZero在DC模式下则相反，其内存开销都普遍高于ZeroSpy. 具体情况如表2所示，DrZero在x86平台上的CC和DC的内存开销中位数分别为2.74倍和55.68倍. 相较ZeroSpy所报告的内存开销中位数4.47倍（CC）和6.56倍（DC），DrZero在CC模式下具有更低的内存开销（降低38.7%），而在DC模式下具有更高的内存开销（升高8.49倍）. 经过进一步分析，DC模式下DrCCTProf[26] 为了更高的性能，将所有已静态、动态分配内存的数据对象的所有地址空间通过影射内存（shadow memory）方法按字节映射、存储其数据对象信息. 该方法相较ZeroSpy依赖的基于Intel Pin的CCTLib[30]支持的基于树的实现拥有更大的内存开销. 此外，由于需要DrZero的DC模式下的冗余零检测需要数据对象的起、止内存地址，在扩展DrCCTProf的数据对象信息实现后，每个数据对象在每个影射位需要存储的信息变为原来的3倍，使得内存开销问题变得更为严重，甚至在ARM平台上NPB FP会超出内存容量（out of memory，OOM）从而无法采集冗余零信息. 因此，未来工作需要提出更加内存友好且能保持低开销的数据对象采集方法来替代DrCCTProf的影射内存方法，以获取更低的内存开销.
![]()
图 11 在CC模式下ZeroSpy，DrZero-x86，DrZero-ARM上的内存开销对比Figure 11. Comparison of the memory overhead of CC mode caused by ZeroSpy, DrZero-x86, and DrZero-ARM![]()
图 12 在DC模式下ZeroSpy，DrZero-x86，DrZero-ARM上的内存开销对比Figure 12. Comparison of the memory overhead of DC mode caused by ZeroSpy, DrZero-x86, and DrZero-ARM4.4 NAB案例研究
NAB是一个包含在SPEC CPU2017基准测试套件[29]中的分子建模程序. NAB是生命科学模拟领域典型的计算密集型程序. 由于DrZero报告的NAB冗余零情况在x86和ARM平台上都类似，因此本文仅展示x86上的冗余零报告结果. DrZero的以代码为中心的冗余零分析模式检测出NAB包含11.52%的整数冗余零和6.57%的浮点冗余零. DrZero报告NAB中产生最多浮点冗余零的指令信息以及其对应于源代码中的位置如图13所示.
![]()
图 13 DrZero CC模式报告中NAB产生最多浮点冗余零的指令Figure 13. The operation with the most significant redundant zeros in NAB reported by DrZero CC mode产生冗余零的代码区域如图14所示，其中
∗kappa 的值频繁为0. 由于完全冗余零的比例很高，本文使用基于条件判断的方法（如图15所示的if/else语句）来跳过处理冗余零的无用计算. 此外，该优化方法还可以通过在进入2个嵌套循环之前判断∗kappa 的值来进一步减少分支开销. 优化后的代码如图15所示，类似的优化也应用于具有类似冗余的其他代码区域. 经过我们的优化，NAB在x86平台实现9.7%的性能加速，ARM平台上实现6.08%的性能加速.![]()
图 14 NAB的函数egb中包含最多冗余零的程序片段Figure 14. Code snippet containing the most significant redundant zeros in the egb function of NAB![]()
图 15 NAB的函数egb优化后的程序片段Figure 15. Code snippet in the egb function of NAB after optimization4.5 Fotonik3D案例研究
Fotonik3D是一个包含在SPEC CPU2017基准测试套件[29]中的计算电磁学程序，其中包含了计算电磁学程序中常见的计算模式. Fotonik3D 使用麦克斯韦方程组的有限差分时域 （FDTD） 方法计算光子波导的传输系数. 在本文的评测中，Fotonik3D使用SPEC套件中提供的ref输入数据集进行评测. 由于Fotonik3D在x86和ARM上检测的冗余零含量类似，本文仅给出x86上的DrZero的冗余零检测结果. DrZero的以代码为中心的冗余零检测结果表明，Fotonik3D的执行过程中含有8.76%的整型冗余零以及32.30%的浮点冗余零. 通过进一步分析发现，其中数组Ex, Ey, Ez相关的计算都含有大量的完全冗余零. 具体情况如图16中左图所示，在计算过程中，数组Ex, Ey, Ez由大量完全冗余零构成，且其中大量x-z平面数据往往为0，即该数组是结构化稀疏的. 因此，稀疏数据使用稠密数据结构以及稠密算法是造成Fotonik3D应用程序中大量完全冗余零及其相关无用计算的根本原因.
为了优化并消除冗余零造成的冗余计算，本文针对该应用数据特点对结构化稀疏数据结构以及对应的算法进行设计. 如图16中右图所示，原Ex, Ey, Ez数组的三维数据存储格式由原来的（x, y, z）的存储顺序改为按照（x, z, y）顺序存储，使得x-z平面在内存中得以连续存储；此外，数组稀疏存储格式按照类似稀疏矩阵格式[31]进行存储，即数组中仅存储非零x-z平面，并将对应y轴方向上的坐标值记录在下标向量Indexy中. 经过本文所提出的优化，Fotonik3D在x86平台上实现1.76倍的性能加速，在ARM平台上实现2.12倍的性能加速.
5. 结束语
本文提出了一个针对冗余零的跨平台细粒度性能分析工具DrZero. 为了适配访存、计算指令分离的ARM指令集，本文提出了基于数据流分析的数据类型推断方法来自动推断访存指令读取内存数据的数据类型. 此外，为了更低的性能开销，本文也提出了在线细粒度缓存迹分析来检测、记录冗余零相关的指标. DrZero也提供了基于VSCode的可视化插件来展示冗余零检测报告以及相应的优化建议. 本文的实验展示了DrZero跨平台检测冗余零的能力. DrZero在以代码、数据为中心的冗余零分析中，分别以x86和ARM平台45.31倍、54.20倍和14.12倍、13.40倍平均性能开销检测冗余零并给出优化建议. 基于DrZero给出的性能优化指导，本文优化的应用程序在x86和ARM上分别达到了最高1.76倍和2.12倍的性能加速. DrZero 的实现代码已经开源：https://github.com/buaa-hipo/ZeroSpy-drcctprof.
在未来，我们认为还有3个问题需要解决. 首先，在ARM平台上数据对象信息采集需要过大的内存开销，这导致运行使用较多内存的应用无法使用以数据为中心的分析模式进行分析，从而错失一些潜在的优化机会. 其次，本文发现的x86和ARM平台之间同一代码下冗余零的发散现象需要进一步研究其原因，以便挖掘更多的性能优化机会. 最后，希望将来更多的ARM平台（例如天河三号原型机中使用的国产ARM处理器FT2000+）中测试本文提出的DrZero工具来发现更多的性能优化机会.
作者贡献声明：游心提出研究思路，设计实现研究方案，撰写论文；杨海龙负责论文起草以及最终版本修订；雷克伦负责采集实验数据并实现可视化界面；孔祥浩负责实现ARM平台部分功能； 徐筠、栾钟治、钱德沛负责最终版本修订.
-
![]()
图 1 机器学习模型代替索引结构的示意图
Figure 1. Illustration of replacing index structures with machine learning models
![]()
图 2 将数据排序并连续存放可简化被拟合函数
Figure 2. Sorting data and storing date continuously simplify the approximated function
![]()
图 3 通过两阶段压缩更新索引可避免数据一致性问题
Figure 3. Updating indexes with two-phase compaction avoids data consistency issue
![]()
图 4 在类TPC-C负载下XIndex可扩展性良好且性能优于现有系统
Figure 4. XIndex achieves good scalability in a TPC-C style workload and outperforms state-of-the-art baselines
![]()
图 7 在只读和读写负载下XStore性能均优于现有系统
Figure 7. XStore outperforms state-of-the-art baselines in both read-only workload and read-write workload
![]()
图 8 Polyjuice使用的并发控制策略表格表示方式
Figure 8. Concurrency control policy table representation used in Polyjuice
![]()
图 9 Polyjuice用遗传算法为特定工作负载训练并发控制策略
Figure 9. Polyjuice uses the evolutionary algorithm to train concurrency control policies for specific workloads
![]()
图 10 不同工作负载下Polyjuice都能优于现有并发控制协议
Figure 10. Polyjuice outperforms existing concurrency control protocols under different workloads
-
[1] He Kaiming, Zhang Xiangyu, Ren Shaoqing, et al. Deep residual learning for image recognition [C] //Proc of the 2016 IEEE Conf on Computer Vision and Pattern Recognition. Piscataway, NJ: IEEE, 2016: 770−778
[2] Silver D, Schrittwieser J, Simonyan K, et al. Mastering the game of Go without human knowledge[J]. Nature, 2017, 550(7676): 354−359 doi: 10.1038/nature24270
[3] Silver D, Huang A, Maddison C, et al. Mastering the game of Go with deep neural networks and tree search[J]. Nature, 2016, 529(7587): 484−489 doi: 10.1038/nature16961
[4] Vaswani A, Shazeer N, Parmar N, et al. Attention is all you need [C] //Advances in Neural Information Processing Systems 30. Red Hook, NY: Curran Associates Inc. , 2017: 6000−6010
[5] Radford A, Narasimhan K, Salimans, T, et al. Improving language understanding by generative pre-training [R/OL]. San Francisco, CA: OpenAI, 2018 [2023-02-27].https://cdn.openai.com/research-covers/language-unsupervised/language_understanding_paper.pdf
[6] Radford A, Wu J, Child R, et al. Language models are unsupervised multitask learners [R/OL]. San Francisco, CA: OpenAI, 2019 [2023-02-27].https://cdn.openai.com/better-language-models/language_models_are_unsupervised_multitask_learners.pdf
[7] Brown T B, Mann B, Ryder N, et al. Language models are few-shot learners [C] //Advances in Neural Information Processing Systems 33. Red Hook, NY: Curran Associates Inc. , 2020: 1877−1901
[8] Lampson B W. Hints for computer system design [C] //Proc of the 9th ACM Symp on Operating Systems Principles. New York: ACM, 1983: 33−48
[9] Lampson B W. Hints and principles for computer system design [R/OL]. Ithaca, NY: CoRR, 2020 [2023-02-27].https://arxiv.org/abs/2011.02455
[10] Hornik K, Stinchcombe M, White H. Multilayer feedforward networks are universal approximators[J]. Neural Networks, 1989, 2(5): 359−366 doi: 10.1016/0893-6080(89)90020-8
[11] Kraska T, Beutel A, Chi E H, et al. The case for learned index structures [C] //Proc of the 2018 Int Conf on Management of Data. New York: ACM, 2018: 489−504
[12] Tang Chuzhe, Wang Youyun, Dong Zhiyuan, et al. XIndex: A scalable learned index for multicore data storage [C] //Proc of the 25th ACM SIGPLAN Symp on Principles and Practice of Parallel Programming. New York: ACM, 2020: 308−320
[13] Wang Youyun, Tang Chuzhe, Wang Zhaoguo, et al. SIndex: A scalable learned index for string keys [C] //Proc of the 11th ACM SIGOPS Asia-Pacific Workshop on Systems. New York: ACM, 2020: 17−24
[14] Wang Zhaoguo, Chen Haibo, Wang Youyun, et al. The concurrent learned indexes for multicore data storage[J]. ACM Transactions on Storage, 2022, 18(1): 1−35
[15] 陈游旻,陆游游,罗圣美,等. 基于RDMA的分布式存储系统研究综述[J]. 计算机研究与发展,2019,56(2):227−239 doi: 10.7544/issn1000-1239.2019.20170849 Chen Youmin, Lu Youyou, Luo Shengmei, et al. Survey on RDMA-based distributed storage systems[J]. Journal of Computer Research and Development, 2019, 56(2): 227−239 (in Chinese) doi: 10.7544/issn1000-1239.2019.20170849
[16] Wei Xingda, Chen Rong, Chen Haibo, et al. 2021. XStore: Fast RDMA-based ordered key-value store using remote learned cache[J]. ACM Transactions on Storage, 2021, 17(3): 1−32
[17] Wei Xingda, Chen Rong, Chen Haibo. Fast RDMA-based ordered key-value store using remote learned cache [C] //Proc of the 14th USENIX Symp on Operating Systems Design and Implementation. Berkeley, CA: USENIX Association, 2020: 117−135
[18] Wang Jiachen, Ding Ding, Wang Huan, et al. Polyjuice: High-performance transactions via learned concurrency control [C] //Proc of the 15th USENIX Symp on Operating Systems Design and Implementation. Berkeley, CA: USENIX Association, 2021: 198−216
[19] Tu S, Zheng Wenting, Kohler E, et al. Speedy transactions in multicore in-memory databases [C] //Proc of the 24th ACM Symp on Operating Systems Principles. New York: ACM, 2013: 18−32
[20] Mao Hongzi, Schwarzkopf M, Venkatakrishnan S B, et al. Learning scheduling algorithms for data processing clusters [C] //Proc of the ACM Special Interest Group on Data Communication. New York: ACM, 2019: 270−288
[21] Kristo A, Vaidya K, Çetintemel U, et al. The case for a learned sorting algorithm [C] //Proc of the 2020 ACM SIGMOD Int Conf on Management of Data. New York: ACM, 2020: 1001−1016
[22] Marcus R, Negi P, Mao Hongzi, et al. Neo: A learned query optimizer[J]. Proceedings of the VLDB Endowment, 2019, 12(11): 1705−1718 doi: 10.14778/3342263.3342644
[23] Marcus R, Negi P, Mao Hongzi, et al. Bao: Making learned query optimization practical [C] //Proc of the 2021 Int Conf on Management of Data. New York: ACM, 2021: 1275−1288
[24] Kraska T, Alizadeh M, Beutel A, et al. SageDB: A learned database system [C/OL] //Proc of the 9th Biennial Conf on Innovative Data Systems Research. 2019 [2023-02-27].https://www.cidrdb.org/cidr2019/papers/p117-kraska-cidr19.pdf
[25] Ding Jialin, Marcus R, Kipf A, et al. SageDB: An instance-optimized data analytics system[J]. Proceedings of the VLDB Endowment, 2022, 15(13): 4062−4078 doi: 10.14778/3565838.3565857
[26] Li Pengfei, Hua Yu, Jia Jingnan, et al. FINEdex: A fine-grained learned index scheme for scalable and concurrent memory systems[J]. Proceedings of the VLDB Endowment, 2021, 15(2): 321−334 doi: 10.14778/3489496.3489512
[27] Dai Yifan, Xu Yien, Ganesan A, et al. From WiscKey to Bourbon: A learned index for log-structured merge trees [C] //Proc of the 14th USENIX Conf on Operating Systems Design and Implementation. Berkeley, CA: USENIX Association, 2020: 155−171
[28] Li Pengfei, Hua Yu, Zuo Pengfei, et al. ROLEX: A scalable RDMA-oriented learned key-value store for disaggregated memory systems [C] //Proc of the 21st USENIX Conf on File and Storage Technologies. Berkeley, CA: USENIX Association, 2023: 99−114
[29] 孟小峰,马超红,杨晨. 机器学习化数据库系统研究综述[J]. 计算机研究与发展,2019,56(9):1803−1820 doi: 10.7544/issn1000-1239.2019.20190446 Meng Xiaofeng, Ma Chaohong, Yang Chen. Survey on machine learning for database systems[J]. Journal of Computer Research and Development, 2019, 56(9): 1803−1820 (in Chinese) doi: 10.7544/issn1000-1239.2019.20190446
-
期刊类型引用(0)
其他类型引用(2)
下载:
计量
- 文章访问数: 538
- HTML全文浏览量: 67
- PDF下载量: 294
- 被引次数: 2
