一种禁忌搜索调度算法的异构多核处理器

摘要

本发明公开一种禁忌搜索调度算法的异构多核处理器，有至少八个核心的异构多核处理器，用于线程调度、资源协同管理和性能统计的上层框架，用于记录两个线程在两个处理器上的最佳调度方案的禁忌表，用于提高异构多核处理器系统性能和节能的禁忌搜索调度算法。本发明由于提出一种禁忌搜索调度算法的异构多核处理器，它有效的减少了线程迁移次数和采样次数。弥补了以前的设计中只考虑时间和能量有效率的问题，有效的提高了处理器芯片的全局性性能和降低了能耗。

说明书

技术领域

本发明涉及处理器芯片领域，更具体的说，涉及一种禁忌搜索调度算法的异构多核处理器。

背景技术

随着半导体产业的不断发展，晶圆上放置的晶体管数量不断提升，多处理器体系结构逐渐成为主流的芯片结构。比起设计和制造更高频率、更复杂的单处理器，工业界倾向于将多个处理器核集成到同一块芯片上，以获得性能的提升。片上多处理器芯片(ChipMultiprocessor，CMP)目前已经在高性能计算、桌面系统、嵌入式系统中得到了广泛应用。

功耗问题是众核芯片目前及未来主要的设计约束和性能制约因素之一。如果众核芯片中单个处理器内核的功率水平是可以控制的，那么对规模日益扩大的芯片进行全局功耗的管理就成为了摆在设计者面前的一个重要课题。众核芯片的全局功耗管理机制应该能够在运行时针对应用程序的特性进行快速地响应，并在不影响芯片性能的前提下动态的对片上的各个处理器内核进行频率的设置(如使用DVFS技术等可以对单个处理器的实际运行频率和电压进行调整)。针对传统的单处理器上应用负载的特性和“程序阶段”行为进行自适应的功耗管理已经进行了比较深入的研究，取得了不错的研究成果。但众核芯片的功耗管理中还面临着算法运行时代价大、可扩展性不好的困境。目前，针对大规模众核芯片的全局功耗管理机制和算法的研究已是新兴的研究。

另一个关注的问题——“不可预见动态异构性”，它不是设计时异构芯片的“静态异构性”，也不是芯片能够将一个或者多核基本内核合并为逻辑处理器的“动态异构性”，而是由于处理器硬件错误而导致的“不可预见动态异构性”。处理器的硬件错误可以分为两种：暂时性错误和永久性错误，也称为软错误和硬错误。软错误是指构成地球低强度背景辐射的核粒子引起的芯片内部电荷贮存状态的改变。软错误不会对芯片产生有形损坏，它的主要危害是产生错误数据并造成设备的临时故障。硬错误是指由于制造缺陷或者使用磨损导致的永久性硬件损坏。如今新型的芯片已经采用错误纠正码等手段来尝试解决软错误，但对硬错误的处理仍然不尽人意。

随着半导体产业的发展，微型芯片变得越来越小，制造过程中的误差和可变性更为频繁发生。制程可变性(ProcessVariation)这不仅使得晶体管和电路的出厂不合格率增长，而且使芯片在离开生产线时就带有各种随机的硬错误，并有可能使它们在承受性能、能耗和温度的变化等方面变得更加脆弱；芯片部件变得更加容易损耗，并且可能会导致芯片在使用时产生硬错误。这些硬错误导致芯片上各个处理器内核在功效、最大工作频率等关键参数上不同于预先的设计。比如一些元件损坏无法使用、某些关键路径上的晶体管速度变慢，处理器为了能够继续工作，不得不进行降级。芯片厂商由于成本的原因，不会只出售完全没有瑕疵的芯片，未来的CMP将被设计为能够在降级状态下正常工作。这些硬错误将在生产和使用过程中随机地发生，每个内核都将受到降级的影响，这就是“不可预见动态异构性”产生的原因。因此，CMP将会变成一个不可预见异构多核系统(即使它当初被设计为同构的)，我们称这种处理器为不可预见动态异构片上多核处理器(UDHCMP，UnpredictablyDynamicHeterogeneousChipMultiprocess)。

如果调度器忽视内核发生的不可预见异构性变化，将会导致较大的性能损失；如果全局功耗管理器忽视这种变化，将会造成不可接受的能量浪费。因此，不可预见动态异构多核处理器调度算法的研究对于众核芯片全局性能与能效管理具有非常重大的意义。

发明内容

本发明所要解决的技术问题是提供一种解决不可预见因素导致的动态异构多核处理器上的任务调度问题的一种禁忌搜索调度算法的异构多核处理器。

本发明的目的是通过以下技术方案来实现的：

一异构多核处理器有若干个核，每个内核拥有独立的二级缓存。每个内核上只运行一个单线程程序，且每个内核之间不存在通信；

一上层框架的主要功能有线程调度、资源协同管理和性能统计；

一禁忌表记录两个线程在两个处理器上的最佳调度方案；

一禁忌搜索调度算法，流程如下：

(1)随机生成初始指派方案，按照指派方案将线程分配到内核上；

(2)随机生成所述线程数量的一半的交换对；

(3)检查禁忌表，移除已被禁忌的交换对；

(4)交换所有交换对中的线程，并对所有迁移后的线程进行采样；

(5)若交换对交换后大于交换前的，则标记这个交换对，并且将它加入禁忌表；否则将交换对取反后加入禁忌表；

(6)若所有迁移过的线程迁移后之和大于迁移前之和，将第(4)步中被标记的交换对中的线程还原到原有内核上；

(7)根据当前线程所在内核生成指派方案，稳定阶段将按照该指派方案进行调度；

(8)如果还有剩余功耗管理时间片，回到(2)；否则结束；

本发明有效的减少了线程迁移次数和采样次数。弥补了以前的设计中只考虑时间和能量有效率的问题，有效的提高了处理器芯片的全局性性能和降低了能耗。

附图说明

图1是本发明实施例的异构多核处理器系统结构示意图；

图2是本发明实施例禁忌表操作流程图；

图3是本发明实施例判断交换对中线程是否进行交换采样示例图。

具体实施方式

下面结合附图和较佳的实施例对本发明作进一步说明。

异构多核处理器系统使用多个单核和一个上层框架来实现，框架结构如图1所示。框架底层是众多单核。在探索周期时，框架对每个线程进行采样，单核采集其上运行的线程的性能与能耗参数，然后将这些参数传递给上层框架。上层框架的主要功能有线程调度、资源协同管理和性能统计。上层框架负责在每个功耗管理时间片的探索周期中为每个线程指定指派方案，它会收集和分析每个内核的采样数据，再使用调度算法来生成最合适的指派方案。这种使用多个单核来构建多核模拟器方案的优点是能够精确的感知每个内核的状态，为动态调度算法提供了可靠的数据支持。另外该框架具有很好的可扩展性，为该系统的可扩展性分析提供了条件。

禁忌搜索(TabuSearch，TS)是一种全局逐步寻优算法，它是局部搜索算法的扩展，是一种对人思维的模拟。它从一个初始解出发，选择合适的方向进行探索，选择让的目标函数值变化最大的候选解。为了避免陷入局部最优解，TS搜索中利用禁忌表，对已经进行的优化过程进行记录和选择，指导下一步的搜索方向。

禁忌搜索最重要的思想是标记对应已搜索的局部最优解的一些对象，并在进一步的迭代搜索中尽量避开这些对象(而不是绝对禁止循环)，从而保证对不同的有效搜索途径的探索，TS的禁忌策略尽量避免迂回搜索，它是一种确定性的局部极小突跳策略。

禁忌搜索的基本步骤如下：首先给定一个当前解(初始值)和一个邻域，然后从众多的初始解之中选取一定数量的候选解；若存在候选解所优于当前最优解，那么无论这个解是否被禁忌，都将它设定为当前最优解及历史最优解，并将这个解加入到禁忌表(用于记录候选解禁忌属性的表)中，同时对禁忌表内所有禁忌对象的有效期进行修改；若不满足以上条件，则从候选解中选择未被禁忌的最佳解作为当前接，无论它是否比当前解要好，同时将它加入禁忌表中，并修改禁忌表中各对象任期；如此重复上述搜索过程直至满足停止准则。

基于禁忌搜索的不可预见异构调度算法(TSU，TabuSearch-basedUnpredictedSchedulingAlgorithm)，算法运行在多个功耗管理时间片中，每个功耗管理时间片又分为探索阶段和稳定阶段。为了减少的线程迁移与采样的次数，TSU调度算法使用禁忌表记录两个线程在两个处理器上的最佳调度方案。为了记录线程的这种“偏好”，算法中以两个线程及线程所在的内核组成的四元组为禁忌对象，将这个四元组称为交换对。以下对交换对及其部分属性进行了定义：

交换对：由两个内核及两个线程组成的四元组表示，如A、B线程目前分别在X、Y内核上运行，可以表示为或者。

交换对之间的关系：相等、相反、无关。当四元组中的两个内核、两个线程以及线程所在的内核都相同时，两个交换对相等，例如和相等，也和相等。当两个内核、两个线程相同，而线程所在的内核不同时，两个交换对相反，如和相反，也和相反。当两个交换对之间既不是相等关系又不是相反关系时，称为交换对无关。这三种关系具有对称性、自反性、传递性。

交换对取反：将交换对中线程所在的内核互换。

基于禁忌搜索的不可预见异构调度算法的关键是禁忌表操作，流程图如图2所示。基于禁忌搜索的不可预见异构调度算法的禁忌表中存放的都是线程交换后大于交换前的交换对。每次线程交换之前，检查该交换对是否在禁忌表中。如果该交换对不在禁忌表中，则可以进行线程交换。如果该交换对在禁忌表中，表示当前两个线程所在的处理器符合线程的偏好，不需要进行交换。每次对交换对进行采样后都要判断，若交换对线程交换前的大于交换后则直接将交换对加入禁忌表；否则将交换对取反后加入禁忌表。

禁忌表中除了存放交换对，还存放每个交换对的有效期，交换对被加入到禁忌表中后会将有效期初始化为禁忌长度，并且每经过一个功耗管理时间片，禁忌长度减一，如果有效期为0，则交换对会被移除出禁忌表。

图3是一个判断交换对是否该进行线程交换采样的例子。在禁忌表中存放着以前的探索周期中交换后大于交换前的交换对，比如禁忌表第一行表示曾经gcc和bzip2在运行在cpu1和cpu2上运行时，gcc和bzip2比较偏向于gcc在cpu1上运行，bzip2在cpu2上运行的调度方式。调度器在进行线程迁移前，向禁忌表查询是否要将gcc交换到cpu2上，bzip2交换到cpu1上来采样。禁忌表发现该交换对在禁忌表中存在，向调度器反馈这个交换对不用进行采样。上述gcc与bzip2是程序标准测试集，用来对系统性能进行评估，cpu指的就是多核处理器中的某一个处理器芯片。

基于禁忌搜索的不可预见异构调度算法比局部搜索调度算法的区别是多了禁忌表写入、禁忌表查询、禁忌表更新三个步骤。本发明利用哈希表来存储和查询交换对，在哈希表中进行查询的算法复杂度是，因此基于禁忌搜索的不可预见异构调度算法的时间复杂度和局部搜索调度算法一样是。

以下是基于禁忌搜索的不可预见异构调度算法的详细参数设置：

(1)目标函数：本文目标是尽量提升片上多核处理器全局的性能和能效；

(2)初始解：以随机调度方案为算法初始解；

(3)邻域：当前调度方案所有线程随机进行两两交换获得的指派方案；

(4)候选解：机从邻域中获取一个候选解。在不可预见多核异构处理器调度问题中，每个候选解都需要采样，为了尽量减小探索周期长度，TSU调度算法和局部搜索调度算法一样只有一个候选解；

(5)禁忌对象：基于禁忌搜索的不可预见异构调度算法将交换对作为禁忌对象；

(6)禁忌表：存放线程交换后比交换前大的交换对及禁忌对象的有效期；

(7)禁忌长度：禁忌对象的初始值，根据实际情况进行调整；

(8)特赦准则：没有特赦准则；

(9)终止准则：当能耗管理时间片用完时终止算法；

基于禁忌搜索的不可预见异构调度算法流程如下：

(1)随机生成初始指派方案，按照指派方案将线程分配到内核上；

(2)随机生成所述线程数量的一半的交换对；

(3)检查禁忌表，移除已被禁忌的交换对；

(4)交换所有交换对中的线程，并对所有迁移后的线程进行采样；

(5)若交换对交换后大于交换前的，则标记这个交换对，并且将它加入禁忌表；否则将交换对取反后加入禁忌表；

(6)若所有迁移过的线程迁移后之和大于迁移前之和，将第(4)步中被标记的交换对中的线程还原到原有内核上；

(7)根据当前线程所在内核生成指派方案，稳定阶段将按照该指派方案进行调度；

(8)如果还有剩余功耗管理时间片，回到(2)；否则结束；

基于禁忌搜索的不可预见异构调度算法的伪代码如表1所示：

表1基于禁忌搜索的不可预见异构调度算法伪代码

以上内容是结合具体的优选实施方式对本发明所作的进一步详细说明，不能认定本发明的具体实施只局限于这些说明。对于本发明所属技术领域的普通技术人员来说，在不脱离本发明构思的前提下，还可以做出若干简单推演或替换，都应当视为属于本发明的保护范围。