HARDWARE-SOFTWARE CO-SYNTHESIS OF HIERARCHICAL HETEROGENEOUS DISTRIBUTED EMBEDDED SYSTEMS

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.