Source: http://www.google.com/patents/US8117392?dq=7,007,239
Timestamp: 2015-02-27 12:03:59
Document Index: 191695449

Matched Legal Cases: ['Application No. 200480038473', 'Application No. 200480038473', 'Application No. 10', 'Application No. 11', 'Application No. 11', 'Application No. 11', 'Application No. 10', 'Application No. 200480038473']

Patent US8117392 - Method and apparatus for efficient ordered stores over an interconnection ... - Google PatentsSearch Images Maps Play YouTube News Gmail Drive More »Sign inAdvanced Patent SearchPatentsA physically distributed cache memory system includes an interconnection network, first level cache memory slices, and second level cache memory slices. The first level cache memory slices are coupled to the interconnection network to generate tagged ordered store requests. Each tagged ordered store...http://www.google.com/patents/US8117392?utm_source=gb-gplus-sharePatent US8117392 - Method and apparatus for efficient ordered stores over an interconnection networkAdvanced Patent SearchPublication numberUS8117392 B2Publication typeGrantApplication numberUS 10/691,176Publication dateFeb 14, 2012Filing dateOct 22, 2003Priority dateOct 22, 2003Also published asCN1898653A, CN100530141C, US20050091121Publication number10691176, 691176, US 8117392 B2, US 8117392B2, US-B2-8117392, US8117392 B2, US8117392B2InventorsMark J. Charney, Ravi Rajwar, Pritpal S. Ahuja, Matthew C. MattinaOriginal AssigneeIntel CorporationExport CitationBiBTeX, EndNote, RefManPatent Citations (21), Non-Patent Citations (19), Classifications (12), Legal Events (3) External Links: USPTO, USPTO Assignment, EspacenetMethod and apparatus for efficient ordered stores over an interconnection network
US 8117392 B2Abstract
One embodiment of the invention addresses a system with a plurality of processors sharing a logically shared, but physically distributed cache. The plurality of processors communicate to the physically distributed caches over an interconnection network. The interconnection network is an unordered network that does not preserve the ordering of requests from one processor or cache (the �requester�) to the same or different caches. Additionally, the messages that one cache may send to another cache over the interconnection network are also not kept in-order by the network. However, the messages may require execution in-order as they are sent out by a requester. These messages may be referred to as ordered requests. Messages that do not require execution in-order may be referred to as non-ordered requests. A store request issued by a requester may be an ordered store request or a non-ordered store request.
In another embodiment, cache management of the logically shared cache addresses the ordering requirements that certain memory consistency models place on the processing of certain stores from a processor into main memory. Certain stores that require special in-order processing are referred to herein as �ordered stores� or �ordered store requests�. In other cases, stores may not require the special in-order processing and are referred to herein as �unordered stores�, �unordered store requests�, or �non-ordered� store requests�. These non-ordered store requests can be executed or processed out of order. The processing of ordered store requests requires that earlier ordered store requests, issued before a current ordered store request, be completely processed before execution occurs of the current ordered store request.
Upon initial execution of a program stored in the disk storage device 203 or stored in some other source such as I/O devices 102, the microprocessor 201 reads program instructions and data stored in the disk storage device 203 or other source and writes them into memory 202. One or more pages or fractions thereof of the program instructions stored within memory 202 are read (i.e. �fetched�) by the microprocessor 201 for storage into an instruction cache (not shown in FIG. 3). Some of the program instructions stored in the instruction cache may be read into an instruction pipeline (not shown) for execution by the microprocessor 201. One or more pages or fractions thereof of the data stored within memory 202 may be read (i.e. �fetched�) by the microprocessor 201 for storage into a data cache. In another embodiment, both instructions and data may be stored into the same cache memory.
Referring now to FIGS. 3A and 4, one or more of the processors 301A-301J can request that an ordered store request be performed by the physically distributed cache memory system 400. Alternatively, one or more cache memories 312A, 312B or cache memory slices at an upper level of the hierarchy of the distributed cache memory system 400 can request that an ordered store request be performed by other levels of the distributed cache memory system 400. The cache memory slices making such requests are typically closer to the processors. The cache memories making such requests may include the internal cache memories 312A of the processors or the upper level cache memories 312B. Collectively, the processors, cache memories, and cache memory slices that request ordered stores may be referred to as requesters. Each requestor has control logic and other hardware elements to generate the ordered stored requests. In the discussions that follow below, �Nc� represents the number of cache memory slices that make up the physically distributed cache and �Np� represents the number of requestors that share the distributed cache.
Each processor/cache requestor 701 has a unique requestor identifier (�RID�) 704 having a constant value of �j� and a single token register (�TR�) 706 having a variable value of �t�. The unique requestor identifier may also be referred to as unique requester identification. The token register may also be referred to as a sequence token register and the token value �t� may also be referred to as a store sequence token or a store sequence number. The token register (�TR�) 706 is �b� bits wide and can have 2b bit values depending upon the number of outstanding ordered store requests to be supported by the processor/requestor. Let �S� represent the number of outstanding ordered stores that each processor supports, then the number of bits in the token register can be determined from the equation of �b�=ceiling [log2 (S)]. The value held by the token register may also be referred to as the requestor sequence token. The token register can be incremented as ordered store requests are generated. The token register can wrap around (i.e., roll-over) back to its initial value (typically zero) when it is incremented beyond its maximum value. However in one embodiment, S is sufficiently large, as well as the number of bits �b�, in proportion to the maximum Network Latency (i.e., maximum network delay) such that by the time the token register rolls-over, a processor would have processed everything. In another embodiment, the processor/requester with the TR register which is about to roll-over polls each cache memory slice to determine if each has processed all tagged memory requests and reached S−1. If all cache memory slices respond to the processor that they are finished, the processor can then allow its given TR register to roll-over.
The value �j� of the requestor identifier (�RID�) 704 is unique. That is no two values of requestor identifiers are the same in the same multiprocessor system with a distributed cache memory system. With the value �j� of each requestor identifier (�RID�) 704 being unique, the values �t� of the token registers in each requestor 701 can be made unique by appending �j� and �t� together. That is, we can �uniqify� the token register TR, by adding the requestor identifier to the token, before it is communicated over the interconnection network to the distributed cache memory system.
Each cache memory slice in the memory hierarchy of the distributed cache memory which are capable of in-order execution of an ordered store request, such as cache memory slices 702A and 702B, has a cache sequence array (CSA) 712. The cache sequence array (CSA) 712 is a table with �Np� entries, which are �b� bits wide. The cache sequence array (CSA) 712 determines the identity of the next ordered store that can be processed by the given cache memory slice in the distributed cache system for each requester identifier (�RID�) 704. As there are Np requestors, there are Np entries in the cache sequence array (CSA) 712.
Reference is now made to FIGS. 5A-5B. FIG. 5A illustrates a diagram of typical fields of a tagged ordered store request 500. FIG. 5B illustrates a diagram of typical fields of a CSA update 510. To support ordered store requests the bit fields of requester identifier (RID) field 501 (the �j� value), a token register value field 502 (the �t� value), and the message identifier (MID) field 504 are utilized in both the tagged ordered store request 500 and the CSA update 510. The bit fields of requester identifier (RID) field 501 (the �j� value), a token register value field 502 (the �t� value) may collectively be referred to as TRU 503. That is, TRU 504 represents the concatenation of the requester id �j� and the value �t� of requestor j's token register TR. The value of TRU 504 can be denoted as �j.t� where j is the requester identifier and �t� is the value of requester j's token register TR.
If the message identifier field 504 indicates an ordered store request (OSR) code 504A of a tagged ordered store request 500, then and address field 505 and a data field 506 are included as part of the tagged ordered store request 500. In other words, the bit fields of the requestor identifier (RID) field 501 (the �j� value) and the token register value field 502 (the �t� value) are concatenated together and appended to the ordered store request code 504A which includes an address 505 and data 506 which is to be stored. In this manner, the tagged order store request 500 is formed.
If the message identifier field 504 indicates a CSA update code 504B and not an ordered store request (OSR) code 504A, then the address field 505 and the data field 506 are not included in the message sent into the distributed cache memory system 400. In this case, the bit fields of the requestor identifier (RID) field 501 (the �j� value) and the token register value field 502 (the �t� value) are based upon the ordered store request that was processed and are appended to the CSA update code 504B.
As discussed previously, each processor/cache requester 701 has a unique requester identifier (�RID�) 704 having a value of �j� and a single token register (�TR�) 706 having a value of �t�. Each processor/cache requester 701 further includes a work queue 707 to store ordered store requests (e.g., ST.REL A, ST.REL B) and control logic 708 to control the generation of the tagged ordered store request 500 and hash or translate the address to select the appropriate cache memory slice and memory cells therein.
In operation, requestor j 701 generates a tagged ordered store request 500 using an address of one of the ordered store request found within the queue 707, appending the requester ID j and the current token register value t. The controller 708 of the requestor j 701 issues the tagged ordered store request 500. The ordered store request is tagged with the value �j.t�. At time X, the tagged ordered store request for ST.REL A is sent to the cache slice k 702A as indicated by arrow 721. Within requestor j 701, after the tagged ordered store request for ST.REL A is sent to the cache slice k 702A, the token register 706 is incremented to a value of (t+1).
Assume for example that requester j 701 has two ordered store requests denoted �ST.REL A� and �ST.REL B� that it is ready to tag and issue as tagged ordered store requests into the physically distributed cache memory system to different addresses �A� and �B�. The ordered store request �ST.REL A� is older than the ordered store request �ST.REL B� and should be processed first to achieve in-order execution. However with the different addresses �A� and �B�, the two ordered store requests �ST.REL A� and �ST.REL B� will be processed by different partitions, cache memory slice k 702A and cache memory slice m 702B of the physically distributed cache memory system.
Requestor j 701 first issues a tagged ordered store request to cache memory slice k 702A with the ordered store request �ST.REL A� being tagged with �j.t� as indicated by arrow 721. When cache memory slice k 702A processes this tagged ordered store request it performs the store and then an update. That is, cache memory slice k 702A broadcasts out cache sequence array (CSA) update having �j.x� to all other cache memory slices as indicated by arrow 722. The value of x=t+1. The cache memory slice k 702A increments its own CSA[j] entry corresponding to the requestor j in order to perform the CSA update therein.
Upon receiving the tagged ordered store request for ST.REL A, cache memory slice k 702A determines whether or not it can execute the tagged ordered store request in-order. To do so, the cache slice k 702A looks to its cache sequence array (CSA) 712 and the entry for requester j 701. How a cache memory slice k 702A determines whether or not it can execute a tagged ordered store request in-order is described further below with reference to FIGS. 9A and 9B. Assuming the cache memory slice k 702A determines it can execute the tagged ordered store request in-order, it does so. After the cache memory slice k 702A has processed or executed the tagged ordered store request for ST.REL A, the value of t is incremented to (t+1) and appended with the requestor ID j to generate and issues a CSA update 510 with the value j.t+1 to all other cache memory slices. Arrows 722 indicate the CSA update being sent to all other cache memory slices including the cache memory slice m 702B. This indicates to caches that have received the CSA update, that they can then process a tagged ordered store request having a �j.t+1� value.
Continuing with the example, at time X+e where e is positive, Requestor j issues the tagged ordered store request including the ordered store request �ST.REL B� tagged with �j.(t+1)� to cache memory slice m 702B as indicated by arrow 723. Within requestor j 701, after the tagged ordered store request for ST.REL B is sent to the cache slice m 702B, the token register 706 is incremented to a value of (t+2).
The cache memory slice m 702B checks to see if its entry for CSA[j] for requester j in the CSA 712 is equal to (t+1). Assuming in this case that cache memory slice k 702A has already processed the ordered store request �ST.REL A� and cache memory slice 702B m received the corresponding CSA update, then cache memory slice 702B m (300) can process the �ST.REL B� as its entry for CSA[j] for requester j is equal to (t+1).
However, now assume that requester j issues the ordered store request �ST.REL B� before the CSA update from the cache memory slice k 702A reaches cache memory slice m 702B, then cache memory slice m 702B m holds on to the tagged ordered store request that includes �ST.REL B� in a network or local buffer until that CSA update with the token �j.x� arrives. In this case, the CSA update is out of order and the cache memory slice has to appropriately handle the ordered store requests it has for processing.
Assuming the cache memory slice m 702B determines it can execute the tagged ordered store request in-order, it does so. After the cache memory slice m 702B has processed or executed the tagged ordered store request for ST.REL B, the value of (t+1) is incremented to (t+2) and appended with the requester ID j to generate and issue a CSA update 510 with the value j.t+2 to all other cache memory slices. Arrows 724 indicate the CSA update being sent to all other cache memory slices including the cache memory slice m 702A. This indicates to caches that have received the CSA update, that they can then process a tagged ordered store request having a �j.t+2� value.
Assuming the cache memory slice m 702B had not received a CSA update with a value of �j.t+1�, it would have been unable to execute a tagged ordered store request with a value of �j.t+1� in order. The cache memory slice m 702B would have had to wait until receiving a CSA update with a value of �j.t+1� before it could execute a tagged ordered store request with a value of �j.t+1�.
Referring now to FIG. 8, a flow chart of control functions performed by the control logic 708 of requestor j 701 to support tagged ordered store requests. In this discussion, as was discussed previously; the number �Np� represents the number of processors that share the distributed cache.
At 800, the system is initialized or reset. At 802, all processor and cache requesters j 701 set their token registers TR 706 and the token value �t� to a starting value, such as zero. As will be discussed further below, all entries of the cache sequence array in each cache memory slice, such as cache sequence array 712 in cache memory slices 702A, 702B, are similarly set to the same initial starting value for �t�, such as zero.
At 806, the ordered store request is tagged with the current value of the TRU tag 503 including the RID �j� 501 and the token register value �t� 502 as illustrated in FIG. 5A. The value of the TRU tag 503 is denoted as �j.t�. The control logic then goes to 808.
Referring now to FIG. 9A, a flow chart of control functions performed by the control logic 714 of each cache memory slice is illustrated for determining whether or not ordered store requests can be processed. At 900, the system is initialized or reset as was previously discussed at 800. At 902, all entries of the cache sequence array 712 in each cache memory slice are set to an initial starting value for �t�, such as zero. This matches the starting token value �t� that each requester j 701 has for its token register TR 706. The control logic then goes to 904.
At 906, the TRU tag j.t is extracted from the tagged ordered store request to determine if the ordered store request can be processed by the given cache memory slice. For the value of the received requestor identifier �j�, the cache memory slice reads the cache sequence entry for the processor that made the ordered store request value, the value CSA [j] where j takes on values from 0 through (S−1), assuming a start value of zero. Recall that �S� represents the number of outstanding ordered stores that each processor supports.
At 908, the CSA[j] entry, the expected sequence number, for the requester j is compared with the �t� part of the tag in the ordered store request. If CSA [j] matches the �t� part of the tag in the ordered store request, then the request can be processed. If CSA [j] does not equal the �t� part of the tag, the tag does not match, and the control logic goes to 913. If CSA [j] equals the �t� part of the tag, the tag does matches, and the control logic goes to 912.
When a cache memory slice receives the tag updates in the CSA update messages out of sequence�say it receives tag update j.t+5 before it receives tag updates j.t+1, j.t+2, j.t+3, and j.t+4�some other cache memory slice had to have received j.t+1 in-order to generate j.t+2 and to trigger j.t+3, and so on in-order to trigger the issuance of a tag update j.t+5. So if a cache memory slice receives a tag update j.t+n without receiving the earlier updates, it is safe for a cache to process all ordered stores up to and including j.t+n upon receipt of the tag update j.t+n.
The addition operation of t+n is performed modulo 2b, where b is the number of bits in the counter part of the tag. Due to the counter having a limited number of b bits, the addition operation may exceed the maximum counter value and rollover to a lower value. Care should be taken to avoid negative effects of a rollover condition. In one embodiment, the number of bits �b� is sufficient in proportion to the maximum Network Latency (i.e., maximum network delay) such that by the time the token register rolls-over, a processor would have processed all prior ordered store requests. In another embodiment, the processor/requester with the TR register which may roll-over polls each cache memory slice to determine if each has processed all tagged memory requests and reached S−1. If all cache memory slices respond to the processor that they are finished, the processor can then allow its given TR register to roll-over.
The TR counter in each requestor is of a limited number of bits, �b� bits, and it correspondingly generates tags with �b� bits. That is, the maximum counter value and �t� of a tag is 2b−1
At 972, the control logic updates the current entry into the cache sequence array table by setting CSA[j] equal to t. Next at 974, the control logic causes the cache memory slice to process any pending ordered store requests with a tag of �j.t�. After processing the ordered store requests, at 980 the control logic returns to 952 to wait and receive the next update.
Patent CitationsCited PatentFiling datePublication dateApplicantTitleUS5347648 *Jul 15, 1992Sep 13, 1994Digital Equipment CorporationDigital computer systemUS5579504 *Mar 17, 1995Nov 26, 1996Digital Equipment CorporationMulti-processor computer system having shared memory, private cache memories, and invalidate queues having valid bits and flush bits for serializing transactionsUS5751995Jan 18, 1996May 12, 1998Intel CorporationApparatus and method of maintaining processor ordering in a multiprocessor system which includes one or more processors that execute instructions speculativelyUS5778434 *Jun 7, 1995Jul 7, 1998Seiko Epson CorporationSystem and method for processing multiple requests and out of order returnsUS5930822Sep 27, 1996Jul 27, 1999Hewlett-Packard Co.Method and system for maintaining strong ordering in a coherent memory systemUS6122714 *Oct 24, 1997Sep 19, 2000Compaq Computer Corp.Order supporting mechanisms for use in a switch-based multi-processor systemUS6311253Jun 21, 1999Oct 30, 2001International Business Machines CorporationMethods for caching cache tagsUS6334159 *Dec 22, 1998Dec 25, 2001Unisys CorporationMethod and apparatus for scheduling requests within a data processing systemUS6389468 *Mar 1, 1999May 14, 2002Sun Microsystems, Inc.Method and apparatus for distributing network traffic processing on a multiprocessor computerUS6418525Jan 29, 1999Jul 9, 2002International Business Machines CorporationMethod and apparatus for reducing latency in set-associative caches using set predictionUS6529999Oct 27, 1999Mar 4, 2003Advanced Micro Devices, Inc.Computer system implementing system and method for ordering write operations and maintaining memory coherencyUS6594734Dec 20, 1999Jul 15, 2003Intel CorporationMethod and apparatus for self modifying code detection using a translation lookaside bufferUS6622214 *Jan 12, 1999Sep 16, 2003Intel CorporationSystem and method for maintaining memory coherency in a computer system having multiple system busesUS7032076Sep 16, 2002Apr 18, 2006Intel CorporationPrefetching data in a computer systemUS7058049 *Mar 8, 2002Jun 6, 2006Semiconductor Technology Academic Research CenterLoad store queue applied to processorUS7127562 *Jun 11, 2003Oct 24, 2006International Business Machines CorporationEnsuring orderly forward progress in granting snoop castout requestsUS7366847 *Feb 6, 2006Apr 29, 2008Azul Systems, Inc.Distributed cache coherence at scalable requestor filter pipes that accumulate invalidation acknowledgements from other requestor filter pipes using ordering messages from central snoop tagUS7644237 *Feb 20, 2004Jan 5, 2010Mips Technologies, Inc.Method and apparatus for global ordering to insure latency independent coherenceUS7856534 *Jan 15, 2004Dec 21, 2010Hewlett-Packard Development Company, L.P.Transaction references for requests in a multi-processor networkUS20020087815Dec 30, 2000Jul 4, 2002Arimilli Ravi KumarMicroprocessor reservation mechanism for a hashed address systemJPH06214875A Title not available* Cited by examinerNon-Patent CitationsReference1Cheong, H., et al., "A Version Control Approach To Cache Coherence," Proceeding of the International Conference on Supercomputing 89, pp. 322-330 (18989.06.30).2CMOS BiCMOS Data Book, Cypress Semiconducotor, 2 � 4096 � 16 Cache RAM, pp. 2-185-2-192, San Jose, CA. Feb. 1, 1989.3First Office Action from counterpart China Patent Application No. 200480038473.5, mailed Oct. 10, 2007, 1 page.4Gharachorlon, K., et al., "Memory Consistency and Event Ordering in Scalable Shared-Memory Multiprocessors," IEEE, 1990.5H. Cheong & A. Veidenbaum, "A Version Control Apporach to Cache Coherence," Proceedings of the International Conference on Supercomputing 89, Jun. 1989, pp. 322-330.6I. Tartalia et al., "A Survey of Software Solutions for Maintenance of Cache Consistency in shared Memory Multiprocessors," Proceedings of the 28th Annual Hawaii Int'l Conference on System Sciences, 1995, pp. 272-282.7Intel IXP1200 Network Processor Datasheet, pp. 9, 10, & 55, 2001.8Intel IXP1200 Network Processor Family, The Goundation of a Total Development Environment for Next-Generation Networks, Product Brief, Order No. 279040-001, 2001.9Jim Handy, The Cache Memory Book, pp. 140-158, Academic Press, Inc. San Diego, CA 1993.10John L. Hennessy, David A. Patterson, Computer Architecture, A Quantitative Approach, Third Edition, 2003, Chapter 5: pp. 389-406; Chapter 6: pp. 527-540; Chapter 8: pp. 787-802, Morgan Kaufmann Publishers, San Francisco, California USA.11K. Gharachorloo et al., "Memory Consistency and Event Ordering in Scalable Shared-Memroy Multiprocessors," Computer Systems Laboratory, Stanford University, CA 94305, May 28, 1990, pp. 15-26.12Notice of Grant of Patent Right For Invention Office Action from counterpart China Patent Application No. 200480038473.5, mailed Apr. 20, 2009, 2 pages.13Notice of Preliminary Rejection from counterpart German Patent Application No. 10-2006-7007706, mailed Aug. 21, 2007, 8 pages.14Office Action from counterpart German Patent Application No. 11 2004 001 984.2-53, mailed Feb. 19, 2008, 7 pages.15Office Action from counterpart German Patent Application No. 11 2004 001 984.2-53, mailed May 10, 2010, 5 pages.16Office Action from counterpart German Patent Application No. 11 2004 001 984.2-53, mailed Sep. 17, 2007, 6 pages.17Office Action from counterpart Japan Patent Application No. 10-2006-7007706, mailed Jan. 12, 2010, 12 pages.18Tartalja, I., et al., "A Survey of Software Solutions for Maintenance of Cache Consistency," Proceedings of the 28th Annual Hawaii International Conference on System Sciences-1995, pp. 272-278.19Third Office Action from counterpart China Patent Application No. 200480038473.5, mailed Mar. 21, 2008, 1 page.Classifications U.S. Classification711/122, 711/144, 711/119, 711/141, 711/118International ClassificationG06F13/42, G06F12/08, G06F13/00Cooperative ClassificationG06Q30/0601, G06F12/0813European ClassificationG06F12/08B4N, G06Q30/0601Legal EventsDateCodeEventDescriptionAug 5, 2014CCCertificate of correctionSep 22, 2011ASAssignmentEffective date: 20031020Free format text: CORRECTIVE ASSIGNMENT TO CORRECT THE ASSIGNOR: CARNEY, MARK J. PREVIOUSLY RECORDED ON REEL 014631 FRAME 0830. ASSIGNOR(S) HEREBY CONFIRMS THE CHARNEY, MARK J.;ASSIGNOR:CHARNEY, MARK J.;REEL/FRAME:026953/0674Owner name: INTEL CORPORATION, CALIFORNIAOct 22, 2003ASAssignmentOwner name: INTEL CORPORATION, CALIFORNIAFree format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNORS:CARNEY, MARK J.;RAJWAR, RAVI;AHUJA, PRITPAL S.;AND OTHERS;REEL/FRAME:014631/0830;SIGNING DATES FROM 20031020 TO 20031021Free format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNORS:CARNEY, MARK J.;RAJWAR, RAVI;AHUJA, PRITPAL S.;AND OTHERS;SIGNING DATES FROM 20031020 TO 20031021;REEL/FRAME:014631/0830RotateOriginal ImageGoogle Home - Sitemap - USPTO Bulk Downloads - Privacy Policy - Terms of Service - About Google Patents - Send FeedbackData provided by IFI CLAIMS Patent Services