# US 2013/0159684 A1 · Batched replays of divergent operations > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 2013/0159684 A1 - Document ID: US20130159684A1 - Status: Published application - Kind: A1 - Application number: 13/329,066 - Filed: 2011-12-16 - Published: 2013-06-20 - Earliest claimed: 2011-12-16 - Assignees: NVIDIA Corporation - Inventors: Michael Fetterman; Jack Hilaire Choquette; Omkar Paranjape; Anjana Rajendran; Eric Lyell Hill; Stewart glenn Carlton; Rajeshwaran Selvanesan; Douglas J. Hahn; Steven James Heinrich - Web page: https://patentgrep.com/patent/US20130159684A1 ## CPC - G06F 9/3851: {from multiple instruction streams, e.g. multistreaming} - G06F 9/3861: {Recovery, e.g. branch miss-prediction, exception handling (error detection or correction G06F11/00)} - G06F 9/3888: {controlled by a single instruction for multiple threads [SIMT] in parallel} - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract One embodiment of the present invention sets forth an optimized way to execute replay operations for divergent operations in a parallel processing subsystem. Specifically, the streaming multiprocessor (SM) includes a multistage pipeline configured to batch two or more replay operations for processing via replay loop. A logic element within the multistage pipeline detects whether the current pipeline stage is accessing a shared resource, such as loading data from a shared memory. If the threads are accessing data which are distributed across multiple cache lines, then the multistage pipeline batches two or more replay operations, where the replay operations are inserted into the pipeline back-to-back. Advantageously, divergent operations requiring two or more replay operations operate with reduced latency. Where memory access operations require transfer of more than two cache lines to service all threads, the number of clock cycles required to complete all replay operations is reduced. ## Claims ### Claim 1 A computer-implemented method for replaying a common resource access operation, the method comprising: selecting a first thread and a second thread from a group of threads configured to execute an instruction in a multi-stage pipeline, wherein neither the first thread nor the second thread has yet executed the instruction; selecting a first set of threads to associate with the first thread; selecting a second set of threads to associate with the second thread; inserting a first replay operation associated with the first thread and the first set of threads into the multi-stage pipeline to execute the instruction; and inserting a second replay operation associated with the second thread and the second set of threads into the multi-stage pipeline to execute the instruction, wherein the second replay operation is inserted into the multi-stage pipeline serially relative to the first replay operation. ### Claim 2 (depends on 1) The method of claim 1, wherein the common resource is a cache line. ### Claim 3 (depends on 1) The method of claim 1, wherein the first thread and the first set of threads share no common thread with the second thread and the second set of threads. ### Claim 4 (depends on 1) The method of claim 1, wherein the first set of threads is selected concurrently with the selection of the first thread, and the second set of threads is selected concurrently with the selection of the second thread. ### Claim 5 (depends on 1) The method of claim 1, wherein the second replay operation associated with the second thread and the second set of threads is inserted into the multi-stage pipeline one pipeline stage subsequent to the first replay operation associated with the first thread and the first set of threads. ### Claim 6 (depends on 1) The method of claim 1, wherein the first thread and each thread in the first set of threads are configured to access a first common shared resource, and the second thread and each thread in the second set of threads are configured to access a second common shared resource. ### Claim 7 (depends on 6) The method of claim 6, wherein the first replay operation associated with the first thread and the first set of threads and the second replay operation associated with the second thread and the second set of threads are inserted into the multi-stage pipeline via a pipeline stage that is subsequent to a first stage of the multi-stage pipeline. ### Claim 8 (depends on 6) The method of claim 6, wherein a second instruction is inserted into the multi-stage pipeline serially relative to the second replay operation associated with the second thread and the second set of threads. ### Claim 9 A subsystem for replaying a common resource access operation, comprising: a load-store unit (LSU) configured to: select a first thread and a second thread from a group of threads configured to execute an instruction in a multi-stage pipeline, wherein neither the first thread nor the second thread has yet executed the instruction; select a first set of threads to associate with the first thread; select a second set of threads to associate with the second thread; insert a first replay operation associated with the first thread and the first set of threads into the multi-stage pipeline to execute the instruction; and insert a second replay operation associated with the second thread and the second set of threads into the multi-stage pipeline to execute the instruction, wherein the second replay operation is inserted into the multi-stage pipeline serially relative to the first replay operation. ### Claim 10 (depends on 9) The subsystem of claim 9, wherein the common resource is a cache line. ### Claim 11 (depends on 9) The subsystem of claim 9, wherein the first thread and the first set of threads share no common thread with the second thread and the second set of threads. ### Claim 12 (depends on 9) The subsystem of claim 9, wherein the first set of threads is selected concurrently with the selection of the first thread, and the second set of threads is selected concurrently with the selection of the second thread. ### Claim 13 (depends on 9) The subsystem of claim 9, wherein the second replay operation associated with the second thread and the second set of threads is inserted into the multi-stage pipeline one pipeline stage subsequent to the first replay operation associated with the first thread and the first set of threads. ### Claim 14 (depends on 9) The subsystem of claim 9, wherein the first thread and each thread in the first set of threads are configured to access a first common shared resource, and the second thread and each thread in the second set of threads are configured to access a second common shared resource. ### Claim 15 (depends on 14) The subsystem of claim 14, wherein the first replay operation associated with the first thread and the first set of threads and the second replay operation associated with the second thread and the second set of threads are inserted into the multi-stage pipeline via a pipeline stage that is subsequent to a first stage of the multi-stage pipeline. ### Claim 16 (depends on 14) The subsystem of claim 14, wherein a second instruction is inserted into the multi-stage pipeline serially relative to the second replay operation associated with the second thread and the second set of threads. ### Claim 17 A computing device, comprising: a subsystem that includes a load-store unit (LSU) configured to: select a first thread and a second thread from a group of threads configured to execute an instruction in a multi-stage pipeline, wherein neither the first thread nor the second thread has yet executed the instruction; select a first set of threads to associate with the first thread; select a second set of threads to associate with the second thread; insert a first replay operation associated with the first thread and the first set of threads into the multi-stage pipeline to execute the instruction; and insert a second replay operation associated with the second thread and the second set of threads into the multi-stage pipeline to execute the instruction, wherein the second replay operation is inserted into the multi-stage pipeline serially relative to the replay operation. ### Claim 18 (depends on 17) The computing device of claim 17, wherein the first thread and each thread in the first set of threads are configured to access a first common shared resource, and the second thread and each thread in the second set of threads are configured to access a second common shared resource. ### Claim 19 (depends on 18) The computing device of claim 18, wherein the first replay operation associated with the first thread and the first set of threads and the second replay operation associated with the second thread and the second set of threads are inserted into the multi-stage pipeline via a pipeline stage that is subsequent to a first stage of the multi-stage pipeline. ### Claim 20 (depends on 18) The computing device of claim 18, wherein a second instruction is inserted into the multi-stage pipeline serially relative to the second replay operation associated with the second thread and the second set of threads.