Scheduling-based hardware-software co-synthesis of heterogeneous distributed embedded systems

• US 6,112,023 A
• Filed: 02/17/1998
• Issued: 08/29/2000
• Est. Priority Date: 02/24/1997
• Status: Expired due to Fees

• Current Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Lakshminarayana, Ganesh, Jha, Niraj K., Dave, Bharat P.
• Primary Examiner(s): Teska, Kevin J.
• Assistant Examiner(s): PHAN, THAI Q
• Application Number:
  US09/024,604
• Time in Patent Office: 924 Days
• Field of Search: 395/500.44, 395/500.48, 395/650, 395/670, 395/674, 395/676, 395/500.03, 395/406, 395/500.17, 395/500.49, 395/800.16, 395/651, 395/653, 395/675 , 395/677, 709/203, 709/226
• US Class Current: 703/27
• CPC Class Codes: G06F 2119/06 Power analysis or power optimisation
• CPC Class Codes: G06F 30/30 Circuit design
• CPC Class Codes: G06F 9/4887 involving deadlines, e.g. rate based, periodic
• CPC Class Codes: Y02D 10/00 Energy efficient computing, e.g. low power processors, power management or thermal management

Abstract

Hardware-software co-synthesis is the process of partitioning an embedded system specification into hardware and software modules to meet performance, power, and cost goals. Embedded systems are generally specified in terms of a set of acyclic task graphs. According to one embodiment of the present invention, a co-synthesis algorithm, called COSYN, starts with periodic task graphs with real-time constraints and produces a low-cost heterogeneous distributed embedded system architecture meeting these constraints. The algorithm has the following features: 1) it allows the use of multiple types of processing elements (PEs) and inter-PE communication links, where the links can take various forms (point-to-point, bus, local area network, etc.), 2) it supports both concurrent and sequential modes of communication and computation, 3) it employs a combination of preemptive and non-preemptive scheduling, 4) it introduces the concept of an association array to tackle the problem of multi-rate systems (which are commonly found in multimedia applications), 5) it uses a static scheduler based on deadline-based priority levels for accurate performance estimation of a co-synthesis solution, 6) it uses a new task clustering technique which takes the changing nature of the critical path in the task graph into account, 7) it supports pipelining of task graphs to derive a cost-efficient architecture, 8) it supports a mix of various technologies, such as 5 V CMOS, 3.3 V CMOS, 2.7 V CMOS, ECL, etc., to meet embedded system constraints and minimize power dissipation, and 9) if desired, it also optimizes the architecture for power consumption.

Claims

1. A method for designing the architecture of an embedded system, comprising:

(a) a pre-processing phase comprising the steps of;

(1) parsing one or more task graphs, one or more system/task constraints, and a resource library for the embedded system, wherein the embedded system has two or more instances of at least one task graph; and

(2) generating an association array for the task graphs, wherein the association array stores a limited amount of information for each instance of a task graph of the embedded system to avoid replication of a full description for each task graph having two or more instances and its associated parameters; and

(b) a synthesis phase, following the pre-processing phase, comprising the step of allocating one or more groups of one or more tasks in the tasks graphs to one or more processing elements (PEs) in the resource library and allocating one or more edges in the tasks graphs to one or more communication links in the resource library, based on performance evaluation of one or more possible allocations for each of the groups and edges in light of the system/task constraints, wherein the performance evaluation uses the association array.

2. The method of claim 1, wherein the pre-processing phase further comprises the step of defining a hyperperiod for the embedded system, wherein the association array stores the limited amount of information for each instance of a task graph of the embedded system in the hyperperiod.

3. The method of claim 2, wherein the hyperperiod is based on modified task graph periods that reduce the hyperperiod.

4. The method of claim 2, wherein the hyperperiod comprises hyperperiod spill to account for a task graph that does not complete within the hyperperiod, wherein the hyperperiod spill is allocated at the beginning of the hyperperiod.

5. The method of claim 1, wherein, for each instance, the limited amount of information comprises a PE instance, an earliest start time, a deadline, a priority level, a best-case projected finish time (PFT), and a worst-case PFT.

6. The method of claim 5, wherein the deadline of the nth instance of a task graph is offset from the deadline of the first instance of the task graph by (n-1) multiplied by the period of the task graph.

7. The method of claim 1, wherein different instances of the task graph are distributed to different PEs, thereby enabling concurrent execution of the different instances in a pipelined manner.

8. The method of claim 1, wherein the task graph has a deadline greater than its period and the association array is a two-dimensional array, one dimension corresponding to consecutive execution of different instances of the task graph and the other dimension corresponding to concurrent execution of different instances of the task graph.

9. An embedded system having an architecture generated using the method of claim 1.

10. A method for designing the architecture of an embedded system, comprising:

(a) a pre-processing phase comprising the steps of;

(1) parsing one or more task graphs, one or more system/task constraints, and a resource library for the embedded system; and

(2) defining a hyperperiod for the embedded system, wherein the hyperperiod comprises hyperperiod spill to account for one or more task graphs that do not complete within the hyperperiod, wherein the hyperperiod spill is allocated at the beginning of the hyperperiod; and

(b) a synthesis phase, following the pre-processing phase, comprising the step of allocating one or more groups of one or more tasks in the tasks graphs to one or more processing elements (PEs) in the resource library and allocating one or more edges in the tasks graphs to one or more communication links in the resource library, based on performance evaluation of one or more possible allocations for each of the groups and edges in light of the system/task constraints, wherein the performance evaluation is based on the hyperperiod with the hyperperiod spill.

11. An embedded system having an architecture generated using the method of claim 10.

12. A method for designing the architecture of an embedded system, comprising:

(a) a pre-processing phase comprising the step of parsing one or more task graphs, one or more system/task constraints, and a resource library for the embedded system; and

(b) a synthesis phase, following the pre-processing phase, comprising the steps of;

(1) generating an allocation array for each group of one or more tasks in the tasks graphs and each edge between groups in the task graphs, wherein each allocation array comprises one or more different possible allocations for the groups and edges arranged based on a selected cost function; and

(2) allocating each group to a processing element (PE) in the resource library and each edge to a communication link in the resource library, by evaluating performance of the one or more possible allocations in the corresponding allocation array in light of the system/task constraints.

13. The method of claim 12, wherein the allocations are ordered in the allocation array by dollar cost.

14. The method of claim 12, wherein the allocations are ordered in the allocation array by average power dissipation.

15. The method of claim 12, wherein the allocation array is generated using architectural hints that pre-store allocation templates corresponding to mappings of sub-task-groups to part of the architecture of the embedded system.

16. The method of claim 12, wherein each allocation step in the allocation array is limited to m new PEs and n new communication links of the same type, wherein m and n are specified thresholds.

17. The method of claim 16, wherein m and n are both two.

18. The method of claim 12, wherein, during allocation array generation, for each allocation, checks are made for signal compatibility and voltage translation buffers are added, as necessary.

19. The method of claim 12, wherein, during allocation array generation, allocations are excluded for which at least one of pin count, gate count, communication port count, memory limits, and peak power dissipation is exceeded.

20. An embedded system having an architecture generated using the method of claim 12.

21. A method for designing the architecture of an embedded system, comprising:

(a) a pre-processing phase comprising the step of parsing one or more task graphs, one or more system/task constraints, and a resource library for the embedded system; and

(b) a synthesis phase, following the pre-processing phase, comprising the steps of;

(1) selecting possible allocations for each group of one or more tasks in the task graphs and each edge in the task graphs;

(2) performing scheduling for each selected allocation, wherein the scheduling for at least one selected allocation uses a combination of preemptive and non-preemptive scheduling taking into account a preemption overhead corresponding to one or more types of operating system overheads associated with the selected allocation;

(3) evaluating performance of each selected allocation based on results of the scheduling in light of the system/task constraints; and

(4) allocating each group to a processing element (PE) in the resource library and each edge to a communication link in the resource library, based on results of the performance evaluation.

22. The method of claim 21, wherein the preemption overhead for the at least one selected allocation is specified a priori.

23. The method of claim 21, wherein preemption is restricted to the last task in a task graph.

24. The method of claim 21, wherein preemption of a higher priority task by a lower priority task is allowed only in the case when the higher priority task is a sink task that will not miss its deadline.

25. The method of claim 21, wherein the scheduling relies on deadline-based priority levels of tasks in allocated groups and edges that are allocated to inter-PE communication links.

26. The method of claim 21, wherein the scheduling takes into consideration any hyperperiod spill that results when execution of one or more different tasks exceed a hyperperiod of the embedded system.

27. The method of claim 21, wherein, during scheduling, a first copy of the task is scheduled and, when possible, start and finish times of any remaining copies of the task in a hyperperiod of the embedded system are updated to reduce scheduling complexity.

28. The method of claim 21, wherein tasks and edges are ordered for scheduling based on decreasing order of their priority levels.

29. The method of claim 28, wherein, if two tasks have equal priority levels, then the task with a shorter execution time is scheduled first.

30. The method of claim 28, wherein, if two edges have equal priority levels, then the edge with a shorter communication time is scheduled first.

31. The method of claim 21, wherein, when scheduling edges, a mode of communication supported by the corresponding communication link and PE is taken into account.

32. The method of claim 31, wherein the mode of communication is either sequential or concurrent.

33. The method of claim 21, wherein, when scheduling edges, the scheduling takes into account a corresponding type of communication link.

34. The method of claim 33, wherein the corresponding type of communication link is either point-to-point, multipoint, or local area network.

35. The method of claim 21, wherein finish time estimation is part of the performance evaluation of each allocation and the finish time estimation calculates the finish time of each task and edge using the longest path algorithm.

36. The method of claim 21, wherein, if the scheduling performances for all of the allocations for the selected cluster fail to meet the deadlines, an allocation is selected based on a cost function by which a summation of best-case finish times of all task graphs is maximum, wherein the best-case finish time of a task graph is a maximum of best-case finish times of constituent tasks with specified deadlines.

37. The method of claim 36, wherein, if there are more than one allocation which satisfy the cost function criteria, an allocation is chosen for which a summation of worst-case finish times of all task graphs is maximum.

38. An embedded system having an architecture generated using the method of claim 21.