Cache coherence protocol engine and method for efficient processing of interleaved memory transactions in a multiprocessor system
First Claim
1. A protocol engine implementing a cache coherence protocol, for use in a multiprocessor computer system, the protocol engine comprising:
- a signal generator configured to generate a series of clock cycles;
a memory transaction array configured to store entries representing a plurality of memory transactions, said plurality of memory transactions being associated with the series of clock cycles;
execution logic configured to execute during a current clock cycle an instruction corresponding to a memory transaction selected in a previous clock cycle, said memory transaction associated with the current clock cycle; and
scheduling logic configured to select during the current clock cycle an active memory transaction associated with the current clock cycle, if any, from among the plurality of memory transactions represented by said entries in said memory transaction array, said scheduling logic configured to then store during the current clock cycle a first instruction address in an instruction address latch when an instruction corresponding to said first instruction address can be executed during a next clock cycle associated with said current clock cycle, said first instruction address corresponding to the memory transaction selected in the previous clock cycle;
store during said current clock cycle a second instruction address in said instruction address latch when said instruction corresponding to said first instruction address cannot be executed during said next clock cycle associated with said current clock cycle, said second instruction address corresponding to the active memory transaction; and
copy during a next clock cycle not associated with the current clock cycle an instruction from an instruction cache into an instruction latch, said instruction corresponding to an instruction address stored in said instruction address latch, the execution logic being further configured to execute during said next clock cycle associated with the current clock cycle an instruction stored in the instruction latch.
4 Assignments
0 Petitions
Accused Products
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. Moreover, the protocol engine is configured to transition from one memory transaction to another in a minimum number of clock cycles. This design improves efficiency for processing commercial workloads, such as on-line transaction processing (OLTP) by taking certain steps in parallel.
23 Citations
60 Claims
-
1. A protocol engine implementing a cache coherence protocol, for use in a multiprocessor computer system, the protocol engine comprising:
-
a signal generator configured to generate a series of clock cycles;
a memory transaction array configured to store entries representing a plurality of memory transactions, said plurality of memory transactions being associated with the series of clock cycles;
execution logic configured to execute during a current clock cycle an instruction corresponding to a memory transaction selected in a previous clock cycle, said memory transaction associated with the current clock cycle; and
scheduling logic configured to select during the current clock cycle an active memory transaction associated with the current clock cycle, if any, from among the plurality of memory transactions represented by said entries in said memory transaction array, said scheduling logic configured to then store during the current clock cycle a first instruction address in an instruction address latch when an instruction corresponding to said first instruction address can be executed during a next clock cycle associated with said current clock cycle, said first instruction address corresponding to the memory transaction selected in the previous clock cycle;
store during said current clock cycle a second instruction address in said instruction address latch when said instruction corresponding to said first instruction address cannot be executed during said next clock cycle associated with said current clock cycle, said second instruction address corresponding to the active memory transaction; and
copy during a next clock cycle not associated with the current clock cycle an instruction from an instruction cache into an instruction latch, said instruction corresponding to an instruction address stored in said instruction address latch, the execution logic being further configured to execute during said next clock cycle associated with the current clock cycle an instruction stored in the instruction latch. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48)
the series of clock cycles comprise even and odd clock cycles. -
3. The protocol engine of claim 1, wherein
the instruction corresponding to the first instruction address cannot be executed during the next clock cycle associated with the current clock cycle when the memory transaction selected in the previous clock cycle terminates during the current clock cycle, a state designation of said memory transaction selected in the previous clock cycle being set to vacant. -
4. The protocol engine of claim 3, wherein
the instruction corresponding to the first instruction address cannot be executed during the next clock cycle associated with the current clock cycle when the memory transaction selected in the previous clock cycle requires a response from a device other than the protocol engine, a state designation of said memory transaction selected in the previous clock cycle being set to waiting. -
5. The protocol engine of claim 1, wherein
the scheduling logic is configured to identify a plurality of active memory transactions represented by the entries stored in the memory transaction array, said scheduling logic is further configured to select the active memory transaction associated with the current clock cycle from said plurality of active memory transactions. -
6. The protocol engine of claim 1, further comprising
a first information buffer, wherein the scheduling logic is further configured to copy during a clock cycle preceding the current clock cycle information corresponding to the memory transaction selected in the previous clock cycle into said first information buffer, the execution logic being further configured to access and update said information corresponding to the memory transaction selected in the previous clock cycle while executing the instruction corresponding to said memory transaction selected in said previous clock cycle. -
7. The protocol engine of claim 6, wherein
when the instruction corresponding to the first instruction address cannot be executed during the next clock cycle associated with the current clock cycle the scheduling logic is further configured to: -
copy from the first information buffer during the current clock cycle said information corresponding to the memory transaction selected in the previous clock cycle into the memory transaction array, and copy during the next clock cycle not corresponding to the current clock cycle information corresponding to the active memory transaction into said first information buffer, the execution logic being further configured to access and update said information corresponding to the active memory transaction while executing one or more instructions corresponding to said active memory transaction.
-
-
8. The protocol engine of claim 6, further comprising
a second information buffer, wherein the scheduling logic is further configured to copy from the first information buffer during the current clock cycle a memory line address included in the information corresponding to the memory transaction selected in the previous clock cycle into said second information buffer when the memory transaction selected in the previous clock cycle terminates during the current clock cycle, said scheduling logic configured to then activate during the next clock cycle not associated with the current clock cycle a suspended memory transaction corresponding to the memory line address copied into in the second information buffer. -
9. The protocol engine of claim 1, further comprising
a second instruction latch, wherein the scheduling logic is configured to copy during a clock cycle following the current clock cycle the instruction stored in the instruction latch from said instruction latch to said second instruction latch so that the execution logic can re-execute said instruction during the next clock cycle associated with the current clock cycle. -
10. The protocol engine of claim 1, wherein
the execution logic is configured to generate during the current clock cycle a condition code from at least partial execution of the instruction stored in the instruction latch, said instruction comprising in part a next instruction address; - and
the selection logic configured to combine the condition code and the next instruction address to produce the first instruction address.
- and
-
11. The protocol engine of claim 1, further comprising
a series of input buffers for storing messages received by the protocol engine, each of said messages corresponding to a memory line, wherein the selection logic is configured to select during the previous clock cycle an input buffer, if any, from the series of input buffers buffering an available message associated with the current clock cycle. -
12. The protocol engine of claim 11, further comprising
an input buffer selection latch, said latch configured to receive during the previous clock cycle and maintain during the current clock cycle an input buffer identifier, said input buffer identifier identifying the selected input buffer, the selection logic being configured to reference the input buffer identifier to access the input buffer during the current clock cycle. -
13. The protocol engine of claim 11, wherein
when the available message includes a memory transaction identifier, the selection logic is configured to: -
execute during the current clock cycle a merge of the available message and a memory transaction identified by said memory transaction identifier to produce a merged instruction address; and
store during the current clock cycle the new instruction address with the memory transaction array entry representing the memory transaction identified by said memory transaction identifier.
-
-
14. The protocol engine of claim 13, wherein
when the first instruction address and the second instruction address cannot be executed during said next clock cycle associated with said current clock cycle, the selection logic is configured to copy during the current clock cycle the merged instruction address into the instruction address latch; - and
set during the current clock cycle a state designation of the memory transaction identified by said memory transaction identifier to running.
- and
-
15. The protocol engine of claim 13, wherein
when one of the first instruction address and the second instruction address can be executed during said next clock cycle associated with said current clock cycle, the selection logic is configured to set during the current clock cycle a state designation of the memory transaction identified by said memory transaction identifier to active. -
16. The protocol engine of claim 11, wherein
the selection logic is configured to determine for the available message a memory transaction identifier; -
set a state designation of a memory transaction identified by said memory transaction identifier to active during the current clock cycle; and
execute during the next clock cycle not associated with the current clock cycle a merge of the available message and the memory transaction identified by said memory transaction identifier.
-
-
17. The protocol engine of claim 11, wherein
the selection logic is configured to allocate during the current clock cycle an entry of the entries stored in the memory transaction array for a new memory transaction when the available message is of a class of messages that does not correspond to any of the plurality of memory transactions represented by the entries stored in the memory transaction array, said new memory transaction corresponding to the available message. -
18. The protocol engine of claim 17, wherein
the available message is of the class when said available message is a low priority message. -
19. The protocol engine of claim 17, wherein
the available message is of the class when none of said plurality of memory transactions represented by the entries stored in the memory transaction array are in a waiting state and correspond to the memory line. -
20. The protocol engine of claim 17, further comprising
a first information buffer, wherein the scheduling logic is further configured to copy during the next clock cycle not associated with the current clock cycle information corresponding to the new memory transaction into said first information buffer, the execution logic being further configured to access and update said information corresponding to the new memory transaction while executing an instruction corresponding to said new memory transaction. -
21. The protocol engine of claim 17, wherein
the selection logic is configured to determine during the current clock cycle whether the available message conflicts with any of the plurality of memory transactions represented by the entries stored in the memory transaction array. -
22. The protocol engine of claim 21, wherein
the available message conflicts with any of the plurality of memory transactions represented by the entries stored in the memory transaction array when any of the plurality of memory transactions represented by the entries stored in the memory transaction array correspond to the memory line. -
23. The protocol engine of claim 21, wherein
the selection logic is configured to activate during the current clock cycle the new memory transaction when the available message does not conflict with any of the plurality of memory transactions represented by the entries stored in the memory transaction array and one of the first instruction address and the second instruction address can be executed during said next clock cycle associated with said current clock cycle. -
24. The protocol engine of claim 21, wherein
the selection logic is configured to, during the current clock cycle, set to running a state designation of the new memory transaction when the available message does not conflict with any of the plurality of memory transactions represented by the entries stored in the memory transaction array and the first instruction address and the second instruction address cannot be executed during said next clock cycle associated with said current clock cycle. -
25. The protocol engine of claim 21, wherein the selection logic is configured to suspend during the current clock cycle the new memory transaction when the available message conflicts with any of the plurality of memory transactions represented by the entries stored in the memory transaction array.
-
26. The protocol engine of claim 21, wherein
the selection logic is configured to copy during the current clock cycle an instruction address from the available message into the instruction address latch if the first instruction address and the second instruction address cannot be executed during said next clock cycle associated with said current clock cycle. -
27. The protocol engine of claim 26, wherein
the scheduling logic is configured to copy, during the next clock cycle not associated with the current clock cycle, a no-operation instruction into the instruction latch when the available message conflicts with any of the plurality of memory transactions represented by the entries stored in the memory transaction array. -
28. The protocol engine of claim 11, wherein
when the available message is of a class of messages that can correspond to a memory transaction the selection logic is configured to determine during the current clock cycle whether any of the plurality of memory transactions represented by the entries stored in the memory transaction array are in a waiting state and correspond to the memory line; -
determine during the current clock cycle whether space is available in the memory transaction array for a new memory transaction entry; and
determine during the current clock cycle whether the available message conflicts with any of the plurality of memory transactions represented by the entries stored in the memory transaction array.
-
-
29. The protocol engine of claim 28, wherein
the selection logic is further configured to identify during the current clock cycle a memory transaction identifier of a memory transaction that is in a waiting state and corresponds to the memory line; - and
store the memory transaction identifier with the available message.
- and
-
30. The protocol engine of claim 29, wherein
the selection logic is configured to activate during the current clock cycle the memory transaction, if there is one, that is in a waiting state and corresponds to the memory line. -
31. The protocol engine of claim 29, wherein
when said memory transaction identifier is identified, the selection logic is configured to execute during the next clock cycle not associated with the current clock cycle a merge of the available message with the memory transaction identified by said memory transaction identifier. -
32. The protocol engine of claim 28, wherein
the selection logic is configured to copy during the current clock cycle an instruction address from the available message into the instruction address latch if the first instruction address and the second instruction address cannot be executed during said next clock cycle associated with said current clock cycle. -
33. The protocol engine of claim 32, wherein
the scheduling logic is configured to copy during the next clock cycle not associated with the current clock cycle a no-operation instruction into the instruction latch when any of the plurality of memory transactions represented by the entries stored in the memory transaction array are in a waiting state and correspond to the memory line. -
34. The protocol engine of claim 32, wherein
the scheduling logic copies during the next clock cycle not associated with the current clock cycle a no-operation instruction into the instruction latch when none of the plurality of memory transactions represented by the entries stored in the memory transaction array are in a waiting state and correspond to the memory line; - and
there is no space available in the memory transaction array for the new memory transaction entry.
- and
-
35. The protocol engine of claim 32, wherein
the scheduling logic copies during the next clock cycle not associated with the current clock cycle a no-operation instruction into the instruction latch when none of the plurality of memory transactions represented by the entries stored in the memory transaction array are in a waiting state and correspond to the memory line; - and
the available message conflicts with any of the plurality of memory transactions represented by the entries stored in the memory transaction array.
- and
-
36. The protocol engine of claim 28, wherein
the available message conflicts with any of the plurality of memory transactions represented by the entries stored in the memory transaction array when any of the plurality of memory transactions represented by the entries stored in the memory transaction array corresponds to the memory line and is not in a waiting state. -
37. The protocol engine of claim 28, wherein
the selection logic is configured to activate during the current clock cycle the new memory transaction when none of the plurality of memory transactions represented by the entries stored in the memory transaction array are in a waiting state and correspond to the memory line; -
there is space available in the memory transaction array for the new memory transaction entry;
the available message does not conflict with any of the plurality of memory transactions represented by the entries stored in the memory transaction array; and
one of the first instruction address and the second instruction address can be executed during said next clock cycle associated with said current clock cycle.
-
-
38. The protocol engine of claim 28, wherein
the selection logic is configured to, during the current clock cycle, set a state designation of the new memory transaction to running when none of the plurality of memory transactions represented by the entries stored in the memory transaction array are in a waiting state and correspond to the memory line; -
there is space available in the memory transaction array for the new memory transaction entry;
the available message does not conflict with any of the plurality of memory transactions represented by the entries stored in the memory transaction array; and
the first instruction address and the second instruction address cannot be executed during said next clock cycle associated with said current clock cycle.
-
-
39. The protocol engine of claim 11, wherein
each of the series of input buffers is assigned a priority level from a plurality of priority levels, the scheduling logic configured to select the selected input buffer by reference to the priority level assigned to the selected input buffer, said selected input buffer having a highest priority level among one or more of the series of input buffers buffering an available message. -
40. The protocol engine of claim 39, wherein
the plurality of priority levels includes a first priority, a second priority, a third priority and a fourth priority, said first priority assigned to an input buffer configured to store messages of a type that always include a memory transaction identifier, said second priority assigned to an input buffer configured to store messages of a type that can include a memory transaction identifier, said third priority assigned to an input buffer configured to store messages of a type that do not include a memory transaction identifier, and said fourth priority assigned to an input buffer configured to store messages of a type sent only by an input/output device. -
41. The protocol engine of claim 39, wherein
the plurality of priority levels includes a first priority, a second priority and a third priority, said first priority assigned to an input buffer configured to store messages that are always solicited responses, said second priority assigned to an input buffer configured to store messages that can be solicited responses and unsolicited messages, and said third priority assigned to an input buffer configured to store messages that are never solicited responses. -
42. The protocol engine of claim 1, further comprising
a packet switch interface, an intra-chip switch interface, and a series of input buffers, said input buffers buffering messages received from said packet switch interface and said intra-chip switch interface during a clock cycle preceding the current clock cycle, said packet switch interface and said intra-chip switch interface also providing an unbuffered source of messages received by said packet switch interface and said intra-chip switch interface during the current clock cycle, wherein the selection logic is configured to select during the previous clock cycle from among said packet switch interface, said intra-chip switch interface, and said series of input buffers a message source for the current clock cycle; - and
said selection logic is further configured to extract a third instruction address from the message source and store said third instruction address in the instruction address latch during the current clock cycle when the instruction corresponding to the first instruction address cannot be executed during the next clock cycle associated with said current clock cycle and the memory transaction array does not include any active memory transactions associated with the current clock cycle.
- and
-
43. The protocol engine of claim 42, further comprising
a message source selection latch, said message source selection latch configured to receive during the previous clock cycle and maintain during the current clock cycle a message source identifier, the selection logic being configured to reference said message source identifier to access the message source during the current clock cycle. -
44. The protocol engine of claim 42, wherein
the selection logic is configured to select an input buffer, from the series of input buffer, as the message source instead of the packet switch interface and said intra-chip interface when said selected input buffer has an available message. -
45. The protocol engine of claim 42, wherein
the selection logic is configured to select from the series of input buffers an input buffer configured to store only messages that are solicited responses when said input buffer configured to store only messages that are solicited responses is buffering a message. -
46. The protocol engine of claim 45, wherein
the selection logic is configured to select from the series of input buffers an input buffer configured to store messages that are solicited responses and messages that are not solicited responses when said input buffer configured to store messages that are solicited responses and messages that are not solicited responses is buffering a message and said input buffer configured to store only messages that are solicited responses is not buffering a message. -
47. The protocol engine of claim 46, wherein
the selection logic is configured to select from the series of input buffers an input buffer configured to store only unsolicited messages when said input buffer configured to store only unsolicited messages is buffering a message and said input buffer configured to store only messages that are solicited responses and said input buffer configured to store messages that are solicited responses and messages that are not solicited responses are not buffering a message. -
48. The protocol engine of claim 47, wherein
the selection logic is configured to select from the series of input buffers an input buffer configured to store only messages corresponding to an input/output device when said input buffer configured to store only messages corresponding to said input/output device is buffering a message and said input buffer configured to store only messages that are solicited responses, said input buffer configured to store messages that are solicited responses and messages that are not solicited responses, and said input buffer configured to store only unsolicited messages are not buffering a message.
-
-
49. A protocol engine implementing a cache coherence protocol, for use in a multiprocessor computer system, the protocol engine comprising:
-
a signal generator configured to generate a series of clock cycles;
a memory transaction array configured to store entries representing a plurality of memory transactions, said plurality of memory transactions being associated with the series of clock cycles;
a message source, said message source including a plurality of message ports and a plurality of input buffers, said plurality of input buffers configured to store messages received through said plurality of message ports;
execution logic configured to execute during a current clock cycle an instruction corresponding to a memory transaction scheduled in a previous clock cycle, said memory transaction associated with the current clock cycle; and
scheduling logic configured to;
identify a plurality of memory transactions, if any, capable of execution during a next clock cycle associated with the current clock cycle, said plurality of memory transactions including one or more of;
the memory transaction scheduled in a previous clock cycle;
an active memory transaction associated with the current clock cycle stored in the memory transaction array; and
a memory transaction corresponding to a message selected from the message source; and
schedule during the current clock cycle one of the plurality of memory transactions according to a predefined prioritization scheme. - View Dependent Claims (50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60)
the scheduling logic is configured to schedule the memory transaction scheduled in a previous clock cycle if identified by the scheduling logic as being capable of execution during the next clock cycle associated with the current clock cycle. -
51. The protocol engine of claim 50, wherein
the scheduling logic is configured to set during the current clock cycle a state of the memory transaction scheduled in a previous clock cycle if not identified by the scheduling logic as being capable of execution during the next clock cycle associated with the current clock cycle. -
52. The protocol engine of claim 49, wherein
the scheduling logic is configured to schedule the active memory transaction if identified by the scheduling logic as being capable of execution during the next clock cycle associated with the current clock cycle, and if the memory transaction scheduled in a previous clock cycle is not identified by the scheduling logic as being capable of execution during the next clock cycle associated with the current clock cycle. -
53. The protocol engine of claim 52, wherein
the scheduling logic is configured to set during a clock cycle after the current clock cycle a state of the active memory transaction to running. -
54. The protocol engine of claim 49, wherein
the scheduling logic is configured to schedule the memory transaction corresponding to the message selected from the message source if said corresponding memory transaction is identified by the scheduling logic as being capable of execution during the next clock cycle associated with the current clock cycle and if the memory transaction scheduled in a previous clock cycle and the active memory transaction are not identified by the scheduling logic as being capable of execution during the next clock cycle associated with the current clock cycle. -
55. The protocol engine of claim 54, wherein
the scheduling logic is configured to set during the current clock cycle a state of the memory transaction corresponding to the message selected from the message source. -
56. The protocol engine of claim 49, wherein
the scheduling logic is configured to select the message selected from the message source during a clock cycle preceding the current clock cycle for scheduling in conjunction with a corresponding memory transaction. -
57. The protocol engine of claim 49, wherein
the scheduling logic is further configured to select another message from the message source during the current clock cycle for merger into a waiting memory transaction. -
58. The protocol engine of claim 49, wherein
the scheduling logic is further configured to select another message from the message source during the current clock cycle to provide the basis of a new memory transaction. -
59. The protocol engine of claim 49, wherein
the scheduling logic is configured to directly select a message stored in one of said plurality of input buffers during a clock cycle preceding the current clock cycle. -
60. The protocol engine of claim 49, wherein
the scheduling logic is configured to speculatively select a message from one of said plurality of message ports during a clock cycle preceding the current clock cycle, said message not guaranteed to arrive during the current clock cycle.
-
Specification