# US 8,751,748 B2 · Reader set encoding for directory of shared cache memory in multiprocessor system > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 8,751,748 B2 - Document ID: US8751748B2 - Status: Granted - Kind: B2 - Application number: 13/008,583 - Filed: 2011-01-18 - Published: 2011-09-08 - Granted: 2014-06-10 - Earliest claimed: 2010-01-15 - Assignees: International Business Machines Corporation - Applicants: Daniel Ahn; Luis H. Ceze; Alan Gara; Martin Ohmacht; Zhuang Xiaotong - Inventors: Daniel Ahn; Luis H. Ceze; Alan Gara; Martin Ohmacht; Zhuang Xiaotong - Web page: https://patentgrep.com/patent/US8751748B2 ## CPC - G06F 9/524: {Deadlock detection or avoidance} - G06F 12/0842: for multiprocessing or multitasking - G06F 12/08: in hierarchically structured memory systems, e.g. virtual memory systems - G06F 12/084: with a shared cache - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract In a parallel processing system with speculative execution, conflict checking occurs in a directory lookup of a cache memory that is shared by all processors. In each case, the same physical memory address will map to the same set of that cache, no matter which processor originated that access. The directory includes a dynamic reader set encoding, indicating what speculative threads have read a particular line. This reader set encoding is used in conflict checking. A bitset encoding is used to specify particular threads that have read the line. ## Claims ### Claim 1 In a multiprocessor system comprising a plurality of processors running speculative threads in parallel; and at least one cache shared by the processors, a method comprising: in a control unit of the cache, maintaining a dynamic record of read accesses to the cache, the record comprising for each cache line a format specification indication specifying a reader encoding format responsive to occurrence of a type of read access, said type including transactional memory (TM), thread level speculation (TLS) and rollback, the record comprises an identification of which speculative thread or threads has read a particular cache line, said identification in the form of a field that encodes thread identification numbers of a group of threads, wherein each bit of said field represents a group of IDs, an aggregate of all IDs is represented as the aggregate of all bits of the field; and a bit set in the field representing the cache line has been read by at least one ID of a corresponding group; directing memory accesses for a same physical address from any of the processors through a same memory addressing scheme of the control unit; abrogating recordation of portions of lines read responsive to one or more of: more than two speculative TM threads have read from the line, a mix of TM and TLS threads have read from the line, and TLS threads from different domains have read from the line; and performing conflict checking for all the processors of the system using the record to locate potential conflicts. ### Claim 2 (depends on 1) The method of claim 1, wherein the identification comprises at least one thread identification number. ### Claim 3 (depends on 2) The method of claim 2, comprising an identification number for each of a plurality of threads that has read that version. ### Claim 4 (depends on 1) The method of claim 1, wherein the identification comprises, for each version of data, an indication of a set of identification numbers that read that version. ### Claim 5 (depends on 1) The method of claim 1, wherein the field encodes a subset of available thread identification numbers in accordance with one bit per number. ### Claim 6 (depends on 5) The method of claim 5, wherein the subset is all thread identification numbers sharing a sequence of more significant bits. ### Claim 7 (depends on 6) The method of claim 6, further comprising storing a pointer to locate speculation identification numbers associated with the subset. ### Claim 8 (depends on 1) The method of claim 1, wherein the field is configured to be able to indicate up to all available speculation identification numbers in accordance with one bit per group of IDs. ### Claim 9 (depends on 4) The method of claim 4, wherein the record comprises two IDs defining the boundaries of a range of ordered IDs. ### Claim 10 (depends on 1) The method of claim 1, wherein the identification is configured to represent a superset of the threads that have accessed the line. ### Claim 11 (depends on 1) The method of claim 1, wherein conflict checking comprises comparing to detect conflicts of current access with previous accesses. ### Claim 12 (depends on 1) The method of claim 1, wherein conflict checking comprises invalidating copies of lines where requesting memory accesses have implicated multiple values. ### Claim 13 (depends on 1) The method of claim 1, wherein the dynamic record comprises an indication of how many threads read the line. ### Claim 14 (depends on 1) The method of claim 1, comprising recording read accesses to more than one version from a single read request. ### Claim 15 (depends on 1) The method of claim 1, wherein maintaining comprises storing IDs in the directory to distinguish one or more speculative versions for the same address. ### Claim 16 (depends on 1) The method of claim 1, wherein the reader encoding format is dependent on a mode of speculation used in generating the read access. ### Claim 17 (depends on 1) The method of claim 1, wherein the reader encoding format is dependent on what set of identification numbers of threads have accessed the cache line. ### Claim 18 (depends on 1) The method of claim 1, wherein the indication comprises a format allowing for one to three speculative thread identification numbers to be listed. ### Claim 19 A multiprocessor system, comprising a plurality of processors configured to carry out speculative execution in parallel; at least one data pathway configured to direct all memory accesses for a same physical address to a shared cache resource; a cache memory comprising the shared cache resource; and a directory based conflict checking mechanism, the mechanism comprising a record comprising for each cache line a reader set encoding format that dynamically represents threads that have read from the shared resource and/or occurrences of types of read accesses to the shared resource, said types including transactional memory (TM), thread level speculation (TLS) and rollback, the record comprising an indication of which speculative thread or threads has read a particular cache line, the indication in the form of a field that encodes thread identification numbers of a group of threads, and further comprising abrogating recordation of portions of lines read responsive to one or more of: more than two speculative TM threads have read from the line, a mix of TM and TLS threads have read from the line, and the TLS threads from different domains have read from the line, wherein each bit of said field represents a group of IDs, an aggregate of all IDs is represented as the aggregate of all bits of said field; and a bit set in a field representing the cache line has been read by at least one ID of a corresponding group. ### Claim 20 (depends on 19) The system of claim 19, wherein the format is dependent on a mode of speculation used in generating a corresponding read access.