Patent ID: 7624386
Filing Date: 2009-11-24
Classification: G06F

Abstract:
1. A method for scheduling computer instructions using a computer processor and memory coupled to a machine accessible medium, comprising: constructing a tree having a plurality of nodes, wherein each of the plurality of nodes represents one or more memory locations, each node including attributes for children of the node, a parent of the node, a last cut vertex for the node, and fan vertices for the node; receiving a request to create a vertex of a dependence graph, the vertex corresponding to a node within the plurality of nodes, wherein the vertex represents one of a machine instruction and a pseudo instruction; adjusting a frontier of nodes in the tree to envelope the node, the frontier of nodes including a group of nodes that are associated with a cut vertex or a fan vertex, wherein the frontier is to track nodes in the tree that are relevant to at least one future request to create a vertex of the dependence graph, adjusting the frontier including inspection of the parent and child attributes of the node to determine a location of the node in relation to the frontier; creating the vertex and at least one predecessor edge in the dependence graph, the predecessor edge to indicate dependence of vertices of the dependence graph, creation of the vertex being based at least in part on the last cut vertex attribute or the fan vertices attribute of the node; and scheduling computer instructions based on the dependence graph.