COHRA: Hardware-software co-synthesis of hierarchical distributed embedded system architectures

Hardware-software co-synthesis of an embedded system architecture entails partitioning of its specification into hardware and software modules suck 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. In this paper, we address the problem of hardware-software co-synthesis of hierarchical distributed embedded system architectures from hierarchical or non-hierarchical task graphs. Our 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 PEs 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. We show how our co-synthesis algorithm can be easily extended to consider fault tolerance or low power objectives or both. Although hierarchical architectures have been proposed before, to the best of our knowledge, this is the first time the notion of hierarchical task graphs and hierarchical architectures has been supported in a co-synthesis algorithm. Application of the proposed algorithm to several examples from real-life telecom transport systems shows that up to 47% reduction in embedded system cost is possible by exploiting the concept of hierarchical task graphs and architectures.