Using police threads to detect dependence violations to reduce speculative parallelization overhead
View Patent ↗A method for detecting a dependence violation in an application that involves executing a plurality of sections of the application in parallel, and logging memory transactions that occur while executing the plurality of sections to obtain a plurality of logs and a plurality of temporary results, where the plurality of logs is compared while executing the plurality of sections to determine whether the dependence violation exists.
1. A method for performing speculative parallelization, comprising:
executing, by a first computer processor, a first co-thread of an application;
executing, by a second computer processor, a second co-thread of the application in parallel with the first co-thread;
assigning a first memory log to the first co-thread;
assigning a second memory log to the second co-thread;
assigning a first police thread to the first memory log and the second memory log;
while executing the second co-thread in parallel with the first co-thread:
logging, in the first memory log, a first plurality of memory transactions requested by the first co-thread;
logging, in the second memory log, a second plurality of memory transactions requested by the second co-thread;
maintaining a plurality of temporary results for the first co-thread and the second co-thread;
performing, by the first police thread, a first comparison of the first memory log with the second memory log; and
identifying, based on the first comparison, a first dependence violation between the first co-thread and the second co-thread, wherein the first dependence violation is caused by a write to a memory location performed by the first co-thread before a read to the same memory location performed by the second co-thread; and
in response to identifying the first dependence violation:
determining a location of the read within the second co-thread where the first dependence violation occurs;
committing a first portion of the plurality of temporary results occurring prior to the location;
rolling back a second portion of the plurality of temporary results occurring after the location; and
generating a notification of the first dependence violation.
2. The method of claim 1 , wherein the first co-thread and the second co-thread each comprise at least one conditional expression of the application.
3. The method of claim 1 , wherein the first co-thread and the second co-thread each comprise a plurality of iterations in a loop of the application.
4. The method of claim 3 , wherein the first comparison is performed in order of the plurality of iterations in the loop.
5. The method of claim 1 , wherein the first memory log and the second memory log comprise only memory transactions associated with at least one indeterminable variable.
6. The method of claim 1 , wherein performing the first comparison comprises:
comparing a portion of the first plurality of memory transactions corresponding to the write in the first memory log with a portion of the second plurality of memory transactions corresponding to the read in the second memory log.
7. A system for performing speculative parallelization, comprising:
a first co-thread executing on a first computer processor;
a second co-thread executing on a second computer processor in parallel with the first co-thread;
a first memory log assigned to the first co-thread and configured to:
log, while executing the second co-thread in parallel with the first co-thread, a first plurality of memory transactions requested by the first co-thread;
a second memory log assigned to the second co-thread and configured to:
log, while executing the second co-thread in parallel with the first co-thread, a second plurality of memory transactions requested by the second co-thread; and
a first police thread assigned to the first memory log and the second memory log and configured to:
while executing the second co-thread in parallel with the first co-thread:
identify a plurality of temporary results for the first co-thread and the second co-thread;
perform a first comparison of the first memory log with the second memory log; and
identify, based on the first comparison, a first dependence violation between the first co-thread and the second co-thread, wherein the first dependence violation is caused by a write to a memory location performed by the first co-thread before a read to the same memory location performed by the second co-thread; and
in response to identifying the first dependence violation:
determine a location of the read within the second co-thread where the first dependence violation occurs;
commit a first portion of the plurality of temporary results occurring prior to the location;
roll back a second portion of the plurality of temporary results occurring after the location; and
generate a notification of the first dependence violation.
8. The system of claim 7 , wherein the first co-thread and the second co-thread each comprise at least one conditional expression of the application.
9. The system of claim 7 , wherein the first co-thread and the second co-thread each comprise a plurality of iterations in a loop of the application.
10. The system of claim 9 , wherein the first comparison is performed in order of the plurality of iterations in the loop.
11. The system of claim 7 , wherein performing the first comparison comprises:
comparing a portion of the first plurality of memory transactions corresponding to the write in the first memory log with a portion of the second plurality of memory transactions corresponding to the read in the second memory log.
12. A distributed computer system for performing speculative parallelization, comprising:
a plurality of physical nodes;
a first co-thread executing on a first physical node of the plurality of physical nodes;
a second co-thread executing, in parallel with the first co-thread, on a second physical node of the plurality of physical nodes;
a first memory log assigned to the first co-thread and configured to:
log, while executing the second co-thread in parallel with the first co-thread, a first plurality of memory transactions requested by the first co-thread;
a second memory log assigned to the second co-thread and configured to:
log, while executing the second co-thread in parallel with the first co-thread, a second plurality of memory transactions requested by the second co-thread; and
a police thread assigned to the first memory log and the second memory log and configured, while executing the second co-thread in parallel with the first co-thread, to:
identify a plurality of temporary results for the first co-thread and the second co-thread;
perform a first comparison of the first memory log with the second memory log;
identify, based on the first comparison, a first dependence violation between the first co-thread and the second co-thread, wherein the first dependence violation is caused by a write to a memory location performed by the first co-thread before a read to the same memory location performed by the second co-thread; and
in response to identifying the first dependence violation:
determine a location of the read within the second co-thread where the first dependence violation occurs;
commit a first portion of the plurality of temporary results occurring prior to the location;
roll back a second portion of the plurality of temporary results occurring after the location; and
generate a notification of the first dependence violation.
13. The method of claim 1 , further comprising:
executing a third co-thread of the application in parallel with a fourth co-thread of the application;
creating a third memory log and a fourth memory log;
assigning a second police thread to the third memory log and the fourth memory log;
while executing the third co-thread in parallel with the fourth co-thread:
logging, in the third memory log, a third plurality of memory transactions requested by the third co-thread;
logging, in the fourth memory log, a fourth plurality of memory transactions requested by the fourth co-thread;
performing, by the second police thread, a second comparison of the third memory log with the fourth memory log to create a first police thread log;
performing a third comparison of the first police thread log with a second police thread log, wherein the second police thread log is created based on a parallel execution of a fifth co-thread of the application with a sixth co-thread of the application;
identifying, based on the third comparison, a second dependence violation; and
generating a notification of the second dependence violation.
14. The method of claim 1 , further comprising:
re-starting, after committing the first portion of the plurality of temporary results, serial execution of the first co-thread at the location.
15. The system of claim 7 , wherein the first police thread is further configured to:
re-start, after committing the first portion of the plurality of temporary results, serial execution of the first co-thread at the location.
16. The system of claim 7 , further comprising:
a third co-thread executing on the first computer processor;
a fourth co-thread executing on the second computer processor in parallel with the third co-thread;
a third memory log configured to log, while executing the third co-thread in parallel with the fourth co-thread, a third plurality of memory transactions requested by the third co-thread;
a fourth memory log configured to log, while executing the third co-thread in parallel with the fourth co-thread, a fourth plurality of memory transactions requested by the fourth co-thread;
a second police thread assigned to the third memory log and the fourth memory log and configured, while executing the third co-thread in parallel with the fourth co-thread, to:
perform a second comparison of the third memory log with the fourth memory log to create a second police thread log; and
a master police thread configured to:
perform a third comparison of the first police thread log with a second police thread log, wherein the second police thread log is created based on a parallel execution of a fifth co-thread with a sixth co-thread;
identify, based on the third comparison, a second dependence violation; and
generate a notification of the second dependence violation.