Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
1998-02-17
2001-09-11
Smith, Matthew (Department: 2825)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
C716S030000, C716S030000, C709S241000, C709S241000, C712S028000
Reexamination Certificate
active
06289488
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to the design of real-time distributed embedded systems, and, in particular, to the process of partitioning an embedded system specification into hardware and software modules using hardware-software co-synthesis.
2. Description of the Related Art
The architecture definition of embedded systems has generally largely been dependent on the ingenuity of system architects. However, in addition to a longer architecture definition interval, at times, the resulting architecture is either over-designed or fails to meet the specified constraints. Therefore, design automation in the area of hardware-software co-synthesis is of utmost importance from design time and quality of architecture standpoints. Finding an optimal hardware-software architecture entails selection of processors, application-specific integrated circuits (ASICs), and communication links such that the cost of the architecture is minimum and all real-time constraints are met. Hardware-software co-synthesis involves various steps such as allocation, scheduling, and performance estimation. The allocation step determines the mapping of tasks to processing elements (PEs) and inter-task communications to communication links. The scheduling step determines the sequencing of tasks mapped to a PE and sequencing of communications on a link. The performance estimation step estimates the finish time of each task and determines the overall quality of the architecture in terms of its dollar cost, ability to meet its real-time constraints, power consumption, fault tolerance, etc. Both allocation and scheduling are known to be NP-complete. See References (
1
)-(
2
). Therefore, optimal co-synthesis is computationally a very hard problem.
Researchers have primarily focused their interest in the last several years on hardware-software co-synthesis of one-CPU-one-ASIC architectures (see References (
3
)-(
9
)), where attempts have been made to move operations from hardware to software or vice versa to minimize cost and meet deadlines.
In the area of distributed system co-synthesis, the target architecture can employ multiple CPUs, ASICs, and field-programmable gate arrays (FPGAs). See Reference (
10
). Two distinct approaches have been used to solve the distributed system co-synthesis problem: optimal and heuristic.
In the optimal domain, the approaches are: 1) mixed integer linear programming (MILP) and 2) exhaustive. The MILP solution proposed in Reference (
11
) has the following limitations: 1) it is restricted to one task graph, 2) it does not handle preemptive scheduling, 3) it requires determination of the interconnection topology up front, and 4) because of time complexity, it is suitable only for small task graphs. A configuration-level hardware-software partitioning algorithm is presented in Reference (
12
) based on an exhaustive enumeration of all possible solutions. Its limitations are: 1) it allows an architecture with at most one CPU, 2) simulation is used for performance evaluation which is very time-consuming, and 3) the communication overheads are ignored.
There are two distinct approaches in the heuristic domain: 1) iterative (see References (
13
)-
20
A, (
16
)), where an initial solution is iteratively improved through various moves, and 2) constructive (see fill References (
17
)-(
19
)), where the solution is built step-by-step and the complete solution is not available until the algorithm terminates. The iterative procedure given in References (
13
)-(
15
) has the following limitations: 1) it considers only one type of communication link, and 2) it does not allow mapping of each successive copy of a periodic task to different PEs. Another iterative procedure targeted for low power system is proposed in Reference (
16
). It uses power dissipation as a cost function for allocation and has the following limitations: 1) it ignores inter-task communication scheduling, and 2) it is not suitable for multi-rate systems commonly found in multi-media systems. A constructive co-synthesis procedure for fault-tolerant distributed embedded systems is proposed in Reference (
17
). However, it does not support communication topologies such as bus, local area network (LAN), etc., and its allocation step uses a pessimistic performance evaluation technique which may increase system cost. Also, it assumes that computation and communication can always be done in parallel, which may not be possible. It is also not suitable for multi-rate embedded systems, e.g., multi-media systems. The optimal approaches are only applicable to task graphs consisting of around 10 tasks, and the heuristic approaches cannot tackle hierarchical task graphs or architectures.
Hierarchical hardware-software architectures have been presented previously in Reference (
20
). There, a parameterized hierarchical architectural template is specified a priori, with ASICs at the lowest layer, general-purpose processors at the next higher layer, and single-board computers above that. Tasks from the task graphs are then manually allocated to one of these layers. However, such a pre-specified architectural template may not lead to the least expensive architecture, as pointed out in Reference (
20
) itself.
Large embedded systems are generally specified in terms of hierarchical task graphs. Thus, it is important for a co-synthesis algorithm to exploit and tackle such specifications. Also, non-hierarchical architectures for large embedded systems, such as those used in telecom applications, inherently create processing and communication bottlenecks. This can substantially increase the embedded system cost.
SUMMARY OF THE INVENTION
A constructive co-synthesis system, called COSYN, is proposed in Reference (
18
) which also targets general and low power distributed architectures. Another constructive co-synthesis system, called COFTA, is proposed in Reference (
19
) which targets fault-tolerant distributed architectures, and addresses reliability and availability of the embedded system during co-synthesis.
The present invention is directed to a heuristic-based co-synthesis technique, called COHRA (CO-synthesis of HieRarchical Architectures), which takes as input an embedded system specification in terms of hierarchical acyclic task graphs, and generates an efficient hierarchical hardware/software architecture that meets the real-time constraints. It has also been extended to optimize power consumption and fault tolerance. The present technique is suited to both small- and large-scale real-time embedded systems. For task graphs from the literature for which mixed integer linear programming (MILP) based optimal results (see Reference (
11
)) are known, COSYN (see Reference (
18
)) also obtains the same optimal results in many orders of magnitude smaller CPU time. Therefore, we compare the performance of COHRA with COSYN. Experimental results demonstrate the efficacy of COHRA.
In the present technique, a hierarchical architecture template is not pre-specified. It is up to the co-synthesis algorithm to come up with the most efficient hierarchical or non-hierarchical heterogeneous distributed system architecture as well as automatically perform allocation and scheduling to meet real-time and other constraints.
In one embodiment, the present invention is a method for designing the architecture of an embedded system, comprising a pre-processing phase and a synthesis phase. The pre-processing phase comprises 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. The synthesis phase, following the pre-processing phase, comprises the step of allocating one or more groups of one or more tasks in the tasks graphs to one or more processing elements 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 the architecture hints and performance evaluation of one or more possible allocations for each of the group
Dave Bharat P.
Jha Niraj K.
Lucent Technologies - Inc.
Mendelsohn Steve
Smith Matthew
Thompson A. M.
LandOfFree
Hardware-software co-synthesis of hierarchical heterogeneous... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Hardware-software co-synthesis of hierarchical heterogeneous..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Hardware-software co-synthesis of hierarchical heterogeneous... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2497415