US7366845B2

Pushing of clean data to one or more processors in a system having a coherency protocol

Summary by NHIP

Data push to processors

The method transmits a data push request to processors and a memory controller, then sets corresponding data to a clean state upon acceptance. The clean state is defined as a Shared state for write-back protocols or a Valid state for write-through protocols.

Claim Score by NHIP

Read claim 19, the broadest

Abstract

Techniques for pushing data to multiple processors in a clean state.

US7366845B2, drawing sheet 1 — Sheet 1 of 8

Term

Term ended

Expired 10 July 2025, 1.2 years ago.

38 claims: 8 independent, 30 dependent

1
A method comprising:transmitting to a plurality of processors and a memory controller, a request to push data from an agent external to the one or more processors;determining whether each of the processors and the memory controller has accepted the request;and if each of the processors and the memory controller have accepted the request, then for each processor having data corresponding to the data to be pushed from the agent, setting a state of the corresponding data to a clean state, if not already in a clean state, and overwriting the corresponding data with the data pushed from the agent.
10
A system comprising:a plurality of processors;a memory controller;and a bus agent coupled with each of the plurality of processors and the memory controller to transmit to the plurality of processors and the memory controller a request to push data to at least one processor and to determine whether each of the plurality of processors and the memory controller receiving the request have accepted the request;wherein if each of the processors and the memory controller have accepted the request, then for each processor having data corresponding to the data to be pushed, the processor sets a state of the corresponding data to a clean state, if not already in a clean state, and overwrites the corresponding data with the pushed data.
12
The system of 10 wherein the plurality of processors comprises a subset of processors in a multi-processor system.
19
Broadest claimClaim Score 77, broad(NHIP)An agent in an electronic system comprising:a bus interface;control circuitry coupled with the bus interface to transmit a request to push data to a plurality of processors and a memory controller over the bus interface and to determine whether each of the processors and the memory controller have accepted the request, in response to each of the processors and the memory controller accepting the request, the control circuit causing data to be transmitted to each of the processors and to the memory controller with an indication to store the data in a clean state.
20
The agent of 19 wherein at least one of the processors, after accepting the request, rejects the transmitted data.
21
The agent of 19 wherein the plurality of processors comprises a subset of processors in a multi-processor system.
26
An apparatus comprising:means for transmitting to a plurality of processors and a memory controller, a request to push data from an agent external to the one or more processors;means for determining whether each of the processors and the memory controller have accepted the request;means for setting a state of the corresponding data to a clean state, if not already in a clean state, in each processor having data corresponding to the data to be pushed from the agent, and means for overwriting the corresponding data with the data pushed from the agent if each of the processors and the memory controller have accepted the request;and means for storing the data pushed from the external agent in a clean state in each processor not having data corresponding to the data to be pushed from the agent if each of the processors and the memory controller have accepted the request.
31
A system comprising:a substantially omni-directional antenna;at least one of a plurality of processors coupled with the antenna;and a bus agent coupled with the plurality of processors and a memory controller to transmit a request to push data to at least a subset of the processors and the memory controller and to determine whether each of the processors receiving the request have accepted the request;wherein if each of the processors and the memory controller have accepted the request, for each processor having data corresponding to the data to be pushed the processor, sets a state of the corresponding data to a clean state, if not already in a clean state, and overwrites the corresponding data with the pushed data and for each processor not having data corresponding to the data to be pushed, to store the pushed data in a clean state.

Independent claims8

46 paragraphs in 5 sections, as filed

TECHNICAL FIELD

0001Embodiments of the invention relate to multi-processor computer systems. More particularly, embodiments of the invention relate to allowing bus agents to push clean data to caches corresponding to multiple processors in a coherent multi-processor computer system.

BACKGROUND

0002In current multi-processor systems, including Chip Multi-Processors, it is common for an input/output (I/O) device such as, for example, a network media access controller (MAC), a storage controller, a display controller, to generate temporary data to be processed by a processor core. Using traditional memory-based data transfer techniques, the temporary data is written to memory and subsequently read from memory by the processor core. Thus, two memory accesses are required for a single data transfer.

0003Because traditional memory-based data transfer techniques require multiple memory accesses for a single data transfer, these data transfers may be bottlenecks to system performance. The performance penalty can be further compounded by the fact that these memory accesses are typically off-chip, which results in further memory access latencies as well as additional power dissipation. Thus, current data transfer techniques result in system inefficiencies with respect to performance and power.

BRIEF DESCRIPTION OF THE DRAWINGS

0004Embodiments of the invention are illustrated by way of example, and not by way of limitation, in the figures of the accompanying drawings in which like reference numerals refer to similar elements.

0005<figref idref="DRAWINGS">FIG. 1</figref> is a block diagram of one embodiment of a computer system.

0006<figref idref="DRAWINGS">FIG. 2</figref> is a conceptual illustration of a push operation from an external agent.

0007<figref idref="DRAWINGS">FIG. 3</figref> is a flow diagram of one embodiment of a technique for pushing a full cache line to multiple target processors having cache memories in a system using a write-back coherency protocol.

0008<figref idref="DRAWINGS">FIG. 4</figref> is a flow diagram of one embodiment of a technique for pushing a full cache line to multiple target processors having cache memories in a system using a write-through coherency protocol.

0009<figref idref="DRAWINGS">FIG. 5</figref> is a flow diagram of one embodiment of a technique for pushing a full cache line to a memory controller in a system using a write-through or a write-back coherency protocol.

0010<figref idref="DRAWINGS">FIG. 6</figref> is a flow diagram of one embodiment of a technique for pushing a partial cache line to multiple target processors having cache memories.

0011<figref idref="DRAWINGS">FIG. 7</figref> is a flow diagram of one embodiment of a technique for pushing a full cache line to a memory controller in a system using a write-through or a write-back coherency protocol.

DETAILED DESCRIPTION

0012In the following description, numerous specific details are set forth. However, embodiments of the invention may be practiced without these specific details. In other instances, well-known circuits, structures and techniques have not been shown in detail in order not to obscure the understanding of this description.

0000Overview

0013In traditional cache designs having hardware support for cache coherency, a caching agent must obtain an exclusive ownership of a cache line before the agent can modify the cache line in the cache(s) controlled by the agent. Described in greater detail below, are architectures and techniques that allow external devices connected to a processor to push data directly to the processor cache(s) without the agent controlling the cache obtaining exclusive ownership of the line.

0014In one embodiment, an external (to the multiple processors having the cache memories receiving the data) agent preparing to push data to a multiprocessor system may initially notify all processors and the memory system (e.g., a memory controller) of the coming push operation. In a shared bus system, for example, notification messages may be accomplished by the processors snooping a shared address bus transaction. In a point-to-point system, notification messages may be sent to all processors as well as to the memory controller.

0015In the shared bus system there may be a single multicast data transfer that all processors and the memory controller. In point-to-point system, the data may be individually transmitted to all processors as well as to one or more memory controllers. If the request is accepted by all processors and the memory controller(s), the data to be written may be transmitted to all processors and to memory. Acceptance of the request may be determined by acknowledgement messages and/or absence of retries or stalls. It is also possible to have a shared bus for the address transactions and point-to-point connections for data transactions, and vice versa.

0016In one embodiment, in the point-to-point system, data may be individually transmitted to each processor and to memory. Each processor may write (or overwrite) data in a cache memory and update the coherency state (e.g., to Shared in a MSI/MESI/MOESI system or to Valid in a VI system). The corresponding memory location may also be updated.

0017In one embodiment, one or more of the following states may be used for coherency purposes. Modified refers to data that has been modified and is stored in a cache memory and the corresponding data in memory may not have been correspondingly modified and therefore may be invalid. Shared refers to data that may be stored by multiple cache memories and the corresponding copy in memory may be valid. Exclusive refers to data that may be stored in only one cache memory and the corresponding copy in memory may be valid. Owned refers to data that may be stored in only one cache memory and the corresponding copy in memory may be invalid. Invalid refers to data stored in a cache memory that may be invalid. Valid refers to data stored in a cache memory that may be valid.

0018<figref idref="DRAWINGS">FIG. 1</figref> is a block diagram of one embodiment of a computer system. The computer system illustrated in <figref idref="DRAWINGS">FIG. 1</figref> is intended to represent a range of computer systems. Alternative computer (or non-computer) systems can include more, fewer and/or different components.

0019In one embodiment, computer system 100 may include interconnect 110 to communicate information between components. Processor 120 may be coupled to interconnect 110 to process information. Further, processor 120 may include internal cache 122, which may represent any number of internal cache memories. In one embodiment, processor 120 may be coupled with external cache 125. Computer system 100 may further include processor 130 that may be coupled to interconnect 110 to process information. Processor 130 may include internal cache 132, which may represent any number of internal cache memories. In one embodiment, processor 130 may be coupled with external cache 135.

0020While computer system 100 is illustrated with two processors, computer system 100 may include any number of processors and/or co-processors. Computer system 100 may also include random access memory controller 140 coupled with interconnect 110. Memory controller 140 may act as an interface between interconnect 110 and memory subsystem 145, which may include one or more types of memory. For example, memory subsystem 145 may include random access memory (RAM) or other dynamic storage device to store information and instructions to be executed by processor 120 and/or processor 130. Memory subsystem 145 also can be used to store temporary variables or other intermediate information during execution of instructions by processor 120 and/or processor 130. Memory subsystem may further include read only memory (ROM) and/or other static storage device to store static information and instructions for processors 120 and/or processor 130.

0021Interconnect 110 may also be coupled with input/output (I/O) devices 150, which may include, for example, a display device, such as a cathode ray tube (CRT) controller or liquid crystal display (LCD) controller, to display information to a user, an alphanumeric input device, such as a keyboard or touch screen to communicate information and command selections to processor 120, and/or a cursor control device, such as a mouse, a trackball, or cursor direction keys to communicate direction information and command selections to processor 102 and to control cursor movement on a display device. Various I/O devices are known in the art.

0022Computer system 100 may further include network interface(s) 160 to provide access to one or more networks, such as a local area network, via wired and/or wireless interfaces. Storage device 170 may be coupled to interconnect 110 to store information and instructions.

0023Instructions are provided to memory subsystem 145 from storage device 170, such as magnetic disk, a read-only memory (ROM) integrated circuit, CD-ROM, DVD, via a remote connection (e.g., over a network via network interface 160) that is either wired or wireless, etc. In alternative embodiments, hard-wired circuitry can be used in place of or in combination with software instructions. Thus, execution of sequences of instructions is not limited to any specific combination of hardware circuitry and software instructions.

0024An electronically accessible medium includes any mechanism that provides (i.e., stores and/or transmits) content (e.g., computer executable instructions) in a form readable by an electronic device (e.g., a computer, a personal digital assistant, a cellular telephone). For example, a machine-accessible medium includes read only memory (ROM); random access memory (RAM); magnetic disk storage media; optical storage media; flash memory devices; electrical, optical, acoustical or other form of propagated signals (e.g., carrier waves, infrared signals, digital signals); etc.

0025<figref idref="DRAWINGS">FIG. 2</figref> is a conceptual illustration of a push operation from an external agent. The example of <figref idref="DRAWINGS">FIG. 2</figref> corresponds to an external (to the processor) agent that may push data to one or more processors and memory. In one embodiment, the data that is pushed by the external agent may be stored by the processors and memory in a clean state (e.g., Shared or Valid). The external agent may be, for example, a direct memory access (DMA) device or a digital signal processor (DSP).

0026As will be described in greater detail below, the data that is pushed by external agent 200 may correspond to a full cache line or the data may correspond to a partial cache line. In one embodiment, during push operation 210, external agent 200 may push data to internal cache 122 of processor 120, internal cache 132 of processor 130 and memory controller 140. The data pushed by external agent 200 then exists coherently in a clean state in the cache of each processor as well as in memory. Thus, the data may be available for a cache hit on a subsequent load to the corresponding address by any of the processors. Because the pushed data is stored in a clean state, when any of the processors replace the data, for example, as the result of a conflict or capacity miss, the replacement may be performed without a write-back operation to memory.

0000Example Push Operations for Full Cache Lines

0027<figref idref="DRAWINGS">FIG. 3</figref> is a flow diagram of one embodiment of a technique for pushing a full cache line to multiple target processors having cache memories in a system using a write-back coherency protocol. In one embodiment, a push request may be transmitted to each target agent (e.g., processor) in a system, 300. Transmission of the push request may be accomplished, for example, by a broadcast message to all processors in a multiprocessor system using a shared bus as the interconnect, or by individual messages to each processor in case of a point-to-point interconnect.

0028If the request is not accepted by all target agents, 310, a retry procedure may be performed, 320. If all target agents accept the request, 310, each target agent determines whether the cache line being pushed is present in its cache memory, 330. In one embodiment, if the cache line is present, 330, the state of the cache line may be updated to or maintained as Shared, 340. The cache line may be overwritten with data being pushed by the external agent, 350.

0029If the cache line is not present in the cache memory of the target agent, 330, the agent may allocate a cache line in the Shared state, 360. The allocated cache line may be filled with the data pushed by the external agent, 370. When the data from the external agent has been stored in the cache of the target agent (350 or 370), the data is stored in the Shared state and is available for each of the target agents.

0030<figref idref="DRAWINGS">FIG. 4</figref> is a flow diagram of one embodiment of a technique for pushing a full cache line to multiple target processors having cache memories in a system using a write-through coherency protocol. In one embodiment, a push request may be transmitted to each target agent (e.g., processor) in a system, 400. Transmission of the push request may be accomplished, for example, by a broadcast message to all processors in a multiprocessor system using a shared bus as the interconnect, or by individual messages to each processor in case of a point-to-point interconnect.

0031If the request is not accepted by all target agents, 410, a retry procedure may be performed, 420. If all target agents accept the request, 410, each target agent determines whether the cache line being pushed is present in its cache memory, 430. In one embodiment, if the cache line is present, 430, the state of the cache line may be maintained in the Valid state, 440. The cache line may be overwritten with data being pushed by the external agent, 450.

0032If the cache line is not present in the cache memory of the target agent, 430, the agent may allocate a cache line in the Valid state, 460. The allocated cache line may be filled with the data pushed by the external agent, 470. When the data from the external agent has been stored in the cache of the target agent (450 or 470), the data is stored in the Valid state and is available for each of the target agents.

0033<figref idref="DRAWINGS">FIG. 5</figref> is a flow diagram of one embodiment of a technique for pushing a full cache line to a memory controller in a system using a write-through or a write-back coherency protocol. In one embodiment, a memory controller may receive a push request that has been transmitted to all target devices in a system, 500.

0034In response to receiving the push request, the memory controller may determine whether all target devices in the system have accepted the push request, 510. If all target devices accept the push request, 510, the memory controller causes the pushed data line to be written to the appropriate memory location 530. If all target devices do not accept the push request, 510, a retry procedure may be implemented, 520.

0000Example Push Operations for Partial Cache Lines

0035<figref idref="DRAWINGS">FIG. 6</figref> is a flow diagram of one embodiment of a technique for pushing a partial cache line to multiple target processors having cache memories. In one embodiment, a push request may be transmitted to each target agent (e.g., processor) in a system, 600. Transmission of the push request may be accomplished, for example, by a broadcast message to all processors in a multiprocessor system using a shared bus as the interconnect, or by individual messages to each processor in case of a point-to-point interconnect.

0036If the request is not accepted by all target agents, 605, a retry procedure may be performed, 610. If all target agents accept the request, 605, each target agent determines whether the cache line being pushed is present in its cache memory, 620.

0037In one embodiment, if the data line is not present in the cache memory of the target agent, 620, the push attempt is rejected, 660. The agent may read the corresponding data from memory, 665. The retrieved data may be stored in the of the target agent, 670.

0038In one embodiment, if the data is present in the cache memory of the target agent, 620, the target agent may determine whether the cache line including the data is stored in a clean state, 625. If the line is stored in a clean state, the pushed, partial line of data may be merged with the existing data stored in the cache, 630.

0039If the line is not stored in a clean state, the target agent may reject the push attempt, 640. The target agent may then write the data in the dirty cache line to memory, 645. The state of the cache line may then be updated to Shared, 650.

0040<figref idref="DRAWINGS">FIG. 7</figref> is a flow diagram of one embodiment of a technique for pushing a partial cache line to a memory controller in a system using a write-through or a write-back coherency protocol. In one embodiment, a memory controller may receive a push request that has been transmitted to all target devices in a system, 700.

0041In response to receiving the push request, the memory controller may determine whether all target devices in the system have accepted the push request, 710. If all target devices accept the push request, 710, the memory controller causes the pushed, partial cache line to be written to the appropriate memory location 730. If all target devices do not accept the push request, 710, a retry procedure may be implemented, 720.

CONCLUSION

0042Reference in the specification to “one embodiment” or “an embodiment” means that a particular feature, structure, or characteristic described in connection with the embodiment is included in at least one embodiment of the invention. The appearances of the phrase “in one embodiment” in various places in the specification are not necessarily all referring to the same embodiment.

0043While the invention has been described in terms of several embodiments, those skilled in the art will recognize that the invention is not limited to the embodiments described, but can be practiced with modification and alteration within the spirit and scope of the appended claims. The description is thus to be regarded as illustrative instead of limiting.

Contents5

Every citation, both ways

Citations
Document	Relation	Office	Cited during
US8806153B2	Cited by	United States of America	Applicant
US2004002992A1	Cites	United States of America	Search report
US2005050281A1	Cites	United States of America	Search report
US2005273560A1	Cites	United States of America	Search report
US2007039002A1	Cites	United States of America	Search report
US5119485A	Cites	United States of America	Search report
US5652915A	Cites	United States of America	Search report
US5903911A	Cites	United States of America	Search report
US6842822B2	Cites	United States of America	Search report

Priority claims
Document	Office	Kind	Date
88160704	United States of America	A	2004-06-29
US20040881607	–	–	–

42 transactions on the USPTO file

Allowed after 2 non-final rejections.

Non-final rejections: 2
Final rejections: 0
RCEs: 0
Appeals: 0

Over time

Point at a mark for the transaction

Transactions

Prosecution transactions, newest first
	Event	Code
2008-06-11	Correspondence Address ChangeC.ADB	C.ADB
2008-04-29	Recordation of Patent Grant MailedPGM/	PGM/
2008-04-29	Patent Issue Date Used in PTA CalculationAllowedPTAC	PTAC
2008-04-09	Issue Notification MailedAllowedWPIR	WPIR
2008-03-12	Dispatch to FDCD1935	D1935
2008-03-12	Application Is Considered Ready for IssuePILS	PILS
2008-03-03	Issue Fee Payment VerifiedN084	N084
2008-03-03	Issue Fee Payment ReceivedIFEE	IFEE
2007-12-04	Mail Notice of AllowanceAllowedMN/=.	MN/=.
2007-11-05	Notice of Allowance Data Verification CompletedAllowedN/=.	N/=.
2007-08-16	Date Forwarded to ExaminerFWDX	FWDX
2007-08-14	Response after Non-Final ActionA...	A...
2007-05-14	Mail Non-Final RejectionNon-final rejectionMCTNF	MCTNF
2007-05-10	Non-Final RejectionNon-final rejectionCTNF	CTNF
2007-03-13	Date Forwarded to ExaminerFWDX	FWDX
2007-02-26	Response after Non-Final ActionA...	A...
2007-02-08	Mail Notice of Informal or Non-Responsive AmendmentNINA	NINA
2007-02-08	Date Forwarded to ExaminerFWDX	FWDX
2007-01-24	New or Additional Drawing FiledC614	C614
2007-01-24	Informal or Non-Responsive Amendment after Examiner ActionA.I.	A.I.
2007-01-24	Response after Non-Final ActionA...	A...
2006-10-18	Mail Non-Final RejectionNon-final rejectionMCTNF	MCTNF
2006-10-16	Non-Final RejectionNon-final rejectionCTNF	CTNF
2006-09-11	Case Docketed to Examiner in GAUDOCK	DOCK
2006-08-31	Case Docketed to Examiner in GAUDOCK	DOCK
2006-08-06	Case Docketed to Examiner in GAUDOCK	DOCK
2006-04-13	Case Docketed to Examiner in GAUDOCK	DOCK
2005-11-10	Information Disclosure Statement consideredIDSC	IDSC
2005-11-10	Information Disclosure Statement (IDS) FiledM844	M844
2005-11-10	Information Disclosure Statement (IDS) FiledWIDS	WIDS
2005-04-14	IFW TSS Processing by Tech Center CompleteTSSCOMP	TSSCOMP
2005-04-14	Case Docketed to Examiner in GAUDOCK	DOCK
2004-11-08	Application Return from OIPEWROIPE	WROIPE
2004-11-08	Application Return TO OIPEROIPE	ROIPE
2004-11-08	Application Dispatched from OIPEOIPE	OIPE
2004-11-08	Application Is Now CompleteCOMP	COMP
2004-09-03	Additional Application Filing FeesADDFLFEE	ADDFLFEE
2004-09-03	A statement by one or more inventors satisfying the requirement under 35 USC 115, Oath of the ApplicOATHDECL	OATHDECL
2004-08-16	Notice Mailed--Application Incomplete--Filing Date AssignedINCD	INCD
2004-08-09	Cleared by OIPE CSRL194	L194
2004-07-25	IFW Scan & PACR Auto Security ReviewSCAN	SCAN
2004-06-29	Initial Exam Team nnIEXX	IEXX

7 legal events, as the office reported them to INPADOC

Over the term

Point at a mark for the event

Events

Legal events, newest first
	Event	Code
2019-10-22	Maintenance fee paymentMAFP	MAFP
2015-10-21	Fee paymentFPAY	FPAY
2014-05-14	AssignmentAS	AS
2013-10-31	Fee payment procedurePAYOR NUMBER ASSIGNED (ORIGINAL EVENT CODE: ASPN); ENTITY STATUS OF PATENT OWNER: LARGE ENTITYFEPP	FEPP
2011-09-21	Fee paymentFPAY	FPAY
2008-04-09	Information on status: patent grantGrantedPATENTED CASESTCF	STCF
2004-09-03	AssignmentAS	AS