非统一内存访问系统中线程化串行程序的方法及装置

摘要

本发明实施例公开了一种非统一内存访问系统中线程化串行程序的方法及装置，涉及多线程技术领域，能够缓减在非统一内存访问系统中由于访存延时差异所导致的多核处理器执行串行程序时的性能的降低。本发明的方法包括：接收待处理的串行程序；获取多核处理器的信息，其中包括多核处理器的互联结构信息、每个所述处理器核的访存延时中的至少一项；将所述串行程序中的可用循环部分线程化为推测线程，将所述串行程序中的串行部分和非可用循环部分线程化为控制线程；根据所述互联结构信息和所述延时信息中的至少一项，将所述控制线程和所述推测线程分配至处理器核。本发明用于支持推测多线程机制的非统一内存访问系统中线程化执行串行程序。

说明书

技术领域

本发明涉及多线程技术领域，尤其涉及一种非统一内存访问系统中线程化 串行程序的方法及装置。

背景技术

随着多核芯片(Chip Multi-Processor，CMP)技术的发展，多核处理器得到 广泛应用。现有的多核处理器主要有UMA(Uniform Memory Access，统一内 存访问)和NUMA(Non-Uniform Memory Access，非统一内存访问)这两种 结构形式。

在UMA中，设备中有多个CPU(Central Processing Unit，中央处理器/处理 器)对称工作，共享相同的物理内存，除CPU以外的所有资源都是共享的，每 个CPU访问内存中的任何地址所需时间相同的；在NUMA中具有多个CPU模块， 每个CPU模块由多个CPU核组成并且具有独立的本地内存、输入输出接口等。不 同CPU模块可以进行连接和信息交互，故每个CPU模块可以访问其他CPU模块的 内存。

在使用多核处理器处理传统的串行程序时，需要将串行程序线程化，从而 加速串行程序在多核处理器上的执行速度，并使多核处理器的获取资源得到更 充分的利用。推测多线程技术(Speculative Multithreading，SMT)就是线程化 串行程序的一种方案。

推测多线程技术的基本思路是：将串行程序的串行部分和循环部分(循环 部分包含串行程序中的多个循环体)划分为新的线程，并将这些线程分配至多 个CPU(Central Processing Unit，中央处理器)核上执行。

在NUMA中实行推测多线程技术的方法与在UMA中实行推测多线程技术的 方法基本相同。即将串行程序线程化为多线程程序，并将不同的线程随机分配 至CPU核上执行；CPU核在执行线程的过程中，需要不断访问内存以支持CPU 核的获取功能，具体的，就是CPU核在执行线程的过程中根据线程的具体执行 代码，访问本地内存，或是通过NUMA中CPU模块之间的互联网络访问其他CPU 模块中的内存，从而完成线程的执行过程。

在将上述方案应用在NUMA中时，CPU核在访问内存时存在访存延时，访 存延时会影响推测多线程机制的执行效果，从而降低多核处理器的性能。

发明内容

本发明的实施例提供一种非统一内存访问系统中线程化串行程序的方法及 装置，能够缓减在非统一内存访问系统中由于访存延时所导致的多核处理器性 能的降低。

本发明的实施例采用如下技术方案：

一方面，本发明的实施例提供一种非统一内存访问系统中线程化串行程序 的方法，包括：

接收待处理的串行程序；

获取多核处理器的信息，所述多核处理器的信息包括所述多核处理器的互 联结构信息、所有处理器核的延时信息中的至少一项，所述延时信息包含每个 所述处理器核的访存延时；

将所述串行程序中的循环部分线程化为推测线程，将所述串行程序中的串 行部分线程化为控制线程；

根据所述互联结构信息和所述延时信息中的至少一项，将所述控制线程和 所述推测线程分配至处理器核。

另一方面，本发明的实施例提供一种非统一内存访问系统中线程化串行程 序的装置，包括：

接收模块，用于接收待处理的串行程序；

提取模块，获取多核处理器的信息，所述多核处理器的信息包括所述多核 处理器的互联结构信息、所有处理器核的延时信息中的至少一项，所述延时信 息包含每个所述处理器核的访存延时；

线程化模块，用于将所述串行程序中的循环部分线程化为推测线程，将所 述串行程序中的串行部分线程化为控制线程；

分配模块，用于根据所述互联结构信息和所述延时信息中的至少一项，将 所述控制线程和所述推测线程分配至处理器核。

本发明实施例提供的方法和装置，能够在非统一内存访问系统中，根据CPU 核访问内存时的延迟信息、各多核处理器的互联结构信息和各CPU核的状态信息 等对串行程序进行线程划分，并根据这些信息，通过相应的调度计划，将推测 线程调度至CPU核上执行。与现有技术相比，本发明实施例能够对串行程序进行 合理的线程划分，并将这些线程以最佳策略分配至CPU核上执行，从而缓减在非 统一内存访问系统中由于访存延时所导致的多核处理器性能的降低。

附图说明

为了更清楚地说明本发明实施例中的技术方案，下面将对实施例描述中所 需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本发明 的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下， 还可以根据这些附图获得其它的附图；

图1为本发明实施例1提供的非统一内存访问系统中线程化串行程序的方法 的流程图；

图2为本发明实施例2提供的非统一内存访问系统中线程化串行程序的方法 的流程图；

图3为本发明实施例1、实施例2提供的非统一内存访问系统中线程化串行程 序的方法中的具体实例的流程图；

图4为本发明实施例2提供的非统一内存访问系统中线程化串行程序的方法 中的具体实例的结构图；

图5为本发明实施例3提供的非统一内存访问系统中线程化串行程序的装置 的结构示意图；

图6为本发明实施例4提供的非统一内存访问系统中线程化串行程序的装置 的结构示意图。

具体实施方式

下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清 楚、完整地描述，显然，所描述的实施例仅仅是本发明一部分实施例，而不是 全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造 性劳动前提下所获得的所有其它实施例，都属于本发明保护的范围。

为使本发明技术方案的优点更加清楚，下面结合附图和实施例对本发明作 详细说明。

实施例1

本发明实施例提供一种非统一内存访问系统中线程化串行程序的方法，如 图1所示，该方法包括：

步骤101，接收待处理的串行程序。

具体的，在本实施例中，在NUMA系统中，计算机通过操作系统中的程序剖 析工具接受待处理的串行程序，并对该串行程序的代码进行前段编译及优化， 将串行程序的程序代码转化为中间代码，为进一步的代码剖析做准备，例如：

如图3所示，计算机通过程序剖析工具中的SUIF前端编译工具对串行程序 的代码进行编译，得到中间代码，并通过SUIF优化器对该中间代码进行优化， 得到优化的中间代码。

步骤102，获取多核处理器的信息。

其中，所述多核处理器的信息包括所述多核处理器的互联结构信息、所有 处理器核的延时信息中的至少一项，所述延时信息包含所述所有处理器核的访 存延时。

具体的，在本实施例中，在NUMA系统中，计算机可以建立两个数据结构：NUMA 基本信息表和可用节点状态信息表。收集NUMA系统的互联结构信息(可以包括 NUMA系统互联拓扑互联结构信息等)和延时信息(可以各核访问不同内存段的 平均延时等)，并保存在NUMA基本信息表中。同时，通过查询系统状态和运行 测试程序，获取计算机中多核处理器的使用情况，

进一步的，将该多核处理器中所有CPU核的状态信息(可以包括CPU核使 用率、CPU核之间的访存冲突的情况等)保存在可用节点状态信息表中，例如：

如图3所示，计算机通过操作系统中的信息收集工具收集诸如互联结构信 息、延时信息、状态信息等NUMA系统信息，并将这些信息作为NUMA启发信息发 送至线程生成器，从而使线程生成器能够根据互联结构信息、延时信息、状态信 息等NUMA系统信息以更加合理的策略将串行程序线程化。

步骤103，将所述串行程序中的可用循环部分线程化为推测线程，将所述串 行程序中的串行部分和非可用循环部分线程化为控制线程。

具体的，在本实施例中，将所述串行程序中的循环部分线程化为推测线程 的过程可以是：计算机通过剖析工具对串行程序的中间代码进行剖析，收集循 环部分的信息；对于循环部分中可被线程化的循环体，进行依赖分析，得到各 个循环体之间的依赖信息；线程生成器根据循环部分的信息和循环体之间的数 据传输信息，根据互联结构信息、延时信息、状态信息等NUMA系统信息所衍生的 线程化的规则，通过SUIF后端编译工具将中间代码编译为线程化可执行代码， 例如：

如图3所示，计算机通过剖析工具(GNU Prof)对优化的中间代码进行动态 剖析，收集包括循环体起点-终点位置，循环次数，循环体大小等信息；并对于 潜在的派生循环体，进行深入的依赖分析，包括数据依赖分析和控制依赖分析， 并获得循环间依赖信息。线程生成器利用剖析信息和循环间依赖信息，根据从 NUMA启发信息衍生得到启发式规则，确定适合派生为推测多线程的区域和派生 线程数目，并在派生区域首尾加入多线程代码和控制信息，并对循环判定条件 和推测线程的部分初始化数据进行预测赋值。最后，使用SUIF后端编译工具将 线程生成器生成的代码编译为线程化可执行代码。

步骤104，根据所述互联结构信息和所述延时信息中的至少一项，将所述控 制线程和所述推测线程分配至处理器核。

具体的，在本实施例中，计算机将串行程序经过线程化所得到的各个线程 的执行代码，根据互联结构信息和/或延时信息所衍生的分配规则，以更加合理 的策略分配至CPU核中。

本发明实施例提供的方法，能够在非统一内存访问系统中，根据CPU核的访 问内存时的延迟信息、各多核处理器的互联结构信息和各CPU核的状态信息等对 串行程序进行线程划分，并根据这些信息，通过相应的调度计划，将推测线程 调度至CPU核上执行。与现有技术相比，本发明实施例能够对串行程序进行合理 的线程划分，并将这些线程以最佳策略分配至CPU核上执行，从而缓减在非统一 内存访问系统中由于访存延时所导致的多核处理器性能的降低。

实施例2

本发明实施例提供一种非统一内存访问系统中线程化串行程序的方法，如 图2所示，该方法包括：

步骤201，接收待处理的串行程序。

步骤202，获取多核处理器的信息，所述多核处理器的信息包括所述多核处 理器的互联结构信息、所有处理器核的延时信息中的至少一项。

其中，所述延时信息包含所述所有处理器核的访存延时。

步骤203，确定所述循环部分中的循环体，获取每一个循环体在每两次循环 之间的数据传输量。

步骤204，判断所述数据传输量是否小于预设值。

其中，若所述数据传输量小于预设值，则所述循环体为串行程序中的可用 循环体；若所述数据传输量不小于预设值，则所述循环体为不可用循环体。

关于预设值的设定可以由本领域技术人员根据实际需要进行，在此不再赘 述。

进一步的，计算机可以根据线程提交时的时延自动反馈调节预设值。

步骤205，根据所述使用率获取可用处理器核的数量。

其中，所述多核处理器的信息还包括所有处理器核的状态信息，所述状态 信息包含所有处理器的使用率。

具体的，在本实施例中，计算机可以从可用节点状态信息表里获取状态信 息，该状态信息中包含的可用CPU核数目。

步骤206，获取所述串行程序中所有可用循环体所包含的循环次数。

具体的，在本实施例中，计算机可以通过剖析工具对中间代码进行剖析， 并根据剖析所得到的信息获取循环体循环次数。

步骤207，取所述可用处理器核的数量和所述循环次数的最小值作为推测线 程的数目。

具体的，在本实施例中，计算机取所述可用处理器核的数量和所述循环次 数的最小值作为推测线程的数目，例如：

node表示可用CPU核的数目，loop表示计算机在通过剖析工具对中间代码进 行剖析所得到的循环体循环次数，从而推测线程数目等于node和loop中的较小 值，即推测线程数目＝Min{node，loop}，例如：可用CPU核数目node＝2，循环 体循环次数loop＝3，则推测线程数目为2。

步骤208，依次获取所述串行程序中的可用循环体，并将获取到的可用循环 体依次生成为推测线程。

具体的，在本实施例中，计算机可以通过线程生成器将可用循环体逐个依 次生成为推测线程中。

步骤209，获取当前推测线程的执行时间，判断所述执行时间是否不小于阈 值。

其中，所述阈值根据所有处理器核的访存延时的平均值获得。

其中，若所述执行时间小于所述阈值，则重复步骤208，获取下一个可用循 环体并将其加入至当前的推测线程中，直至当前推测线程的执行时间不小于所 述阈值。

具体的，在本实施例中，计算机可以通过线程生成器将一个可用循环体加 入到推测线程中，并检测该推测线程执行时间是否大于等于所有处理器核的访 存延时的平均值。如果这个条件不满足，则可以选取另一个可用循环体并加入 到该推测线程中，并再次检测该推测线程执行时间是否大于等于所有处理器核 的访存延时的平均值，直至推测线程执行时间大于等于所有处理器核的访存延 时的平均值为止。从而，使该推测线程中包含了足够数量的循环体，以便该推 测线程在CPU核上执行时，能够更多地利用CPU核的计算功能。

步骤210，将所有不可用循环体加入到控制线程中。

具体的，在本实施例中，计算机将经过步骤204所得到的不可用循环体加入 到控制线程中，从而使包含了可用循环体的推测线程在CPU核上执行时，能够更 多地利用CPU核的计算功能。

步骤211，根据所述延时信息，将所述控制线程分配至所述可用处理器核中 延时时间最小的处理器核。

具体的，在本实施例中，计算机可以从可用节点状态信息表中所包含的延 时信息中，锁定平均时延最小的CPU核，并将控制线程分配至该CPU核上。

步骤212，根据所述互联结构信息确定与控制线程所在的处理器核位于同一 个处理器模块的处理器核。

具体的，在本实施例中，如图4所示，为一个16核NUMA结构的多核处理器。 其中，该多核处理器由4个CPU模块组成，并且每个CPU模块都包含独立的4个CPU 核、本地内存、I/O槽口等元件，同时这4个CPU模块共享一个高速缓冲存储器。 由于各个CPU模块之间可以通过互联网络进行连接和信息交互，因此每个CPU核 可以访问其他CPU模块的本地内存。但是，CPU核访问本地内存的速度将远高于 访问系统内其它节点的本地内存的速度，并且访问其他CPU模块的本地内存的 CPU核会产生较大的延时。

计算机可以根据互联结构信息确定与控制线程所在的CPU核位于同一个处 理器模块的CPU核，例如：控制线程所在的CPU核为CPU模块1中的C1，计算机根 据互联结构信息获知同样是CPU模块1中的C2、C3、C4为与控制线程所在的处理 器核位于同一个处理器模块的处理器核。

步骤213，将推测线程优先分配至与控制线程所在的处理器核位于同一个处 理器模块的处理器核。

步骤214，在没有被分配的推测线程中，获得相互间具有数据依赖关系的推 测线程及具有数据依赖的推测线程的数据传输量。

具体的，在本实施例中，如图3所示，由于串行程序的源代码是前后连续的， 所以在一个推测线程的执行过程中，会需要另一个推测线程的数据、程序代码 或执行结果等，即推测线程中之间会存在数据依赖，计算机可以通过剖析工具 对中间代码进行动态剖析，从而确定相互之间具有数据依赖的推测线程，并获 取具有数据依赖的推测线程的数据传输量。

步骤215，将有具有数据依赖的推测线程中的数据传输量大的推测线程优先 分配至位于同一个处理器模块中的处理器核。

具体的，在本实施例中，计算机将相互之间具有数据依赖的推测线程分配 至位于同一个处理器模块中的处理器核，例如：

如图3所示，计算机可以通过剖析工具对中间代码进行动态剖析，并得知推 测线程A和推测线程B之间、推测线程C和推测线程D之间、推测线程E和推测线程 F之间存在数据依赖并获得了推测线程A和推测线程B之间的数据传输量1、推测 线程C和推测线程D之间的数据传输量2、推测线程E和推测线程F之间的数据传输 量3，并且数据传输量1大于数据传输量2，数据传输量2大于数据传输量3。

如图4所示，由于数据传输量1大于数据传输量2，数据传输量2大于数据传 输量3，则计算机优先将推测线程A和推测线程B分别分配至CPU模块2中的C1和C2 上；之后计算机采用相同方法，由于数据传输量2大于数据传输量3，则计算机 优先将推测线程C和推测线程D分别分配至CPU模块2中的C3和C4上；对于推测线 程E和推测线程F，若还有可以同时容纳推测线程E和推测线程F这两个推测线程 的CPU模块，则将推测线程E和推测线程F分配至该CPU模块中，若已没有可以同 时容纳两个推测线程的CPU模块，则将推测线程E和推测线程F归入其余没有被分 配的推测线程，并采用步骤216的方法处理其余没有被分配的推测线程。

在线程的执行过程中，C1执行推测线程A，并将执行过程中推测线程A的信 息储存至本地内存2中，同时，C2执行推测线程B的过程中需要读取推测线程A的 信息，则C2能够直接从本地内存2读取C1储存在本地内存2中的推测线程A的信 息，从而避免了CPU核在访问其他CPU模块的本地内存时所产生的延时，从而缓 减了因延时导致的CPU执行多线程程序时的性能降低。

步骤216，将其余没有被分配的推测线程优先分配至延时时间与控制线程所 在处理器核的延时时间的差值小的处理器核。

具体的，在本实施例中，计算机将控制线程所在处理器核的延时时间与剩 余的可用CPU核的访存时延时间之间的差值由小到大排序，并将没有被分配的推 测线程优先分配至差值小的处理器核上，从而保证了在每次分配CPU核的过程 中，使用的都是与控制线程所在处理器核的延时时间的差值最小的那一部分CPU 核，从而缓减了因延时导致的CPU执行多线程程序时的性能降低。

本发明实施例提供的方法，能够在非统一内存访问系统中，根据CPU核的访 问内存时的延迟信息、各多核处理器的互联结构信息和各CPU核的状态信息等对 串行程序进行线程划分，并根据这些信息，通过相应的调度计划，将推测线程 调度至CPU核上执行。与现有技术相比，本发明实施例能够对串行程序进行合理 的线程划分，并将这些线程以最佳策略分配至CPU核上执行，从而缓减在非统一 内存访问系统中由于访存延时所导致的多核处理器性能的降低。

实施例3

本发明实施例提供一种非统一内存访问系统中线程化串行程序的装置，如图3 所示，该装置包括：接收模块501、提取模块502、线程化模块503、分配模块 504。

接收模块501，用于接收待处理的串行程序。

提取模块502，用于获取多核处理器的信息，所述多核处理器的信息包括所 述多核处理器的互联结构信息、所有处理器核的延时信息中的至少一项。

其中，所述延时信息包含所述所有处理器核的访存延时。

线程化模块503，用于将所述串行程序中的循环部分线程化为推测线程，将 所述串行程序中的串行部分线程化为控制线程。

分配模块504，用于根据所述互联结构信息和所述延时信息中的至少一项， 将所述控制线程和所述推测线程分配至处理器核。

本发明实施例提供的装置，能够在非统一内存访问系统中，通过接收模块 接受待处理的串行程序，并通过提取模块获取CPU核的访问内存时的延迟信息、 各多核处理器的互联结构信息和各CPU核的状态信息等信息，再通过线程化模块 根据这些信息对串行程序进行线程划分，并根据这些信息，使用分配模块，通 过相应的调度计划，将推测线程调度至CPU核上执行。与现有技术相比，本发明 实施例能够对串行程序进行合理的线程划分，并将这些线程以最佳策略分配至 CPU核上执行，从而缓减在非统一内存访问系统中由于访存延时所导致的多核处 理器性能的降低。

实施例4

本发明实施例提供一种非统一内存访问系统中线程化串行程序的装置，如图3 所示，该装置50包括：接收模块501、提取模块502、线程化模块503、分配模 块504，其中，线程化模块503包括：第一提取单元5031、第一检测单元5032、 第二提取单元5033、第三提取单元5034、比较单元5035、第一添加单元5036、 第二检测单元5037、第二添加单元5038；分配模块504包括：第一分配单元5041、 定位单元5042、第二分配单元5043、筛选单元5044、第三分配单元5045、第四 分配单元5046。

接收模块501，用于接收待处理的串行程序。

提取模块502，用于获取多核处理器的互联结构信息、所有处理器核的延时 信息和所有处理器核的状态信息中的至少一项。

其中，所述延时信息包含所述所有处理器核的访存延时。

线程化模块503，用于将所述串行程序中的可用循环部分线程化为推测线 程，将所述串行程序中的串行部分和非可用循环部分线程化为控制线程。

其中所述线程化模块503包括：

第一提取单元5031，用于确定所述循环部分中的循环体，获取每一个循环 体在每两次循环之间的数据传输量。

第一检测单元5032，用于判断所述数据传输量是否小于预设值。

其中，若所述数据传输量小于预设值，则所述循环体为串行程序中的可用 循环体；若所述数据传输量不小于预设值，则所述循环体为不可用循环体。

第二提取单元5033，用于根据所述使用率获取可用处理器核的数量。

其中，所述多核处理器的信息还包括所有处理器核的状态信息，所述状态 信息包含所有处理器的使用率。

第三提取单元5034，用于获取所述串行程序中所有可用循环体所包含的循 环次数。

比较单元5035，用于取所述可用处理器核的数量和所述循环次数的最小值 作为推测线程的数目。

第一添加单元5036，用于依次获取所述串行程序中的可用循环体，并将获 取到的可用循环体依次生成为推测线程，获取下一个可用循环体并加入到当前 推测线程中，直至当前推测线程的执行时间不小于所述阈值。

第二检测单元5037，用于获取当前推测线程的执行时间，判断所述执行时 间是否不小于阈值，所述阈值根据所有处理器核的访存延时的平均值获得。

若小于，则通过所述第一添加单元5036获取下一个可用循环体并加入到当 前推测线程中，直至当前推测线程的执行时间不小于所述所有处理器核的访存 延时的平均值。

第二添加单元5038，用于将所有不可用循环体加入到控制线程中。

分配模块504，用于根据所述互联结构信息和所述延时信息中的至少一项， 将所述控制线程和所述推测线程分配至处理器核。

其中所述分配模块504包括：

第一分配单元5041，用于根据所述延时信息，将所述控制线程分配至所述 可用处理器核中相互访存平均延时时间最小的处理器核。

定位单元5042，用于根据所述互联结构信息确定与控制线程所在的处理器 核位于同一个处理器模块的处理器核。

第二分配单元5043，用于将推测线程优先分配至与控制线程所在的处理器 核位于同一个处理器模块的处理器核。

筛选单元5044，用于在没有被分配的推测线程中，获取具有数据依赖的推 测线程，并获取所述具有数据依赖的推测线程的数据传输量。

第三分配单元5045，用于将有具有数据依赖的推测线程中的数据传输量大 的推测线程优先分配至位于同一个处理器模块中的处理器核。

第四分配单元5046，用于将其余没有被分配的推测线程优先分配至延时时 间与控制线程所在处理器核的延时时间的差值小的处理器核。

本发明实施例提供的装置，能够在非统一内存访问系统中，通过接收模块 接受待处理的串行程序，并通过提取模块获取CPU核的访问内存时的延迟信息、 各多核处理器的互联结构信息和各CPU核的状态信息等信息，再通过线程化模块 根据这些信息对串行程序进行线程划分，并根据这些信息，使用分配模块，通 过相应的调度计划，将推测线程调度至CPU核上执行。与现有技术相比，本发明 实施例能够对串行程序进行合理的线程划分，并将这些线程以最佳策略分配至 CPU核上执行，从而缓减在非统一内存访问系统中由于访存延时所导致的多核处 理器性能的降低。

本领域普通技术人员可以理解实现上述实施例装置中的全部或部分流程， 是可以通过获取机程序来指令相关的硬件来完成，所述的程序可存储于一获取 机可读取存储介质中，该程序在执行时，可包括如上述各装置的实施例的流程。 其中，所述的存储介质可为磁碟、光盘、只读存储记忆体(Read-Only Memory， ROM)或随机存储记忆体(Random Access Memory，RAM)等。

以上所述，仅为本发明的具体实施方式，但本发明的保护范围并不局限于 此，任何熟悉本技术领域的技术人员在本发明揭露的技术范围内，可轻易想到 的变化或替换，都应涵盖在本发明的保护范围之内。因此，本发明的保护范围 应该以权利要求的保护范围为准。