片上网络多核处理器多线程的资源分配处理方法和系统

摘要

本发明提供一种片上网络多核处理器多线程的资源分配处理方法和系统。该系统包括检测单元，用于在片上网络多核处理器多线程程序执行过程中，检测出互斥控制的地址和数值，并将地址和数值写入互斥控制索引表；互斥控制索引表，用于存储所述检测单元检测出的互斥控制的地址和数值；剥夺分发处理单元，用于根据所述互斥控制索引表的地址和数值，将具有相同地址的互斥控制的线程排列进入登记队列，并剥夺所述登记队列中的部分线程的忙等待核资源，分发给其他线程使用。其有效地提高了多核处理器多线程程序的整体性能和可扩展性。

说明书

技术领域

本发明涉及在多核处理器上多线程处理技术领域，尤其涉及到动态改变 多核处理器芯片资源分配的一种片上网络(Network-on-chip，NoC)多核处理器 多线程的资源分配处理方法和系统。

背景技术

随着摩尔(Moore)定律的持续应用，单芯片上集成的晶体管数量越来越 多，为了充分利用如此多的晶体管以提高性能，同时由于设计复杂度的过高、 功耗和温度的限制，微处理器工业界不得不从努力提高乱序执行的单核处理 器性能转变为提高片上网络(NoC)多核处理器性能。

多核处理器，甚至众核处理器的出现，使得多线程程序的普及是不可避 免，因此，为了在多核处理器上提高应用程序的总体性能，尽可能的开发线 程级并行性而不是传统的单线程程序的指令级并行性已经是大势所趋。

在多线程程序中，各个线程分别执行同一个程序的不同部分，并通过共 享内存进行交互，为了保证程序的正确性，多个线程不允许同时更新共享数 据，这就是互斥原则。

现有技术中，在多线程程序的互斥控制中，使用同步原语(比如，锁 (lock))，其将包含有对共享数据访问的代码保护起来，其中被保护起来的 代码段称为临界区，这意味着，在同一时间内，只能有一个线程进入临界区， 而其他需要访问该临界区的线程必须忙等待，直到该线程离开临界区才能进 入。因此，对临界区的冲突访问使得多线程的执行串行化，会大大降低了程 序整体性能，并且其他线程等待进入临界区所执行的自旋操作，既占用了处 理器资源，也浪费了功耗，而且过多的自旋操作容易影响正确性(比如，活 锁)。对于某些具有非常多的数据同步的程序(比如，Mozilla Firefox、MySQL、 操作系统内核)，临界区不仅降低了性能，而且限制了程序的可扩展性(达到 峰值性能所需的线程数)。

同时，在多线程程序的互斥控制中，还使用栅栏(barrier)同步，其对先 到达同步点的线程需要等待其他还没有到达该同步点的线程，直到指定数量 的线程都到达同步点，所有线程才执行下一个阶段的计算。因此，先到达同 步点的线程忙等待的时间在很大程度上是由最后到达该同步点的线程决定 的。先到达同步点的线程所执行的自旋等待操作，其中，除了最后一个迭代 循环检测到标志位翻转，之前的迭代循环都是无效操作。因此，在栅栏(barrier) 同步的互斥控制中，同样也存在既占用了处理器资源，也浪费了功耗的问题。

发明内容

本发明的目的在于提供一种片上网络多核处理器多线程的资源分配处理 方法和系统，其有效地提高了多核处理器多线程程序的整体性能和可扩展性。

为实现本发明目的而提供的一种片上网络多核处理器多线程的资源分配 处理方法，包括如下步骤：

步骤S100，在片上网络多核处理器多线程程序执行过程中，检测出互斥 控制的地址和数值，并将地址和数值写入互斥控制索引表；

步骤S200，根据所述互斥控制索引表的地址和数值，将具有相同地址的 互斥控制的线程排列进入登记队列，并剥夺所述登记队列中的部分线程的忙 等待核资源，分发给其他线程使用。

较优地，所述步骤S100中，检测出互斥控制的地址和数值，并将地址和 数值写入互斥控制索引表，包括如下步骤：

步骤S110，检测出锁和/或栅栏，并且将锁的地址和数值、和/或栅栏的 同步信号量的地址和数值分别存入锁硬件索引表和/或同步信号量硬件索引 表。

较优地，所述步骤S200，包括如下步骤：

步骤S210，使用锁硬件索引表记录的锁的地址和数值，并将需要同一把 锁的线程进入锁登记队列，根据计时器计时，在计时达到预设值时，剥夺锁 登记队列中部分线程所在的忙等待核资源，分发给正在临界区中的线程使用；

较优地，所述步骤S200还包括下列步骤：

步骤S220，使用同步信号量硬件索引表记录同步信号量地址和数值，并 将先到达同步点的线程进入同步登记队列，根据计时器计时，在计时达到预 设值时，剥夺同步登记队列中部分线程所在的忙等待核资源，分发给未到达 同步点的线程使用。

为实现本发明目的还提供一种片上网络多核处理器多线程的资源分配处 理系统，包括检测单元，互斥控制索引表，剥夺分发处理单元，其中：

所述检测单元，用于在片上网络多核处理器多线程程序执行过程中，检 测出互斥控制的地址和数值，并将地址和数值写入互斥控制索引表；

所述互斥控制索引表，用于存储所述检测单元检测出的互斥控制的地址 和数值；

所述剥夺分发处理单元，用于根据所述互斥控制索引表的地址和数值， 将具有相同地址的互斥控制的线程排列进入登记队列，并剥夺所述登记队列 中的部分线程的忙等待核资源，分发给其他线程使用，从而加快临界区的执 行。

较优地，所述互斥控制的地址和数值，包括锁的地址和数值和/或栅栏的 同步信号量的地址和数值；所述互斥控制索引表，包括锁硬件索引表和/或同 步信号量硬件索引表。

较优地，所述剥夺分发处理单元，包括锁线程剥夺处理子单元，栅栏线 程剥夺子处理单元和计时器，其中：

所述锁线程剥夺处理子单元，用于使用锁硬件索引表记录的锁的地址和 数值，并将需要同一把锁的线程进入锁登记队列，根据计时器计时，在计时 达到预设值时，剥夺锁登记队列中部分线程所在的忙等待核资源，分发给正 在临界区中的线程使用；

所述栅栏线程剥夺子处理单元，用于使用同步信号量硬件索引表记录同 步信号量地址和数值，并将先到达同步点的线程进入同步登记队列，根据计 时器计时，在计时达到预设值时，剥夺同步登记队列中部分线程所在的忙等 待核资源，分发给未到达同步点的线程使用；

所述计时器，用于进行计时。

较优地，所述剥夺的核资源为剥夺运算部件和一级缓存资源；

在剥夺所述一级缓存时，采用最近最少使用页面替换策略，并且按预设 的数量限定可剥夺缓存的数量进行剥夺。

较优地，所述锁登记队列或者所述同步登记队列的每一项是32位向量， 每一位顺序对应不同的线程。

本发明的有益效果：本发明的片上网络多核处理器多线程的资源分配处 理方法和系统，通过检测出由于互斥控制(如锁(lock)和栅栏(barrier) 机制)导致的忙等待处理器核，利用忙等待核的资源加速临界区和同步点之 间的线程的执行，从而提高程序的整体性能和可扩展性。

附图说明

图1为本发明实施例的片上网络多核处理器多线程的资源分配处理系统 结构示意图；

图2为本发明片上网络多核处理器多线程的资源分配处理方法进行锁剥 夺执行多线程程序运行与传统的多线程程序运行效果对比图；

图3为本发明片上网络多核处理器多线程的资源分配处理方法进行同步 资源剥夺执行多线程程序运行与传统的多线程程序运行效果对比图。

具体实施方式

为了使本发明的目的、技术方案及优点更加清楚明白，以下结合附图， 对本发明片上网络多核处理器多线程的资源分配处理方法和系统的实现进行 进一步详细说明。应当理解，此处所描述的具体实施例仅仅用以解释本发明， 并不用于限定本发明。

作为一种可实施方式，本发明实施例的片上网络多核处理器多线程的资 源分配处理方法，包括如下步骤：

步骤S100，在片上网络多核处理器多线程程序执行过程中，检测出互斥 控制的地址和数值，并将地址和数值写入互斥控制索引表；

步骤S200，根据所述互斥控制索引表的地址和数值，将具有相同地址的 互斥控制的线程排列进入登记队列，并剥夺所述登记队列中的部分线程的忙 等待核资源，分发给其他线程使用，从而加快临界区的执行。

较佳地，作为一种可实施方式，所述步骤S100中，所述互斥控制的地址 和数值，包括锁的地址和数值和/或栅栏的同步信号量的地址和数值；所述互 斥控制索引表，包括锁硬件索引表和/或同步信号量硬件索引表。

较佳地，作为一种可实施方式，所述剥夺的核资源为剥夺运算部件和一 级缓存(L1 cache)资源等；

作为一种可实施方式，所述运算部件包括但不限于浮点和整数加法器、 乘法器和除法器；

作为一种可实施方式，所述一级缓存(L1 cache)包括但不限于指令缓存 (Instruction cache，Icache)和数据缓存(Data cache，Dcache)。

在加速临界区执行和加快关键线程到达同步点的方法中涉及到的资源， 作为一种可实施方式，可以是运算部件和一级缓存(L1 cache)等。运算部件 包括浮点和整数加法器、乘法器和除法器。一级缓存(L1 cache)包括指令缓 存(Instruction cache，Icache)和数据缓存(Data cache，Dcache)。

通过增加处理器核运算部件的个数，使得每一拍从保留站发射到功能部 件的指令数增多，等同于增大了指令窗口的大小。

通过增加处理器一级缓存(L1 cache)大小，大大加快了处理器核取指和 取数速度。

为了避免被剥夺资源的处理器核恢复使用它自己的资源时产生不必要的 开销，更佳地，在剥夺所述一级缓存(L1 cache)时，采用最近最少使用页面 (Least Recently Used，LRU)替换策略，并且按预设的数量限定可剥夺缓存 (cache)的数量进行剥夺。

较佳地，作为一种可实施方式，所述步骤S100中，检测出互斥控制的地 址和数值，并将地址和数值写入互斥控制索引表，包括如下步骤：

步骤S110，检测出锁(lock)和/或栅栏(barrier)，并且将锁的地址 和数值、和/或栅栏的同步信号量的地址和数值分别存入锁硬件索引表和/或 同步信号量硬件索引表。

作为一种可实施方式，本发明实施例中，可通过利用ll/sc指令判定检测 锁。

由于实现锁的汇编代码中包含有特殊的ll/sc指令，所以本发明实施例中， 通过检测ll/sc指令来判定锁，当某一把锁被第一次使用，抢锁必定成功，将 该锁的地址和数值存入锁硬件索引表。

所述步骤S200，包括如下步骤：

步骤S210，使用锁硬件索引表记录的锁的地址和数值，并将需要同一把 锁的线程进入锁登记队列，根据计时器计时，在计时达到预设值时，剥夺锁 锁登记队列中部分线程所在的忙等待核资源，分发给正在临界区中的线程使 用，从而加速临界区的执行；

较佳地，作为一种可实施方式，所述步骤S210中，包括如下步骤：

步骤S211，在该锁的地址和数值存入锁硬件索引表时，启动计时器开始 计时，当检测出抢同一把锁的其他线程时，如果锁此时不可用，则将该同一 把锁的其他线程标记到锁登记队列；

步骤S212，当原来占用该锁的线程还没有离开临界区，而计时器到达预 设数值时，则从登记队列的队尾中取出一个或者多个线程，剥夺所述队尾取 出的一个或者多个线程的部分资源给正在临界区中的线程使用，同时将计时 器归零并重新开始计时；

步骤S213，当原来占用该锁的线程离开临界区，则从登记队列的队头中 取出一个线程，让所述队头取出的线程进入临界区作为新的占用该锁的线程， 同时将剥夺的资源转交给所述队头取出的线程，并将该离开临界区的线程从 锁登记队列删除，计时器归零后重新开始计时，返回步骤S212，直至锁登记 队列为空后结束返回。

步骤S220，使用同步信号量硬件索引表记录同步信号量地址和数值，并 将先到达同步点的线程进入同步登记队列，根据计时器计时，在计时达到预 设值时，剥夺同步登记队列中部分线程所在的忙等待核资源，分发给未到达 同步点的线程使用，从而加速未到达同步点的线程的执行。

栅栏的功能是迫使先到达同步点的线程等待，直到所有线程都到达同步 点后才能继续执行。

栅栏检测是一种现有技术，因此，在本发明实施例中，不再一一详细描 述。

较佳地，作为一种可实施方式，所述步骤S220中，包括如下步骤：

步骤S221，当第一个线程到达栅栏(barrier)，在同步信号量硬件索引表 中记录同步信号量的地址和数值时，启动计时器开始计时；

步骤S222，当其他线程到达栅栏(barrier)，则标记登记队列的相应位；

步骤S223，当计时器到达某一预设的数值，而该栅栏(barrier)指定数 量的线程还没有完全到达，则从登记队列中取出队尾的一个或者多个线程， 剥夺它们的部分资源给未到达该栅栏(barrier)的线程使用；

步骤S224，同时计时器归零后重新开始计时，返回步骤S223，直至所述 预先指定数量的线程都到达栅栏后进入步骤S225；

步骤S225，当所有预先指定数量的线程都到达了栅栏(barrier)，则将同 步信号量硬件登记表清空并返回。

作为一种可实施方式，在系统初始化时，将计时器初始化归零。

更佳地，所述锁登记队列或者所述同步登记队列的每一项是32位向量， 每一位顺序对应不同的线程。

相应地，本发明实施例的一种片上网络多核处理器多线程的资源分配处 理系统，如图3所示，其包括检测单元10，互斥控制索引表30，剥夺分发处 理单元20，其中：

所述检测单元10，用于在片上网络多核处理器多线程程序执行过程中， 检测出互斥控制的地址和数值，并将地址和数值写入互斥控制索引表30；

所述互斥控制索引表30，用于存储所述检测单元10检测出的互斥控制 的地址和数值；

所述剥夺分发处理单元20，用于根据所述互斥控制索引表的地址和数值， 将具有相同地址的互斥控制的线程排列进入登记队列，并剥夺所述登记队列 中的部分线程的忙等待核资源，分发给其他线程使用，从而加快临界区的执 行。

较佳地，所述较佳地，作为一种可实施方式，所述步骤S100中，所述互 斥控制的地址和数值，包括锁的地址和数值和/或栅栏的同步信号量的地址和 数值；所述互斥控制索引表，包括锁硬件索引表和/或同步信号量硬件索引表。

较佳地，作为一种可实施方式，所述剥夺的核资源为剥夺运算部件和一 级缓存(L1 cache)资源等；

所述运算部件包括但不限于浮点和整数加法器、乘法器和除法器；

所述一级缓存(L1 cache)包括但不限于指令缓存(Instruction cache， Icache)和数据缓存(Data cache，Dcache)。

较佳地，作为一种可实施方式，所述剥夺分发处理单元20，包括锁线程 剥夺处理子单元201，栅栏线程剥夺子处理单元202和计时器203，其中：

所述锁线程剥夺处理子单元201，用于使用锁硬件索引表记录的锁的地 址和数值，并将需要同一把锁的线程进入锁登记队列，根据计时器202计时， 在计时达到预设值时，剥夺锁锁登记队列中部分线程所在的忙等待核资源， 分发给正在临界区中的线程使用，加速临界区的执行；

所述栅栏线程剥夺子处理单元202，用于使用同步信号量硬件索引表记 录同步信号量地址和数值，并将先到达同步点的线程进入同步登记队列，根 据计时器202计时，在计时达到预设值时，剥夺同步登记队列中部分线程所 在的忙等待核资源，分发给未到达同步点的线程使用，加速未到达同步点的 线程的执行；

所述计时器202，用于进行计时。

本发明实施例的片上网络多核处理器多线程的资源分配处理系统，其与 本发明实施例的片上网络多核处理器多线程的资源分配处理方法工作过程相 同，因此，在本发明实施例中，不再一一详细描述。

如图4为本发明实施例片上网络多核处理器多线程的资源分配处理方法 和系统执行的多线程程序通过检测锁(lock)并剥夺核资源而加快运行与传 统的多线程程序运行效果对比图。

图5为本发明实施例片上网络多核处理器多线程的资源分配处理方法通 过检测栅栏((barrier)剥夺核资源而加快运行执行与传统的多线程程序运行 效果对比图。

其中，检测环境如表1所示。

表1 为本发明资源分配检测运行环境表

  clock frequency   2GHz   issue width   2-wide   processor style   In-order

  pipeline stages   5   L1cache(I and D)   32KB，2-way set associative   L2 cache   256KB，8-way set associative   Coherence   MESI，On-chip distributed directory

本发明实施例的片上网络多核处理器多线程的资源分配处理方法和系 统，通过使用硬件检测出由于锁(lock)和栅栏(barrier)机制导致的忙等 待处理器核，利用忙等待核的资源加速临界区和同步点之间的一个或者多个 影响应用程序最终运行时间的线程的关键线程(比如涉及到锁(lock)的进 入临界区的线程和涉及到栅栏(barrie)的还没有到达同步点的线程)的执 行，从而提高程序的整体性能和可扩展性。最后应当说明的是，很显然，本 领域的技术人员可以对本发明进行各种改动和变型而不脱离本发明的精神和 范围。这样，倘若本发明的这些修改和变型属于本发明权利要求及其等同技 术的范围之内，则本发明也意图包含这些改动和变型。