Cache coherence protocol engine system and method for processing memory transaction in distinct address subsets during interleaved time periods in a multiprocessor system

• US 6,622,217 B2
• Filed: 06/11/2001
• Issued: 09/16/2003
• Est. Priority Date: 06/10/2000
• Status: Expired due to Fees

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Stets, Robert J Jr., Ravishankar, Mosur K., Nowatzyk, Andreas, Gharachorloo, Kourosh, Barroso, Luiz A.
• Primary Examiner(s): Yoo, Do Hyun
• Assistant Examiner(s): TAKEGUCHI, KATHY K
• Application Number:
  US09/878,983
• Publication Number:
  US 20020046327A1
• Time in Patent Office: 827 Days
• Field of Search: 711/141, 711/140, 711/167, 711/168, 711/169, 711/157, 711/127
• US Class Current: 711/141
• CPC Class Codes: G06F 12/0828 with concurrent directory accessing, i.e. handling multiple concurrent coherency transactions
• CPC Class Codes: G06F 2212/621 Coherency control relating to peripheral accessing, e.g. from DMA or I/O device

Abstract

The present invention relates generally to a protocol engine for use in a multiprocessor computer system. The protocol engine, which implements a cache coherence protocol, includes a clock signal generator for generating signals denoting interleaved even clock periods and odd clock periods, a memory transaction state array for storing entries, each denoting the state of a respective memory transaction, and processing logic. The memory transactions are divided into even and odd transactions whose states are stored in distinct sets of entries in the memory transaction state array. The processing logic has interleaving circuitry for processing during even clock periods the even memory transactions and for processing during odd clock periods the odd memory transactions.

Claims

1. A protocol engine implementing a cache coherence protocol, for use in a multiprocessor computer system, the protocol engine comprising:

a clock signal generator for generating clock signals, including a even/odd clock signal for denoting interleaved even clock periods and odd clock periods;

a memory transaction state array for storing a plurality of entries related to respective memory transactions, each entry storing a memory transaction state for a memory transaction on a memory line of information having an associated memory line address identified in the entry;

the plurality of entries in the memory transaction state array including first and second sets of entries, wherein the first set of entries is used for storing memory transaction states of memory transactions on memory lines having memory line addresses within a first predefined set of addresses, and the second set of entries is used for storing memory transaction states of memory transactions on memory lines having memory line addresses within a second predefined set of addresses, and wherein the first and second predefined sets of memory line addresses are distinct and non-overlapping; and

processing logic for processing the memory transactions whose states are stored in the entries of the memory transaction state array, including interleaving circuitry for processing during the even clock periods memory transactions whose memory transaction state is stored in entries in the first set of entries and for processing during the odd clock periods memory transactions whose memory transaction state is stored in entries in the second set of entries.

2. The protocol engine of claim 1, wherein the first predefined set of memory line addresses are even memory line addresses, having a predefined address bit whose value is “

0”

, and the second predefined set of memory line addresses are odd memory line addresses.

3. The protocol engine of claim 2, wherein a predefined bit of the even memory line addresses has a value of “

0” and

the same predefined bit of the odd memory line addresses have a value of “

1”

.

4. The protocol engine of claim 1, wherein

the processing logic includes:

an instruction array for storing executable instructions;

an execution unit for executing instructions retrieved from the instruction array; and

interleaved instruction access logic for retrieving during a first odd clock period an instruction for processing a memory transaction whose memory transaction state is stored in the first set of entries in the memory transaction state array, and for retrieving during a first even clock period an instruction for processing a memory transaction whose memory transaction state is stored in the second set of entries in the memory transaction state array;

the execution unit including interleaved instruction execution circuitry for executing during an even clock period following the first odd clock period the instruction retrieved during the first odd clock period, and for executing during an odd clock period following the first even clock period the instruction during the first even clock period.

5. The protocol engine of claim 1, wherein

the memory transaction state stored in each entry in the memory transaction state array indicates whether the entry represents a memory transaction and whether the represented memory transaction, if any, is ready for processing by the processing logic.

6. The protocol engine of claim 5, wherein

the memory transactions include even memory transactions, comprising even memory transactions whose memory transaction state is stored in the first set of entries, and odd memory transactions whose memory transaction state are stored in the second set of entries;

and

the processing logic includes;

an instruction array for storing executable instructions;

an execution unit for executing instructions retrieved from the instruction array; and

interleaved instruction access logic, coupled to the instruction array, for accessing, during each of at least a subset of the odd clock periods, a respective instruction of the executable instructions for processing one of the even memory transactions, if any, that is ready for processing, and for accessing, during each of at least a subset of the even clock periods, a respective instruction of the executable instructions for processing one of the odd memory transactions, if any, that is ready for processing;

the execution unit including interleaved instruction execution circuitry for executing during each even clock period the respective instruction, if any, accessed during a prior odd clock period, and for executing during each odd clock period the respective instruction, if any, accessed during a prior even clock period.

7. The protocol engine of claim 5, wherein the processing logic includes:

an instruction array for storing executable instructions;

an execution unit for executing instructions retrieved from the instruction array;

a scheduler, coupled to memory transaction state array, for selecting an even memory transaction, if any, comprising a memory transaction that is ready for processing and whose memory transaction state is stored in the first set of entries, and for selecting an odd memory transaction, if any, comprising a memory transaction that is ready for processing and whose memory transaction state is stored in the second set of entries; and

interleaved instruction access logic, coupled to the instruction array, for accessing a respective instruction during each odd clock period for processing the selected even memory transaction, if any, and for accessing a respective instruction during each even clock period for processing the selected odd memory transaction, if any;

the execution unit including interleaved instruction execution circuitry for executing during each even clock period the instruction, if any, accessed during a prior odd clock period, and for executing during each odd clock period the instruction, if any, accessed during a prior even clock period.

8. The protocol engine of claim 7, wherein the scheduler is configured to select during each even clock period the even memory transaction, if any, for which an instruction is to be accessed by the interleaved access logic during a next odd clock period and which is to be processed by the execution logic during a next even clock period, and is further configured to select during each odd clock period the odd memory transaction, if any, for which an instruction is to be accessed by the interleaved access logic during a next even clock period and which is to be processed by the execution logic during a next odd clock period.

9. A multiprocessor computer system, comprising:

a plurality of nodes, each node including;

an interface to a local memory subsystem, the local memory subsystem storing a multiplicity of memory lines of information and a directory;

a memory cache for caching a multiplicity of memory lines of information, including memory lines of information stored in a remote memory subsystem that is local to another node;

a clock signal generator for generating clock signals, including a even/odd clock signal for denoting interleaved even and odd clock periods; and

a protocol engine implementing a cache coherence protocol, the protocol engine including;

a memory transaction state array for storing a plurality of entries related to respective memory transactions, each entry storing a memory transaction state for a memory transaction on a memory line of information having an associated memory line address identified in the entry;

the plurality of entries in the memory transaction state array including first and second sets of entries, wherein the first set of entries is used for storing memory transaction states of memory transactions on memory lines having memory line addresses within a first predefined set of addresses, and the second set of entries is used for storing memory transaction states of memory transactions on memory lines having memory line addresses within a second predefined set of addresses, wherein the first and second predefined sets of memory line addresses are distinct and non-overlapping; and

processing logic for processing the memory transactions whose states are stored in the entries of the memory transaction state array, including interleaving circuitry for processing during the even clock periods memory transactions whose memory transaction state is stored in entries in the first set of entries and for processing during the odd clock periods memory transactions whose memory transaction state is stored in entries in the second set of entries.

10. The multiprocessor computer system of claim 9, wherein the first predefined set of memory line addresses are even memory line addresses, having a predefined address bit whose value is “

0”

, and the second predefined set of memory line addresses are odd memory line addresses.

11. The multiprocessor computer system of claim 10, wherein a predefined bit of the even memory line addresses has a value of “

0” and

the same predefined bit of the odd memory line addresses have a value of “

1”

.

12. The multiprocessor computer system of claim 9, wherein

the processing logic includes:

an instruction array for storing executable instructions;

an execution unit for executing instructions retrieved from the instruction array; and

interleaved instruction access logic for retrieving during a first odd clock period an instruction for processing a memory transaction whose memory transaction state is stored in the first set of entries in the memory transaction state array, and for retrieving during a first even clock period an instruction for processing a memory transaction whose memory transaction state is stored in the second set of entries in the memory transaction state array;

the execution unit including interleaved instruction execution circuitry for executing during an even clock period following the first odd clock period the instruction retrieved during the first odd clock period, and for executing during an odd clock period following the first even clock period the instruction during the first even clock period.

13. The multiprocessor computer system of claim 9, wherein

the memory transaction state stored in each entry in the memory transaction state array indicates whether the entry represents a memory transaction and whether the represented memory transaction, if any, is ready for processing by the processing logic.

14. The multiprocessor computer system of claim 13, wherein

the memory transactions include even memory transactions, comprising even memory transactions whose memory transaction state is stored in the first set of entries, and odd memory transactions whose memory transaction state are stored in the second set of entries;

and

the processing logic includes;

an instruction array for storing executable instructions;

an execution unit for executing instructions retrieved from the instruction array; and

interleaved instruction access logic, coupled to the instruction array, for accessing, during each of at least a subset of the odd clock periods, a respective instruction of the executable instructions for processing one of the even memory transactions, if any, that is ready for processing, and for accessing, during each of at least a subset of the even clock periods, a respective instruction of the executable instructions for processing one of the odd memory transactions, if any, that is ready for processing;

the execution unit including interleaved instruction execution circuitry for executing during each even clock period the respective instruction, if any, accessed during a prior odd clock period, and for executing during each odd clock period the respective instruction, if any, accessed during a prior even clock period.

15. The protocol engine system of claim 13, wherein the processing logic includes:

an instruction array for storing executable instructions;

an execution unit for executing instructions retrieved from the instruction array;

a scheduler, coupled to memory transaction state array, for selecting an even memory transaction, if any, comprising a memory transaction that is ready for processing and whose memory transaction state is stored in the first set of entries, and for selecting an odd memory transaction, if any, comprising a memory transaction that is ready for processing and whose memory transaction state is stored in the second set of entries; and

interleaved instruction access logic, coupled to the instruction array, for accessing a respective instruction during each odd clock period for processing the selected even memory transaction, if any, and for accessing a respective instruction during each even clock period for processing the selected odd memory transaction, if any;

the execution unit including interleaved instruction execution circuitry for executing during each even clock period the instruction, if any, accessed during a prior odd clock period, and for executing during each odd clock period the instruction, if any, accessed during a prior even clock period.

16. The protocol engine system of claim 15, wherein the scheduler is configured to select during each even clock period the even memory transaction, if any, for which an instruction is to be accessed by the interleaved access logic during a next odd clock period and which is to be processed by the execution logic during a next even clock period, and is further configured to select during each odd clock period the odd memory transaction, if any, for which an instruction is to be accessed by the interleaved access logic during a next even clock period and which is to be processed by the execution logic during a next odd clock period.