Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Patent
1998-02-17
2000-08-29
Teska, Kevin J.
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
716 2, 716 4, 716 7, 716 8, 709102, 709103, 709104, 709105, 709106, G06F 1750
Patent
active
061102202
ABSTRACT:
Hardware-software co-synthesis of an embedded system requires mapping of its specifications into hardware and software modules such that its real-time and other constraints are met. Embedded system specifications are generally represented by acyclic task graphs. Many embedded system applications are characterized by aperiodic as well as periodic task graphs. Aperiodic task graphs can arrive for execution at any time and their resource requirements vary depending on how their constituent tasks and edges are allocated. Traditional approaches based on a fixed architecture coupled with slack stealing and/or on-line determination of how to serve aperiodic task graphs are not suitable for embedded systems with hard real-time constraints, since they cannot guarantee that such constraints would always be met. The present invention addresses the problem of concurrent co-synthesis of aperiodic and periodic specifications of embedded systems. The algorithm estimates the resource requirements of aperiodic task graphs and allocates execution slots on processing elements and communication links for executing them. The present approach guarantees that the deadlines of both aperiodic and periodic task graphs are always met. Simultaneous consideration of aperiodic task graphs while performing co-synthesis of periodic task graphs is vital for achieving superior results compared to the traditional slack stealing and dynamic scheduling approaches. This is the first co-synthesis algorithm that provides simultaneous support of periodic and aperiodic task graphs with hard real-time constraints. Application of the proposed algorithm to several examples from real-life telecom transport systems shows that up to 28% and 34% system cost savings are possible over co-synthesis algorithms which employ slack stealing and rate-monotonic scheduling, respectively.
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.
Srinivasan et al, "Hardware-Software Co-Synthesis of Fault-Tolerant Real-Time Distributed Embedded Systems", IEEE Proceedings of the 1995 European Design Automation Conference EURO-DAC '95, pp. 334-339, Sep. 1995.
Hamidzadeh et al, "Dynamic Scheduling of Real-Time Aperiodic Tasks on Multiprocessor Architectures", IEEE Proceedings of the 29th Hawaii International Conference on System Sciences, pp. 469-478, Jan. 1996.
Dave et al, "CASPER: Concurrent Hardware-software Co-Synthesis of Hard Real-Time Aperiodic and Periodic Specifications of Embedded System Architectures", IEEE Proceedings of Design, Automation, and Test in Europe 1998, pp. 118-124, Feb. 1998.
"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 Systems, 11 pages.
"An Efficient Algorithm for Graph Isomorphism", by D.G. Corneil and C.C. Gotlieb, Journal of the Association 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 Committee on Real-Time Systems, 15 pages.
"Aperiodic Servers in a Deadline Scheduling Environment", by T.M. Ghazalie and T.P. Baker; Realtime Systems 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 of 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.
"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, Apr. 1989, 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, Dec. 1995, 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.
Dave Bharat P.
Jha Niraj K.
Broda Samuel
Lucent Technologies - Inc.
Teska Kevin J.
LandOfFree
Concurrent hardware-software co-synthesis of hard real-time aper does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Concurrent hardware-software co-synthesis of hard real-time aper, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Concurrent hardware-software co-synthesis of hard real-time aper will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-1244770