WikiPatents - Community Patent Review
Create Free Account  |  License or Sell Your Patent  |  WikiPatents Marketplace  |  WikiPatents Blog
Username:  Password:  
    
Advanced Search
Flexible probe/probe response routing for maintaining coherency    

Custom CD of patents similar to US6631401 : Flexible probe/probe response routing for maintaining coherency - $19.95
United States Patent6631401   
Link to this pagehttp://www.wikipatents.com/6631401.html
Inventor(s)Keller; James B. (Palo Alto, CA); Gulick; Dale E. (Austin, TX)
AbstractA computer system may include multiple processing nodes, one or more of which may be coupled to separate memories which may form a distributed memory system. The processing nodes may include caches, and the computer system may maintain coherency between the caches and the distributed memory system. Particularly, the computer system may implement a flexible probe command/response routing scheme. The scheme may employ an indication within the probe command which identifies a receiving node to receive the probe responses. For example, probe commands indicating that the target or the source of transaction should receive probe responses corresponding to the transaction may be included. Probe commands may specify the source of the transaction as the receiving node for read transactions (such that dirty data is delivered to the source node from the node storing the dirty data). On the other hand, for write transactions (in which data is being updated in memory at the target node of the transaction), the probe commands may specify the target of the transaction as the receiving node. In this manner, the target may determine when to commit the write data to memory and may receive any dirty data to be merged with the write data.
   














 Title Information Submit all comments and votes
 
Patent Text Patent PDF Print Page Summary File History
Plain text PDF images Print Summary File History
Drawing from US Patent 6631401
Flexible probe/probe response routing for maintaining coherency - US Patent 6631401 Drawing
Flexible probe/probe response routing for maintaining coherency
Inventor     Keller; James B. (Palo Alto, CA); Gulick; Dale E. (Austin, TX)
Owner/Assignee     Advanced Micro Devices, Inc. (Sunnyvale, CA)
Patent assignment
All assignments
Company News
Publication Date     October 7, 2003
Application Number     09/217,367
PAIR File History     Application Data   Transaction History
Image File Wrapper   Patent Term   Fees
Litigation
Filing Date     December 21, 1998
US Classification    
Int'l Classification    
Examiner     Winder; Patrice
Assistant Examiner    
Attorney/Law Firm     Merkel; Lawrence J. Meyertons, Hood, Kivlin, Kowert & Goetzel, P.C.
Address
Parent Case    
Priority Data    
USPTO Field of Search    
Patent Tags     flexible probe/probe response routing maintaining coherency
   
Enter a comma (,) or semicolon (;) between multiple tag words/phrases.
Describe this patent:
 Amusing   
 Clever   
 Complex   
 Efficient   
 Historic   
 Important   
 Innovative   
 Interesting   
 Practical   
 Simple   
[no votes]
Patent WIKI

Share information and news about this patent, including information and news about the technology, inventors, company, ligation and licensing.

 References Submit all comments and votes
 
*references marked with an asterisk below are user-added references
 U.S. References
 
Add a new US reference:  
ReferenceRelevancyCommentsReferenceRelevancyComments
6370621
Keller

Apr,2002

[0 after 0 votes]
6295583
Razdan
711/137
Sep,2001

[0 after 0 votes]
6292705
Wang
700/5
Sep,2001

[0 after 0 votes]
6286090
Steely, Jr.
711/207
Sep,2001

[0 after 0 votes]
6275905
Keller
711/141
Aug,2001

[0 after 0 votes]
6249846
Van Doren
711/144
Jun,2001

[0 after 0 votes]
6209065
Van Doren
711/150
Mar,2001

[0 after 0 votes]
6199153
Razdan
711/212
Mar,2001

[0 after 0 votes]
6138218
Arimilli

Oct,2000

[0 after 0 votes]
6112281
Bamford

Aug,2000

[0 after 0 votes]
6108737
Sharma
710/107
Aug,2000

[0 after 0 votes]
6108752
VanDoren
711/117
Aug,2000

[0 after 0 votes]
6101420
VanDoren

Aug,2000

[0 after 0 votes]
6098115
Eberhard

Aug,2000

[0 after 0 votes]
6085263
Sharma

Jul,2000

[0 after 0 votes]
6070231
Ottinger

May,2000

[0 after 0 votes]
6049851
Bryg
711/141
Apr,2000

[0 after 0 votes]
6038644
Irie
711/141
Mar,2000

[0 after 0 votes]
6018791
Arimilli

Jan,2000

[0 after 0 votes]
6012127
McDonald
711/141
Jan,2000

[0 after 0 votes]
5991819
Young

Nov,1999

[0 after 0 votes]
5987544
Bannon
710/100
Nov,1999

[0 after 0 votes]
5966729
Phelps
711/146
Oct,1999

[0 after 0 votes]
5924118
Arimilli
711/130
Jul,1999

[0 after 0 votes]
5893144
Wood

Apr,1999

[0 after 0 votes]
5887138
Hagersten
709/215
Mar,1999

[0 after 0 votes]
5878268
Hagersten
712/28
Mar,1999

[0 after 0 votes]
5859983
Heller
709/251
Jan,1999

[0 after 0 votes]
5749095
Hagersten
711/141
May,1998

[0 after 0 votes]
5684977
Van Loo
711/143
Nov,1997

[0 after 0 votes]
5673413
Deshpande
711/141
Sep,1997

[0 after 0 votes]
5659708
Arimilli
711/146
Aug,1997

[0 after 0 votes]
5560038
Haddock

Sep,1996

[0 after 0 votes]
5537575
Foley
711/141
Jul,1996

[0 after 0 votes]
5517494
Green
370/408
May,1996

[0 after 0 votes]
5412788
Collins
711/157
May,1995

[0 after 0 votes]
5303362
Butts, Jr.
711/121
Apr,1994

[0 after 0 votes]
 Foreign References
 Other References
 Market Review Submit all comments and votes
   
Market Size
Estimate the gross annual revenues of the relevant market sector:
> $10B
$5B - $10B
$2B - $5B
$500M - $2B
$100M - $500M
$10M - $100M
$1M - $10M
$500K - $1M
$100K - $500K
< $100K
[No votes]
$0
 
$0   $2.5B   $5B   $7.5B   $10B

[0 market size comments]
Market Share
Estimate the percentage of the relevant market sector this invention will capture:
75% - 100%
50% - 74.99%
25% - 49.99%
10 - 24.99%
5 - 9.99%
2 - 4.99%
1 - 1.99%
< 1%
[No votes]
0.0%
 
0%   25%   50%   75%   100%

[0 market share comments]
Reasonable Royalty
What percentage of gross sales should the inventor or assignee be paid?
75% - 100%
50% - 74.99%
25% - 49.99%
10 - 24.99%
5 - 9.99%
2 - 4.99%
1 - 1.99%
< 1%
[No votes]
0.0%
 
0%   25%   50%   75%   100%

[0 reasonable royalty comments]
Public's "Guesstimation" of Royalty Value
Market SizeN/A[No votes]
xMarket ShareN/A[No votes]
xReasonable RoyaltyN/A[No votes]

N/A

[0 Guesstimation of Royalty Value Comments]
License Availablity
If you are NOT the owner or assignee, answer here:
Yes, license is available for purchase

No, license is not currently available



[No votes]
[0 license availability comments]
License Availablity
If you ARE the owner or assignee, answer here:
Yes, license is available for purchase

No, license is not currently available



[No votes]
[0 owner/assignee comments]
Competitive Advantage
Does this invention have a significant competitive advantage over similar technologies?
Yes

No



[No votes]
Most helpful competitive advantage comment
[No comments]

[0 competitive advantage comments]
Commercial Alternatives
Are there viable commercial alternatives for this invention?
Yes

No



[No votes]
Most helpful commercial alternative comment
[No comments]

[0 commercial alternatives comments]
 Technical Review Submit all comments and votes
 Claims Submit all comments and votes
 


What is claimed is:

1. An apparatus comprising a first node coupled to receive a probe, the probe generated by a target node in response to a request transmitted to the target node by a source node, and wherein the first node is configured to generate a probe response in response to the probe, and wherein the first node is configured to select which one of the target node and the source node is to receive the probe response in response to an indication in the probe, and wherein the first node is configured to transmit the probe response to the one of the target node or the source node.

2. The apparatus as recited in claim 1 wherein the probe includes a first node number indicative of the target node and a second node number indicative of the source node, and wherein the first node is configured to select one of the first node number and the second node number for routing the probe response responsive to the indication in the probe.

3. The apparatus as recited in claim 1 wherein the probe response optionally includes data depending on whether or not the first node is storing a modified copy of data identified by the probe.

4. The apparatus as recited in claim 3 wherein the probe includes a data movement indication indicative of whether or not the modified copy is to be transmitted in response to the probe, wherein the probe response optionally includes data further dependent on the data movement indication.

5. The apparatus as recited in claim 1 wherein the probe includes a next state field identifying a next state for data identified by the probe in the first node if the first node is caching the data, wherein the first node is configured to change a state of the data in the first node responsive to the next state field.

6. A method comprising: receiving a probe in a first node, the probe generated by a target node in response to a request transmitted to the target node by a source node; generating a probe response in the first node in response to the probe; selecting one of the target node and the source node to receive the probe response in response to an indication in the probe; and transmitting the probe response to the one of the target node or the source node.

7. The method as recited in claim 6 wherein the probe includes a first node number indicative of the target node and a second node number indicative of the source node, the method further comprising selecting one of the first node number and the second node number for routing the probe response responsive to the indication in the probe.

8. The method as recited in claim 6 further comprising optionally transmitting data in the probe response depending on whether or not the first node is storing a modified copy of data identified by the probe.

9. The method as recited in claim 8 wherein the probe includes a data movement indication indicative of whether or not the modified copy is to be transmitted in response to the probe, wherein the optionally transmitting is further dependent on the data movement indication.

10. The method as recited in claim 6 wherein the probe includes a next state field identifying a next state for data identified by the probe in the first node if the first node is caching the data, wherein the method further comprises changing a state of the data in the first node responsive to the next state field.
 Description Submit all comments and votes
 


BACKGROUND OF THE INVENTION

1. Field of the Invention

This invention is related to the field of computer systems and, more particularly, to coherency systems within computer systems.

2. Description of the Related Art

Generally, personal computers (PCs) and other types of computer systems have been designed around a shared bus system for accessing memory. One or more processors and one or more input/output (I/O) devices are coupled to memory through the shared bus. The I/O devices may be coupled to the shared bus through an I/O bridge which manages the transfer of information between the shared bus and the I/O devices, while processors are typically coupled directly to the shared bus or are coupled through a cache hierarchy to the shared bus.

Unfortunately, shared bus systems suffer from several drawbacks. For example, since there are multiple devices attached to the shared bus, the bus is typically operated at a relatively low frequency. The multiple attachments present a high capacitive load to a device driving a signal on the bus, and the multiple attach points present a relatively complicated transmission line model for high frequencies. Accordingly, the frequency remains low, and bandwidth available on the shared bus is similarly relatively low. The low bandwidth presents a barrier to attaching additional devices to the shared bus, as performance may be limited by available bandwidth.

Another disadvantage of the shared bus system is a lack of scalability to larger numbers of devices. As mentioned above, the amount of bandwidth is fixed (and may decrease if adding additional devices reduces the operable frequency of the bus). Once the bandwidth requirements of the devices attached to the bus (either directly or indirectly) exceeds the available bandwidth of the bus, devices will frequently be stalled when attempting access to the bus. Overall performance may be decreased.

One or more of the above problems may be addressed using a distributed memory system. A computer system employing a distributed memory system includes multiple nodes. Two or more of the nodes are connected to memory, and the nodes are interconnected using any suitable interconnect. For example, each node may be connected to each other node using dedicated lines. Alternatively, each node may connect to a fixed number of other nodes, and transactions may be routed from a first node to a second node to which the first node is not directly connected via one or more intermediate nodes. The memory address space is assigned across the memories in each node.

Nodes may additionally include one or more processors. The processors typically include caches which store cache blocks of data read from the memories. Furthermore, a node may include one or more caches external to the processors. Since the processors and/or nodes may be storing cache blocks accessed by other nodes, a mechanism for maintaining coherency within the nodes is desired.

SUMMARY OF THE INVENTION

The problems outlined above are in large part solved by a computer system as described herein. The computer system may include multiple processing nodes, one or more of which may be coupled to separate memories which may form a distributed memory system. The processing nodes may include caches, and the computer system may maintain coherency between the caches and the distributed memory system. Particularly, the computer system may implement a flexible probe command/response routing scheme.

In one embodiment, the scheme employs an indication within the probe command which identifies a receiving node to receive the probe responses. Generally, the probe command is a request to a node to determine if a cache block is stored in that node and an indication of the actions to be taken by that node if the cache block is stored in that node. The probe response indicates that the actions have been taken, and may include a transmission of data if the cache block has been modified by the node. By providing the flexibility to route the probe responses to different receiving nodes depending upon the command sent, the maintenance of coherency may be performed in a relatively efficient manner (e.g. using the fewest number of packet transmissions between processing nodes) while still ensuring that coherency is maintained.

For example, probe commands indicating that the target or the source of transaction should receive probe responses corresponding to the transaction may be included. Probe commands may specify the source of the transaction as the receiving node for read transactions (such that dirty data is delivered to the source node from the node storing the dirty data). On the other hand, for write transactions (in which data is being updated in memory at the target node of the transaction), the probe commands may specify the target of the transaction as the receiving node. In this manner, the target may determine when to commit the write data to memory and may receive any dirty data to be merged with the write data.

Broadly speaking, a computer system is contemplated. The computer system may comprise a first processing node and a second processing node. The first processing node may be configured to initiate a transaction by transmitting a request. Coupled to receive the request from the first processing node, the second processing node may be configured to generate a probe in response to the request. The probe includes an indication which designates a receiving node to receive responses to the probe. Additionally, the second processing node may be configured to generate the indication responsive to a type of the transaction.

A method for maintaining coherency in a computer system is also contemplated. A request from a source node is transmitted to a target node. A probe is generated in the target node responsive to the request. A receiving node is designated for responses to the probe via an indication within the probe. A probe response to the probe is routed to the receiving node.

BRIEF DESCRIPTION OF THE DRAWINGS

Other objects and advantages of the invention will become apparent upon reading the following detailed description and upon reference to the accompanying drawings in which:

FIG. 1 is a block diagram of one embodiment of a computer system.

FIG. 2 is a block diagram of a pair of processing nodes shown in FIG. 1, highlighting one embodiment of interconnect therebetween.

FIG. 3 is a block diagram of one embodiment of an information packet.

FIG. 4 is a block diagram of one embodiment of an address packet.

FIG. 5 is a block diagram of one embodiment of a response packet.

FIG. 6 is a block diagram of one embodiment of a data packet.

FIG. 7 is table illustrating exemplary packet types with may be employed by one embodiment of a computer system.

FIG. 8 is a block diagram of one embodiment of a probe packet.

FIG. 9 is a block diagram of one embodiment of a probe response packet.

FIG. 10 is a block diagram of one embodiment of a read response packet.

FIG. 11 is a diagram illustrating an example flow of packets corresponding to a read block transaction.

FIG. 12 is a diagram illustrating a second example flow of packets corresponding to a read block transaction.

FIG. 13 is a diagram illustrating an example flow of packets corresponding to a sized write transaction.

FIG. 14 is a flowchart illustrating operation of one embodiment of a memory controller.

FIG. 15 is a flowchart illustrating operation of one embodiment of a processing node which receives a probe packet.

FIG. 16 is a block diagram of one embodiment of a processing node.

While the invention is susceptible to various modifications and alternative forms, specific embodiments thereof are shown by way of example in the drawings and will herein be described in detail. It should be understood, however, that the drawings and detailed description thereto are not intended to limit the invention to the particular form disclosed, but on the contrary, the intention is to cover all modifications, equivalents and alternatives falling within the spirit and scope of the present invention as defined by the appended claims.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS

Exemplary Computer System Embodiment

Turning now to FIG. 1, one embodiment of a computer system 10 is shown. Other embodiments are possible and contemplated. In the embodiment of FIG. 1, computer system 10 includes several processing nodes 12A, 12B, 12C, and 12D. Each processing node is coupled to a respective memory 14A-14D via a memory controller 16A-16D included within each respective processing node 12A-12D. Additionally, processing nodes 12A-12D include interface logic used to communicate between the processing nodes 12A-12D. For example, processing node 12A includes interface logic 18A for communicating with processing node 12B, interface logic 18B for communicating with processing node 12C, and a third interface logic 18C for communicating with yet another processing node (not shown). Similarly, processing node 12B includes interface logic 18D, 18E, and 18F; proce