Multiprocessor scheduling and execution

• US 5,742,821 A
• Filed: 11/08/1995
• Issued: 04/21/1998
• Est. Priority Date: 11/08/1995
• Status: Expired due to Term

• Current Assignee: Avago Technologies General IP PTE Limited (Broadcom, Inc.)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Prasanna, G.N. Srinivasa
• Primary Examiner(s): TOPLU, LUCIEN
• Application Number:
  US08/555,051
• Time in Patent Office: 895 Days
• Field of Search: 395/672, 395/674, 395/675
• US Class Current: 718/102
• CPC Class Codes: G06F 8/451 Code distribution considering CPU load at run-time G06F9/505; load rebalancing G06F9/5083

Abstract

In accordance with the principles of the invention, a multiprocessor scheduling and execution system and method is disclosed for signal processing tasks on P processors using a computer to schedule the execution. The method comprises representing the signal processing tasks in a manner stored within the computer so as to determine flow equations and timing constraints for the processor scheduling, performing corrected gradient descents on the stored representation of the signal processing tasks using the determined timing constraints and an error criterion until substantial convergence to a processor schedule occurs, and executing the signal processing tasks on the P processors substantially in accordance with the processor schedule.

Claims

1. A method of executing signal processing tasks on P processors using a computer to schedule the execution, said method comprising the steps of:

representing the signal processing tasks in a manner stored within said computer so as to determine flow equations and timing constraints for the processor scheduling;

performing corrected gradient descents on the stored representation of the signal processing tasks using said flow equations and determined timing constraints and an error criterion until substantial convergence to a processor schedule occurs; and

executing the signal processing tasks on said P processors substantially in accordance with said processor schedule.

2. The method of claim 1, wherein the step of representing the signal processing tasks in a manner stored within said computer comprise removing transitive edges from each of a plurality of edges between a respective first task node and a second task node of a plurality of task nodes of the stored representation of the signal processing tasks.

3. The method of claim 2, wherein the step of representing the signal processing tasks in a manner storm within said computer comprise summing each of said plurality of flows between said plurality of task nodes to determine flow conservation and summing branches in each fundamental loop of a tree formed from said plurality of nodes to determine said flow equations and timing constraints.

4. The method of claim 3, wherein the step of performing corrected gradient descents includes determining an orthonormal basis.

5. The method of claim 3, wherein said tree formed from said plurality of nodes comprises a breadth first spanning tree.

6. The method of claim 1, wherein the step of representing the signal processing tasks in a manner stored within said computer includes augmenting non-essential edges of said signal processing tasks to convert said non-essential edges to essential edges.

7. The method of claim 6, wherein the step of augmenting non-essential edges comprises adding a dummy node to a non-essential edge.

8. The method of claim 1, wherein the step of determining timing constraints includes performing calculations based, at least in part, upon a set of loop equations being based on (E-N+1) loops, where E is the number of edges in said graph, and N is the number of task nodes.

9. The method of claim 1, wherein said signal processing tasks include matrix operations.

10. The method of claim 9, wherein said matrix operations include matrix additions and matrix multiplications.

11. The method of claim 1, wherein said P processors, comprise processors selected from the group consisting essentially of general purpose computers and special purpose signal processors.

12. A system for executing signal processing tasks on P signal processors comprising:

the P signal processors;

a processing scheduler; and

a memory system to store a representation of said signal processing tasks in a manner to determine flow equations and timing constraints for said processing scheduler;

said processing scheduler being adapted to schedule the execution of the signal processing tasks on said P signal processors and to perform correcting gradient descents on the stored representations of the signal processing tasks using said determined flow equations and timing constraints until substantial convergence to a processor schedule occurs.

13. The system of claim 12, wherein said processing scheduler is further adapted to augment non-essential edges of said signal processing tasks to essential edges and to remove transitive edges from a flow between a respective first task node and second task node of a plurality of task nodes of the stored representations of the signal processing tasks.

14. The system of claim 13, wherein said processing scheduler is further adapted to augment by adding a dummy node to a non-essential edge.

15. The system of claim 12, wherein said memory system further determines said flow equations and timing constraints by calculating a set of loop equations by summing each branch of a fundamental loop of a tree formed from said plurality of nodes.

16. The system of claim 12, wherein the P signal processors comprise digital signal processors (DSPs).

17. The system of claim 12, wherein the P signal processors comprise microprocessors.