Digital Equipment Corporation

Compaq Information Technologies Group, L.p.

Compaq Computer Corporation, Inc.

Cadence Design Systems, Inc.

Hewlett-Packard Development Company, L.p.

Harvard College

Rahul Razdan

James B Keller

Richard Eugene Kessler

Derrick R Meyer

Michael D Smith

Stephen R Van Doren

David A Webb, Jr

Gabriel P Bischoff

Solomon J Katzman

Edward J McLellan

Daniel Lawrence Leibholz

Alexander Saldanha

David Arthur James Webb, Jr

Ernst G Ulrich

David A Webb

David J Roberts

Stuart C Rae

Bill Grundmann

Nadim Khalil

Edward John Mclellan

Han-Hsun Chao

Disclosed is a full-chip level verification methodology that combines static timing analysis techniques with dynamic event-driven simulation. The specification discloses a capability to partition a multiple-clock design into various clock domains and surrounding asynchronous regions automatically and to determine the timing of the design on an instance by instance basis. Static timing analysis techniques can be leveraged to verify the synchronous cores of each clock domain. The asynchronous regions of the design and the interaction between synchronous cores of the clock domains are validated using detailed dynamic event-driven simulation without the burden of carrying the interior timing attributes of the synchronous cores that have already been verified.

Method and apparatus for enhancing the performance of event driven dynamic simulation of digital circuits based on netlist partitioning techniques

A method and apparatus for critical and false path verification takes all the potential false paths and captures the conditions that would make them true paths (or false paths) as a Boolean expression (net list), for the combinational logic only. The net list does not have to be at the gate level, but can be a simplified gate level representation because the verification process is only concerned with the logical behavior, not the actual structure. This allows the simulation to execute more quickly. Since the conditions are only captured between register elements, it can be formally proved whether or not the path can be exercised. If no register value can activate the path, then the analysis is done. Otherwise, a simulation is performed to determine whether the register values required to active the condition actually occur. If the Boolean condition can be satisfied, the simulation is performed on the sequential logic to justify those values. If the satisfiability engine fails to finish, then the simulation is run on the combinatinal logic, and an attempt is made to justify the values sequentially as well.

Method and apparatus for critical and false path verification

A computer system includes an external unit governing a cache which generates a set-dirty request as a function of a coherence state of a block in the cache to be modified. The external unit modifies the block of the cache only if an acknowledgment granting permission is received from a memory management system responsive to the set-dirty request. The memory management system receives the set-dirty request, determines the acknowledgment based on contents of the plurality of caches and the main memory according to a cache protocol and sends the acknowledgment to the external unit in response to the set-dirty request. The acknowledgment will either grant permission or deny permission to set the block to the dirty state.

Method and apparatus for developing multiprocessor cache control protocols using an external acknowledgement signal to set a cache to a dirty state

According to the present invention a cache within a multiprocessor system is speculatively filled. To speculatively fill a designated cache, the present invention first determines an address which identifies information located in a main memory. The address may also identify one or more other versions of the information located in one or more caches. The process of filling the designated cache with the information is started by locating the information in the main memory and locating other versions of the information identified by the address in the caches. The validity of the information located in the main memory is determined after locating the other versions of the information. The process of filling the designated cache with the information located in the main memory is initiated before determining the validity of the information located in main memory. Thus, the memory reference is speculative.

Method and apparatus for performing speculative memory fills into a microprocessor

Load/store execution order violations in an out-of-order processor are reduced by determining whether a source address of a load instruction is the same as a destination address of a store instruction on which execution the load instruction depends. If they are the same, then execution of the load instruction is delayed until execution of the store instruction. In an system where virtual registers are mapped to a physical register, the physical registers mapped by the store and load instructions are compared. A table has entries corresponding to instructions in an instruction queue. In each table entry corresponding to a store instruction, the store instruction's destination address offset and physical register reference are saved. A load instruction's source address offset and physical reference are compared with each of the table entries corresponding to store instructions to determine whether a dependency exists. Furthermore, a matrix also has row entries corresponding to instruction queue entries. In addition, each matrix row has a separate indicator for each instruction queue entry. Upon determining that a load instruction is dependent upon a store instruction, the indicator corresponding to the store instruction in the matrix row corresponding to the load instruction is marked, while an indicator is &ldquo;unmarked&rdquo; when the corresponding store instruction issues. Execution of any load instruction is delayed while any indicator in the load instruction's corresponding matrix row is marked. When a store instruction executes, all indicators in the column corresponding to the store instruction are unmarked.

Method and apparatus for delaying the execution of dependent loads

A technique controls memory access requests. The technique involves acquiring a first series of requests including a prefetch request for performing a prefetch operation that prefetches a first set of instructions from a memory, and adding a first entry in a request queue in response to the prefetch request. The first entry identifies the prefetch operation. The technique further involves attempting to retrieve a second set of instructions from a cache to create a cache miss, and generating, in response to the cache miss, a second series of requests including a fetch request for performing a fetch operation that fetches the second set of instructions from the memory to satisfy the cache miss. The technique further involves acquiring the second series of requests that includes the fetch request, and adding a second entry in the request queue in response to the fetch request. The second entry identifies the fetch operation. The technique further involves invalidating the first entry in the request queue when the fetch request is acquired before the prefetch operation initiates, and maintaining the first entry in valid form in the request queue and performing the prefetch operation to completion when the fetch request is acquired after the prefetch operation initiates.

Methods and apparatus for minimizing the impact of excessive instruction retrieval

An architecture which splits primary and secondary cache memory buses and maintains cache hierarchy consistency without performing an explicit invalidation of the secondary cache tag. Two explicit rules are used to determine the status of a block read from the primary cache. In particular, if any memory reference subset matches a block in the primary cache, the associated secondary cache block is ignored. Secondly, if any memory reference subset matches a block in the miss address file, the associated secondary cache block is ignored. Therefore, any further references which subset match the first reference are not allowed to proceed until the fill back to main memory has been completed and the associated miss address file entry has been retired. This ensures that no agent in the host processor or an external agent can illegally use the stale secondary cache data.

Method and apparatus for optimizing bcache tag performance by inferring bcache tag state from internal processor state

A multiprocessor system includes a plurality of processors, each processor having one or more caches local to the processor, and a memory controller connectable to the plurality of processors and a main memory. The memory controller manages the caches and the main memory of the multiprocessor system. A processor of the multiprocessor system is configurable to evict from its cache a block of data. The selected block may have a clean coherence state or a dirty coherence state. The processor communicates a notify signal indicating eviction of the selected block to the memory controller. In addition to sending a write victim notify signal if the selected block has a dirty coherence state, the processor sends a clean victim notify signal if the selected block has a clean coherence state.

Method and apparatus for developing multiprocessor cache control protocols by presenting a clean victim signal to an external system

A memory management system couples processors to each other and to a main memory. Each processor may have one or more associated caches local to that processor. A system port of the memory management system receives a request from a source processor of the processors to access a block of data from the main memory. A memory manager of the memory management system then converts the request into a probe command having a data movement part identifying a condition for movement of the block out of a cache of a target processor and a next coherence state part indicating a next state of the block in the cache of the target processor.

Method and apparatus for developing multiprocessor cache control protocols using a memory management system generating atomic probe commands and system data control response commands

A computing apparatus connectable to a cache and a memory, includes a system port configured to receive an atomic probe command or a system data control response command having an address part identifying data stored in the cache which is associated with data stored in the memory and a next coherence state part indicating a next state of the data in the cache. The computing apparatus further includes an execution unit configured to execute the command to change the state of the data stored in the cache according to the next coherence state part of the command.

Method and apparatus for developing multiprocessor cache control protocols using atomic probe commands and system data control response commands

A processor of a multiprocessor system is configured to transmit a full probe to a cache associated with the processor to transfer data from the stored data of the cache. The data corresponding to the full probe is transferred during a time period. A first tag-only probe is also transmitted to the cache during the same time period to determine if the data corresponding to the tag-only probe is part of the stored data stored in the cache. A stream of probes accesses the cache in two stages. The cache is composed of a tag structure and a data structure. In the first stage, a probe is designated a tag-only probe and accesses the tag structure, but not the data structure, to determine tag information indicating a hit or a miss. In the second stage, if the probe returns tag information indicating a cache hit the probe is designated to be a full probe and accesses the data structure of the cache. If the probe returns tag information indicating a cache miss the probe does not proceed to the second stage.

Method and apparatus for resolving probes in multi-processor systems which do not use external duplicate tags for probe filtering

A data caching system and method includes a data store for caching data from a main memory, a primary tag array for holding tags associated with data cached in the data store, and a duplicate tag array which holds copies of the tags held in the primary tag array. The duplicate tag array is accessible by functions, such as external memory cache probes, such that the primary tag remains available to the processor core. An address translator maps virtual page addresses to physical page address. In order to allow a data caching system which is larger than a page size, a portion of the virtual page address is used to index the tag arrays and data store. However, because of the virtual to physical mapping, the data may reside in any of a number of physical locations. During an internally-generated memory access, the virtual address is used to look up the cache. If there is a miss, other combinations of values are substituted for the virtual bits of the tag array index. For external probes which provide physical addresses to the duplicate tag array, combinations of values are appended to the index portion of the physical address. Tag array lookups can be performed either sequentially, or in parallel.

Method and apparatus for a dedicated physically indexed copy of the data cache tag arrays

A data caching system comprises a hashing function, a data store, a tag array, a page translator, a comparator and a duplicate tag array. The hashing function combines an index portion of a virtual address with a virtual page portion of the virtual address to form a cache index. The data store comprises a plurality of data blocks for holding data. The tag array comprises a plurality of tag entries corresponding to the data blocks, and both the data store and tag array are addressed with the cache index. The tag array provides a plurality of physical address tags corresponding to physical addresses of data resident within corresponding data blocks in the data store addressed by the cache index. The page translator translates a tag portion of the virtual address to a corresponding physical address tag. The comparator verifies a match between the physical address tag from the page translator and the plurality of physical address tags from the tag array, a match indicating that data addressed by the virtual address is resident within the data store. Finally, the duplicate tag array resolves synonym issues caused by hashing. The hashing function is such that addresses which are equivalent mod 2,are pseudo-randomly displaced within the cache. The preferred hashing function maps VA<,XOR,to bits <,of the cache index.

Method and apparatus for minimizing dcache index match aliasing using hashing in synonym/subset processing

A method and apparatus for preventing system wide data dependent stalls is provided. Requests that reach the top of a probe queue and which target data that is not contained in an attached cache memory, are stalled until the data is filled into the appropriate location in cache memory. Only the associated central processor unit's probe queue is stalled and not the entire system. Accordingly, the present invention allows a system to chain together two or more concurrent operations for the same data block without adversely affecting system performance.

Distributed data dependency stall mechanism

A computing apparatus has a mode selector configured to select one of a long-bus mode corresponding to a first memory size and a short-bus mode corresponding to a second memory size which is less than the first memory size. An address bus of the computing apparatus is configured to transmit an address consisting of address bits defining the first memory size and a subset of the address bits defining the second memory size. The address bus has N communication lines each configured to transmit one of a first number of bits of the address bits defining the first memory size in the long-bus mode and M of the N communication lines each configured to transmit one of a second number of bits of the address bits defining the second memory size in the short-bus mode, where M is less than N.

Growing community of inventors

Princeton, MA, United States of America

Rahul Razdan