Methods and means for scheduling parallel processors

• US 5,768,594 A
• Filed: 07/14/1995
• Issued: 06/16/1998
• Est. Priority Date: 07/14/1995
• Status: Expired due to Fees

• Current Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Matias, Yossi, Gibbons, Phillip B., Blelloch, Guy E.
• Primary Examiner(s): Coleman, Eric
• Application Number:
  US08/502,625
• Time in Patent Office: 1,068 Days
• Field of Search: 395/800, 395/706, 395/705, 395/670, 395/672
• US Class Current: 717/149
• CPC Class Codes: G06F 2209/5021 Priority
• CPC Class Codes: G06F 9/5066 Algorithms for mapping a plurality of inter-dependent sub-tasks onto a plurality of physical CPUs mappping at compile time, see G06F8/451

Abstract

Parallel processing is performed by determining sequential ordering of tasks for processing, assigning priorities to the tasks available on the basis of the sequential ordering, selecting a number of tasks greater than a total number of available parallel processing elements from all available tasks having the highest priorities, partitioning the selected tasks into a number of groups equal to the available number of parallel processing elements, and executing the tasks in the parallel processing elements.

Claims

1. A method of parallel processing, comprising:

determining a sequential ordering of tasks for processing,

assigning priorities to available tasks on the basis of the earliest and then later in the sequential ordering;

selecting a number of tasks greater than a total number of available parallel processing elements from all available tasks having the highest priorities;

partitioning the selected tasks into a number of groups equal to the available number of parallel processing elements; and

executing the tasks in the groups in the parallel processing elements;

said determining step establishing an ordering with a specific predetermined sequential schedule that is independent of the parallel execution, and said assigning step assigns priorities for parallel execution on the basis of the sequential schedule that is independent of the parallel execution.

2. A method as in claim 1, wherein the number of selected tasks differs from the number of available tasks and differs from the available number of parallel processing elements.

3. A method as in claim 1, wherein the number of selected tasks is more than the available number of processors and less that the maximum number of tasks possible.

4. A method as in claim 1, wherein the number of selected tasks is N and the number of available parallel processing elements is p, and the step of partitioning partitions the N selected tasks into p groups of substantially N/p size.

5. A method as in claim 1, wherein the step of partitioning includes a step of delegating each group to one of the parallel processing elements.

6. A method as in claim 1, wherein the step of assigning includes assigning in a number of parallel steps.

7. A method as in claim 1, wherein spawned steps are placed in the ordering of parent tasks that spawned them.

8. A method as in claim 1, wherein said step of partitioning is performed in a number of parallel steps.

9. A method as in claim 1, wherein said sequential ordering is a Depth-first Traversal (DFT) schedule.

10. A method as in claim 1, wherein the step of processing spawns a number of tasks and the step of assigning priorities includes assigning priorities to tasks spawned.

11. A method as in claim 10, wherein the number of selected tasks is N and the number of available parallel processing elements is p, and the step of partitioning partitions the N selected tasks into p groups of substantially N/p size.

12. A method as in claim 1, wherein the step of selecting includes placing a limit L on the number N of selected tasks from among a number M of available tasks, and if the available tasks M are equal or greater than the number L then N=L, and if M<

L, N=M.

13. A method as in claim 1, wherein the step of partitioning includes weighting the tasks and the step of partitioning includes dividing the tasks into the groups on the basis of the weighting.

14. A method as in claim 1, wherein the step of determining applies to each task of a program a designation that identifies the ordering of the task in the sequence.

15. A method as in claim 1, wherein the step of assigning priorities is on the basis of high to low priorities for first to last in the sequential ordering such that tasks are entered in the parallel processing elements on the basis of high to low priorities for the first to last in the sequential ordering.

16. An apparatus for parallel processing, comprising:

a task sequential-ordering preprocessor for sequential ordering of tasks for processing;

a task priority-assigning assignment manager responsive to the sequential ordering;

a plurality of available parallel processing elements;

means for selecting a number of tasks greater than a total number of available parallel processing elements from all available tasks having the highest priorities;

means for partitioning the selected tasks into a number of groups equal to the available number of parallel processing elements; and

means for entering the tasks in the groups in the parallel processing elements;

said preprocessor including a sequential schedule that establishes a predetermined ordering that is independent of the parallel execution so that priorities for parallel execution occur on the basis of sequential scheduling that is independent of the parallel execution.

17. An apparatus as in claim 16, wherein the number of selected tasks differs from the number of available tasks and differs from the available number of parallel processing elements.

18. An apparatus as in claim 16, wherein the number of selected tasks i s more than the available number of processors and less that the maximum number of tasks possible.

19. An apparatus as in claim 16, wherein the number of selected tasks is N and the number of available parallel processing elements is p, and the means for partitioning partitions the N selected tasks into p groups of substantially N/p size.

20. An apparatus as in claim 16, wherein the means for partitioning includes a means for delegating each group to one of the parallel processing elements.

21. An apparatus as in claim 16, wherein the assignment manager assigns in a number of parallel steps.

22. An apparatus as in claim 16, wherein said assignment manager places spawned steps in the ordering of parent tasks that spawned them.

23. An apparatus as in claim 16, wherein said means for partitioning is performed in a number of parallel steps.

24. An apparatus as in claim 16, wherein said sequential ordering processor is a Depth-first Traversal (DFT) preprocessor.

25. An apparatus as in claim 16, wherein the preprocessor spawns a number of tasks and the assignment manager includes assigning priorities to tasks spawned.

26. An apparatus as in claim 25, wherein the number of selected tasks is N and the number of available parallel processing elements is p, and the means for partitioning partitions the N selected tasks into p groups of substantially N/p size.

27. An apparatus as in claim 16, wherein the means for selecting includes placing a limit L on the number N of selected tasks from among a number M of available tasks, and if the available tasks M are equal or greater than the number L then N=L, and if M<

L, N=M.

28. A method as in claim 16, wherein the means for partitioning includes means for weighting the tasks and the means for partitioning includes means for dividing the tasks into the groups on the basis of the weighting.

29. A system as in claim 16, wherein the preprocessor applies to each task of a program a designation that identifies the ordering of the task in the sequence.

30. A system as in claim 16, wherein the assignment manager assigns priorities on the basis of high to low priorities for first to last in the sequential ordering such that said means for entering enters tasks in the parallel processing elements on the basis of high to low priorities for first to last in the sequential ordering.