Scheduler of program instructions for streaming vector processor having interconnected functional units

• US 7,140,019 B2
• Filed: 06/28/2002
• Issued: 11/21/2006
• Est. Priority Date: 06/28/2002
• Status: Expired due to Fees

• Current Assignee: Motorola, Inc. (Motorola Solutions, Inc.)
• Original Assignee: Motorola, Inc. (Motorola Solutions, Inc.)
• Inventors: Essick, Raymond B. IV, Saidi, Ali, Chiricescu, Silviu, May, Philip E., Norris, James M., Lucas, Brian Geoffrey, Schuette, Michael Allen, Moat, Kent Donald
• Primary Examiner(s): BULLOCK JR, LEWIS ALEXANDER
• Application Number:
  US10/184,772
• Publication Number:
  US 20040003220A1
• Time in Patent Office: 1,607 Days
• Field of Search: 718100-108, 715/736
• US Class Current: 718/102
• 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 for scheduling a computation for execution on a computer with a number of interconnected functional units. The computation is representable by a data-flow graph with a number of nodes connected by edge. A loop-period of the computation is calculated and the nodes are scheduled for throughput by assigning an execution cycle and a functional unit to each node of the data-flow graph. The scheduling of flexible nodes is adjusted to minimize the number of interconnections required in each execution cycle. The edges of the data-flow graph are allocated to one or more of the interconnections between functional units. The scheduling method may be used, for example, to optimize the interconnection fabric design for an ASIC or as part of a compiler for a re-configurable streaming vector processor.

Claims

1. A method for scheduling a computation for execution on a computer comprising a plurality of functional units interconnected by a plurality of interconnections, the computation being representable by a data-flow graph having a plurality of nodes and a plurality of edges and the method comprising:

(a) computing a loop-period of the computation;

(b) attempting to schedule the plurality of nodes within the loop period for throughput by assigning an execution cycle and a functional unit to each node of the plurality of nodes;

(c) adjusting the scheduling of flexible nodes of the plurality of nodes to reduce the number of interconnections required in any execution cycle if the number of interconnections required exceeds the number of interconnections in the plurality of interconnections; and

(d) allocating the plurality of edges to one or more of the plurality of interconnections.

2. A method in accordance with claim 1, wherein one or more of the functional units is partitioned into two or more slices, the method further comprising:

mapping nodes of the data-flow graph onto slices of the one of more of the partitioned functional units so as to reduce the number of interconnections required in an execution cycle.

3. A method in accordance with claim 2, and wherein the mapping nodes of the data-flow graph onto slices of the one of more of the partitioned functional units so as to reduce the number of interconnections required in an execution cycle comprises:

computing a set of execution cycles number for which the number of interconnections required is greater than the number of interconnections in the plurality of interconnections;

computing tail-times for each node that is the source of an edge that intersects the set of execution cycles; and

mapping nodes onto slices of the one of more of the partitioned functional units so as to reduce the number of interconnections required in a cycle.

4. A method in accordance with claim 2, further comprising:

computing the set of execution cycles for which the number of interconnections required is greater than the number of interconnections in the plurality of interconnections;

computing lead-times for each node that is the destination of an edge that intersects the set of execution cycles allocated to a cycle of the first set of execution cycles; and

mapping nodes onto the slices of the one of more of the partitioned functional units so as to reduce the number of interconnections required in a cycle.

5. A method in accordance with claim 2, wherein slugs are used to discard results from unused slices of the one of more of the partitioned functional units.

6. A method in accordance with claim 1, wherein the edges of the plurality of edges are allocated so that values are stored at one or more of:

an input of a functional unit;

an output of a functional unit;

a storage entry in the interconnection fabric; and

a trampoline node.

7. A method in accordance with claim 1, wherein the plurality of interconnections comprises a re-configurable interconnect fabric having a plurality of links and wherein the edges of the plurality of edges are allocated so that values live at one or more of:

an output of a functional unit;

a storage entry in the interconnection fabric;

a trampoline node; and

an input of a functional unit.

8. A method in accordance with claim 1, wherein the scheduling the plurality of nodes for throughput by assigning an execution cycle and a functional unit to each node of the plurality of nodes comprises:

(b1) attempting to schedule the plurality of node within the loop-period; and

(b2) while the attempt to schedule the plurality of node within the loop-period is unsuccessful, increasing the loop-period and repeating from (b1).

9. A method in accordance with claim 1, wherein the allocating the plurality of edges to one or more of the plurality of interconnections comprises

(d1) attempting to allocate the plurality of edges to one or more of the plurality of interconnections;

and

(d2) if the attempt to allocate the plurality of edges is unsuccessful, increasing the loop-period and repeating from (d1).

10. A method in accordance with claim 1, wherein the plurality of interconnections comprises a re-configurable interconnect fabric having a plurality of links and wherein the allocation of an edge of the plurality of edges is ordered as:

the input or output of the functional unit to which the node is assigned;

a storage entry in the interconnection fabric; and

the input or output of a free functional unit.

11. A method in accordance with claim 1, further comprising splitting the data-flow graph into a number of partitions, corresponding to the number of iterations that are executed in parallel when a steady state operation of the computer has been achieved.

12. A method in accordance with claim 1, further comprising overlapping the schedules for two or more adjacent iterations to obtain a higher throughput.

13. A method in accordance with claim 1, wherein consecutive iterations are scheduled to use different functional unit instances.

14. A method in accordance with claim 1, wherein two schedules are computed, one for maximum throughput and one for minimum latency, and wherein a schedule of the two schedules is selected in accordance with the number of iterations to be performed.

15. A method in accordance with claim 1, wherein the resulting schedule is represented as one of a set of very long instruction words and microcode instructions.

16. A method for minimizing the number of interconnections required by a computer to execute a computation, the computer comprising a plurality of functional units interconnected by a plurality of interconnections, the computation being representable by a data-flow graph having a plurality of nodes and a plurality of edges and the method comprising:

(a) computing a loop-period of the computation;

(b) attempting to schedule the plurality of nodes within the loop period by assigning an execution cycle and a functional unit to each node of the plurality of nodes;

(c) adjusting the scheduling the plurality of nodes to minimize the number of interconnections required in any execution cycle;

(d) adjusting the scheduling of the plurality of nodes to increase throughput if the throughput is below a predetermined minimum throughput;

(e) adjusting the scheduling of the plurality of nodes to decrease latency if the latency exceeds a predetermined maximum latency; and

(f) allocating the plurality of edges to one or more of the plurality of interconnections.

17. A computer readable medium containing instructions which, when executed on a first computer, carry out a process of scheduling a computation for execution on a second computer, the second computer having a plurality of functional units interconnected by a plurality of interconnections, and the computation being representable by a data-flow graph having a plurality of nodes and a plurality of edges, the process of scheduling comprising:

(a) computing a loop-period of the computation;

(b) attempting to schedule the plurality of nodes within the loop period for throughput by assigning an execution cycle and a functional unit to each node of the plurality of nodes;

(c) adjusting the scheduling of flexible nodes of the plurality of nodes to reduce the number of interconnections required in each execution cycle if the number of interconnections required is greater than the number of interconnection in the plurality of interconnections; and

(d) allocating the plurality of edges to one or more of the plurality of interconnections.

18. A computer readable medium in accordance with claim 17, wherein one or more of the functional units is partitioned into two or more slices, the process further comprising:

assigning slices of the one of more of the partitioned functional units so as to reduce the number of interconnections required in an execution cycle.

19. A computer readable medium in accordance with claim 18, wherein the assigning slices of the one of more of the partitioned functional units so as to reduce the number of interconnections required in an execution cycle comprises:

computing a set of execution cycles number for which the number of interconnections required is greater than the number of interconnections in the plurality of interconnections;

computing tail-times for each node allocated to a cycle of the set of execution cycles; and

mapping nodes to slices of the one of more of the partitioned functional units so as to reduce the number of interconnections required in a cycle.

20. A computer readable medium in accordance with claim 18, further comprising:

computing the set of execution cycles for which the number of interconnections required is greater than the number of interconnections in the plurality of interconnections;

computing lead-times for each node that is the destination of an edge that intersects the set of execution cycles allocated to a cycle of the first set of execution cycles; and

mapping nodes to the slices of the one of more of the partitioned functional units so as to reduce the number of interconnections required in a cycle.

21. A computer readable medium in accordance with claim 17, wherein the allocating the plurality of edges to one or more of the plurality of interconnections comprises

(d1) attempting to allocate the plurality of edges to one or more of the plurality of interconnections;

and

(d2) if the attempt to allocate the plurality of edges is unsuccessful, increasing the loop-period and repeating from (d1).

22. A computer readable medium in accordance with claim 17 where the first and second computers are the same computer.

23. An application specific integrated circuit for performing a computation representable by a data-flow graph having a plurality of nodes and a plurality of edges, the application specific integrated circuit having a plurality of functional units interconnected by a plurality of interconnections, wherein the number of interconnections in the plurality of interconnections is determined by:

(a) computing a loop-period of the computation;

(b) attempting to schedule the plurality of nodes within the loop period for throughput by assigning an execution cycle and a functional unit to each node of the plurality of nodes;

(c) adjusting the scheduling of flexible nodes of the plurality of nodes to minimizing the number of interconnections required in each execution cycle; and

(d) allocating the plurality of edges to one or more of the plurality of interconnections.

24. An application specific integrated circuit in accordance with claim 23, wherein the allocating the plurality of edges to one or more of the plurality of interconnections comprises

(d1) attempting to allocate the plurality of edges to one or more of the plurality of interconnections;

and

(d2) if the attempt to allocate the plurality of edges is unsuccessful, increasing the loop-period and repeating from (d1).