High speed variable length best match look-up in a switching device
    1.
    发明授权
    High speed variable length best match look-up in a switching device 失效
    高速可变长度最佳匹配查找在开关设备

    公开(公告)号:US5909440A

    公开(公告)日:1999-06-01

    申请号:US767576

    申请日:1996-12-16

    IPC分类号: H04L12/56 H04Q11/04 H04J3/24

    摘要: A method and apparatus for looking up a key associated with a packet to determine a route through a routing device, the method including, upon receipt of a key, forward traversing one or more nodes which make up a trie stored in a memory by evaluating at each node traversed a bit in the key as indicated by a bit-to-test indicator associated with each node. A value of the bit in the key determining the path traversed along the trie. The method includes locating an end node having a route and comparing the route to the key. If they match, destination information associated with the end node is outputted to guide the transfer of the packet through the routing device. If they do not match, the trie is traversed backwards to locate a best match for the key.

    摘要翻译: 一种用于查找与分组相关联的密钥以确定通过路由设备的路由的方法和装置,所述方法包括在接收到密钥时,通过在存储器中评估组合存储在存储器中的特征进行向前遍历一个或多个节点 每个节点遍历密钥中的位,如与每个节点相关联的位测试指示符所示。 键中的位的值决定了沿着特里经过的路径。 该方法包括定位具有路由并将路由与密钥进行比较的端节点。 如果匹配,则输出与终端节点相关联的目的地信息,以引导通过路由设备传送分组。 如果它们不匹配,则向后穿过该线索以找到该键的最佳匹配。

    Method and apparatus for testing cache RAM residing on a microprocessor
    2.
    发明授权
    Method and apparatus for testing cache RAM residing on a microprocessor 失效
    用于测试驻留在微处理器上的缓存RAM的方法和装置

    公开(公告)号:US5781721A

    公开(公告)日:1998-07-14

    申请号:US714515

    申请日:1996-09-16

    摘要: An apparatus and method for enabling a cache controller and address and data buses of a microprocessor with an on-board cache to provide a SRAM test mode for testing the on-board cache. Upon assertion of a SRAM test signal to a SRAM test pin on the microprocessor chip, the cache and bus controllers cease normal functionality and permit data to be written to, and read from, individual addresses within the on-board cache as though the on-board cache is simple SRAM. After the chip is reset, standard SRAM tests can then be implemented by reading and writing data to selected cache memory addresses as though the cache memory were SRAM. Upon completion of the tests, the SRAM test signal is deasserted and the cache and bus controllers resume normal operating functionality. A reset signal is then applied to the microprocessor to reinitialize control logic employed within the microprocessor. In this way, cache memory on-board a microprocessor can be tested using standard SRAM testing algorithms and equipment thereby eliminating a need for specialized test equipment to test cache memory contained on a microprocessor chip.

    摘要翻译: 一种用于使得高速缓存控制器和具有板上高速缓存的微处理器的地址和数据总线能够提供用于测试车载高速缓存的SRAM测试模式的装置和方法。 在将SRAM测试信号断言给微处理器芯片上的SRAM测试引脚之后,高速缓存和总线控制器停止正常的功能,并允许将数据写入板载缓存中的单个地址并从其读取, 板缓存是简单的SRAM。 芯片复位后,可以通过将数据读取和写入选定的高速缓冲存储器地址来实现标准SRAM测试,就好像高速缓存是SRAM一样。 测试完成后,SRAM测试信号被断言,缓存和总线控制器恢复正常的操作功能。 然后将复位信号施加到微处理器以重新初始化微处理器内采用的控制逻辑。 以这种方式,可以使用标准SRAM测试算法和设备来测试微处理器上的高速缓存,从而无需专门的测试设备来测试包含在微处理器芯片上的高速缓冲存储器。

    Cache memory system with independently accessible subdivided cache tag
arrays
    3.
    发明授权
    Cache memory system with independently accessible subdivided cache tag arrays 失效
    具有可独立访问的细分缓存标签阵列的高速缓存存储器系统

    公开(公告)号:US5675765A

    公开(公告)日:1997-10-07

    申请号:US604687

    申请日:1996-02-21

    IPC分类号: G06F12/08 G06F12/12 G06F13/16

    摘要: Two independently accessible subdivided cache tag arrays and a cache control logic is provided to a set associative cache system. Each tag entry is stored in two subdivided cache tag arrays, a physical and a set tag array such that each physical tag array entry has a corresponding set tag array entry. Each physical tag array entry stores the tag addresses and control bits for a set of cache lines. The control bits comprise at least one validity bit indicating whether the data stored in the corresponding cache line is valid. Each set tag array entry stores the descriptive bits for a set of cache lines which consists of the most recently used (MRU) field identifying the most recently used cache lines of the cache set. Each subdivided tag array is provided with its own interface to enable each array to be accessed concurrently but independently by the cache control logic which performs read and write operations against the cache. The cache control logic makes concurrent and independent accesses to the separate tag arrays to read and write the control and descriptive information in the tag entries. The accesses are grouped by type of operation to be performed and each type of accesses is made during predesignated time slots in an optimized manner to enable the cache control logic to perform certain selected read/write accesses to the physical tag array while performing other selected independent read/write accesses to the set tag array concurrently.

    摘要翻译: 两个独立可访问的细分高速缓存标签阵列和高速缓存控制逻辑被提供给一组联合高速缓存系统。 每个标签条目存储在两个细分高速缓存标签数组中,即物理标签和集合标签数组,使得每个物理标记数组条目都具有相应的集合标签数组条目。 每个物理标签阵列条目存储一组缓存线的标签地址和控制位。 控制位包括至少一个表示存储在对应的高速缓存行中的数据是否有效的有效位。 每个集合标签阵列条目存储用于识别高速缓存集合中最近使用的高速缓存行的最近使用(MRU)字段的一组高速缓存行的描述位。 每个细分标签阵列都提供有自己的接口,以使每个阵列可以同时进行访问,但是独立于对高速缓存执行读写操作的高速缓存控制逻辑。 缓存控制逻辑使对独立标签数组的并发和独立访问能够读取和写入标签条目中的控制和描述信息。 访问按要执行的操作类型进行分组,并且以优化的方式在预定时间段内进行每种类型的访问,以使得高速缓存控制逻辑能够执行对物理标签阵列的某些所选择的读/写访问,同时执行其他选择的独立 同时对set标签数组进行读/写访问。

    Instruction and data cache with a shared TLB for split accesses and
snooping in the same clock cycle
    4.
    发明授权
    Instruction and data cache with a shared TLB for split accesses and snooping in the same clock cycle 失效
    指令和数据缓存与共享TLB在同一时钟周期中进行拆分访问和窥探

    公开(公告)号:US5440707A

    公开(公告)日:1995-08-08

    申请号:US875692

    申请日:1992-04-29

    IPC分类号: G06F12/08 G06F12/10

    CPC分类号: G06F12/1054 G06F12/0831

    摘要: A caching arrangement which can work efficiently in a superscaler and multiprocessing environment includes separate caches for instructions and data and a single translation lookaside buffer (TLB) shared by them. During each clock cycle, retrievals from both the instruction cache and data cache may be performed, one on the rising edge of the clock cycle and one on the falling edge. The TLB is capable of translating two addresses per clock cycle. Because the TLB is faster than accessing the tag arrays which in turn are faster than addressing the cache data arrays, virtual addresses may be concurrently supplied to all three components and the retrieval made in one phase of a clock cycle. When an instruction retrieval is being performed, snooping for snoop broadcasts may be performed for the data cache and vice versa. Thus, for every clock cycle, an instruction and data cache retrieval may be performed as well as snooping.

    摘要翻译: 可以在超标度和多处理环境中有效工作的缓存装置包括用于指令和数据的单独缓存和由它们共享的单个翻译后备缓冲器(TLB)。 在每个时钟周期期间,可以执行从指令高速缓存和数据高速缓存的检索,一个在时钟周期的上升沿,一个在下降沿。 TLB能够每个时钟周期翻译两个地址。 因为TLB比访问标签阵列要快,而是比寻址高速缓存数据阵列更快,所以可以将虚拟地址同时提供给所有三个组件,并在时钟周期的一个阶段进行检索。 当正在执行指令检索时,可以对数据高速缓存执行窥探广播的侦听,反之亦然。 因此,对于每个时钟周期,可以执行指令和数据高速缓存检索以及窥探。

    Cache miss buffer adapted to satisfy read requests to portions of a
cache fill in progress without waiting for the cache fill to complete
    5.
    发明授权
    Cache miss buffer adapted to satisfy read requests to portions of a cache fill in progress without waiting for the cache fill to complete 失效
    高速缓存未命中缓冲器适用于满足对缓存中填充的部分的读取请求,而不等待缓存填充完成

    公开(公告)号:US5353426A

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

    申请号:US875983

    申请日:1992-04-29

    IPC分类号: G06F12/08 G06F13/00

    CPC分类号: G06F12/0859

    摘要: A cache array, a cache tag and comparator unit and a cache multiplexor are provided to a cache memory. Each cache operation performed against the cache array, read or write, takes only half a clock cycle. The cache tag and comparator unit comprises a cache tag array, a cache miss buffer and control logic. Each cache operation performed against the cache tag array, read or write, also takes only half a clock cycle. The cache miss buffer comprises cache miss descriptive information identifying the current state of a cache fill in progress. The control logic comprises a plurality of combinatorial logics for performing tag match operations. In addition to standard tag match operations, the control logic also conditionally tag matches an accessing address against an address tag stored in the cache miss buffer. Depending on the results of the tag match operations, and further depending on the state of the current cache fill if the accessing address is part of the memory block frame of the current cache fill, the control logic provides appropriate signals to the cache array, the cache multiplexor, the main memory and the instruction/data destination. As a result, subsequent instruction/data requests that are part of a current cache fill in progress can be satisfied without having to wait for the completion of the current cache fill, thereby further reducing cache miss penalties and function unit idle time.

    摘要翻译: 缓存阵列,缓存标签和比较器单元以及高速缓存多路复用器被提供给高速缓冲存储器。 针对缓存阵列执行的每个缓存操作只读半个时钟周期。 缓存标签和比较器单元包括缓存标签阵列,高速缓存未命中缓冲器和控制逻辑。 针对缓存标签阵列执行的每个缓存操作,读或写也只需要半个时钟周期。 高速缓存未命中缓冲器包括识别正在进行的缓存填充的当前状态的缓存未命中描述信息。 控制逻辑包括用于执行标签匹配操作的多个组合逻辑。 除了标准标签匹配操作之外,控制逻辑还有条件地将访问地址与存储在高速缓存未命中缓冲器中的地址标签相匹配。 根据标签匹配操作的结果,如果访问地址是当前高速缓存填充的存储器块帧的一部分,则进一步取决于当前缓存填充的状态,控制逻辑向缓存阵列提供适当的信号, 缓存多路复用器,主存储器和指令/数据目的地。 结果,可以满足作为当前缓存的一部分的后续指令/数据请求,而不必等待当前高速缓存填充的完成,从而进一步减少高速缓存未命中处罚和功能单元空闲时间。

    Multiple bank column redundancy intialization controller for cache RAM
    6.
    发明授权
    Multiple bank column redundancy intialization controller for cache RAM 失效
    用于缓存RAM的多列列冗余初始化控制器

    公开(公告)号:US5537665A

    公开(公告)日:1996-07-16

    申请号:US518659

    申请日:1995-08-24

    CPC分类号: G11C29/76

    摘要: An apparatus and method for controlling the initialization of shifting circuitry which provides column redundancy for multiple banks of cache memory on-board a microprocessor. Upon sensing deassertion of a reset signal, a master controller supplies non-overlapping two phase clock signals to one bank controller for each bank of the cache memory. Each bank has a set of fuses which supply a bank shift location to the bank controller indicating the location of a bad column in the bank. The master controller also activates a pre-loadable counter which provides each bank controller with a signal which counts down to zero from half the maximum number of columns in a bank. Each bank controller then provides the shifting signals necessary to initialize the shifting circuitry for its bank. In this way, defective columns located in different positions in each bank can be replaced by redundant paths, thereby repairing the cache and increasing the manufacturing yield of microprocessors with an on-board cache memory.

    摘要翻译: 一种用于控制移位电路的初始化的装置和方法,其为微处理器上的多组缓存存储器提供列冗余。 在感测到取消复位信号时,主控制器为高速缓冲存储器的每一组提供非重叠的两相时钟信号给一个存储体控制器。 每个银行都有一套保险丝,为银行控制人提供一个银行转账位置,指示银行中一个不良列的位置。 主控制器还激活一个可预加载的计数器,为每个银行控制器提供一个信号,该信号从银行中最大列数的一半倒数为零。 然后,每个银行控制器提供为其银行初始化移位电路所必需的移动信号。 以这种方式,位于每个组中不同位置的缺陷列可以被冗余路径替代,从而修复高速缓存并且通过机载缓存存储器增加微处理器的制造产量。

    Inter-domain latch for scan based design
    7.
    发明授权
    Inter-domain latch for scan based design 失效
    用于基于扫描的设计的域间锁存

    公开(公告)号:US5390190A

    公开(公告)日:1995-02-14

    申请号:US890690

    申请日:1992-05-29

    CPC分类号: G01R31/318552

    摘要: In a sequential logic design having two domains, each having opposing clock edge for its flip-flops, an inter-domain latch is provided for establishing a controllable and observable boundary point for the two domains. The inter-domain latch comprises three multiplexors and three latches. The first multiplexor, the first latch, the second multiplexor, the second latch, the third latch and the third multiplexor are coupled serially. Additionally, the output of the first latch is by-passed to the third multiplexor. The latches either open when the clock pulse is low or when the clock pulse is high. The first and third latches are driven by the same clock pulses, and the second latch is driven by an inverted clock pulse. Scan vectors for the first and second domains are scanned in through the first and second multiplexors respectively. The outputs of the first and second domains are observed at the second latch and the third multiplexor respectively.

    摘要翻译: 在具有两个域的顺序逻辑设计中,每个域具有用于其触发器的相对的时钟沿,提供了域间锁存器,用于建立两个域的可控和可观察的边界点。 域间锁存器包括三个多路复用器和三个锁存器。 第一多路复用器,第一锁存器,第二多路复用器,第二锁存器,第三锁存器和第三多路复用器被串行耦合。 另外,第一锁存器的输出被旁路到第三多路复用器。 当时钟脉冲为低电平或时钟脉冲为高电平时,锁存器打开。 第一和第三锁存器由相同的时钟脉冲驱动,第二锁存器由反相时钟脉冲驱动。 第一和第二域的扫描向量分别通过第一和第二多路复用器进行扫描。 分别在第二锁存器和第三多路复用器处观察第一和第二域的输出。

    Methods and apparatus for implementing a pseudo-LRU cache memory
replacement scheme with a locking feature
    8.
    发明授权
    Methods and apparatus for implementing a pseudo-LRU cache memory replacement scheme with a locking feature 失效
    用于实现具有锁定特征的伪LRU高速缓存存储器替换方案的方法和装置

    公开(公告)号:US5353425A

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

    申请号:US875357

    申请日:1992-04-29

    IPC分类号: G06F12/12 G06F13/14

    CPC分类号: G06F12/126 G06F12/125

    摘要: In a memory system having a main memory and a faster cache memory, a cache memory replacement scheme with a locking feature is provided. Locking bits associated with each line in the cache are supplied in the tag table. These locking bits are preferably set and reset by the application program/process executing and are utilized in conjunction with cache replacement bits by the cache controller to determine the lines in the cache to replace. The lock bits and replacement bits for a cache line are "ORed" to create a composite bit for the cache line. If the composite bit is set the cache line is not removed from the cache. When deadlock due to all composite bits being set will result, all replacement bits are cleared. One cache line is always maintained as non-lockable. The locking bits "lock" the line of data in the cache until such time when the process resets the lock bit. By providing that the process controls the state of the lock bits, the intelligence and knowledge the process contains regarding the frequency of use of certain memory locations can be utilized to provide a more efficient cache.

    摘要翻译: 在具有主存储器和更快的高速缓冲存储器的存储器系统中,提供具有锁定特征的高速缓存存储器替换方案。 在缓存中与每行相关联的锁定位在标签表中提供。 这些锁定位优选地通过执行应用程序/处理来设置和复位,并且由高速缓存控制器结合高速缓存替换位使用以确定要替换的高速缓存中的行。 高速缓存行的锁定位和替换位为“OR”以创建高速缓存行的复合位。 如果复合位置1,高速缓存行不会从缓存中删除。 当由于所有复合位被置位而导致死锁将导致所有替换位被清除。 一条缓存​​线始终保持不可锁定。 锁定位“锁定”高速缓存中的数据行,直到进程重置锁定位为止。 通过提供该过程控制锁定位的状态,可以利用该过程包含关于某些存储器位置的使用频率的智能和知识来提供更有效的缓存。