用于多核处理器的多线程应用识别存储器调度方案

摘要

一种设备可包括存储器控制器，其识别多线程应用，并基于对所述多线程应用的识别调整用于所述多线程应用的存储器调度方案。

说明书

背景技术

向多/许多核（多核）处理器的转变已使多线程应用在客户端和 服务器平台上都很流行。此类应用的高线程级并行(TLP)有效地利用 了多核处理器（如芯片多处理器(CMP)系统）支持的硬件并行。存在 对于加速多线程应用的执行的软件和硬件提议，例如一起执行应用的 线程的操作系统的协调线程调度。然而，没有提议解决用于多线程应 用的存储器调度（如由存储器控制器）中可使性能显著降级的性能问 题。

诸如先就绪先来到先服务(FRFCFS)机制和并行识别批量调度 (PAR-BS)机制的一些机制试图改善存储器控制器的性能。例如， FRFCFS机制通过调度访问存储体的行缓冲器的存储器请求来提高 存储器控制器的性能。PAR-BS机制将存储器请求分批，一批一批地 执行存储器请求，并且通过对每个批次应用最短作业优先法(SJF)调 度来改善存储器控制器的性能。然而，这两种机制只优化了用于单线 程应用的存储器调度，而不能优化用于多线程应用的存储器调度。

发明的实施例的概要

根据一个实施例，一种计算设备实现的方法可包括由计算设备识 别多线程应用和由计算设备基于对多线程应用的识别调整用于多线 程应用的存储器调度方案。

根据一个方面，多线程应用可与第一组相关；识别多线程应用可 包括接收与第一组相关的多线程应用的线程；并且该方法还可包括接 收与第二组相关的单线程应用的线程。

根据另一方面，调整存储器调度方案可包括确定第一组和第二组 中的空闲线程的数量；基于确定的第一组中的空闲线程的数量对第一 组进行排名；基于确定的第二组中的空闲线程的数量对第二组进行排 名；以及使与第一组和第二组中排名较高的一个组相关的存储器请求 优先于与第一组和第二组中排名较低的一个组相关的存储器请求。

根据另一个实施例，设备的存储器控制器可包括用来接收与组相 关的多线程应用的线程以及接收与其它组相关的单线程应用的线程 的处理逻辑。该处理逻辑还可确定所述组和所述其它组中空闲线程的 数量；基于确定的所述组中的空闲线程的数量对所述组进行排名；以 及基于确定的所述其它组中的空闲线程的数量对所述其它组进行排 名。处理逻辑还可使与所述组和所述其它组中排名较高的一个组相关 的存储器请求优先于与所述组和所述其它组中排名较低的一个组相 关的存储器请求。

根据又一个实施例，设备可包括用来识别多线程应用并基于对多 线程应用的识别调整用于多线程应用的存储器调度方案的存储器控 制器。

根据又一个实施例，一种计算机可读存储设备可存储一个或多个 计算机可执行指令，并且可包括用来从一组其它应用中识别多线程应 用的一个或多个指令以及用来基于对多线程应用的识别调整用于多 线程应用的存储器调度方案的一个或多个指令。

附图简述

并入本说明书中并构成本说明书的一部分的附图示出了本文描 述的一个或多个实施例，并且与其它描述一起对这些实施例进行了解 释。其中：

图1是经历性能降级的示例性存储器调度布置的示意图；

图2是可根据本文描述的实施例的可执行多线程应用识别存储 器调度方案的设备的示例性组件的示意图；

图3是图2中描述的设备的处理单元和主存储器的示例性组件的 示意图；

图4是图3中描述的处理单元的存储器控制器的示例性功能组件 的示意图；

图5是图4中描述的存储器控制器的线程组接收器的示例性功能 组件的示意图；

图6是图4中描述的存储器控制器的空闲线程检测器的示例性功 能组件的示意图；

图7是图4中描述的存储器控制器的组排名器的示例性功能组件 的示意图；

图8是图4中描述的存储器控制器的存储器调度器的示例性功能 组件的示意图；

图9A和图9B是能够由图5中描述的线程组接收器执行的示例 性操作的示意图；

图10A和图10B是能够由图6中描述的空闲线程检测器执行的 示例性操作的示意图；

图11是能够由图7中描述的组排名器执行的示例性操作的示意 图；

图12A和图12B是能够由图8中描述的存储器调度器执行的示 例性操作的示意图；

图13-图15是根据本文描述的实施例的用于多线程应用识别存 储器调度的示例性过程的流程图。

具体实施方式

以下详细描述参考附图。不同附图中的相同参考数字可标识相同 或相似的元件。此外，以下详细描述不限制本发明。

概述

本文描述的系统和/或方法可使设备（如带有多核处理器的设备， 例如个人计算机、膝上型计算机、平板计算机、服务器设备、手持或 移动设备和/或其它类型的计算或通信设备）的存储器控制器能够识 别一个或多个多线程应用，并基于对多线程应用的识别调整或优化用 于多线程应用的存储器调度方案。此类系统和/或方法可防止归因于 不充足的存储器调度的（如设备中的）性能降级。在一个实施例中， 存储器控制器可接收与第一组相关的多线程应用的线程，并可接收与 第二组相关的单线程应用的线程。存储器控制器可确定第一和第二组 中的空闲线程的数量，可基于空闲线程的数量对第一组和第二组进行 排名，并可使来自具有较高排名的组的存储器请求优先于来自具有较 低排名的组的存储器请求。

如本文所使用的，术语“线程”旨在被宽泛地解释为包括允许应 用执行顺序的动作或一次执行许多动作的计算机程序（或应用）的部 分（如任务）。应用中的每个线程可识别在被应用指示时执行的进程。

如本文所使用的，术语“组件”和“设备”旨在被宽泛地理解为 包括硬件（如处理器、微处理器、专用集成电路(ASIC)、现场可编程 门阵列(FPGA)、芯片、存储设备（如只读存储器(ROM)、随机存取 存储器(RAM)等）等）或硬件和软件的组合（如执行存储设备中包含 的软件的处理器、微处理器、ASIC等）。

示例性存储器调度布置

图1是经历性能降级的示例性存储器调度布置100的示意图。如 图所示，单线程应用（如APP_A）可包括与多核处理器的第一存储 体（如BANK1）和第一核（如CORE_1）相关的两个存储器请求。 多线程应用（如APP_B）可包括两个线程（如线程APP_B1和APP_B2） 和用于同步的障碍。在一个实例中，用于同步的障碍可指示多核处理 器对在障碍之前和之后提供的存储器请求实施排序约束。线程 APP_B1可与多核处理器的第二核（如CORE_2）相关，可包括在障 碍之后提供的两个存储器请求，并可包括在障碍之前提供的且与第一 存储体BANK1相关的三个存储器请求。线程APP_B2可与多核处理器的第三核（如CORE_3）相关，并可包括在障碍之后提供的两个存 储器请求。

多线程应用APP_B可被设计为通过使线程APP_B1访问第一存 储体BANK1且使线程APP_B2访问第二存储体BANK2来利用存 储体级并行。由于在障碍周围可能的负载不平衡（如由于实现完美的 运行时负载平衡可能很难而可能发生这种情况），线程APP_B2可在 线程APP_B1之前到达障碍。负载不平衡可阻止与线程APP_B2相关 的存储器请求访问第二存储体BANK2，从而可导致第三核CORE_3 处于空闲状态。第三核CORE_3可保持在空闲状态，直到与线程 APP_B1相关的（如在障碍之下提供的）三个存储器请求被处理。因 此，与线程APP_B1相关的（如在障碍之下提供的）三个存储器请求 应被赋予高于与单线程应用APP_A相关的存储器请求的优先级（如 使得第三核CORE_3保持空闲达三个周期）。

然而，当前存储器调度方案不识别多线程应用且试图调度存储器 请求以加速语义地阻止多线程应用的其它线程取得进展的同一多线 程应用的线程。例如，由于障碍，线程APP_B1可阻止线程APP_B2 取得进展。如果在布置100中采用FRFCFS存储器调度方案，则由于 单线程应用APP_A具有高于线程APP_B1的行缓冲器命中率， FRFCFS方案可使性能降级。在FRFCFS方案中，命中行缓冲器的存 储器请求可被优先化。因此，单线程应用APP_A的存储器请求可优 先于线程APP_B1的存储器请求，因为单线程应用APP_A的存储器 请求与第一存储体BANK1的相同行（如行1）相关，而线程APP_B1 的存储器请求与第一存储体BANK1的不同行（如行2-4）相关。这 可将第三核CORE_3的空闲时间从三个周期增加到五个周期，并可阻 止第三核CORE_3在障碍之后执行多线程应用APP_B。

如果布置100中采用PAR-BS存储器调度方案，则根据最短作业 优先法(SJF)策略，PAR-BS方案可将具有最少数量的存储器请求的线 程的存储器请求在存储器请求队列中优先化。因此，单线程应用 APP_A的存储器请求可优先于线程APP_B1的存储器请求，因为单 线程应用APP_A的存储器请求的数量为二，而线程APP_B1的存储 器请求的数量为三。这可将第三核CORE_3的空闲时间从三个周期增 加到五个周期，并可阻止第三核CORE_3在障碍之后执行多线程应 用APP_B。FRFCFS和PAR-BS存储器调度方案以及其它存储器调度 方案不识别多线程应用，使性能降级，并使操作系统对协调线程调度 的努力徒劳。

相反，本文描述的系统和/或方法可使设备的存储器控制器能够 识别一个或多个多线程应用，并基于对多线程应用的识别优化用于多 线程应用的存储器调度方案。例如，本文描述的系统和/或方法可将 可使一组线程而不是仅单个线程受益的存储器请求优先化（如服务于 线程APP_B1的请求以使线程APP_B1和线程APP_B2都受益）。

示例性设备配置

图2是根据本文描述的实施例的可执行多线程应用识别存储器 调度方案的设备200的示例性组件的示意图。设备200可包括利用多 核处理器和/或多线程应用的任何计算或通信设备。例如，设备200 可包括个人计算机、台式计算机、膝上型计算机、平板计算机、服务 器设备、无线电话、个人通信系统(PCS)终端、个人数字助理(PDA)、 蜂窝电话、智能电话和/或其它类型的计算或通信设备。

如图2所示，设备200可包括总线210、处理单元220、主存储 器230、ROM240、存储设备250、输入设备260、输出设备270和/ 或通信接口280。总线210可包括允许设备200的组件之间通信的路 径。

处理单元220可包括一个或多个处理器（如多核处理器）、微处 理器或可解释并执行指令的其它类型的处理单元。在一个实施例中， 处理单元220可包括其包括多个核的单个处理器。主存储器230可包 括RAM、动态RAM(DRAM)和/或可存储供处理单元220执行的信息 和指令的另一类型的动态存储设备。ROM240可包括ROM设备或可 存储供处理单元220使用的静态信息和/或指令的另一类型的静态存 储设备。存储设备250可包括磁和/或光学记录介质及其对应的驱动 器。

输入设备260可包括允许操作者向设备200输入信息的机制，例 如键盘、鼠标、笔、麦克风、语音识别和/或生物特征机制、触摸屏 等。输出设备270可包括向操作者输出信息的机制，包括显示器、打 印机、扬声器等。通信接口280可包括使设备200能够与其它设备和 /或系统通信的任何收发器类的机制。例如，通信接口280可包括用 于通过网络与另一设备或系统通信的机制。

如本文所述，设备200可响应于处理单元220执行包含在计算机 可读介质（例如主存储器230）中的软件指令而执行某些操作。计算 机可读介质可被定义为物理或逻辑存储设备。逻辑存储设备可包括单 个物理存储设备内或分布在多个物理存储设备间的存储空间。软件指 令可从另一计算机可读介质（例如存储设备250）或通过通信接口280 从另一设备读入到主存储器230中。包含在主存储器230中的软件指 令可使处理单元220执行本文描述的过程。或者，硬连线电路可代替 或结合软件指令用来实现本文描述的过程。因此，本文描述的实施例 不限于硬件电路和软件的任何特定组合。

尽管图2示出了设备200的示例性组件，但在其它实施例中，相 对于图2所示，设备200可包括更少的组件、不同的组件、以不同方 式布置的组件或附加的组件。或者或另外，设备200的一个或多个组 件可执行被描述为由设备200的一个或多个其它组件执行的一个或 多个其它任务。

图3是设备200的处理单元220和主存储器230的示例性组件的 示意图。在一个实施例中，图3所示的组件可形成存储器调度布置 300。如图所示，处理单元220可包括多个核310-1、310-2、310-3等 （在本文统称为“核310”）和存储器控制器320。主存储器230可包 括多个存储器存储体330-1、330-2等（在本文统称为“存储体330”）。

核310可集成到单个集成电路管芯（如芯片多处理器(CMP)）上 或可集成到单个芯片封装中的多个管芯上。核310中的每个核可包括 处理器、微处理器或可解释并执行指令的另一类型的处理单元。

存储器控制器320可包括一个或多个处理器、微处理器、ASIC、 FPGA或可解释并执行（如包含在存储器控制器320的计算机可读介 质中的）指令的其它类型的处理逻辑，以便执行本文描述的操作。在 一个实施例中，存储器控制器320可包括管理去往或来自主存储器 230的数据流的数字电路。存储器控制器320可为单独的芯片，或可 集成到另一芯片中，例如在处理单元220的管芯上。存储器控制器 320可包括逻辑，其用来从主存储器230读取和向其写入以及通过发 送经过主存储器230的电流来刷新主存储器230。可通过使用多路复 用器和多路分用器来促进从主存储器230读取和向其写入。存储器控 制器320可选择主存储器230的正确的行和列地址，作为向多路复用 器的输入。多路分用器可选择主存储器230的正确的存储器位置，并 可返回与该存储器位置相关的数据。在另一实施例中，存储器控制器 320可为处理单元220的功能组件。

存储体330中的每个可包括存储在主存储器230中的数据的个别 部分。在一个实例中，存储体330中的每个可包含临时存储的数据并 用作存储器缓存。存储体330可连续地排序，从而可提供对存储在主 存储器230中的个别项目的容易访问。存储体330中的每个可包括可 被设计为独立处理信息传输的主存储器230的物理部分。

如图3中进一步所示，存储器控制器320可提供用于单线程应用 (APP_A)340和包括两个线程（如线程(APP_B1)350-1和线程 (APP_B2)350-2）的多线程应用(APP_B)350的存储器调度方案。单线 程应用340可由核310-1执行且可与存储体330-1相关。线程350-1 可由核310-2执行且可与存储体330-1相关。线程350-2可由核310-3 执行且可与存储体330-2相关。因此，图3所示的存储器调度布置300 可类似于图1所示的存储器调度布置100。

然而，与传统的存储器调度方案（如上文参照图1所述的）不同， 存储器控制器320可提供成本有效的存储器调度方案，其在多线程应 用（如多线程应用350）包括空闲线程时将多线程应用的线程（如线 程350-1和350-2）优先化。为了解释的目的，假定多线程应用350 包括空闲线程（如线程350-2可以是空闲的）。线程可出于几种原因 而空闲。例如，如上文参照图1所述，在障碍处的负载不平衡可使在 较早的时间到达障碍的线程空闲。在另一实例中，被锁定保护的关键 部分可只允许多线程应用的一个线程进入，而等待进入该关键部分的 （如多线程应用的）其它线程变得空闲。在又一个实例中，多线程应 用的在算法上顺序的区域可由多线程应用的单个线程执行，从而可使 多线程应用的其它线程空闲。通过使具有空闲线程的多线程应用的线 程优先化，存储器控制器320可帮助空闲线程迅速结束无效率的执行 阶段并使多线程应用返回到所有线程被并行地完全执行的执行阶段。

在一个实施例中，存储器控制器320可接收（如与通过操作系统 与第一组相关的）多线程应用350的线程350-1和350-2，并可接收 （如通过操作系统与第二组相关的）单线程应用340的线程。存储器 控制器320可确定第一和第二组中空闲线程（如线程350-2）的数量， 并基于该空闲线程的数量对第一组和第二组进行排名。例如，由于第 一组可能包括空闲线程（如线程350-2）而第二组可能不包括空闲线 程，所以存储器控制器320可使第一组的排名高于第二组。存储器控 制器320可使来自具有较高排名的组的存储器请求优先于来自具有 较低排名的组的存储器请求。例如，存储器控制器320可使来自第一 组（如来自线程350-2）的存储器请求优先于来自第二组（如来自单 线程应用340）的存储器请求。

尽管图3示出了处理单元220和主存储器230的示例性组件，但 在其它实施例中，相对于图3所示，处理单元220和/或主存储器230 可包括更少的组件、不同的组件、以不同方式布置的组件或附加的组 件。或者或另外，处理单元220和/或主存储器230的一个或多个组 件可执行被描述为由处理单元220和/或主存储器230的一个或多个 其它组件执行的一个或多个其它任务。

示例性存储器控制器配置

图4是存储器控制器320的示例性功能组件的示意图。在一个实 施例中，结合图4所描述的功能组件可由包括在存储器控制器320中 的一个或多个处理器、微处理器、ASIC、FPGA或其它类型的处理逻 辑来实现。如图4所示，存储器控制器320可包括线程组接收器400、 空闲线程检测器410、组排名器420和存储器调度器430。

线程组接收器400可包括可接收与一个或多个应用相关的一个 或多个线程440并可产生线程440的线程组信息450-1（如针对由设 备200的操作系统定义的第一线程组）和线程组信息450-2（如针对 由设备200的操作系统定义的第二线程组）的硬件或硬件和软件的组 合。例如，线程组接收器400可产生单线程应用的线程的线程组信息 450-1并可产生多线程应用的线程的线程组信息450-2。如图4所示， 线程组接收器400可将线程组信息450-1（如针对第一定义的线程组） 和线程组信息450-2（如针对第二定义的线程组）提供到空闲线程检 测器410和组排名器420。下文将结合例如图5提供线程组接收器400 更多详细信息。

空闲线程检测器410可包括可接收来自线程组接收器400的线程 组信息450-1和450-2并可接收与线程440相关的一个或多个存储器 请求460的硬件或硬件和软件的组合。空闲线程检测器410可基于线 程组信息450-1/450-2和存储器请求460确定线程440中的哪些线程 是空闲的，并可将所确定的空闲线程提供到组排名器420，如参考数 字470所指示。下文将结合例如图6提供空闲线程检测器410的更多 详细信息。

组排名器420可包括可接收来自线程组接收器400的线程组信息 450-1和450-2并可接收来自空闲线程检测器410的空闲线程470的 硬件或硬件和软件的组合。组排名器420可基于每个线程组中的空闲 线程470的数量对（如由线程组信息450-1和450-2所定义的）线程 组中的线程进行排名。组排名器420可将线程组的排名提供到存储器 调度器430，如参考数字480所指示。下文将结合例如图7提供组排 名器420的更多详细信息。

存储器调度器430可包括可接收来自组排名器420的线程组排名 480并可接收与线程440相关的一个或多个存储器请求460的硬件或 硬件和软件的组合。存储器调度器430可基于线程组排名480将存储 器请求460优先化，如参考数字490所指示，并可在设备200中实现 经过优先化的存储器请求490。下文将结合例如图8提供存储器调度 器430的更多详细信息。

尽管图4示出了存储器控制器320的示例性功能组件，但在其它 实施例中，相对于图4中所示，存储器控制器320可包括更少的功能 组件、不同的功能组件、以不同方式布置的功能组件或附加的功能组 件。或者或另外，存储器控制器320的一个或多个功能组件可执行被 描述为由存储器控制器320的一个或多个其它功能组件执行的一个 或多个其它任务。

图5是存储器控制器320的线程组接收器400的示例性功能组件 的示意图。在一个实施例中，结合图5所述的功能组件可由包括在存 储器控制器320中的一个或多个处理器、微处理器、ASIC、FPGA或 其它类型的处理逻辑来实现。如图5所示，线程组接收器400可包括 每核组标识(ID)寄存器500。

每核组ID寄存器500可包括可接收例如来自设备200的操作系 统的线程信息510和组ID信息520的硬件或硬件和软件的组合。在 一个实例中，当一起执行同一应用的线程时，操作系统可产生线程信 息510（如用于协调线程调度）。组ID信息520可包括在每个核（如 核310中的每个核）上被执行的线程的组ID。当操作系统在核（如 核310中的一个核）上调度特定线程时，操作系统可用该特定线程的 组ID（如组ID信息520）更新每核组ID寄存器500。

在一个示例实施例中，多线程应用的主线程如同该主线程是单线 程应用那样被操作系统执行。操作系统可向主线程分配组标识(ID)。 当主线程生成更多线程时，操作系统可向生成的线程分配组ID（如 组ID信息520）。当多线程应用的线程中的一个线程被调度来在特定 核（如核310中的一个核）上执行时，每核组ID寄存器500可将待 执行的线程设置为该组ID。如图5进一步所示，每核组ID寄存器500 可基于线程信息510和组ID信息520产生线程组信息450-1和线程 组信息450-2。

尽管图5示出了线程组接收器400的示例性功能组件，但在其它 实施例中，相对于图5所示，线程组接收器400可包括更少的功能组 件、不同的功能组件、以不同方式布置的功能组件或附加的功能组件。 或者或另外，线程组接收器400的一个或多个功能组件可执行被描述 为由线程组接收器400的一个或多个其它功能组件执行的一个或多 个其它任务。

图6是存储器控制器320的空闲线程检测器410的示例性功能组 件的示意图。在一个实施例中，结合图6所述的功能组件可由包括在 存储器控制器320中的一个或多个处理器、微处理器、ASIC、FPGA 或其它类型的处理逻辑来实现。如图6所示，空闲线程检测器410可 包括未激活核位向量600，该未激活核位向量600可包括一个或多个 位610-1、…、610-4（在本文统称为“位610”）。

未激活核位向量600可包括可接收来自线程组接收器400的线程 组信息450-1和450-2、可接收存储器请求460并可接收时间段620 的硬件或硬件和软件的组合。未激活核位向量600可基于线程组信息 450-1和450-2将位610中的每个位关联到线程440之一及其对应的 核（如核310之一）。例如，未激活核位向量600可将位610-1与单 线程应用的线程关联，可将位610-2与多线程应用的第一线程关联， 并可将位610-3与多线程应用的第二线程关联。未激活核位向量600 可定期地在时间段620开始时设置位610中的每个位（如为特定的 值）。时间段620可为可变参数并可基于利用存储器控制器320的设 备200的类型和/或由设备200执行的应用的类型来设置。在一个实 例中，时间段620可为足够短以迅速适应应用阶段变化，但可为足够 长以防止在核（如核310中的一个核）未空闲时将其误判为空闲。在 一个实施例中，时间段620可被设置为约一千(1,000)个时钟周期的 值。

当存在来自在对应的核上执行的线程（如按线程组信息450-1和 450-2所定义的）的存储器请求（如存储器请求460）时，未激活核 位向量600可重置位610之一。例如，如图6所示，位610-1、610-2 和610-4可与来自在对应的核上执行的线程的存储器请求460相关。 因此，未激活核位向量600可重置位610-1、610-2和610-4。由于位 610-3不与存储器请求相关，所以未激活核位向量600可不重置位 610-3。如果在时间段620结束时位（如位610-3）保持被设置，则未 激活核位向量600可确定在对应于位610-3的核上执行的线程在时间 段620期间是空闲的，如参考数字470所指示。未激活核位向量600 可输出空闲线程的指示470。

尽管图6示出了空闲线程检测器410的示例性功能组件，但在其 它实施例中，相对于图6所示，空闲线程检测器410可包括不同的功 能组件、以不同方式布置的功能组件或附加的功能组件。

图7是存储器控制器320的组排名器420的示例性功能组件的示 意图。在一个实施例中，结合图7所述的功能组件可由包括在存储器 控制器320中的一个或多个处理器、微处理器、ASIC、FPGA或其它 类型的处理逻辑来实现。如图7所示，组排名器420可包括排名机制 700。

排名机制700可包括可接收来自线程组接收器400的线程组信息 450-1和450-2（未示出）并可接收来自空闲线程检测器410的空闲 线程的指示470（未示出）的硬件或硬件和软件的组合。排名机制700 可接收一个或多个线程组（如按线程组信息450-1和450-2所定义的） 中的位610和与该一个或多个线程组相关的线程（如按线程组信息 450-1和450-2所定义的）。例如，如图7所示，排名机制700可（如 在时间段620结束时）接收线程组(g)720中的位610-2和610-3并可 接收与线程组(g)720相关的线程730。排名机制700可基于线程组 (g)720中的位610-2和610-3确定线程组(g)720的排名740-1。在一个 实施例中，排名机制700可通过将位610-2和610-3（如其对应于线 程组(g)720占用的空闲核）的值相加来确定线程组(g)720的排名 740-1。

在一个实施例中，排名机制700可根据如下方程式来确定线程组 (g)720的排名740-1：

${\mathrm{Rank}}_g={\Sigma }_{m=1}^M\mathrm{IC}\left[\mathrm{Core}{\mathrm{ID}}_m\right]$

其中，Rank_g可对应于线程组(g)的排名，M可对应于属于线程组(g) 的线程的总数，m可对应于线程组(g)使用的核，IC可对应于线程组(g) 占用的空闲核的数量，且CoreID_m可对应于线程组(g)使用的第m个 核的ID。因此，线程组(g)的排名可等于该线程组占用的空闲核的数 量。

如果线程组的所有线程已激活（如由核310之一执行），该线程 组的所有对应的位610可被重置，并且该线程组的排名可被确定为 零。如果线程组的一个或多个线程空闲（如未由核310之一执行，例 如空闲线程470），则该线程组的一个或多个位610可被设置（如不 重置），并且该线程组的排名可被确定为大于零。例如，如图7所示， 由于位610-3被设置（如指示线程组(g)包括空闲线程470），排名机 制700可确定线程组(g)的排名740-1为大于零的值。排名机制700可 确定其它线程组的排名740-2和740-3，并可输出排名740-1、740-2 和740-3（如其可对应于线程组排名480）。如图6进一步所示，排名 740-2可为零，这可指示对应线程组的所有线程已激活（如由核310 之一执行）。

尽管图7示出了组排名器420的示例性功能组件，但在其它实施 例中，相对于图7所示，组排名器420可包括不同的功能组件、以不 同方式布置的功能组件或附加的功能组件。

图8是存储器控制器320的存储器调度器430的示例性功能组件 的示意图。在一个实施例中，结合图8所述的功能组件可由包括在存 储器控制器320中的一个或多个处理器、微处理器、ASIC、FPGA或 其它类型的处理逻辑来实现。如图8所示，存储器调度器430可包括 组排名规则组件800、先就绪规则组件810和先来到先服务规则组件 820。

组排名规则组件800可包括可接收存储器请求460和（如来自组 排名器420的）线程组排名480并可基于线程组排名480将存储器请 求460优先化（如参考数字830所指示）的硬件或硬件和软件的组合。 例如，组排名规则组件800可将来自具有较高线程组排名的线程组的 存储器请求优先于来自具有较低线程组排名的线程组的存储器请求。

组排名规则组件800可确保（如与空闲线程组和核相关的）存储 器请求被优先化。空闲线程组和核可将其空闲状态通知存储器控制器 320（如通过线程组排名480），从而可向存储器控制器320指示空闲 的核希望与相邻的核（如由相同线程组占用的其它核）分享存储器带 宽。存储器控制器320又可尝试将相邻的核优先化。这可通过空闲时 间的减少使总系统吞吐量增加。这还可通过降低可能由空闲的核消耗 的静态功率和/或泄露功率来减少系统功耗。

先就绪规则组件810可包括可接收存储器请求460和与存储器请 求460相关的行缓冲器信息840的硬件或硬件和软件的组合。行缓冲 器信息840可指示存储器请求460中的哪些会命中（如主存储器230 的）行缓冲器或未命中行缓冲器。先就绪规则组件810可基于行缓冲 器信息840将存储器请求460优先化，如参考数字850所指示。例如， 先就绪规则组件810可将命中行缓冲器的存储器请求优先于未命中 行缓冲器的存储器请求。

先来到先服务组件820可包括可接收存储器请求460和与存储器 请求460相关的时间信息860的硬件或硬件和软件的组合。时间信息 860可指示存储器请求460到达（如主存储器230）的时间。先来到 先服务组件820可基于时间信息860将存储器请求460优先化，如参 考数字870所指示。例如，先来到先服务组件820可将在时间上更早 到达（如主存储器230）的存储器请求优先于在时间上更晚到达（如 主存储器230）的存储器请求。

如图8进一步所示，组优先化的存储器请求830、行缓冲器优先 化的存储器请求850和/或时间优先化的存储器请求870可形成优先 化的存储器请求490。在一个实施例中，存储器调度器430可首先使 用组排名规则组件800、然后使用先就绪规则组件810、最后使用先 来到先服务规则组件820来调度（如优先化）存储器请求460。

尽管图8示出了存储器调度器430的示例性功能组件，但在其它 实施例中，相对于图8所示，存储器调度器430可包括更少的功能组 件、不同的功能组件、以不同方式布置的功能组件或附加的功能组件。 或者或另外，存储器调度器430的一个或多个功能组件可执行被描述 为由存储器调度器430的一个或多个其它功能组件执行的一个或多 个其它任务。

示例性存储器控制器操作

图9A和图9B是能够由线程组接收器400（图4）执行的示例性 操作900的示意图。如图9A所示，单线程应用910（如APP_A）可 包括与多核处理器（如处理单元220）的核310-1和存储体330-1（未 示出）相关的两个存储器请求920-1和920-2。多线程应用（如APP_B） 可包括两个线程（如APP_B1线程930和APP_B2线程950）和用于 同步的障碍。线程930可与处理单元220的核310-2和存储体330-1 （未示出）相关，可包括在障碍之后提供的两个存储器请求940-6和 940-7，并可包括在障碍之前提供的三个存储器请求940-3、940-4和 940-5。线程950可与处理单元220的核310-3和存储体330-2（未示 出）相关，并可包括在障碍之后提供的两个存储器请求940-1和940-2。

多线程应用APP_B可被设计为通过使线程930访问存储体330-1 且线程950访问存储体330-2来利用存储体级并行。为了解释的目的， 假定由于障碍周围可能的负载不平衡（如其可能由于可能无法实现完 美的运行时负载平衡而发生），线程950在线程930之前到达障碍。 负载不平衡可能阻止与线程950相关的存储器请求940-1和940-2访 问存储体330-2，从而可能使核310-3处于空闲状态。核310-3可能保 持在空闲状态下，直到与线程930相关的存储器请求940-3、940-4 和940-5被处理。因此，与线程930相关的存储器请求940-3、940-4 和940-5应被赋予高于与单线程应用910相关的存储器请求920-1和 920-2的优先级（如使得核310-3仅在三个周期而不是五个周期内保 持空闲）。

如图9B所示，（如存储器控制器320的）线程组接收器400可 接收线程910、930和950（如其对应于线程440）、线程信息510和 组ID信息520。例如，线程组接收器400可接收单线程应用APP_A 的线程910的组ID，并可接收多线程应用APP_B的线程930和950 的另一组ID。线程组接收器400可基于线程信息510和组ID信息520 产生线程910、930和950的线程组信息450-1和450-2。例如，线程 组接收器400可产生线程组信息450-1（如针对单线程应用APP_A的 线程910）和线程组信息450-2（如针对多线程应用APP_B的线程930 和950）。

尽管图9A和图9B示出了能够由线程组接收器400执行的示例 性操作，但在其它实施例中，相对于图9A和图9B所示，线程组接 收器400可执行更少的操作、不同的操作或附加的操作。

图10A和图10B是能够由空闲线程检测器410（图6）执行的示 例性操作1000的示意图。如图10A所示，由于障碍周围可能的负载 不平衡，线程950可在线程930之前到达障碍。负载不平衡可阻止与 线程950相关的存储器请求940-1和940-2访问存储体330-2（未示 出），从而可能使核310-3处于空闲状态，并且可能使线程950空闲， 如参考数字1010所指示。

如图10B所示，空闲线程检测器410的未激活核位向量600可 包括位610-1（如针对核310-1）、位610-2（如针对核310-2）和位610-3 （如针对核310-3）。位610-1可通过未激活核位向量600被重置（如 为零的值），因为位610-1可与来自在对应的核（如核310-1）上执行 的线程（如线程910）的存储器请求920-1和920-1相关。位610-2 可通过未激活核位向量600被重置（如为零的值），因为位610-2可 与来自在对应的核（如核310-2）上执行的线程（如线程930）的存 储器请求940-3、940-4和940-5相关。位610-3可被设置（如为大于 零的值），因为位610-3可不与来自在对应的核（如核310-3）上执行 的线程的存储器请求相关。如果位610-3在时间段620结束时保持被 设置，则未激活核位向量600可确定在对应于位610-3的核（如核 310-3）上执行的线程（如线程950）在时间段620期间空闲，如参考 数字1020所指示。未激活核位向量600可输出空闲线程的指示1020。

尽管图10A和图10B示出了能够由空闲线程检测器410执行的 示例性操作，但在其它实施例中，相对于图10A和图10B所示，空 闲线程检测器410可执行更少的操作、不同的操作或附加的操作。

图11是能够由组排名器420（图7）执行的示例性操作1100的 示意图。如图所示，组排名器420的排名机制700可接收单线程应用 APP_A的位1110和多线程应用APP_B的位1120。位1110可包括位 610-1，如上文结合图10B所述，位610-1可被重置（如为零的值）。 位1120可包括位610-2和位610-3，如上文结合图10B所述，位610-2 可被重置（如为零的值），且位610-3可被设置（如为大于零的值）。

排名机制700可基于与位1110相关的值确定单线程应用APP_A 的排名1130。如图11所示，由于位610-1被设置为零的值，单线程 应用APP_A的排名1130可被确定为零。排名机制700可基于位1120 确定多线程应用APP_B的排名1140。在一个实施例中，排名机制700 可通过将位610-2和位610-3的值相加来确定多线程应用APP_B的 排名1140。如图11所示，由于位610-2被设置为零的值且位610-3 被设置为大于零的值，多线程应用APP_B的排名1140可被确定为大 于零的值。

尽管图11示出了能够由组排名器420执行的示例性操作，但在 其它实施例中，相对于图11所示，组排名器420可执行更少的操作、 不同的操作或附加的操作。

图12A和图12B是能够由存储器调度器430（图8）执行的示例 性操作1200的示意图。如图12A所示，（如单线程应用APP_A的） 线程910可包括请求来自存储体330-1的存储的存储器请求920-1和 920-2。（如多线程应用APP_B的）线程930可包括请求来自存储体 330-1的存储的存储器请求940-3、940-4和940-5。

参照图12B，存储器调度器430的组排名规则组件800可将与线 程930相关的存储器请求940-3、940-4和940-5优先于与线程910相 关的存储器请求920-1和920-2，使得核310-3仅在三个周期而不是 五个周期内保持空闲。如图12B所示，组排名规则组件800可接收 单线程应用APP_A的排名1130和多线程应用APP_B的排名1140， 并可基于排名1130和1140使多线程应用APP_B优先于单线程应用 APP_A，如参考数字1210所指示。例如，参照图12A，（如线程930 的）存储器请求940-3、940-4和940-5可被分别指定存储体330-1的 行1、2和3，而（如线程910的）存储器请求920-1和920-2可被指 定存储体330-1的行4。由于存储体330-1的行1-3在存储体330-1 的行4之前出现，所以存储器请求940-3、940-4和940-5可在存储器 请求920-1和920-2之前被操作。

通过使多线程应用APP_B优先于单线程应用APP_A，存储器控 制器320可将多线程应用APP_B的空闲时间从五个周期（如采用 FRFCFS和PAR-BS机制时就将是这样的情况）减少到三个周期。这 可以改善总体的系统吞吐量，因为核310-3可更早地开始执行有用的 工作。这也可以通过减少可被空闲的核310-3消耗的静态功率和/或泄 露功率来降低系统功耗。

尽管图12A和图12B示出了能够由存储器调度器430执行的示 例性操作，但在其它实施例中，相对于图12A和图12B所示，存储 器调度器430可执行更少的操作、不同的操作或附加的操作。

图13-15是根据本文描述的实施例的用于多线程应用识别存储器 调度的示例性过程1300的流程图。在一个实施例中，过程1300可由 设备200（图2）执行。在另一实施例中，过程1300的部分或全部可 由设备200的一个或多个组件（例如，存储器控制器320）执行。

如图13所示，过程1300可包括接收与第一组相关的多线程应用 的线程（块1310）和接收与第二组相关的单线程应用的线程（块 1320）。例如，在上文结合图4描述的实施例中，存储器控制器320 的线程组接收器400可接收与一个或多个应用相关的一个或多个线 程440，并可产生线程440的线程组信息450-1（如针对由设备200 的操作系统定义的第一线程组）和线程组信息450-2（如针对由设备 200的操作系统定义的第二线程组）。在一个实例中，线程组接收器 400可产生单线程应用的线程的线程组信息450-1（例如，如由操作 系统所定义的），并可产生多线程应用的线程的线程组信息450-2（例 如，如由操作系统所定义的）。

如图13进一步所示，过程1300可包括确定第一组和第二组中的 空闲线程的数量（块1330）。例如，在上文结合图4描述的实施例中， 存储器控制器320的空闲线程检测器410可接收来自线程组接收器 400的线程组信息450-1和450-2，并可接收与线程440相关的一个 或多个存储器请求460。空闲线程检测器410可基于线程组信息 450-1/450-2和存储器请求460确定线程440中的哪些线程是空闲的， 并可将所确定的空闲线程提供到组排名器420，如参考数字470所指 示。

返回到图13，过程1300可包括基于所确定的空闲线程的数量对 第一组和第二组进行排名（块1340）。例如，在上文结合图4描述的 实施例中，存储器控制器320的组排名器420可接收来自线程组接收 器400的线程组信息450-1和450-2，并可接收来自空闲线程检测器 410的空闲线程470。组排名器420可基于每个线程组中空闲线程470 的数量对（如按线程组信息450-1和450-2所定义的）线程组中的线 程进行排名。组排名器420可将线程组的排名提供到存储器调度器 430，如参考数字480所指示。

如图13中进一步所示，过程1300可包括将来自具有较高排名的 组的存储器请求优先于来自具有较低排名的组的存储器请求（块 1350）。例如，在结合图4描述的实施例中，存储器控制器320的存 储器调度器430可接收来自组排名器420的线程组排名480，并可接 收与线程440相关的一个或多个存储器请求460。存储器调度器430 可基于线程组排名480将存储器请求460优先化，如参考数字490所 指示，并可在设备200中实现经过优先化的存储器请求490。

过程块1330和1340可包括图14中所示的过程块。如图14所示， 过程块1330和1340可包括将位向量中的第一位与第一组中的线程的 部分相关（块1400）、将位向量中的第二位与第一组中的线程的剩余 部分相关（块1410）以及将位向量中的第三位与第二组中的线程相 关（块1420）。例如，在上文结合图6描述的实施例中，存储器控制 器320的未激活核位向量600可基于线程组信息450-1和450-2将位 610中的每个位与线程440之一及其对应的核（如核310之一）相关。 在一个实例中，未激活核位向量600可将位610-1与单线程应用的线 程相关，可将位610-2与多线程应用的第一线程相关，并可将位610-3 与多线程应用的第二线程相关。

如图14进一步所示，过程块1330和1340可包括在时间段开始 时设置位向量中的位（块1430），以及在接收到与一个或多个位相关 的线程的一个或多个存储器请求时重置位向量中的这一个或多个位 （块1440）。例如，在上文结合图6所述的实施例中，未激活核位向 量600可在时间段620开始时定期地设置位610中的每个位（如为特 定的值）。当存在来自在对应的核上执行的（如按线程组信息450-1 和450-2所定义的）线程的存储器请求（如存储器请求460）时，未 激活核位向量600可重置位610中的一个位。在一个实例中，位610-1、 610-2和610-4可与来自在对应的核上执行的线程的存储器请求460 相关。因此，未激活核位向量600可重置位610-1、610-2和610-4。 由于位610-3不与存储器请求相关，所以未激活核位向量600可不重 置位610-3。

返回到图14，过程块1330和1330可包括基于在时间段结束时 在位向量中保留的所设置的位确定空闲线程的数量（块1450），以及 基于在时间段结束时保留的所设置的位的值对第一组和第二组进行 排名（块1460）。例如，在上文结合图6和图7所述的实施例中，如 果位（如位610-3）在时间段620结束时保持被设置，则未激活核位 向量600可确定在对应于位610-3的核上执行的线程在时间段620期 间空闲，如参考数字470所指示。未激活核位向量600可输出空闲线 程的指示470。存储器控制器320的组排名规则组件800可（如从组 排名器420）接收存储器请求460和线程组排名480，并可基于线程 组排名480将存储器请求460优先化，如参考数字830所指示。在一 个实例中，组排名规则组件800可将来自具有较高线程组排名的线程 组的存储器请求优先于来自具有较低线程组排名的线程组的存储器 请求。

过程块1350可包括图15中所示的过程块。如图15所示，过程 块1350可包括基于与存储器请求相关的组排名确定存储器请求的第 一优先级（块1500），基于先就绪规则确定存储器请求的第二优先级 （块1510），以及基于先来到先服务规则确定存储器请求的第三优先 级（块1520）。例如，在上文结合图8描述的实施例中，存储器控制 器320的存储器调度器430可首先使用组排名规则组件800、再使用 先就绪规则组件810、最后使用先来到先服务规则组件820来调度（如 优先化）存储器请求460。

本文描述的系统和/或方法可使设备（如带有多核处理器的设备， 例如个人计算机、膝上型计算机、平板计算机、服务器设备和/或其 它类型的计算或通信设备）的存储器控制器能够识别一个或多个多线 程应用并基于对多线程应用的识别调整或优化用于多线程应用的存 储器调度方案。此类系统和/或方法可防止归因于不充足的存储器调 度的（如设备中的）性能降级。

上文对实施例的描述提供示例和说明，但非旨在穷举或将本发明 限制为所公开的精确形式。按照上文的教导，可进行各种修改和变化， 或者可通过实施本发明获得各种修改和变化。

例如，虽然对于图13-图15描述了很多块，但在其它实施例中可 修改这些块的顺序。此外，可以并行地执行非依赖块。在另一实例中， 本文描述的多个不同的应用和线程仅为了说明目的而提供。

显然，在附图中示出的实施例中，如上文描述的各方面可以软件、 固件和硬件的很多不同形式来实现。用于实现这些方面的实际的软件 代码或专门的控制硬件不应被理解为具有限制性。因此，各方面的操 作和行为是在没有参考特定软件代码的情况下描述的，即应理解可基 于本文的描述来设计软件和控制硬件以实现这些方面。软件也可以包 括用于描述电路及其布置的硬件描述语言(HDL)、Verilog、寄存器传 输级(RTL)、图形数据库系统(GDS)II数据或其它软件。此类软件可存 储在计算机可读介质中并用来配置制造过程，以产生能够以实施本发 明的各方面的方式操作的物理电路。

此外，本文描述的某些实施例可被实现为执行一个或多个功能的 “逻辑”。此逻辑可包括硬件（例如，处理器、ASIC或FPGA）或硬 件和软件的组合。

尽管在权利要求书中陈述和/或在说明书中公开了特征的特定组 合，但这些组合不旨在限制本发明。实际上，这些特征中的很多特征 可以未专门在权利要求书中陈述和/或在说明书中公开的方式组合。

除非明确指出，否则本申请中使用的元件、块或指令不应被理解 为对于本发明是关键的或必不可少的。另外，如本文所使用的，冠词 （“a”）旨在包括一个或多个项目。在仅意指一个项目时，使用术语 “一个”或类似语言。此外，除非明确注明，否则短语“基于”意在 指“至少部分地基于”。