Electrical computers and digital processing systems: memory – Storage accessing and control – Shared memory area
Reexamination Certificate
2000-09-29
2002-11-26
Verbrugge, Kevin (Department: 2187)
Electrical computers and digital processing systems: memory
Storage accessing and control
Shared memory area
C711S148000
Reexamination Certificate
active
06487643
ABSTRACT:
FIELD OF THE INVENTION
Embodiments of the present invention relate to a computer system having a multi-node computer architecture. In particular, the present invention relates to a method and apparatus for managing memory related requests in a multi-node architecture such that there is no starvation of requests from a subset of nodes and every request from a node gets a chance to eventually complete.
BACKGROUND
Computer systems may contain multiple processors that may work together to perform a task. For example, a computer system may contain four processors that may share system resources (e.g., input devices or memory devices) and may perform parallel processing. The processors may send messages to each other, may send messages to system resources, and may send and receive messages from the system resources. For example, such messages may include requests for information that is stored at a location in a memory device or a request to store information in a location of a memory device.
In many computer systems, the set of data currently being used by a microprocessor may be copied from a system memory device such as a dynamic random access memory (DRAM) into a relatively smaller but faster cache memory device such as a static random access memory (SRAM). The cache memory device is usually private to each processor such that only one processor can read or write to it. In such systems, a cache is said to be “coherent” if the information resident in the cache reflects a consistent view of the information in all the private cache memory devices and the DRAM memory. Cache “snooping” is a technique used to detect the state of a memory location in private cache memory devices on a memory access that might cause a cache coherency problem. In a multi-processor system, the messages sent between processors may include cache snooping messages.
A processor may be said to encounter a “livelock” or “starvation” situation when a coherency event generated by a processor is unable to complete for an indefinite amount of time even after repeated attempts, because another event from the same processor or another processor prevents it from making forward progress. If the sending of requests from processors in a multi-processor system and servicing of the requests at the responding agent is not managed properly, then some of the requests may be starved by the responding agent and a livelock situation may occur. For example, a first processor may be accessing a memory location, and at the same time the second processor may be also accessing the same memory location. If the memory agent can satisfy only one request to a memory location at a time and must ask all other requests to the same location to be reissued, then it is possible that the request from the first processor never completes because the same memory location is being accessed again and again by the second processor. In this case, requests from the second processor cause starvation of the request from the first processor, therefore causing a livelock at the first processor.
REFERENCES:
patent: 5485579 (1996-01-01), Hitz et al.
patent: 5495419 (1996-02-01), Rostoker et al.
patent: 5535116 (1996-07-01), Gupta et al.
patent: 5541914 (1996-07-01), Krishnamoorthy et al.
patent: 5551048 (1996-08-01), Steely, Jr.
patent: 5557533 (1996-09-01), Koford et al.
patent: 5581729 (1996-12-01), Nishtala et al.
patent: 5588131 (1996-12-01), Borrill
patent: 5588132 (1996-12-01), Cardoza
patent: 5588152 (1996-12-01), Dapp et al.
patent: 5590292 (1996-12-01), Wooten et al.
patent: 5590345 (1996-12-01), Barker et al.
patent: 5594918 (1997-01-01), Knowles et al.
patent: 5603005 (1997-02-01), Bauman et al.
patent: 5613136 (1997-03-01), Casavant et al.
patent: 5617537 (1997-04-01), Yamada et al.
patent: 5625836 (1997-04-01), Barker et al.
patent: 5634004 (1997-05-01), Gopinath et al.
patent: 5634068 (1997-05-01), Nishtala et al.
patent: 5636125 (1997-06-01), Rostoker et al.
patent: 5644753 (1997-07-01), Ebrahim et al.
patent: 5655100 (1997-08-01), Ebrahim et al.
patent: 5657472 (1997-08-01), Van Loo et al.
patent: 5678026 (1997-10-01), Vartti et al.
patent: 5680571 (1997-10-01), Bauman
patent: 5680576 (1997-10-01), Laudon
patent: 5682322 (1997-10-01), Boyle et al.
patent: 5682512 (1997-10-01), Tetrick
patent: 5684977 (1997-11-01), Van Loo et al.
patent: 5699500 (1997-12-01), Dasgupta
patent: 5701313 (1997-12-01), Purdham
patent: 5701413 (1997-12-01), Zulian et al.
patent: 5708836 (1998-01-01), Wilkinson et al.
patent: 5710935 (1998-01-01), Barker et al.
patent: 5713037 (1998-01-01), Wilkinson et al.
patent: 5717942 (1998-02-01), Haupt et al.
patent: 5717943 (1998-02-01), Barker et al.
patent: 5717944 (1998-02-01), Wilkinson et al.
patent: 5734921 (1998-03-01), Dapp et al.
patent: 5734922 (1998-03-01), Hagersten et al.
patent: 5742510 (1998-04-01), Rostoker et al.
patent: 5745363 (1998-04-01), Rostoker et al.
patent: 5749095 (1998-05-01), Hagersten
patent: 5752067 (1998-05-01), Wilkinson et al.
patent: 5754789 (1998-05-01), Nowatzyk et al.
patent: 5754871 (1998-05-01), Wilkinson et al.
patent: 5754877 (1998-05-01), Hagersten et al.
patent: 5761523 (1998-06-01), Wilkinson et al.
patent: 5765011 (1998-06-01), Wilkinson et al.
patent: 5781439 (1998-07-01), Rostoker et al.
patent: 5784697 (1998-07-01), Funk et al.
patent: 5787094 (1998-07-01), Cecchi et al.
patent: 5793644 (1998-08-01), Koford et al.
patent: 5794059 (1998-08-01), Barker et al.
patent: 5796605 (1998-08-01), Hagersten
patent: 5802578 (1998-09-01), Lovett
patent: 5805839 (1998-09-01), Singhal
patent: 5815403 (1998-09-01), Jones et al.
patent: 5842031 (1998-11-01), Barker et al.
patent: 5848254 (1998-12-01), Hagersten
patent: 5857113 (1999-01-01), Muegge et al.
patent: 5860159 (1999-01-01), Hagersten
patent: 5862316 (1999-01-01), Hagersten et al.
patent: 5864738 (1999-01-01), Kessler et al.
patent: 5867649 (1999-02-01), Larson
patent: 5870313 (1999-02-01), Boyle et al.
patent: 5870619 (1999-02-01), Wilkinson et al.
patent: 5875117 (1999-02-01), Jones et al.
patent: 5875201 (1999-02-01), Bauman et al.
patent: 5875462 (1999-02-01), Bauman et al.
patent: 5875472 (1999-02-01), Bauman et al.
patent: 5878241 (1999-03-01), Wilkinson et al.
patent: 5878268 (1999-03-01), Hagersten
patent: 5881303 (1999-03-01), Hagersten et al.
patent: 5887138 (1999-03-01), Hagersten et al.
patent: 5887146 (1999-03-01), Baxter et al.
patent: 5892970 (1999-04-01), Hagerstein
patent: 5897657 (1999-04-01), Hagersten et al.
patent: 5900020 (1999-05-01), Safranek et al.
patent: 5903461 (1999-05-01), Rostoker et al.
patent: 5905881 (1999-05-01), Tran et al.
patent: 5905998 (1999-05-01), Ebrahim et al.
patent: 5911052 (1999-06-01), Singhal et al.
patent: 5914887 (1999-06-01), Scepanovic et al.
patent: 5922063 (1999-07-01), Olnowich et al.
patent: 5925097 (1999-07-01), Gopinath et al.
patent: 5931938 (1999-08-01), Drogichen et al.
patent: 5938765 (1999-08-01), Dove et al.
patent: 5941967 (1999-08-01), Zulian
patent: 5943150 (1999-08-01), Deri et al.
patent: 5946710 (1999-08-01), Bauman et al.
patent: 5950226 (1999-09-01), Hagersten et al.
patent: 5958019 (1999-09-01), Hagersten et al.
patent: 5960455 (1999-09-01), Bauman
patent: 5961623 (1999-10-01), James et al.
patent: 5963745 (1999-10-01), Collins et al.
patent: 5963746 (1999-10-01), Barker et al.
patent: 5963975 (1999-10-01), Boyle et al.
patent: 5964886 (1999-10-01), Slaughter et al.
patent: 5966528 (1999-10-01), Wilkinson et al.
patent: 5971923 (1999-10-01), Finger
patent: 5978578 (1999-11-01), Azarya et al.
patent: 5978874 (1999-11-01), Singhal et al.
patent: 5983326 (1999-11-01), Hagersten et al.
patent: 5999734 (1999-12-01), Willis et al.
patent: 6026461 (2000-02-01), Baxter et al.
patent: 6038646 (2000-03-01), Sproull
patent: 6038651 (2000-03-01), VanHuben et al.
patent: 6041376 (2000-03-01), Gilbert et al.
patent: 6049845 (2000-04-01), Bauman et al.
patent: 6049853 (2000-04-01), Kingsbury et al.
patent: 6052760 (2000-04-01), Bauman et al.
patent: 6055617 (2000-04-01), Kingsbury
patent: 6065037 (2000-05-01), Hitz et al.
patent: 6065077 (2000-05-01), Fu
patent: 6081844 (2000
Khare Manoj
Kumar Akhilesh
Intel Corporation
Kenyon & Kenyon
Verbrugge Kevin
LandOfFree
Method and apparatus for preventing starvation in a... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for preventing starvation in a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for preventing starvation in a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2934583