Scheduling of instructions
First Claim
Patent Images
1. A computer-implemented method of scheduling instructions, comprising:
- maintaining a memory resident directed acyclic graph comprising nodes representing instructions and the nodes connected via edges whose weights represent dependencies between pairs of instructions;
maintaining a ready list that includes ready nodes currently in the graph that have no predecessor node in the graph and have not been scheduled, a priority associated with each ready node in the ready list, wherein for at least one of the ready nodes the associated priority is determined based on the weights of one or more edges connected to the ready node in the graph;
maintaining a non-scheduled list that includes non-scheduled nodes currently in the graph that have not been scheduled and are not included in the ready list, a priority associated with each non-scheduled node included in the non-scheduled list, wherein for at least one of the non-scheduled nodes the associated priority is determined based on the weights of one or more edges connected to the non-scheduled node in the graph; and
automatically determining whether the next node to be scheduled is to be taken from the ready list or from the non-scheduled list, the determining further comprising;
identifying a non-scheduled node with the highest priority among the non-scheduled nodes included in the non-scheduled list;
scheduling the identified non-scheduled node in response to the priority associated with the identified non-scheduled node being higher than the priority associated with each ready node included in the ready list, andscheduling a ready node with the highest priority among the ready nodes included in the ready list in response to the priority associated with the identified non-scheduled node not being higher than the priority associated with each ready node included in the ready list.
6 Assignments
0 Petitions
Accused Products
Abstract
A method of automatically extracting information from an architecture description. A memory resident directed acyclic graph data structure comprising nodes representing instructions and edges whose weights represent dependencies between pairs of instructions is constructed. A list of ready nodes are maintained in the directed acyclic graph. A list of nodes not scheduled is maintained. And, it is determined whether the next instruction to be scheduled is to be taken from the list of ready nodes or from the list of nodes not yet scheduled.
82 Citations
15 Claims
-
1. A computer-implemented method of scheduling instructions, comprising:
-
maintaining a memory resident directed acyclic graph comprising nodes representing instructions and the nodes connected via edges whose weights represent dependencies between pairs of instructions; maintaining a ready list that includes ready nodes currently in the graph that have no predecessor node in the graph and have not been scheduled, a priority associated with each ready node in the ready list, wherein for at least one of the ready nodes the associated priority is determined based on the weights of one or more edges connected to the ready node in the graph; maintaining a non-scheduled list that includes non-scheduled nodes currently in the graph that have not been scheduled and are not included in the ready list, a priority associated with each non-scheduled node included in the non-scheduled list, wherein for at least one of the non-scheduled nodes the associated priority is determined based on the weights of one or more edges connected to the non-scheduled node in the graph; and automatically determining whether the next node to be scheduled is to be taken from the ready list or from the non-scheduled list, the determining further comprising; identifying a non-scheduled node with the highest priority among the non-scheduled nodes included in the non-scheduled list; scheduling the identified non-scheduled node in response to the priority associated with the identified non-scheduled node being higher than the priority associated with each ready node included in the ready list, and scheduling a ready node with the highest priority among the ready nodes included in the ready list in response to the priority associated with the identified non-scheduled node not being higher than the priority associated with each ready node included in the ready list. - View Dependent Claims (2, 3, 4, 5, 6)
-
-
7. A computer system comprising a processor and a non-transitory computer readable medium coupled to the processor via a bus, wherein the non-transitory computer readable medium comprises instructions that when executed by the process processor implement a method of scheduling instructions, comprising:
-
maintaining a memory resident directed acyclic graph comprising nodes representing instructions and the nodes connected via edges whose weights represent dependencies between pairs of instructions; maintaining a ready list that includes ready nodes currently in the graph that have no predecessor node in the graph and have not been scheduled, a priority associated with each ready node in the ready list, wherein for at least one of the ready nodes the associated priority is determined based on the weights of one or more edges connected to the ready node in the graph; maintaining a non-scheduled list that includes non-scheduled nodes currently in the graph that have not been scheduled and are not included in the ready list, a priority associated with each non-scheduled node included in the non-scheduled list, wherein for at least one of the non-scheduled nodes the associated priority is determined based on the weights of one or more edges connected to the non-scheduled node in the graph; and automatically determining whether the next node to be scheduled is to be taken from the ready list or from the non-scheduled list, the determining further comprising; identifying a non-scheduled node with the highest priority among the non-scheduled nodes included in the non-scheduled list, scheduling the identified non-scheduled node in response to the priority associated with the identified non-scheduled node being higher than the priority associated with each ready node included in the ready list, and scheduling a ready node with the highest priority among the ready nodes included in the ready list in response to the priority associated with the identified non-scheduled node not being higher than the priority associated with each ready node included in the ready list. - View Dependent Claims (8, 9, 10, 11)
-
-
12. A non-transitory computer readable medium having stored thereon instructions that when executed on a computer processor implement a method of scheduling instructions, comprising:
-
maintaining a memory resident directed acyclic graph comprising nodes representing instructions and the nodes connected via edges whose weights represent dependencies between pairs of instructions; maintaining a ready list that includes ready nodes currently in the graph that have no predecessor node in the graph and have not been scheduled, a priority associated with each ready node in the ready list, wherein for at least one of the ready nodes the associated priority is determined based on the weights of one or more edges connected to the ready node in the graph; maintaining a non-scheduled list that includes non-scheduled nodes currently in the graph that have not been scheduled and are not included in the ready list, a priority associated with each non-scheduled node included in the non-scheduled list, wherein for at least one of the non-scheduled nodes, the associated priority is determined based on the weights of one or more edges connected to the non-scheduled node in the graph; and automatically determining whether the next node to be scheduled is to be taken from the ready list or from the non-scheduled list, the determining further comprising; identifying a non-scheduled node with the highest priority among the non-scheduled nodes included in the non-scheduled list, scheduling the identified non-scheduled node in response to the priority associated with the identified non-scheduled node being higher than the priority associated with each ready node included in the ready list, and scheduling a ready node with the highest priority among the ready nodes included in the ready list in response to the priority associated with the identified non-scheduled node not being higher than the priority associated with each ready node included in the ready list. - View Dependent Claims (13, 14, 15)
-
Specification