一种NUMA架构下平衡多线程间访存延迟的调度系统及方法

摘要

本发明公开了一种NUMA架构下平衡多线程间访存延迟的调度系统及方法，所述系统包括检测模块、采样模块、分析模块、判断模块和调度模块，通过采样保存多线程程序运行过程中每个线程的访存信息，预测分析该多线程程序中各线程的访存延迟是否不平衡，根据分析结果进行合理的调度，对远端访存的线程访问变量进行迁移调度至线程所在节点或使用交错存放将其平均分配到各节点上，从而保证各线程的访存延迟基本相等。本发明通过平衡多线程间访存延迟的方式，优化多线程程序在NUMA架构下的运行性能，本发明通过一种细粒度，有针对性的方式进行实时调度，使多线程程序取得并行区域的性能优化。

说明书

技术领域

本发明属于计算机体系结构下的多线程性能优化领域，更具体的，涉 及一种NUMA架构下平衡多线程间访存延迟的调度系统及方法。

背景技术

非一致访存(NUMA)架构是目前流行的商用服务器架构之一，它采 用了分布式存储器模式，且其中所有节点的处理器都可以访问全部的物理 内存，易于管理，可扩充性好，因此得到了广泛的应用。

在NUMA架构中，每个CPU访问的内存可以分为两种：与CPU在同 一个节点的内存称为本地内存，访问延迟非常低；与CPU在不同节点上的 内存叫做远端内存，对于远端内存的访问，CPU需要通过节点互联的方式 进行，所以其访问延迟要比本地内存的访问延迟长。这种访存延迟的不一 致性是NUMA架构的最主要特点，但它却给程序的调度和运行带来了困难， 如果没有得到合理的线程以及数据分配，那么很有可能导致该程序中所有 的访存操作都成为远端访存，从而经历较大的访存延迟，程序运行时间大 大延长，使程序的性能大打折扣。当然，这些由于远端访存造成的延迟可 以通过系统仔细地将程序的线程和它所用的数据协同调度进一步减少或消 除。

针对程序在NUMA架构下运行的特殊性，目前已经提出了一些NUMA 感知的调度算法。大部分NUMA感知的调度算法仅是针对单个线程，或者 针对多个线程时仅单纯地将各个线程独立开来考虑，并没有考虑到多线程 并行时的同步问题。

对于运行过程中存在线程同步操作的多线程程序，在NUMA架构下运 行时需要考虑各个线程的运行速度问题，如果在需要达到同步的线程中存 在一些线程，由于执行的远端访存较多，导致运行速度慢，那么该线程成 为了拖累程序运行速度的关键线程，这个时候为了减少其他线程远端访存 所做的工作，其对于最终程序所表现出来的整体性能并不能有很好的提高。 现有的针对NUMA架构下程序运行性能的优化工具中，缺乏针对多线程之 间访存延迟均衡这一问题的优化方式。相应地，本领域亟需寻找一种适用 于NUMA架构下平衡多线程访存延迟的方法。

发明内容

针对现有技术的以上缺陷或不足，本发明提出一种NUMA架构下平衡 多线程间访存延迟的调度系统及方法。利用本发明中的系统及方法，相应 能够有效解决由于NUMA架构下访存行为的非一致性导致的多线程程序各 线程间访存延迟的不一致问题，显著提高了NUMA架构下分析调度的实时 性，大大优化了NUMA架构下程序运行性能。

为实现上述目的，本发明一种NUMA架构下平衡多线程间访存延迟的 调度系统，其特征在于，所述系统包括检测模块、采样模块、分析模块、 判断模块和调度模块，其中，

检测模块，用于探测程序是否进入多线程并行执行区域，还用于在探 测程序进入多线程并行执行区域后，启动采样模块；

采样模块，用于对多线程程序运行过程中每个线程的访存行为进行采 样，并将采样过程中获取的访存信息保存；

分析模块，一方面用于根据所述采样模块获取的访存信息，定期对所 述多线程程序中各线程的访存延迟不平衡度进行评估，还用于针对发生不 平衡现象的多线程程序进行访存行为分析，此外，所述分析模块还用于根 据所述采样模块获取的访存信息进行访存规律分析；

判断模块，用于根据所述访存延迟不平衡度判断是否发生多线程间访 存延迟不平衡现象，同时，还用于在访存延迟不平衡现象发生时进一步判 断线程访问变量是否仅由一个线程访问、线程访问变量与访问该变量的线 程是否处于同一个节点及线程访问变量大小是否小于第二阈值Size，此外， 所述判断模块，还用于判断程序多线程并行执行的区域是否结束；

调度模块，用于根据所述分析模块的访存行为分析和访问规律分析， 及判断模块的判断结果对远端访存的线程访问变量进行迁移调度至线程所 在节点或使用交错存放将其平均分配到各节点上。

作为进一步优选的，所述访存信息包括发起访存行为的线程ID，访存 行为的目的地址，完成访存行为所耗费的时钟周期数和访存行为的类型。

作为进一步优选的，所述访存延迟不平衡度具体为：

ξ_T＝|D_T-D_avg|/D_avg

其中，ξ_T为线程T的访存延迟不平衡度，D_T为线程T的平均访存延迟， D_avg为所有线程的平均访存延迟。

作为进一步优选的，所述访存行为分析具体包括：

根据所述采样模块获取的访存信息，估计每个线程访问变量的线程平 均访存延迟，并依次将线程平均访存延迟最大的线程访问变量交由判断模 块进行处理。

作为进一步优选的，所述访问规律分析具体为：观察多线程程序中每 个线程访问变量中是否没有被多个线程共同访问的线程访问变量子块。

作为进一步优选的，所述采样模块还用于保存采样过程中为线程访问 数据分配的内存大小及分配的内存地址。

按照本发明的另一个方面，提出了一种基于上述系统的NUMA架构下 平衡多线程间访存延迟调度系统的调度方法，其特征在于，包括以下步骤：

(1)检测模块检测程序是否进入多线程并行执行区域，一旦发现程序 处于多线程并行执行区域，立即启动采样模块；

(2)采样模块持续对程序的多线程访存行为进行采样，并将采样获取 的访存信息根据线程ID进行分类并保存，根据访存行为的时间顺序为每个 线程建立一个访存事件流，并通过分析模块不断更新计算每个线程的平均 访存延迟；

(3)分析模块定期对各线程的访存延迟不平衡度进行评估；

(4)通过判断模块判断各线程的访存延迟不平衡度是否大于第一阈值 Threshhold；若是，则跳转至步骤(5)，否则，继续执行步骤(3)；

(5)分析模块对多线程程序进行访存行为分析，根据估计的每个线程 访问变量的线程平均访存延迟，选取线程平均访存延迟最大的线程访问变 量，并将该线程访问变量交由判断模块进行处理；

(6)判断模块判断所述线程访问变量是否仅由一个线程访问，若是， 则跳转至步骤(7)，否则跳转至步骤(8)。

(7)判断模块进一步判断所述线程访问变量与访问该变量的线程是否 处于同一个节点，若是，则返回步骤(5)分析模块依次选取下一个访存延 迟最大的线程访问变量进行访存行为分析，否则，调度模块将该线程访问 变量迁移至访问该变量的线程所在节点；

(8)判断模块进一步判断所述线程访问变量大小是否小于第二阈值 Size，若是，则转入步骤(9)，否则转入步骤(10)；

(9)将该线程访问变量复制分发到NUMA架构下的各个节点；

(10)分析模块根据所述采样模块获取的访存信息对多线程程序进行 访问规律分析，若所述线程访问变量中没有被多个线程共同访问的线程访 问变量子块，则转入步骤(10-1)，否则转入步骤(10-2)；

(10-1)将各线程访问的线程访问变量子块分别存放到各线程所在的节 点；

(10-2)通过交错存放将所述线程访问变量平均分配到NAMU架构下 的各个节点上；

(11)判断模块判断程序多线程并行执行的区域是否结束，若否，则 返回步骤(3)继续执行；否则调度结束。

作为进一步优选的，所述访存信息包括发起访存行为的线程ID，访存 行为的目的地址，完成访存行为所耗费的时钟周期数和访存行为的类型。

作为进一步优选的，所述访存延迟不平衡度具体为：

ξ_T＝|D_T-D_avg|/D_avg

其中，ξ_T为线程T的访存延迟不平衡度，D_T为线程T的平均访存延迟， D_avg为所有线程的平均访存延迟。

作为进一步优选的，所述采样模块还保存采样过程中为线程访问变量 分配的内存大小及分配的内存地址。

总体而言，按照本发明点的以上技术方案与现有技术相比，主要具备 以下的技术优点：

1、能实现更细粒度，更有针对性的优化。本发明中提出的整个平衡调 度过程都只针对多线程程序并行运行的部分，这正是多线程程序在NUMA 架构下运行时容易由于访存不一致性导致性能损耗的部分。同时，本发明 中提出的方案能够针对每一个线程访问变量做出优化调整，相比于现有技 术，该调整粒度更合理也更能发现访存不一致导致的问题。

2、本发明中提出的调度是一种实时分析调度方法，多线程程序在 NUMA架构下每一次的运行都存在与上一次不尽相同的地方，这种实时的 分析调度方式能够更好地针对每一次运行过程的特点进行优化，摒弃了现 有技术中离线、静态分析的缺陷。

3、本发明中提出的调度方式能够实现完全自动化的优化行为，不需要 用户参与。所有的优化工作对于用户来说是完全透明的，相比于现有技术， 本发明不需要对用户层代码做任何的修改等工作。

附图说明

图1为本发明NUMA架构下平衡多线程间访存延迟的调度系统框架示 意图；

图2为与本发明系统对应的NUMA架构下平衡多线程间访存延迟的调 度方法流程图。

具体实施方式

为了使本发明的目的、技术方案及优点更加清楚明白，以下结合附图 及实施例，对本发明进行进一步详细说明。应当理解，此处所描述的具体 实施例仅仅用以解释本发明，并不用于限定本发明。

如图1所示，本发明一种NUMA架构下平衡多线程间访存延迟的调度 系统，所述系统包括检测模块、采样模块、分析模块、判断模块和调度模 块，其中，

检测模块，用于探测程序是否进入多线程并行执行区域，还用于在探 测程序进入多线程并行执行区域后，启动采样模块；

采样模块，用于对多线程程序运行过程中每个线程的访存行为进行采 样，并将采样过程中获取的访存信息保存，本发明优选使用红黑树方式进 行保存；其中，所述访存信息包括发起访存行为的线程ID，访存行为的目 的地址，完成访存行为所耗费的时钟周期数，访存行为的类型。所述采样 模块还用于保存采样过程中为线程访问变量分配的内存大小及分配的内存 地址。

分析模块，一方面用于根据所述采样模块获取的访存信息，定期对所 述多线程程序中各线程的访存延迟不平衡度进行评估，其中，所述访存延 迟不平衡度具体为：

ξ_T＝|D_T-D_avg|/D_avg

其中，ξ_T为线程T的访存延迟不平衡度，D_T为线程T的平均访存延迟， D_avg为所有线程的平均访存延迟。

所述分析模块还用于针对发生不平衡现象的多线程程序进行访存行为 分析，所述访存行为分析具体包括：根据所述采样模块获取的访存信息， 估计每个线程访问变量的线程平均访存延迟，并依次将线程平均访存延迟 最大值的线程访问变量交由判断模块进行处理。

此外，所述分析模块还用于根据所述采样模块获取的访存信息进行访 存规律分析；所述访问规律分析具体为：观察多线程程序中每个线程访问 的线程访问变量中是否没有共同访问的线程访问变量子块。

判断模块，用于根据所述访存延迟不平衡度判断是否发生多线程间访 存延迟不平衡现象，同时，还用于在访存延迟不平衡现象发生时进一步判 断线程访问变量是否仅由一个线程访问、线程访问变量与访问该变量的线 程是否处于同一个节点及线程访问变量大小是否小于第二阈值Size(该值可 取所用系统一次访存读取的数据大小)，此外，所述判断模块，还用于判断 程序多线程并行执行的区域是否结束；

调度模块，用于根据所述分析模块的访存行为分析和访问规律分析， 及判断模块的判断结果对远端访存的线程访问变量进行迁移调度至线程所 在节点或使用交错存放将其平均分配到各节点上。

本发明提出了一种基于上述系统的NUMA架构下平衡多线程间访存延 迟的调度方法，概括来说，所述方法包括采样，分析，以及调度三个部分。

采样是指在多线程程序运行过程中对每个线程的访存行为进行采样， 并将采样过程中获取的访存信息通过有效的组织方式，如使用红黑树方式 保存，从而用于分析模块进行分析；分析所做的主要工作是根据采样获得 的访存信息预测该多线程程序中各线程的访存延迟是否不平衡，以及如果 不平衡，具体是哪个线程因为什么缘故造成了不平衡；调度部分所做的工 作是根据分析的结果进行合理的调度，决定应该针对哪个线程访问变量采 取什么样的措施尽快消除这种访存延迟不平衡现象，从而保证各线程的访 存延迟基本相等。

其中，具体来说，采样过程我们可以借助硬件提供的采样机制进行访 存行为的采样，例如Intel芯片提供的精确事件采样机制(PEBS)以及AMD 芯片提供的指令采样机制(IBS)都可以通过采样的方式，提供多线程运行 过程中的访存信息。包括各种存储访问行为相关的数据以及地址，执行该 行为的线程，线程所在CPU以及节点等信息。在分析过程中，我们可以通 过建立红黑树的方式将采样过程中收集到的信息保存起来，为每一个线程 维护一棵红黑树，其中每个节点以线程访问变量地址作为关键值，每个节 点按时间顺序保存该线程对该线程访问变量的每一次访存信息。这样，我 们就能方便地计算出每个线程的平均访存延迟以及每个线程访问变量的线 程平均访存延迟。在调度部分，我们可以利用操作系统提供的函数来进行 线程访问变量的拷贝和调度。

该调度方法针对的是多线程并行执行的区域，其中的采样、分析、调 度等过程也都只针对程序并行执行的部分。采样过程采集的信息包括发起 访存行为的线程ID，该访存行为的目的地址，完成该访存行为所耗费的时 钟周期数，该访存行为的类型(远端访存/本地访存)等。采样过程采集的 信息还包括变量的内存分配行为。当多线程程序为变量分配内存时，采样 过程将会记录分配的内存大小以及分配的内存地址等信息。

如图2所示，本发明提出的基于上述系统的一种NUMA架构下平衡多 线程间访存延迟的调度方法，包括以下步骤：

(1)检测模块检测程序是否进入多线程并行执行区域，一旦发现程序 处于多线程并行执行区域，立即启动采样模块；

(2)采样模块持续对程序的多线程访存行为进行采样，并将采样获取 的访存信息根据线程ID进行分类并保存(本发明优选使用红黑树方式进行 保存)，根据访存行为的时间顺序为每个线程建立一个访存事件流，并通过 分析模块不断更新计算每个线程的平均访存延迟；其中，所述访存信息包 括发起访存行为的线程ID，访存行为的目的地址，完成访存行为所耗费的 时钟周期数，访存行为的类型。

另外，所述采样模块还保存采样过程中为线程访问数据分配的内存大 小及分配的内存地址；

(3)分析模块定期对各线程的访存延迟不平衡度进行评估，其中，所 述访存延迟不平衡度具体为：

ξ_T＝|D_T-D_avg|/D_avg

其中，ξ_T为线程T的访存延迟不平衡度，D_T为线程T的平均访存延迟， D_avg为所有线程的平均访存延迟；

(4)通过判断模块判断各线程的访存延迟不平衡度是否大于第一阈值 Threshhold(该值可取10％-20％，大部分情况下线程的访存次数都比较多， 所以即使不平衡度在10％-20％之间，最后累积造成各个线程完成并行区域 工作的时间差也是会影响到多线程程序的运行性能的。)；若是，则跳转至 步骤(5)，否则，继续执行步骤(3)；

(5)分析模块对多线程程序进行访存行为分析，根据估计的每个线程 访问变量的线程平均访存延迟，选取线程平均访存延迟最大的线程访问变 量，并将该线程访问变量交由判断模块进行处理；

(6)判断模块判断所述线程访问变量是否仅由一个线程访问，若是， 则跳转至步骤(7)，否则跳转至步骤(8)。

(7)判断模块进一步判断所述线程访问变量与访问该变量的线程是否 处于同一个节点，若是，则返回步骤(5)分析模块依次选取下一个访存延 迟最大的线程访问变量进行访存行为分析，否则，调度模块将该线程访问 变量迁移至访问该变量的线程所在节点；

(8)判断模块进一步判断所述线程访问变量大小是否小于第二阈值 Size(该值可取所用系统一次访存读取的数据大小)，若是，则转入步骤(9)， 否则转入步骤(10)；

(9)将该线程访问变量复制分发到NUMA架构下的各个节点；

(10)分析模块根据所述采样模块获取的访存信息对多线程程序进行 访问规律分析，若所述线程访问变量中没有被多个线程共同访问的线程访 问变量子块，则转入步骤(10-1)，否则转入步骤(10-2)；

(10-1)将各线程访问的线程访问变量子块分别存放到各线程所在的节 点；

(10-2)通过交错存放将所述线程访问变量平均分配到NAMU架构下 的各个节点上，避免访存集中而导致的线程访存延迟不平衡的现象；

(11)判断模块判断程序多线程并行执行的区域是否结束，若否，则 返回步骤(3)继续执行；否则调度结束，进一步观察是否仍有访存延迟不 平衡的现象。

本领域的技术人员容易理解，以上所述仅为本发明的较佳实施例而已， 并不用以限制本发明，凡在本发明的精神和原则之内所作的任何修改、等 同替换和改进等，均应包含在本发明的保护范围之内。