Configurable transactional memory for synchronizing transactions

A configurable transactional memory synchronizes transactions from clients. The configurable transactional memory includes a memory buffer and a transactional buffer. The memory buffer includes allocation control and storage, and the allocation control is configurable to selectively allocate the storage between a transactional buffer and a data buffer for the data words. The transactional buffer stores state indicating each combination of a data word and a client for which the data word is referenced by a write access in the transaction in progress from the client. The transactional arbiter generates the completion status for the transaction in progress from each client. The completion status is either committed for no collision or aborted for a collision. A collision is an access that references a data word of the transaction from the client following a write access that references the data word of another transaction in progress from another client.

FIELD OF THE INVENTION

The present invention generally relates to transactional memories, and more particularly to configurable transactional memories.

BACKGROUND OF THE INVENTION

Programmable logic devices (PLDs) are a well-known type of integrated circuit that can be programmed to perform specified logic functions. One type of PLD, the field programmable gate array (FPGA), typically includes an array of programmable tiles. These programmable tiles can include, for example, input/output blocks (IOBs), configurable logic blocks (CLBs), dedicated random access memory blocks including block RAM (BRAM), multipliers, digital signal processing blocks (DSPs), processors, clock managers, delay lock loops (DLLs), and so forth.

Each programmable tile typically includes both programmable interconnect and programmable logic. The programmable interconnect typically includes a large number of interconnect lines of varying lengths interconnected by programmable interconnect points (PIPs). The programmable logic implements the logic of a user design using programmable elements that can include, for example, function generators, registers, arithmetic logic, and so forth.

A user design may implement a multiprocessing system in a PLD that includes multiple dedicated processors. A user design may also implement a multiprocessing system by implementing soft processors in the programmable logic and interconnect resources of the PLD. An example user design may implement a multiprocessing system in a PLD using a dedicated processor and a soft processor that is a state machine specifically designed to implement a particular function of the user design.

To perform the function of the user design, the processors may need to exchange data. It may be time consuming and expensive to design the protocols for exchanging data between the processors of a multiprocessing system. The exchange of data between the processors may limit the performance of the multiprocessing system.

The present invention may address one or more of the above issues.

SUMMARY OF THE INVENTION

Various embodiments of the invention provide a configurable transactional memory for synchronizing transactions from clients. Each client has a transaction in progress until a completion status is generated for the transaction. The transaction in progress from the client includes one or more accesses. Each access is either a read access or a write access referencing a data word in the configurable transactional memory. The configurable transactional memory includes a memory buffer and a transactional buffer. The memory buffer includes allocation control and storage. The allocation control is configurable to selectively allocate the storage between a transactional buffer and a data buffer for the data words. The transactional buffer stores state indicating each combination of a data word and a client for which the data word is referenced by a write access in the transaction in progress from the client. In response to the state, the transactional arbiter generates the completion status for the transaction in progress from each client. The completion status is either committed in response to an absence of a collision or aborted in response to a presence of a collision. The collision is present for an access that references a data word of the transaction from the client following a write access that references the data word of another transaction in progress from another client.

DETAILED DESCRIPTION

FIG. 1is a block diagram of a system illustrating a configurable transactional memory102in accordance with various embodiments of the invention. Each client104through110may be a processor or a state machine for processing transactions.

The clients104through110of a multiprocessor system may efficiently exchange data using read and write accesses to a configurable transactional memory102. The configurable transactional memory102may synchronize the exchange of data without using locks or mutexes. Compared to locks or mutexes, the configurable transactional memory102may provide better performance and simpler protocols for exchanging data. Performance may be improved because the overhead of locks and mutexes is eliminated. The protocols may be simpler because synchronization is provided by the configurable transactional memory102instead of user-supplied locks and/or mutexes. The simplified synchronization of data exchange using configurable transactional memory102may improve robustness by eliminating user-supplied locks and/or mutexes that are complex and prone to error.

The configurable transactional memory102may synchronize transactions from clients104through110. A transaction may include multiple read and/or write accesses, and the configurable transactional memory102should process these accesses as an atomic operation. The configurable transactional memory102may successfully complete the accesses of the transaction after atomically performing the accesses. If a conflict prevents the configurable transactional memory102from atomically performing the accesses, the configurable transactional memory102may abort the transaction. After the configurable transactional memory102aborts a transaction from client104, client104may later retry the transaction. The configurable transactional memory102might successfully complete the retried transaction when the conflict has cleared.

Example applications for configurable transactional memory102include network processing and query processing for a database. Each transaction from one of clients104through110may be readily specified in a localized region of the control flow of a software program executed by a processor or in a localized sequence of states of a state machine.

In an example scenario, client104may issue a transaction on line112to configurable transactional memory102. If the configurable transactional memory102successfully completes the accesses of the transaction as an atomic operation, the configurable transactional memory102may respond with a commit signal on line114. If the configurable transactional memory102could not atomically perform the accesses of the transaction because of a collision conflict with another transaction from another client106, the configurable transactional memory102may respond with an abort signal on line116.

The configurable transactional memory102may include a memory buffer120and a transactional arbiter122. The memory buffer120may include allocation control124and storage126. Allocation control124may divide the storage126between a transactional buffer128and a data buffer130. The transactional buffer128may include states132through134for tracking the accesses of clients104through110, respectively. Each access of the transactions may read or write one of data words136though138or a portion of one of these data words.

In one embodiment, each client104through110may issue one transaction at a time, and each transaction may include multiple accesses that each read or write one of data words136through138. State132may track the accesses of the current transaction in progress from client104. State132may include a read bit for each data word136through138that is read or referenced by the current transaction from client104, and state132may include a write bit for each data word136through138that is written or referenced by the current transaction from client104. For each access of the current transaction from client104, the transactional arbiter122may update the state132to set the read or write bit as appropriate for the type of access to the data word.

In an example scenario, for each access of the current transaction from client104, transactional arbiter122checks the states of the other clients, for example, state134, for a collision with a write access in an in-progress transaction from another client, for example, client110. If the state134indicates the current transaction from client110has referenced the data word, then transactional arbiter122updates state132for client104to indicate the presence of the collision. The transaction arbiter122may similarly check for a collision between the access and the current transaction from the other clients106and108.

After client104has completed the accesses of the current transaction, client104may request completion of the transaction. For example, client104may issue a commit request on line112to request completion of the transaction. Transactional arbiter122may check state132for the presence of a collision. If a collision is present, transactional arbiter122may generate a completion status of aborted by asserting the abort signal on line116. For the absence of a collision, transactional arbiter122may generate a completion status of committed by asserting the commit signal on line114. The transactional arbiter122may also clear the state132to indicate that the current transaction from client104is no longer in progress.

It will be appreciated that configurable transactional memory102may support multiple transactions in progress from each client. For example, configurable transactional memory102may support two current transactions in progress from a client that is a virtual combination of clients104and106.

In one embodiment, configurable transactional memory102supports accesses both within and outside of transactions. For example, transactions may include accesses that read or write only data word136, and other accesses outside the transaction may read or write only data word138. Thus, a portion of the data buffer130may be allocated for atomic transactions and another portion of the data buffer may be allocated for non-atomic accesses.

In another embodiment, allocation control124may be included as a component140of transaction arbiter122. For example, memory buffer120may include only storage126that is one or more block RAMs of a PLD. Transactional arbiter122may be dedicated logic of the PLD that may be configured with the size of the transactional buffer128and the data buffer130.

In one embodiment, states132through134are included in respective entries in transactional buffer128for the data words accessed by one or more of the current transactions in progress from clients104through110. Transactional arbiter122may create an entry in transactional buffer128for each access to a data word without an already existing entry. Transactional arbiter122may delete an entry from transactional buffer when no in-progress transaction references the data word for the entry.

FIG. 2is a field diagram of an example entry for tracking accesses to a data word in accordance with various embodiments of the invention. The tag field204contains an address tag of the one of data words136through138referenced by the access. The data field202contains a temporary copy of the data word. The read fields, read1, read2, . . . read N (206,208, and210) and write fields write1, write2, . . . write N (212,214, and216) are used to indicate the type of the access (read or write) and the one of clients1-N that is the source of the access. For each access to a data word without an existing entry, the transactional arbiter creates a new entry in the transactional buffer with the format shown inFIG. 2. For example, to create a new value of the data word136from data buffer130into the data field202of the new entry in transactional buffer128. The transactional arbiter122sets the tag field204of the new entry to the storage126address of the data word136. The transactional arbiter122initializes the tracking state of fields206through216in the new entry by clearing these fields.

In an example scenario, for each read access of a transaction from client106, the transactional arbiter122sets the corresponding read bit field208of the entry for the data word referenced by the read access. In another example, for each write access of a transaction from client106, the write field214is set in the entry for the data word referenced by the write access, unless there is a collision because one of the other write fields212and216is already set. Although multiple read fields206through210may be set, usually at most one of write fields212through216is set. For each write access of a transaction from client106, the transactional arbiter122may write the write data of the write access to the data field202of the entry for the data word. For an access of a transaction from another client, for example, client104, to the same data word, the transactional arbiter122may check whether any of write fields212through216are already set in the entry. If any of the write fields212through216are already set, the transactional arbiter122may abort the transaction from client104because of the collision with the transaction in progress from another client.

On successful or aborted completion of a transaction from client104, the transactional arbiter122may clear the read field206and the write field212of the entries for every data word accessed by the transaction. If the clearing of field206and212causes all fields206through216of the entry for data word136to become cleared, no transaction in progress is referencing data word136. The transactional arbiter122may then delete the entry from the transactional buffer128. For an aborted transaction, the transactional arbiter122may delete the entry including discarding the data field202of the entry. For a successfully committed transaction that had the write field212set in the entry for data word136, the transactional arbiter122may first transfer the data field202of the entry from the transactional buffer128to the data word136in the data buffer130.

In one embodiment, for each read access of a transaction from client106, the transactional arbiter122may set the read field208of the entry unless the write field214is already set. For each write access of a transaction from client106, the transactional arbiter122may clear the read field208of the entry and set the write field214of the entry. For an access of a transaction from another client104to the same data word when any of write fields212through216is already set in the entry, the transactional arbiter122may indicate the presence of a collision by setting both the read field206and the write field212in the entry.

FIG. 3is a block diagram of a programmable logic device that may include a configurable transaction memory in accordance with one or more embodiments of the invention.

As noted above, advanced PLDs can include several different types of programmable logic blocks in the array. For example,FIG. 3illustrates an FPGA architecture300that includes a large number of different programmable tiles including multi-gigabit transceivers (MGTs301), configurable logic blocks (CLBs302), random access memory blocks (BRAMs303), input/output blocks (IOBs304), configuration and clocking logic (CONFIG/CLOCKS305), digital signal processing blocks (DSPs306), specialized input/output blocks (I/O307) (e.g., configuration ports and clock ports), and other programmable logic308such as digital clock managers, analog-to-digital converters, system monitoring logic, and so forth. Some FPGAs also include dedicated processor blocks (PROC310).

For example, a CLB302can include a configurable logic element (CLE312) that can be programmed to implement user logic plus a single programmable interconnect element (INT311). A BRAM303can include a BRAM logic element (BRL313) and a transactional arbiter316in addition to one or more programmable interconnect elements. Typically, the number of interconnect elements included in a tile depends on the height of the tile. In the pictured embodiment, a BRAM tile has the same height as four CLBs, but other numbers (e.g., five) can also be used. Similarly, a DSP tile306can include a DSP logic element in addition to an appropriate number of programmable interconnect elements. An IOB304can include, for example, two instances of an input/output logic element (IOL315) in addition to one instance of the programmable interconnect element (INT311). As will be clear to those of skill in the art, the actual I/O pads connected, for example, to the I/O logic element315are manufactured using metal layered above the various illustrated logic blocks, and typically are not confined to the area of the input/output logic element315.

The BRAM logic element313may be used as a block memory by a user design that disables the transaction arbiter316. Together, the BRAM logic element313and the transaction arbiter316may implement a configurable transactional memory. It will be appreciated that certain BRAM303of architecture300may omit the transaction arbiter316.

In the pictured embodiment, a columnar area near the center of the die (shown shaded inFIG. 3) is used for configuration, clock, and other control logic. Horizontal areas309extending from this column are used to distribute the clocks and configuration signals across the breadth of the FPGA.

Some FPGAs utilizing the architecture illustrated inFIG. 3include additional logic blocks that disrupt the regular columnar structure making up a large part of the FPGA. The additional logic blocks can be programmable blocks and/or dedicated logic. For example, the processor block PROC310shown inFIG. 3spans several columns of CLBs and BRAMs.

FIG. 4is a flow diagram of a process400for tracking accesses of transactions for a configurable transactional memory in accordance with various embodiments of the invention. The configurable transactional memory may store state for tracking the accesses of the transactions.

At step402, configuration data is generated for the configurable transactional memory and the configurable transactional memory is configured with the configuration data. Various aspects of configurable transactional memory may be configured. A number of block RAMs may be selected to set the total size of storage in a memory buffer. The storage in the memory buffer may be allocated between a transactional buffer for tracking transactions and a data buffer for storing data words read and written by accesses of the transaction. A mode may be selected for how to notify a client of the completion of a transaction from the client. Two clients may have differing notification modes.

Decision404waits for an access from a client. The access may be a read, write, or read-modify-write access to a specified data word or a portion of a specified data word.

Decision406checks whether the data word already has tracking state in the transactional buffer. If the data word already has tracking state from a transaction in progress, process400proceeds to decision408; otherwise, process400proceeds to step410. At step410, an entry for the data word is created in the transactional buffer with the tracking state cleared. At step412, the data word is copied from the memory buffer to the entry in the transactional buffer.

Decision408checks whether an in-progress transaction from a different client has referenced the data word as indicated by the existing state for the data word. If the existing state indicates a collision from a prior write, process400proceeds to step414; otherwise, process400proceeds to step416.

At step416, a bit for the client may be set in the tracking state of the entry in the transactional buffer for the data word. If the access is a read access, a read bit for the client may be set in the entry for the data word, and if the access is a write access, a write bit for the client may be set in the entry for the data word.

At step414, a collision bit may be set for the client in the tracking state of the entry for the data word. A transaction is aborted if there is a collision for an access of the transaction. However, the transaction may be aborted either immediately or after processing the other accesses of the transaction. Decision418checks whether the configurable transactional memory was configured at step402to immediately abort the transaction. For the immediate abort mode, process400proceeds to step420; otherwise, process400returns to decision404to wait for the next access from one of the clients.

A transaction may also be aborted on request from the client issuing the transaction. Decision422checks whether the client has requested that the transaction be aborted. For an abort request, process400proceeds to step420; otherwise, process400proceeds to decision424. It will be appreciated that abort requests may be processed asynchronously. For example, another process may check for abort requests from the clients.

At step420, the transaction of the current access is aborted. The bits of the tracking state for the client are cleared in the entry or entries of every data word accessed by the transaction. If a particular data word has not been accessed by any current transaction in progress from the other clients, the clearing of the bits for the client may clear the entire tracking state of the entry. Any write data in the entry may be discarded and the entry may be deleted from the transactional buffer.

Decision424checks the access type of the current access to a data word. If the access is a write access then process400proceeds to step426, and if the access is a read access then process400proceeds to step428. At step426, the write data of the write access is written into the entry in the transactional buffer for the data word. For a write access that writes a portion of a data word, the write data may be merged with the data in the entry for the data word. At step428, read data from the entry for the data word is returned to the client.

Decision430checks whether configurable transactional memory was configured at step402to speculatively commit transactions. For speculative commit mode, process400proceeds to step432; otherwise, process400returns to decision404to await the next access. At step432, the client issuing the access is notified that the client may commit the transaction if the transaction does not include any more accesses. If the transaction includes another access, another speculative commit may be generated for this additional access. The client may still be expected to request a commit of the transaction that causes the configurable transactional memory to clean up the tracking state for the transaction.

FIG. 5is a flow diagram of a process for completing transactions for a configurable transactional memory in accordance with various embodiments of the invention. The configurable transactional memory may successfully complete the current transaction if the transaction does not have a collision. The configurable transactional memory may abort the current transaction if the transaction does have a collision.

Decision502waits for a commit request for the current transaction from a client. Decision504checks whether a collision is present for the client. Tracking state may indicate whether a collision was previously detected for an access of the current transaction. If a collision is present, process500proceeds to decision506; otherwise, process500proceeds to decision508.

Decision508checks whether the current transaction has accessed more data words. A transaction arbiter may scan through the entries in the transaction buffer to find the next entry having set state bits for the client. If the current transaction has accessed another data word, then process500proceeds to decision510; otherwise, process500proceeds to step512. At step510, the entry for the data word is checked for a set write bit for the client. If the write bit is set in the entry for the data word, process500proceeds to step514; otherwise process500returns to decision508. At step514, data including write data for the current transaction is copied from the entry in the transactional buffer to the data word in the data buffer.

At step512, the configurable transactional memory generates a committed completion status for the current transaction, and the current transaction is no longer in progress.

Decision506checks the abort mode. For an immediate abort mode, process500returns to decision502because the transaction has already been aborted. Otherwise, process500proceeds to step516to abort the transaction. At step516, the configurable transactional memory generates an aborted completion status for the current transaction, and the current transaction is no longer in progress.

At step518, the state tracking bits for the client are cleared in the entry for each access of the current transaction. At step520, each entry that has all state tracking bits clear is deleted from the transactional buffer.

FIG. 6is a block diagram of a system for configuring a configurable transactional memory in accordance with various embodiments of the invention. An initial step in the usage of a configurable transactional memory may include configuring the configurable transactional memory for synchronizing a specified set of transactions for a particular user design.

A processor-readable device602may be configured with software modules604through614for configuring a configurable transactional memory. Execution of the instructions in software module604may cause processor616to select a number of the clients for the configurable transactional memory. Software module606may cause processor616to allocate storage for data words in a data buffer of the configurable transactional memory. Software module608may cause processor616to allocate storage for a transactional buffer of the configurable transactional memory.

A static analysis of the transactions specified in software for the clients may set the size of the transaction buffer. A compiler may statically analyze the transactions during compilation of the software. While a non-configurable transactional memory may have equal amounts of storage for the transactional and data buffers to support any possible set of transactions, the static analysis of the actual set of transactions may permit allocating less than half of the storage to the transactional buffer of the configurable transactional memory. Because less storage is needed, the configurable transactional memory may more efficiently implement a transactional memory for any particular set of transactions. Because the amount of storage can be determined for any given set of transactions, the configurable transactional memory may still support any possible set of transactions.

Software module610may cause processor616to determine a number of block RAMs for a memory buffer that includes the data and transactional buffers. Software module612may cause processor616to generate and output configuration data for configuring the configurable transactional memory to support the number of clients using the number of block RAMs for the memory buffer. Software module614may cause processor616to configure the configurable transactional memory with the configuration data.