公开(公告)号：US5584002A

公开(公告)日：1996-12-10

申请号：US21010

申请日：1993-02-22

申请人： Philip G. Emma ,  Joshua W. Knight ,  Keith N. Langston ,  James H. Pomerene ,  Thomas R. Puzak

发明人： Philip G. Emma ,  Joshua W. Knight ,  Keith N. Langston ,  James H. Pomerene ,  Thomas R. Puzak

IPC分类号： G06F12/08 ,  G11C29/00 ,  G06F11/20

CPC分类号： G11C29/88 ,  G06F12/0864

摘要： A method for addressing data in a cache unit which has a plurality of congruence classes, following a failure which disables one or more of the congruence classes in the cache unit. A plurality of synonym classes are established. A subset of the congruence classes is assigned to each of the synonym classes. Any disabled congruence classes are identified. The synonym class to which the disabled congruence class belongs is identified. An alternate congruence class is selected which belongs to the same synonym class as the disabled congruence class. When a request is received by the cache to store a line of data into the disabled congruence class, the line is stored into the alternate congruence class in response to the request.

摘要翻译： 一种用于在具有多个同余类的高速缓存单元中寻址数据的方法，该故障在禁用高速缓存单元中的一个或多个同余类之后。 建立了多个同义词类。 同余类的一个子集被分配给每个同义词类。 确定任何残疾同侪课程。 识别残疾同伴课所属的同义词类。 选择一个替代同余类，属于与残疾同余类相同的同义词类。 当高速缓存接收到请求以将一行数据存储到禁用的同余类中时，响应于请求将该行存储到备用同余类中。

公开(公告)号：US5233702A

公开(公告)日：1993-08-03

申请号：US390587

申请日：1989-08-07

申请人： Philip G. Emma ,  Joshua W. Knight ,  James H. Pomerene ,  Thomas R. Puzak ,  Rudolph N. Rechtschaffen

发明人： Philip G. Emma ,  Joshua W. Knight ,  James H. Pomerene ,  Thomas R. Puzak ,  Rudolph N. Rechtschaffen

IPC分类号： G06F12/08

CPC分类号： G06F12/0862 ,  G06F2212/6024

摘要： A cache memory system develops an optimum sequence for transferring data values between a main memory and a line buffer internal to the cache. At the end of a line transfer, the data in the line buffer is written into the cache memory as a block. Following an initial cache miss, the cache memory system monitors the sequence of data requests received for data in the line that is being read in from main memory. If the sequence being used to read in the data causes the processor to wait for a specific data value in the line, a new sequence is generated in which the specific data value is read at an earlier time in the transfer cycle. This sequence is associated with the instruction that caused the first miss and is used for subsequent misses caused by the instruction. If, in the process of handling a first miss related to a specific instruction, a second miss occurs which is caused by the same instruction but which is for data in a different line of memory, the sequence associated with the instruction is marked as an ephemeral miss. Data transferred to the line buffer in response to an ephemeral miss is not stored in the cache memory and limited to that portion of the line accessed within the line buffer.

公开(公告)号：US5434985A

公开(公告)日：1995-07-18

申请号：US928851

申请日：1992-08-11

申请人： Philip G. Emma ,  Joshua W. Knight ,  James H. Pomerene ,  Thomas R. Puzak

发明人： Philip G. Emma ,  Joshua W. Knight ,  James H. Pomerene ,  Thomas R. Puzak

IPC分类号： G06F9/38

CPC分类号： G06F9/3806 ,  G06F9/3844

摘要： System and method for predicting a multiplicity of future branches simultaneously (parallel) from an executing program, to enable the simultaneous fetching of multiple disjoint program segments. Additionally, the present invention detects divergence of incorrect branch predictions and provides correction for such divergence without penalty. By predicting an entire sequence of branches in parallel, the present invention removes restrictions that decoding of multiple instructions in a superscalar environment must be limited to a single branch group. As a result, the speed of today's superscalar processors can be significantly increased. The present invention includes three main embodiments: (1) the first embodiment is directed to a simplex multibranch prediction device, that can predict a plurality of branch groups in one cycle and provide early detection of wrong predictions; (2) the second embodiments is directed to a duplex multibranch prediction device that can detect divergence in a predicted stream, and provide redirection (correction) within the stream; and (3) the third embodiment is directed to an n-plex multibranch prediction device, that can predict n multiplicity of branch predictions simultaneously and provide an early detection of wrong predictions as well as correction of wrong predictions.

摘要翻译： 用于从执行程序同时（并行）预测多个未来分支的系统和方法，以使得能够同时获取多个不相交的程序段。 此外，本发明检测不正确分支预测的发散，并且对这种发散提供校正而没有惩罚。 通过并行地预测整个分支序列，本发明消除了限制在超标量环境中多个指令的解码必须限于单个分支组的限制。 因此，今天的超标量处理器的速度可以大大提高。 本发明包括三个主要实施例：（1）第一实施例涉及可以在一个周期内预测多个分支组并提供错误预测的早期检测的单工多分支预测装置; （2）第二实施例涉及可以检测预测流中的发散并且在流内提供重定向（校正）的双工多分支预测设备; 和（3）第三实施例涉及n-plex多分支预测装置，其可以同时预测分支预测的多个，并提供错误预测的早期检测以及错误预测的校正。

公开(公告)号：US5197139A

公开(公告)日：1993-03-23

申请号：US505198

申请日：1990-04-05

申请人： Philip G. Emma ,  Joshua W. Knight ,  James H. Pomerene ,  Thomas R. Puzak ,  Rudolph N. Rechtschaffen ,  Frank J. Sparacio

发明人： Philip G. Emma ,  Joshua W. Knight ,  James H. Pomerene ,  Thomas R. Puzak ,  Rudolph N. Rechtschaffen ,  Frank J. Sparacio

IPC分类号： G06F12/08

CPC分类号： G06F12/0817

摘要： A store through cache environment managed exclusively grants exclusivity on a large granularity basis. A cross-invalidate is realized for all changed lines via a single transmission when exclusivity is released. A dynamic table that operates in conjunction with a directory look-aside table (DLAT) determines a number of pages that can be held exclusive simultaneously. For adequate operating speed, the special table must be either fully associative or at least set associative. Alternatively, the table can be incorporated into the DLAT. Each DLAT entry is also extended to include a set of "resident" bits and a "valid nonresident" bit. When exclusively is released, the set of local change bits is broadcast to all processors. Upon receipt of such broadcast, the appropriate action is to change the "valid nonresident" indication to read-only and to clear residence bits whose corresponding local change bit is set.

公开(公告)号：US5353421A

公开(公告)日：1994-10-04

申请号：US91416

申请日：1993-07-13

申请人： Philip G. Emma ,  Joshua W. Knight ,  James H. Po merene ,  Thomas R. Puzak ,  Rudolph N. Rechtschaffen ,  James R. Robinson

发明人： Philip G. Emma ,  Joshua W. Knight ,  James H. Po merene ,  Thomas R. Puzak ,  Rudolph N. Rechtschaffen ,  James R. Robinson

IPC分类号： G06F9/38

CPC分类号： G06F9/3806 ,  G06F9/3848

摘要： A multi-prediction branch prediction mechanism predicts each conditional branch at least twice, first during the instruction-fetch phase of the pipeline and then again during the decode phase of the pipeline. The mechanism uses at least two different branch prediction mechanisms, each a separate and independent mechanism from the other. A set of rules are used to resolve those instances as to when the predictions differ.

摘要翻译： 多预测分支预测机制首先在流水线的指令获取阶段期间至少预测每个条件分支，然后再次在流水线的解码阶段期间。 该机制使用至少两个不同的分支预测机制，每个分离机制与另一个独立的机制相互独立。 使用一组规则来解决这些实例关于预测不同的情况。

公开(公告)号：US5210831A

公开(公告)日：1993-05-11

申请号：US429922

申请日：1989-10-30

申请人： Philip G. Emma ,  Joshua W. Knight ,  James H. Pomerene ,  Rudolph N. Rechtschaffen ,  Frank J. Sparacio

发明人： Philip G. Emma ,  Joshua W. Knight ,  James H. Pomerene ,  Rudolph N. Rechtschaffen ,  Frank J. Sparacio

IPC分类号： G06F9/38

CPC分类号： G06F9/3844

摘要： Methods and apparatus are described for processing branch instructions using a history based branch prediction mechanism (such as a branch history table) in combination with a data dependent branch table (DDBT), where the branch instructions can vary in both outcome and test operand location. The novel methods and apparatus are sensitive to branch mispredictions and to operand addresses used by the DDBT, to identify irrelevant DDBT entries. Irrelevant DDBT entries are identified within the prediction mechanism using state bits which, when set, indicate that: (1) a given entry in the prediction mechanism was updated by the DDBT and (2) subsequent to such update a misprediction occurred making further DDBT updates irrelevant. Once a DDBT entry is determined to be irrelevant, it is prevented from updating the prediction mechanism. The invention also provides methods and apparatus for locating and removing irrelevant entries from the DDBT. The update packet, sent by the DDBT to the history based prediction mechanism, is expanded to include the test operand address actually used by the DDBT. If the state bits indicate the update is irrelevant, then the operand address can be used to locate and delete the offending DDBT entry since the DDBT is organized based on operand addresses. Additionally, the invention provides for inhibiting creation of further DDBT entries when a Branch Wrong Guess event occurs subsequent to a DDBT update to a given prediction mechanism entry.

公开(公告)号：US4991090A

公开(公告)日：1991-02-05

申请号：US51792

申请日：1987-05-18

申请人： Philip G. Emma ,  Joshua W. Knight, III ,  James H. Pomerene ,  Rudolph N. Rechtschaffen ,  Frank J. Sparacio

发明人： Philip G. Emma ,  Joshua W. Knight, III ,  James H. Pomerene ,  Rudolph N. Rechtschaffen ,  Frank J. Sparacio

IPC分类号： G06F9/38 ,  G06F15/16 ,  G06F15/177

CPC分类号： G06F9/3814 ,  G06F9/3802 ,  G06F9/3834

摘要： Monitoring apparatus is provided to allow out-of-sequence fetching of operands while preserving the appearance of in-sequence fetching to the processor of a computer. The key elements include a stack (119) of N entries holding the addresses of the last M, where M is less than or equal to N, out-of-sequence fetches. A comparator (103) is provided for comparing addresses in the stack with a test address. This test address is supplied via an OR gate (107) as either store addresses or cross-invalidate addresses, the latter being for a multiprocessor system. The addresses in the stack that compare with the test address are set as invalid. In addition, all addresses in the stack are set as invalid on the occurrence of a cache miss or serializing instruction. Finally, a select and check entry function (113) associates an address in the stack with the instruction it represents and deletes the address from the stack when the instruction is handled in its proper sequence.

公开(公告)号：US5276882A

公开(公告)日：1994-01-04

申请号：US558998

申请日：1990-07-27

申请人： Philip G. Emma ,  Joshua W. Knight ,  James H. Pomerene ,  Rudolph N. Rechtschaffen ,  Frank J. Sparacio ,  Charles F. Webb

发明人： Philip G. Emma ,  Joshua W. Knight ,  James H. Pomerene ,  Rudolph N. Rechtschaffen ,  Frank J. Sparacio ,  Charles F. Webb

IPC分类号： G06F9/38 ,  G06F9/42

CPC分类号： G06F9/3806 ,  G06F9/30054 ,  G06F9/4426

摘要： Method and apparatus for correctly predicting an outcome of a branch instruction in a system of the type that includes a Branch History Table (BHT) and branch instructions that implement non-explicit subroutine calls and returns. Entries in the BHT have two additional stage fields including a CALL field to indicate that the branch entry corresponds to a branch that may implement a subroutine call and a PSEUDO field. The PSEUDO field represents linkage information and creates a link between a subroutine entry and a subroutine return. A target address of a successful branch instruction is used to search the BHT. The branch is known to be a subroutine return if a target quadword contains an entry prior to a target halfword that has the CALL field set. The entry with the CALL bit set is thus known to be the corresponding subroutine call, and the entry point to the subroutine is given by the target address stored within the entry. A PSEUDO entry is inserted into the BHT at the location corresponding to the entry point of the subroutine, the PSEUDO entry being designated as such by having the PSEUDO field asserted. The PSEUDO entry contains the address of the returning branch instruction in place of the target address field.

摘要翻译： 用于正确预测包括分支历史表（BHT）的类型的系统中的分支指令的结果和实现非显式子程序调用和返回的分支指令的方法和装置。 BHT中的条目具有两个附加的阶段字段，包括CALL字段，以指示分支条目对应于可以实现子程序调用的分支和PSEUDO字段。 PSEUDO字段表示链接信息，并创建子程序条目和子程序返回之间的链接。 成功的分支指令的目标地址用于搜索BHT。 如果目标四字包含有设置了CALL字段的目标半字之前的条目，则该分支被称为子程序返回。 因此，具有CALL位置位的条目是相应的子程序调用，并且子程序的入口点由存储在条目中的目标地址给出。 将PSEUDO条目插入到与子程序的入口点相对应的位置处的BHT中，PSEUDO条目被指定为通过使PSEUDO字段被断言。 PSEUDO条目包含返回分支指令的地址，代替目标地址字段。

公开(公告)号：US5636364A

公开(公告)日：1997-06-03

申请号：US347972

申请日：1994-12-01

申请人： Philip G. Emma ,  Joshua W. Knight, III ,  Thomas R. Puzak

发明人： Philip G. Emma ,  Joshua W. Knight, III ,  Thomas R. Puzak

IPC分类号： G06F12/08 ,  G06F13/14

CPC分类号： G06F12/0806 ,  G06F12/0859

摘要： In a cache-to-memory interface, a means and method for timesharing a single bus to allow the concurrent processing of multiple misses. The multiplicity of misses can arise from a single processor if that processor has a nonblocking cache and/or does speculative prefetching, or it can arise from a multiplicity of processors in a shared-bus configuration.

摘要翻译： 在缓存到存储器接口中，一种用于对单个总线进行时分多路复用以允许并发处理多个未命中的方法和方法。 如果该处理器具有非阻塞高速缓存和/或进行推测性预取，或者可能由共享总线配置中的多个处理器产生，则单个处理器可能会产生多个未命中。

公开(公告)号：US5297281A

公开(公告)日：1994-03-22

申请号：US836193

申请日：1992-02-13

申请人： Philip G. Emma ,  Joshua W. Knight ,  James H. Pomerene ,  Rudolph N. Rechtschaffen ,  Frank J. Sparacio

发明人： Philip G. Emma ,  Joshua W. Knight ,  James H. Pomerene ,  Rudolph N. Rechtschaffen ,  Frank J. Sparacio

IPC分类号： G06F9/38 ,  G06F9/28

CPC分类号： G06F9/3844 ,  G06F9/3853 ,  G06F9/3885

摘要： A digital computer includes a main and an auxiliary pipeline processor which are configured to concurrently execute contiguous groups of instructions taken from a single instruction sequence. The instructions in a sequence may be divided into groups by using either taken-branch instructions or certain instructions which may change the contents of the general purpose registers as group delimiters. Both methods of grouping the instructions use a branch history table to predict the sequence in which the instructions will be executed.

摘要翻译： 数字计算机包括主和辅助流水线处理器，其被配置为同时执行从单个指令序列获取的连续的指令组。 序列中的指令可以通过使用分支指令或某些指令来划分成组，这些指令可以将通用寄存器的内容改变为分组分隔符。 分组指令的两种方法都使用分支历史表来预测指令执行的顺序。