Data processing: structural design – modeling – simulation – and em – Simulating electronic device or electrical system – Target device
Patent
1998-02-17
2000-09-12
Teska, Kevin J.
Data processing: structural design, modeling, simulation, and em
Simulating electronic device or electrical system
Target device
703 2, 703 22, 703 23, 709102, 709104, 709105, 712 28, 712 30, 717 5, 717 8, G06F 944
Patent
active
061171808
ABSTRACT:
Embedded systems employed in critical applications demand high reliability and availability in addition to high performance. Hardware-software co-synthesis is the process of partitioning an embedded system specification into hardware and software modules to meet performance, cost, reliability, and availability goals. The present invention addresses the problem of hardware-software co-synthesis of fault-tolerant real-time heterogeneous distributed embedded systems. Fault detection capability is imparted to the embedded system by adding assertion and duplicate-and-compare tasks to the task graph specification prior to co-synthesis. The reliability and availability of the architecture are evaluated during co-synthesis. On embodiment of the present invention, called COFTA, allows the user to specify multiple types of assertions for each task. It uses the assertion or combination of assertions that achieves the required fault coverage without incurring too much overhead. New methods are proposed to: 1) perform fault tolerance based task clustering, which determines the best placement of assertion and duplicate-and-compare tasks, 2) derive the best error recovery topology using a small number of extra processing elements, 3) exploit multi-dimensional assertions, and 4) share assertions to reduce the fault tolerance overhead. The present algorithm can tackle multirate systems commonly found in multimedia applications.
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.
"Dynamic Critical-Path Scheduling: An Effective Technique for Allocating Task Graphs to Multiprocessors", by Yu-Kwong Kwok, Ishfaq Ahmad, IEEE Transactions on Parallel and Distributed Systems, vol. 7, No. 5, May 1996, 17 pages.
"Efficient Scheduling Algorithms for Real-Time Multiprocessor Systems", by Krithi Ramamritham, John A. Stankovic, and Perng-Fei Shiah, IEEE Transactions on Parallel and Distributed, vol. 1, No. 2, Apr. 1990, 12 pages.
"Exploiting Unused Periodic Time for Aperiodic Service Using the Extended Priority Exchange Algorithm", by Brinkley Sprunt, John Lehoczky, and Lui Sha, IEEE Computer Society Real-Time Systems Symposium, Dec. 6-8, 1988, pp. 251-258.
"Hardware-Software Co-Design of Embedded Systems", by Wayne H. Wolf, Proceedings of the IEEE, vol. 82, No. 8, Jul. 1994, pp. 967-989.
"A Hardware-Software Codesign Methodology for DSP Applications", by Asawaree Kalavade and Edward A. Lee, Sep. 1993 IEEE Design & Test of Computers, pp. 16-28.
"Hardware-Software Cosynthesis for Digital Systems", by Rajesh K. Gupta and Giovanni De Micheli, Sep. 1993, IEEE Design & Test of Computers, pp. 29-40.
A Hardware/Software Partitioner Using a Dynamically Determined Granularity, by Jorg Henkel and Rolf Ernst, DAC 97-Jun. 1997 Anaheim, CA, 3 pages.
"Hill-Climbing Heuristics for Optical Hardware, Dimensioning and Software Allocation in Fault-Tolerant Distributed Systems", by Fausto Distant and Vincenzo Piuri, IEEE Transactions on Reliability, vol. 38, No. 1, 1989 Apr., pp. 28-39.
"Load Sharing with Consideration of Future Task Arrivals in Heterogeneous Distributed Real-Time Systems", by Chao-Ju Hou and Kang G. Shin, 1991 IEEE Real-Time Computer Laboratory, pp. 94-103.
"Low Overhead Fault Tolerance for Real-Time Distributed Systems: Application to Hardware/Software Co-Synthesis of Embedded Systems", by Santhanam Srinivasan and Niraj K. Jha, 31 pages, corresponding to conference paper presented Sep. 1995 in Proc. European Design Automation Conf.
"On-Line Scheduling of Hard Deadline Aperiodic Tasks in Fixed-Priority Systems", by Sandra Ramos-Thuel and John P. Lehoczky, 1993 IEEE, pp. 160-171.
"On-Line Scheduling of Real-Time Tasks", by Kwang S. Hong and Joseph Y.-T. Leung, 1988 IEEE Computer Society, pp. 244-250.
On the Complexity of Fixed-Priority Scheduling of Periodic, Real-Time Tasks, by Joseph Y.-T. Leung and Jennifer Whitehead, 1982 North-Holland Publishing Company, Performance Evaluation 2 (1982), pp. 237-250.
"On Non-Preemptive Scheduling of Periodic and Sporadic Tasks", by Kevin Jeffay, Donald F. Stanat, and Charles U. Martel, Dec. 1991 IEEE Twelfth Real-Time Systems Symposium, pp.129-139.
Optimal Algorithms for Synthesis of Reliable Application-Specific Heterogeneous Multiprocessors, by Aurobindo Dasgupta and Ramesh Karri, IEEE Transactions on Reliability, vol. 44, No. 4, 1995 Dec., pp. 603-613.
"Optimal Priority Assignment for Aperiodic Tasks With Firm Deadlines in Fixed Priority Pre-Emptive Systems", by Robert Davis and Alan Burns, Information Processing Letters, vol. 53, No. 5, Mar. 1995, pp. 249-254.
"Performance Estimation for Real-Time Distributed Embedded Systems", by Ti-Yen Yen and Wayne Wolf, Dept. of Electrical Engineering, Princeton University, pp. 1-6, Proc. of Intl. Conf. on Computer Design, Oct. 1995.
"Process Partitioning for Distributed Embedded Systems", by Junwei Hou and Wayne Wolf, Sep. 1996 IEEE, pp. 70-75.
"Program Implementation Schemes for Hardware-Software Systems", by Rajesh K. Gupta, Claudionor N. Coelho Jr., and Giovanni De Micheli, Jan. 1994 IEEE, vol. 27, No. 1, pp. 48-55.
"Rate-Monotonic Analysis for Real-Time Industrial Computing", by Mark H. Klein et al., Jan. 1994, vol. 27, No. 1, pp. 24-33.
"Replication and Allocation of Task Modules in Distributed Real-Time Systems", by Chao-Ju Hou and Kang G. Shin, Jun. 1994, IEEE Computer Society, pp. 26-35.
"Scheduling Algorithms and Operating Systems Support for Real-Time Systems", by Krithi Ramamritham and John A. Stankovic, Proceedings of the IEEE, vol. 82, No. 1, Jan. 1994, pp. 55-67.
"Scheduling Parallel I/O Operations in Multiple Bus Systems", by Ravi Jain et al., Journal of Parallel and Distributed Computing 16, 1992, pp. 352-362.
"Scheduling Periodically Occurring Tasks on Multiple Processors", by Eugene L. Lawler and Charles U. Martel, Information Processing Letters, vol. 12, No. 1, Feb. 1981.
"Scheduling Slack Time in Fixed Priority Pre-emptive Systems", by R.I. Davis, K.W. Tindell, and A. Burns, Dec. 1993 IEEE Real-Time Systems Symposium, pp. 222-231.
"Scheduling Tasks with Resource Requirements in Hard Real-Time Systems", by Wei Zhao et al., IEEE Transactions on Software Engineering, vol. SE-13, No. 5, May 1987, pp. 564-577.
"Sensitivity-Driven Co-Synthesis of Distributed Embedded Systems", by Ti-Yen Yen and Wayne Wolf, International Symposium on System Synthesis, 1995, pp. 1-6.
"SIERA: A Unified Framework for Rapid-Prototyping of System-Level Hardware and Software", by Mani B. Srivastava and Robert W. Brodersen, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 14, No. 6, Jun. 1995, pp. 676-693.
"SOS: Synthesis of Application-Specific Heterogeneous Multiprocessor Systems", by Shiv Prakash and Alice C. Parker, Journal of Parallel and Distributed Computing, vol. 16, No. 4, pp. 338-351 (1992).
"SpecCharts: A VHDL Front-End for Embedded Systems", by Frank Vahid, Sanjiv Narayan, and Daniel D. Gajski, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 14, No. 6, Jun. 1995, pp. 694-706.
"Synthesis of Application Specific Instruction Sets", Ing-Jer Huang and Alvin M. Despain, IEEE Transactions of Computer-Aided Design of Integrated Circuits and Systems, vol. 14, No. 6, Jun. 1995, pp. 663-675.
"System-Level Synthesis of Low-Power Hard Real-Time Systems", by Darko Kirovski and Miodrag Potkonjak, DAC97, Jun. 1997, Anaheim, CA, 6 pages.
"Task Allocation for Maximizing Reliability of Distributed Computer Systems", by Sol M. Shatz, Jia-Ping Wang, and Masanori Goto, IEEE Transactions on Computers, vol. 41, No. 9, Sep. 1992, pp. 1156-1160.
"TBFT: A Task-Based Fault Tolerance Scheme for Distributed Systems", by Shalini Yajnik, Santhanam Srinivasan, Niraj K. Jha, Seventh International Confe
Dave Bharat P.
Jha Niraj K.
Broda Samuel
Lucent Technologies - Inc.
Mendelsohn Steve
Teska Kevin J.
LandOfFree
Hardware-software co-synthesis of heterogeneous distributed embe 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 heterogeneous distributed embe, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Hardware-software co-synthesis of heterogeneous distributed embe will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-91959