Abstract:
A method, including: initiating a memory operation at a first node including a first memory controller (MC) and a transaction table configured to store a list of nodes affected by the memory operation, transmitting a store request signal to a second node including a second MC and an access table (AT) where the store request signal includes data from the first MC, storing data to the AT in entries corresponding to memory address(es) (MAs) affected by the memory operation, identifying a memory conflict with one or more nodes in the list of nodes when the MAs affected by the memory operation are also affected by one or more conflicting transactions listed in the AT, transmitting an abort signal from the second node to each of the nodes corresponding to the memory conflict, and transmitting an intent to commit signal from the first node to the second node.

Description:
BACKGROUND 
     As current designs close in on the physical limits of semiconductor based microprocessors, new problems, such as increased heat dissipation and power consumption, have prompted designers to consider alternatives to the traditional single die microprocessor. Accordingly, designers may employ parallel processing systems that include multiple microprocessors working in parallel in order to surpass the physical limits of a single processor system. However, such parallel systems with multiple processors place different sets of constraints on designers in comparison to single processor systems. For example, parallel processor based systems may have no centralized memory module and instead rely on linking memory modules at each node to create a global memory address space. These systems may have transactional memory support in order to facilitate concurrency control among the various memory modules. However, transactional memory support does not necessarily imply that the system has global cache or memory space coherence. Accordingly, it may be necessary to detect memory conflicts within the transactional memory system in shared memory systems that do not employ global memory coherence. 
     SUMMARY OF THE INVENTION 
     In general, one or more aspects of the invention relate to controlling transactions in a transactional shared memory system having a plurality of nodes connected through an interconnect network. The method involves initiating a memory operation at a first node comprising a first memory controller and a transaction table, wherein the transaction table is configured to store a list of nodes affected by the memory operation, transmitting a store request signal through the interconnect network to a second node comprising a second memory controller and an access table, wherein the store request signal comprises memory operation data from the first memory controller, storing memory operation data to the access table in entries corresponding to one or more memory addresses affected by the memory operation, identifying a memory conflict with one or more nodes in the list of nodes when the one or more memory addresses affected by the memory operation are also affected by one or more conflicting transactions listed in the access table, transmitting an abort signal from the second node to each of the one or more nodes corresponding to the memory conflict, and transmitting an intent to commit signal from the first node to the second node. 
     In general, one or more aspects of the invention relate a method of detecting memory conflicts in a transactional shared memory system having a plurality of nodes connected through an interconnect network. The method includes initiating a memory operation at a first node comprising a first memory controller and a transaction table, wherein the transaction table is configured to store a list of nodes affected by the memory operation, transmitting a store request signal through the interconnect network to a second node comprising a second memory controller and an access table, wherein the store request signal comprises memory operation data from the first memory controller, storing the memory operation data to the access table and indexing the memory operation data by memory addresses affected by the memory operation, and identifying a memory conflict with one or more nodes when the memory addresses affected by the memory operation are also affected by one or more conflicting transactions in the access table. 
     In general, one or more aspects of the invention relate a transactional shared memory system. The system includes a plurality of nodes, each connected through an interconnect network and comprising a memory module, a plurality of memory controllers, each corresponding to one of the plurality of nodes, and a plurality of access tables, each corresponding to one of the plurality of memory controllers and configured to store remote transaction data and memory addresses affected by a remote memory operation corresponding to the remote transaction data, wherein each of the plurality of memory controllers is configured to detect memory conflicts with one or more of the plurality of nodes. 
     Other aspects and advantages of the invention will be apparent from the following description and the appended claims. 
    
    
     
       BRIEF DESCRIPTION OF DRAWINGS 
         FIG. 1  shows a shared memory system in accordance with one or more embodiments disclosed herein. 
         FIG. 2  shows a flow chart of a method detecting memory conflicts in accordance with one or more embodiments disclosed herein. 
         FIG. 3(   a ) shows a transaction table in accordance with one or more embodiments disclosed herein. 
         FIG. 3(   b ) shows an access table in accordance with one or more embodiments disclosed herein. 
         FIG. 3(   c ) shows a reverse access table in accordance with one or more embodiments disclosed herein. 
         FIGS. 4-5  show a flow chart of a method of controlling memory operations in accordance with one or more embodiments disclosed herein. 
         FIG. 6  shows a computer system in accordance with one or more embodiments disclosed herein. 
     
    
    
     DETAILED DESCRIPTION 
     Generally, embodiments of the disclosed invention relate to a system for and method of detecting memory conflicts in a shared memory system in which multiple processors, or nodes, may share memory address space with each other over an interconnect network. Specifically, embodiments of the disclosed invention relate to a system and method for detecting memory conflicts when they occur (“eager detection”) in a shared memory system without global cache or memory space coherence. 
     Specific details of the present disclosure will now be described in detail with reference to the accompanying figures. 
     Referring now to  FIG. 1 , a shared memory system  100  including four nodes (e.g., node A  111 , node B  112 , node C  113 , and node D  114 ) and an interconnect network  120  is shown in accordance with one or more embodiments of the invention. In one or more embodiments of the invention, each of the nodes  111 ,  112 ,  113 , and  114  is able to transmit data signals to, and receive data signals from, each of the other nodes over the interconnect network  120 . For example, each of the nodes may transmit data signals comprising memory addresses and data among each other in order to facilitate a shared memory system. 
     Each of the nodes  111 ,  112 ,  113 , and  114  may be a processor, or a group of processors, in a larger computing system. In accordance with one or more embodiments of the shared memory system  100 , each of the nodes  111 ,  112 ,  113 , and  114  may include memory modules  121 ,  122 ,  123 , and  124 . Accordingly, in this embodiment, the memory modules  121 ,  122 ,  123 , and  124  collectively make up the shared memory space of the shared memory system  100 . Because the interconnect network  120  introduces delay into the system, each of the memory modules  121 ,  122 ,  123 , and  124  may further include a cache to prevent unnecessary memory requests across the interconnect network  120 . Further, each of the nodes  111 ,  112 ,  113 , and  114  may process data in parallel and include support for a transactional based global memory system. Thus, at a given point in time, transactions being processed at two or more of the nodes  111 ,  112 ,  113 , and  114  may simultaneously affect a specific memory address located on one of the memory modules  121 ,  122 ,  123 , and  124 , thereby causing a memory conflict. 
     In order to mitigate memory conflicts, each of the nodes  111 ,  112 ,  113 , and  114  may include memory controllers  131 ,  132 ,  133 , and  134 , respectively, in accordance with one or more embodiments of the disclosed invention. All accesses to the global memory space must be made through a given node&#39;s memory controller. The memory controller may, for example, then determine whether a given memory address is a local address or a remote address that must be accessed through the interconnect network. In accordance with one or more embodiments of the disclosed invention, the memory controllers  131 ,  132 ,  133 , and  134  may detect memory conflicts within the shared memory system  100 . 
     Referring now to  FIG. 2 , a method of detecting a memory conflict within the shared memory system is shown in accordance with one or more embodiments of the invention. First, in step  201 , a node initiates a memory operation to access memory requested by, for example, software being processed on the node in accordance with one or more embodiments of the invention. A memory operation may, for example, be a single instruction included in a series of instructions that make up a transaction. For example, node A  111  initiates a memory operation through the memory controller A  131  that may result in a new value being stored to a memory address located at node C  113 . Accordingly, in step  203 , the memory controller A  131  transmits a store request signal over the interconnect network  120  to the memory controller  133  located at node C  113 . The store request signal may include, for example, memory operation data including transaction identification data and access type. Upon receiving a store request signal, in step  205 , the memory controller  133  stores the memory operation data to an access table indexed by one or more memory addresses that the memory operation may affect in accordance with one or more embodiments of the invention. Next, in step  207 , the memory controller  131  may search the access table to determine whether any other memory operations also affect the same memory address. Finally, in step  209 , the memory controller  131  may identify that a memory conflict has occurred if it finds that other memory operations may affect the same memory address in accordance with one or more embodiments of the invention. 
     Referring now to  FIG. 3(   a ), a transaction table  310  is shown in accordance with embodiments of the invention. The transaction table  310  may be implemented on a memory controller in order to track transactions and any remote nodes that these transactions may affect. For example, transaction ID  311  is associated with a list of nodes  312 , thereby indicating that memory operations within transaction ID  311  may affect memory addresses stored at the nodes listed in the list of nodes  312 . Each of the memory controllers in the shared memory system may implement a transaction table  310  to keep track of outstanding transactions. Once a transaction is completed, the corresponding entry may be deleted from the transaction table  310 . 
     Referring now to  FIG. 3(   b ), an access table  320  is shown in accordance with embodiments of the invention. The access table  320  may be implemented on a memory controller in order to track memory addresses and any memory operation requests that may affect the memory addresses. For example, memory address  321  is associated with a list of transactions  322 , thereby indicating that memory address  321  may be affected by each of the memory operation requests included in the list of transactions  322 . Each of the memory controllers in the shared memory system may implement an access table  320  to keep track of outstanding memory operation requests from remote nodes that may affect the local memory module. Each of the transactions in the list of transaction  322  may include, for example, a transaction ID, memory operation data, and an access type. Once a transaction is completed, the corresponding transaction may be deleted from a list of transactions in the access table  320 . 
     Referring now to  FIG. 3(   c ), a reverse access table  330  is shown in accordance with embodiments of the invention. The access table  330  may be implemented on a memory controller in order to track outstanding transaction IDs and pointers to information stored in an access table. For example, transaction ID  331  is associated with a list of pointers  332 . Each of the pointers in the list of pointers  332  points to an entry in an access table, thereby rendering faster access to a list of transactions that may conflict with transaction ID  331 . Each of the memory controllers in the shared memory system may implement a reverse access table  330  to quickly access outstanding transaction requests and any transactions that may conflict with the transaction requests. Once a transaction is completed, the corresponding transaction may be deleted from the access table  330 . 
     Referring now to  FIG. 4 , a method of controlling memory operations in a shared memory system having a plurality of nodes is shown in accordance with embodiments of the invention. First, in step  401 , a node initiates a memory operation to access memory requested by, for example, software being processed on the node in accordance with one or more embodiments of the invention. For example, node A  111  initiates a memory operation through the memory controller A  131  that will result in a new value being stored to a memory address located at node C  113 . Memory controller A  131  may also enter the transaction ID into a transaction table and store any nodes that the memory operation may affect through remote memory access. 
     Accordingly, in step  403 , the memory controller A  131  transmits a store request signal over the interconnect network  120  to the memory controller C  133  located at node C  113  in accordance with one or more embodiments of the invention. The store request signal may include, for example, memory operation data including transaction identification data and access type. Upon receiving a store request signal, in step  405 , the memory controller C  133  stores the memory operation data to an access table indexed by one or more memory addresses that the memory operation may affect in accordance with one or more embodiments of the invention. The memory controller C  133  may also store transaction ID data and pointers to the access table to a reverse access table in this step. Next, in step  407 , the memory controller C  133  may search the access table to identify whether the memory operation conflicts with any other transactions in accordance with one or more embodiments of the invention. 
     In step  409 , if the memory controller C  133  determines that there may be a memory conflict, the memory controller C  133  transmits an abort signal to any nodes that are processing a transaction that may conflict in accordance with one or more embodiments of the invention. For example, if the memory controller C  133  finds that node B  112  has an transaction that may affect a memory location that the memory operation affects, the memory controller C  133  would transmit an abort signal to node B  112  indicating that node B  112  should abort the conflicting transaction. Next, in step  411  the home node A  111  sends an intent to commit signal to node C  113  to request that the memory operation data written in the access table by memory controller C  133  be committed to the memory module C  123  in accordance with one or more embodiments of the invention. Node C  113  may also return a “transmit OK” signal to node A  111  acknowledging that a commit is okay for the memory operation. Finally, node C  113  may commit the memory operation to the memory module C  123  and transmit a “commit done” signal to node A  111 . 
     Referring now to  FIG. 5 , a method of committing a memory operation in a shared memory system having a plurality of nodes is shown in accordance with embodiments of the invention. First, in step  501 , the local node that is the home of the memory operation retrieves the list of nodes corresponding to the memory operation from the corresponding transaction table and transmits intent to commit signals to each of the retrieved list of remote nodes. Upon receiving an intent to commit signal, in step  503 , each of the remote nodes may consult the corresponding reverse access table to check for abort signals, and respond to the local node, in step  505 , with a commit okay signal. The local node may then wait to receive commit okay signals from each of the remote nodes. Finally, upon receipt of the commit okay signals, in step  507 , the local node may transmit commit done signals to each of the remote nodes indicating that the commit is complete. 
     Advantageously, separating memory operation control into the request, abort, and commit steps allows for the possibility of in-flight abort signals. A node may request to initiate a transaction, but abort before it reaches the commit step, thereby preventing an error in the shared memory system. 
     Referring now to  FIG. 6 , portions of the invention may be implemented in software, such as, for example, a source of data for a memory operation and each of the tables discussed above with respect to  FIGS. 3(   a )- 3 ( c ). Further, whether or not a specific memory store or load is locally cached at a memory controller or initiated on a remote memory controller may be determined in software. For example, an alternative load and write instruction may be implemented in software to ensure that a specific memory store or load is written or loaded through the cache to the original location. Generally, caches may be made write-back to save bandwidth within the system, but a compiler may identify selected memory operations that may affect other nodes and force a write-through operation that is written or loaded through the cache to or from the original memory location. 
     These portions of the invention may be implemented on virtually any type of computer regardless of the platform being used. For example, as shown in  FIG. 6 , a computer system  600  includes a processor  602 , associated memory  604 , a storage device  606 , and numerous other elements and functionalities typical of today&#39;s computers (not shown). The computer system  600  may also include input means, such as a keyboard  608  and a mouse  610 , and output means, such as a monitor  612 . The computer system  600  is connected to a local area network (LAN) or a wide area network (e.g., the Internet) (not shown) via a network interface connection (not shown). Those skilled in the art will appreciate that these input and output means may take other forms, now known or later developed. Further, those skilled in the art will appreciate that one or more elements of the aforementioned computer system  600  may be located at a remote location and connected to the other elements over a network. 
     Further, portions of the invention may be implemented on a distributed system having a plurality of nodes, where each portion of the invention may be located on a different node within the distributed system. In one or more embodiments of the invention, the node corresponds to a computer system. Alternatively, the node may correspond to a processor with associated physical memory. 
     In one or more embodiments of the invention, software instructions to perform embodiments of the invention, when executed by a processor, may be stored on a computer readable medium such as a compact disc (CD), a diskette, a tape, a file, or any other computer readable storage device. Further, one or more embodiments of the invention may be implemented as an Application Program Interface (API) executing on a computer system(s), where the API includes one or more software instructions. 
     Embodiments of the transactional shared memory system disclosed herein may exhibit one or more of the following advantages. The transactional shared memory system disclosed herein may allow for a hardware-based eager (i.e. aggressive) conflict detection scheme that is applicable to non-coherent global shared memory systems, thereby reducing wasted processing due to conflicts. Further, the transactional shared memory system disclosed herein may be light weight, and orthogonal to other components of a shared memory system, such as, for example, a store buffer. The transaction shared memory system disclosed herein may not require broadcasts to all nodes in order to detect memory conflicts. Finally, the transaction shared memory system disclosed herein may allow for minimal processing overhead for transactions with a small number of expected conflicts. 
     While the invention has been described with respect to a limited number of embodiments, those skilled in the art, having the benefit of this disclosure, will appreciate that other embodiments may be devised which do not depart from the scope of the invention as disclosed herein. Accordingly, the scope of the invention should be limited only by the attached claims.