一种异构多核线程调度方法、系统及异构多核处理器

摘要

本发明涉及一种异构多核线程调度方法，包括根据程序的动态特征分别为线程和核生成排序列表，并根据排序列表找出线程和核的最优的稳定匹配，根据该稳定匹配进行线程调度。包括接收运行在该核的线程的特征向量，并据其为该线程给各个核进行选择一个优先级排序；为各个核对各个线程进行排序；接收各个线程和核的排序列表，并找出线程和核的稳定匹配结果；接收该匹配结果，通过操作系统进行调度，将各个线程分配到相应的核上运行。避免了抽样调度带来的巨大开销；将更多影响性能功耗的复杂因素考虑在内，只需要预测的相对关系而非具体值，降低了模型的复杂度的同时也提高了调度的精确性。

说明书

技术领域

本发明涉及一种在单指令集异构多核处理器(Single-ISA heterogeneous  multi-core processors)中线程与核数目相等情况下的线程调度方法 (threads scheduling policy)领域,尤其涉及一种根据线程和核对彼此进行选 择优先级排序后，用Gale-Shapley算法完成线程调度方法的实现。

背景技术

随着集成电路工艺的发展,越来越多的核被集成到同一个片上系统中,片 上多核处理器(chip multi-processors,CMP)逐渐成为一种主流的处理器结 构。片上多核处理器通过在片上集成多个相同的通用核为并行运行在系统中的 程序提供更好的性能表现，但同时也会受到功耗，散热，芯片面积等的限制。 为了更为有效地充分利用片上有限的功耗以及面积，工业界及学术界提出了异 构多核处理器结构。

异构多核处理器有多种构成形式，本发明主要涉及单指令集异构多核处理 器（Single-ISA heterogeneous multi-core processors）。在单指令集异构 多核处理器中，不同类型的核共用同一套指令集。核之间的差异既可以是由频 率、缓存大小、功耗限制（power budget）等参数导致的，也可能是由于基本 结构设计（例如：out-of-order或in-order，指令发射宽度等）的不同引起。 另外，本发明主要针对异构多核处理器中每个核上都各自运行着一个单线程程 序的情况，因此线程数目总是等于系统中的核的数目，并且线程可视为与程序 等价。

不同的程序通常具有不同的程序特征。进一步，即使对于同一个程序，根 据输入集以及执行阶段的变化，其程序特征也会发生显著的变化。

在异构多核处理器中，根据程序特征，将各个线程调度到它们各自最为合 适的核上面运行，这称之为线程调度。线程调度的目的在于用合适的核为线程 提供更好的性能表现，同时尽量避免功耗的浪费，使得片上有限的功耗以及面 积资源都得到更有效地利用。

调度方法有静态和动态之分，其中，静态的调度方法通过离线提取程序与 具体执行环境无关的特征来推测各个线程在不同类型的核上运行的性能表现， 根据预测结果，将各个线程调度到相应的核上运行。静态调度方法只用到了程 序间的差异，忽略了程序自身在不同的执行阶段所具有不同的程序特征，因此 静态调度方法存在天然的缺陷。

基于抽样的动态调度方法的做法将调度分为两个阶段进行：抽样阶段和稳 定执行阶段。当标志着程序动态特征发生了显著变化的触发事件发生后，进入 抽样阶段；在抽样阶段中，将各个线程分别调度到每种类型的核上试运行，因 此需要遍历所有的调度方案，并记录下每种调度方案相应的性能表现；然后挑 选出性能表现最优的调度方案进入较长时期的稳定执行阶段，直到下一个触发 事件的发生。基于抽样的动态调度方法能够充分利用程序的动态特征进行调 度。但是，在抽样阶段会带来大量的线程迁移代价，并且遍历不同的调度方案 时需要让程序在各种非理想的调度方案下试运行，由此导致的性能开销也非常 大；另外抽样开销会随着系统中核的类型增加而迅速增加，使得这类调度方法 的可扩展性很差，无法应用于实际中。

为了避免抽样带来的开销，一类基于启发式的调度方法被提出。这类调度 方法借助一些硬件的监控部件（monitor）来采集程序运行中的一些关键信息， 例如IPC，缓存失效率，阻塞时间等，并根据经验规则用这些动态信息来估算 各个线程在不同类型的核上运行的性能表现，然后使用贪心算法根据收益大小 为线程选择合适的核。

下面对这类调度方法中具有代表性的技术方案进行一些简单的介绍：

在一个由不同频率的核构成的异构多核处理器中，将线程按照上一执行阶 段的IPC由高到低排序，同时将核按频率进行排序，然后将线程与核按照排序 的相对位置进行匹配。类似的做法还可以通过采集线程的缓存失效率（cache  miss rate）等信息来将线程分为计算密集型（compute-intensive）和访存密 集型（memory-intensive）两类，然后将计算密集型的线程调度到大核上（例 如：频率高，缓存面积大，乱序执行等等）运行，访存密集型的线程被调度到 小核上（例如：频率低，缓存面积小，顺序执行等等）运行。这种调度方法的 出发点是将指令级并行度（ILP）较高的计算密集型线程分配到大核上从而取 得更好的性能表现，访存密集型的线程分配到小核上以节约功耗。这类做法的 进一步改进是，将采集到的缓存失效率、阻塞时间（stall time）等信息结合 各个核的结构参数，估算出各个线程在不同核上运行的性能表现，然后用贪心 算法根据性能收益大小将线程调度到各个核上运行。

这类调度方法通常只用到少数重要的程序特征（例如缓存失效率，IPC等） 和核的结构参数（例如频率，缓存大小等）结合一定的领域知识或者经验规则 来对程序的性能进行估算，而实际上，程序的性能与大量复杂因素相关，这导 致预测往往不够准确，从而使得这类调度方法的效果不理想。

另外，现有的调度方法大多依赖于通过一个公式模型考虑有限几个因素来 预测各个线程在不同类型的核上运行的性能表现。但是程序的实际性能与各种 复杂的因素相关，导致这类预测的准确性有限。另一方面，即使存在一个精确 的预测模型，其实现的复杂度通常很高，而且也不一定有助于实现更好的调度。 例如，假设一个线程在两个不同类型的核上运行的实际性能分别为（5,4.8）， 模型A的预测为（4.9,5.1），模型B的预测为（10,1）。显然，模型A的预测 更为准确，但是根据模型B的预测做出的调度方案却更可靠。从这个例子可以 看出，实际上需要不是线程在不同的核上面运行的性能准确值，而是一个相对 关系，即预测线程在各个核上运行的一个性能排序。

另一方面，现有的调度方法大多从线程的角度出发，以线程作为决策主体， 根据单一的优化目标进行贪心调度。

总的来说，之前提出的调度方法都是从程序的视角出发设定一个优化目 标，以程序作为决策主体来挑选适合的核。这种单向选择的调度方法存在的问 题是在调度过程中，核没有根据其自身结构特点以及功耗限制等情况来主动决 定是否接收一个线程的权利。例如，当一个核被某个计算密集型的线程选择后， 意味着对于该线程而言这个核能够为其提供最好的性能；但是从核的角度出 发，如果这个核接收该线程可能导致其功耗超过限制（power budget），则这 种调度方案显然不够理想。

发明内容

为了解决上述技术问题，本发明的目的在于提出一种基于Gale-Shapley 算法的异构多核处理器的线程调度方法及调度系统，针对异构多核处理器中的 线程调度问题，本发明能够根据程序特征的变化进行动态调度，有效避免了基 于抽样的调度方法带来的巨大开销，以及启发式调度方法对性能难以精确预测 导致调度不够理想的缺陷，并且将线程和核都作为决策参与者，在调度的过程 中可以同时兼顾线程和核的需求。

具体地讲，本发明公开了一种异构多核线程调度方法，包括根据程序的动 态特征分别为线程和核生成排序列表，并根据排序列表找出线程和核的最优的 稳定匹配，根据该稳定匹配进行线程调度。

所述的线程和核生成排序列表包括生成排序模型，具体包括如下步骤：

（1）选择一理想数据库；

（2）从该数据库中提取程序抽样片段；

（3）将程序抽样片段分别在各个核的模拟器上运行，并得到相应响应， 把程序抽样片段及其响应分为训练集和测试集两部分；

（4）选择合适的学习算法训练排序模型；

（5）当排序模型的测试误差满足要求时，训练阶段结束。

所述的该程序抽样片段包括特征向量，对于线程，输入一个程序抽样片段 的该特征向量，输出一个对各个核的排序列表；对于核，输入各个线程程序抽 样片段的该特征向量，输出为每个核对各线程的排序列表。

所述的异构多核线程调度方法，具体包括如下步骤：

收集线程运行中的各类动态信息，输出为线程的某个程序抽样片段的特征 向量；

接收运行在该核的线程的特征向量，并据其为该线程给各个核进行选择一 个优先级排序；

为各个核对各个线程进行排序；

接收各个线程和核的排序列表，并找出线程和核的稳定匹配结果；

接收该匹配结果，通过操作系统进行调度，将各个线程分配到相应的核上 运行。

所述的异构多核线程调度方法，该找出线程和核的稳定匹配包括如下步 骤：

（1）线程按照其优先级排序由高到低向核提出匹配请求，如果核没有匹配 对象，则选择接受请求与其形成匹配对；

（2）如果核已经有了匹配对象，则比较新的线程与匹配对象的优先级，如 果新线程的优先级高于之前接受的线程，则选择接受新的线程作为匹配对象， 如果新线程的优先级低于之前接受的线程，则拒绝新的请求；

（3）被拒绝的线程重新选择排序列表上下一个核提出匹配请求，直到所有 的线程和核都已经找到匹配对象。

所述的找出线程和核的稳定匹配包括采用Gale-Shapley算法。

本发明还公开了一种异构多核线程调度系统，其特征在于，包括信息采集 模块、T排序器、C排序器、匹配器、线程调度器，其中：

信息采集模块,用于收集各个线程运行中的各类动态信息,输出为各个线 程的某个程序抽样片段的特征向量；

T排序器，用于接收运行在该核上的线程的特征向量，并据其为该线程给 各个核进行选择优先级排序；

C排序器，用于为各个核对各个线程进行排序；

匹配器，用于接收各个线程和各个核的排序列表，并得到线程和核的稳定 匹配结果；

线程调度器，接收该匹配结果，通过操作系统进行调度，将各个线程分配 到相应的核上运行。

本发明还公开了一种采用上述任何一种异构多核线程调度方法的异构多 核处理器。

本发明还公开了一种包括上述异构多核线程调度系统的异构多核处理器。

本发明的有益效果是：在能够利用程序的动态特征的基础上避免了抽样调 度带来的巨大开销；用一个非线性的学习排序模型替代用经验公式来预测性能 功耗的做法，可以将更多影响性能功耗的复杂因素考虑在内，并且只需要预测 的相对关系而非具体值，降低了模型的复杂度的同时也提高了调度的精确性； 在线程的调度过程中，通过将线程和核都视为博弈过程中的独立决策主体，从 而做到兼顾程序的性能需求与核的功耗限制；利用Gale-Shapley算法找到一 个处于帕累托最优的稳定匹配并据其进行线程调度。

附图说明

图1本发明排序模型离线训练架构

图2本发明四核异构多核处理器的结构实施例

具体实施方式

本发明借鉴博弈论，将线程与核都视为自私的决策参与者，它们都会从各 自的角度出发尽量分别最大化其性能或者功耗收益，客观上使得调度方法能够 兼顾线程和核两方面的优化目标，从而得到一个更优的全局调度决策。

在本发明中，需要得到线程对于各个核的选择优先级排序。并从核的角度 出发，对各个线程进行一个接收的优先级排序。

为了得到上述各优先级排序，需要使用学习排序技术（learn-to-rank  technique）训练出排序模型（ranker）。如图1给出了本发明得到排序模型的 一个具体做法：

应用数据库Application database：一个包含所有程序的无穷大的理想 数据库；

程序抽样片段Sample application phase：从一些范例程序中提取的程 序抽样片段，其具备的程序特征应该能够代表大部分常用程序，并且用一些常 用的程序分析工具如mika可以提取出程序的特征向量；

模拟器Simulator：对于一个异构多核处理器，核的数目以及各个核的类 型已经事先确定，将程序抽样片段分别在各个核的模拟器上运行，并得到相应 响应（each core response），把程序抽样片段及其响应分为训练集和测试集 两部分；

学习算法Learning algorithm：排序模型ranker的训练是一个监督学习 过程，根据情况选择合适的学习算法例如RankBoost等来训练排序模型；

排序模型Ranker model：当排序模型的测试误差已经可以满足要求时， 训练阶段结束。

对于线程而言，T-ranker的输入是一个程序片段的特征向量，输出是对 各个核的一个排序列表，对于T-ranker而言，需要排序的核是固定不变的， 输入变量只是每个程序片段的特征向量，因此只需要训练一个T-ranker即可 在所有核上通用；对于某个核而言，C-ranker的输入是各个线程片段的特征 向量，输出是该核对各线程的一个排序列表，对于C-ranker而言，需要排序 的线程处于变化中，并且各个核具有不同的结构配置特征，即使对于相同的一 组线程其排序结果页不相同，因此需要为每个核单独训练一个C-ranker。

训练完毕后，可将排序模型通过硬件实现，集成在各个核上。或者作为本 发明调度系统的一部分。

在利用排序模型分别为线程和核得到其各自的排序列表之后，根据 Gale-Shapley算法找到稳定匹配，然后根据匹配结果来进行线程调度。从而 达到一个帕累托最优的状态，使得所有的线程和核都处于一个相对满意的状 态，从而客观上实现一个近似全局最优的线程调度。

假设集合A和集合B中各有N个元素，并且每个元素都有一个自己的优先 级排序列表包含另一集合的所有元素，则根据Gale-Shapley算法总可以为这 两个集合找到一个稳定的匹配状态，使得每个元素都能找到在其所能找到的最 佳匹配对象。一个不稳定的匹配意味着在该状态下存在集合A中的元素a与集 合B中的元素b各自在对方的排序列表上都优先于他们现在各自的匹配对象， 因此a和b都更倾向于拒绝它们当前的匹配对象而与对方进行匹配。一个不存 在不稳定因素的匹配即为稳定匹配。对于集合A和B，可能存在多个稳定匹配。 理论证明，根据Gale-Shapley算法找到的匹配总是处于帕累托最优状态，并 且是所有稳定匹配中最好的一种。

为实现本发明而提供的基于Gale-Shapley算法的异构多核处理器的线程 调度方法，以一个4核的异构多核处理器作为例子来进行说明。显然，本发明 也可以扩展到集成了更多核的异构多核处理器中，并且对于核的类型没有限 制。

如图2所示，在一个4核的异构多核处理器中，除了4个核之外，包括以 下部件：每个核上的信息采集模块Monitor，每个核上的T排序器T-ranker， 一个C排序器C-ranker，一个匹配器Matchmaker，一个线程调度器Scheduler。

Monitor：用于收集线程运行中的各类动态信息，包括但不限于缓存失效 率，阻塞时间，整数指令数目，浮点指令数目等，其输出为线程的某个程序段 的特征向量；

T-ranker：接收运行在该核的线程的特征向量，并据其为该线程给各个核 进行选择优先级排序，通常以性能为排序标准；

C-ranker：实际上在C-ranker内部集成了四个排序模型，分别用于为各 个核对四个线程进行排序，排序标准可以设为在满足功耗限制（power budget） 的前提下按照性能功耗比从高到低排序；由于每个单独的ranker都需要接收 来自四个线程的特征向量，因而将其集中在一起可以降低通讯开销，只需要从 四个核的Monitor接收一次信息；

Matchmaker：接收各个线程和核的排序列表，并根据Gale-Shapley算法 找出稳定匹配结果；

Scheduler：接收Matchmaker的匹配结果，通过操作系统进行调度，将各 个线程分配到相应的核上运行。

为了使本发明的目的、技术方案及优点更加清楚透彻，以下结合附图及实 施例，对本发明的基于Gale-Shapley算法的异构多核处理器的线程调度方法 进行进一步详细说明。应当理解，此处所描述的具体实施例仅仅用以解释本发 明，并不用于限定本发明。

本发明实施例基于Gale-Shapley算法的异构多核处理器的线程调度方 法，包括根据程序的动态特征分别为线程和核生成排序列表，并根据排序结果 用Gale-Shapley算法找出一个最优的稳定匹配进行线程调度。本实施例中假 设系统中只有core0，core1，core2，core3四个异构核，其各自具有不同的 结构配置。显然，本发明也可以扩展到包含更多核的异构处理器中，其实现方 式与本例中的四核异构多核处理器没有太大差别，因此不在此加以具体说明， 但是都应该视为包含在本发明范畴内。

下面先以图1所示排序模型训练架构为例具体介绍ranker模型离线训练 的实现过程。

首先，以具有代表性的范例程序例如SPEC2006作为程序库，将其按照一 定规则切分为一系列的程序段，例如将每一千万条指令视为一个程序段；用程 序分析工具例如mika等提取程序段的特征向量，其中可以包含ILP，整数指 令数，浮点指令数，缓存失效率等各类信息；从库中随机挑选一些程序段，分 别在core0，core1，core2，core3四个核的模拟器上进行仿真，并得到相应 的性能信息如IPC等，以及功耗信息如性能功耗比等；将随机挑选的程序段及 其仿真结果随机划分为训练集和测试集两部分，选定学习排序算法例如 RankBoost进行排序模型的训练，排序模型的训练过程是一个监督学习的过 程。

对于T-ranker，其输入为一个程序段的特征向量，输出为同一程序段在 四个核上运行的性能排序，也就是线程对核的选择优先级排序，如前所述， T-ranker只需要训练一个模型即可分别用于四个核；对于某个核的C-ranker， 其输入为在该核运行的四个不同程序段的特征向量，输出为四个的性能功耗比 排序，即核对线程的接受优先级排序，C-ranker需要单独为每个核训练一个 独立的排序模型。当模型在测试集上的测试误差低到可以接受的程度时，模型 的训练阶段结束。

当排序模型训练结束后，将其以硬件的方式在异构多核处理器上实现，用 于线程调度。

下面以图2所示异构多核处理器调度架构为例具体介绍Gale-Shapley算 法的异构多核处理器的线程调度方法的实现。

假设有四个线程T0，T1，T2，T3运行于该异构多核处理器。初始化时， 由于没有线程的先验信息，将其随机调度在四个核上，例如得到如下匹配方式 （T0，core0），（T1，core1），（T2，core2），（T3，core3）。

经过一段时间运行之后，各个Monitor采集到所在核的程序动态特征，将 其分别发送给相应T-ranker以及C-ranker，并得到如下排序结果：

表1 线程对核的排序结果

表2 核对线程的排序结果

在得到以上排序列表后，将排序结果发送到Matchmaker，Matchmaker根 据Gale-Shapley算法找出一个最优的稳定匹配：

首先，T0根据其选择优先级排序向Core2提出请求，Core2此时没有匹配 对象，接受T0的请求，形成一个匹配对（T0，Core2）；

接着，T1根据其选择优先级排序向Core1提出请求，Core1此时没有匹配 对象，接受T1的请求，形成一个匹配对（T1，Core1）；

然后，T2根据其选择优先级排序向Core2提出请求，Core2此时已经与 T0匹配，Core2查看其其接受优先级排序，发现T2的优先级高于T0，于是接 受T2提出的请求，重新形成匹配对（T2，Core2）；

由于Core2重新与T2匹配，因此T0失去匹配对象，其按照降序顺序向 Core1提出请求，TO在Core1的排序列表上优先级高于T1，因此Core1选择 接受，形成新的匹配对（T0，Core1）。

以此类推，线程按照其优先级排序由高到低向核提出匹配请求，如果核没 有匹配对象，则选择接受请求与其形成匹配对；如果核已经有了匹配对象，则 比较新的线程与匹配对象的优先级，如果新线程的优先级高于之前接受的线 程，则选择接受新的线程作为匹配对象，如果新线程的优先级低于之前接受的 线程，则拒绝新的请求；被拒绝的线程重新选择排序列表上下一个核提出匹配 请求；直到所有的线程和核都已经找到匹配对象，根据Gale-Shapley算法进 行的匹配过程结束。理论证明，该匹配一定处于稳定状态，且是所有稳定匹配 中最优的一种。并且毫无疑问，根据上述过程得到的匹配是帕累托最优的，因 为没有线程（或核）可以在不损害其它线程（或核）收益的前提下改善自身收 益。

最终得到的稳定匹配为：（T0，Core1），（T1，Core3），（T2，Core2），（T3， Core0）。Scheduler根据匹配结果将线程分别调度至对应核上运行。Monitor 继续采集新的程序特征，为下一次调度做准备。

以上只是本发明的实施例，还有很多情况同理可推，不一一列举，特别是 本发明只是用到排序算法RankBoost得到排序结果，并结合Gale-Shapley算 法得到稳定匹配用于线程调度，还可以用其他的排序算法结合Gale-Shapley 算法，达到同样的匹配结果，例如AdaRank，Rank SVM等。

显然，本领域的技术人员可以对本发明进行各种改动和变型而不脱离本发 明的精神和范围。这些修改和变型属于本发明的保护范围之内。