Fast tree-based generation of a dependence graph

A method 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;
• scheduling computer instructions based on relative positions of the plurality of nodes within the tree and based on a series of requests, each of the series of requests being related to one of the plurality of nodes in the tree, wherein the instructions include at least one of machine instructions or pseudo instructions, wherein the scheduling of instructions includes:
• receiving a request to create a vertex of a dependence graph corresponding to a node within the plurality of nodes,
• maintaining a frontier of nodes in the tree, the frontier of nodes including a group of nodes that are associated with a cut vertex or a fan vertex, wherein the frontier tracks nodes in the tree that are relevant to future requests,
• adjusting the frontier to envelope the node including inspection of the parent and child attributes of the node to determine a location of the node in relation to the frontier, and
• 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
• executing the scheduled computer instructions.

A system comprising:

• a processor;
• memory coupled to the processor to store data, the data comprising computer instructions to be scheduled, wherein the computer instructions to be scheduled include at least one of machine instructions or pseudo instructions;
• and
• an instruction scheduler to schedule the computer instructions based on relative positions of a plurality of nodes within a hierarchical tree and based on a series of requests, 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, wherein the instruction scheduler is to:
• receive a request to create a vertex of a dependence graph corresponding to a node within the plurality of nodes,
• maintain a frontier of nodes in the hierarchical tree, the frontier of nodes including a group of nodes that are associated with a cut vertex or a fan vertex, wherein the frontier tracks nodes in the hierarchical tree that are relevant to future requests to create vertices of the dependence graph,
• adjust the frontier of the hierarchical tree to envelope the node including inspection of the parent and child attributes of the node to determine a location of the node in relation to the frontier, and
• create the vertex and at least one predecessor edge in the dependence graph, the predecessor edge to indicate dependence of vertices of 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.

An article of manufacture comprising a machine-accessible medium having stored thereon instructions which, when executed by a machine, cause the machine to:

• construct 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;
• receive 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;
• adjust 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;
• create 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;
• schedule computer instructions based on the dependence graph;
• and
• execute the scheduled instructions.