List scheduling algorithm for a cycle-driven instruction scheduler

• US 20020083423A1
• Filed: 10/04/2001
• Published: 06/27/2002
• Est. Priority Date: 02/17/1999
• Status: Abandoned Application

• Current Assignee: Elbrus International Limited
• Original Assignee: Elbrus International Limited
• Inventors: Ostanevich, Alexander Y., Volkonsky, Vladimir Y.
• Application Number:
  US09/971,858
• Publication Number:
  US 20020083423A1
• Time in Patent Office: Days
• US Class Current: 717/149
• CPC Class Codes: G06F 8/452 Loops
• CPC Class Codes: G06F 9/3824 Operand accessing
• CPC Class Codes: G06F 9/3826 Bypassing or forwarding of data results, e.g. locally between pipeline stages or within a pipeline stage
• CPC Class Codes: G06F 9/3828 with global bypass, e.g. between pipelines, between clusters
• CPC Class Codes: G06F 9/3834 Maintaining memory consistency
• CPC Class Codes: G06F 9/3836 Instruction issuing, e.g. dynamic instruction scheduling or out of order instruction execution
• CPC Class Codes: G06F 9/3885 using a plurality of independent parallel functional units
• CPC Class Codes: G06F 9/3891 organised in groups of units sharing resources, e.g. clusters

Abstract

A method for scheduling a plurality of operations of one or more types of operations including a plurality of computing resources is provided. The method includes building a list of partial lists for the one or more types of operations where the partial lists include one or more operations. A current partial list of a type of operation is determined. A computing resource for an operation in the current partial list is then allocated. The method then determines if additional computing resources for the type of operation are available for the current partial list. If so, the method reiterates back to determining a current partial list. If additional computing resources are not available, the method performs the steps of excluding the current partial list from the list and if the list includes any other partial lists, reiterating back to determining a current partial list.

Claims

1. A method for scheduling a plurality of operations of one or more types of operations using a parallel processing architecture including a plurality of computing resources, the method comprising:

(a) building a list of partial lists for the one or more types of operations, the partial lists including one or more operations from the plurality of operations;

(b) determining a current partial list of a type of operation to allocate from the list of partial lists;

(c) allocating a computing resource for an operation in the current partial list;

(d) determining if additional computing resources for the type of operation are available for the current partial list;

(e) if additional computing resources are available, reiterating to step (b);

(f) if additional computing resources are not available, performing the steps of;

(1) excluding the current partial list from the list;

(2) if the list includes any other partial lists, reiterating to step (b).

2. The method of claim 1, further comprising incrementing a clock cycle to a next cycle.

3. The method of claim 2, further comprising updating the list of partial lists and reiterating to step (b).

4. The method of claim 3, wherein updating the list of partial lists comprises excluding operations allocated from the partial list.

5. The method of claim 1, further comprising assigning a priority to the partial lists.

6. The method of claim 5, wherein assigning the priority comprises assigning the priority based on a priority of an operation in each partial list.

7. The method of claim 5, wherein determining the current partial list of the type of operation to allocate from the list comprises determining the current partial list of a highest priority.

8. The method of claim 1, further comprising excluding the allocated operation from the partial list.

9. The method of claim 1, further comprising assigning a new priority to the plurality of partial lists based on an operation not already allocated in the partial list.

10. A method for scheduling a plurality of operations using a parallel processing architecture including a plurality of computing resources, the method comprising:

(a) building a list of partial lists, the partial lists including one or more operations in the plurality of operations;

(b) assigning priorities to the partial lists;

(c) determining a current partial list with a highest priority;

(d) allocating an available computing resource for an operation in the current partial list;

(e) assigning a new priority to the current partial list;

(f) determining if additional computing resources are available for the current partial list;

(g) if additional computing resources are available, performing the steps of;

(1) determining if the current partial list includes additional operations;

(2) if the current partial list includes additional operations, reiterating to step (d);

(3) if the current partial list does not include additional operations, excluding the current partial list from the list and reiterating to step (c);

(h) if additional computing resources are not available, performing the steps of;

(1) excluding the current partial list from the list;

(2) if the list includes any other partial lists, reiterating to step (c).

11. The method of claim 10, wherein assigning a priority to the partial lists comprises assigning a priority based on an operation in each of the partial lists.

12. The method of claim 10, wherein assigning a new priority to the current partial list comprises assigning a new priority based on an operation not already allocated in the current partial list.

13. The method of claim 10, further comprising excluding the allocated operation from the current partial list.

14. The method of claim 10, further comprising incrementing a clock cycle to a next cycle.

15. The method of claim 14, further comprising updating the plurality of partial lists and the list to reflect the allocated operations.

16. The method of claim 14, further comprising resetting the list.