US6097886A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Cluster-based hardware-software co-synthesis of heterogeneous distributed embedded systems
Assignee: Nokia of America Corp
•
Filing: 1998-02-17
•
Granted: 2000-08-01
•
Expires: 2018-02-17
Abstract
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.
Inventors
- 👤 Bharat P. Dave
- 👤 Niraj K. Jha
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-08 03:57
CPC Classifications
G; G06; G06F; G06F8/00; G06F8/10
Claims Analysis
Total Claims: 32
Claim 1
Independent Claim
163 words
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 the one or more task graphs to form one or more clusters for the embedded system, wherein, after each task in a task graph is grouped into a cluster, a critical path for the corresponding task graph is re-determined to account for any changes in the critical path; and (b) a synthesis phase, following the pre-processing phase, comprising the step of allocating the clusters 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 clusters and edges in light of the system/task constraints.
Claim 2
Independent Claim
163 words
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 the one or more task graphs to form one or more clusters for the embedded system, wherein, after each task in a task graph is grouped into a cluster, a critical path for the corresponding task graph is re-determined to account for any changes in the critical path; and (b) a synthesis phase, following the pre-processing phase, comprising the step of allocating the clusters 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 clusters and edges in light of the system/task constraints.
Claim 3
Dependent Claim
23 words
The method of claim 1, wherein priority levels of the tasks are used to determine the order of selecting tasks during task clustering.
Claim 4
Dependent Claim
19 words
The method of claim 2, wherein the priority levels are recalculated after each task is grouped into a cluster.
Claim 5
Dependent Claim
24 words
The method of claim 2, wherein the priority levels are used to determine how the selected task is to be grouped with other tasks.
Claim 6
Dependent Claim
26 words
The method of claim 2, wherein energy levels of the tasks are used to determine how the selected task is to be grouped with other tasks.
Claim 7
Dependent Claim
19 words
The method of claim 5, wherein the energy levels are recalculated after each task is grouped into a cluster.
Claim 8
Dependent Claim
22 words
The method of claim 2, wherein the priority levels are calculated based on task deadlines as well as computation and communication costs.
Claim 9
Dependent Claim
17 words
The method of claim 1, wherein a new cluster is started before an existing cluster is completed.
Claim 10
Dependent Claim
19 words
The method of claim 1, wherein, during task clustering, the size of a cluster is limited by the hyperperiod.
Claim 11
Dependent Claim
13 words
An embedded system having an architecture generated using the method of claim 1.
Claim 12
Independent Claim
157 words
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 the one or more task graphs to form one or more clusters for the embedded system, wherein, during task clustering, a first cost function, used to select the next task for clustering, is recalculated after each task is grouped into a cluster; and (b) a synthesis phase, following the pre-processing phase, comprising the step of allocating the clusters 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 clusters and edges in light of the system/task constraints.
Claim 13
Independent Claim
157 words
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 the one or more task graphs to form one or more clusters for the embedded system, wherein, during task clustering, a first cost function, used to select the next task for clustering, is recalculated after each task is grouped into a cluster; and (b) a synthesis phase, following the pre-processing phase, comprising the step of allocating the clusters 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 clusters and edges in light of the system/task constraints.
Claim 14
Dependent Claim
18 words
The method of claim 11, wherein the first cost function is based on priority levels of the tasks.
Claim 15
Dependent Claim
22 words
The method of claim 12, wherein the priority levels are calculated based on task deadlines as well as computation and communication costs.
Claim 16
Dependent Claim
21 words
The method of claim 13, wherein the deadline-based priority level calculation is not restricted to a specific form of communication mechanism.
Claim 17
Dependent Claim
16 words
The method of claim 13, wherein different tasks within a single task graph have different deadlines.
Claim 18
Dependent Claim
35 words
The method of claim 13, wherein the priority level is modified based on hyperperiod spill used to account for one or more task graphs that do not complete within a hyperperiod for the embedded system.
Claim 19
Dependent Claim
25 words
The method of claim 11, wherein a second cost function is used to determine how the selected task is to be grouped with other tasks.
Claim 20
Dependent Claim
16 words
The method of claim 17, wherein the second cost function is based on the priority levels.
Claim 21
Dependent Claim
18 words
The method of claim 17, wherein the second cost function is based on energy levels of the tasks.
Claim 22
Dependent Claim
20 words
The method of claim 17, wherein the second cost function is recalculated after each task is grouped into a cluster.
Claim 23
Dependent Claim
17 words
The method of claim 11, wherein a new cluster is started before an existing cluster is completed.
Claim 24
Independent Claim
23 words
The method of claim 1l, wherein, during task clustering, the size of each cluster is limited by a hyperperiod for the embedded system.
Claim 25
Dependent Claim
13 words
An embedded system having an architecture generated using the method of claim 11.
Claim 26
Independent Claim
148 words
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 the one or more task graphs to form one or more clusters for the embedded system; and (b) a synthesis phase, following the pre-processing phase, comprising the step of allocating the clusters 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 clusters and edges in light of the system/task constraints, wherein, during the synthesis phase, the clusters are sequentially selected based on cost functions for the clusters.
Claim 27
Independent Claim
148 words
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 the one or more task graphs to form one or more clusters for the embedded system; and (b) a synthesis phase, following the pre-processing phase, comprising the step of allocating the clusters 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 clusters and edges in light of the system/task constraints, wherein, during the synthesis phase, the clusters are sequentially selected based on cost functions for the clusters.
Claim 28
Dependent Claim
12 words
The method of claim 24, wherein the cost functions are priority levels.
Claim 29
Dependent Claim
25 words
The method of claim 25, wherein the priority level of a cluster is the maximum priority level of the tasks and edges within the cluster.
Claim 30
Dependent Claim
33 words
The method of claim 24, wherein the cost functions are recalculated after each cluster is allocated to account for any changes in the cost functions of the tasks and edges within the clusters.
Claim 31
Dependent Claim
12 words
The method of claim 27, wherein the cost functions are priority levels.
Claim 32
Dependent Claim
13 words
An embedded system having an architecture generated using the method of claim 24.
References Cited (Backward Citations)
US4885684A
Cited
US5452461A
Cited
US5202987A
Cited
US5210872A
Cited
US5418953A
Cited
US5590323A
Cited
US5781787A
Cited
US5768594A
Cited
US5870588A
Cited
US5742821A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2003-08-01 | 2004-01-31 | 2004-08-01 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-08-01 | 2008-01-31 | 2008-08-01 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-08-01 | 2012-01-31 | 2012-08-01 | $7700.00 | Window Closed / Lapsed |