US 6,289,488 B1 · Hardware-software co-synthesis of hierarchical heterogeneous distributed embedded systems

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.

Claims24

Dependent claims

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.

Dependencies are inferred from the claim text.

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

Life of this patent

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

Life of this patent

Abstract

Claims24