Non-speculative distributed solution of conflicts for protocol of cash-memory coherence

FIELD: cash-memory devices.

SUBSTANCE: method includes stages, on which conflicting calls of data block from multiple one-rank nodes are solved by one-rank node, having trustworthy copy of called data, which is called using conflicting messages, while one-rank node with the copy selects target node from list of nodes which sent conflicting messages, and conflicting calls for data block are solved using base node, appropriate for called data, if a unique, cashed copy is absent, which is stored on one of one-rank nodes, while base node, having trustworthy copy of called data, picks target node from list of nodes, which sent conflicting messages.

EFFECT: higher efficiency.

4 cl, 24 dwg

The technical field to which the invention relates.

This invention relates to devices of the cache memory. More specifically, the invention relates to distributed conflict resolution in a multiprocessor system having multiple devices cache-memory.

Prior art

If your system includes multiple devices of the cache memory (cache), it must be ensured reliability available for use data. This is usually accomplished by manipulating data in accordance with the coherency Protocol of the cache memory. When the number of caches and/or processors also makes maintaining the coherence cache.

When multiple components (for example, the cache memory, the processor requests the same data block, the conflict between the various components must be resolved in a way that supports the validity of the data. Existing at a given time protocols coherence cache memory are usually the only component responsible for the resolution of conflicts. However, as system complexity increases, the dependence of conflict resolution from a single component can reduce overall system performance.

In Fig. 1a through 1e shows a conceptual illustration of a conflict situation in a multinode system. Nodes 110, 20 and 130 are peers, which can store a copy of the requested data (e.g., cache line in the cache memory. The base unit 140 is for the requested data base (H) node. In the example of Fig. 1A through 1e peer-to-peer nodes 110 and 120 store false copy or store any copies of the requested data, and peer-to-peer node 130 stores a modified copy of the requested data that was not overwritten in memory. The base unit stores in memory the original copy of the data or changed data variants, if changes are overwritten in memory.

As shown in Figa, peer node 120, to request a copy of the data block, for example, the cache line, sends the message "Request Data" (Data Request). The message "Request Data" is passed to the peer node 110 and the peer node 130. However, the message "Request for Data" to a peer node 130 delay. The delay may be caused, for example, lack of available bandwidth, buffering, etc.

Peer node 110 responds to the message "Request Data" peer 120 the message "the Lack of Reliable Copies (No Valid Copy), which specifies the peer node 120 that peer node 110 does not have a true copy of the requested data. Some time after the transmission of peer-to-peer node 120 message "Request Data", peer node 110, as shown in Figs, p is reday message "Request Data" peer-to-peer nodes 120 and 130, requesting the same data that was requested peer node 120.

Peer node 120 sends to the peer node 110 in response to the message "Data Request" message "the Lack of Reliable Backup. Peer node 130 sends the requested data to peer node 110. A copy of the data, if any, supported by a peer node 130,marked as unreliable, and a copy of data stored by a peer node 110, marked as Modified.

After some time after the peer 130 answered "Data Request" peer 110 and marked copy of the data as unreliable as reliable peer-to-peer node 130, as shown in Figs, takes detained the message "Request Data from the peer 120. In response to the message "Request Data" peer-to-peer node 130 sends a message to the Lack of Reliable copies of peer-to-peer node 120. It should be noted that the data state stored by a peer node 130, changed from the time the original message "Request for Data" to the response time of the peer 130 on the message "Data Request".

Because peer-to-peer nodes 110 and 130 reply to message "Request Data" peer 120 messages "the Lack of Reliable Copies, peer 120, not finding any reliable cached copies of the requested the x data requests a copy of the data at a reference node 140. Thus, as shown in Fig.1d, a peer sends the message "Read" (Read) base site 140. The base unit 140 retrieves the requested data from memory and sends the data to the peer node 120. Peer node 120 then stores the requested data in the Exclusive (Exclusive) state.

As shown in Figi, the sequence of messages shown in Fig. 1A through 1e, results in the existence of two incompatible copies of the data line. In the example, peer node 110 stores a copy of data in an Altered state, and peer 120 stores a copy of data in Exceptional condition. However, the copy stored by a peer node 120, is not exceptional in relation to the peer node 120. Thus, in a multi-node systems in some circumstances you may experience inconsistent copies of data, if not provided with a mechanism for conflict resolution cache.

List of figures

This invention shown in the form of a non-limiting example in the accompanying drawings, in which similar reference numbers indicate similar elements.

Fig. 1a through 1e is a conceptual representation of conflict in the multi-node system.

Figa and 2b is a conceptual view request joint is used on the cached string.

Figa and 3b is a conceptual representation of the query shared uncached line.

Fig. 4a through 4f is a conceptual representation of the tripartite conflicting requests for the shared line.

Fig. with 5a through 5g - conceptual representation of the tripartite conflicting requests for the shared line.

6 is a block diagram of one embodiment of a node.

7 is one embodiment of a multiprocessor system.

Detailed description of the invention

Here is described how to use a single package, a container for a set of Protocol messages cache. In the following description with explanatory purposes set forth numerous private details to provide a thorough understanding of the present invention. However, for any who are skilled in the art, it will be obvious that the invention may be made without these private details. In other examples, avoid vague understanding of the invention, circuits and devices are shown in block diagrams.

Request message

The following messages are requests for data/actions from the requested node. These messages are broadcast to all nodes in the system.

To consider a Line (Port Read Line, PRL): This is a request for a copy of the data segment, such as, n is the sample, cache line.

Be considered Unreliable Line (Port a Read Invalidate Line, PRIL): This is a request for a copy of the data segment, if the copy of the node data provider is unreliable. This message may also be referred to as "request to join a possession."

To write a string (Port Write Line PWL): This message initiates the recording of data (for example, a modified cache line in memory. This message may also be referred to as "the replacement of the corrupted data".

Mark the string as Unreliable (Port Invalidate Line, PIL): This message causes a state change in the planned c data of the sharing status in Exceptional condition.

To write a String and mark it as False (Port Write Invalidate Line, PWIL): This message initiates the write data in the memory and makes the target copy of the data to be unreliable.

Response message

The following messages are messages sent from the peer-to-peer (that is, nonbasic) nodes to the requesting node in response to the queries described above.

Confirmation Unreliable Status (Invalid State Acknowledgement, IACK): This message is a response to the request (PRL, PRIL, PIL, PWIL)when the node sending the response is inaccurate copy of the requested data or no copy of the requested data.

Confirmation of the sharing Status (Shared State Acknowledgement SACK): This is communicated to the E. is a response to the request PRL, when the node that sent the response, a copy of the requested data sharing.

The ACK Data (Acknowledgement of Data Received, DACK): This message acknowledges receipt of the requested data. This message sends the base unit when the base unit receives a message CNCL. The destination node for the message DACK is the node forwarding included in the message CNCL. The node receiving the transferred data or memory data base node does not respond to the sending node.

Conflict(CNFL): This message indicates that there is simultaneously processed for the requested cache line.

Data [Conflicts] (Data):This message is used to send data and lists of conflicts, if any. The conflict list is empty, if the data is sent or if the base node sends data from the memory to the first owner. During data transfer, the sending node joins the list of conflicts. The receiving node uses the list to send responses CNFL to relevant queries stored in the buffer.

Messages to the base node

These messages are sent to the peer node to the base node.

Read [Conflicts](READ):This message requests the data from the base node and lists the conflicts, if any. This message is sent after the AC is a peer adopted all the answers, if none of the received message was not a message DATA.

Cancel (Conflicts)(CNCL):This message is sent to the base node in response to a cache hit in peer-to-Peer node and lists all the conflicts, if any. This message cancels the operation fetch proactive, performed by the underlying node.

Message from the base node

These messages are sent by the base node on the peer-to-Peer and/or the Requesting nodes.

Data:This message includes the requested data and may indicate the state of the data (M/E/F), which must be used by the Requesting node.

ACK:This message indicates that the requested data has been sent to the Requesting node. After sending the base node ACK current period is completed.

Transfer (XFR):This message instructs the receiving node to send data to the host specified in the message. The base node sends this message to the current owner of the requested data, if the base node is informed about the state of conflict that require the current owner of the data has transferred data to the target node. Instead of the message XFR message XFRI, if the base node determines that unresolved conflicting request is a message PRIL or PWIL, which means that the current Vlad the LEC must designate the line as unreliable when initiating data transfer. In one embodiment, the first node during the period, which will send the message CNCL, is the current owner. The period in this context is the period between the first data request and the resolution of all conflicts of data requests. If the base node sends data to the node from memory, then this node is the current owner. Sending messages XFR/XFRI instructs the target node to be the current owner. In one embodiment, the target site selected from the list of conflicts provided by the base node in a message READ or CNCL. The target nodes of the selected node from which the base node has received the message READ. Thus, if the base node considers the node And the current owner of the cache line, because the host And sent to the base node message CNCL(B, C), the base node waits for the reception of the message READ from nodes b or C, to send a message XFR/XFRI on the site And to instruct the node And to send data to host (B or C)who sent the message READ. The base node then waits to be sent from the third node messages READ before sending the message XFR/XFRI instructing the third node to send data.

A brief description of the MESIF Protocol

There are two main schemes ensure coherence cache, acquisition scheme (now often called Symmetric multi-processing (SMP)and the directory schema (often referred to as Distributed Together Use ishema Memory (DSM)). The fundamental difference between them lies in the placement and access to meta-information, i.e. information about which stores copies of the cache line.

In the case of monitoring cache this information is distributed directly from the cached copies, that is, each valid copy of the cache line is supported by module, which must determine its ability to respond whenever any node in the new requests permission to access the cache line. Somewhere - usually in a fixed location is a warehouse in which to store cached data. This location can contain true copy, even when the string is cached. However, the location of this node is usually unknown to the requesting node requesting nodes simply perform the broadcast address of the requested cache line, along with the necessary permissions in the broadcast message, and all the nodes that could have a copy must answer in order to ensure that consistency is maintained, and the node containing a non-cached copy, respond, if no other (peer) node is not responding.

For diagrams based on the catalog, in addition to a fixed place, where uncached data, there is a fixed location, the directory indicates where the constant is stored on a cached copy. To make a new access to the cache line, the node must communicate with a node that contains the catalog, which usually is the same site that contains uncached store data, thus allowing the corresponding node to provide the data if the copy in the primary storage device reliable. This node is referred to as the base node.

The directory can be distributed in two ways. First, data from the main memory (uncached store) are often distributed among nodes, and the catalogue is distributed in the same manner. Secondly, the meta-information can be disseminated, and the base node stores the minimum information about cached does the string, and if so, where ever is the only copy.

The acquisition scheme based on broadcast, because there is no separate place, where the meta-information, so all nodes must be notified of each request, each node is responsible for doing their part to ensure coherence maintenance. This circuit includes a message intervention, instruct the base node is not responding when another node provides the data.

Schema observations have the advantage consisting in the fact, chootey can be direct and quick, but they don't scale well, because all nodes are required to track all requests. Schema-based directory and scale better, but require more complex responses, often involving three nodes in point-to-point link.

The main MESIF Protocol described here provides a Protocol that is similar to the observation, without the limitations associated with only one serial bus. Like the Protocol monitor cache, MESIF to maintain coherence is based on nodes with cached copies of data. The use of point-to-point communication lines, and not synchronous, centralized broadcast causes a problem changing the time scale, the essence of which is that from the point of view of different sites it seems that events occur in a different order. As described in more detail below, the MESIF Protocol handles the change of time scale, recognizing when could be the possible errors and making sure that they are properly processed. The term "base unit" is used to determine where the constant is uncached copy, but the base node participates in each transaction (group of operations) - while not on the critical path to solve the problem changing the time scale, and conflict resolution. Because of the parallel-broadcast entity schema MESIF reaches Nizkor the delay time, associated with monitoring protocols, providing in most cases, getting a cached copy of the data with minimum latency: the only request-response in forward and backward directions between two nodes.

The main MESIF Protocol includes the broadcast of the initial request to all peers, as well as to the base node. If a copy is cached in state E, F, or M, then it is included in the response. Then the base node sends a second message informing you that the request has been satisfied. If the requested string is uncached, or if there are only copies in the S-state, the second request is sent to the base node is used to confirm the previous query, the data on which the base node may by this time have chosen from my memory. In any case, the base node shall respond to the second request (and at first, although they sometimes can be combined) to ensure synchronization and conflict resolution. It should be noted that the base node may have one or more caches, so that it can respond to the original query in the same way as any other node.

Conflict handling implement a distributed way. The problem changing the time scale complicates the detection of conflicts, because some requests may be delayed for an arbitrarily long time. However, the conflict will be detected if each node keeps track of the conflicts after the query is executed. Both nodes can detect and not detect the conflict, but at least one node detects. Since all nodes must respond to the broadcast request, or providing data or indication that they do not have copies of (or, in some circumstances, do not provide a copy, which they have), and the response may include an indication of the conflict, so that the conflicting nodes will detect the conflict.

Difficulties arise when the permission node to use the data immediately after they are received, without waiting for reception of all responses. Thus, the node receiving the copy of the data is permitted immediately after the reception to use the data within itself, but is not permitted to make use of the data visible to the rest of the system until the node has not received confirmation from the base node. The confirmation may also include instructions regarding the fact that the node should send its copy to another node, and possibly remove a node from its cache.

Finally, when a node responds to a request from another node providing the cached data, the node should delay all other accepted them requests for the same cache line as long as the node does not accept the response from the gas node, confirming the data forwarding node, thus ensuring that all nodes observe the same order of transmission of the (possibly rewritable), cache line.

The base site is a repository for uncached data, but the base node may also have a processor, generating queries, and include one or more caches. Just like any other node, when the processor base unit detects the absence of the necessary data, the base node shall perform a broadcast query to all other (peer-to-peer) nodes and the base node should process the request within itself, as if it were any other request arriving at the base node. It should be noted that this is a special case, since the base node is not explicitly sends messages to itself (base node). In addition, when receiving an external request for data that is cached locally, the base node must meet to guarantee the uniqueness of the later response of the base node. That is, the base node may respond to the initial request by providing data, but the base node should also answer the second query as the base node.

The Protocol variants allow the base node to reply through a non-cached copy of the data, not knowing whether the data is true, war is vlaa asking it to the requesting node, and the second answer is the base node for the classification case, when they were given inappropriate danniele detailed, made on the basis of pseudo-code description of the various implementation options MESIF Protocol corresponding to the one described here aims at the end of Appendix A.

A brief description of the non-speculative distributed conflict resolution

In General, the coherency Protocol of the cache memory requires conflict resolution to ensure an orderly changes in the status of the various cache lines or other blocks of data. The described method of conflict resolution provides sequential consistency, which means that at any time there can only be only modifiable copy of the cache line, and that no copy of the cache line cannot be changed, while the other copy can be read. Therefore, to maintain sequential consistency conflicting change requests copies of the cache line must be enabled.

In one embodiment, the conflict is allowed through the use of properties of time. That is, regardless of the delays, none of the two nodes cannot request the cache line before the other. Thus, conflicts can be detected, at least one of the conflicting requesting nodes, if each node monitors in the e requests after as this site has developed its own request.

In one embodiment, if the line is in the Exclusive (E) state, the Modified (M) state or condition of the forward (F), conflicts are resolved in a node that contains a unique copy. Winning in the conflict, and possibly losing, report the conflict to the base node, which connects pairs reports about the conflict and generates instructions forwarding to ensure that, ultimately, receive all requesting nodes of the requested data. In one embodiment, if the requested cache line or necesitaban, or is present only in the state sharing (S), the base unit provides for the requested cache line copy of the requested data and resolves conflicts.

In one embodiment, the distributed conflict resolution described here is part of the Protocol cache, referred to as the MESIF Protocol, in which the cached copy of the cache line associated one of five States (Modified (M) state, Exclusive (E) state share (S), Unreliable (I) state, a state of forward (F)). In one embodiment, the period of silence after all responses to the request until it was taken to a confirmation message from the base node, providing the t awareness of all of the conflicting nodes conflicts, involving these nodes. The period of silence does not restrict the use of data in the cache, but effectively prevents the spread of data in other caches.

The following detailed discussion uses terms related to nodes in a multinode system. In one embodiment, the node includes a processor having an internal cache, external cache memory and/or external storage device. In an alternative embodiment, the node is an electronic system (e.g., computer system, mobile device) is connected to other electronic systems. Can also be used in other variants of the configurations node. In the following examples dashed lines display a list of previously sent messages, and the solid lines show the described messages. For clarity of the drawings, after the resolution of the set of messages (e.g., PRIL and its corresponding IACK), the lines representing these messages, then the drawings are not depicted.

Figa and 2b are conceptual views query shared cached rows. Associated with different messages on Figa and 2b numbering (for example, 1. PRIL, 7. IACK), with the aim of explaining the example of the conflict provides an approximate ordering. The exact timing relationships, the picture is different on Figa and 2b, as well as in the other examples (i.e. Figa-3f) are not required.

As shown in Figa, peer node 210 transmits a message PRIL peer nodes 220 and 230 and the base node 240. Peer node 210 could also request the same data block, using the message PRL, in which case the peer node 230 in response to the request message is not marked his copy as unreliable. Peer node 220 responds to the PRIL message IACK message that indicates that the peer node 220 may not provide valid copy of the requested data. Peer node 220 is shown initially contains a copy of the requested data in the state S, which is a reliable copy of the data, but is not a copy, which may be provided in response to a request for a copy of the data. As the PRIL message requests a copy of the data and requires all other copies to be marked as unreliable remaining copies of the data, the peer node 220 brings its copy of the data from the S-state in the I-state. Because peer-to-peer node 230 contains a copy of the requested data in the F-state (single authoritative copy of which shall be provided to the requesting node), peer node 230 provides a peer node 210 a copy of the requested data. Peer node 230 also brings its copy of the requested data in I-is status. Peer node 210 stores the requested data in the E-state. Alternatively, peer node 210 stores the requested data in the F-state.

As shown in Fig.2b, in response to receiving the requested data from peer node 230, peer node 210 sends the base node 240 message CNCL(230)(), which instructs the base node 240 to cancel retrieving the requested data from memory (or to cancel the data transfer, if they have already extracted). Message CNCL(230)() specifies the base node 240 that a copy of the requested data was adopted from peer node 230, and that peer node 210 has not found any conflict by querying the data PRIL message.

In response to the message CNCL(230)() from peer node 210 base node 240 transmits the ACK message to the peer node 210 and the DACK message to the peer node 230. ACK indicates to the peer node 210 that the base node 240 acknowledges receipt of the message CNCL(230)(). The DACK message from a peer node 240 peer node 230 confirms the reception of data from peer node 210 and terminates the process data request to the peer node 210.

Figa and 3b are conceptual views query shared uncached line. As shown in Figs, peer node 210 to request copies of the data block passes the message to PRIL. POSCO is ku peer-to-peer nodes 220 and 230 do not keep accurate copy of the requested data, the nodes 220 and 230 are responsible IACK message.

As shown in Fig.3b as peer-to-peer node 210 took IACK message from all peers, peer node 210 sends the base node 240 message READ(), which requests a copy of the pre-requested data that has been retrieved from the memory core node 240. The message READ() specifies the base node 240 that peer node 210 found no conflicts with the PRIL message. Base unit 240 provides a copy of the requested data using messages DataE. In one embodiment, the base unit 240 also includes an ACK message DataE (i.e. in the same batch of messages). In an alternative embodiment, messages DataE and ACK transmit separately.

In Fig. 4a through 4f shows a conceptual representation of the tripartite conflicting requests for shared cached string. As shown in Figa, peer node 210 sends a message PRL peer nodes 220 and 230 and the base node 240. Message PRL designed core node 240, for any reason delayed, for example, due to the delay of the waiting time in the system 200. As neither peer node 220 or peer node 230 in response to message PRL cannot provide valid copy of the requested data to peer node 220 and the peer node 230 and send the keys to the peer node 210 IACK message.

Message PRL peer node 210 does not require any of the receiving peer nodes to be marked as unreliable copies, if any, stored on the receiving peers. Peer node 210 may also be applied to data request message PRIL, requiring that all peer nodes storing the requested data, regardless of whether they were provided to the requesting node or not marked as unreliable stored on site a copy of the requested data. Conflicts can be caused by any combination of messages that otherwise would cause inconsistent results.

As shown in Fig.4b, shortly after receiving peer node 220 from peer node 210 messages PRL and before the base unit 240 receives a message PRL from peer node 210, the peer node 220 transmits a message PRIL, requesting the same data block. Peer node 220 transmits a message PRIL peer nodes 210 and 230 and the base node 240; however, the PRIL message, destined to the peer node 210, detained. Peer node 230 and the base node 240 to respond PRIL peer node 220 IACK message.

As shown in Figs, peer node 230 subsequently transmits the PRIL message peer-to-peer nodes 210 and 220 and the base node 240. The base node 240 responds to the message is the PRIL message IACK, indicates that the core node 240, no valid copy of the requested data. Peer node 210 responds to the PRIL message peer-to-peer node 230 message CNFL, which indicates that the peer node 210 has a conflict with the PRIL message received from peer node 230.

Peer node 220 responds to the PRIL message peer-to-peer node 230 message CNFLI, which indicates that the peer node 220 has a conflict with the PRIL message received from peer node 230. Message CNFLI indicates that a conflicting message to peer node 220 is the PRIL message requiring acknowledgement copy of the data unreliable. Message CNFL peer node 210 indicates that a conflicting message to peer node 210 is the message PRL, does not require recognition of copies of the data to be unreliable.

As shown in Fig.4d, after receiving a base node 240 of the delayed messages PRL peer node 210, the base node 240 responds with an IACK message indicating that the base Assembly 240, no valid copy of the requested data.

In response to receiving the message CNFL from peer node 210 and messages CNFLI from peer node 220 peer node 230 transmits to the base node 240 message READ(210, 220*). The message READ(210, 220*) requests a copy of the data from the memory managed by the base node 240. The message READ(210 220*) indicates, the data request to the peer node 230 conflicts with the requests of the peer nodes 210 and 220, and that the requesting peer node 220 requires recognition of copies of the data are unreliable (as indicated by an asterisk). Because peer-to-peer node 230 from the first nodes with conflicting requests sent message READ core node 240, peer node 230 is the first peer node received a copy of the requested data, and the current owner of the requested data.

In response to the message READ(210, 220*) base unit provides a peer node 230 of the requested data in the message DataE. Message DataE instructs the peer node 230 to store data in state E. alternatively could be used other data messages (e.g., DataF, DataS). The base node 240 to respond to subsequent messages READ/CNCL peer nodes 210 and 220 maintains a list of conflicts, provided peer-to-peer node 230.

As shown in Figa, in response to an IACK message from the base node 240, peer node 210 transmits to the base node 240 message READ(230*). The message READ does not indicate a conflict with the PRIL message peer-to-peer node 220, because the peer node 210 has not yet received this message PRIL. If the peer node 210 took the PRIL message from peer node 220, the message READ would indicate a conflict with a peer knots is m 220.

In response to the message READ(230*) base unit 240 sends the peer node 230 message XFRI(210)prescribing the peer node 230 to send the requested data to peer node 210. Message XFRI also specifies the peer node 230 that a conflicting message to a peer that has not yet received data (peer-to-peer node 220), requires after sending data to the peer node 210 recognition data unreliable.

Peer node 230 sends the requested data to peer node 210 in message DataE(220), which requires the peer node 210 to store the requested data in the state E, and informs the peer node 210 that request message may conflict with the message to peer node 220. Peer node 230 has detected a conflict with the message to peer node 220. Before peer node 210 will take the requested data, accept arrested the PRIL message from peer node 220.

Because peer-to-peer node 210 has already delivered its list of conflicts in the core node 240 has not received the requested information from peer node 230, peer node 210 stores in the buffer PRIL message, received from a peer node 220. In response to receiving message DATA from peer node 230 having a conflict with a peer node 220, peer node 210 sends to the communication CNFL, indicates that the peer node 210 has a conflict with the PRIL message peer-to-peer node 220.

As shown in Fig.4f, in response to message CNFL from peer node 210, peer node 230 sends a message READ(210, 230*) core node 240 that indicates the presence of conflict with the message PRL peer node 210 and with the PRIL message peer-to-peer node 230. The base node 240 responds to the message READ(210, 230*) message ACK to the peer node 220 and the message XFRI(220) to the peer node 210. Peer node 210 sends the requested data to peer node 220 in message DataE(230). Peer node 220 has preliminarily determined there is a conflict with a peer node 230. Delivery ACK message to the peer node 220 indicates no further conflict with the PRIL message peer-to-peer node 220.

Fig. with 5a through 5g are conceptual views tripartite conflicting requests for uncached data line. As shown in Figa, peer node 210 to request data block sends a message PRIL peer nodes 220 and 230 and the base node 240. Message delivery PRIL core node 240 detained. Shortly after sending the message PRIL peer node 210 peer node 220 sends a message PRIL, requesting a copy of the same data block, the peer nodes 210 and 230 and the base node 240.

As abrajano on Fig.5b, peer node 230 responds to the PRIL message peer-to-peer node 210 IACK message. Peer node 230 indicates a delay in the processing time of his response to the PRIL message peer-to-peer node 220. Peer node 210 responds to the PRIL message peer-to-peer node 220 message CNFLI. Similarly, peer-to-peer node 220 responds to the PRIL message from peer node 210 message CNFLI.

As shown in Figs, before receiving nodes 210 and 220 copies of the requested data, peer node 230 sends a message PRIL peer nodes 210 and 220 and the base node 240. Peer-to-peer nodes 210 and 220 correspond to the PRIL message from peer node 230 messages CNFLI. Due to the delay of message processing PRIL peer node 220 peer node 230 sends to the peer node 220 instead of the message IACK message CNFLI to indicate the presence of a conflict with a newly generated peer node 230 request for the same data block.

As shown in Fig.5d, after receiving responses from all peer nodes in the peer node 230 sends to the base node 240 message READ(210*, 220*). The base node 240 to provide the requested data to peer node 230, responds with a message DataE, as peer-to-peer node 230 is the first peer node, which sends a message READ to the base node 240. Peer node 230 is the current Prime what Lam data.

As shown in Figa, after receiving responses from all peer nodes in the peer node 210 sends the base node 240 message READ(210*, 230*). Base unit 240 also receives delayed the PRIL message from peer node 210. The base node 240 responds to the PRIL message peer-to-peer node 210 IACK message, which indicates that the base node 240 will not provide a copy of the requested data. This is due to the fact that peer-to-peer node 230 has a valid, cached copy of the requested data.

Base unit 240 sends the peer node 230 message XFRI(220)prescribing the peer node 230 to provide a copy of the requested data to peer node 210. Peer node 230 is the second peer node receiving a copy of the requested data, because the peer node 230 is the second peer node that sent the base node 240 message READ by querying the data.

As shown in Fig.5f, peer node 230 sends the message DataE a copy of the requested data to peer node 220. Peer node 210 sends the base node 240 message READ(220*, 230*). The base node 240 responds to the message READ peer node 210 is sent to the peer node 220 messages XFRI (210), which requires the peer node 220 to send a copy of the requested data peer-to-peer is the node 210.

As shown in Figg, peer node 220 sends a copy of the requested data in the message DataE peer node 210. Peer node 220 also recognizes inaccurate copy of the data stored by a peer node 220. Base unit 240 sends an ACK message to the peer node 210, which indicates that all requests on the block data have been resolved and satisfied.

Examples of systems that support non-speculative distributed conflict resolution

Figure 6 depicts a block diagram of a variant of execution of the node. The node 600 is depicted having a single processor, cache memory, memory controller and memory; however, the node may include any quantity of any of these components. In addition, the site may also include additional and/or other components (for example, a bridge between the tires).

The processor 610 may be a processor of any type known in the art. In one embodiment, the processor 610 includes a cache memory 620. In alternative versions of the cache memory 620 is for the processor 610 external, or can be used for more devices of the cache memory, which processor 610 internal or external.

The controller 630 memory connected to the cache memory 620 and a memory 640. The controller 630 memory works as an interface between the cache memory 620 and the memory is updated 640. In one embodiment, the controller 630 memory maintains the coherency of the cache memory in accordance with the Protocol described here coherence cache. The controller 630 memory communicates with other nodes through the communication line 650 site. In an alternative embodiment, the processor 610 communicates with the controller 630 memory to maintain, as described here, the coherence of the cache memory, and a processor 610 communicates with other nodes through an alternate communication line 655 nodes.

In one embodiment, the communication line 650 nodes include a dedicated interface for each node interacts with the node 600. In an alternative embodiment, the communication hub 650 may include multiple interfaces, the number of which differs from the number of nodes communicates with the node 600. In one embodiment, the node 600 communicates with one or more agents (intermediaries), representing the set of nodes.

7 shows one embodiment of a multiprocessor system. Under the multi-processor system 700 refers to the set of systems that have multiple processors, for example, a computer system, the monitoring system in real time, etc. Alternative multiprocessor system may include more or less if estvo components and/or other components. In some cases described here the ways of the cache control can be applied to systems with a single processor and multiprocessor systems. Multiprocessor system 700 can be configured to operate as a multi-node system.

Multiprocessor system 700 includes a bus system 710 or other device (other devices) communication to exchange information. Bus system 710 may include any number of tires and related schemes interconnects, such as bridges between the tires. The processor 720 is connected to a busbar system 710 for processing information. The processor 720 may include a cache memory 722, such as a cache memory level zero (L0), and the controller 724 cache. In one embodiment, the processor 720 is also connected to the cache 725, which may be a cache memory of any type. In an alternative embodiment, the cache 725 can be connected to the bus system 710. Can also be used for other configuration options processor cache.

In one embodiment, the controller 724 cache is connected to the cache memory 722 via the interface 728 cache memory, which may be, for example, the internal processor bus 720. A cache controller connected to the cache memory 725 interface 726 cache memory that provides the interface between the processor 720 and external cache phamacia 700 also includes a processor 730 cache-memory controller 732 and 734 cache. The controller 734 cache is connected to the cache memory 732 interface 738 cache memory. Similarly, the controller 734 cache is connected to the cache memory 735 using the interface 736 cache memory. In one embodiment, the cache memory 735 is connected to the processor 730.

Although a multiprocessor system 700 is shown having two processors, multiprocessor system 700 may include any number of processors and/or coprocessors. Multiprocessor system 700 also includes a system 740 storage connected to the bus system 710. System 740 storage may include any combination of dynamic (e.g., random access memory) and static (e.g., a persistent storage device (RAM, ROM), the ROM on the CD-ROM (CD-ROM), a disk drive, flash memory storage devices and their associated drives, if necessary. The storage device system 740 storage used for storing information and instructions that must be executed by the processors of the multiprocessor system 700. System 740 storage can also be used for storing temporary variables or other intermediate information during execution of instructions by the processor.

Instructions can be provided to the system 740 storage of static or remote storage device, such as a magnet is the first disk, integrated circuit permanent memory (ROM), CD-ROM, digital versatile disk (DVD), via a wired or wireless remote connection, etc. In alternative embodiments, execution instead of or in combination with software instructions can be used hardware. Thus, execution of sequences of instructions is not limited to any specific combination of hardware and software instructions.

Multiprocessor system 700 also includes a network interface 750 to provide access to a network such as a LAN and/or Internet. Network interface 750 can provide wireless and/or wired network interfaces, which may include transmitting instructions to the remote electronic access and/or from it. The environment of electronic access includes any facility that provides (i.e. stores and/or transmits) the content (for example, the machine-executable instructions) in a format readable by an electronic device (e.g., computer, personal information device, a cell phone).

For example, a machine-accessible medium includes a persistent storage device (ROM); random access memory (RAM, RAM); drive on magnetic disks; optical storage media; flash memory is ti; electrical, optical, acoustical or other form of distribution of signals (e.g. carrier waves, infrared signals, digital signals).

Multiprocessor system 700 can also include a display device 760, such as a cathode ray tube (CRT, CRT) or liquid crystal display (LCD, LCD), for displaying information. As a rule, to the bus 710 attached device (s) 770 input data, including, for example, a keyboard having alphanumeric and other keys, to transmit information and commands to the processors 720 and/or 730. Another type of user input devices, serving to convey information about the direction and the selected commands to the processors 720 and 730 and the control cursor movement on display device 760, is a device for cursor control, such as a mouse, trackball (trackball, or cursor control keys.

Used in the description, references to "one implementation" or "an embodiment" means that a particular feature, structure or characteristic described in connection with the option run, included in at least one embodiment of the present invention. Used in various places in the description of the phrase "in one embodiment" does not necessarily mean the treatment is the same version of the runtime.

In the foregoing description the invention has been described with reference to certain ways of its implementation. However, it will be obvious that it may be made of various modifications and changes, within the broad framework of the essence and scope of the invention. The description and drawings should, accordingly, be considered only illustrative, but not limiting context.

The following is an illustrative description of the algorithms MESIF in pseudocode format. Descriptions are based on the packages; that is, each procedure is executed in response to an incoming or outgoing packet. Alternatively, the algorithms can be described as a reaction to a change of state due to the reception or generation package.

To simplify the description made the following assumptions:

1. Each peer/requesting host side has one caching agent;

2. Basic nodes do not have a caching agent; and

3. Algorithms for memory requests in the base nodes can be more complex than shown here, and handle all the edge cases generated MESIF (more than one reading, a lot of times, the recording redirection and so on).

Case with a base unit having a caching agent (which may occur in some embodiments, execution), is derived from the above algorithms, namely what redstem Association procedures for received packets, due to the inclusion of procedures relating to the transfer to/from the base node, the local caching agent (or intermediary).

In one embodiment, the caches satisfy the following constraints:

1. The cache will form PRL, only if the line is in state I.

2. The cache will form PRIL, only if the line is in state I or S.

3. The cache will form PWL, only if the string is in the state M

4. The cache can freely move in the state I from state S, F, and E.

5. The cache can freely move in condition M from state E (the assumption that the record is made.)

6. Other state transitions of the cache can occur only after the completion of a request, which he has issued, or after receiving a request from a peer.

Described below basic Protocol covers only the requests PRL, PRIL and PWL and uses a method of conflict resolution involving conflict list transmitted simultaneously with data transmission. Extensions and additional features of this basic Protocol is covered in the following sections.

Basic Protocol MESIF

Generating query

Procedure call:

The cache generates a new request to (inactive) address

Algorithm:

Mark the address as active

If the request is PRL or PRIL

Send the request to all other who they peer nodes and the base node

If the request is PWL

Send a request to the base node

The request is received by the base node

Procedure call: the Base node has accepted the request

Algorithm:

If the request is PWL

To initiate a memory write

(to handle the sending, canceling pending operations read, etc.)

To send an ACK message back to the requester

If the request is PRL or PRIL

To initiate a read from memory

(Can buffer data if the read ended before a message was received, READ, etc)

Welcome to the requesting peer node

Procedure call:

A peer request received (PRL or PRIL)

Algorithm:

If the address is redirected

To buffer any incoming request

Otherwise, if the address is not active

To track the cache

Otherwise, if the address is active

If the active query is PWL

To buffer any incoming request

- End If

If the incoming request is in the list of active conflicts query

If the active query is PRL

Reply with a message CNFL

Otherwise (the active query is PRIL)

Reply with a message CNFLI

Otherwise, if the active query is "phase data" (see below for a Collection of Answers)

To buffer any incoming request

Otherwise

Add the requesting party in the conflict list (active demand)

If the incoming Zap the OS is PRIL

To mark the requesting party in the conflict list as a conflicting PRIL

If the active query is PRL

Reply with a message CNFL

Otherwise (there is an active request PRIL)

Reply with a message CNFLI

Responses to the request-observation

Procedure call:

In the cache presents the request as a request-observations to generate the appropriate response

Algorithm:

To search for the answer and the next state in the table below based on the current state of the cache and the type of the incoming request (next state S/I indicates that the cache can translate the string in any of the States; note: continue to send DATA_F in response to message PRL, even when recognition is unreliable local copy - see below option Answer PRL DATA_E/M)

If the request-observation PRL locates the desired cache line in state M

To initiate a request PWL

Can buffer the query observation (to delay the DATA_F, until overwritten in the storage device)

Otherwise

If the request-observation locates the desired cache line (in state M, E or F)

Mark the address as redirected

Transfer the cache line in the next state

Send a response to the requester

Collect responses

Procedure call:

Received the response from the peer to the request PRL/PRIL

Algorithm:

If the answer is SACK(only in the case of PRL)

To register the existence of shared copies in the system Otherwise, if the answer is DATA

To register receive forwarded data from the responding node

Send in the cache line of the cache and the new state (note: the line is not yet visible for everyone!)

Otherwise, if the answer is CNFL

Add the responding node in the list conflicts

Otherwise, if the answer is CNFLI

Add the responding node in the list conflicts

To mark the responding node as the calling conflict PRIL

- End If

If you answered all peers

To mark the request as being in the "of f the th data

If you received the response DATA

Send basic node CNCL forwarding node and the list conflicts

Otherwise

To send a basic site, READ and list conflicts

Cancel on the base Assembly

Procedure call:

The base node took CNCL (containing a forwarding node and a list of conflicts)

Algorithm:

To cancel a pending read operation (if exist)

To mark the requesting node is the current owner of this address to Send DACK forwarding node

If there are no conflicts

Send ACK to the requesting node

-- conflict-free cached period completed

Otherwise

Include a list of conflicts for this address as "pending requests"

- wait for messages READ to send messages XFR

A READ request on the base Assembly

Procedure call:

The base node has received the READ (which contains a list of conflicts)

Algorithm:

If there is no current owner

If data is not available

Wait until reading

Send DATA_E to the requesting node

If the conflict list is empty

Send ACK to the requesting node

- conflict-free uncached period completed

Otherwise

Include a list of conflicts for this address as "pending nodes"

Otherwise

Add pending resolution of conflicts to "waiting nodes for this address

is dalite the requesting node from the number of pending nodes"

If there are no remaining pending nodes Send XFR (destination: the requesting node) "current owner"

Send ACK to the requesting node

-- Period completed

Otherwise

If one or more of the outstanding units (including the requesting node) sent PRIL

Send XFRI (destination: the requesting node) "current owner"

Otherwise

Send XFR (destination: the requesting node) "current owner"

To identify the requesting node "current owner"

The message is received on transfer

Procedure call:

The requesting party has received the message XFR or XFRI (containing the target node)

Algorithm:

To wait for data if they have not yet adopted

If taken XFRI

Send inquiry-observation PRIL in the cache

Otherwise

Send inquiry-observation PRL in the cache

Add a list of conflicts (except the host node in the packet DATA. To send packet DATA to the target node

Receiving data transmitted

Procedure call:

As the XFR, the requesting party received DATA contains a list of conflicts)

Algorithm:

To send data to processor

Include a list of conflicts in the current list conflicts

If bateriafina requests coincide with the elements of list conflicts

Reply with a message CNFL for each matching query

Redirection DACK

Procedure call:

Per the smart host took DACK

Algorithm:

To remove the address label redirected

To handle bateriafina requests via an algorithm to accept requests of peers

Request ACK

Procedure call:

The requester has received the ACK from the base node

Algorithm:

If the active request is PWL

Transfer the cache line to the desired next state (E or I)

If buffered request observation (PRL discovered a cache line in state M)

Send DATA_F requesting party

Transfer the cache line in the following state (S) or in the state I Otherwise (the request is a message PRL or PRIL)

To release the buffered requests (i.e. treat them as if they just arrived at the site)

To wait for data if they have not yet adopted

Send the ACK processor

≪<= END BASIC PROTOCOL =≫>

Request PIL

In the above algorithms Protocol only way to translate the node cache line from state F to state E is the recognition string false (put the line in the condition I) and then request PRIL. This causes the transmission of the message DATA.

To support the direct transition F->E can use the query PIL. This request is sent to all peer nodes and the base node, and instructs the rest of the caches to recognize false jointly used the s copies of the cache line, contained in them. To prevent interference in the change of state from sent messages PRIL and/or PRL, the message PIL can be assigned a higher priority.

CHANGES IN the UNDERLYING PROTOCOL:

The formation of the query

Procedure call:

The cache generates a new request (inactive) address

Algorithm:

Mark the address as active

If the request is PRL or PRIL

Send the request to all other peer nodes and the base node

≫ If the request is PIL

≫ Send the request to all other peers

If the request is PWL

Send a request to the base node

Welcome to the requesting peer node

Procedure call:

A peer request received (PRL or PRIL)

The only change in the algorithm is the buffering request, if there is an active request PIL, as is done in the existence of active query PWL.

Receiving a peer request PIL

Procedure call:

A peer request received PIL

Algorithm:

Send in the cache request-observation PIL

Answers to queries-monitoring

Used the same algorithm with the new table "Reply/Next state (no associated with PIL elements for F, E and M, because the requesting party in the state F state F, E, and M is unaimously the who)

Collect responses

Procedure call:

Received the response from the peer to the request PIL

Algorithm:

If all peers answered

Request cache transfer line into the condition E

Release all buffered requests

-- query PIL completed

Immediate response and M>S PWL

The problem of handling in connection with messages PRL detecting cache line in state M, is necessary, rewrite (is spravki messages PWL) before forwarding the data. After making some minor changes to the data can be redirected or rewritten at the same time. The base node does not send DACK, until it becomes as request PWL and CNCL from requesting/winning node.

CHANGES IN the UNDERLYING PROTOCOL:

The request is received by the base node

Procedure call:

The base node has accepted the request

Algorithm:

If the request - PWL

To initiate recording in the storage device

(to handle the redirection canceling pending operations read, etc.)

≫ If PWL was for PRL-found-M

≫ If taken CNCL

≫ Send DACK on a forwarding node that is specified in CNCL

≫ Otherwise

≫ Mark address as writable

≫ Otherwise

≫ Send ACK back to the requester

If the request is PRL or PRIL

To initiate a read from the storage device

(Can buffer data if the read ended up getting READ, etc)

Answers to queries-monitoring

Procedure call:

The request is sent (as request-observation) in the cache to generate the appropriate response

Algorithm:

Search for table ' Reply/Next state as in the basic Protocol

If the request-monitoring detects a cache line in state M, E or F)

Mark the address as redirected

Translate article is CMOS cache in the next state

If the request-observation PRL detects a cache line can Initsiirovat overwrite PWL labeled PRL-found-M

Send DATA_F the requestor is marked as PRL-found-M

Otherwise

Send a response to the requester

Collect responses

Algorithm:

The differences lie in registration data PRL-found-M and notifying the base node of the special redirection when sending CNCL:

Otherwise, if the answer is DATA

To register receive data sent from the responding node

If the request is PRL and found the line in the condition M (specified via the message DATA)

Mark a forwarding node as PRL-found-M

Send cache line and the new state in the cache (note: the cache line is not yet visible for everyone!)

If you answered all peers

If you have received the response DATA

Send CNCL, a forwarding node (labeled PRL-found-M if it happened), and a list of conflicts underlying node

Cancel on the base Assembly

Procedure call:

the base node took CNCL (containing a forwarding node and a list of conflicts)

Algorithm:

The only difference is whether you want to send DACK:

If a forwarding node produced overwrite PRL-found-M

If adopted PWL

Send DACK forwarding node</>

Otherwise

Mark the address as needing rewrite

Otherwise

Send DACK forwarding node

Redirection DACK

There is no difference. Issued PWL treated as a single package (or request complete message DACK).

STATE FM

Another alternative messages PRL detecting lines in the state M, is added to MESIF FM status. This state indicates a shared copy of the modified string. As in state M, if the data is evicted from the cache, they should be overwritten(PWL). As with condition F, the data cannot be changed, and the node responds with a discovery requests to read the string.

If the node has a string in state M, takes PRL, he responds with a message DATA_FM instead of issuing PWL and response message DATA_F.

The transition from FM in state M is not permitted except through PIL. A direct transition from FM in state E is not allowed.

CHANGES IN the UNDERLYING PROTOCOL:

Answers to queries-monitoring

Procedure call:

The request is sent as a query-observations in the cache to generate an appropriate response

Algorithm:

The search for the answer and the next state in the table below, based on the current state of the cache and the type of the incoming request (next state S/I indicates that the cache can translate the line in any of the States; note: still send DATA_F(M) in response to PRL, even if found to be inaccurate local copy - see below option Answer PRL DATA_E/M)

If the request-monitoring detects a cache line in state M, E or F)

Mark the address as redirected

Transfer the cache line in the following condition is

Send a response to the requester

Conflict-free data

Send the list of conflicts together with the transmitted data difficult to implement by hardware. You can unsubscribe from this list of conflicts, if the requests in the middle of a transmission circuit know that they are in the middle and they are allowed to answer buffered requests (using the IACK /SACK) after receiving the transferred data. This allows all the other conflicting nodes to perform further steps, and thus fulfilling the remaining messages READ to reach the base of the node.

In this embodiment, the query (PRL and PRIL, that is, the read requests) are four phases:

1) Phase send - queries

2) the Phase of the collection - the collection (followed by sending messages READ or CNCL)

3) Phase data waiting for data

4) Phase hold - in the middle of the chain of conflicts, delay data to the message XFR, send IACK/SACK on buffered and incoming requests.

In this embodiment, the query will know that he is in the middle of the chain, if no ACK is encapsulated in the transmitted message DATA. Only mentioned phase retention differs from the basic Protocol. In fact, the phase data of the underlying Protocol or remains the same (for non-conflicting requests or queries at the end of the chain of period/purpose is onflict), or divided into two phases, the first of which is still the phase data, and the second is now the phase deductions ending after receiving XFR.

CHANGES IN the UNDERLYING PROTOCOL:

Welcome to the requesting peer node

The only change in the algorithm is to check whether there is an active request in the phase hold:

If the address is redirected

[same as before]

Otherwise, if the address is not active

[same as before]

Otherwise, if the address is active

If the active query - PWL

[same as before]

If the incoming request is in the list of active conflicts query

[same as before]

Otherwise, if the active query is "phase retention"

If the incoming request - PRL

Reply with a message SACK (or IACK, if the previous PRIL got IACK)

Otherwise the incoming request is a PRIL

Mark the active query as needing to invalidate

Reply with a message IACK

Otherwise, if the active query is "phase data"

[same as before]Otherwise

[same as before]

Collect responses

The only change in this algorithm is the fact that the request is completed, if he sends a CNCL, and the conflict list is empty. In other words, the system has transferred the CACHE-TO-Cache and there was no conflict is; the only thing left to do is to notify the base node that does not require acknowledgement (ACK).

Note: the query CNCL (with conflicts) while waiting XFR remains in the phase data, i.e. it is not included in the phase retention.

Cancel on the base Assembly

Procedure call:

The base node took CNCL (containing a forwarding node and a list of conflicts)

Algorithm:

To cancel a pending read operation (if exist)

To identify the requesting node is the current owner of this address

Send DACK to the sending node

If there are no conflicts

-- conflict-free cached period completed

Otherwise

Include a list of conflicts in the "pending requests" for this address-- wait for messages READ to send messages XFR

A read request on the base Assembly

Procedure call:

The base node has received the READ (which contains a list of conflicts)

Algorithm:

If there is no current owner

If data is not available

To initiate a read if necessary

Wait until reading

Send DATA_E to the requesting node

If the conflict list is empty

-- conflict-free uncached period completed

Otherwise

Include a list of conflicts in the form of "waiting for node" for this address

-- wait for messages READ to send messages XFR</>

Otherwise

Add pending resolution of conflicts to "waiting nodes for this address

Remove the requesting node from the pending nodes"

If there are no remaining pending nodes

Send XFR+ACK (destination: the requesting node) "current owner"

-- period completed

Otherwise

If one or more of the outstanding units (including the requesting node) is PRIL

Send XFRI (destination: the requesting node) "current owner"

Otherwise

Send XFR (destination: the requesting node) "current owner"

To identify the requesting node "current owner"

The message is received on transfer

The change here (in addition to handling XFR+ACK) is to determine whether the simulated response IACK for PRIL during phase retention. If so, the string is recognized as false by observation.

Procedure call:

The requesting party took XFR, XFR+ACK or XFRI (containing the target node)

Algorithm:

To wait for data if they have not yet adopted

If taken XFRI or the request is flagged for a false recognition

Send inquiry-observation PRIL in the cache

Otherwise

Send inquiry-observation PRL in the cache

-- End If

If taken XFR+ACK

To send to the destination packet DATA+ACK

Otherwise

Send the target node, the packet DATA

Receiving data transmitted

Procedure call:

abrasively side received DATA or DATA+ACK in the message XFR (the requesting party is in phase data, so she finds out about this through XFR)

Algorithm:

To send data to processor

If the package is received DATA

Translate the request into a phase retention

For each buffered query

If buffered request is PRL

Reply with a message SACK (or IACK, if the previous PRIL took IACK)

Otherwise -- buffered request is PRIL

To celebrate local request as requiring recognition false

Reply with a message IACK

otherwise -- accepted DATA+ACK

-- the request is completed and the period completed

DATA_E/M response to PRL

When the request-observation PRL detects a cache line, it must to maintain korrektnosti reply message DATA_F, regardless transfers the cache line in state S or I. you Can keep sending DATA_E in the transition to state I, but this requires additional communication with the cache, to inform them that received the status of E must be reduced to the status of F. basically, the algorithm is such that if the node has already received DATA_E, then takes a SACK, he must change the cache state from E to F.

1. The way non-speculative allocation resolve conflicting requests for data containing phases, which allow conflicting requests on the block data from multiple peers through peer with an authoritative copy of the requested e is the R, which is requested by the conflicting messages when it referred to a peer that has an authoritative copy of the requested data, selects the target node from the list of peers, who gave conflicting messages; and resolve conflicting requests on the block data through a reference node corresponding to the requested data, if there is no unique, the cached copy is stored on one of the peer nodes, the base unit having an authoritative copy of the requested data, selects the target node from the list of peers, who gave conflicting messages.

2. The method according to p. 1, in which the resolution of conflicting requests by peer contains the steps that take from a peer that does not have accurate copies of the requested data, the list of peers, who gave conflicting requests for the requested data; and transmit a copy of the requested data to the target peer node from the list.

3. The method according to p. 2, wherein transmitting the copy of the requested data to the target peer node further comprises a stage on which to transmit the target peer node of the list minus the transmitting peer.

4. The method according to p. 2, additionally containing a stage on which to take the up a confirmation message from the base node, corresponding to the requested data.

5. The method according to p. 2, additionally containing a stage at which change the state associated with the copy of the requested data stored by a peer node, transmitting the requested data to the target node.

6. The method according to p. 1, in which the resolution of conflicting requests by the base node contains the steps that take from the peer list peer who sent conflicting requests for the requested data; and transmit a copy of the requested data from the base node to the target node from the list.

7. The method according to p. 6, wherein transmitting the copy of the requested data to the target node further comprises a stage on which the transfer target node list minus the transmitting node.

8. The method according to p. 1, wherein the data block contains the string cache.

9. A multi-node system for providing non-speculative distributed conflict resolution of data queries containing multiple device having the cache peer to generate requests for data, and a peer that has reliable, cached copy of the requested data, is designed to resolve conflicting requests and provide copies of the requested data to one of the many requesting peer by using the fact that h is mentioned about the peer, having reliable, cached copy of the requested data, selects the target node of the mentioned set of the requesting peer; and a base node that corresponds to the requested data, coupled with peer-to-peer nodes and the base node is designed to resolve conflicting requests, if there is no peer-to-peer node that stores valid, the cached copy of the requested data, using the fact that the base node selects the target node of the mentioned set of the requesting peer nodes.

10. The system under item 9, in which the requested data contains a cache line.

11. The system under item 9, in which one or more requesting peers for conflict resolution passed peer list peer nodes that have generated conflicting request.

12. System on p. 11, in which the peer node to resolve conflicting requests transmits the target node from the list, a copy of the requested data.

13. The system under item 12, in which the peer node to resolve conflicting requests, in addition, must pass the target node, a copy of the list minus the transmitting node.

14. The system under item 9, in which one or more requesting peers transmit the basic node in the list of peers that generated conflictuous the th query.

15. System on p. 14, in which the base node transmits to the destination node from the list, a copy of the requested data.

16. The system under item 15, in which the peer node to resolve conflicting requests, in addition, must pass the target node, a copy of the list minus the sending and destination nodes.

17. The system under item 9, in which the peer node contains a processor; a cache memory connected to the processor; and an external memory connected to the processor.

18. The system under item 9, additionally containing agent to represent the set of nodes that are connected with peer-to-peer nodes and the base node.

19. A device for providing non-speculative distributed conflict resolution data requests containing a means for resolving conflicting requests on the block data from multiple peers through peer with an authoritative copy of the requested data, which is requested by the conflicting messages when it referred to a peer that has an authoritative copy of the requested data, selects the target node from the list of peers, who gave conflicting messages; and means for resolving conflicting requests on the block data through a reference node corresponding to the requested data, if unique, cached to the Oia is not stored on any of the peers, the base unit having an authoritative copy of the requested data, selects the target node from the list of peers, who gave conflicting messages.

20. The device according to p. 19, in which the means for resolving conflicting requests by the peer node includes means for receiving from a peer that does not have accurate copies of the requested data, the list of peers who sent conflicting requests for the requested data; and means for providing copies of the requested data to the target peer node from the list.

21. The device according to p. 19, in which the means for resolving conflicting requests by the base node includes means for receiving from the peer list peer who sent conflicting requests for the requested data; and means for providing copies of the requested data from the base node to the target node from the list.

22. The device according to p. 19, in which the data block contains the string cache.

23. A node in a multiprocessor computing environment to perform a non-speculative distributed conflict resolution queries containing memory for storing the original and rewritten copies of data corresponding to a predetermined range of addresses; a cache memory for storing a copy for ratively data blocks and the control circuit, connected to the memory and the cache memory for receiving from a peer node a message containing the request for the copy of the block data stored in the memory, and the list of nodes, if any, issued conflicting request message, and the control circuit provides a copy of the requested data to the requesting peer node, and, in addition, the control circuit receives the following conflicting request from a node from the list and sends previous to the requesting node, the message instructing to send a copy of the requested data to the next requesting node.

24. Host by p. 23, in which the data block contains the string cache.

25. Host by p. 23, in which the control circuit includes a processor.

26. Host by p. 23, in which the control circuit includes a memory controller.

27. Host by p. 23, in which the control circuit, in addition, provides the requesting peer node a copy of the above list.