多核共享cache确定性技术

虞保忠，周 霆，李运喜，黄凡帆

(中航工业西安航空计算技术研究所 第三研究室，陕西 西安 710010)

0 引 言

多核共享cache确定性是多核应用于嵌入式实时系统所需要解决的关键技术。所谓确定性是指在给定输入条件下，计算机能够在确定的时间输出确定的结果，即时间和计算结果确定。多核系统由于多个处理器核心共享cache，在并行运行时会竞争cache，导致cache抖动，影响软件运行时序，计算机不能在确定的时间完成计算任务，这就是多核共享cache确定性问题。通用领域对时间确定性并不敏感，只需要能够输出正确的结果，时间不确定性并不是功能问题。然而在实时确定性要求较高的安全应用领域，如工业控制、医疗、航空航天、汽车等，对计算机软件运行时序非常敏感，时间上的不确定性可能引发灾难性后果，因此确定性是实时系统关键需求。共享cache竞争冲突，微观上影响CPU取指和内存读写时间的不确定性，宏观上导致应用执行时间的波动，影响软件服务质量，在安全关键领域甚至降低了软件实时性。在多核平台构建安全关键系统需要重点考虑共享cache冲突干扰问题。Tim Loveless提出了构建安全多核系统需要面临共享cache确定性关键技术挑战[1]，美国联邦航空局一直在研究多核应用于航空领域，针对多核共享cache提出了一些确定性分析和缓解建议[2]。本研究为了解决嵌入式实时系统多核并行时竞争共享cache冲突问题，在实时操作性中设计并实现cache确定性缓解策略，减少共享cache冲突，降低多核之间互扰，保证软件执行时间的确定性，通过实验对比分析，经过确定性缓解后，程序运行时间确定。

1 国内外研究

多核共享cache竞争冲突是普遍存在的问题，图1是典型的多核共享cache结构，核在访问L2 cache会产生竞争冲突，导致cache抖动、访问延迟等问题。国内外安全关键系统领域研究者深入分析共享cache确定性问题引发的原因、影响因素及产生的后果，通过消除或降低影响因素的方式缓解共享cache确定性问题。

图1 多核共享cache冲突

CAST32A[2]是软件认证指南，提出了多核需要解决重点解决多核之间的互相干扰问题，特别是共享cache竞争冲突导致的确定性问题。安全认证过程应当考虑共享cache的确定性影响因素，采用硬件或软件方法缓解共享cache的确定性问题。欧洲航空安全委员会研究的航空系统应用多核项目提出需要对多核共享cache进行确定性影响分析，明确影响边界及危害等级，并需要采取缓解措施。这两项研究明确提出了安全关键领域应用多核技术所带来的共享cache冲突问题。由于硬件平台的通用性，并没有针对安全关键领域提供硬件层的确定性技术支持，因此需要重点从软件层面采取确定性缓解措施。国内外学者意识到了共享cache确定性问题带来的服务质量、安全性、实时性等问题，分别从硬件和软件层提出了共享cache缓解方法，包括cache分区、cache锁等机制。Awan M A等提出动态资源调度机制解决混合安全关键系统中共享cache确定性问题[3]。

一些多核处理器，如T2080平台在硬件层面提供共享cache分区能力，把共享cache按核分配。这种分配方式是按行分配原则，每个cache组有16行，根据读、写方式，可允许每个处理器核以读或写方式使用指定的cache行。因此一个处理器核能够使用的共享cache容量是0/16、1/16、2/16…至16/16的总cache大小。操作系统在给核分配共享cache容量时，按比例分配，保证每个核占用独立的cache空间，避免共享cache竞争冲突。这种cache分配属于静态分区能力，cache分配到核，而不能随应用分配。

Intel®Xeon®E5 2600 v3系列服务器处理器引入了Cache Allocation Technology(CAT)[4]和Cache Monitoring Technology(CMT)[5]能够给应用分配私有共享cache空间。在硬件层提供共享cache的分配能力，CAT为cache空间管理控制提供软件可编程接口，由操作系统根据应用实际需求分配资源ID、资源容量，并分配到指定处理器核上调度，能够实现对应用程序进行共享cache分配管理。CPU提供一套寄存器和接口中监控cache事件，CMT可在多核平台上同时监控多个应用程序的cache使用情况。

硬件独有的cache分区能力不具备通用性，很多货架产品并不支持这种能力。Sparsh Mittal[6]意识到共享cache带来的性能损失、缺乏公平性及较低服务质量(QoS)等问题，因此研究了一些多核共享cache分区技术。Mehrzad Nejat等[7]为了提升多核共享cache效能，提出了多核平台的动态调频调压及运行cache分区技术，在保证服务质量前提下节约功耗。而Saad Zia Sheikh等[8]在多核实时平台上提出了动态cache分区技术，满足多核系统实时性和确定性需求。

共享cache运行时动态分区[8-13]技术能够一定程序缓解共享cache确定性问题，但是它们依赖于硬件提供的cache分区能力[4,5]。由于多数货架产品不具备这样的能力，特别是嵌入式系统领域，这就极大限制了共享cache分区应用场景。因此需要能够不依赖于硬件，且能够满足实时性需求的cache确定性缓解技术。Zheng W等提出在任务调度和cache锁方面进行优化[14]，以实现cache的最大效能，这种方法针对特定的任务集合，不能满足不同应用的需求，且不能解决cache确定性问题。Elena Lucherini[15]和Holtryd NR等[16]研究通用计算系统中的内存页着色技术，通过页着色实现共享cache的分区，基于Linux系统实现，修改内存分配器以实现页着色。这种页着色技术的实现依赖Linux的内存管理机制，不具备实时性，不能应用于多核实时系统领域。

本文在国产实时653操作系统中实现共享cache分区和共享cache染色方法，通过这两种方法达到缓解多核共享cache确定性问题。653操作系统是遵守航空653标准的实时分区操作系统，具备时空隔离能力、多核支持能力、分区与核亲和设置能力，将处理器核的cache容量需求抽象成分区的cache容量需求，解决机载应用多核共享cache确定性问题。

2 基于路的共享cache分区

基于路的共享cache分区是按cache路分配给处理器核。cache的组成结构由路、组构成，共享cache有N个组，每个组内有M路(8路、16路)，按路分配的就是把每个组内的各路cache分配给固定的核。

这种基于路cache分区策略(way-based)通常是通过利用硬件级支持来实现。Power PC T2080平台支持共享L2 cache在路一级别的划分，通过对一组共享cache控制寄存器的配置，能够做到将L2 cache中指定的路分配给指定的处理器核心，同时能够指定该处理器核心对所分配的cache 路的操作权限，如读时分配、写时分配。读时分配是指处理器核在读内存操作时，允许其分配该路cache，将读的内存数据缓存在cache中，提升读内存性能；写时分配是指处理器核在写内存时，允许其分配该路cache，将待写数据缓存在cache中，不直接写内存，提升写内存性能。

基于路的cache分区策略示意如图2所示，在一个四路组相联的共享cache结构中，将cache的第一路和第二路分配给Core0，第三路和第四路分配给Core1，两个核分别占用每个cache组的两路cache，达到两个核各独占50%共享cache容量的目的。这种cache分区策略需要操作系统提供配置界面，针对每种硬件平台提供配置数据。用户通过配置界面为每个核配置相应的cache路。

图2 基于路的cache分区策略

操作系统的基于路的共享cache分区设计实现如图3所示。操作系统对外提供共享cache分配数据配置接口，在操作系统开发环境中进行配置，配置数据以XML数据形式传递给操作系统。用户分别配置每个CPU核能够使用的cache路，共享cache是16路组相联，每一路都可独立配置。每路配置数据包括能够访问的核集和访问模式。核集是一个32位数，每一位表示一个核，为0表示该核能够访问此路cache，为0表示该核不能访问此路cache。访问模式是读、写操作，读配置为1时表示该核读内存时能够分配此路cache，为0时表示该核读内存时不能够分配此路cache；写配置为1时表示该核写内存时能够分配此路cache，为0时表示该核写内存时不能够分配此路cache。通过这种细粒度的配置控制，严格控制核访问内存时的cache操作行为，避免多核分配同一路cache时的竞争冲突。L2CachePartitionPolicy根据配置数据生成硬件能够识别的分区策略，转换成对应的硬件参数，并且由L2CachePartition将策略写入到硬件中，开启平台的L2 cache分区功能，每个CPU核只能使用分配的cache行，避免cache路竞争。多核之间的cache路隔离机制给用户提供了一种可配置的cache私有化划分方法，允许用户根据实际应用场景按需分配，是一种非常灵活的配置方法，具有硬件依赖性，同时也需要用户能够准确估算各处理器核需要的cache容量。

图3 基于路的Cache分区流程

cache分区属于静态分配机制，在系统初始化阶段根据配置数据为每个核分配相应的共享cache路及访问模式，分配方式与核相关，运行时无法动态修改，运行于该核上的所有应用共享这些cache空间。因此这种cache分区策略属于按核分配，无法根据核上应用动态分配，能够在一定程度上缓解多核共享cache确定性一，但是牺牲了共享cache利用率，且有一定的局限性。

3 基于组的共享cache染色

基于组的共享cache染色是一种硬件无关的共享cache分区方法。与基于路的共享cache分区不同，它是把共享cache中的N个组分成若干份，每个核一份，每个核使用独立的cache组。操作系统将页着色设计作为一项配置项向用户提供，为用户提供cache确定性的解决策略，根据处理器核数确定页色数目，做到每个核一种页色。

共享cache的组织结构如图4所示，内存地址的Set index域索引至具体的cache组，而组内的cache路是全相联。cache染色分区的目的是不同核访问不同的cache组，其原理就是不同核访问的物理地址的Set index域不同。所以操作系统的共享cache染色设计实现是对处理器核上运行分区的物理地址分配管理，按照对应的色域进行分区物理地址空间分配。

图4 cache组织结构

操作系统的页着色分配对象为653分区，如图5所示。每个分区绑定在固定核上运行，操作系统给分区分配固定颜色的内存页。操作系统重新设计内存分配器，分区的内存空间按页分配，内存空间按页管理，且标识相应的颜色，不同颜色的内存映射到不同的共享cache组。在分区初始化阶段分配若干个内存页。通过静态分配方式给各分区分配对应颜色的物理内存。具体设计流程包括：操作系统配置项目根据具体的处理器平台为用户提供cache染色的具体信息，包括是否使能cache染色、操作系统可提供的颜色数目、cache大小、每种颜色的cache大小等信息，用户依据配置信息为每个分区配置分区所需要的cache颜色，操作系统依据用户的配置在启动阶段为每一个分区分配与该分区配置的cache颜色数量匹配的内存地址，完成每一个分区的虚拟地址与物理地址的映射，保证不同分区的物理地址页按照页着色算法的映射关系被映射到不同的cache块中，如图5所示。

图5 确定性多核操作系统cache着色设计框架

共享cache确定性缓解技术与硬件平台相关，操作系统在启动过程中需要获取硬件的cache信息，包括容量、组织结构、地址索引段等。将这些信息作为cache分区的输入数据，操作系统根据这些数据给分区分配内存空间段、cache容量。

用户在配置项目中根据操作系统提供的具体处理器信息完成对各个应用分区的cache颜色的划分。操作系统中的cache染色分组设计如图6所示，其主要涉及操作系统的空间管理和任务调度。根据平台的共享cache配置信息获取接口获取共享cache的一些配置参数，同时获取平台的CPU核数。将共享cache按照核数分成若干组，计算组大小及标识出内存地址中的cache组标识位。空间管理模块按组进行内存分配管理，每一组内存地址映射到对应的cache组。在给任务分配内存空间时，根据任务所属的CPU核从对应的内存组中分配内存。因此，最终结果是CPU核调度任务运行时，只能占用固定的cache组，不同核之间使用单独的cache组。

图6 共享cache染色分组流程

4 实验结果

4.1 实验环境

本文在国产实时653操作系统中实现并验证共享cache分区和共享cache染色方法，硬件测试环境如图7所示，1台PC机、1台Power PC T2080目标机、1台国产FT2000A/HK目标机，通过1台以太网交换机连接，用于加载待测试程序及调试控制；目标机的串口通过1台N-port，经以太网交换机连接到PC机，用于查看目标机程序的执行输出。

图7 硬件测试环境

4.2 实验方法

本实验方法是在多核平台中(2核和4核)，每个处理器核运行访存密集型测试程序，连续多次运行，统计测试程序每次运行时间，通过程序运行时波动性验证确定性效果，运行时间越稳定，确定性越好，偶尔出现运行时间较大波动的，则确定性较差。

T2080是四核处理器平台，2 MB共享cache，在国产操作系统中构建4个应用分区，每个核上一个应用分区；FT2000AHK是双核处理器平台2 MB共享cache，构建2个应用分区。每个应用分区内执行高频次的内存访问，通过跨cache行的方式触发共享cache不命中事件，引发多核并发访问共享cache。针对基于路的共享cache分区方法，通过配置数据平均分配共享cache，测试每个核上测试程序执行时间，测试单核情况下测试程序执行时间，测试不开启基于路的共享cache分区时每个核上测试程序执行时间。针对基于组的共享cache染色方法，通过物理地址配置方式，使每个分区坐落在不同的cache组，测试每个核上程序执行时间，测试单核情况下测试程序执行时间及不开启基于组的共享cache染色方法时每个核上测试程序执行时间。FT2000AHK本身不支持共享cache分区，因此只测试验证了基于组的共享cache染色方法。分别测试单核无冲突干扰、多核不开启共享cache确定性缓解措施及开启确定性缓解措施后每个测试程序执行时间波动性。

4.3 结果分析

图8是T2080平台上的共享cache确定性缓解测试数据。该平台四核共享二级cache，提供硬件层的cache分区能力及禁止二级cache的能力。因此分别测试了单核、多核基于组的cache染色分区、多核cache不分区、禁止二级cache及多核基于路的cache分区的配置下测试程序的性能。如该图所示，横轴是测试程序运行次数，纵轴是测试程序运行时间，在单核情况下，测试程序性能最优，稳定性也较好，这是由于单核独占共享cache，没有核间的竞争冲突；而多核不分区情况下，测试程序性能会出现多次抖动，这些抖动是由核间的共享cache竞争冲突产生；在关闭共享cache情况下，测试程序性能最差，但是稳定性好；基于路的cache硬件分区配置下，性能稍优于禁止共享cache的配置，且稳定性较好；基于组的cache染色分区性能与不分区的配置相当，且稳定性好。cache硬件分区和cache染色分区都能够在一定程序上缓解确定性问题，但是硬件分区是针以核为对象分配cache行，多核不会共享同一cache行，共享数据也就需要每个核单独加载；而cache染色分区是以任务为对象分配cache组，多核共享的数据只需要一个核加载，因此cache染色分区的性能稍优于cache硬件分区。

图8 T2080共享cache确定性缓解测试

图9是FT2000平台上的共享cache确定性缓解测试数据。由于该平台硬件层不提供cache分区能力，因此使用平台无关的cache染色技术进行cache分区。如该图所示，横轴是测试程序运行次数，纵轴是测试程序运行时间，在单核情况下，测试程序性能最优，稳定性也较好，这是由于单核独占共享cache，没有核间的竞争冲突；而双核不分区情况下，测试程序性能会出现多次抖动，这些抖动是由核间的共享cache竞争冲突产生；在双核分区情况下，测试程序性能较稳定，没有抖动现象。

图9 FT2000共享Cache确定性测试结果

共享cache确定性缓解技术实验结果表明，无缓解措施情况下，程序在T2080和FT2000平台上运行时间会偶尔出现较大波动，而经过缓解措施后，程序运行时间平稳，平台上能够取得较好的确定性效果。

5 结束语

本文针对多核平台的653操作系统设计实现共享cache分配管理，根据应用分区的cache需求进行分配。这种cache分区策略能够避免共享cache竞争冲突，确定性缓解机制作为操作系统的配置能力，无论多核处理器是否具备共享cache硬件级分区能力，都能够在操作系统层实现共享cache分区。该方法不增加额外硬件开销，对操作系统改动很少，只涉及到存储空间管理的改造，在不影响系统性能前提下提升多核系统确定性。在注重安全性实时性的安全关键领域，确定性高于计算性能，操作系统通过设计cache分区方法缓解确定性问题。