IJSER Home >> Journal >> IJSER
International Journal of Scientific and Engineering Research
ISSN Online 2229-5518
ISSN Print: 2229-5518 12    
Website: http://www.ijser.org
scirp IJSER >> Volume 2, Issue 12, December 2011
Frame Communication Module for Bin-Packing Algorithms for Distributed Embedded Systems
Full Text(PDF, 3000)  PP.  
Author(s)
Mr. Anand, Dr. S.Ravi Mrs.V.Kavitha and Dr.Uma Rajaram
KEYWORDS
Bin packing Algorithm, CAN, Embedded system, Interprocess communication, Local interconnection Network, Quality of service, Schedule ability analysis
ABSTRACT
Embedded real-time systems must satisfy not only logical functional requirements, but also para-functional properties such as timeliness, Quality of Service (QoS) and reliability. The proposed scheme describes an automated schedulability analysis, and generates glue code to integrate the final runtime executable for the system. Its extensive glue code generation capabilities include the ability to insert inter-processor communications code at arbitrary software boundaries. The objective of this deployment is to minimize hardware requirements while satisfying the timing constraints of the software. The classical approach to addressing this problem is to use bin-packing techniques. A bin-packing algorithm is proposed to exploit the capability of partitioning software modules into smaller pieces which exhibits that number of bins required can be reduced. In this paper, we investigate how to assign signals to periodic frames with the objective function to minimize the network bandwidth requirement while not violating specified deadlines. This problem is NP-hard, but can for most typical applications be solved efficiently by using simple heuristics. The effectiveness of our algorithm is demonstrated by applying it to signal sets derived from automotive applications for a CAN based system and for the newly developed, low cost and low speed, Local Interconnect Network (LIN). The results can be of great use in cost sensitive embedded systems such as car control systems, where the used hardware, communication networks and nodes (typically micro-controllers), have to be highly utilized to keep the production cost at a minimum level.
References
[1] Take F. Abdelzaher and Kang G. Shin. ‚Period-Based Load Partitioning and Assignment for Large Real-Time Applications‛, IEEE Transactions on Computers, 49, 2000.

[2] N.C. Audsley, A. Burns, M.F. Richardson, and A.J. Wellings. Hard Real- Time Scheduling, ‚The Deadline Monotonic Approach‛, In Proceedings of 8th IEEE Workshop on Real-Time Operating Systems and Software, 1991.

[3] Brenda S. Baker, ‚A new proof for the first-fit decreasing bin-packing algorithm‛, Journal of Algorithms, 6:49–70, 1985.

[4] Coffman, E.G., Jr., M.R. Garey, and D.S. Johnson, ‚Bin Packing with Divisible Item Sizes‛, Journal of Complexity, 3(4),406-428, December1987.

[5] Dionisio de Niz and Raj Rajkumar. Glue-code Generation, ‚Closing the Loophole in Model-based Development‛, In IEEE Real-time Systems and Application Simposium (RTAS) 2004 - MoDES, Toronto, CANADA, June 2004.

[6] Dionisio de Niz and Raj Rajkumar. Time Weaver, ‚A Software-Through- Models Framework for Embedded Real-Time Systems‛, In Proceedigs of ACM Language Compilers and Tools for Embedded Systems Symposium 2003, San Diego, CA, June 2003.

[7] D.S. Johnson. Near-Optimal Bin Packing Algorithms. PhD thesis, Massachusetts Institute of Technology, 1973.

[8] D.S. Johnson, A. Demers, D. Ullman, M.R. Garey, and R.L. Graham. ‚Worst-case performance bounds for simple one-dimensional packing algorithms‛, SIAM Journal of Computing, 3:299–325, 1974.

[9] Mark H. Klein, Thomas Ralya, Bill Pollak, and Ray Obenza.‛ A Practitioners’ Handbook for Real-Time Analysis: Guide to Rate Monotonic Analysis for Real-Time Systems‛, Kluwer Academic Publishers, 1993.

[10] C. L. Liu and J. Layland, ‚Scheduling alghorithms for multiprogramming in a hard real-time environment‛, Journal of the ACM, Vol. 20, No. 1, 1973.

[11] Nir Naaman and Raphael Rom, ‚ Packet Scheduling with Fragmentation‛, In Proceedings of the IEEE INFOCOM Symposium 2002, New York, NY, June 2002.

[12] Ken Tindell, Alan Burns, and Andy Wellings, ‚Allocating Hard Real- Time Tasks‛, An NP-Hard Problem Made Easy. Real-Time Systems, 4(2):145–65, 1992

[13]Tindell K., J. Clark, ‚Holistic Schedulability Analysis for Distributed Hard Real-time Systems‛. Technical Report YCS197, Real-Time Systems Research Group, Univ. of York, 1993.

[14] K. W. Tindell and A. Burns. ‚Guaranteed message latencies for distributed safety-critical hard real-time control networks‛,Technical Report YCS229, Dept. of Computer Science, University ofYork, June 1994.

[15] J Jonsson and J Vasell, ‚Evaluation and comparison of task allocation and scheduling methods for distributed real-time systems‛, In proceeding of Second IEEE International Conference on Engineering of Complex Computer Systems, 21-25 Oct. 1996.

[16] H. Jiandong and D. Ding-Zhu, ‚Resource management for continuous multimedia database applications‛., In proceedings of RTSS’94. 1994.

[17]Hongfeng Wang; Yanjie Chen, ‚A Hybrid Genetic algorithm for 3D Bin Packing Problem‛ 2010 IEEE Fifth International conference, ISBN:978-1-4244-6437-1, 23-26 Sept. 2010

Untitled Page