Method and apparatus for increasing capacity of cache directory in multi-processor systems

A method and an apparatus for increasing capacity of cache directory in multi-processor systems, the apparatus comprising a plurality of processor nodes and a plurality of cache memory nodes and a plurality of main memory nodes.

RELATIONSHIP TO OTHER APPLICATIONS

This application claims priority to and the benefit of the following UK application: GB1114620.6, filed 24 Aug. 2011, titled “Method and apparatus for increasing capacity of cache directory in multi-processor systems”. The applicant claims the benefit of the prior application(s) under any and all relevant section(s) of 35 U.S.C. 119(a) through (d) and (f), 172, and 365(a) and (b) and claims priority under rule 37 CFR 1.55. All prior related applications are hereby incorporated by references for all purposes as allowed by law.

FIELD OF THE INVENTION

This invention relates generally to multi-processor systems and more specifically to the field of cache coherency in multi-processor systems.

BACKGROUND

In order to enhance the processing throughput of computer processor systems, processors typically employ a series of cache memory nodes to provide low latency access to blocks of memory stored therein, as compared to the latency to access main memory. The cache memory nodes hold copies of frequently accessed memory blocks from main memory.

In a system with multiple processors and multiple cache memory nodes it is possible that there exist within the system multiple copies of the same memory block. Two examples of such systems are shown inFIGS. 1A and 1B. Systems such as these require a mechanism for keeping the multiple copies of each memory block synchronised, such that when the value stored in a particular copy of a particular memory block in a particular cache memory node is changed, that change is reflected in all other cache memory nodes and main memory nodes in the system that hold a copy of said particular memory block.

Often a coherency protocol, such as Modified, Owned, Shared, Invalid (MOSI), is used to manage such synchronisation, maintaining consistency between cache memory nodes and main memory nodes. One method the coherency protocol may use to accomplish this is to delay the realisation of a change to a value in a cache memory node until it has deleted all other copies of the memory block containing the value from other cache memory nodes in the system, stalling the processor node connected to that cache memory node.

In order for the coherency protocol to function, it needs a way of discovering which memory blocks are stored in each cache memory node in the system. Often a directory node is used to provide the coherency protocol with a list of the memory blocks held in each cache memory node.

As the number of processor nodes in a multi-processor system increases, the directory node becomes a bottleneck, as every memory access performed by any cache memory node in the system needs to reference the directory node, limiting the performance of the system. This in turn limits the maximum number of processors that can operate efficiently in the system. Thus a need exists to increase the capacity of the directory node.

US2003/0005237 provides a processor-cache operational scheme and topology within a multi-processor data processing system having a shared lower level cache (or memory) by which the number of coherency busses is reduced and more efficient snoop resolution and coherency operations with the processor caches are provided. As illustrated inFIG. 2, L2 cache209includes a copy207A′,207B′,207C′ and207D′ of each L1 directory207A,207B,207C and207D. Precise images of L1 directories207A,207B,207C and207D are maintained whenever the L1 cache205A,205B,205C and205D are modified, either by the local processor operations or other external operations. The illustrated cache configuration and coherency operational characteristic eliminates the need to issue coherency operations (e.g. snoops) directly to the L1 directories within the processor modules.

Although US2003/0005237 does provide a performance improvement over a system that needs to issue snoops, it does contain a significant weakness. The L2 cache,209, only contains a single copy of each L1 directory, therefore can only service a request from one processor node at a time. For example, if all four processor nodes201A,201B,201C and201D were to issue coherent memory requests A0, A1, A2 and A3 at the same time, the requests would need to be queued and serviced one at a time. For this reason the L2 cache may become a performance bottleneck.

BRIEF SUMMARY OF THE INVENTION

In one embodiment, an apparatus comprising a plurality of processor nodes and a plurality of cache memory nodes and a plurality of main memory nodes. The contents of the cache memory nodes are kept synchronised to each other and to the main memory nodes by a coherency manager. The coherency manager accesses a set of directory nodes as a necessary part of the process of maintaining synchronisation and each directory contains a list of the contents of all of the cache memory nodes, such that there is duplication of all of the contents of each directory node in the other directory nodes. Each directory node can be accessed independently and concurrently by the coherency manager.

DETAILED DESCRIPTION OF THE INVENTION

All prior patent applications, patents, documents and other publications referred to in this application are hereby incorporated by references for all purposes as allowed by law.

Preferred embodiments of the present invention aim to enable multi-processor systems that may be generally improved in the following respects.

According to one aspect of the present invention, there is provided an apparatus comprising a plurality of processor nodes and a plurality of cache memory nodes and a plurality of directory nodes and one or more main memory nodes, wherein each directory node contains a copy of the information contained in the other directory nodes and wherein each directory node can be accessed independently and concurrently by the cache memory nodes, and wherein each directory node is used to service memory access requests from a subset of the processor nodes in the system. The duplication of the directory node contents between the plurality of directory nodes enables each cache memory node to synchronise its contents with the contents of all other cache memory nodes in the system while removing the bottleneck of only having a single directory node which all cache memory nodes must access sequentially. Thus the performance of cache memory synchronisation is improved.

Furthermore, according to the present invention there is provided an apparatus comprising a plurality of processor nodes and a plurality of cache memory nodes and one or more main memory nodes, and where the contents of the cache memory nodes are kept synchronised to each other and to the main memory nodes by accessing two or more directory nodes and where each directory node contains a list of the contents of more than one of the cache memory nodes, such that there is duplication of some or all of the contents of each directory node in the other directory nodes, and where each directory node can be accessed independently and concurrently in order to improve the performance of said synchronisation.

The advantage of providing two or more directory nodes is that each can provide a dedicated directory service to a subset of the cache memory nodes in the system. Moreover, the form and structure of the information stored in each directory node is not important. It is only required that each directory node contain sufficient information so that a cache memory node can make decisions based on where copies of memory blocks are currently located within the system.

The apparatus may include a coherency manager, where the cache memory nodes send their access requests to said coherency manager and said coherency manager accesses multiple directory nodes simultaneously in order to service multiple access requests simultaneously. The coherency manager may reorder and prioritise said access requests in order to improve the performance of the apparatus.

Said coherency manager may be realised as a plurality of coherency managers wherein each coherency manager is responsible for managing the synchronisation of a subset of said cache memory nodes. This may allow the apparatus to achieve higher performance through a higher level of parallelism.

The plurality of coherency managers may exchange messages directly between each other in order to resolve conflicts more quickly, thus improving the performance of cache memory synchronisation.

The cache memory nodes may be configured to maintain the contents of the directory nodes, updating the contents of the directory nodes using the same control functions that are used to update the contents of the cache memory nodes, thus simplifying the design of the apparatus.

The processor nodes may be configured to maintain the contents of the directory nodes, thus allowing the functions of the apparatus to be easier to modify through software changes and allowing for a simpler form of cache memory node.

The coherency manager or plurality of coherency managers may be configured to maintain the contents of the directory nodes, allowing the coherency managers to better synchronise the operations of reading and updating the contents of the directory nodes in order to improve the performance of cache memory synchronisation.

An exemplary embodiment of the invention will now be described, by way of example, with reference to the accompanying drawings, described herein.

Turning toFIG. 3, a block diagram of one embodiment of a system is shown. In the illustrated embodiment, the system includes a plurality of processor nodes301,302,304and305. The system includes two cache memory nodes310and311. Two of the processor nodes301and302connect to cache memory node310. Two of the processor nodes304and305connect to cache memory node311. The system includes two directory nodes320and321. Cache memory node310is connected to directory nodes320and321for purposes of updating the contents of said directory nodes. Cache memory node310is connected to directory node320for purposes of reading the contents of said directory node as part of the process of synchronising said cache memory node to cache memory node311. Cache memory node311is connected to directory nodes320and321for purposes of updating the contents of said directory nodes. Cache memory node311is connected to directory node321for purposes of reading the contents of said directory node as part of the process of synchronising said cache memory node to cache memory node310.

Each cache memory node310and311consists of a data memory and a tag memory coupled to a respective cache control circuit.

Generally cache memory node310may be configured to cache blocks of memory from main memory for access by the corresponding processor node301and302. Generally cache memory node311may be configured to cache blocks of memory from main memory for access by the corresponding processor node304and305. The memory blocks may hold either instructions or data. The cache memory nodes each comprise a plurality of entries, where each entry is capable of storing a memory block. Additionally each entry may store a state of the block, as well as any other relevant information for the memory block such as the address tag or information for a replacement algorithm (such as least recently used state).

In the illustrated embodiment the directory nodes320and321each contain a list of cache contents322and323. The list of cache contents contains a complete list of the contents of all the cache memory nodes in the system, and is updated when the contents of any cache memory node changes. In this way a single directory node provides a complete map of the contents of all the cache memory nodes in the system.

In the illustrated embodiment, the list of contents within the directory nodes is updated at the same time as the contents of the cache memory nodes are updated. In other embodiments there may be a delay between the cache memory nodes contents changing and the directory node contents changing.

In the illustrated embodiment, the cache memory nodes310and311are each able to handle a memory access request from a processor node simultaneously. Cache memory node310passes the memory request to directory node320. Cache memory node311passes the memory request to directory node321.

Turning now toFIG. 4, a block diagram of one embodiment of a system is shown. In the illustrated embodiment, the system includes a plurality of cache memory nodes (e.g. cache memory nodes403,404and405). Each cache memory node is connected to one processor node400,401and402. In other embodiments (see above with reference toFIG. 3) the cache memory nodes may each connect to multiple processor nodes. In other embodiments (not illustrated) the cache memory nodes may each connect to a further cache memory node which is connected to a processor node.

In the illustrated embodiment each cache memory node is also connected to the coherency manager423. The coherency manager is connected to at least one main memory node426. In the illustrated embodiment, the coherency manager is connected to two directory nodes415and419. In other embodiments the cache memory nodes may connect directly to the main memory node. Each cache memory node403,404and405consists of a data memory and a tag memory coupled to a respective cache control circuit. Each directory node415and419contain a list of cache contents416and420.

Generally the cache memory nodes403,404and405may be configured to cache blocks of memory from main memory for access by the corresponding processor node400,401and402. The memory blocks may hold either instructions or data. The cache memory nodes each comprise a plurality of entries, where each entry is capable of storing a memory block. Additionally each entry may store a state of the block, as well as any other relevant information for the memory block such as the address tag or information for a replacement algorithm (such as least recently used state).

In the illustrated embodiment the list of cache contents416and420contains a complete list of the contents of all the cache memory nodes in the system, and is updated when the contents of any cache memory node changes. In this way a single directory node provides a complete map of the contents of all the cache memory nodes in the system.

In the illustrated embodiment, the list of cache contents within the directory nodes is updated at the same time as the contents of the cache memory nodes are updated. In other embodiments there may be a delay between the cache memory nodes contents changing and the directory contents changing.

In the illustrated embodiment, the coherency manager is logically divided into two channels. In other embodiments the coherency manager may be logically divided into three or more channels.

In the illustrated embodiment, the coherency manager is able to handle two memory access requests simultaneously by passing one of the requests to directory node415and the other request to directory node419.

Turning now toFIG. 5, a block diagram of one embodiment of a system is shown. In the illustrated embodiment, the system includes a plurality of cache memory nodes (e.g. cache memory nodes504,505,506and507inFIG. 5). Each cache memory node is connected to one processor node500,501,502and503. Each cache memory node is also connected to one of two coherency managers531and534. The coherency managers each connect to one main memory node533and536. Coherency manager504is connected to directory node521. Coherency manager534is connected to directory node526. Each cache memory node504,505,506and507consists of a data memory and a tag memory coupled to a respective cache control circuit. Each directory node521and526contain a list of cache contents522and527.

Generally the cache memory nodes504,505,506and507may be configured to cache blocks of memory from main memory for access by the corresponding processor node500,501,502and503. The memory block may hold either instructions or data. The cache memory nodes each comprise a plurality of entries, where each entry is capable of storing a memory block. Additionally each entry may store a state of the block, as well as any other relevant information for the memory block such as the address tag or information for a replacement algorithm (such as least recently used state).

In the illustrated embodiment, the coherency memory system is logically divided into two channels. Channel A consists of coherency manager531, directory node521, cache memory node504and cache memory node505. Channel B consists of coherency manager534, directory node526, cache memory node506and cache memory node507. In other embodiments there may be more than two channels.

In the illustrated embodiment, when one of the cache memory nodes belonging to channel A issues a memory access request to coherency manager531, the coherency manager passes the request to directory node521. When one of the cache memory nodes belonging to channel B issues a memory access request to coherency manager534, the coherency manager passes the request to directory node526. In this way the system can handle two requests at once. Directory node521has a complete list of the contents of all the cache memory nodes in the system. Likewise directory node526has a complete list of the contents of all the cache memory nodes in the system. In one embodiment the directory nodes communicates directly with the cache controller in each cache memory node in the system.

Turning now toFIG. 6, a block diagram of the preferred embodiment of a system is shown. In the illustrated embodiment, the system includes 32 cache memory nodes (e.g. cache memory nodes632to663inFIG. 6). Each cache memory node is connected to one processor node600to631. Each cache memory node is also connected to one of four coherency managers668to671. The coherency managers each connect to one main memory node664to667. Coherency manager668is connected to directory node672. Coherency manager669is connected to directory node673. Coherency manager670is connected to directory node674. Coherency manager671is connected to directory node675.

In the illustrated embodiment, the coherency memory system is logically divided into four channels. Channel A consists of coherency manager668, directory node672, and cache memory nodes632to639. Channel B consists of coherency manager669, directory node673, and cache memory nodes641to647. Channel C consists of coherency manager670, directory node674, and cache memory nodes648to655. Channel D consists of coherency manager671, directory node675, and cache memory nodes656to663. In other embodiments there may be more than four channels.

In the illustrated embodiment, when one of the cache memory nodes belonging to channel A issues a memory access request to coherency manager668, the coherency manager passes the request to directory node672. When one of the cache memory nodes belonging to channel B issues a memory access request to coherency manager669, the coherency manager passes the request to directory node673. When one of the cache memory nodes belonging to channel C issues a memory access request to coherency manager670, the coherency manager passes the request to directory node674. When one of the cache memory nodes belonging to channel D issues a memory access request to coherency manager671, the coherency manager passes the request to directory node675. In this way the system can handle four requests at once. Directory node672, has a complete list of the contents of all the cache memory nodes in the system. Likewise directory node673, directory node674and directory node675, each have a complete list of the contents of all the cache memory nodes in the system. In one embodiment the directory nodes communicate directly with the cache controller in each cache memory node in the system.

Turning now toFIG. 7, a high-level block diagram of the functional infrastructure of a computer system700that may be used to implement one possible embodiment of the invention. The system700includes, but is not limited to, a desktop computer, a laptop computer, a netbook, a tablet computer, a notebook computer, a smartphone, a server, a workstation, a supercomputer, or any other type of computing device. In another embodiment, the system700may be a system on chip integrated circuit.

The processor710has a number of processor nodes711to execute instructions of the system700. The processor also has a number of cache memory nodes712to cache instructions and/or data of the system700. In another embodiment the cache memory nodes include, but are not limited to, level one, level two and level three, cache memory or any other configuration of cache memory within the processor710.

The processor may have a number of directory nodes713and may have a number of coherency managers714and715. In another embodiment the function of the directory nodes and the coherency managers may be performed within the cache memory nodes.

The processor has a number of memory controllers716and717where each memory controller is used to control and access a main memory node720and721. The main memory may include volatile memory722, such as synchronous dynamic random access memory (SDRAM), dynamic random access memory (DRAM) and/or other types of volatile memory.

The coherency manager nodes714and715are used to synchronise the contents of the cache memory nodes712, the directory nodes713and the main memories720and721.

The bus controller718performs functions that enable the processor710to access and communicate with a number of input output devices and with non-volatile memory728. In one embodiment the bus controller may be a PCI Express controller. Common examples of input/output devices include keyboards, mice and printers730, display devices731such as monitors or liquid crystal display (LCD) panels. The computer system can be connected to other systems or network attached storage (NAS) through network adaptors724. The non-volatile memory728includes, but is not limited to, NAND flash memory, NOR flash memory, read only memory (ROM), electrically erasable programmable read only memory (EEPROM), or any other type of non-volatile memory device.

The main memory720and721stores information and instructions to be executed by the processor710. The main memory may also store temporary variables or other intermediate information while the processor710is executing instructions.

While the modules shown inFIG. 6are depicted as separate blocks within the system700, the functions performed by some of these blocks may be integrated within a single semiconductor integrated circuit or may be implemented using two or more separate integrated circuits. For example, although the cache memory nodes712are depicted as a block incorporated within the processor, the cache memory nodes can be implemented as a separate blocks within the system, separate from the processor. In another embodiment, the system may include more than one processor block.