JP2007509439A - Method and apparatus for efficient sequence preservation in interconnected networks - Google Patents

Abstract

The physical distributed cache memory system has an interconnect network, a first level cache memory slice, and a second level cache memory slice. The first level cache memory slice is coupled to the interconnect network and generates a tagged order preservation request. Each tagged sequence save request has a tag with a requester identification and a save sequence token. The second level cache memory slice is coupled to the interconnect network and executes the save order request sequentially through the physical cache memory system in response to each tag in the tagged save order request.

Description

  The present invention relates generally to cache memory management, and more particularly to providing order storage for shared distributed cache memory systems in unordered networks.

  It is well known to use a high speed cache memory between the processor and the low speed main memory to improve the average access time to the low speed main memory. The use of cache memory can improve the execution performance of the processor. Initially, the cache memory was separate from the processor, but later became an integral part of the processor as technology improved. When the cache memory becomes an integral part of the processor, the access time to the cache memory can be further reduced.

  Multiple levels of cache memory are incorporated between the processor and main memory. In general, as the speed of the cache memory increases, the cache memory becomes closer to the processor, but its size decreases. When interpreted differently, the size of the cache memory generally increases, and as the access time increases, the cache memory moves away from the processor. However, multiple levels of cache memory complicate cache management, especially when instructions branch or jump to addresses to other instructions or memory.

  A memory controller or cache controller internal or external to the processor is used to provide cache management of the cache memory between the main memory and the processor. Various cache memories to maximize the use of cache memory and reduce the number of cache misses required for the processor to read data / instructions from the slow main memory or write data / instructions to the slow main memory Management algorithms are incorporated. A cache coherence protocol has been introduced to maintain the consistency of data stored in cache memory by tracking the state of data blocks that can be shared. Other cache memory management algorithms are also incorporated.

  In the following detailed description of the present invention, numerous specific details are set forth in order to provide a thorough understanding of the present invention. However, it will be apparent to those skilled in the art that the present invention may be practiced without these specific details. In other instances, well-known methods, procedures, components, and circuits have not been described so as not to obscure aspects of the present invention unnecessarily.

  One embodiment of the present invention deals with systems with multiple processors that share a logically shared but physically distributed cache. The plurality of processors communicate with caches that are physically distributed over the interconnect network. An interconnect network is an unordered network that does not preserve the order of requests from one processor or cache ("requester") to the same or different caches. In addition, messages that can be sent from one cache to another in an interconnected network are also not kept in order by the network. However, the messages may need to be executed in the order in which they are sent by the requester. These messages are sometimes referred to as ordered requests. Messages that do not need to be executed in order may be referred to as non-ordered requests. The storage request issued by the requester may be an order storage request or an unordered storage request.

  A subset of order requests are order preservation requests. The order saving request described further below is a requesting side saving request that needs to be executed in order with respect to other order saving requests issued by the requesting side. The previous save order request must be processed before the current save order request is processed. That is, the current save order request must be processed before a subsequent save order request is processed. An unordered save request is a save request on the request side that can be executed out of order with respect to other order requests on the request side.

  A logically shared cache memory may be partitioned such that a particular address block of the cache memory is managed by different chunks of the physically distributed cache memory.

  In other embodiments, cache management of logically shared caches addresses the ordering requirement that a specific memory consistency model is set for a specific save operation from the processor to main memory. A particular store that requires a special order of processing is referred to herein as an “ordered store” or “ordered store request”. In addition, the storage may not require a special ordering process, in this case “unordered store”, “unordered store request” or “non-ordered storage request (non- ordered store request) ”. These unordered storage requests can be executed or processed in a discrete order. Processing the save order request requires that the previous save order request issued prior to the current save order request be completely processed before execution of the current save order request.

  A simple low performance method of processing a save order request from one processor is that the processor issues a new save order request until all previous save order requests from the processor are processed by the cache memory system. Suppression. However, it is not so simple in a multiprocessor system that processes order preservation requests from a plurality of processors. The method of processing order preservation requests from multiple processors in a multiprocessor system is further complicated.

  In an embodiment of the present invention, a simple low performance method of processing order preservation requests provided a shared memory system by using a small amount of additional request tracking hardware to support a multiprocessor system. This is improved by adding multiple processors to use parallel processing in a network of processors. In another embodiment of the present invention, parallel processing of network processors can process multiple order preservation requests from one processor of the network at the same time or overlapping time intervals. One processor does not have to wait for the previous order save to complete completely before sending a new order save request to the cache system over the unordered network.

  Referring to FIG. 1, a block diagram of a general computer system 100 in which the present invention can be used is illustrated. The computer system 100 includes a central processing unit (CPU) 101, an input / output device (I / O) 102 (keyboard, modem, printer, external storage device, etc.), and a monitor device (M) 103 (CRT or graphic display, etc.) And a memory 104 for storing information. The monitor device (M) 103 provides computer information in a human readable format such as a visual or auditory format. The system 100 may be a plurality of different systems including a network processing system such as a media access controller (MAC) or a computer system.

  Referring to FIG. 2A, a block diagram of a central processing unit 101A in which embodiments of the present invention can be used is illustrated. The central processing unit 101A includes a microprocessor 201, a main memory 202 for storing program instructions, and a disk storage device 203, which are coupled as illustrated. The microprocessor 201 includes one or more execution units 210, at least one cache memory 212, and a cache controller 214. Microprocessor 201 may have a separate memory controller 216 for controlling access to main memory 202. In this case, the memory controller interfaces the other elements of the microprocessor 201 with the main memory 202. Ideally, the execution unit 210 reads / writes data to the cache memory 212 without having to access the low speed main memory 202 directly. That is, it is desirable for the execution unit to avoid mistakes in the cache memory 212. There is a physical limit on the size of the cache memory 212. However, in a multiprocessor system, the system can be designed such that the cache memory 212 within each processor can be logically shared. In another embodiment, in addition to one or more internal cache memories in a processor, one or more external cache memories are provided and may be logically shared by multiple processors in an interconnect network of a multiprocessor system. Good.

  The disk storage device 203 may be a floppy disk, ZIP disk, DVD disk, hard disk, rewritable optical disk, flash memory, or other nonvolatile storage device. The microprocessor 201 and the disk storage device 203 can read / write information from / to the memory 202 via the memory bus. Thus, the microprocessor 201 and the disk storage device 203 can change the memory location in the memory 202 during program execution. In order to do this directly, the disk storage device 203 has a disk controller with direct memory access, which can perform a save to memory and thereby change the code. The controller is an example of a direct memory access (DMA) agent because it can directly access the memory. Other devices that have direct access to store information in memory are also DMA agents. The memory 202 is typically dynamic random access memory (DRAM), but may be other types of rewritable storage devices.

  Upon initial execution of a program stored in disk storage device 203 or other source (I / O device 102), microprocessor 201 reads program instructions and data stored in disk storage device 203 or other source, and Is written into the memory 202. One or more pages of program instructions or portions thereof stored in memory 202 are read (ie, “fetched”) by microprocessor 201 for storage in 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 of data stored in the memory 202 or portions thereof may be read (ie, “fetched”) by the microprocessor 201 for storage in the data cache. In other embodiments, both instructions and data may be stored in the same cache memory.

  Referring to FIG. 2B, a block diagram of a multiprocessor system 101B in which embodiments of the present invention can be used is illustrated. The multiprocessor system 101B may be a multiprocessor central processing unit. The multiprocessor system 101B has a plurality of processors 201A-201J. Each of the plurality of processors 201A-201J includes one or more execution units 210A-201N. An execution unit is sometimes called a core. Each of the plurality of processors 201A-201J may further include one or more levels of internal cache memory slices (CMS) 212A-212M coupled to one or more execution units 210A-210J. . Each of the plurality of processors 210A-210J may be coupled to an I / O device and / or a monitor device.

  Multi-processor system 101B further includes one or more levels of external cache memory slices (CMS) 212A'-212L 'coupled to each other through an interconnect network and coupled to multiple processors 201A-201J. Have. Multiprocessor system 101B may further include one or more main memories 202A-202K coupled to interconnect network 250 and a disk storage device 203 coupled to interconnect network 250.

  The processors 202A-201J, the cache memory slices 212A'-212L ', and the disk storage device 203 may directly read / write information from / to the main memories 202A-202K. That is, the main memories 202A-202K can be shared by the processors 202A-201J, the cache memory slices 212A'-212L ', and the disk storage device 203. Further, messages may be communicated between the processors 202A-201J, main memory 202A-202K, cache memory slices 212A'-212L ', and disk storage device 203 through the interconnect network 250. By using messaging in the interconnect network 250, the multi-processor system 101B may be provided with the execution or processing of the order of order preservation requests.

  Referring to FIG. 3A, a block diagram of a multiprocessor system 101C is shown. The multiprocessor system 101C includes a primary interconnect network 300A, a plurality of processors 301A-301J each having an internal cache memory 312A, and one or more processors coupled between the plurality of processors 301A-301J and the interconnect network 300A. Primary level through higher level cache memory 312B, level of cache memory slice 312C coupled to interconnect network 300A, other level of cache memory slice 312D coupled to interconnect network 300A, and secondary interconnect network 300B And other levels of cache memory slice 312E coupled to interconnect network 300A.

  The multiprocessor system 101C may further include one or more main memories 302A, 302B and / or 302C. Main memory 302A may be directly coupled to primary interconnect network 300A. Main memory 302B may be coupled to primary interconnect network 300A through secondary interconnect network 300B. Main memory 302C may be coupled to low level cache memory slice 312E and primary interconnect network 300A through secondary interconnect network 300B.

  Internal cache memory 312A, one or more higher level cache memories 312B, cache memory slice 312C levels, cache memory slice 312D levels and cache memory slice 312E levels are physically distributed multi-level cache memory System embodiments may be formed. An embodiment of a physically distributed multi-level memory system comprises main memories 302A, 302B included in a cache memory slice.

  The processor, cache memory slice and main memory may be considered as nodes of the interconnect network. Messages may flow from one node to other nodes through the interconnection network and may be broadcast from one node to all other nodes. The topology of the multiprocessor system 101C and the interconnection networks 300A and 300B includes a bus network topology, a tree network topology, a ring network topology, a grid or mesh network topology, a torus network topology, a hypercube network topology, and all connections. It may be a type topology or a combination thereof.

  Interconnect networks 300A and 300B may be one or more switches between wire traces routed in an integrated circuit, buses routed in the same integrated circuit, and / or functional blocks of the same integrated circuit. . Alternatively, interconnect networks 300A and 300B may be wire traces routed between integrated circuits, buses between integrated circuits, and / or one or more switches between integrated circuits. Switches, bridges or routers (not shown) may be used to interconnect the primary interconnect network 300A and the secondary interconnect network 300B, so that messages may be passed around accordingly. .

  Because messages flow through the interconnect network, they may experience different delays when routed from node to node or when routed from node to all nodes. These different delays can cause an unordered sequence of message transfers. That is, the interconnection network is an unordered network when processing an order storage request.

  Referring to FIG. 3B, a block diagram of a multiprocessor system 101C 'is shown. FIG. 3B shows that the majority of the system 101C ′ of FIG. 3A, including the primary interconnect network 300A, may be part of a single monolithic integrated circuit (IC) chip 350. That is, except for the main memory 302C, the elements of the system 101C may be integrated into a single silicon chip 350 as shown in the system 101C '.

  Referring to FIG. 3C, a block diagram of a multiprocessor system 101C '' is shown. FIG. 3C illustrates that system 101C may be partitioned across integrated circuit boundaries in a primary interconnect network 300A that is part of a plurality of integrated circuit (IC) chips 360A-360B. The elements of the system 101C may be integrated into a plurality of silicon chips. Alternatively, the elements of the multi-processor system 101C '' may be one or more printed circuit boards that are electrically coupled together, such as through a common backplane or printed circuit board (PCB) traces.

  Referring to FIG. 4, a logical diagram of a block diagram of a physical distributed cache memory system 400 is illustrated. The physical distributed cache memory system 400 receives the message with the hash address in the address hash control logic 404 for generating the hash address and the primary interconnection network 300A or the primary interconnection network 300A and the secondary interconnection network 300B. One or more cache memory slices 412A-412K. Each of the one or more cache memory slices 412A-412K has one or more blocks of memory cells 414A-414K.

  The physical distributed cache memory system 400 is shared by requesters such as processors or cache memory. The physical distributed cache memory system 400 can be in a number of ways so that one address block of memory cells is associated with one cache memory slice and the next address block of memory cells is associated with another cache memory slice. It may be divided. Address 402 from the requester is hashed by address hash logic 404 to select a cache memory slice and one or more blocks of that memory cell.

  Referring to FIGS. 3A and 4, one or more processors 301A-301J may request that an order preservation request be executed by the physical distributed cache system 400. Alternatively, one or more cache memories 312A, 312B or a higher level cache memory slice in the hierarchy of distributed cache memory system 400 may require an order preservation request to be performed by another level of distributed cache memory system 400. can do. The cache memory slice that makes such a request is generally near the processor. The cache memory that makes such a request may include the internal cache memory 312A or the upper level cache memory 312B of the processor. The processor, cache memory, and cache memory slice that require order preservation may be collectively referred to as a requester. Each requester has control logic and other hardware elements that generate an order preservation request. In the following description, “Nc” represents the number of cache memory slices constituting the physical distributed cache, and “Np” represents the number of requesters sharing the distributed cache.

  Referring temporarily to FIG. 7, the cache memory slices 702A and 702B at different levels of the memory hierarchy, in which the processor / cache requester 701 at one level of the memory hierarchy can execute the order of the order preservation requests, Shown to communicate.

Each processor / cache requester 701 has a unique requestor identifier (“RID”) 704 having a constant value of “j” and a single token register (“TR” having a variable value of “t”. : Token register ”) 706. The unique requester identifier may also be referred to as a unique requester identification. The token register may be referred to as a sequence token register, and the token value “t” may also be referred to as a stored sequence token or stored sequence number. The token register ("TR: token register") 706 is "b" bits wide and may have 2 ^b bits wide, depending on the number of outstanding order preservation requests supported by the processor / requester. it can. Assuming that “S” represents an outstanding order preservation request supported by each processor, the number of bits in the token register can be determined from the equation “b” = ceiling [log ₂ (S)]. The value held by the token register may also be referred to as the requester sequence token. The token register may be incremented each time a save order request is generated. When the token register increases beyond its maximum value, it can wrap around (ie, roll over) back to its initial value (generally 0). However, in one embodiment, S is sufficiently large and the number of bits in “b” is sufficiently large compared to the maximum network latency (ie, maximum network delay). Thereby, the processor is processing everything by the time the token register rolls over. In another embodiment, the processor / requestor with the TR register that is about to roll over polls each cache memory slice, and each has processed all tagged memory requests and has reached S-1 Decide whether or not. When responding to the processor that all cache memory slices are finished, the processor may allow that given TR register to roll over.

  The value “j” of the requesting identifier (“RID: requestor identifier”) 704 is unique. That is, the two values of the requester identifier are not the same in the same multiprocessor system in a distributed cache memory system. Since the value “j” of each requesting identifier (“RID”) 704 is unique, the token register value “t” of each register 701 is obtained by adding “j” and “t” together. Can be unique. That is, the token register TR can be made “unique” by adding a requestor identifier to the token before being communicated to the distributed cache memory system over the interconnect network.

  Each cache memory slice (cache memory slices 702A and 702B, etc.) of the memory hierarchy of the distributed cache memory that can execute the order of the order saving request is provided with a cache sequence array (CSA) 712. Have. The cache sequence array (CSA) 712 is a table having entries of “Np” having a “b” bit width. The cache sequence array (CSA) 712 determines, for each requesting identifier (“RID”) 704, the next order-save identification that can be processed by a given cache memory slice of the distributed cache system. Since there are Np requesters, there are Np entries in the cache sequence array (CSA).

  Reference is made to FIGS. 5A-5B. FIG. 5A shows a general field diagram of a tagged sequence preservation request 500. FIG. 5B shows a general field diagram of CSA update 510. To support order preservation requests, a requester identifier (RID) field 501 (value of “j”), a token register value field 502 (value of “t”), and a message identifier (MID) message field The bit field 504 is used in both the tagged order storage request 500 and the CSA update 510. The bit field of the requesting identifier (RID) field 501 (value of “j”) and the token register value field 502 (value of “t”) may be collectively referred to as TRU 503. That is, the TRU 504 represents a connection between the request side id “j” and the value “t” of the token register TR of the request side j. The value of TRU 504 can also be displayed as “j.t”. Here, j is a request side identifier, and “t” is the value of the token register TR of the request side j.

  The message identifier (MID) field 504 is a code indicating an ordered store request (OSR) 504A or CSA update 504B. Other codes for message identifier (MID) field 504 may be used to indicate other message formats.

  If the message identifier field 504 indicates an order preservation request (OSR) code 504A of the tagged preservation request 500, an address field 505 and a data field 506 are included as part of the tagged order preservation request 500. In other words, the requester identifier (RID) field 501 (value of “j”) and the bit field of the token register value field 502 (value of “t”) are concatenated together, and the stored address 505 and data 506 Is added to the order storage request code 504A. In this way, the tagged order storage request 500 is formed.

  If the message identifier field 504 indicates a CSA update code 504B and does not indicate an order preservation request (OSR) code 504A, the address field 505 and the data field 506 are not included in the message sent to the distributed cache memory system 400. In this case, the bit field of the request side identifier (RID) field 501 (value of “j”) and the token register value field 502 (value of “t”) is based on the processed order storage request and the CSA update code 504B. To be added.

  In one embodiment, the tagged bit order save request 500 and the data bit field of the CSA update 510 are transmitted from the requestor to the cache memory slice or from one cache memory slice to another cache memory slice in the interconnect network 300A, 300B. A packet may flow to the slice. In other embodiments, the tagged sequence save request 500 and the data bit field of the CSA update 510 may flow in parallel on the parallel interconnect bus of the interconnect network. In other embodiments, the tagged order preservation request 510 and the data bit field of the CSA update 510 may flow continuously over the serial interconnection of the interconnection network. In yet other embodiments, the tagged order preservation request 500 and the data bit field of the CSA update 510 may flow in a combination of one or more packets in parallel or serial in the interconnect network. In addition, a tagged order save request 500 is generated by the requester and sent to the interconnect network, and a CSA update 510 is generated by the cache memory slice that performed the order save request and sent to the interconnect network.

  With reference to FIG. 6A, a block diagram of a cache memory slice 602 is illustrated. Cache memory slice 602 shows a single instance of a cache memory slice. The cache memory slice 602 includes a cache sequence array 604 and cache control logic 606 that supports execution of the order of order preservation requests. The cache control logic 606 can also provide general cache control functions associated with cache memory. Cache memory slice 602 includes request buffer 608, cache tag bits 610, cache data array 612, tag matching logic 614, column selection 616, coupled together as illustrated in FIG. 6A. It has further.

  The request buffer 608 temporarily holds a cache storage request for processing in the queue. Generally, the cache tag bit 610 is an upper address bit that helps to identify the contents of the cache line of the memory cell along with the valid bit and other status bits. Cache data array 612 is an array of memory cell rows and columns for storing data. Tag matching logic 614 determines whether there is a hit or miss in a given cache memory slice. A hit indicates that the desired data is stored in the cache data array 612 for a given cache memory slice. A miss indicates that the desired data is not stored in the cache data array 612 and the request needs to be passed to the next level in the hierarchy of the distributed cache memory system. Column selection 616 responds to hit and miss indications as to whether a column of memory cells should be selected from cache data array 612.

  The cache sequence array 604 allows the cache memory slice 602 to execute order preservation requests sequentially through the physical distributed cache memory system. The cache sequence array 604 stores one or more save sequence tokens associated with one or more save order requests as cache sequence entries.

  Referring to FIG. 6B, a block diagram of a cache sequence array (CSA) 604 is illustrated. The cache sequence array (CSA) 604 has a cache sequence array (CSA) table 632. A cache sequence array (CSA) table 632 stores a storage sequence token t for each requester j. The requester identifier j serves as an address to the cache sequence array (CSA) table 632, thereby sending the addressed data to the cache control logic 606.

  Each cache sequence entry in the cache sequence array (CSA) table 632 indicates a current save sequence tag t that a given cache memory slice can execute sequentially from a given requester j. If the save order request has been hashed to a given cache memory slice 602 that matches the requesting j's cache sequence entry, the cache memory slice performs the save order request. If a different save order request is hashed to a given cache memory slice 602 that does not match that requester j's cache sequence entry, the cache memory slice currently does not execute the save order request, but instead Hold it in the request buffer 608 or other queue for later processing. In this way, the order storage request can be executed in order.

  A cache sequence array (CSA) table 632 in the cache memory slice maintains one order preservation request entry for each requester. As described above, each cache memory slice can maintain the execution order of the order saving request for each requesting side j.

  Referring to FIG. 7, a block diagram illustrating an exemplary sequence of order execution of a save order request generates a tagged save order request, executes the save order request, and issues a cache sequence update message. Have.

  As described above, each processor / cache requester 701 has a unique requestor identifier (“RID”) 704 having a value of “j” and a single token register (“TR” having a value of “t”. )) 706. Each processor / cache requester 701 controls the generation of a work queue 707 for storing an order storage request (for example, ST.REL A, ST.REL B) and a tagged order storage request 500, and the memory therein Control logic 708 is further included for hashing or translating the address to select the cell and the appropriate cache memory slice.

  As described above, each cache memory slice in the memory hierarchy of the distributed cache memory capable of executing the order of the order preservation request has a cache sequence array (CSA). FIG. 7 shows a cache memory slice k702A and a cache memory slice m702B having a cache sequence array (CSA) 712.

  In operation, requester j701 appends requestor IDj and the current token register value t, and uses one address of the save order request in queue 707 to issue tagged save order request 500. Generate. The controller 708 of the requesting j701 issues a tagged order storage request 500. The order save request is tagged with the value “j.t”. At time X, as indicated by the arrow 721, the ST.REL A tagged order storage request is transmitted to the cache slice k702A. At the requesting side j701, after the ST.REL A tagged order storage request is transmitted to the cache slice k702A, the token register 706 is increased to the value of (t + 1).

  For example, “ST.REL A” and “ST” where the requesting side j701 is ready to tag and issue different addresses “A” and “B” as a tagged sequence storage request to the physical distributed cache memory system Suppose we have two order preservation requests denoted by .REL B ". The order preservation request “ST.REL A” is older than the order preservation request “ST.REL B” and must be processed first to realize the execution of the order. However, using different addresses “A” and “B”, the two order storage requests “ST.REL A” and “ST.REL B” are different parts (cache memory slice k702A and cache of physical distributed cache memory system). Processed by memory slice m702B).

  As indicated by an arrow 721, first, the requesting side j701 issues a tagged order saving request to the cache memory slice k702A with the order saving request “ST.REL A” tagged with “j.t”. When the cache memory slice k702A processes the tagged order storage request, the cache memory slice k702A executes the storage and updates. That is, as indicated by arrow 722, cache memory slice k702A broadcasts a cache sequence array (CSA) update having “j.x” to all other cache memory slices. The value x = t + 1. Cache memory slice k702A increments its own CSA [j] entry corresponding to requestor j to perform its CSA update.

  When the ST.REL A tagged order storage request is received, the cache memory slice k702A determines whether the tagged order storage request can be executed in order. To do this, cache slice k702A examines its cache sequence array (CSA) 712 and the requester j701 entry. The method for determining whether the cache memory slice k702A can execute the tagged order storage request in turn is described further below with reference to FIGS. 9A and 9B. Assuming that the cache memory slice k702A decides that it can execute the tagged sequence save request in turn, it does this. After the cache memory slice k702A processes or executes the ST.REL A tagged order storage request, the value of t increases to (t + 1) and is given the requester IDj, with the value j.t + 1 Generate and issue CSA updates 510 for all other cache memory slices. Arrow 722 indicates that the CSA update is sent to all other cache memory slices including cache memory slice m702B. This indicates that the cache that received the CSA update can process the tagged order storage request having a value of “j.t + 1”.

  Tagged order storage requests are in a disjoint order in a given cache memory slice for various reasons. For example, because a CSA update has not been received in a given cache memory slice in a timely manner, tagged order storage requests can be out of order. As another example, a tagged sequence preservation request could be out of order because another tagged order preservation request was issued before the previous order preservation request was fully processed and the CSA update was issued. is there. As yet another example, since a later tagged sequence save request was received before all CSA updates were received from other cache memory slices of a given requester j, There is a possibility.

  Continuing with the example, at time X + e (e is a positive number), as indicated by the arrow 723, the requesting side j requests an order storage request “ST” tagged with “j. (T + 1)”. A tagged order storage request including “.REL B” is issued to the cache memory slice m702B. At the requesting side j701, after the ST.REL B tagged order saving request is transmitted to the cache slice m702B, the token register 706 increases to the value of (t + 2).

  When the ST.REL B tagged order saving request is received, the cache memory slice m702B determines whether the tagged order saving request can be executed in order. To do this, the cache slice m702B examines its cache sequence array (CSA) 712 and the requester j701 entry.

  The cache memory slice m702B checks whether the entry of CSA [j] on the requesting side j of the CSA 712 is equal to (t + 1). In this case, assuming that the cache memory slice k702A has already processed the order preservation request “ST.REL A” and the cache memory slice 702Bm has received the corresponding CSA update, the cache memory slice 702Bm ( 300) can process “ST.REL B” because the entry in CSA [j] of requesting side j is equal to (t + 1).

  However, assuming that the requester j issues an order preservation request “ST.REL B” before the CSA update from the cache memory slice k702A reaches the cache memory slice m702B, the cache memory slice m702B Until the CSA update with the token “jx” arrives, keep the tagged order storage request including “ST.REL B” in the network or local buffer. In this case, the CSA updates are out of order and the cache memory slice must properly process the order preservation requests it has for processing.

  Assuming that the cache memory slice m702B decides that it can execute the tagged sequence save request in turn, it does this. After the cache memory slice m702B processes or executes the ST.REL B tagged order storage request, the value of (t + 1) increases to (t + 2) and is given the requesting side IDj, and the value j. Generate and issue CSA update 510 for all other cache memory slices at t + 2. Arrow 724 indicates that the CSA update is sent to all other cache memory slices including cache memory slice m702A. This indicates that the cache that received the CSA update can process the tagged order storage request having the value of “j.t + 2”.

  Assuming that the cache memory slice m702B has not received a CSA update with a value of “j.t + 1”, it executes in sequence the tagged order save request with the value of “j.t + 1” Can not do it. Cache memory slice m702B waits until it receives a CSA update with a value of “j.t + 1” before executing a tagged sequence save request with a value of “j.t + 1”. There must be.

  Referring to FIG. 8, a flowchart of control functions performed by the control logic 708 of the requesting j701 to support tagged order storage requests is shown. As described above, in this description, the number “Np” represents the number of processors sharing the distributed cache.

At 800, the system is initialized or reset. In 802, all the processors and the cache requesting side j701 set the token register TR706 and the token value “t” to an initial value (0 or the like). As described further below, all entries in each cache memory slice's cache sequence array (such as cache memory slices 702A and 702B's cache sequence array 712) will also have the same initial for "t". Set to a value (such as 0)
At 804, the control logic determines whether the requesting j701 is ready to send an order storage request to the physical distributed cache memory system. Otherwise, the control logic loops back to 804 and basically waits for an order save request to be issued. If the save order request is sent to the physical distributed cache memory system for processing, the control logic proceeds to 806.

  At 806, the save order request is tagged with the current value of the TRU tag 503 including RID “j” 501 and token register value “t” 502, as shown in FIG. 5A. The value of the TRU tag 503 is indicated as “j.t”. Control logic then proceeds to 808.

  At 808, control logic 708 of requesting j701 increments token register TR706 so that the current value of t is assigned a value of t + 1 for later use in the next save order request. Control logic then proceeds to 810.

  At 810, a tagged order storage request 500 is issued to the physical distributed cache memory system. The address of the tagged sequence save request is hashed and the tagged sequence save request is sent to the appropriate cache memory slice (such as cache memory slice k702A).

  FIG. 9A is a first flowchart of the control functions performed by the control logic 714 of each cache memory slice to support tagged sequence preservation requests. FIG. 9B is a second flowchart of the control functions performed by the control logic 714 of each cache memory slice to support tagged sequence preservation requests.

  Referring to FIG. 9A, a flowchart of control functions performed by the control logic 714 of each cache memory slice is illustrated for determining whether an order preservation request can be processed. At 900, the system is initialized or reset as previously described at 800. At 902, all entries in the cache sequence array 712 of each cache memory slice are set to an initial value of “t” (eg, 0). This matches the initial token value “t” that each requesting j701 has for its token register TR706. Control logic then proceeds to 904.

  At 904, the control logic of each cache memory slice determines whether a tagged sequence save request 501 has been received from the requesting side. Otherwise, the control logic loops back to 904 and basically waits to receive a tagged sequence save request. If a tagged sequence save request is received for processing, control logic proceeds to 906.

  At 906, the TRU tag j.t is extracted from the tagged order save request and determines whether the order save request can be processed by a given cache memory slice. With respect to the value of the received request side identifier “j”, the cache memory slice takes the value of the order saving request (value CSA [j] (j assumes a value of 0 to (S-1) assuming an initial value of 0) Read the cache sequence entry of the processor that performed)). Recall that “S” represents the number of outstanding sequence saves supported by each processor.

  In 908, the CSA [j] entry of the requesting side j and the expected sequence number are compared with the “t” portion of the tag of the order storage request. If CSA [j] matches the “t” portion of the tag in the order preservation request, the request can be processed. If CSA [j] is not equal to the “t” portion of the tag, the tag does not match and control logic proceeds to 913. If CSA [j] is equal to the “t” portion of the tag, the tag matches and control logic proceeds to 912.

  At 913, the corresponding tagged sequence save request (including tags) is saved in the normal work queue of the cache for later processing.

  If the tags match at 912 (CSA [j] = t), the cache processes the save order request and proceeds to 914.

  At 914, the CSA [j] entry is incremented for a given requester and control logic proceeds to 916.

  At 916, a CSA update is issued to all other cache memory slices. A given cache memory slice that has processed a tagged order save request issues token j. (T + 1) to all other cache memory slices in the system and token value (if any). Indicates that the message from the requesting party j corresponding to t + 1 can be processed. The requester also increments its token and checks the work queue for any matching requests after the CSA update.

  A process of updating CSA separately will be described. As described above, the network of physical distributed cache memory slices can reorder tagged order storage requests so that they can be processed in order. However, the network of physical distributed cache memory slices can also reorder CSA updates received by each cache memory slice as well.

  Temporarily referring to FIG. 7, for example, cache memory slice 701A sends two CSA updates including tag updates j. (T + 1) and j. (T + 2) sequentially to a nearby cache. Consider that the cache memory slices 702B have been reached in a discrete order. In addition, cache memory slice 702B has a tagged ordered save request that needs to wait for a CSA update including tag updates j. (T + 1) and j. (T + 2), but from cache memory slice 702A Assume that a unique CSA update indicating tag update j.t + 2 has been received. In this scenario, the CSA updates are out of order.

  When CSA update message tag updates are received in the order in which the cache memory slices are out of order (before receiving tag update j.t + 1, j.t + 2, j.t + 3 and j.t + 4) When tag update j.t + 5 is received), any other cache memory slice generates j.t + 2, j.t + 3, etc. in order and issues tag update j.t + 5 It is necessary to receive j.t + 1 in order to start. Therefore, if the cache memory slice receives a tag update j.t + n without receiving the previous update, when the tag update j.t + n is received, the cache will contain j.t + n It is safe to handle all sequence preservation.

Further operation of t + n is performed a 2 ^b modulo. Where b is the number of bits in the counter portion of the tag. Since the counter has a limited number of b bits, further operations may roll over to a smaller value beyond the maximum counter value. Care must be taken to avoid the negative effects of rollover conditions. In one embodiment, the number of bits “b” is sufficient compared to the maximum network latency (ie, the maximum network delay), so that by the time the token register rolls over, the processor Processing an order save request. In another embodiment, a processor / requestor with a TR register that may roll over polls each cache memory slice, each processing all tagged memory requests and reaching S-1. Determine whether or not. Upon responding to the processor that all cache memory slices have been completed, the processor allows that given TR register to roll over.

Each requesting TR counter has a limited number of bits ("b" bits) and therefore generates a tag with "b" bits. That is, the maximum counter value and the tag “t” are 2 ^b −1.

Cache memory slice k702A receives a CSA update with a tag of j.2 ^b -2, but receives other CSA updates, including those with a tag value of j.0 to j.2 ^b -3 Assume that it is not. Further assume that cache memory slice k702A processes all of its order preservation requests and sends a CSA update with a tag value of j.2 ^b -1. issuance of CSA update with a tag update of J.2 ^b -1, the other cache memory slices (cache memory slices m702B etc.) has a J.2 ^b -1 without waiting other CSA update Processing of the tagged order storage request may be activated. Thereafter, since the tag j.0 is the next counter value after j.2 ^b −1, the cache memory slice m702B may issue a CSA update message including the update tag of j.0.

  Referring to FIG. 9B, a flowchart of the control functions performed by the cache memory slice control logic is illustrated for the tag update process.

  At 950, the CSA update routine executed by the control logic of each cache memory slice is initialized at power up or reset.

  At 952, the control logic determines whether the cache memory slice has received a CSA update message with tag update j.t. Otherwise, the control logic loops back to 952 and basically waits to receive tag updates. When a CSA update message with tag update j.t is received, control logic proceeds to 972.

  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 order preservation request with the tag “j.t”. After processing the save order request, at 980, the control logic returns to 952 to receive the next update.

  While specific embodiments have been described and illustrated in the accompanying drawings, it will be understood that such embodiments are merely illustrative of the broad description and not limiting. In addition, since various other modifications will occur to those skilled in the art, it will be understood that the invention is not limited to the specific configurations and arrangements shown and described. For example, the present invention or some of its features can be implemented in hardware, firmware, software, or a combination thereof. In that case, the software is provided on a processor readable storage medium (such as magnetic, optical or semiconductor storage).

Block diagram of a general computer system in which the present invention may be used Block diagram of a central processing unit in which the present invention may be used Block diagram of a multiprocessor central processing unit in which the present invention may be used. Block diagram of an embodiment of a multiprocessor system in which the present invention may be used Block diagram of another embodiment of a multiprocessor system in which the present invention may be used. Block diagram of another embodiment of a multiprocessor system in which the present invention may be used. Block diagram of logical shared / physical distributed cache memory system Illustration of the general fields of a tagged sequence save request CSA update general field diagram Cache memory slice block diagram Block diagram of cache sequence array (CSA) Block diagram of an exemplary sequence of execution of order preservation request order Flowchart of control functions performed by requesting control logic to support tagged sequence save requests Flow chart of the control function executed by the control logic of each cache memory slice as to whether or not the order saving request can be processed Flow chart of control functions executed by control logic of each cache memory slice that processes tag update

Claims (40)

An interconnection network;
A first level cache memory slice coupled to the interconnect network for generating a tagged sequence storage request having a requester identification and a storage sequence token;
A physical distributed cache memory coupled to the interconnect network and having a second level cache memory slice for sequentially executing the order preservation request through the physical distributed cache memory system in response to each tag of the tagged order preservation request system. The physical distributed cache memory system according to claim 1,
A physical distributed cache memory system in which one or more of the tagged ordered storage requests are received in a disjoint order by at least one of the second level cache memory slices. The physical distributed cache memory system according to claim 1,
Each of the first level cache memory slices comprises a physical distributed cache memory system having a unique requester identification and a sequence token register that generates the tagged order preservation request. The physical distributed cache memory system according to claim 1,
Each of the second level cache memory slices comprises a physical distributed cache memory system having a cache sequence array that sequentially executes the order preservation requests through the physical distributed cache memory system. The physical distributed cache memory system according to claim 4,
The cache sequence array has a cache sequence array table that stores a save sequence token associated with a save order request as a cache sequence entry;
The physical distributed cache memory system, wherein the cache sequence entry indicates one or more order preservation requests that the cache memory slice can currently execute. The physical distributed cache memory system according to claim 4,
Each of the second level cache memory slices further comprises control logic coupled to the cache sequence array;
The physical distributed cache memory system, wherein the control logic generates a cache sequence array that controls execution of the order of the order preservation request and updates the second level cache memory slice. The physical distributed cache memory system according to claim 1,
Each of the first level cache memory slices is coupled to a processor and generates a tagged order preservation request. The physical distributed cache memory system according to claim 7,
The physical distributed cache memory system, wherein the processor includes an internal cache memory that generates the tagged order storage request. The physical distributed cache memory system according to claim 1,
A physical distributed cache memory system further comprising a higher level cache memory coupled to one or more processors. The physical distributed cache memory system according to claim 9,
The physical distributed cache memory system, wherein the one or more processors include an internal cache memory that generates the tagged order storage request. The physical distributed cache memory system according to claim 9,
The higher-level cache memory is a physically distributed cache memory system that generates the tagged order storage request. A method for order preservation requests in a physical distributed cache memory system, comprising:
A tag is attached to the order storage request indicating the request side identification display and the storage sequence number,
Sending a tagged sequence save request to the cache memory slice of the physical distributed cache memory system;
Comparing the expected sequence number associated with the requester identification with the stored sequence number;
Executing the order preservation request if the preservation sequence number matches the expected sequence number; The method of claim 12, comprising:
The method further comprising saving the tagged sequence save request for later execution if the saved sequence number does not match the expected sequence number. The method of claim 12, comprising:
The method further comprising updating the expected sequence number associated with the requester identification in response to performing the order storage request. The method of claim 12, comprising:
Before executing the order saving request, it is further determined whether a previous order saving request made by the requester is being executed, and if so, executing the order saving request. Method. 16. A method according to claim 15, comprising
The determining is whether a save sequence number associated with the previous order save request and the requester identification is received by the cache memory slice to execute the order save request. How to determine. 16. A method according to claim 15, comprising
A method in which execution of the current order save is delayed until all previous order save requests are executed when it is determined that all previous order save requests made by the requester have not been executed. A data signal flow coupled to a cache memory for execution of an order of order preservation requests,
A requester identifier that indicates the requester that initiated the save order request; and
A token value indicating a sequence of the order storage request;
A data signal flow comprising: a request identifier and a message identifier indicating that the token value is available to be read by the cache memory. A data signal flow according to claim 18, comprising:
The data signal flow further indicating that the request identifier and the token value are added to the order storage request, the message identifier. A data signal flow according to claim 19,
The order storage request;
An address to store the data,
A data signal flow further comprising: the order storage request data to be stored; A data signal flow according to claim 18, comprising:
The method of further indicating that the message identifier is for the requestor identifier and the token value to update a cache sequence array. A plurality of processors each having one or more levels of processor cache memory;
A distributed cache memory system coupled to the plurality of processors and having a plurality of primary interconnect networks and a plurality of cache memory slices coupled to the primary interconnect networks;
A processing unit comprising: a plurality of cache memories coupled between the plurality of processors and the primary interconnect network of the distributed cache memory system;
The processor or cache memory has a unique requester identification and a sequence token register for generating a tag to be attached to an order preservation request of the plurality of cache memory slices of the distributed cache memory system, The tag has a requester identification and a sequence token associated with the requester identification;
Each cache memory slice includes a processing unit having a cache sequence array that sequentially executes the order preservation requests through the distributed cache memory system. A processing unit according to claim 22,
A processing unit in which one or more of the order preservation requests of the plurality of cache memory slices are received in a disjoint order by at least one cache memory slice. A processing unit according to claim 22,
The cache sequence array has a cache sequence array table that stores a save sequence token associated with a save order request as a cache sequence entry;
The cache sequence entry is a processing unit that indicates an order preservation request that the cache memory slice can currently execute. 25. A processing unit according to claim 24, comprising:
One cache memory slice of the plurality of cache memory slices receives a store order request having a sequence token that matches a predetermined requesting cache sequence entry indicating the order;
The one cache memory slice is a processing unit that executes a current order preservation request. The processing unit according to claim 25, wherein
The one cache memory slice further updates the cache sequence entry of the plurality of cache memory slices. 25. A processing unit according to claim 24, comprising:
One of the plurality of cache memory slices receives a store order request having a sequence token that does not match a predetermined requesting cache sequence entry indicating the disjoint order;
The one cache memory slice is a processing unit that stores a current save order request for subsequent order execution with other save order requests. An input / output device;
Dynamic random access memory,
A computer system comprising: said dynamic random access memory; and a multiprocessor processor coupled to said input / output device,
The multiprocessor processor is:
A plurality of processors each having one or more levels of processor cache memory;
A distributed cache memory system coupled to the plurality of processors and having an interconnect network and a plurality of cache memory slices coupled to the interconnect network;
A plurality of cache memories coupled between the plurality of processors and the interconnect network;
The processor or cache memory has a unique requester identification and a sequence token register for generating a tag to be attached to an order preservation request of the plurality of cache memory slices of the distributed cache memory system, The tag has a requester identification and a sequence token associated with the requester identification;
A computer system wherein each cache memory slice has a cache sequence array that sequentially executes the order preservation requests through the distributed cache memory system. 29. A computer system according to claim 28, comprising:
One of the plurality of cache memory slices receives a save order request having a sequence token that matches a predetermined requesting cache sequence entry indicating the order;
The one cache memory slice is a computer system that executes a current order preservation request. 30. A computer system according to claim 29, comprising:
The one cache memory slice further updates the cache sequence entry of the plurality of cache memory slices. 29. A computer system according to claim 28, comprising:
The order storage request is a computer system that is a request side storage request that requires execution of an order with respect to another order request on the request side. A computer system according to claim 31, wherein
A computer system that requires processing prior save order requests before the current save order request can be processed. A computer system according to claim 30, comprising
An unordered save request is a request side save request that can be executed out of order with respect to other order requests on the request side. An interconnection network;
A plurality of processors coupled to the interconnect network and coupled to the interconnect network for tagged sequence storage requests each having a tag including a requester identification and a storage sequence token;
A multiprocessor having an integrated circuit coupled to the interconnect network and having a plurality of cache memory slices that sequentially execute the order preservation requests from the plurality of processors in response to each tag of the tagged order preservation request. A multiprocessor according to claim 34, comprising:
The order storage request is a multiprocessor that is a storage request that requires execution of an order with respect to another order request on the requesting side. 36. The multiprocessor of claim 35, wherein
Multi-processors that require processing before a previous save order request can be processed before the current save order request can be processed. 36. The multiprocessor of claim 35, wherein
An unordered save request is a multiprocessor that is a save request that can be executed out of order with respect to other order requests. A multiprocessor according to claim 34, comprising:
Each of the plurality of cache memory slices includes a cache sequence array that sequentially executes the order preservation request through the general connection network. 40. A multiprocessor according to claim 38, wherein
The cache sequence array has a cache sequence array table that stores a save sequence token associated with an order save request as a cache sequence entry;
The cache sequence entry is a multiprocessor indicating an order preservation request that the cache memory slice can currently execute. A multiprocessor according to claim 34, comprising:
The plurality of cache memory slices are coupled to the interconnect network from a distributed cache memory system shared by the plurality of processors.

Images