Hardware-software co-synthesis of hierarchical heterogeneous distributed embedded systems

• US 6,289,488 B1
• Filed: 02/17/1998
• Issued: 09/11/2001
• Est. Priority Date: 02/24/1997
• Status: Expired due to Term

• Current Assignee: WSOU Investments, LLC (WSOU Holdings, LLC)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Dave, Bharat P., Jha, Niraj K.
• Primary Examiner(s): Smith, Matthew
• Assistant Examiner(s): THOMPSON, ANNETTE M
• Application Number:
  US09/025,537
• Time in Patent Office: 1,302 Days
• Field of Search: 395/500.34, 703/13, 716/1
• US Class Current: 716/105
• 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

Abstract

Hardware-software co-synthesis of an embedded system architecture entails partitioning of its specification into hardware and software modules such that its real-time and other constraints are met. Embedded systems are generally specified in terms of a set of acyclic task graphs. For medium-to-large scale embedded systems, the task graphs are usually hierarchical in nature. The embedded system architecture, which is the output of the co-synthesis system, may itself be non-hierarchical or hierarchical. Traditional non-hierarchical architectures create communication and processing bottlenecks, and are impractical for large embedded systems. Such systems require a large number of processing elements and communication links connected in a hierarchical manner, thus forming a hierarchical distributed architecture, to meet performance and cost objectives. The present invention addresses the problem of hardware-software co-synthesis of hierarchical heterogeneous distributed embedded system architectures from hierarchical or non-hierarchical task graphs. The co-synthesis algorithm has the following features: 1) it supports periodic task graphs with real-time constraints, 2) it supports pipelining of task graphs, 3) it supports a heterogeneous set of processing elements and communication links, 4) it allows both sequential and concurrent modes of communication and computation, 5) it employs a combination of preemptive and non-preemptive static scheduling, 6) it employs a new task clustering technique suitable for hierarchical task graphs, and 7) it uses the concept of association arrays to tackle the problem of multi-rate tasks encountered in multimedia systems.

Claims

1. 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 architectural hints, one or more system/task constraints, and a resource library for the embedded system; and

(b) a constructive co-synthesis phase, following the pre-processing phase, comprising the step of allocating one or more groups of one or more tasks in the task graphs to one or more processing elements (PEs) in the resource library and allocating one or more edges in the task graphs to one or more communication links in the resource library, based on one or more of the architecture hints and performance evaluation of one or more possible allocations for each of the groups and edges in light of the system/task constraints, wherein an architectural hint provides a priori information that directs allocation of (1) a group of one or more tasks in a task graph towards a particular PE or (2) an edge in a task graph towards a particular communication link.

2. The method of claim 1, wherein at least one architectural hint is used to indicate whether a particular task is hierarchical or non-hierarchical.

3. The method of claim 1, wherein at least one architectural hint is used to indicate whether particular tasks from different instances of the same type of PE can be merged.

4. The method of claim 1, wherein at least one architectural hint is used to indicate whether a particular task is targeted for reuse.

5. The method of claim 1, wherein at least one architectural hint is used to indicate whether a e particular task is a hierarchy facilitating task.

6. The method of claim 1, wherein at least one architectural hint is used to indicate whether a particular edge is a hierarchy facilitating edge.

7. The method of claim 1, wherein at least one architectural hint is used to indicate whether a particular task is preemptible by a lower priority task.

8. The method of claim 1, wherein at least one architectural hint is used to indicate whether a particular task should be mapped to a particular layer of the architecture.

9. 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) performing task clustering on one or more non-hierarchical tasks in the task graphs to form one or more clusters for the embedded system; and

(b) a constructive co-synthesis phase, following the pre-processing phase, comprising the step of allocating the clusters and one or more hierarchical tasks in the task grab to one or more processing elements (PEs) in the resource library and allocating one or more edges in the task 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 clusters, edges, and hierarchical tasks in light of the system/task constraints.

10. The method of claim 9, wherein, during the pre-processing phase, one or more architectural hints indicate that one or more tasks are hierarchical tasks.

11. The method of claim 9, wherein, during the synthesis phase, the clusters and the hierarchical tasks are selected based on priority levels.

12. The method of claim 11, wherein, during the synthesis phase, the priority level of each task, cluster, and hierarchical task is recalculated after each cluster or hierarchical task is allocated.

13. The method of claim 9, wherein, during the synthesis phase, the clusters and the hierarchical tasks are selected based on average power dissipation.

14. The method of claim 9, wherein, during the pre-processing phase, one or more sub-architectures are generated for the embedded system and, during the synthesis phase, preference is given to allocating the clusters and the hierarchical tasks to the sub-architectures.

15. The method of claim 14, wherein the sub-architectures are generated based on one or more architectural hints.

16. The method of claim 14, wherein, during the pre-processing phase, preferences are specified for allocating one or more particular tasks to particular hierarchy layers of the embedded system and the sub-architectures are generated based on the layer allocation preferences.

17. The method of claim 9, wherein one or more hierarchical task graphs are reused one or more times in the embedded system.

18. The method of claim 9, wherein the pre-processing phase further comprises the step of parsing one or more hierarchy facilitating tasks (HFTs) and one or mote hierarchy facilitating edges (HFEs), which are used to indicate delegation of the tasks and edged.

19. The method of claim 9, wherein, if two originally consecutive tasks are allocated to the same PE, then any associated HFTs and HFEs are removed from the task graph.

20. 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;

(b) a constructive co-synthesis phase, following the pre-processing phase, comprising the step of allocating one or more groups of one or more tasks in the task graphs to one or more processing elements (PEs) in the resource library and allocating one or more edges in the task 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; and

(c) a hierarchy compression phase, following the synthesis phase, comprising the step of merging at least two PEs into a single PE to generate a compressed embedded system that continues to meet the system/task constraints.

21. The method of claim 20, wherein two PEs are merged into a single PE if each task allocated to one of the two PEs is preference- and exclusion-compatible with every task allocated to the other PE.

22. The method of claim 20, wherein at least two layers in the architecture are collapsed by moving one or more tasks from a PE at one layer to a PE at another layer.

23. The method of claim 20, wherein the hierarchy compression phase comprises the steps of:

(1) generating one or more possible merges for each of one or more pairs of layers in the architecture; and

(2) performing one or more of the possible merges based on evaluation of results from performing scheduling for each possible merge for each pair of layers in light of the system/task constraints.

24. The method of claim 23, wherein steps (1) and (2) are repeated as long as at least one of architecture cost, merge potential, or layer count is decreasing.