Electrical computers and digital processing systems: support – Reconfiguration
Reexamination Certificate
1999-09-10
2002-07-02
Butler, Dennis M. (Department: 2185)
Electrical computers and digital processing systems: support
Reconfiguration
C713S001000
Reexamination Certificate
active
06415384
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
Embedded systems perform application-specific functions using central processing units (CPUs). They employ both general-purpose CPUs and application-specific integrated circuits (ASICs). ASICs can be based on standard cells, gate arrays, field-programmable gate arrays (FPGAs), or complex programmable logic devices (CPLDs). An embedded system architecture consists of hardware architecture and software architecture. The hardware architecture of an embedded system defines the interconnections of various hardware components. The software architecture defines the allocation of sequences of codes to specific general-purpose processors. Hardware/software co-synthesis is a process to obtain hardware and software architectures such that various embedded system constraints such as real-time, cost, power, etc., are met. Hardware/software co-synthesis involves various steps such as allocation, scheduling, and performance estimation. Optimal hardware/software co-synthesis is known to be an NP-complete problem, where NP stands for non-deterministically polynomial. See Reference (1). Embedded systems employing reconfigurable hardware such as FPGAs and CPLDs are referred as reconfigurable embedded systems. Reconfigurable systems can provide higher performance as well as flexibility to adapt with changing system needs at low cost. See References (2)-(4). Dynamically reconfigurable embedded systems exploit reconfigurability of programmable devices at run-time to achieve further cost savings. With the availability of partially reconfigurable devices, dynamically reconfigurable systems have become viable. See References (5)-(8).
Co-synthesis of heterogeneous distributed systems has been previously addressed in References (9)-(24). Some of these co-synthesis systems (see References (12), (15), (16), (20), (23), and (24)) employ programmable devices such as FPGAs. However, none of these systems target dynamically reconfigurable embedded systems.
SUMMARY OF THE INVENTION
Dynamically reconfigurable embedded system architectures require reconfiguration of programmable hardware components such as FPGAs and CPLDs. These devices are either completely or partially reprogrammed at run-time to perform different functions at different times. Hardware/software co-synthesis of dynamically reconfigurable architectures spans three major sub-problems: 1) delay management, 2) reconfiguration management, and 3) reconfiguration interface synthesis. Delay for a circuit through a programmable device varies depending on how the constituent circuit is placed and routed. Delay management techniques ensure that the delay constraint for the specific function is not exceeded while mapping the tasks to the programmable devices. Reconfiguration management techniques identify the grouping of tasks and their allocation such that the number of reconfigurations as well as time required for each reconfiguration are minimized while ensuring that real-time constraints are met. Reconfiguration interface synthesis determines an efficient interface for reprogramming programmable devices such that cost of the system is reduced while minimizing the reconfiguration time.
The present invention is related to a heuristic-based constructive co-synthesis algorithm, CRUSADE (Co-synthesis of ReconfigUrable System Architectures of Distributed Embedded systems) which optimizes the cost of the hardware architecture while meeting the real-time and other constraints.
The present invention addresses the co-synthesis of dynamically reconfigurable architectures. Fault-tolerant distributed embedded systems can offer high performance as well as dependability (reliability) and availability to meet the needs of critical real-time applications. The present invention can be easily extended to address the needs of fault-tolerant systems. In order to establish its effectiveness, CRUSADE has been successfully applied to several large real-life examples from mobile communication network base station, video distribution router, and telecom embedded systems.
In one embodiment, the present invention is a method for designing the architecture of an embedded system, comprising a pre-processing phase, a synthesis phase, and a reconfiguration phase. The pre-processing phase comprises the step of parsing one or more task graphs, 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 performance evaluation of one or more possible allocations for each of the groups and edges in light of the system/task constraints, to generate a current version of the embedded system. The reconfiguration phase, following the synthesis phase, comprises the step of generating a reconfigurable version of the embedded system by merging at least two programmable PEs of the current version of the embedded system into a composite reconfigurable programmable PE having at least two modes of operation.
REFERENCES:
patent: 4885684 (1989-12-01), Austin et al.
patent: 5202987 (1993-04-01), Bayer et al.
patent: 5210872 (1993-05-01), Ferguson et al.
patent: 5418953 (1995-05-01), Hunt et al.
patent: 5452461 (1995-09-01), Umekita et al.
patent: 5590323 (1996-12-01), Kartalopoulos
patent: 5742821 (1998-04-01), Prasanna
patent: 5768594 (1998-06-01), Blelloch et al.
patent: 5781787 (1998-07-01), Shafer et al.
patent: 5870588 (1999-02-01), Rompaey et al.
patent: 5954792 (1999-09-01), Balarin
patent: 5961599 (1999-10-01), Kalavade et al.
patent: 5968115 (1999-10-01), Trout
“A Global Criticality/Local Phase Driven Algorithm for the Constrained Hardware/Software Partitioning Problem”, by Asawaree Kalavade and Edward A. Lee; 1994 IEEE, pp. 42-48.
“Algorithms for Scheduling Hard Aperiodic Tasks in Fixed-Priority Systems using Slack Stealing”, by Sandra R. Thuel and John P. Lehoczky, 1994 IEEE, pp. 22-33.
“Allocation of Periodic Task Modules with Precedence and Deadline Constraints in Distributed Real-Time Systems”,by Chao-Ju Hou and Kang G. Shin, 1992 IEEE Computer Society Technical Committee on Real-Time Systewms, 11 pages.
“An Efficient Algorithm for Graph Isomorphism”, by D.G. Corneil and C.C. Gotlieb, Journal of the Associatioin for Computing Machinery, vol. 17, No. 1, Jan. 1970, pp. 51-64.
“An Optimal Algorithm for Scheduling Soft-Aperiodic Tasks in Fixed-Priority Preemptive Systems”, by John P. Lehoczky and Sandra Ramos-Thuel, 1992 IEEE Computer Society Technical Committe on Real-Time Systems, 15 pages.
“Aperiodic Servers in a Deadline Scheduling Environment”, by T.M. Ghazalie and T.P. Baker; Realtime System 9, (1995), pp. 31-67.
“Architectural Support For Designing Fault-Tolerant Open Distributed Systems”, by Salim Hariri, Alok Choudhary, and Behcet Sarikaya, 1992 IEEE.
“Calculating the Maximum Execution Time on Real-Time Programs”, by P. Puschner and C.H. Koza, The Journal of Real-Time Systems, 1,(1989), pp. 159-176.
“Communication Synthesis for Distributed Embedded Systems”, by Ti-Yen Yen and Wayne Wolf, Proceedings of International Conference on Computer-Aided Design, pp. 288-294, Nov. 1995.
“Computer-Aided Hardware-Software Codesign”, by Giovanni De Micheli, Aug. 1994 IEEE Micro Chips, Systems, Software, and Applications, 8 pages.
“Configuration-Level Hardware/Software Partitioning for Real-Time Embedded Systems”, by Joseph G. D'Ambrosio and Xiaobo (Sharon) Hu, 1994 IEEE, pp. 34-41.
“Constrained Software Generation for Hardware-Software Systems”, by Rajesh K. Gupta and Giovanni De Micheli, 1994 IEEE, pp. 56-63.
“Dyna
Butler Dennis M.
Lucent Technologies - Inc.
Mendelsohn & Associates PC
LandOfFree
Hardware/software co-synthesis of dynamically reconfigurable... 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 dynamically reconfigurable..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Hardware/software co-synthesis of dynamically reconfigurable... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2833051