Patent ID: 7379858

Claim:
A method for speculative computing, comprising: modeling a software system in the form of a control flow graph, the control flow graph comprising nodes and directed edges, each node corresponding to a component of the software system, and each edge corresponding to a single-step transition of the software system from one component to another component; assigning a transition probability to each edge of the control flow graph; modeling the control flow graph as a Markov chain having a transition matrix T comprising the transition probabilities; computing reaching probabilities of reaching each node of the control flow graph from any other node of the control flow graph using the Markov chain comprising: defining a reaching probabilities matrix R; if the control flow graph contains any strongly connected components: defining an augmented matrix T′ based on T and containing an additional row and column; re-computing at least one of a row and a column of R, corresponding to a node in the strongly connected components using T′; repeating the re-computation of at least one of a row and a column of R for each node in the strongly connected components; and updating the reaching probabilities matrix, R using the re-computed columns or rows of R; and performing at least one of speculative parallel thread compilation for the software system or speculative parallel thread execution for the software system based on the computed or re-computed reaching probabilities.