[go: up one dir, main page]

CN1169045C - 基于跟踪的指令高速缓冲存储 - Google Patents

基于跟踪的指令高速缓冲存储 Download PDF

Info

Publication number
CN1169045C
CN1169045C CNB998164860A CN99816486A CN1169045C CN 1169045 C CN1169045 C CN 1169045C CN B998164860 A CNB998164860 A CN B998164860A CN 99816486 A CN99816486 A CN 99816486A CN 1169045 C CN1169045 C CN 1169045C
Authority
CN
China
Prior art keywords
trace segment
data line
trace
segment
data
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Expired - Fee Related
Application number
CNB998164860A
Other languages
English (en)
Other versions
CN1354852A (zh
Inventor
Rf
R·F·克里克
G·J·欣顿
ն�
M·D·乌普顿
D·J·萨格
C·W·李
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Intel Corp
Original Assignee
Intel Corp
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Intel Corp filed Critical Intel Corp
Publication of CN1354852A publication Critical patent/CN1354852A/zh
Application granted granted Critical
Publication of CN1169045C publication Critical patent/CN1169045C/zh
Anticipated expiration legal-status Critical
Expired - Fee Related legal-status Critical Current

Links

Images

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F9/00—Arrangements for program control, e.g. control units
    • G06F9/06—Arrangements for program control, e.g. control units using stored programs, i.e. using an internal store of processing equipment to receive or retain programs
    • G06F9/30—Arrangements for executing machine instructions, e.g. instruction decode
    • G06F9/38—Concurrent instruction execution, e.g. pipeline or look ahead
    • G06F9/3802—Instruction prefetching
    • G06F9/3808—Instruction prefetching for instruction reuse, e.g. trace cache, branch target cache
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F12/00—Accessing, addressing or allocating within memory systems or architectures
    • G06F12/02—Addressing or allocation; Relocation
    • G06F12/08—Addressing or allocation; Relocation in hierarchically structured memory systems, e.g. virtual memory systems
    • G06F12/0802—Addressing of a memory level in which the access to the desired data or data block requires associative addressing means, e.g. caches
    • G06F12/0875—Addressing of a memory level in which the access to the desired data or data block requires associative addressing means, e.g. caches with dedicated cache, e.g. instruction or stack
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F9/00—Arrangements for program control, e.g. control units
    • G06F9/06—Arrangements for program control, e.g. control units using stored programs, i.e. using an internal store of processing equipment to receive or retain programs
    • G06F9/30—Arrangements for executing machine instructions, e.g. instruction decode
    • G06F9/38—Concurrent instruction execution, e.g. pipeline or look ahead
    • G06F9/3802—Instruction prefetching
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F9/00—Arrangements for program control, e.g. control units
    • G06F9/06—Arrangements for program control, e.g. control units using stored programs, i.e. using an internal store of processing equipment to receive or retain programs
    • G06F9/30—Arrangements for executing machine instructions, e.g. instruction decode
    • G06F9/38—Concurrent instruction execution, e.g. pipeline or look ahead
    • G06F9/3836—Instruction issuing, e.g. dynamic instruction scheduling or out of order instruction execution
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F9/00—Arrangements for program control, e.g. control units
    • G06F9/06—Arrangements for program control, e.g. control units using stored programs, i.e. using an internal store of processing equipment to receive or retain programs
    • G06F9/30—Arrangements for executing machine instructions, e.g. instruction decode
    • G06F9/38—Concurrent instruction execution, e.g. pipeline or look ahead
    • G06F9/3854—Instruction completion, e.g. retiring, committing or graduating
    • G06F9/3858—Result writeback, i.e. updating the architectural state or memory

Landscapes

  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Software Systems (AREA)
  • Physics & Mathematics (AREA)
  • General Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Memory System Of A Hierarchy Structure (AREA)
  • Debugging And Monitoring (AREA)
  • Advance Control (AREA)
  • Executing Machine-Instructions (AREA)

Abstract

一个由数据阵列(14)和控制逻辑(26)组成的高速缓存。数据阵列(14)含有若干数据线；控制逻辑(26)则用来存储数据线中的许多指令跟踪段，其中包括跨越多个数据线的跟踪段。在一个具体实施例中，每个跟踪段含有一个或多个具有一条或多条基本指令块的跟踪段成员；每个跟踪段成员拥有一条数据线；多线跟踪段的数据线是有序组合的(逻辑组合的)。检索多线跟踪段的跟踪段成员时，先确定存有跟踪段的第一跟踪段成员的数据线，然后再根据数据线的逻辑序列组合依次确定存有其余跟踪段成员的其余的数据线。

Description

基于跟踪的指令高速缓冲存储
1. 发明领域
本发明涉及计算机系统领域。更具体地说，本发明涉及指令高速缓存技术。
2. 发明背景
以前，高速缓存的指令是按照其空间关系被存储和组织在一个指令高速缓冲存储器中。典型地，每行高速缓存储存的是在主存储器中空间上彼此相邻的指令。这种空间高速缓存指令的方法至少有一个缺点：不论一个程序的执行从一行高速缓存的中间转移出来还是程序的执行转移到一行高速缓存的中，通常都需要访问多行高速缓存。
在美国专利No.5,381,533中，波莱格(Peleg)和维瑟(weiser)揭示了另一组织高速缓存指令的方法以克服空间存储方式中的上述的缺点以及其它一些缺点。按照波莱格和维瑟的方法，高速缓存指令按照预定的执行顺序被存储和组织起来。那些预定要按序执行的指令的基本块被组织成跟踪段并存储在高速缓存行中，每个高速缓存行有一个跟踪段。如果位于前驱基本块末尾的分支指令被指示已占据的话，则存储于高速缓存行中用以形成跟踪段的相应的后继基本块就是分支目标基本块；否则，后继基本块就是被跳过的基本块。在高速缓存行内的后继基本块，借助第一个基本块的第一条指令的方式，按照定位到第一条指令，顺序被检索。
由于波莱格和维瑟的方法不支持跟踪段跨越多条高速缓存行，所以为定位下一高速缓存行，地址匹配每次只能在存储于某高速缓存行中的指令执行后才能进行。结果，波莱格和维瑟的方法至少存在这样一个缺点：在一段时间内，它能提供给处理器执行单元的指令数是有限的。这种限制对具有非常高的指令执行速率的现代处理器来说，是特别不希望看到的。
麦尔文(Melvin)等人在一篇题为：“在动态预定机中的大原子单元的硬件支持，微程序和微结构第21届年度专题研讨会年报”一文中(1998年11月30日-12月2日，圣迭哥，加里佛尼亚)，建议按执行原子单元来储存和组织高速缓存指令。每一个高速缓存入口(假定是一高速缓存行)是由一个执行原子单元组成。一个执行原子单元是一个最小的微操作码组，处理器可视其为不可分单元来分发。微操作码是由处理器使用的微指令用以实现宏指令。文章还建议用一个填充单元来构造执行原子单元。填充单元用来接收来自预取缓冲器和微操作码发生器的微操作码。至少在下述两个条件下执行原子单元的构造才可终止：第一个是当检测出流控制发生变化时，第二个是当填充单元中不再有足够的空的微操作码存储槽来供下一个宏指令使用时。
麦尔文的方法受到若干缺陷的困扰，至少包括以下缺点：每一个原子执行单元基本上只允许占据一个基本块；而且必须高速缓存一个宏指令的所有被译码的微操作码。如果当宏指令组中包括一些译码后变成大量微操作码的复杂的宏指令时，则所述后一个缺点是特别不希望看到的情况。
于是，人们希望有一种新方法来储存和组织高速缓存指令，包括译码后的微操作码，这种方法应具有波莱格等人和麦尔文等人(的方法)的优点，但又没有他们的缺点。
发明概要
一个高速缓存由一个数据阵列和控制逻辑组成。数据阵列包括许多数据线，而控制逻辑则把许多指令的跟踪段储存在数据线中，其中也包括那些跨越多条数据线的跟踪段。
在一个具体实施例中，每个跟踪段包括一个或多个具有一条或多条基本指令块的跟踪段成员，每一个跟踪段成员占据一条数据线，多线跟踪段的数据线被有序地组合起来(按逻辑组合)。多线跟踪段的跟踪段成员的检索是这样完成的：先定位存有这个跟踪段的第一跟踪段成员的数据线，然后根据数据线的逻辑后继关联定位存有其余跟踪段成员的其余的数据线。在一个具体实施例中，这些指令是宏指令的微操作码。
在一个具体实施例中，为使每一条数据线存储一个跟踪段的第一跟踪段成员需要保留一个存储单元地址。存有一个跟踪段的第一跟踪段成员的数据线是通过与保留的定位地址和存取地址相匹配的地址来定位的。在一个具体实施例中，地址匹配是用地址位的子集来进行的，而且匹配的数据线要被验证是否真的含有被搜寻的第一跟踪段成员。在一个S集N路的具体实施例中，跟踪段成员的存储还需用一个标准来进一步验证，此标准保证所保留的与某数据线集的各路有关的，匹配定位地址子集的地址，如果有，是唯一的。
在一个具体实施例中，在适当的地方，将保留在逻辑方式中顺序结合某跟踪段的每条数据线及其前驱和后继数据线的至少部分控制信息。某个多线跟踪段的后继数据线至少部分依靠这些保留的局部顺序联合的控制信息来定位。在一个S集N路的具体实施例中，在适当的时候，为某个跟踪段的每一条数据线都保留了指引其进入前驱数据线集的一条通路的道路索引，及指引其进入后继数据线集的一条通路的道路索引。此外，还保留了多线跟踪段的后继数据线之间的预定集关系。
在一个具体实施例中，运用了大量数据线终止条件来终止一条数据线中的跟踪段指令的高速缓冲存储，同时继续高速缓冲存储另一条数据线中的跟踪段指令。在一个具体实施例中，也运用了大量跟踪段终止条件来终止作为一个跟踪段的指令的高速缓冲存储，同时继续把指令作为一个新跟踪段来高速缓冲存储。
在一个具体实施例中，控制逻辑包括两个状态机使高速缓冲存储器运行于执行模式和跟踪段建立模式。每一种模式都包括许多操作状态。在跟踪段建立模式下建立跟踪段，随后在执行模式下定位和检索其的成员。
附图的简要描述
本发明将以示范具体实施例的方式(但不是限制)，结合附图加以描述，图中相同的标号表示相似的元素或部件，其中：
图1是一方框图，示出了根据本发明的一个具体实施例的一个高速缓冲存储器的构成和运行；
图2是一方框图，示出了根据一个具体实施例，高速缓存的指令被组织在数据阵列中的方式；
图3-5示出了根据一个具体实施例的标签条目、数据线和微操作码的具体内容；
图6-7是两个状态图，示出了根据一个具体实施例的控制逻辑使高速缓冲存储器运行的方法；
图8-9是一流水线图示，示出了根据一个具体实施例的高速缓存进行读操作的方法；
图10-11是一流水线图示，示出了根据一个具体实施例的用微码定序器进行协调的方法；
图12是一流水线图示，示出了根据一个具体实施例的用下一指令指针(IP)发生电路进行协调的方法；
图13是一流水线图示，示出了根据一个具体实施例的取微操作的方法；
图14是一流水线图示，示出了根据一个具体实施例的高速缓存写操作运作的方法；
图15是一方框图，根据一个具体实施例，示出了当一个跟踪段被写爆时，如何进行尾部维护；以及
图16是一方框图，示出了根据一个具体实施例的适于本发明工作的计算机系统。
发明的详细描述
以下将描述本发明的各个方面。然而，对那些擅长此项技术的人来说，很明显，本发明可以只取其某些方面或取其所有方面来使用。为了说明起见，列出了具体数字、材料和配置，以求对本发明的彻底理解。但是，对于本领域的技术人员来说，同样明显的是，本发明也可以在没有具体细节的情况下被使用。在其他实例中，一些众所周知的特征被省略或简化了，为的是不使本发明模糊不清。
现在，参看图1所示的方框图，它示出了本发明的高速缓冲存储器的一个具体实施例。如图所示本发明的高速缓冲存储器10由数据阵列14和控制逻辑26组成，如图示，它们彼此耦合。对该所示的具体实施例来说，高速缓冲存储器10还进一步包括标签了阵列12，直接抽取器18，以及填充缓冲器20，它们如图所示相互耦合并与上面列举的元素耦合。
象传统的高速缓冲存储器一样，数据阵列14由许多数据线组成，而标签阵列12则由许多对应于数据线的标签条目组成。标签条目和对应的数据线一起形成高速缓冲存储器10的高速缓存行。但是，与传统的高速缓冲存储器不同的是，控制逻辑26控制高速缓冲存储器10来高速缓冲存储数据阵列14中的指令，并通过跟踪段，如：28，其中也包括那些跨越多条数据线的跟踪段来组织高速缓存的指令。每一个跟踪段包含一个或多个跟踪段成员，它们分属于一个或多个指令的基本块；每一个跟踪段成员占据一条数据线，而且多线跟踪段的各数据线被有序地组合(逻辑地组合)起来。多线跟踪段的跟踪段成员的检索是通过先定位存有该多线跟踪段的第一跟踪段成员的数据线，然后再根据数据线的逻辑序列组合(下面将进行更全面的描述)相继找到存有其余跟踪段成员的其余的数据线来完成的。在一个具体实施例中，这些指令被译码成宏指令的微操作码。
本领域的普通技术人员也会意识到：通过跟踪高速缓存指令或译码后的微操作码这种方式，使得一个跟踪段能跨越多条数据线，这样，可以供给处理器的执行单元的指令数将大于以前的技术方法所能承受的速率。而且，由于有了允许多数据线跟踪高速缓冲存储的优点，能够自动展开的程序循环长度将会更长，有效地免除了需要一个编辑器来进行循环展开优化以最大限度的开发处理器的性能。结果，程序产生的代码将更紧凑，从而又导致存储空间和取指时间的节省。
图2进一步详细地示出了本发明的跟踪段28，其在一个典型的4路256集数据阵列14的具体实施例的环境中，数据阵列14存有被译码的宏指令的微操作码的指令。根据下面的描述，本领域的普通技术人员会意识到：其它集的长度组合的高速缓存以及其它非集组合的组织结构也可以用来实施本发明。而且，这些指令可以是任何一种指令。近而，为了便于说明，把一个跟踪段的第一跟踪成员称为跟踪段头；把跟踪段的最后一个跟踪段成员称为跟踪段尾；而把中间跟踪段成员称为跟踪段体。在一个只有两个跟踪段成员的简化情况下，第二个跟踪段成员既是跟踪段体，也是跟踪段尾；在只有一个跟踪段成员的情况下，这个唯一的跟踪段成员同时既是跟踪段头，也是跟踪段体，还是跟踪段尾。
对这个被示出的具体实施例来说，对于存有一个跟踪段的第一跟踪段成员的数据线来说，将保留一个定位地址。存有跟踪段的第一跟踪段成员的数据线将通过与保留的定位地址和访问地址相匹配地址来定位的。而且，地址匹配是用一个地址位的子集来实现的。匹配数据线还要被验证是否该数据线真的含有被搜寻的第一跟踪段成员。此外，跟踪段成员的存储还需用一个标准来进一步验证，此标准保证所保留的与某数据线集的各路有关的，匹配定位地址子集的地址，如果有，是唯一的。
在一个替代的具体实施例中，其它的跟踪段成员也与存储器地址有关。在另一个替代的具体实施例中，地址匹配使用所有地址位来实现。
对该所示具体实施例来说，保留了有序地联合每一条存有跟踪段体或尾的数据线与其逻辑方式下前驱数据线的部分控制信息，同样，也保留了有序地联合存有跟踪段头或体的数据线与其逻辑方式下后继数据线的部分控制信息。多线跟踪段的后继数据线部分地依赖于被保留的部分有序联系控制信息来定位。更具体地说，对每一条存有跟踪段体或尾的数据线来说，都保留了一个引导进入前驱数据线集的通路的道路索引；而对每一条存有跟踪段头或体的数据线来说，都保留了一个引导进入后继数据线集的通路的道路索引。此外，还保留了多线跟踪段的后继数据线之间的预定集关系。
对该所示具体实施例来说，用若干数据线终止条件来终止高速缓冲存储一条数据线中的跟踪段的指令，并继续高速缓冲储存另一条数据线中的跟踪段的指令。而且，还用若干跟踪段终止条件来终止高速缓冲储存作为一个跟踪段的指令，并继续高速缓冲储存作为一个新的跟踪段的指令。
对该所示具体实施例来说，数据线终止条件包括遇到译码后变成“大量”微操作码的“复杂的”宏指令。只有所遇到的复杂宏指令的预定数量的微操作码被存于当前数据线中，下一个宏指令的微操作码将被高速缓冲存储在一条新数据线中。构成“复杂”宏指令的构成取决于应用情况。本领域的普通技术人员会明白，本发明可以用被高速缓冲存储的宏指令的非译码的或全译码的微操作码来实现。
对该所示具体实施例来说，数据线终止条件还包括在每个跟踪段允许的分支微操作码的最大预定界限达到后又遇到一个分支微操作码情况。该分支微操作码将被高速缓冲存储在一条新数据线中。在一个具体实施例中，这个预定界限是2。然而，本领域的普通技术人员会明白：本发明可以用、也可以不用每个跟踪段所允许的分支指令或分支微操作码的最大界限来实现；如果用了，这个界限可以小于或大于2。
对该所示具体实施例来说，数据线终止条件还包括对一个“新的”宏指令的所有微操作码没有足够空间的情况。这个“新的”宏指令的微操作码将被高速缓存在一条替代的新数据线中。换而言之，在该所示具体实施例中，一条宏指令的所有微操作码被高速缓存于同一条数据线中。然而，本领域的普通技术人员会明白：本发明可以由高速缓存在多于一条数据线内的一条宏指令的微操作码来实现。
对该所示具体实施例来说，数据线终止条件还包括填充缓冲器20满了的情况。然而，本领域的普通技术人员会明白：本发明可以用可从填充缓冲器取出的多个填充的数据线来实现。
对改所示具体实施例来说，跟踪段终止条件包括遇到一条间接分支宏指令，或一个调用，或一个返回的情况。但是，本领域的普通技术人员会明白：用一个附加跟踪，本发明可以在每个跟踪段具有一个以上间接分支宏指令、一个调用、和/或一个调用返回情况下实现。
对该所示具体实施例来说，跟踪段终止条件还包括遇到一个转移条件预测失效通告，以及一个中断/异常的情况。
对该所示具体实施例来说，跟踪段终止条件还包括遇到含有大量微操作码的“长运行”跟踪段，其微操作码数超过了预定的所允许的跟踪段最大长度即每个跟踪段的微操作码数。在一个具体实施例中，预定的最大值是64集。但是，正如本领域的普通技术人员将会明白的那样，本发明可以有，也可以没有预定的最大值；如果用了最大值，则这个最大值可以小于或大于64集。
图3进一步详细示出了，根据本发明的标签阵列12中的一个标签条的具体实施例。对该所示具体实施例来说，标签条30含有位36(头)和位38(尾)，为的是表明这条相应的数据线是否是一个跟踪段头和/或一个跟踪段尾。如果以上两位都未设置，那么，相应的数据线为跟踪段体。如果以上两位都被设置，则相应的数据线既是跟踪段体，也是跟踪段头和尾，即：以前描述过的“单成员”的退化情况。对该所示具体实施例来说，标签条30还含有位34(LA)，在相应的数据线是一个跟踪段头时，它用来储存一个线性地址；还含有位32(有效)，用来表示位34是否有效。
对该所示具体实施例来说，标签条30还含有位40(下一路)和位42(前一路)，以便对直接后继跟踪段成员进行有序检索。更具体地说，位40和42规定了后继数据线和前驱数据线的“路”存储单元。对该所示具体实施例来说，检签条30不包括任何表示对后继数据线和前驱数据线进行集识别的位。对该所示具体实施例来说，后继数据线和前驱数据线的集识别总是分别为x+1模S和x-1模S，这里，x是当前数据线的集识别，而S是数据阵列14的集数。在另一个具体实施例中，可能用一些附加位来规定后继和前驱数据线的集识别；换而言之，后继和前驱数据线可以定位于任何集中。
对该所示具体实施例来说，标签条30还含有位48(UIP)，位50(NLIP)，和位56(UIP有效MS PTR)，用来识别下一个微操作码指令指针(UIP)，下一个宏指令线性指令指针(NLIP)和UIP是否有效(MS PTR)。UIP也被用作当遇到复杂宏指令的微操作码时进入只读存储器(ROM)的入口指令指针，当设置此位时，UIP有效地意味着这一事实：高速缓冲储存在相应数据线中的指令由于遇到了一个复杂宏指令而被终止了。在一个具体实施例中，NLIP只为一个跟踪段尾而被保留。在另一个具体实施例中，NLIP为一个跟踪段的头、体、尾而被保留。保留含有各个跟踪段成员的NLIP具有下述优点：当访问这些跟踪段成员时如果需要它时，例如剩余的跟踪段写爆了，不用实时计算它(下面将会更全面的说明)。
每个标签条在相应的数据线放在一起时被建立起来。更具体地说，对在图1中示出的高速缓冲存储器10的具体实施例来说，在相应数据线被建立的同时，填充缓冲器20中的各标签条也被建立了。下面，将更详细地描述各标签条建立的方法和这些域的用法。
图4和图5进一步详细地示出数据阵14中的一条数据线的一个具体实施例。如所示，对所示的具体实施例来说，每一条数据线52含有6个微操作码(uOPs)54。每一个UOP54又含有表示这个UOP是否有效的位58(UOP有效)和分别表示源寄存器、目的寄存器以及UOP码的位70-76(sre0，sre1，dest，和UOP码)。对所示的具体实施例来说，每一个UOP54还含有表示宏指令的指令指针的delta(数值)增量的位60(delta IP)；表示位60所表示的delta指令指针是否有效的位62(delta IP valid)；如果UOP是一个分支微操作码，则规定分支目标地址的位64(Br Tgt)；以及当UOP是一个浮点运行时，表示浮点操作码的位68(FOP code)。对所示的具体实施例来说，这些信息由一个宏指令译码器来提供。这些域的目的和用法在此项技术中是众所周知的。因此不再对它们进行进一步描述。
应当注意的是，一些被描述为存储在标签条30中的信息可以存储在相应的数据线52中；反过来也一样。还应当注意的是，根据不同的设计考虑，每个域的具体位数可以选择，这里规定的位数只是为了易于理解本发明。
现在，返回参看图1，如先前描述的那样，对所示的具体实施例来说，高速缓存10包括直接抽取器18和填充缓冲器20。在UOP54从数据阵14中被读出时，直接抽取器18用来为转移地址计算电路计算分支地址而从UOP54中抽取分支目标线性指令指针(Br Tgt)64。此外，跟踪段头的1个线性指令指针(LA)34(存在对应的标签条30中)也按规定程序发送到这个转移地址计算电路去计算转移地址。除头LA34外，NLIP50被发送到下一个指令指针计算电路去计算下一个指令指针，其输入包括转移地址计算电路的输出。微操作指令指针(UIP)48和Msptr56分别发送到一个微码定序器中来提取复杂宏指令的其余的微操作码uOPs，及一个多路转接器用于在数据阵14和微码定序器输出的uOPs之间进行选择。
当从存储器到译码器、以及从译码器到填充缓冲器20的数据通道的数据宽度小于数据线大小时，填充缓冲器20在数据线发往标签阵12和数据阵14之前，用来按预测执行方向组建数据线。对所示的具体实施例来说，填充缓冲器20包含多个缓冲器以便在同一时间建立多条数据线。填充缓冲器20收集地址、控制信息以及分别存储进标签阵12的标签条中和相应的数据阵14的数据线中的经过译码的微操作码uOPs。
控制逻辑26除了控制标签阵12和数据阵14外，还控制填充缓冲器20的操作。图6和图7示出控制逻辑26操作图1所示高速缓冲存储器的具体实施例的方式。控制逻辑26基本上按两个互补模式中的一个来操作高速缓冲存储器10，一个是图6所示的执行模式，一个是图7中所示的跟踪段建立模式。在一个具体实施例中，两种互补模式相互排斥运行，而在另一个具体实施例中，由于具有用于共享资源的仲裁电路的保障，两种互补模式可以同时运行。在一个具体实施例中，这两种互补模式受两个对应的状态机的控制，一个是执行模式状态机，另一个是跟踪段建立模式状态机。当然，本发明可以用更多或更少的状态机来实现。
执行模式状态机在7种状态中的一种状态下运行：闲置状态78，头查找状态80，体查找状态82，尾状态84，微码定序器(MS)状态86，体缺失状态88和跟踪建立状态90。如图所示，在复位或是执行单元检测到一个uOP转移条件预测失效情况下，执行模式状态机从闲置状态78开始。当控制逻辑26收到宏转移条件预测失效的执行单元发来的通知，或者当它本身检测到取到了一个线性指令指针(LIP)或跟踪段建立条件结束时，执行模式状态机便从闲置状态78转换到头查找状态80。
在头查找状态80，执行模式状态机引起了用与下一个指令指针IP对应的地址查找一个跟踪段头的过程，下一个指令指针IP是由下一个IP计算电路根据为这些跟踪段头维护的存储器地址来提供的。如果在现行查找完成之前，执行单元检测到一个宏转移条件预测失效，那么执行模式状态机将会用一个“新的”下一个IP来重新启动跟踪段查找过程。如果头查找过程进行完毕，那么这个过程将导致高速缓存命中或失效。
如果头查找过程导致高速缓存命中，而且这个跟踪段头不同时是跟踪段尾，而且这个跟踪段头数据线不是以一个复杂宏指令来结尾，那么执行模式状态机会让这个跟踪段头的微操作码被输出到执行单元，并且转换到体查找状态82。如果头查找过程导致高速缓存命中，而跟踪段头又同时是跟踪段尾，而且这个跟踪段的头/尾数据线不是以一个复杂宏指令结尾，那么执行模式状态机会让这个跟踪段头/尾的微操作码被输出到执行单元，并且将状态机转换到尾状态84。如果头查找过程导致高速缓存命中，而这条跟踪段头数据线以一个复杂宏指令结尾，那么执行模式状态机会让这个跟踪段头的微操作码被输出到执行单元，并且状态机转换到MS状态86。如果查找过程导致高速缓存失效，则高速缓存10将状态机转换到跟踪建立状态90。
在体查找状态82，执行模式状态机使下一个跟踪段体被查找。对所示具体实施例来说，如先前所描述的那样，下一个跟踪段体位于路W中集x+1模S的数据线处，其中路W由当前标签条的路位40检索，这里x是现行集，S是数据阵列14的集数，W是被检索的路。在另一个具体实施例中，下一个跟踪段体位于路W中的集Y(由集的标识符位表示)的数据线处，路W由当前标签条的下一个路位40检索。一旦被查找到，执行模式状态机就使跟踪段体的uOPs被输出到执行单元。执行模式状态机保持这一状态并继续使下一个跟踪段体被查找、当找到时使它们的uOPs被输出。只要高速缓存命中，又没有达到跟踪段尾，且没有遇到一条以复杂宏指令结尾的数据线，又没有收到执行单元之一的宏/微转移条件预测失效的通知，上述过程就会继续下去。对所示的具体实施例来说，一条经过译码宏指令的微操作码可能包括一个或多个转移微操作码。
当处理体查找状态82时，如果控制逻辑26被某个执行单元告知检测到一个宏转移条件预测失效时，则执行模式状态机就会中止体查找过程，并转回到头查找状态80。如果体查找过程导致高速缓存命中，而且这条数据线不是以一个复杂宏指令结尾，但是这条数据线是一个跟踪段尾，那么执行模式状态机在这个跟踪段尾的uOPs被输出后转换到尾状态84。如果体查找过程导致高速缓存命中，而且这条数据线以一个复杂宏指令结尾，那么执行模式状态机在这条数据线的uOPs被输出后，转换到微码定序器(MS)状态86。如果体查找过程导致高速缓存失效，则执行模式状态机转换到体“缺失”状态88。
在尾状态84，执行模式状态机无条件地返回头查找状态80。同样，在体“缺失”状态88，执行模式状态机也无条件的返回查找状态80。对所示的具体实施例来说，由于替换数据线目标是被选择的(路径预测，最近最少使用(LRU)，及类似算法)这种方式，跟踪段体可能被另一个跟踪段写爆，所以当查找一个跟踪段体时，有可能得到高速缓存失效的结果。
在MS状态86，执行模式状态机允许微码定序器输出剩余的以复杂宏指令结尾的数据线的uOPs。只要执行模式状态机没有收到某个执行单元检测到了一个宏/微转移条件预测失效的通知，那么它就允许微码定序器这样下去直到所有剩余的uOPs被输出完为止。如果执行模式状态机收到某个执行单元检测到一个宏/微转移条件预测失效的通知，则它就中止这种允许。如果执行模式状态机收到检测到一个宏转移条件预测失效的通知，那么它就转回到头查找状态80。如果执行模式状态机收到检测到一个微转移条件预测失效的通知，那么它就转换回闲置状态78。
然而，如果控制逻辑26收到微码定序器已经完成输出剩余的以复杂宏指令结尾的数据线的uOPs的通知，则如果这条数据线不是一个跟踪段尾的话，那么执行模式状态机就会转换到体查找状态82；如果这条数据线是一个跟踪段尾，则转换到尾状态84。
在跟踪建立状态90，执行模式状态机在检测到一个跟踪段结束条件(由互补的跟踪段建立模式状态机指示)时，则无条件地转换到闲置状态78。[换句话说，执行模式的跟踪建立状态90本质上是一个等待状态。]
跟踪段建立模式状态机在以下7种状态中的一种状态下运行：闲置状态92，取请求状态94，等待uOPs状态96，旁路uOPs状态98，填充缓冲器写入阵列状态100，MS和填充缓冲器写入阵列状态102以及头查找状态104。如图所示，在复位或是执行单元检测到一个宏/微转移条件预测失效情况下，跟踪段建立状态机从闲置状态92开始。当控制逻辑26检测到需要发出一条取指令请求时，即对高速缓存10的访问已导致高速缓存失效时，跟踪段建立模式状态机就从闲置状态92转换到取请求状态94。
在取请求状态94，跟踪段建立模式状态机让一个取指令请求发到一个取指单元，而且它自已转换到等待uOPs状态96。在等待uOPs状态96，跟踪段建立模式状态机保持此状态，直到有效的uOPs被提供给填充缓冲器20。此时，跟踪段建立模式状态机转换到旁路uOPs状态98。在旁路uOPs状态98，跟踪段建立模式状态机将来自填充缓冲器20的有效的uOPs前递到执行单元，并继续这样做下去，直到遇到一个数据线终止条件。如果数据线终止条件是遇到一个复杂宏指令，那么跟踪段建立模式状态机就转换到微码定序器(MS)和填充缓冲器写入标签和数据阵列状态102。对其它的数据线终止条件，如果在填充缓冲器20中建立起来的旁路uOPs不可高速缓冲储存，那么跟踪段建立模式状态机就返回等待uOPs状态96，否则，跟踪段建立模式状态机就从旁路uOPs状态98转换到填充缓冲器写入阵列状态100。
在填充缓冲器写入阵列状态100，完成的数据线被发送到标签和数据阵列12和14中相应的地址。在所示具体实施例中要检索它的话，在数据阵列14中的地址是集x+1模S的各路中的一种的地址。在另一个具体实施例中要检索它的话，在数据阵列14中的地址是一个索引集的各路中的一路的地址。在一个具体实施例中，路通过路预测来选择。或者，可以使用LRU(最近最少使用)法。进一步说，当与寻找跟踪段头的方法匹配的部分地址一起使用时，在保证与集x+1模S(或者一个索引集)的标签地址的子集相匹配的标签是唯一的条件下，LRU方法更为有效。换句话说，如果一个非LRU路具有一个与继任的数据线的标签地址的子集匹配的对应标签，其标签与继任数据线的标签地址的子集相匹配的标签相同，那么就选择非LRU路，而不选LRU路。
当把数据线写进标签和数据阵列12和14时，如果刚被写进数据阵列14的数据线不是跟踪段尾(即：未遇到跟踪结束条件)，则跟踪段建立模式状态机转换回等待uOPs状态96。如果被写的数据线是跟踪段尾，如果下一个线性指令指针(NLIP)未知，则跟踪段建立模式状态机就转换回闲置状态92，否则，跟踪段建立模式状态机就转换到头查找状态104。
在MS和填充缓冲器写入标签和数据阵列状态102，完成的数据线如先前对状态100的描述那样被写进标签和数据阵12和14。但是，跟踪段建立模式状态机并不离开这个状态，直到它接到MS的信号说：复杂宏指令的剩余的微操作码已经全部被输出到执行单元为止。当MS完成输出时，如果被写的数据线不是跟踪段尾(即：未遇到跟踪结束条件)，那么，象在状态100一样，跟踪段建立模式状态机转换到等待uOPs状态96。如果被写的数据线是跟踪段尾，当NLIP未知时，跟踪段建立模式状态机转换到闲置状态92；当NLIP已知时，就转换到头查找状态104。此外，如果控制逻辑26接到通知说某个执行单元已测到一个微操作码转移预测失效，则跟踪段建立模式状态机就转换到闲置状态。
在头查找到状态104，跟踪段建立模式状态机使跟踪段头根据已知的NLIP被查找(通过互补执行模式状态机)。如果查找导致命中(当得到互补执行模式状态机通知时)，则跟踪段建立模式状态机就转换到闲置状态92；否则，跟踪段建立模式状态机金刚石以取请求状态94。如先前描述过的一样，跟踪段建立模式状态机再从取请求状态94转换到其它状态。
现在参看图8-15，此处所示8张流水线图说明一个具体实施例中先前描述的各种操作的流水的各个流水线阶段。这些图将作为参考帮助描述一个具体实施例的先前描述的各项操作的流水线过程。这些操作本身将不再重复描述。可参考先前的描述了解细节。在各图中，用垂直实线表示的时间周期代表一个时钟周期。用垂直虚线表示的时间周期代表一个时钟周期内的一部分。内行人会明白：其它的时间分割或流水线方式，甚至包括非流水线方式、也可以用来完成上面描述的操作。
图8示出一个跟踪段头查找操作的流水线的流水阶段的一个具体实施例。如图所示，当查找一个跟踪段头时，在一个时钟周期的前半段，标签阵列12被访问。内容地址匹配(CAM)查找在这个时钟周期的第一个四分之一时间内执行。对被说明的具体实施例来说，在CAM查找期间，只使用了标签地址位的预定的子集。接着，在时钟周期的第二和第三个四分之一时间内，使用在这个时钟周期的第一个四分之一时间内CAM查找获得的结果，对数据阵列14进行访问。在时钟周期的第三个四分之一时间内，执行对潜在的命中标签条的全标签匹配。然后，根据全标签匹配的结果，在时钟周期的第四个四分之一时间内或者允许被检索的数据输出，或者令其失效。
图9示出非跟踪段头查找，即：跟踪段体/尾查找的流水线的流水阶段的一个具体实施例。如所示，当查找一个跟踪段体/尾时，在时钟周期的前半段，标签阵列12被访问。同时，在时钟周期的第一个四分之一时间内，得到了从前趋跟踪段头/体检索出的路信息。接着，在时钟周期的第2和第3个四分之一时间内，使用得到的路信息和预定的集关系，对数据阵列14进行访问。然后，在时钟周期的第三个四分之一时间内，执行全标签匹配。检索那些可能被写“爆”的跟踪段体/尾。然后，根据全标签匹配结果，在时钟周期的第四个四分之一时间内，或者允许被检索的数据输出，或者令其失效。
图10示出将转换到微码定序器的uOPs输出的流水线的流水阶段的一个具体实施例。在第一个时钟周期的前半段期间，标签阵列12被访问。在第一个时钟周期的后半段，执行对微码定序器转换条件的检测，即：检测当前数据线是否被一个复杂宏指令终断。如果检测到这种情况，则输出uOP的指令指针和一个用来选择被微码定序器输出的uOPs的选择信号。在第二个时钟周期的前半段，微码定序器的只读存储器(ROM)被访问，而且在第二个时钟周期的后半段，执行微码定序器的任何附加处理请求。然后，输出的uOPs被送到第三个时钟周期中的下一个流水阶段。
图11示出微码定序器转换的uOP输出的流水线的流水阶段的一个具体实施例。在第一个时钟周期的前半段，微码定序器的只读存储器(ROM)被访问。在第一个时钟周期的后半段，执行微码定序器的附加处理请求，包括检测转换回去的条件，即：以复杂宏指令终止的数据线的剩余uOPs已被输出。如果转换回去的条件被测到，则微码定序器向高速缓存10输出一个“转回”信号。然后，在第二个时钟周期的前半段，访问标签阵列12，而在第二个时钟周期的后半段，如先前参照图8和图9描述的那样，操作继续进行。
图12示出一个把NLIP输出到下一个指令指针(IP)计算电路去的流水线的流水阶段的具体实施例。如先前描述的那样，在第一个时钟周期的前半段，标签阵列12被访问。在第一个时钟周期的后半段，执行标签匹配等工作，包括检测跟踪结束条件。当检测到跟踪结束条件时，从标签阵列12中检索出的当前标签条的NLIP被输出到下一个指令指针IP计算电路。在第二个时钟周期，“新的”NLIP被返回(如果没有预测转移目标)。
图13示出一个响应高速缓存失效的取请求的流水线的各个流水阶段的具体实施例。如所示，在跟踪头查找致使高速缓存失效的下一个时钟周期中，取请求(称为：需求型)被发出。对所示具体实施例来说，在这下一个时钟周期内，一个指令翻译旁视缓冲区(iTLB)被访问。
图14示出将一个完成的数据线写入数据阵列14的流水线的各流水阶段的一个具体实施例。如所示，在第一个时钟周期，当前集x的LRU路被确定。如先前描述的那样，在一个具体实施例中，LRU路符合一个标准，即确保对一个集中的所有路有唯一的部分标签地址。同时，在第一时钟周期内，当前集x的被选路的集x-1模S的前一路被确定。(注意：如果当前集x的被选路的集x-1模S的前一路非空，它意味着集x的被选路当前正被其它跟踪段使用，它将要被写爆。)如所示，在第二和第三时钟周期内，uOPs被前递并写入数据阵列14。同时，在第二时钟周期内，集x的LRU信息被更新。最后，在第三时钟周期中，集x-1模S中的前一个尾信息被更新。如果对集x的被选路的集x-1模S的下一路非空，那么，对应于集x-1模S的下一集的数据线就被设立为另一个跟踪段的跟踪段尾。在另一个具体实施例中，在第二时钟周期中，一个跟踪段成员被无条件地标定为跟踪段尾，并且在需要时，在第三时钟周期中再改正过来。
图15示出尾维护，并更详细说明“写爆”的情况。图中所示的是两个典型的跟踪段TS1和TS2。为了便于说明，TS1包括跟踪段体102和跟踪段尾104，它们分别储存在集x-2模S，0路以及集x-1模S，0路中；其中TS2则包括跟踪段体106和108、及跟踪段尾110，它们分别储存在集x-2模S，1路、集x-1模S，1路以及集x，1路中。集x、1路被选来储存TS1的一个新的跟踪段尾112。为了将集x、1路与TS1适当地联系起来，如所示，集x和1路的前一路域被修改为索引到0路。集x和1路的尾信息已经设置，所以不需再作改动。如果集x和1路以前未用来储存跟踪段尾，那么就要设置尾信息。
此外，为了正确地将集x和1路的数据线设立为TS1的跟踪段尾，下一路域及储存在集x-1，0路中的TS1的前一个尾的尾信息必须要更新。如图所示，集x-1模S，0路的下一路域被更新为索引1路，而尾信息则被清除。而且，在一个具体实施例中，TS2的控制信息也需更新。如图所示写爆的跟踪段尾110的直接前趋、即：TS2的前一个跟踪段体108被转变成TS2的跟踪段尾108。设置集x-1模S，1路的尾位来完成这一转变。
图16示出一个适于实现本发明的计算机系统的具体实施例。如图所示，典型的计算机系统100中包括本发明中高速缓冲存储器10’的一个具体实施例。此外，这个典型的计算机系统100还包括一个跟转移预测单元102(它包括转移目标地址计算电路以及下一个指令指针(IP)计算电路)，微码定序器104，多路转接器106，执行单元108，指令转移预测单元110，指令表旁视缓冲区(iTLB)112，和译码器114。这些组件如图所示相互耦合。
高速缓冲存储器10’的构成和操作如前所述。其余的组件102-104意在代表技术中已有的这些组件的广泛的类型。在一个具体实施例中，10’和102-104的所有这些组件都被布置在同一个处理器集成电路(芯片)中。在另一些具体实施例中，这些组件可分属于不同的(处理器)芯片。
虽然本发明的方法和装置已用以上列举的具体实施例进行了描述，但内行人会认识到：本发明并不局限于所描述的具体实施例。在附加的权利要求书的精神和范围内的修改和替换也可用于实现本发明。这些描述应被看作是对本说明而不是限制。
至此，跟踪基本指令高速缓冲存储的方法和装置已描述完毕。

Claims (46)

1.一种高速缓存指令的装置，它包括：
a)具有多条数据线的一个数据阵列；和
b)耦合在所述数据阵列上的控制逻辑，它把许多指令的跟踪段，包括跨越多条数据线的跟踪段，存入数据线，还通过将地址匹配于单个位置地址去寻找跨越跟踪段的多条数据线中的每一条。
2.如权利要求1所述的装置，其中，所述控制逻辑用具有一个或多个指令的跟踪段成员构成每个跟踪段，并把每个跟踪段成员存储在数据线中；该控制逻辑进一步以逻辑方式把一多线跟踪段的各数据线顺序地联系起来。
3.如权利要求1所述的装置，其中，所述控制逻辑这样来检索一个多线跟踪段的跟踪段成员：它先找到存有多线跟踪段的第一跟踪段成员的数据线，并检索出这个第一跟踪段成员，然后根据这些数据线的逻辑顺序关系，相继找到存储着其余跟踪段成员的其余数据线，并且当这些跟踪段成员所拥有的数据线被找到时，检索出这些剩余的跟踪段成员。
4.如权利要求3所述的装置，其中，所述控制逻辑维护着与存有跟踪段的第一跟踪段成员的数据线有关的地址，以便进行所述的寻找跟踪段的第一跟踪段成员。
5.如权利要求4所述的装置，其中，
该装置还包括至少部分内容地址匹配电路，而且，
也被耦合到所述至少部分内容地址匹配电路上的控制逻辑，使“至少部分内容地址”与某个与访问地址相联系的维护地址相匹配，以便找到存有跟踪段的第一跟踪段成员的数据线。
6.如权利要求5所述的装置，其中，
所述控制逻辑使部分内容地址与联系访问地址的维护地址相匹配，以便找到存有某个跟踪段的第一跟踪段成员的数据线；并且
该控制逻辑还进一步证实存在某条部分匹配数据线中的这个第一跟踪段成员就是要找的那个第一跟踪段成员。
7.如权利要求1所述的装置，其中，在适当的地方，所述控制逻辑维护每个多线跟踪段的各条数据线的“至少部分控制信息”，用逻辑的方法有序地将这条数据线与它逻辑上的后继数据线联系起来。
8.如权利要求7所述的装置，其中，
所述数据线被组织在S个集的N条路中；并且，
所述控制逻辑维护多线跟踪段的各条数据线的下一路的索引，最后一条数据线除外，以检索直接后继数据线的一条路的位置。
9.如权利要求7所述的装置，其中，
所述数据线被组织在S个集的N条路中；并且，
所述控制逻辑将以个多线跟踪段的后继跟踪段成员存储在后继数据线内，在后继数据线之间维持一种预定的集关系。
10.如权利要求7所述的装置，其中，
所述数据线被组织在S个集的N条路中；而且，
所述控制逻辑维护着多线跟踪段的各个数据线的下一集索引，最后一根数据线除外，以检索直接后继数据线的一个集的位置。
11.如权利要求11所述的装置，其中，在适当的地方，所述控制逻辑维护一个多线跟踪段的每条数据线的“至少部分控制信息”，用逻辑的方法将数据线与它逻辑上的前趋数据线有序的联系起来。
12.如权利要求11所述的装置，其中，
所述数据线被组织在S个集的N条路中；而且，
所述控制逻辑维护着多线跟踪段的的各条数据线的前一路索引，第一数据线除外，以检索直接前趋数据线的一路的位置。
13.如权利要求1所述的装置，其中，所述控制逻辑还进一步维护着与所有所述数据线或其中选出的若干条数据线有关的一个或多个控制信息，用以优化所述装置的性能。
14.如权利要求13所述的装置，其中，所述控制逻辑还进一步维护存储有一个跟踪段的最后跟踪段成员的数据线的下一个指令指针。
15.如权利要求13所述的装置，其中，所述控制逻辑还进一步维护存储着跟踪段成员的每一条数据线的下一个指令指针。
16.如权利要求13所述的装置，其中，所述控制逻辑还进一步维护存储有某个跟踪段的第一跟踪段成员的各条数据线的第一跟踪段成员的指示符。
17.如权利要求13所述的装置，其中，所述控制逻辑还进一步维护存储有某个跟踪段的最后跟踪段成员的各条数据线的最后跟踪段成员的指示符。
18.如权利要求13所述的装置，其中，所述控制逻辑还进一步维护存储有跟踪段成员的各数据线的微操作码指令指针。
19.如权利要求13所述的装置，其中，所述控制逻辑还进一步在适当的地方维护某条数据线的一个转移目标地址。
20.如权利要求1所述的装置，其中，所述控制逻辑能按照多数据线终止条件，终止一个跟踪段的指令在一条数据线中的存储，并且继续该跟踪段的指令在另一条数据线中的存储。
21.如权利要求20所述的装置，其中，所述数据线终止条件包括遇到一个复杂宏指令，其译码后至少有M个微操作码，此处的M等于或大于预定的最大值。
22.如权利要求20所述的装置，其中，所述数据线终止条件包括在预定的每个跟踪段的条件转移微操作码的最大限已达到后，又遇到一个条件转移操作码的情况。
23.如权利要求1所述的装置，其中，所述控制逻辑按照多跟踪段终止条件，终止作为当前跟踪段成员的指令储存，并且继续作为一个新跟踪段成员的指令储存。
24.如权利要求23所述的装置，其中，所述跟踪段终止条件包括遇到一个间接转移宏指令。
25.如权利要求23所述的装置，其中，所述数据线终止条件包括在预定的每个跟踪段的指令的最大限已达到后，又遇到一条指令的情况。
26.如权利要求1所述的装置，其中，所述装置还进一步包括许多缓冲器，用来在将跟踪段成员存入数据线以前，沿预测的执行方向创建跟踪段成员。
27.如权利要求1所述的装置，其中，所述装置还进一步包括一个耦合到数据阵列上的直接提取器，用以提取与其内容正由该数据阵列输出的数据线相关联的转移指令指针。
28.如权利要求1所述的装置，其中，
所述装置进一步包括(c)一个拥有许多对应于数据线的标签条的标签阵列，而且被耦合在所述控制逻辑上；并且，
所述控制逻辑把控制信息存入标签条，以便储存和检索这些跟踪段的跟踪段成员。
29.一种高速缓存指令的方法包括：
a)把第一批一个或多个指令存入第一数据线作为一跟踪段的第一跟踪段成员；
b)存储与包括有第一跟踪段成员的第一数据线相关的地址信息，以便能找到第一数据线并检索第一跟踪段成员；而且
c)把第二批一个或多个指令存入第二数据线作为该跟踪段的第二跟踪段成员；
d)存储除与所述第一数据线相关的地址信息外的关于第二数据线的“至少部分控制信息”，以便在找到第一跟踪段成员时，就能找到第二数据线并检索第二跟踪段成员。
30.如权利要求29所述的方法，其中所述方法还进一步包括：
d)把第三批一个或多个指令存入第三数据线，作为所述跟踪段的第三跟踪段成员；并且
e)存储除与所述第二数据线相关的地址信息外的关于第三数据线的“至少部分控制信息”，以便在检索所述第二跟踪段成员时，就能找到第三数据线并检索第三跟踪段成员。
31.如权利要求30所述的方法，其中(a)，(b)和(d)每项均按照多数据线终止条件被终止。
32.如权利要求30所述的方法，其中(a)，(b)和(d)每项均包括在一个缓冲器中建立所述第一/第二/第三数据线，以沿着预测的执行方向创建跟踪段成员。
33.一种高速缓存指令的方法包括：
a)通过与访问地址匹配的地址来找到存有一跟踪段的第一跟踪段成员的第一数据线，其中访问地址又依赖于被维护的与跟踪段的第一跟踪段成员相关的位置地址；
b)检索第一跟踪段成员以及除地址信息外的关于存有该跟踪段的第二跟踪段成员的第二数据线的第一个“至少部分控制信息”，该“至少部分控制信息”被维护与第一数据线相关；而且
c)不用地址匹配找到第二数据线，并至少部分的依赖于被检索的关于第二数据线的第一个“至少部分控制信息”，检索第二跟踪段成员。
34.如权利要求33所述的方法，其中，(c)进一步包括检索关于存有第三跟踪段的跟踪段成员的第三数据线的第二个“至少部分控制信息”，该第二个“至少部分控制信息”被维护与第二数据线相关；而且，该方法进一步包括：
d)找到第三数据线，并至少部分的依赖于被检索的关于第三数据线的第二个“至少部分控制信息”，检索第三跟踪段成员。
35.如权利要求34所述的方法，其中，(b)，(c)和(d)中的一项或几项进一步包括检索来自微码定序器的宏指令的微操作码。
36.如权利要求33所述的方法，其中(c)包括访问数据阵列中的数据线的某一集的某一路，此处该集的该路是由被检索的关于所述第二数据线的第一个“至少部分控制信息”中的一个路索引进行索引的，而且该集是由预定的第一和第二数据线之间的集关系管理的。
37.如权利要求33所述的方法，其中步骤(c)包括访问数据阵列中的数据线的某一集的某一路，此处该路和该集分别是由被检索的关于所述第二数据线的第一个“至少部分控制信息”的一个路索引和一个集索引进行索引。
38.如权利要求33所述的方法，其中，(a)项所述地址匹配使用所维护的访问地址和位置地址的相应的地址位子集来执行，而且(a)进一步包括验证匹配的数据线是否的确含有正在寻找的第一跟踪段成员。
39.一个高速缓冲存储器装置，包括：
a)使该高速缓冲存储器装置运行于执行一模式的第一状态机，其中，存于许多数据线中的各指令的跟踪段的跟踪段成员被查找并输出；而且
b)使该高速缓冲存储器装置运行于一跟踪段建立模式的第二状态机，该第二状态机独立于且区别于第一状态机，其中，各指令的跟踪段的跟踪段成员被建立并存储在数据线中。
40.如权利要求39所述的高速缓冲存储器装置，其中，当所述高速缓冲存储器装置于执行模式操作时，第一状态机运行该高速缓冲存储器装置于包括跟踪段头查找查状、跟踪段体查找状态和跟踪段尾查找状态等多种状态中的一种状态，来分别查找跟踪段头、跟踪段体和跟踪段尾。
41.如权利要求40所述的高速缓冲存储器装置，其中，所述多种状态中进一步包括用来检索来自微码定序器的宏指令的微操作码的微码定序器查找状态。
42.如权利要求39所述的高速缓冲存储器装置，其中，当运行于所述跟踪段建立模式时，该高速缓冲存储器装置运行于包括将一个跟踪段成员从一个填充缓冲器发送到数据阵列的填充缓冲器发送状态的诸多状态中的一个状态，(在此状态下)第一跟踪段成员沿预测的执行方向被建立。
43.一个处理器包括：
a)一个执行单元；
b)一个耦合执行单元的高速缓冲存储器，该高速缓冲存储器包括一个拥有许多数据线的数据阵列；和控制逻辑，它把包括跨越多条数据线的跟踪段在内的许多指令的跟踪段存入数据线。
44.一个计算机系统包括：
a)一个处理器，它包括一个具有许多数据线的数据阵列的高速缓冲存储器，以及控制逻辑，它把包括跨越多条数据线的跟踪段在内的许多指令的跟踪段存入数据线；以及
b)一个耦合到该处理器的输入/输出组件。
45.一个处理器包括：
a)一个执行单元；和
b)一个耦合到该执行单元的高速缓冲存储器，该高速缓冲存储器具有使其运行于执行模式的第一状态机，其中，存储在许多数据线中的指令的各跟踪段的跟踪段成员被查找到并输出；还有一个用于使高速缓冲存储器运行于跟踪段建立模式的第二状态机，其中，各指令的跟踪段的跟踪段成员被建立并被储存到数据线中，该第二状态机独立于且区别于第一状态机。
46.一个计算机系统包括：
a)一个处理器，它包括一个高速缓冲存储器，该高速缓冲存储器具有使其运行于执行模式的第一状态机，其中，存储在许多数据线中的指令的各跟踪段的跟踪段成员被查找并被输出；还有一个用于使高速缓冲存储器运行于跟踪段建立模式的第二状态机，其中，各指令的跟踪段的跟踪段成员被建立并被存到数据线中，该第二状态机独立于且区别于第一状态机；并且还有
b)一个耦合到该处理器上的输入/输出组件。
CNB998164860A 1997-10-23 1999-01-15 基于跟踪的指令高速缓冲存储 Expired - Fee Related CN1169045C (zh)

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
US08/956,375 US6018786A (en) 1997-10-23 1997-10-23 Trace based instruction caching
PCT/US1999/000959 WO2000042502A1 (en) 1997-10-23 1999-01-15 Trace based instruction caching

Publications (2)

Publication Number Publication Date
CN1354852A CN1354852A (zh) 2002-06-19
CN1169045C true CN1169045C (zh) 2004-09-29

Family

ID=26795369

Family Applications (1)

Application Number Title Priority Date Filing Date
CNB998164860A Expired - Fee Related CN1169045C (zh) 1997-10-23 1999-01-15 基于跟踪的指令高速缓冲存储

Country Status (6)

Country Link
US (1) US6018786A (zh)
EP (1) EP1198747A4 (zh)
JP (1) JP2003509733A (zh)
CN (1) CN1169045C (zh)
AU (1) AU2233099A (zh)
WO (1) WO2000042502A1 (zh)

Cited By (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN101158925B (zh) * 2006-10-04 2010-06-09 国际商业机器公司 用于支持跟踪和标准高速缓存行的同时存储的装置和方法
CN103513958A (zh) * 2012-06-27 2014-01-15 上海芯豪微电子有限公司 高性能指令缓存系统和方法

Families Citing this family (85)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US6185675B1 (en) * 1997-10-24 2001-02-06 Advanced Micro Devices, Inc. Basic block oriented trace cache utilizing a basic block sequence buffer to indicate program order of cached basic blocks
US6513155B1 (en) * 1997-12-12 2003-01-28 International Business Machines Corporation Method and system for merging event-based data and sampled data into postprocessed trace output
US6216206B1 (en) * 1997-12-16 2001-04-10 Intel Corporation Trace victim cache
US6105081A (en) * 1998-06-01 2000-08-15 Advanced Micro Devices, Inc. UART character matching used for address matching on a register-by-register basis
US6339822B1 (en) 1998-10-02 2002-01-15 Advanced Micro Devices, Inc. Using padded instructions in a block-oriented cache
US6442674B1 (en) * 1998-12-30 2002-08-27 Intel Corporation Method and system for bypassing a fill buffer located along a first instruction path
US6185669B1 (en) * 1999-02-18 2001-02-06 Hewlett-Packard Company System for fetching mapped branch target instructions of optimized code placed into a trace memory
US6730023B1 (en) * 1999-10-15 2004-05-04 Hemopet Animal genetic and health profile database management
US8234099B2 (en) * 1999-10-15 2012-07-31 Hemopet Computer program for determining a nutritional diet product for a canine or feline animal
US7548839B2 (en) * 1999-10-15 2009-06-16 Hemopet System for animal health diagnosis
EP1223852A4 (en) 1999-10-15 2007-07-18 W Jean Dodds ANIMAL HEALTH DIAGNOSIS
US6594734B1 (en) * 1999-12-20 2003-07-15 Intel Corporation Method and apparatus for self modifying code detection using a translation lookaside buffer
US6578138B1 (en) 1999-12-30 2003-06-10 Intel Corporation System and method for unrolling loops in a trace cache
US7260684B2 (en) * 2001-01-16 2007-08-21 Intel Corporation Trace cache filtering
US6950924B2 (en) * 2002-01-02 2005-09-27 Intel Corporation Passing decoded instructions to both trace cache building engine and allocation module operating in trace cache or decoder reading state
US20030191893A1 (en) * 2002-04-09 2003-10-09 Miller John Alan Method, system, and apparatus for efficient trace cache
US7103751B1 (en) 2002-06-27 2006-09-05 Intel Corporation Method and apparatus for representation of an address in canonical form
US7941651B1 (en) 2002-06-27 2011-05-10 Intel Corporation Method and apparatus for combining micro-operations to process immediate data
US7010665B1 (en) 2002-06-27 2006-03-07 Intel Corporation Method and apparatus for decompressing relative addresses
US7111148B1 (en) 2002-06-27 2006-09-19 Intel Corporation Method and apparatus for compressing relative addresses
US7124277B2 (en) * 2003-08-22 2006-10-17 Intel Corporation Method and apparatus for a trace cache trace-end predictor
US7133969B2 (en) * 2003-10-01 2006-11-07 Advanced Micro Devices, Inc. System and method for handling exceptional instructions in a trace cache based processor
US8069336B2 (en) * 2003-12-03 2011-11-29 Globalfoundries Inc. Transitioning from instruction cache to trace cache on label boundaries
US20050149709A1 (en) * 2003-12-29 2005-07-07 Intel Corporation Prediction based indexed trace cache
US7457917B2 (en) * 2004-12-29 2008-11-25 Intel Corporation Reducing power consumption in a sequential cache
US7239980B2 (en) * 2005-08-30 2007-07-03 International Business Machines Corporation Method and apparatus for adaptive tracing with different processor frequencies
US8024522B1 (en) 2005-09-28 2011-09-20 Oracle America, Inc. Memory ordering queue/versioning cache circuit
US7987342B1 (en) 2005-09-28 2011-07-26 Oracle America, Inc. Trace unit with a decoder, a basic-block cache, a multi-block cache, and sequencer
US7966479B1 (en) 2005-09-28 2011-06-21 Oracle America, Inc. Concurrent vs. low power branch prediction
US8051247B1 (en) 2005-09-28 2011-11-01 Oracle America, Inc. Trace based deallocation of entries in a versioning cache circuit
US7953961B1 (en) 2005-09-28 2011-05-31 Oracle America, Inc. Trace unit with an op path from a decoder (bypass mode) and from a basic-block builder
US7814298B1 (en) 2005-09-28 2010-10-12 Oracle America, Inc. Promoting and appending traces in an instruction processing circuit based upon a bias value
US7783863B1 (en) 2005-09-28 2010-08-24 Oracle America, Inc. Graceful degradation in a trace-based processor
US8015359B1 (en) * 2005-09-28 2011-09-06 Oracle America, Inc. Method and system for utilizing a common structure for trace verification and maintaining coherency in an instruction processing circuit
US7953933B1 (en) 2005-09-28 2011-05-31 Oracle America, Inc. Instruction cache, decoder circuit, basic block cache circuit and multi-block cache circuit
US7779307B1 (en) 2005-09-28 2010-08-17 Oracle America, Inc. Memory ordering queue tightly coupled with a versioning cache circuit
US7568089B1 (en) 2005-10-26 2009-07-28 Sun Microsystems, Inc. Flag management in processors enabled for speculative execution of micro-operation traces
US7949854B1 (en) 2005-09-28 2011-05-24 Oracle America, Inc. Trace unit with a trace builder
US7747822B1 (en) 2005-10-31 2010-06-29 Oracle America Inc. Maintaining memory coherency with a trace cache
US8037285B1 (en) 2005-09-28 2011-10-11 Oracle America, Inc. Trace unit
US7849292B1 (en) 2005-09-28 2010-12-07 Oracle America, Inc. Flag optimization of a trace
US8032710B1 (en) 2005-09-28 2011-10-04 Oracle America, Inc. System and method for ensuring coherency in trace execution
US7937564B1 (en) 2005-09-28 2011-05-03 Oracle America, Inc. Emit vector optimization of a trace
US7877630B1 (en) 2005-09-28 2011-01-25 Oracle America, Inc. Trace based rollback of a speculatively updated cache
US8019944B1 (en) 2005-09-28 2011-09-13 Oracle America, Inc. Checking for a memory ordering violation after a speculative cache write
US7870369B1 (en) 2005-09-28 2011-01-11 Oracle America, Inc. Abort prioritization in a trace-based processor
US8499293B1 (en) 2005-09-28 2013-07-30 Oracle America, Inc. Symbolic renaming optimization of a trace
US7676634B1 (en) 2005-09-28 2010-03-09 Sun Microsystems, Inc. Selective trace cache invalidation for self-modifying code via memory aging
US8370576B1 (en) 2005-09-28 2013-02-05 Oracle America, Inc. Cache rollback acceleration via a bank based versioning cache ciruit
US7681019B1 (en) 2005-11-18 2010-03-16 Sun Microsystems, Inc. Executing functions determined via a collection of operations from translated instructions
US7797517B1 (en) 2005-11-18 2010-09-14 Oracle America, Inc. Trace optimization via fusing operations of a target architecture operation set
US20070186049A1 (en) * 2006-02-03 2007-08-09 International Business Machines Corporation Self prefetching L2 cache mechanism for instruction lines
US20080077778A1 (en) * 2006-09-25 2008-03-27 Davis Gordon T Method and Apparatus for Register Renaming in a Microprocessor
US20080215804A1 (en) * 2006-09-25 2008-09-04 Davis Gordon T Structure for register renaming in a microprocessor
US8010745B1 (en) 2006-09-27 2011-08-30 Oracle America, Inc. Rolling back a speculative update of a non-modifiable cache line
US8370609B1 (en) 2006-09-27 2013-02-05 Oracle America, Inc. Data cache rollbacks for failed speculative traces with memory operations
US8386712B2 (en) * 2006-10-04 2013-02-26 International Business Machines Corporation Structure for supporting simultaneous storage of trace and standard cache lines
US7610449B2 (en) * 2006-10-04 2009-10-27 International Business Machines Corporation Apparatus and method for saving power in a trace cache
US7934081B2 (en) * 2006-10-05 2011-04-26 International Business Machines Corporation Apparatus and method for using branch prediction heuristics for determination of trace formation readiness
US20080250206A1 (en) * 2006-10-05 2008-10-09 Davis Gordon T Structure for using branch prediction heuristics for determination of trace formation readiness
US20080114964A1 (en) * 2006-11-14 2008-05-15 Davis Gordon T Apparatus and Method for Cache Maintenance
US20080250207A1 (en) * 2006-11-14 2008-10-09 Davis Gordon T Design structure for cache maintenance
US20080235500A1 (en) * 2006-11-21 2008-09-25 Davis Gordon T Structure for instruction cache trace formation
US20080120468A1 (en) * 2006-11-21 2008-05-22 Davis Gordon T Instruction Cache Trace Formation
US8181005B2 (en) * 2008-09-05 2012-05-15 Advanced Micro Devices, Inc. Hybrid branch prediction device with sparse and dense prediction caches
US8012769B2 (en) * 2008-11-12 2011-09-06 Hemopet Thyroid analyte detection and measurement
US7794954B2 (en) * 2008-11-12 2010-09-14 Hemopet Detection and measurement of thyroid analyte profile
US7799532B2 (en) * 2008-11-12 2010-09-21 Hemopet Detection and measurement of thyroid hormone autoantibodies
US20100151062A1 (en) * 2008-12-16 2010-06-17 Bruno Stefanon Determining nutrients for animals through gene expression
US7873482B2 (en) * 2008-12-16 2011-01-18 Bruno Stefanon Diagnostic system for selecting nutrition and pharmacological products for animals
KR20100084036A (ko) * 2009-01-15 2010-07-23 삼성전자주식회사 소프트웨어의 에러 검출 장치 및 방법
US8621149B2 (en) * 2009-12-23 2013-12-31 Intel Corporation Controlling access to a cache memory using privilege level information
CN103513957B (zh) * 2012-06-27 2017-07-11 上海芯豪微电子有限公司 高性能缓存方法
CN102789483B (zh) * 2012-06-30 2014-12-10 华为技术有限公司 数据验证方法、装置和系统
US9442725B2 (en) * 2013-08-21 2016-09-13 Airwatch Llc Branch trace compression
US10606599B2 (en) * 2016-12-09 2020-03-31 Advanced Micro Devices, Inc. Operation cache
US10185645B2 (en) 2017-03-08 2019-01-22 Microsoft Technology Licensing, Llc Resource lifetime analysis using a time-travel trace
US9959194B1 (en) 2017-03-08 2018-05-01 Microsoft Technology Licensing, Llc Indexing a trace by insertion of memory snapshots for replay responsiveness
US9983978B1 (en) 2017-03-08 2018-05-29 Microsoft Technology Licensing, Llc Querying an indexed time-travel trace
US9934126B1 (en) 2017-03-08 2018-04-03 Microsoft Technology Licensing, Llc Indexing a trace by insertion of reverse lookup data structures
US9940369B1 (en) 2017-03-08 2018-04-10 Microsoft Technology Licensing, Llc Searching an indexed time-travel trace
US9934127B1 (en) 2017-03-08 2018-04-03 Microsoft Technology Licensing, Llc Indexing a trace by insertion of key frames for replay responsiveness
US10282274B2 (en) 2017-06-14 2019-05-07 Microsoft Technology Licensing, Llc Presenting differences between code entity invocations
CN110851073B (zh) * 2018-08-20 2023-06-02 慧荣科技股份有限公司 储存装置及巨集指令的执行方法
CN113795823B (zh) * 2019-02-13 2025-03-14 诺基亚技术有限公司 处理器资源的可编程控制

Family Cites Families (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
AU3776793A (en) * 1992-02-27 1993-09-13 Intel Corporation Dynamic flow instruction cache memory

Cited By (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN101158925B (zh) * 2006-10-04 2010-06-09 国际商业机器公司 用于支持跟踪和标准高速缓存行的同时存储的装置和方法
CN103513958A (zh) * 2012-06-27 2014-01-15 上海芯豪微电子有限公司 高性能指令缓存系统和方法
CN103513958B (zh) * 2012-06-27 2017-01-25 上海芯豪微电子有限公司 高性能指令缓存系统和方法

Also Published As

Publication number Publication date
JP2003509733A (ja) 2003-03-11
CN1354852A (zh) 2002-06-19
EP1198747A4 (en) 2005-03-16
US6018786A (en) 2000-01-25
WO2000042502A1 (en) 2000-07-20
AU2233099A (en) 2000-08-01
EP1198747A1 (en) 2002-04-24

Similar Documents

Publication Publication Date Title
CN1169045C (zh) 基于跟踪的指令高速缓冲存储
US6170038B1 (en) Trace based instruction caching
US6216206B1 (en) Trace victim cache
US5941980A (en) Apparatus and method for parallel decoding of variable-length instructions in a superscalar pipelined data processing system
US6073213A (en) Method and apparatus for caching trace segments with multiple entry points
KR100734529B1 (ko) 밀접하게 결합된 다중 프로세서를 위한 고속의 다중 스레딩
US6611910B2 (en) Method for processing branch operations
JP3412575B2 (ja) 命令履歴キャッシングを使用して推測的に命令を実行する回路、データ処理システム、およびそのための方法
US5381533A (en) Dynamic flow instruction cache memory organized around trace segments independent of virtual address line
US6076144A (en) Method and apparatus for identifying potential entry points into trace segments
CN101878467B (zh) 用于跨越指令高速缓冲存储器线的指令的预解码修复高速缓冲存储器
CN1109967C (zh) 多线程处理器中指令和关联读取请求的后台完成
US5774710A (en) Cache line branch prediction scheme that shares among sets of a set associative cache
CN1429361A (zh) 用于在一个多线程处理器内在多个线程之间划分资源的方法和装置
CN104662520B (zh) 用于管理具有不同高速缓存能力的跨页指令的方法和设备
CN103198026A (zh) 指令高速缓存功耗降低
US7831815B2 (en) Data processing apparatus and method for identifying sequences of instructions
US5893146A (en) Cache structure having a reduced tag comparison to enable data transfer from said cache
CN101223504B (zh) 高速缓存用于多状态处理器的指令
KR100942408B1 (ko) 가변 길이 명령어에 대한 절전 방법 및 장치
JP2008545199A (ja) メモリ内の同じページに対する多数の変換ルックアサイド緩衝器へのアクセスの防止
US7155574B2 (en) Look ahead LRU array update scheme to minimize clobber in sequentially accessed memory
KR100742002B1 (ko) 캐시 메모리 장치, 및 이를 포함하는 프로세서 및 컴퓨터시스템
KR20010108104A (ko) 트레이스 기반의 명령어 캐시
US7711926B2 (en) Mapping system and method for instruction set processing

Legal Events

Date Code Title Description
C10 Entry into substantive examination
SE01 Entry into force of request for substantive examination
C06 Publication
PB01 Publication
C14 Grant of patent or utility model
GR01 Patent grant
CF01 Termination of patent right due to non-payment of annual fee

Granted publication date: 20040929

Termination date: 20160115

EXPY Termination of patent right or utility model