一种优化三级缓存访问延迟的多核处理器调度方法及装置与流程

1.本技术涉及处理器技术领域，尤其涉及一种优化三级缓存访问延迟的多核处理器调度方法及装置。


背景技术：

2.在多核处理器芯片中处理器核的数量相对较多时，核间互联往往会选择mesh(无线网格)结构，例如arm的cmn(coherent mesh network，相干网状网络)网络。此时，l1 cache(一级缓存)和l2 cache(二级缓存)通常是由每个处理器核私有(某些架构下可能少数几个核共享l2cache，而l3 cache(三级缓存)则是分布的放置在mesh互联上，由所有处理器核一起共享。每一块分布的l3 cache会用于缓存一定地址范围内的内存数据，例如arm cmn网络中slc。由于mesh互联的面积较大，不同位置的处理器核访问同一块l3 cache的延迟的差距可能会达到几十个处理器执行周期的量级。如果多核调度能考虑到每个处理器核访问每个l3 cache块的延迟，则能提高单核的处理性能。
3.因此，本技术解决的技术问题是如何降低多核处理器对三级缓存的访问延迟。


技术实现要素：

4.本技术提供了一种优化三级缓存访问延迟的多核处理器调度方法及装置，能够降低各个处理器核对三级缓存的访问延迟，提高处理器的性能。
5.第一方面，本技术提供了一种优化三级缓存访问延迟的多核处理器调度方法，该方法包括：
6.构建各三级缓存块与各处理器核的跳步距离排序表；
7.构建各三级缓存块与内存地址的映射关系配置表；
8.获取新任务和候选处理器核队列；
9.查询步骤：根据新任务的访问地址和候选处理器核队列查询跳步距离排序表和映射关系配置表，得到目标处理器核；
10.将新任务分配到目标处理器核。
11.进一步的，上述构建各三级缓存块与各处理器核的跳步距离排序表，包括：
12.根据芯片拓扑结构构建各三级缓存块与各处理器核的跳步距离排序表。
13.上述实施例实现了三级缓存块和处理器核之间距离信息的获取。
14.进一步的，上述根据芯片拓扑结构构建各三级缓存块与各处理器核的跳步距离排序表，包括：获取芯片拓扑结构中各处理器核和各三级缓存块的位置；
15.距离获取步骤：基于路由算法得到处理器核的位置到各三级缓存块的跳步距离；
16.排序步骤：对各跳步距离进行排序，得到处理器核的跳步距离矩阵；
17.对各处理器核执行距离获取步骤和排序步骤，得到多个跳步距离矩阵；
18.根据多个跳步距离矩阵得到跳步距离排序表。
19.上述实施例通过使用路由算法，能够快速准确地获得处理器核到各三级缓存块之
间的跳步距离，从而能够得到准确的跳步距离排序表。
20.进一步的，候选处理器核队列是根据启发原则对各处理器核进行筛选得到的。
21.上述实施例通过启发原则获得候选处理器核队列，使得最终分配的目标处理器核满足不同角度上多核调度性能的优化。
22.进一步的，启发原则包括负载均衡策略、核敏感性策略和访问延迟策略。
23.上述实施例根据负载均衡策略、核敏感性策略和访问延迟策略得到候选处理器核队列，使得选出的目标处理器核同时满足负载均衡、核敏感性和访问延迟等多种性能上的优化。
24.进一步的，该方法还包括：在得到候选处理器核队列后，检测候选处理器核队列中处理器核的数量是否大于第一预设数值；若是，则执行查询步骤。
25.上述实施例避免了跳步距离排序表和映射关系配置表的无用查询，进一步优化了对多核处理器进行任务分配时的启发流程。
26.进一步的，上述根据新任务的访问地址和候选处理器核队列查询跳步距离排序表和映射关系配置表，得到目标处理器核，包括：
27.根据新任务的访问地址查询映射关系配置表，得到待访问缓存块；
28.根据待访问缓存块查询跳步距离排序表，得到候选处理器核队列中距离待访问缓存块最近的处理器核，并将其作为目标处理器核。
29.上述实施例根据新任务的访问地址来确定需要访问的三级缓存块，从而选择出距离被访问的三级缓存块最近的处理器核，避免了为完成任务访问远距离的三级缓存块造成的巨大延迟。
30.进一步的，该方法还包括：
31.在得到待访问缓存块后，检测待访问缓存块的数量是否大于第二预设数值；
32.若是，则根据新任务的访问地址、待访问缓存块、跳步距离排序表和映射关系配置表得到目标处理器核。
33.上述实施例避免了新任务需访问多个三级缓存块时容易导致的跳步距离排序表查询出错的问题，实现了对访问多个三级缓存块的新任务的分配。
34.进一步的，上述根据新任务的访问地址、待访问缓存块、跳步距离排序表和映射关系配置表得到目标处理器核，包括：
35.根据新任务的访问地址和映射关系配置表得到各待访问缓存块的地址权重；
36.根据跳步距离排序表和各待访问缓存块的地址权重，计算候选处理器核队列中各处理器核的访问延迟；将访问延迟最低的处理器核作为目标处理器核。
37.上述实施例以新任务在三级缓存块中的地址权重为依据，实现了对各处理器核执行新任务时对三级缓存的访问延迟的准确计算，确保了目标处理器核的访问延迟最小。
38.进一步的，上述根据跳步距离排序表和各待访问缓存块的地址权重，计算候选处理器核队列中各处理器核的访问延迟，包括：
39.根据跳步距离排序表获取处理器核到各待访问缓存块的距离；将处理器核到待访问缓存块的距离与待访问缓存块的地址权重相乘，得到处理器核到待访问缓存块的子延迟；
40.将处理器核到各待访问缓存块的子延迟相加，得到处理器核的访问延迟。
41.上述实施例避免了新任务访问多个三级缓存块时可能带来的流程出错，通过访问三级缓存块的地址权重来计算访问延迟，确保了访问多个三级缓存块的目标处理器核的延迟最低。
42.进一步的，该方法还包括：
43.响应于调度中断指令，基于各调度域进行调度域遍历，得到待均衡处理器；
44.将待均衡处理器中的进程迁移到当前处理器上。
45.上述实施例实现了多核处理器中负载均衡、处理器进程迁移的过程，避免了处理器因内部负载过高导致的进程延迟、性能降低。
46.进一步的，上述基于各调度域进行调度域遍历，得到待均衡处理器，包括：
47.将最底层的调度域作为当前调度域，对当前调度域进行遍历；
48.最大负载获取步骤：根据当前调度域的各调度组的负载值得到最大负载处理器；
49.判断当前调度域的负载不均衡度是否小于迁移代价；
50.若是，则将当前调度域的父调度域作为当前调度域；并返回最大负载获取步骤；否则将最大负载处理器作为待均衡处理器。
51.上述实施例给出了根据调度域和调度组对待均衡处理器的判断和获取步骤，实现了对需要进行负载均衡和进程迁移的处理器的准确判断。
52.进一步的，调度域包括位于同一级的多个三级调度域；三级调度域包括访问同一个三级缓存块的距离相同的若干个处理器核。
53.上述实施例通过增加三级调度域，使得本技术在进行负载均衡时，不会在同一节点的多个cpu中任意选择一个核，而是会优先选择访问三级缓存距离相同的核，从而优化了处理器在负载均衡中对三级缓存的访问延迟。
54.进一步的，上述根据当前调度域的各调度组的负载值得到最大负载处理器，包括：
55.若当前调度域中的调度组为三级调度域，则根据三级调度域中的处理器核的数量，以及各处理器核的负载计算三级调度域的负载值。
56.上述实施例给出的对三级调度域负载值的计算方法，避免了因三级调度域的组成结构不同导致的负载值的计算出错、负载均衡的结果出错。
57.第二方面，本技术提供了一种优化三级缓存访问延迟的多核处理器调度装置，该装置包括：
58.跳步距离构建模块(101)，用于构建各三级缓存块与各处理器核的跳步距离排序表；
59.映射关系构建模块(102)，用于构建各三级缓存块与内存地址的映射关系配置表；
60.获取模块(103)，用于获取新任务和候选处理器核队列；
61.查询模块(104)，用于根据新任务的访问地址和候选处理器核队列查询跳步距离排序表和映射关系配置表，得到目标处理器核；
62.分配模块(105)，用于将新任务分配到目标处理器核。
63.上述实施例提供的一种优化三级缓存访问延迟的多核处理器调度装置，通过构建三级缓存块和处理器核的跳步距离排序表，以及三级缓存块和内存地址的映射关系配置表，在接收到新任务后，根据新任务和候选处理器核队列查询这两张表，从而得到距离新任务所要访问的三级缓存块最近的目标处理器核并将新任务分配至其中，使得处理器核无需
为了完成新任务去访问远处的三级缓存块，从而降低各个处理器核对三级缓存的访问延迟，提高处理器的性能。
64.进一步的，该装置还包括：
65.遍历模块(201)，用于响应调度中断指令，基于各调度域进行调度域遍历，得到待均衡处理器；
66.迁移模块(202)，用于将待均衡处理器中的进程迁移到当前处理器上。
67.上述实施例给出了实现多核处理器中负载均衡、处理器进程迁移的装置，避免了处理器因内部负载过高导致的进程延迟、性能降低。
68.进一步的，上述遍历模块(201)包括：
69.底层遍历单元(21)，用于将最底层的调度域作为当前调度域，对当前调度域进行遍历；
70.负载处理单元(22)，用于根据当前调度域的各调度组的负载值得到最大负载处理器；
71.判断单元(23)，用于判断当前调度域的负载不均衡度是否小于迁移代价；
72.均衡单元(24)，用于将当前调度域的父调度域作为当前调度域；并返回负载处理单元(22)；或者将最大负载处理器作为待均衡处理器。
73.上述实施例给出了遍历模块(201)中待均衡处理器进行判断和获取的单元结构，实现了对需要进行负载均衡和进程迁移的处理器的准确判断。
74.第三方面，本技术实施例提供了一种计算机设备，包括存储器、处理器及存储在存储器上并可在处理器上运行的计算机程序，处理器执行计算机程序时执行如上述任一实施例的一种优化三级缓存访问延迟的多核处理器调度方法的步骤。
75.第四方面，本技术实施例提供了一种计算机可读存储介质，其上存储有计算机程序，计算机程序被处理器执行时实现如上述任一实施例的一种优化三级缓存访问延迟的多核处理器调度方法的步骤。
76.综上，与现有技术相比，本技术实施例提供的技术方案带来的有益效果至少包括：
77.本技术实施例提供的一种优化三级缓存访问延迟的多核处理器调度方法，通过构建三级缓存块和处理器核的跳步距离排序表，以及三级缓存块和内存地址的映射关系配置表，在接收到新任务后，根据新任务和候选处理器核队列查询这两张表，从而得到距离新任务所要访问的三级缓存块最近的目标处理器核并将新任务分配至其中，使得处理器核无需为了完成新任务去访问远处的三级缓存块，从而降低各个处理器核对三级缓存的访问延迟，提高处理器的性能。
附图说明
78.图1为本技术实施例提供的一种优化三级缓存访问延迟的多核处理器调度方法的流程图。
79.图2为本技术实施例提供的芯片拓扑结构的示意图。
80.图3为本技术实施例提供的目标处理器核获取步骤的流程图。
81.图4为本技术实施例提供的负载均衡步骤的流程图。
82.图5为本技术实施例提供的负载均衡时处理器的任务队列示意图。
83.图6为本技术又一实施例提供的待均衡处理器判断步骤的流程图。
84.图7为本技术实施例提供的一种优化三级缓存访问延迟的多核处理器调度装置的结构图。
85.图8为本技术实施例提供又一种优化三级缓存访问延迟的多核处理器调度装置的结构图。
86.图9为本技术实施例提供的遍历模块(201)的结构图。
具体实施方式
87.下面将结合本技术实施例中的附图，对本技术实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本技术一部分实施例，而不是全部的实施例。基于本技术中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本技术保护的范围。
88.请参见图1，本技术实施例提供了一种优化三级缓存访问延迟的多核处理器调度方法，该方法具体包括以下步骤：
89.步骤s01，构建各三级缓存块与各处理器核的跳步距离排序表。
90.步骤s02，构建各三级缓存块与内存地址的映射关系配置表。
91.步骤s03，获取新任务和候选处理器核队列。
92.步骤s04，根据新任务的访问地址和候选处理器核队列查询跳步距离排序表和映射关系配置表，得到目标处理器核。
93.步骤s05，将新任务分配到目标处理器核。
94.上述实施例提供的一种优化三级缓存访问延迟的多核处理器调度方法，通过构建三级缓存块和处理器核的跳步距离排序表，以及三级缓存块和内存地址的映射关系配置表，在接收到新任务后，根据新任务和候选处理器核队列查询这两张表，从而得到距离新任务所要访问的三级缓存块最近的目标处理器核并将新任务分配至其中，使得处理器核无需为了完成新任务去访问远处的三级缓存块，从而降低各个处理器核对三级缓存的访问延迟，提高处理器的性能。
95.其中，构建映射关系配置表的方式有很多种，例如地址均分策略：将全部的内存地址按照三级缓存块的数量进行均分，使得每个三级缓存块中所包括地址范围的大小是相同的；地址哈希策略：将内存地址进行哈希后放入各个三级缓存块中：层次化策略，将内存地址以层次化结构放入各个三级缓存块中，等等。具体地，三级缓存块slc(system level cache，系统级缓存)21和slc22的跳步距离排序表如下所示：
96.slc21 distance
97.[0098][0099]
slc22 distance
[0100]
coredistanceec221ec212ec232ec152ec143
…ꢀ
[0101]
各个三级缓存块与内存地址的映射关系配置表如下所示(注意：其中slc对应的地址空间不一定是连续的空间)：
[0102]
slc(三级缓存块)address range(地址范围)slc210x0～0xffffffffslc220x100000000～0x1ffffffffslc230x200000000～0x2ffffffff
…ꢀ
[0103]
具体地，面对候选处理器核队列，根据新任务分配的内存地址范围，在映射关系配置表中查到对应的l3 cache块的id，然后根据l3 cache块的id号到跳步距离排序表中查找所有候选的处理器核中距离l3 cache块最近的处理器核，将新任务放入该处理器核的任务队列中。
[0104]
请参见图2，在一些实施例中，上述构建各三级缓存块与各处理器核的跳步距离排序表，包括：根据芯片拓扑结构构建各三级缓存块与各处理器核的跳步距离排序表。
[0105]
上述实施例实现了三级缓存块和处理器核之间距离信息的获取。
[0106]
请参见图2，在一些实施例中，上述根据芯片拓扑结构构建各三级缓存块与各处理器核的跳步距离排序表，包括：
[0107]
获取芯片拓扑结构中各处理器核和各三级缓存块的位置。
[0108]
距离获取步骤：基于路由算法得到处理器核的位置到各三级缓存块的跳步距离。
[0109]
排序步骤：对各跳步距离进行排序，得到处理器核的跳步距离矩阵。
[0110]
对各处理器核执行距离获取步骤和排序步骤，得到多个跳步距离矩阵。
[0111]
根据多个跳步距离矩阵得到跳步距离排序表。
[0112]
以获取图2中的处理器核ec21到三级缓存块slc22之间的跳步距离为例，路由算法的具体实施方式为：ec21到节点xp05为1个跳步距离，节点xp05到xp15之间为1个跳步距离，
将跳步距离相加，得到ec21到slc22之间的跳步距离为2；以此类推进行查询得到ec21到各个三级缓存块之间的距离，并进行排序，得到跳步距离矩阵，进而得到跳步距离排序表。
[0113]
上述实施例通过使用路由算法，能够快速准确地获得处理器核到各三级缓存块之间的跳步距离，从而能够得到准确的跳步距离排序表。
[0114]
在一些实施例中，候选处理器核队列是根据启发原则对各处理器核进行筛选得到的。
[0115]
其中，启发原则为除本技术外其他的分配新任务至处理器调度队列的方法。
[0116]
上述实施例通过启发原则获得候选处理器核队列，使得最终分配的目标处理器核满足不同角度上多核调度性能的优化。
[0117]
在一些实施例中，启发原则包括负载均衡策略、核敏感性策略和访问延迟策略。
[0118]
其中，在mqms(multi-queue scheduling，多队列调度)方法中，当一个新任务进入系统时，系统会根据一定的启发原则将该任务放入相应的调度队列，每个调度队列独立进行调度。一个任务如果block(阻塞)了，再唤醒时也会尽量放在同一个队列中，从而减少因为cold cache或者访存延迟过长而引入的额外开销。
[0119]
改进前的启发原则主要考虑到负载均衡(比如选择负载相对较少的cpu核队列)、核敏感性(比如大小核)、访存延迟(比如优先选择本地存储对应的cpu核)等因素。
[0120]
在本技术中，也是根据这些启发原则生成的候选处理器核队列。
[0121]
上述实施例根据负载均衡策略、核敏感性策略和访问延迟策略得到候选处理器核队列，使得选出的目标处理器核同时满足负载均衡、核敏感性和访问延迟等多种性能上的优化。
[0122]
在一些实施例中，该方法还包括：在得到候选处理器核队列后，检测候选处理器核队列中处理器核的数量是否大于第一预设数值；若是，则执行查询步骤。
[0123]
其中，第一预设数值为1，查询步骤即为上述实施例中的步骤s04，根据新任务的访问地址和候选处理器核队列查询跳步距离排序表和映射关系配置表，得到目标处理器核。若候选处理器核队列中的核数量为1，则可省去查询步骤，直接将唯一的处理器核作为目标处理器核。
[0124]
具体地，如果现有的启发原则选出的处理器核仅有一个，则无需再进行跳步距离排序表和映射关系配置表的查询，直接将新任务分配至唯一的处理器核。
[0125]
上述实施例避免了跳步距离排序表和映射关系配置表的无用查询，进一步优化了对多核处理器进行任务分配时的启发流程。
[0126]
请参见图3，在一些实施例中，上述根据新任务的访问地址和候选处理器核队列查询跳步距离排序表和映射关系配置表，得到目标处理器核，包括：
[0127]
步骤s041，根据新任务的访问地址查询映射关系配置表，得到待访问缓存块。
[0128]
步骤s042，根据待访问缓存块查询跳步距离排序表，得到候选处理器核队列中距离待访问缓存块最近的处理器核，并将其作为目标处理器核。
[0129]
即根据新任务分配的内存地址范围，在映射关系配置表中查到对应的l3 cache块的id，然后根据l3 cache块的id号到跳步距离排序表中查找所有候选的处理器核中距离l3 cache块最近的处理器核，将新任务放入该处理器核的任务队列中。
[0130]
上述实施例根据新任务的访问地址来确定需要访问的三级缓存块，从而选择出距
离被访问的三级缓存块最近的处理器核，避免了为完成任务访问远距离的三级缓存块造成的巨大延迟。
[0131]
在一些实施例中，该方法还可以包括：
[0132]
在得到待访问缓存块后，检测待访问缓存块的数量是否大于第二预设数值。
[0133]
若是，则根据新任务的访问地址、待访问缓存块、跳步距离排序表和映射关系配置表得到目标处理器核。其中，第二预设数值为1。
[0134]
具体地，若待访问缓存块的数量小于等于第二预设数值，则执行上述步骤s042，即直接根据待访问缓存块查询跳步距离排序表，无需再查询映射关系配置表，在得到候选处理器核队列中距离待访问缓存块最近的处理器核后，将其作为目标处理器核。
[0135]
上述实施例避免了新任务需访问多个三级缓存块时容易导致的跳步距离排序表查询出错的问题，实现了对访问多个三级缓存块的新任务的分配。
[0136]
在一些实施例中，上述根据新任务的访问地址、待访问缓存块、跳步距离排序表和映射关系配置表得到目标处理器核，包括：
[0137]
根据新任务的访问地址和映射关系配置表得到各待访问缓存块的地址权重。
[0138]
根据跳步距离排序表和各待访问缓存块的地址权重，计算候选处理器核队列中各处理器核的访问延迟；将访问延迟最低的处理器核作为目标处理器核。
[0139]
具体地，如果在映射关系配置表中查到新任务对应的内存地址范围会涉及多块l3 cache，则在计算所有候选的处理器核到l3 cache块的距离时，先在跳步距离排序表中查出处理器核到每一块相关的l3 cache的距离，再按地址范围的权重计算出总的距离。
[0140]
上述实施例以新任务在三级缓存块中的地址权重为依据，实现了对各处理器核执行新任务时对三级缓存的访问延迟的准确计算，确保了目标处理器核的访问延迟最小。
[0141]
在一些实施例中，上述根据跳步距离排序表和各待访问缓存块的地址权重，计算候选处理器核队列中各处理器核的访问延迟，包括：
[0142]
根据跳步距离排序表获取处理器核到各待访问缓存块的距离；将处理器核到待访问缓存块的距离与待访问缓存块的地址权重相乘，得到处理器核到待访问缓存块的子延迟。
[0143]
将处理器核到各待访问缓存块的子延迟相加，得到处理器核的访问延迟。
[0144]
例如，以上述示例中的表格为例，假如新任务访问的内存空间中80％分布在slc21，20％分布在slc22，则处理器核ec21访问l3 cache的scl21块和scl22块的延迟为80％*1+20％*2＝1.2，而处理器核ec22访问l3 cache的scl21块和scl22块的延迟为80％*2+20％*1＝1.8。所以相比之下，1.2＜1.8，ec21的访问延迟更低，将新任务分配至ec21。
[0145]
上述实施例避免了新任务访问多个三级缓存块时可能带来的流程出错，通过访问三级缓存块的地址权重来计算访问延迟，确保了访问多个三级缓存块的目标处理器核的延迟最低。
[0146]
请参见图4和图5，在一些实施例中，该方法还包括：
[0147]
步骤s11，响应于调度中断指令，基于各调度域进行调度域遍历，得到待均衡处理器。
[0148]
步骤s12，将待均衡处理器中的进程迁移到当前处理器上。
[0149]
其中，调度中断指令是由操作系统的程序中设定的中断函数所实现的，中断函数
中设置了发出调度中断指令的时钟数，即每经过一定的周期/时钟数，便会发生一次调度中断。
[0150]
如图5所示，假设cpu0和cpu1分别分配了ac和bd，但是过了一段时间c执行完了，只剩下a，则明显cpu0的负载会比cpu1要低。为了解决这个问题，需要及时对进程进行“迁移”，将某个进程从一个cpu迁移到另一个cpu。现有的负载均衡方法通过调度域和调度组来控制任务迁移的方式，其中调度组是负载均衡的基本单位，迁移只能在同一调度域的调度组之间迁移。以下是改进前linux中调度域和调度组的定义。
[0151] 调度域调度组smt核线程mc共享l2的核核die节点共享l2的核numa集群节点
[0152]
上述实施例实现了多核处理器中负载均衡、处理器进程迁移的过程，避免了处理器因内部负载过高导致的进程延迟、性能降低。
[0153]
请参见图6，在一些实施例中，上述基于各调度域进行调度域遍历，得到待均衡处理器，具体可以包括如下步骤：
[0154]
步骤s111，将最底层的调度域作为当前调度域，对当前调度域进行遍历。
[0155]
步骤s112，根据当前调度域的各调度组的负载值得到最大负载处理器。
[0156]
步骤s113，判断当前调度域的负载不均衡度是否小于迁移代价。
[0157]
步骤s114，若是，则将当前调度域的父调度域作为当前调度域；并返回步骤s112；否则将最大负载处理器作为待均衡处理器。
[0158]
其中，最底层的调度域为smt调度域，即以线程为调度组的核调度域。
[0159]
具体地，当调度中断发生时，实现负载均衡的基本流程为：
[0160]
1.从当前cpu开始，由下至上遍历调度域，从最底层开始做负载均衡。
[0161]
2.在当前调度域中查找最繁忙的调度组，在最繁忙的调度组中找出最繁忙的cpu。
[0162]
3.如果当前调度域不满足迁移条件(负载不均衡的程度小于迁移的代价)，该调度域就需要作为一个调度组到上一层的父调度域中与其它组进行比较。
[0163]
4.如果当前调度域满足迁移条件，则将最繁忙的cpu的进程迁移到当前cpu上。
[0164]
其中由下至上遍历调度域的时候，记录每一级调度域中最繁忙的处理器的负载值和对应的是哪一个cpu。比如，假设当前调度发生在smt这一级，则记录下来当前的调度域，即核中负载最大的cpu。当进入mc这一级时，首先获得所有共享l2的每一个核中负载最大的cpu的负载值，然后比较判断哪个cpu的负载值最大。
[0165]
上述实施例给出了根据调度域和调度组对待均衡处理器的判断和获取步骤，实现了对需要进行负载均衡和进程迁移的处理器的准确判断。
[0166]
在一些实施例中，调度域包括位于同一级的多个三级调度域；三级调度域包括访问同一个三级缓存块的距离相同的若干个处理器核。
[0167]
具体地，在调度域和调度组的分级中增加一级ml3c，即三级调度域，这一级的调度域是访问每一个l3 cache块距离相同的核，调度组取决于上一级的调度域。
[0168][0169][0170]
仍然以上述拓扑结构为例，假设所有处理器核拥有独立的l1和l2，当前任务访问的l3cache块是slc21，则相关的调度域和调度组如下表所示(此处只关注slc21 distance表中列出的几个处理器核的情况)：
[0171][0172]
上述实施例通过增加三级调度域，使得本技术在进行负载均衡时，不会在同一节点的多个cpu中任意选择一个核，而是会优先选择访问三级缓存距离相同的核，从而优化了处理器在负载均衡中对三级缓存的访问延迟。
[0173]
在一些实施例中，上述根据当前调度域的各调度组的负载值得到最大负载处理器，包括：
[0174]
若当前调度域中的调度组为三级调度域，则根据三级调度域中的处理器核的数量，以及各处理器核的负载计算三级调度域的负载值。
[0175]
具体地，由于ml3c的不同调度域的核数量可能不一致，因此在ml3c作为调度组，die为当前调度域时，在die中寻找最繁忙的、负载最大的调度组时需要根据核的数量进行比较，即核的数量和每个核的负载一起组成了ml3c的总负载值。
[0176]
上述实施例给出的对三级调度域负载值的计算方法，避免了因三级调度域的组成结构不同导致的负载值的计算出错、负载均衡的结果出错。
[0177]
请参见图7，本技术另一实施例提供了一种优化三级缓存访问延迟的多核处理器调度装置，该装置具体可以包括：
[0178]
跳步距离构建模块101，用于构建各三级缓存块与各处理器核的跳步距离排序表。
[0179]
映射关系构建模块102，用于构建各三级缓存块与内存地址的映射关系配置表。
[0180]
获取模块103，用于获取新任务和候选处理器核队列。
[0181]
查询模块104，用于根据新任务的访问地址和候选处理器核队列查询跳步距离排序表和映射关系配置表，得到目标处理器核。
[0182]
分配模块105，用于将新任务分配到目标处理器核。
[0183]
上述实施例提供的一种优化三级缓存访问延迟的多核处理器调度装置，通过构建三级缓存块和处理器核的跳步距离排序表，以及三级缓存块和内存地址的映射关系配置表，在接收到新任务后，根据新任务和候选处理器核队列查询这两张表，从而得到距离新任务所要访问的三级缓存块最近的目标处理器核并将新任务分配至其中，使得处理器核无需为了完成新任务去访问远处的三级缓存块，从而降低各个处理器核对三级缓存的访问延迟，提高处理器的性能。
[0184]
请参见图8，在一些实施例中，该装置还包括：
[0185]
遍历模块201，用于响应调度中断指令，基于各调度域进行调度域遍历，得到待均衡处理器。迁移模块202，用于将待均衡处理器中的进程迁移到当前处理器上。
[0186]
上述实施例给出了实现多核处理器中负载均衡、处理器进程迁移的装置，避免了处理器因内部负载过高导致的进程延迟、性能降低。
[0187]
请参见图9，在一些实施例中，上述遍历模块201包括：
[0188]
底层遍历单元21，用于将最底层的调度域作为当前调度域，对当前调度域进行遍历。
[0189]
负载处理单元22，用于根据当前调度域的各调度组的负载值得到最大负载处理器。
[0190]
判断单元23，用于判断当前调度域的负载不均衡度是否小于迁移代价。
[0191]
均衡单元24，用于将当前调度域的父调度域作为当前调度域；并返回负载处理单元22；或者将最大负载处理器作为待均衡处理器。
[0192]
上述实施例给出了遍历模块201中待均衡处理器进行判断和获取的单元结构，实现了对需要进行负载均衡和进程迁移的处理器的准确判断。
[0193]
本技术提供的关于一种优化三级缓存访问延迟的多核处理器调度装置的具体限定，可参见上文中关于一种优化三级缓存访问延迟的多核处理器调度方法的实施例，于此不再赘述。上述一种优化三级缓存访问延迟的多核处理器调度装置中的各个模块可全部或部分通过软件、硬件及其组合来实现。上述各模块可以硬件形式内嵌于或独立于计算机设备中的处理器中，也可以以软件形式存储于计算机设备中的存储器中，以便于处理器调用执行以上各个模块对应的操作。
[0194]
以具体的例子表示本技术一种优化三级缓存访问延迟的多核处理器调度方法的实现过程：
[0195]
多核cpu调度方法分为两类：sqms(single queue scheduling，单队列调度)和mqms(multi-queue scheduling，多队列调度)。sqms基于全局的调度队列进行调度。它的优点是比较简单，可以较好的保证负载均衡性。它主要有两个缺点：
[0196]
1.可扩展性差：需要使用锁保证正确性，但是当处理器数量增加时，竞争变多，锁
的开销会直接影响性能。
[0197]
2.cache亲和度差：由于每一个cpu直接从全局的队列中选择下一个任务执行，导致同一个任务在不同cpu之间切换，从而无法重复利用之前缓存的数据。
[0198]
mqms方法针对sqms的问题提出。它存在多个分布的调度队列，通常每个处理器核一个队列，每一个队列根据一定的调度规则(比如轮转)独立进行调度。当一个新任务进入系统时，系统会根据一定的启发原则将该任务放入相应的调度队列。一个任务如果block了，再唤醒时也会尽量放在同一个队列中，从而减少因为cold cache或者访存延迟过长(例如numa中访问远端存储)而引入的额外开销。
[0199]
mqms主要有两个优点：一是避免了共享同一队列而导致的锁开销，二是更好的cache亲和度。它的主要缺点是负载均衡问题。如图5所示，假设cpu0和cpu1分别分配了ac和bd，但是过了一段时间c执行完了，则明显cpu0的负载会比cpu1要低。为了解决这个问题，我们需要及时对进程进行“迁移”，将某个进程从一个cpu迁移到另一个cpu。例如一个cpu队列时不时偷窥一下其它队列，看看其它队列是否相对比较满，如果比较满可以“偷”一个任务到自己的队列。linux中使用的o(1)调度器和cfs(completely fair scheduler，完全公平调度程序)都属于mqms类型。
[0200]
对于mqms而言，新任务进入系统时选择处理器核队列的启发原则和负载均衡的方法都会直接影响调度的性能。常见的新任务进入系统时选择处理器核队列的启发原则包括：
[0201]
1.随机。
[0202]
2.找一个当前任务更少的队列。
[0203]
3.asymmetric multiprocessor(非对称多处理机)考虑core sensitivity(核敏感性)，即在大小核结构中大核往往服务于低延迟或者ipc要求比较高的workload，而其它workload如果调度到大核可能不一定能带来性能提升，而且可能导致能耗增加。这里所谓敏感度，即为一个thread从大核换到小核时对性能的影响。
[0204]
4.numa中尽可能选择本地存储对应的cpu。
[0205]
负载均衡方法通过调度域和调度组来控制任务迁移的方式，调度组是负载均衡的基本单位，迁移只能在同一调度域的调度组之间迁移。以下是改进前linux中调度域和调度组的定义。
[0206] 调度域调度组smt核线程mc共享l2的核核die节点共享l2的核numa集群节点
[0207]
当调度中断发生时，cpu进行负载均衡的基本流程为：
[0208]
1.从当前cpu开始，由下至上遍历调度域，从最底层(smt)开始做负载均衡。
[0209]
2.在当前调度域中查找最繁忙的调度组，在最繁忙的调度组中找出最繁忙的cpu。
[0210]
3.如果当前调度域不满足迁移条件(负载不均衡的程度小于迁移的代价)，该调度域就需要作为一个调度组到上一层的父调度域中与其它组进行比较。
[0211]
4.如果当前调度域满足迁移条件，则将最繁忙的cpu的进程迁移到当前cpu上。
[0212]
在多核处理器芯片中处理器核的数量相对较多时，核间互联往往会选择mesh结构，例如arm的cmn网络。此时，l1 cache和l2 cache通常是由每个处理器核私有(某些架构下可能少数几个核共享l2 cache)，而l3 cache则是分布的放置在mesh互联上，由所有处理器核一起共享。每一块分布的l3 cache会用于缓存一定地址范围内的内存数据，例如arm cmn网络中slc。由于mesh互联的面积较大，不同位置的处理器核访问同一块l3 cache的延迟的差距可能会达到几十个处理器执行周期的量级。如果多核调度能考虑到每个处理器核访问每个l3 cache块的延迟，则能提高单核的处理性能。基于这一思想，本技术本专栏对新任务进入系统时选择处理器核的启发原则和负载均衡的方法分别进行改进。
[0213]
1.新任务进入系统时选择处理器核的启发原则。
[0214]
在mqms方法中，当一个新任务进入系统时，系统会根据一定的启发原则将该任务放入相应的调度队列，每个调度队列独立进行调度。一个任务如果block了，再唤醒时也会尽量放在同一个队列中，从而减少因为cold cache或者访存延迟过长而引入的额外开销。改进前的启发原则主要考虑到负载均衡(比如选择负载相对较少的cpu核队列)、核敏感性(比如大小核)、访存延迟(比如numa系统中优先选择本地存储对应的cpu核)等因素。本技术考虑到l3 cache访问延迟的影响，增加一个启发策略，根据任务需要访问的内存空间分布选择距离相对较近的处理器核执行。以下为具体流程：
[0215]
(1).在os启动之前，根据芯片拓扑结构生成每个l3 cache块到每个处理器核的跳步距离排序表，例如，如图2所示，形成slc21和slc22的跳步距离排序表如下所示：
[0216]
slc21 distance
[0217]
core(处理器核)distance(距离)ec211ec222ec142ec153ec233
…ꢀ
[0218]
slc22 distance
[0219]
coredistanceec221ec212ec232ec152ec143
…ꢀ
[0220]
完成mesh互联中各l3 cache块与内存地址的映射关系配置表的填写，例如arm cmn的sam(system address map)。注意，slc对应的地址空间不一定是连续的空间。
[0221]
slc(三级缓存块)address range(地址范围)slc210x0～0xffffffff
slc220x100000000～0x1ffffffffslc230x200000000～0x2ffffffff
…ꢀ
[0222]
当一个新任务进入系统时，首先仍然考虑负载均衡、核敏感性等因素，生成候选处理器核队列。如果有多个候选处理器核，根据新任务分配的内存地址范围，在映射关系配置表中查到对应的l3cache块id，然后根据l3 cache块的id号到跳步距离排序表表中查找所有候选的cpu核中距离最近的cpu核，最后将新任务放入该cpu核对应的任务队列中。
[0223]
如果在映射关系配置表中查到当前新任务对应的内存地址范围会涉及多块l3 cache，则在计算所有候选cpu核到l3 cache块的距离时，先在跳步距离排序表中查出到每一块相关的l3 cache的距离，再按地址范围的权重计算出总的距离。
[0224]
例如，以上述示例中的表格为例，假如新任务访问的内存空间中80％分布在slc21，20％分布在slc22，则cpu核ec21访问l3 cache的scl21块和scl22块的延迟为80％*1+20％*2，即
[0225]
1.2，而cpu核ec22访问l3 cache的scl21块和scl22块的延迟为80％*2+20％*1，即1.8。所以相比之下，ec21的访问延迟更低。
[0226]
2.负载均衡方法
[0227]
本技术考虑到l3 cache访问延迟的影响，在调度域和调度组的分级中增加一级ml3c，这一级的调度域是访问每一个l3 cache块距离相同的核，调度组取决于上一级的调度域。
[0228] 调度域调度组smt核线程mc共享l2的核核ml3c访问l3 cache距离相同的核共享l2的核die节点访问l3 cache距离相同的核numa集群节点
[0229]
仍然以上述拓扑结构为例，假设所有处理器核拥有独立的l1和l2，当前任务访问的l3cache块是slc21，则相关的调度域和调度组如下表所示(此处只关注slc21 distance表中列出的几个处理器核的情况)：
[0230][0231]
在负载均衡时，考虑到当前任务涉及的l3 cache块，尽可能将任务迁移到同一个调度域的核中执行。需要注意的是，由于ml3c的不同调度域的核数量可能不一致，因此在die中寻找最繁忙的调度组时需要根据核的数量进行比较。
[0232]
本技术可以优化每个处理器核访问l3 cache的延迟，从而改进单核处理器的性能。根据之前基于gem5 power单核模拟器的评估结果，当l3 cache的访问延迟从72个处理器时钟周期(基于cmn网络延迟计算的l3 cache平均访问延迟)提升到24个处理器时钟周期(基于cmn网络延迟计算的某个处理器核访问离自己最近的l3 cache的延迟)时，单个处理器核在spec17上的性能可以提升近10％。
[0233]
本技术实施例提供了一种计算机设备，该计算机设备可以包括通过系统总线连接的处理器、存储器、网络接口和数据库。其中，该计算机设备的处理器用于提供计算和控制能力。该计算机设备的存储器包括非易失性存储介质、内存储器。该非易失性存储介质存储有操作系统、计算机程序和数据库。该内存储器为非易失性存储介质中的操作系统和计算机程序的运行提供环境。该计算机设备的网络接口用于与外部的终端通过网络连接通信。处计算机程序被处理器执行时，使得处理器执行如上述任一实施例的一种优化三级缓存访问延迟的多核处理器调度方法的步骤。本实施例提供的计算机设备的工作过程、工作细节和技术效果，可以参见上文中关于一种优化三级缓存访问延迟的多核处理器调度方法的实施例，于此不再赘述。
[0234]
本技术实施例提供了一种计算机可读存储介质，其上存储有计算机程序，计算机程序被处理器执行时实现如上述任一实施例的一种优化三级缓存访问延迟的多核处理器调度方法的步骤。其中，所述计算机可读存储介质是指存储数据的载体，可以但不限于包括软盘、光盘、硬盘、闪存、优盘和/或记忆棒(memory stick)等，所述计算机可以是通用计算机、专用计算机、计算机网络、或者其他可编程装置。
[0235]
本实施例提供的计算机可读存储介质的工作过程、工作细节和技术效果，可以参见上文中关于一种优化三级缓存访问延迟的多核处理器调度方法的实施例，于此不再赘述。
[0236]
本领域普通技术人员可以理解实现上述实施例方法中的全部或部分流程，是可以通过计算机程序来指令相关的硬件来完成，所述的计算机程序可存储于一非易失性计算机可读取存储介质中，该计算机程序在执行时，可包括如上述各方法的实施例的流程。其中，本技术所提供的各实施例中所使用的对存储器、存储、数据库或其它介质的任何引用，均可包括非易失性和/或易失性存储器。非易失性存储器可包括只读存储器(rom)、可编程rom(prom)、电可编程rom(eprom)、电可擦除可编程rom(eeprom)或闪存。易失性存储器可包括随机存取存储器(ram)或者外部高速缓冲存储器。作为说明而非局限，ram以多种形式可得，诸如静态ram(sram)、动态ram(dram)、同步dram(sdram)、双数据率sdram(ddrsdram)、增强型sdram(esdram)、同步链路(synchlink)dram(sldram)、存储器总线(rambus)直接ram(rdram)、直接存储器总线动态ram(drdram)、以及存储器总线动态ram(rdram)。
[0237]
以上实施例的各技术特征可以进行任意的组合，为使描述简洁，未对上述实施例中的各个技术特征所有可能的组合都进行描述，然而，只要这些技术特征的组合不存在矛盾，都应当认为是本说明书记载的范围。以上所述实施例仅表达了本技术的几种实施方式，其描述较为具体和详细，但并不能因此而理解为对发明专利范围的限制。应当指出的是，对于本领域的普通技术人员来说，在不脱离本技术构思的前提下，还可以做出若干变形和改进，这些都属于本技术的保护范围。因此，本技术专利的保护范围应以所附权利要求为准。

技术特征：
1.一种优化三级缓存访问延迟的多核处理器调度方法，其特征在于，所述方法包括：构建各三级缓存块与各处理器核的跳步距离排序表；构建各所述三级缓存块与内存地址的映射关系配置表；获取新任务和候选处理器核队列；查询步骤：根据所述新任务的访问地址和所述候选处理器核队列查询所述跳步距离排序表和所述映射关系配置表，得到目标处理器核；将所述新任务分配到所述目标处理器核。2.根据权利要求1所述的方法，其特征在于，所述构建各三级缓存块与各处理器核的跳步距离排序表，包括：根据芯片拓扑结构构建各所述三级缓存块与各所述处理器核的所述跳步距离排序表。3.根据权利要求2所述的方法，其特征在于，所述根据芯片拓扑结构构建各所述三级缓存块与各所述处理器核的所述跳步距离排序表，包括：获取所述芯片拓扑结构中各所述处理器核和各所述三级缓存块的位置；距离获取步骤：基于路由算法得到所述处理器核的位置到各所述三级缓存块的跳步距离；排序步骤：对各所述跳步距离进行排序，得到所述处理器核的跳步距离矩阵；对各所述处理器核执行所述距离获取步骤和所述排序步骤，得到多个所述跳步距离矩阵；根据多个所述跳步距离矩阵得到所述跳步距离排序表。4.根据权利要求1所述的方法，其特征在于，所述候选处理器核队列是根据启发原则对各所述处理器核进行筛选得到的。5.根据权利要求4所述的方法，其特征在于，所述启发原则包括负载均衡策略、核敏感性策略和访问延迟策略。6.根据权利要求4所述的方法，其特征在于，所述方法还包括：在得到所述候选处理器核队列后，检测所述候选处理器核队列中所述处理器核的数量是否大于第一预设数值；若是，则执行所述查询步骤。7.根据权利要求1所述的方法，其特征在于，所述根据所述新任务的访问地址和所述候选处理器核队列查询所述跳步距离排序表和所述映射关系配置表，得到目标处理器核，包括：根据所述新任务的访问地址查询所述映射关系配置表，得到待访问缓存块；根据所述待访问缓存块查询所述跳步距离排序表，得到所述候选处理器核队列中距离所述待访问缓存块最近的所述处理器核，并将其作为所述目标处理器核。8.根据权利要求7所述的方法，其特征在于，所述方法还包括：在得到所述待访问缓存块后，检测所述待访问缓存块的数量是否大于第二预设数值；若是，则根据所述新任务的访问地址、所述待访问缓存块、所述跳步距离排序表和所述映射关系配置表得到所述目标处理器核。9.根据权利要求8所述的方法，其特征在于，所述根据所述新任务的访问地址、所述待访问缓存块、所述跳步距离排序表和所述映射关系配置表得到所述目标处理器核，包括：根据所述新任务的访问地址和所述映射关系配置表得到各所述待访问缓存块的地址
权重；根据所述跳步距离排序表和各所述待访问缓存块的所述地址权重，计算所述候选处理器核队列中各所述处理器核的访问延迟；将所述访问延迟最低的所述处理器核作为所述目标处理器核。10.根据权利要求9所述的方法，其特征在于，所述根据所述跳步距离排序表和各所述待访问缓存块的所述地址权重，计算所述候选处理器核队列中各所述处理器核的访问延迟，包括：根据所述跳步距离排序表获取所述处理器核到各所述待访问缓存块的距离；将所述处理器核到所述待访问缓存块的距离与所述待访问缓存块的所述地址权重相乘，得到所述处理器核到所述待访问缓存块的子延迟；将所述处理器核到各所述待访问缓存块的所述子延迟相加，得到所述处理器核的访问延迟。11.根据权利要求1所述的方法，其特征在于，所述方法还包括：响应于调度中断指令，基于各调度域进行调度域遍历，得到待均衡处理器；将所述待均衡处理器中的进程迁移到当前处理器上。12.根据权利要求11所述的方法，其特征在于，所述基于各调度域进行调度域遍历，得到待均衡处理器，包括：将最底层的调度域作为当前调度域，对所述当前调度域进行遍历；最大负载获取步骤：根据所述当前调度域的各调度组的负载值得到最大负载处理器；判断所述当前调度域的负载不均衡度是否小于迁移代价；若是，则将所述当前调度域的父调度域作为所述当前调度域，并返回所述最大负载获取步骤；否则将所述最大负载处理器作为所述待均衡处理器。13.根据权利要求12所述的方法，其特征在于，所述调度域包括位于同一级的多个三级调度域；所述三级调度域包括访问同一个所述三级缓存块的距离相同的若干个处理器核。14.根据权利要求13所述的方法，其特征在于，所述根据所述当前调度域的各调度组的负载值得到最大负载处理器，包括：若所述当前调度域中的调度组为所述三级调度域，则根据所述三级调度域中的所述处理器核的数量，以及各所述处理器核的负载计算所述三级调度域的负载值。15.一种优化三级缓存访问延迟的多核处理器调度装置，其特征在于，所述装置包括：跳步距离构建模块(101)，用于构建各三级缓存块与各处理器核的跳步距离排序表；映射关系构建模块(102)，用于构建各所述三级缓存块与内存地址的映射关系配置表；获取模块(103)，用于获取新任务和候选处理器核队列；查询模块(104)，用于根据所述新任务的访问地址和所述候选处理器核队列查询所述跳步距离排序表和所述映射关系配置表，得到目标处理器核；分配模块(105)，用于将所述新任务分配到所述目标处理器核。16.根据权利要求15所述的装置，其特征在于，所述装置还包括：遍历模块(201)，用于响应调度中断指令，基于各调度域进行调度域遍历，得到待均衡处理器；迁移模块(201)，用于将所述待均衡处理器中的进程迁移到当前处理器上。
17.根据权利要求16所述的装置，其特征在于，所述遍历模块(201)包括：底层遍历单元(21)，用于将最底层的调度域作为当前调度域，对所述当前调度域进行遍历；负载处理单元(22)，用于根据所述当前调度域的各调度组的负载值得到最大负载处理器；判断单元(23)，用于判断所述当前调度域的负载不均衡度是否小于迁移代价；均衡单元(24)，用于将所述当前调度域的父调度域作为所述当前调度域；并返回所述负载处理单元(22)；或者将所述最大负载处理器作为所述待均衡处理器。18.一种计算机设备，包括存储器、处理器及存储在存储器上并可在处理器上运行的计算机程序，其特征在于，所述处理器执行所述计算机程序时实现如权利要求1至14中任一项所述方法的步骤。19.一种计算机可读存储介质，其上存储有计算机程序，其特征在于，所述计算机程序被处理器执行时实现如权利要求1至14中任一项所述方法的步骤。

技术总结
本申请属于处理器技术领域，公开了一种优化三级缓存访问延迟的多核处理器调度方法及装置；该方法包括：构建各三级缓存块与各处理器核的跳步距离排序表；构建各三级缓存块与内存地址的映射关系配置表；获取新任务和候选处理器核队列；根据新任务的访问地址和候选处理器核队列查询跳步距离排序表和映射关系配置表，得到目标处理器核；将新任务分配到目标处理器核。本申请能够降低各个处理器核对三级缓存的访问延迟。存的访问延迟。存的访问延迟。


技术研发人员：刘丹 苟鹏飞
受保护的技术使用者：北京市合芯数字科技有限公司
技术研发日：2023.07.17
技术公布日：2023/9/9