减少处理引擎中的加载-存储冲突惩罚的系统和方法

摘要

一种用于乱序处理引擎的加载-存储冲突检测系统，包括：调度器，向多个指令流水线派遣指令。指令流水线包括当执行推定派遣的加载指令时提供加载有效信号的加载流水线。加载-存储冲突检测系统包括比较逻辑、广播逻辑和阻止逻辑。当推定派遣的加载指令的加载指令虚拟地址与先前派遣的且对应数据尚未准备好的存储指令的至少一个存储指令虚拟地址匹配时，比较逻辑声明清除信号。广播逻辑向调度器广播加载有效信号，以使能依赖于推定派遣的加载指令的任何指令的派遣。当清除信号被声明时，阻止逻辑无效加载有效信号，以避免降低处理性能的加载-存储冲突。

说明书

技术领域

本发明一般涉及一种处理引擎，更具体地涉及一种减少推定的乱序处理 引擎中的加载-存储冲突惩罚的系统和方法。

背景技术

诸如微处理器等的处理引擎执行诸如x86指令集架构等的指令集架构的 指令。在许多这样的引擎中，经常被称为宏指令的、指令集架构的指令首先 被翻译成微指令(或微操作或“μop”)，微指令被发射到将指令派遣到执行单 元的保留站模块。这里，微指令被更一般地简称为“指令”。指令也被发射到 确保指令的按次序退出(retirement)的重排序缓冲器。

乱序(out-of-order，O-O-O)调度器在处理器设计中被广泛使用，并且 提供高性能处理器与他者之间的重要区别。在O-O-O调度器中，基于依赖性 来派遣每个指令，当多个指令分别使用同一寄存器来作为源和目的地时存在 依赖性。此外，一些指令的依赖性难以识别，诸如加载(load)指令和存储 (store)指令的依赖性。这是因为，依赖性不是由于同一寄存器而引起的， 而是由于同一地址而引起的，而该地址是不为调度阶段的调度器所知道的。 所以，一种通常的方法是推定地假设加载指令和存储指令不具有任何冲突。 当后面不幸检测到冲突时，结果是不正确的，清空流水线，并且再次派遣指 令。当指令的推定派遣是不正确的时，指令的清空和重新派遣引起显著的惩 罚(penalty)。

发明内容

根据一个实施例的微处理器包括加载流水线、调度器、地址生成单元和 加载-存储队列。加载流水线包括多个级，包含至少一个操作数级和多个执行 级。调度器向至少一个操作数级派遣加载指令，以由执行级来执行。加载指 令包括推定派遣的加载指令。地址生成单元在推定派遣的加载指令已进行到 执行级之前提供关于推定派遣的加载指令的加载指令虚拟地址。当在加载指 令虚拟地址与至少一个先前派遣的且尚未确定对应存储数据的存储指令的存 储指令虚拟地址之间发生匹配时，加载-存储队列声明清除信号以无效推定派 遣的加载指令。

倘若冲突，诸如当在加载指令虚拟地址与至少一个先前派遣的存储指令 的存储指令虚拟地址之间发生匹配时，清除信号无效推定派遣的加载指令。 以此方式，当清除信号被声明时调度器可以不过早地派遣依赖性指令，否则 相反的是，调度器被配置为调度依赖于投机加载指令的指令的派遣。

在一个实施例中，加载流水线被配置为当推定派遣的加载指令已经进行 到所选择的执行级时声明加载有效信号。提供阻止逻辑(kill logic)，当清除 信号被声明时，阻止逻辑阻止调度器检测到加载有效信号。可以提供广播逻 辑以当加载有效信号被声明时接收和广播加载有效信号，除非清除信号被声 明以无效推定派遣的加载指令。广播逻辑可以包括当清除信号被声明时阻止 广播逻辑广播加载有效信号的阻止逻辑。

加载-存储队列可以包括多个条目，每个用于将推定派遣的加载指令的加 载指令虚拟地址与一个或多个存储指令虚拟地址进行比较。可以为每个条目 提供有效逻辑和适格逻辑，以确保对应的存储指令虚拟地址与早先派遣的且 对应存储数据尚未被确定的存储指令对应。每个条目可以声明初步清除信号， 并且可以提供或(OR)逻辑以当任何一个或多个初步清除信号被声明时声明 清除信号。

为乱序处理引擎公开加载-存储冲突检测系统。处理引擎包括：调度器， 向多个指令流水线派遣指令，其中指令流水线包括当执行推定派遣的加载指 令时提供加载有效信号的加载流水线。加载-存储冲突检测系统包括比较逻 辑、广播逻辑和阻止逻辑。当推定派遣的加载指令的加载指令虚拟地址与至 少一个先前派遣的且对应数据尚未准备好的存储指令的至少一个存储指令虚 拟地址匹配时，比较逻辑声明清除信号。广播逻辑向调度器广播加载有效信 号，以使能依赖于推定派遣的加载指令的任何指令的派遣。当在加载有效信 号之前或与其同时声明清除信号时，阻止逻辑无效加载有效信号。

阻止逻辑可以被并入广播逻辑或调度器或二者的任何适当组合中。加载- 存储冲突检测系统可以包括用于存储一个或多个存储指令虚拟地址的存储 器。

减少乱序投机处理引擎中的加载-存储冲突的方法包括：提供关于对应存 储数据尚未准备好的至少一个先前派遣的存储指令中的每一个的存储指令地 址；向加载流水线推定派遣加载指令；在执行推定派遣的加载指令之前确定 关于推定派遣的加载指令的加载指令地址；将加载指令地址与至少一个先前 派遣的存储指令中的每一个的存储指令地址进行比较；当加载指令地址与至 少一个先前派遣的存储指令的存储指令地址匹配时，声明清除信号；在执行 推定派遣的加载指令的同时声明加载有效信号；以及当清除信号也被声明时 无效加载有效信号。

该方法可以包括：向调度器的每个队列广播加载有效信号；以及当也清 除信号也被声明时抑制加载有效信号的广播。该方法可以包括：确定至少一 个先前派遣的存储指令中的每一个存储指令地址的有效性。该方法可以包括： 将加载指令地址与多个存储指令地址进行比较，并且当加载指令地址与多个 存储指令地址之一匹配时，声明多个初步清除信号中的对应的一个；并且当 至少一个初步清除信号时被声明时声明清除信号。

附图说明

参照以下描述和附图，将更好地理解本发明的益处、特征和优点，在附 图中：

图1是根据本发明的一个实施例实施的超标量流水线微处理器的简化框 图；

图2是以简化方式描绘根据示出冲突和对应因果关系的传统配置的 O-O-O指令序列相比于顺序执行指令序列的图；

图3是根据一个实施例的接收从图1的保留站中的LD RS Q派遣的指令 的图1的加载流水线以及对应的加载执行级的简化框图；

图4是根据本发明的一个实施例的图3的LoStQ的更具体的框图；以及

图5是根据本发明的一个替换实施例的图4的LoStQ的示范性条目的图。

具体实施方式

发明人已经认识到与因处理引擎内的加载指令的推定派遣而导致的加载 -存储冲突相关联的惩罚。因此，他们开发了一种在加载指令被派遣以执行之 前检测加载-存储冲突的系统和方法。该方法进一步压制或者抑制加载指令的 派遣生效，以防止依赖于该推定派遣的加载指令的其它指令的发射。因为并 不过早地派遣潜在依赖的指令，所以流水线无需被清空并且依赖性指令无需 被重播(replay)。以此方式，与该推定派遣的加载指令相关联的惩罚被减少 或被最小化。加载-存储(Lo-St)队列(LoStQ)结构被加入到检测加载指令 与未准备好完成的任何存储指令之间的冲突的指令流水线中。未准备好完成 的存储指令意指已经确定了地址部分(STA)但是尚未确定数据部分(STD)， 以致存储指令被暂时认为“LoSt”。加载-存储队列LoStQ检测该冲突并发回 一清除信号，以阻止将加载指令的派遣生效广播至保持派遣指令的调度队列。 该清除信号抑制依赖于该推定派遣的加载指令的其它指令的派遣，以提高性 能效率。

图1是根据本发明的一个实施例实施的超标量流水线微处理器100的简 化框图。微处理器100包括：指令高速缓冲存储器102，其高速缓冲存储诸 如x86指令集架构等的指令集架构的宏指令。其它或可替换的指令集架构也 是可以预期的。微处理器100包括：指令翻译器104，其接收宏指令并将其 翻译成微指令。然后，微指令被提供到寄存器别名表(RAT)106，RAT 106 产生微指令的依赖性并按照程序次序向保留站108发射微指令，并经由指令 路径107向重排序缓冲器(ROB)110发射微指令。从RAT 106发射的微指 令(ISSUE INST)通常可以被称为微指令，但是这里更一般地被简化为“指 令”。ROB 110存储关于从RAT 106发射的每个指令的条目。保留站108将指 令派遣到多个执行单元112中合适的一个。

执行单元112可以包括：一个或多个整数执行单元，诸如整数算法/逻辑 单元(ALU)114等；一个或多个浮点执行单元116，诸如包含诸如MMX和 SSE单元的单指令多数据(SIMD)执行单元等；存储次序缓冲器(MOB) 118等。MOB 118通常将存储器类型的指令处理到系统存储器120，MOB 118 诸如包括加载指令执行流水线117和与其相似的存储指令执行流水线119。系 统存储器120可以经由数据高速缓冲存储器(例如，L2数据高速缓冲存储器， 未示出)和总线接口单元(BIU，未示出)与MOB 118对接。执行单元112 将它们的结果提供到ROB 110，这确保指令的按次序退出。

在一个实施例中，保留站108包括多个RS队列，其中，当指令准备好 被执行时，每个RS队列向对应的执行单元112调度并派遣对应发射的指令。 通常，为每个执行单元112提供单独的RS队列。例如，为整数执行单元114 提供RS Q1 122，并且为浮点执行单元116提供RS Q2 124。在一个实施例中， LD RS Q 126向加载流水线117提供加载指令，并且单独的ST RS Q 128向存 储流水线119提供存储指令。保留站108的每个RS Q可以被替代地称为调度 器，其调度向对应的执行单元112派遣所发射的指令的调度逻辑等(未示出)。

图2是以简化方式描绘根据示出冲突和对应因果关系的传统配置的 O-O-O指令序列250相比于顺序执行指令序列200的图。顺序执行序列200 开始于存储指令，该存储指令被划分为存储地址(STA)微指令(μop)202 和之后的存储数据(STD)μop 206，STDμop 206用于利用地址ADD在系统 存储器120中的存储位置204存储数据D。存储μop之后是加载(LD)指令 或LDμop 208，用于将数据从地址ADD处的存储位置204加载到诸如寄存 器等的贮存位置。因为按照正确的次序来执行指令，所以到执行LDμop 208 时在存储位置204存储了正确的数据D，从而通过加载正确的数据D而正确 获得加载结果。

O-O-O指令序列250也开始于STA微操作(μop)202。然而，在该情况 下，因为尚不知道数据D操作数，所以LDμop 208在STDμop 206之前被乱 序(脱离程序次序)派遣。LDμop 208将当前存储在地址ADD的存储位置 204处的数据X加载到所选择的贮存位置，其中，出于实践目的，数据X与 数据D不同。因为数据D尚不可得，所以LDμop 208加载了错误的数据X。 如由箭头210所示，LDμop 208的推定执行被报告回保留站108处的依赖于 LDμop 208的其他依赖性μop，并且这些依赖性μop可以被派遣到对应执行 单元的流水线中以在执行之前取回操作数。最后，如由箭头212所示，加载 μop 208的结果被报告回ROB 110，上述结果包括检测到不正确的加载结果的 “MISS WHY(错过为什么)”或类似其它线程等。响应于此，ROB 110清空 加载流水线117，以去除LDμop 208，并且也清空处理已经派遣的、依赖于 LDμop 208的任何指令的任何其他的执行流水线。此外，如由箭头216所示， 在执行STDμop 206以取回正确的数据D之后，最终必须重播LDμop 208和 对应的依赖性指令。执行流水线的清空以及加载指令和任何依赖性指令的重 播对微处理器100的性能有负面影响。

图3是根据一个实施例的接收从保留站108中的LD RS Q 126派遣的指 令的加载流水线117以及对应的加载执行级的简化框图。保留站108被示出 为包括如前所述的多个RS Q或调度器。加载流水线117被划分为多个相继级， 被示出为D级302、Q级304、R级306、A(I)级308、B级310、C级312、 E1级314和E2级316。通过经由加载流水线117与公共时钟信号(未示出) 同步地传递或传播数据和信息的同步锁存器318的对应集合来分离各级。在 相继级之间绘制垂直虚线和对应的框，以描绘级边界。

级D 302是每个执行单元112的每个流水线都公用的发射级，其中，指 令从RAT 106被发射至保留站108中的调度RS Q。级Q、R和A(I)304、306 和308是操作数级，其中派遣所选择的加载指令以执行，并且在实际执行之 前确定所选择的指令的操作数。其余级B、C、E1和E2是用于执行所派遣的 加载指令的加载执行级。当从级Q处的LD RS Q 126派遣有效的加载指令时， 一个派遣有效信号DV(Q)被声明(asserted)。当该加载指令通过加载流水线 117传播时，每个级产生对应的派遣标签DT(Q)、DT(R)、DT(I)、DT(B)、DT(C)。

在级A(I)308中，选择逻辑320从可能的源(例如，源可能是寄存器、 几个类型的常数中的一个、存储地址等)当中选择用于该加载指令的操作数， 用于确定第一源SRCA和第二源SRCB二者，第一源SRCA和第二源SRCB 被提供到地址产生单元(AGU)322的相应输入。作为选择逻辑320的一个 实施例，第一复用器(MUX)319在可能的源当中进行选择以提供第一源 SRCA，并且第二MUX 321在可能的源当中进行选择以提供第二源SRCB， 第一源SRCA和第二源SRCB二者被提供到AGU 32的输入。AGU 322输出 对应的加载指令虚拟地址(LDVA)以访问系统存储器120。应当明白，LDVA 可以被转换为用于访问系统存储器120的物理地址。应当注意，LDVA可以 仅仅是加载指令的虚拟地址的一部分。例如，12位AGU 322计算与物理地址 的[11:0]一致的[11:0]LDVA。然而，如果[11:0]LDVA与先前派遣的存储数据 尚未确定的存储指令的存储指令虚拟地址(STVA)相同，则LD指令和ST 指令的物理地址很可能相同，物理地址相同意味着检测到加载-存储冲突。在 其他实施例中，将计算和比较更多位的虚拟地址以提高精确度。

示出通过同步锁存器318向级B 310提供LDVA，以启动执行。在级B 310，LDVA的锁存版本被提供到加载-存储队列(LoStQ)326的输入，当LDVA 与先前派遣的存储数据尚未确定的至少一个存储指令的存储指令虚拟地址 (STVA)之间发生匹配时，LoStQ 326产生一个清除信号CLR，该清除信号 CLR用以无效该推定派遣的加载指令。后面将进一步描述LoStQ 326的细节。 在级B 310，加载有效(LV)逻辑325声明加载有效信号LD VALID，LD VALID 信号被提供回级D 302中的广播(BC)逻辑324的输入。BC逻辑324操作 以将LD VALID信号转发或广播到保留站108内的一个或多个甚至所有调度 器RS Q。以此方式，已经发射到保留站108并且依赖于LD指令的任何指令 可以被调动以用于派遣到对应的执行单元。通常，在提供LD VALID信号之 前这些依赖性指令不被派遣，以此确保正确执行。值得注意的是，AGU 322 早在操作数级(例如，级A(I)304)就提供加载指令的LDVA，也就是说，在 该加载指令进入到执行级(例如，级B)以生成LD VALID信号之前，AGU 322 就提供加载指令的LDVA。

来自LoStQ 326的CLR信号被提供回在BC逻辑324内示出的阻止逻辑 328。通常，阻止逻辑328进行操作以防止LD VALID信号被BC逻辑324广 播到保留站108的调度器RS Q。在一个实施例中，单独添加阻止逻辑328来 防止LD VALID信号的广播。在另一个实施例中，BC逻辑324包括并入BC 逻辑324内的禁止逻辑等，其中仅当CLR信号没有被声明来禁止广播时，BC 逻辑324才将LD VALID信号传递到保留站108。

在一个替换实施例中，阻止逻辑328可以在BC逻辑324外部提供，其 中阻止逻辑328基于CLR的状态来传递或阻挡LD VALID信号的广播。在另 一个替换实施例中，阻止逻辑328分布在保留站108的调度RS Q当中。在该 情况下，CLR信号可以改为被提供到保留站108内的每个调度RS Q，在该情 况下，声明CLR信号可防止广播的LD VALID信号改变每个RS Q内的操作 信号、位或值。

通常，当CLR信号在LD VALID之前或者至少与LD VALID同时被声明 时，CLR信号抑制LD VALID信号的声明被检测到。当LD VALID信号被抑 制时，依赖于该推定发射的加载指令的任何指令不会被发射以执行。可以在 稍后重播该加载指令之后执行这些依赖性指令。

图4是根据本发明的一个实施例的LoStQ 326的更具体的框图。如前所 述，AGU 322形成每个加载虚拟地址LDVA并将其传递到级B 310(经由一 组对应的锁存器318)。LoStQ 326包括比较逻辑。LoStQ 326包括各自被标注 为ENTnn的多个条目，其中，“nn”表示条目号。在所示出的实施例中，LoStQ 326包括16个条目ENT00、ENT01、…、ENT15(或ENT00-ENT15)。示出 了第一条目ENT00的细节，其中，应当明白，为了每次比较多达16个虚拟 地址，其余条目ENT01-ENT15中的每一个与第一条目ENT00基本相同。

LoStQ 326接收一个或多个先前派遣的存储数据尚未被确定的存储指令 的虚拟地址。如本领域技术人员所明白的，存储指令被划分为用于确定系统 存储器120的地址的STA μop和用于确定对应的数据值的对应STDμop。在 MOB 118的存储流水线119内处理STA μop和STDμop。在一个实施例中， LoStQ 326只接收对应的STD μop将要被存储流水线119处理的一个或多个 先前派遣的STA μop确定的虚拟地址。在另一个实施例中，LoStQ 326从存储 流水线119接收全部虚拟地址。例如，LD RS Q 126也包括16个条目，其保 持将被派遣到存储流水线119的16个存储指令。在这样的情况下，LoStQ 326 的条目分别与LD RS Q 126的条目对应，并且从存储流水线119接收全部存 储指令虚拟地址(STVA0-STVA15)。如这里进一步描述的，LoStQ 326识别 推定派遣的加载指令的LDVA与任何一个存储指令的虚拟地址之间的冲突。 当检测到冲突时，LoStQ 326声明CLR信号以抑制LD VALID信号被保留站 108检测到，以便防止过早派遣依赖于该推定派遣的加载指令的任何指令。

第一条目ENT00包括：比较器402，将推定派遣的LD指令的虚拟地址 LDVA与第一条目ENT00所接收的STA μop的存储指令虚拟地址STVA0进 行比较。如果虚拟地址相同，则比较器402向与(AND)逻辑404(其中，“&” 表示逻辑与函数)的一个输入声明匹配信号M0。第一条目ENT00也包括： 与逻辑406，从存储流水线119接收指示虚拟地址STVA0是否有效的适格有 效信号QV0。第一条目ENT00也包括：或(OR)逻辑408，从存储流水线 119接收适格条件信号QC0A和QC0B，其中任一适格条件信号被断言为真 (true)，则STVA0有效。适格条件信号QC0A和QC0B被一起进行逻辑或， 然后与QV0进行逻辑与，以确定一个存储有效信号VE0以指示STVA0的有 效性。“有效性”意味着STVA0对应一个比推定性的加载指令更早派遣的存 储指令，并且该存储指令的对应存储数据尚未被确定。VE0被提供到与逻辑 404的另一输入，与逻辑404输出第一条目ENT00的第一清除信号CL0。条 目ENT00-ENT15中的每个输出清除信号CL1-CL15中的对应一个，并且 CL1-CL15被提供到或逻辑410的相应输入，或逻辑410输出CLR信号。

在LoStQ 326的操作中，如果虚拟地址LDVA与分别提供给条目ENT00- ENT15的多达16个存储虚拟地址STVA0-STVA15中的任何有效的一个匹配， 则检测到冲突并且在B级310内声明CLR。如果CLR被声明，则当推定派 遣的加载指令到达B级310并且然后声明LD VALID信号时，阻止逻辑324 抑制或阻挡LD VALID信号的声明被保留站108检测到。以此方式，位于保 留站108的RS队列中的任何一个的、也依赖于该加载指令的任何指令不被 过早派遣以执行。因而，其中已经过早派遣依赖性指令的执行流水线无需被 清空，并且对应的指令无需被重播。最终，按照程序次序非推定地重播该加 载指令，这避免了潜在冲突。如果没有在LD VALID之前或与LD VALID同 时声明CLR，则没有检测到冲突，并且允许执行并完成该推定派遣的加载指 令。

在一个实施例中，可以从存储流水线119直接提供存储虚拟地址 STVA0-STVA15以及对应的适格有效信号QV0-QV15和适格条件信号 QC0A/B-QC15A/B。可替换地，当时序或线程因素可能防止直接接口时，可 以在存储流水线119与LoStQ 326之间提供中间存储设备，诸如寄存器或锁 存器等。可替换地，如图5中的示例性条目ENnn所示，LoStQ 326的条目 ENT00-ENT15中的每个可以包括存储设备502，用于存储存储指令虚拟地址 和适格信号。存储指令虚拟地址和适格信号仍然可以在存储流水线119内生 成，只是被拷贝到存储设备502。存储设备502可以是寄存器或锁存器等。

应当明白，LoStQ 326可能检测并指示实际上并不存在的冲突。在该情 况下，推定派遣加载指令的任何益处将丧失，并且可能由于延迟依赖性指令 而导致轻微的性能下降。无论如何，错误检测的统计发生概率相对较小，因 此检测到实际冲突的性能益处显著胜过因错误检测而导致的轻微性能下降。

已经呈现前述描述以使得本领域普通技术人员能够如在特定应用及其需 求的上下文中提供的那样做出和使用本发明。虽然已经参照其一些优选版本 考虑细节而描述了本发明，但是其他版本和变形是可以的并且可以被预计到。 优选实施例的各种修改对于本领域技术人员来说将是显而易见的，并且这里 所限定的一般原理可以被应用于其他实施例。例如，可以以包括逻辑器件或 电路等的任何适当方式来实施这里所描述的电路。

本领域技术人员应当明白，他们能够容易地使用所公开的概念和特定实 施例来作为设计或修改其他结构的基础，以执行与本发明相同的目的，而不 会背离本发明的精神和范围。因此，本发明不意欲被限制为这里所示出和描 述的特定实施例，而是应当符合与这里公开的原理和新颖性特征一致的最宽 范围。