Scheduling of instructions

• US 8,689,202 B1
• Filed: 03/30/2005
• Issued: 04/01/2014
• Est. Priority Date: 03/30/2004
• Status: Active Grant

• Current Assignee: Synopsys Incorporated
• Original Assignee: Synopsys Incorporated
• Inventors: Braun, Gunnar, Hoffmann, Andreas, Leupers, Rainer, Grieve, Volker, Hohenauer, Manuel
• Primary Examiner(s): Vu, Tuan A
• Application Number:
  US11/096,184
• Time in Patent Office: 3,289 Days
• Field of Search: 717/161, 717/141, 717/140, 717/151, 717/159, 717/149, 717/9, 717/160, 718/102, 370/316
• US Class Current: 717/161
• CPC Class Codes: G06F 8/445 Exploiting fine grain parallelism, i.e. parallelism at instruction level run-time instruction scheduling G06F9/3836

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.

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.

2. The method of claim 1, wherein the maintaining of the graph comprises automatically extracting information from an architecture description to construct the directed acyclic graph data structure.

3. The method of claim 2, wherein the information comprises data flow hazards.

4. The method of claim 1, wherein determining a priority associated with a node included in the graph comprises:

accumulating edge weights for paths from the node to leaf nodes; and

assigning the priority to the node based on the path having the maximum accumulated edge weight.

5. The method of claim 1, wherein the dependencies comprise read after write, write after write, and write after read.

6. The method of claim 1, wherein the node scheduled is a father node of nodes that have zero latency.

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.

8. The computer system of claim 7, wherein the maintaining of the graph comprises automatically extracting information from an architecture description to construct the directed acyclic graph data structure.

9. The computer system of claim 8, wherein the information comprises data flow hazards.

10. The computer system of claim 7, wherein determining a priority associated with a node included in the graph comprises:

accumulating edge weights for paths from the node to leaf nodes; and

assigning the priority to the node based on the path having the maximum accumulated edge weight.

11. The computer system of claim 7, wherein the dependencies comprise read after write, write after write, and write after read.

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.

13. The computer readable medium of claim 12, wherein the maintaining of the graph comprises automatically extracting information from an architecture description to construct the directed acyclic graph data structure.

14. The computer readable medium of claim 13, wherein the information comprises data flow hazards.

15. The computer readable medium of claim 12, wherein determining a priority associated with a node included in the graph comprises:

accumulating edge weights for paths from the node to leaf nodes; and

assigning the priority to the given node based on the path having the maximum accumulated edge weight.