1. A method for detecting a conflict between a transaction and a TLB (Translation Lookaside Buffer) shootdown in a transactional memory in which a TLB shootdown operation message is received by a processor to invalidate at least one entry in a TLB of said processor corresponding to at least one page, the method comprising:
tracking, by said processor, pages touched by said transaction;
determining, by said processor, whether said received TLB shootdown operation message is associated with one of said touched pages; and
aborting, by said processor, said transaction in response to determining that said received TLB shootdown operation message is associated with said one of said touched pages.
2. The method according to claim 1, further comprising:
providing a data structure having entries for said touched pages.
3. The method according to claim 2, further comprising:
initializing all said entries in said data structure at a start of said transaction or at an end of said transaction.
4. The method according to claim 2, further comprising:
issuing a load or store instruction;
determining a page size referenced by said load or store instruction;
determining whether the determined page size is tracked by said data structure;
determining an effective address referenced by said load or store instruction in response to determining that said determined page size is tracked by the data structure;
determining index bits of said load or store instruction based on said determined page size and said determined effective address;
running at least one hash function with said determined index bits in order to locate an entry in said data structure corresponding to said load or store instruction; and
indicating a flag in said entry.
5. The method according to claim 4, further comprising:
checking whether a page size associated with said received TLB shootdown operation message is tracked by using said data structure;
determining a page address associated with said received TLB shootdown operation message if said checked page size is tracked by using said data structure;
selecting a subset of common bits between an effective address and the page address, referenced by said load or store instruction, in order to use the selected subset as said determined index bits, wherein the selected subset is determined by said page size;
running said at least one hash function with said determined index bits in order to locate a further entry in said data structure;
evaluating whether said further entry indicates said flag; and
aborting said transaction if said further entry indicates said flag.
6. The method according to claim 5, further comprising:
aborting said transaction if said checked page size is not tracked by using said data structure.
7. The method according to claim 2, wherein said data structure is a bloom filter.
8. The method according to claim 2, wherein said data structure is included in a memory storage device or a set of registers independent from a cache memory device and independent from said TLB.
9. The method according to claim 2, wherein said data structure is embedded within said TLB.
10. The method according to claim 2, wherein said data structure is embedded within a data cache memory device by marking cache lines that have been accessed during said transaction.
11. The method according to claim 10, further comprising:
searching said marked cache lines in said data cache memory device in order to find cache lines that include portions of said touched pages.
12. The method according to claim 5, further comprising:
making changes made during said transaction permanent if said further entry does not indicate said flag.
13. The method according to claim 5, wherein the page address is a corresponding virtual address in a two-level virtual memory system, or a corresponding physical address in a single-level virtual memory system.
The claims below are in addition to those above.
All refrences to claim(s) which appear below refer to the numbering after this setence.
1. A method of generating a codeword based on a low-density parity check (LDPC) code, wherein the codeword has a message segment, outer code parity segment, and LDPC parity segment, and wherein the LDPC code is associated with a parity check matrix having a corresponding message portion, outer code parity portion, and LDPC parity portion, the method comprising:
processing the message segment of the codeword based on the message portion of the parity check matrix in a first time interval;
processing the outer code parity segment of the codeword based on the outer code parity portion of the parity check matrix in a second time interval subsequent to the first time interval; and
generating the LDPC parity segment of the codeword from the processed message segment and processed outer code parity segment based on the LDPC parity portion of the parity check matrix.
2. The method of claim 1, wherein processing the message segment of the codeword comprises:
multiplying the message segment of the codeword and the message portion of the parity check matrix to produce a partial matrix-vector product.
3. The method of claim 2, wherein the partial matrix-vector product is a first partial matrix-vector product, and wherein processing the message segment of the codeword comprises:
multiplying the outer code parity segment of the codeword and the outer code parity portion of the parity check matrix to produce a second parial matrix-vector product.
4. The method of claim 3, wherein generating the LDPC parity segment of the codeword comprises:
combining the first partial matrix-vector product and the second partial matrix-vector product to produce a complete matrix-vector product; and
computing the LDPC parity segment of the codeword based on the complete matrix-vector product.
5. The method of claim 1, wherein generating the codeword comprises performing a back substitution to obtain the LDPC parity segment of the codeword from the LDPC parity portion of the parity check matrix.
6. The method of claim 1, wherein the parity check matrix comprises a plurality of sub-matrices that are each within the message portion, outer code parity portion, or LDPC parity portion of the parity check matrix, and wherein the message segment of the codeword is processed in a plurality of stages that are each associated with one of the sub-matrices in the message portion of the parity check matrix.
7. The method of claim 6, further comprising:
selecting sub-matrices in a first row of the message portion of the parity check matrix for processing the message segment of the codeword in a first consecutive group of the plurality of stages; and
selecting sub-matrices in a second row of the message portion of the parity check matrix for processing the message segment of the codeword in a second consecutive group of the plurality of stages.
8. The method of claim 6, wherein the outer code parity segment of the codeword is processed in a plurality of stages that are each associated with one of the sub-matrices in the outer code parity portion of the parity check matrix.
9. The method of claim 6, wherein generating the LDPC parity segment of the codeword comprises:
accumulating results of each of the plurality of stages; and
computing the LDPC parity segment of the codeword based on the accumulated results.
10. The method of claim 6, further comprising:
decomposing each of the sub-matrices into a plurality of sub-sub-matrices, wherein each stage of processing the message segment of the codeword is further divided into a plurality of sub-stages that are computed serially.
11. An encoder for generating a codeword based on a low-density parity check (LDPC) code, wherein the codeword has a message segment, outer code parity segment, and LDPC parity segment, and wherein the LDPC code is associated with a parity check matrix having a corresponding message portion, outer code parity portion, and LDPC parity portion, the encoder comprising:
computational logic configured to:
process the message segment of the codeword based on the message portion of the parity check matrix in a first time interval; and
process the outer code parity segment of the codeword based on the outer code parity portion of the parity check matrix in a second time interval subsequent to the first time interval; and
a back substitution module configured to generate the LDPC parity segment of the codeword from the processed message segment and processed outer code parity segment based on the LDPC parity portion of the parity check matrix.
12. The encoder of claim 11, wherein the computational logic is further configured to:
multiply the message segment of the codeword and the message portion of the parity check matrix to produce a partial matrix-vector product.
13. The encoder of claim 11, wherein the partial matrix-vector product is a first partial matrix-vector product, and wherein the computational logic is further configured to:
multiply the outer code parity segment of the codeword and the outer code parity portion of the parity check matrix to produce a second partial matrix-vector product.
14. The encoder of claim 13, wherein the back substitution module is further configured to:
combine the first partial matrix-vector product and the second partial matrix-vector product to produce a complete matrix-vector product; and
compute the LDPC parity segment of the codeword based on the complete matrix-vector product.
15. The encoder of claim 11, wherein the back substitution module is further configured to perform a back substitution to obtain the LDPC parity segment of the codeword from the LDPC parity portion of the parity check matrix.
16. The encoder of claim 11, wherein the parity check matrix comprises a plurality of sub-matrices that are each within the message portion, outer code parity portion, or LDPC parity portion of the parity check matrix, and wherein computational logic is configured to process the message segment of the codeword in a plurality of stages that are each associated with one of the sub-matrices in the message portion of the parity check matrix.
17. The encoder of claim 16, further comprising control logic that interfaces with the computational logic, wherein the control logic is configured to:
select the sub-matrices in a first row of the message portion of the parity check matrix for processing the message segment of the codeword in a first consecutive group of the plurality of stages; and
select the sub-matrices in a second row of the message portion of the parity check matrix for processing the message segment of the codeword in a second consecutive group of the plurality of stages.
18. The encoder of claim 16, wherein the computational logic is configured to process the outer code parity segment of the codeword in a plurality of stages that are each associated with one of the sub-matrices in the outer code parity portion of the parity check matrix.
19. The encoder of claim 16, wherein the back substitution module is further configured to:
accumulate results of each of the plurality of stages; and
compute the LDPC parity segment of the codeword based on the accumulated results.
20. The encoder of claim 16, further comprising control logic that interfaces with the computational logic, wherein the control logic is configured to:
decompose each of the sub-matrices into a plurality of sub-sub-matrices, and wherein the computational logic is further configured to:
process each stage in a plurality of serial sub-stages that are each associated with a different sub-sub-matrix.