US 8,151,255 B2Granted

Using police threads to detect dependence violations to reduce speculative parallelization overhead

AssigneeOracle America, Inc.

InventorsPhyllis E. Gustafson, Miguel Angel Lujan Moreno, Michael H. Paleczny, Christopher A. Vick, Olaf Manczak, Jay R. Freeman

Life of this patent

Estimating the term…

patentgrep

Loading patent…

Abstract

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.

Claims16

Dependent claims

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.

16 more elements

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.

17 more elements

Dependencies are inferred from the claim text.