Method and system for scheduling in an adaptable computing engine

• US 20020184291A1
• Filed: 05/31/2001
• Published: 12/05/2002
• Est. Priority Date: 05/31/2001
• Status: Abandoned Application

• Current Assignee: Cornami, Inc.
• Original Assignee: Cornami, Inc.
• Inventors: Hogenauer, Eugene B.
• Application Number:
  US09/872,397
• Publication Number:
  US 20020184291A1
• Time in Patent Office: Days
• US Class Current: 718/102
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues

Abstract

Aspects of a scheduler for an adaptable computing engine are described. The aspects include providing a plurality of computation units as hardware resources available to perform a particular segment of an assembled program on an adaptable computing engine. A schedule for the particular segment is refined by allocating the plurality of computation units in correspondence with a dataflow graph that represents the particular segment in an interactive manner until a feasible schedule is achieved.

Claims

1. A method for scheduling an assembled program in an adaptable computing engine, the method comprising:

providing a plurality of computation units as hardware resources available to perform a particular segment of the assembled program;

representing the particular segment as a dataflow graph; and

refining a schedule that allocates the plurality of computation units in correspondence with the dataflow graph in an iterative manner until a feasible schedule is achieved.

2. The method of claim 1 wherein the step of refining further comprises associating a value representing cost of the schedule, and determining if the value meets conditions of acceptability.

3. The method of claim 2 wherein the conditions of acceptability further comprise a cost of zero.

4. The method of claim 2 wherein when the value does not meet conditions of acceptability, the method further comprises altering the schedule through a small incremental change in a random manner to provide an altered schedule.

5. The method of claim 4 wherein the altering in a random manner further comprises selecting a node of the dataflow graph at random and selecting an available change for the selected node at random.

6. The method of claim 4—

further comprising computing the value for the altered schedule.

7. The method of claim 6 wherein when the altered schedule has a computed value that is higher than the value of the schedule, the altered schedule is not used.

8. The method of claim 6 wherein when the altered scheduled has a computed value that is lower than the value of the schedule, the method further comprises designating the altered schedule as the schedule, and repeating the step of determining if the value meets conditions of acceptability.

9. The method of claim 8 wherein when the value does meet conditions of acceptability, the method further comprises designating the schedule as the feasible schedule.

10. The method of claim 9—

further comprising representing the particular segment as a scheduled dataflow graph once the feasible schedule has been achieved.

11. The method of claim 1 wherein providing a plurality of computation units further comprises providing the plurality of computation units as a matrix in the adaptable computing machine.

13. The system of claim 12 wherein the plurality of computation units further comprise a matrix of the adaptable computing engine.

14. The system of claim 12 wherein the means for scheduling and allocating further associates a value representing cost of the schedule, and determines if the value meets conditions of acceptability.

15. The system of claim 14 wherein the conditions of acceptability further comprise a cost of zero.

16. The system of claim 14 wherein when the value does not meet conditions of acceptability, the means for scheduling and allocating further alters the schedule through a small incremental change in a random manner to provide an altered schedule.

17. The system of claim 16 wherein the means for scheduling and altering further alters in a random manner by selecting a node of the dataflow graph at random and selecting an available change for the selected node at random.

18. The system of claim 16 wherein the means for scheduling and altering further computes the value for the altered schedule.

19. The system of claim 18 wherein when the altered schedule has a computed value that is higher than the value of the schedule, the altered schedule is not used.

20. The system of claim 18 wherein when the altered scheduled has a computed value that is lower than the value of the schedule, the means for scheduling and altering further designates the altered schedule as the schedule and repeats the determination of whether the value meets conditions of acceptability.

21. The system of claim 20 wherein when the value does meet conditions of acceptability, the means for scheduling and altering further designates the schedule as the feasible schedule.

22. The system of claim 21 wherein the means for scheduling and altering further represents the particular segment as a scheduled dataflow graph once the feasible schedule has been achieved.

24. The method of claim 23 wherein the acceptable cost level further comprises a cost of zero.

25. The method of claim 23 further comprising representing the code segment as a dataflow graph of nodes and edges.

26. The method of claim 25 wherein the step of adjusting further comprises selecting a node of the dataflow graph at random and selecting an available change for the node at random to adjust the chosen schedule.

12. A system for scheduling an assembled program in an adaptable computing engine, the system comprising:

a plurality of computation units for providing hardware resources available to perform a particular segment of the assembled program;

a host controller for configuring the plurality of computation units; and

means for scheduling and allocating the plurality of computation units to perform the particular segment by refining a schedule that allocates the plurality of computation units in correspondence with a dataflow graph representative of the particular segment in an iterative manner until a feasible schedule is achieved

23. A method for determining an optimal schedule for a matrix of computation units in an adaptable computing engine, the method comprising:

determining a value representative of a cost for a chosen schedule of utilizing the matrix to perform a code segment;

adjusting the chosen schedule randomly through small incremental steps until the value reaches an acceptable cost level; and

designating a feasible schedule once the acceptable cost level is reached.