Email this article 
Open Access
Subscription or Fee Access
Optimization of Bank Switching Instructions In Microcontrollers Having Partitioned Memory Architectures
Abstract
This paper describes an optimization algorithm and its implementation, developed for a static machine code analyzer which helps to eliminate the redundant bank switching instructions in partitioned memory architectures. The Optimization algorithm rests on a relation matrix formed for the memory bank state transition corresponding to each bank selection instruction. Redundant data and program memory bank selection instructions in the intraprocedural sequence, loops and interprocedural routines in the applicationprogram are eliminated. Analysis is done at machine code levels, so no software or runtime overhead. This results in reduced code size as well as increased execution speed. No assertion or annotated assembly code is needed. This method scales well into large number of memory blocks as well as other architectures, once appropriate information isavailable. A prototype based on PIC 16F87X microcontrollers is described and the results obtained for a sample program is presented.
Keywords
References
B. Scholz, B. Burgstaller, and J. Xue, “Minimal placement of bank selection instructions for partitioned memory architectures,” ACM Transactions on Embedded Computing Systems (TECS), vol. 7, Issue 2,Feb. 2008.
Application notes, AN586, Macros for Page and Bank Switching,Microchip Technology Inc, http:// www.microchip.com., 1997.
R. Leupers, Code Optimization Techniques for embedded processors-Methods, Algorithms and Tools, Kluwer Academic Publishers, 2000.
Jean Labrosse et al., Embedded Software: Know It All, Elsevier Inc.,2008.
Mariamma Chacko and Poulose Jacob, "Validation of Embedded Software through Static Analysis of Machine Codes", in Proc. of IEEE International Advance Computing Conference, Patiala, India, Mar. 2009, pp. 488-493.
John Regehr and Alastair Reid, “HOIST: A System for Automatically Deriving Static Analyzers for Embedded Systems”, in Proc. of the 11th international conference on Architectural support for programming languages and operating systems, Boston, MA, USA, October 07-13,2004.
P. Cousot, R. Cousot, J. Feret, L. Mauborgne, A. Min´e, D. Monniaux,and X. Rival, “The Astr’ee Analyser”, In M. Sagiv, editor, Proc. 14th ESOP’2005, Edinburg, UK, volume 3444 of LNCS, Springer, Apr. 2-10,2005, pp. 21–30.
Sudheendra Hangal and Monica S. Lam, “Tracking Down Software Bugs Using Automatic Anomaly Detection”, International conference on software Engineering, May 2002, pp. 291-301.
Zhang X. and Guptha R., “Whole Execution Traces and Their Applications”, ACM Transactions on Architecture and Code Optimization, Vol. 2No. 3, pp 301-334, Sept. 2005.
X. Zhang, N. Gupta and R. Gupta, “Whole Execution Traces and their use in Debugging”, in The Compiler Design Handbook-Optimization and Machine code Generation”, 2nd ed., Y.N. Srikant and Priti Shankar, CRC Press, 2008.
J. Bergeron, M. Debbabi, J. Desharnais, M.M. Erhioui, Y. Lavoie, and N.Tawbi, “Static detection of malicious code in executable programs,”Int. J. of Req. Eng., 2001.
S. S. Muchnick, Advanced Compiler Design Implementation. Morgan Kaufman Publishers, San Francisco, CA, 1997.
G. Balakrishnan and T. Reps, “Analyzing memory accesses in x86 executables,” In Comp.Construct., Lec. Notes in Comp. Sci.,Springer-Verlag,. 2004, pp. 5–23.
C. Cifuentes and A. Fraboulet, “Intraprocedural static slicing of binary executables,” in Int.Conf. on Softw. Maint., 1997, pp.188–195.
A. Kiss, J. Judit, G. Lehotai, and G. Tibor, “Interprocedural Static Slicing of Binary Executables,” in Proc. of the third IEEE international workshop on Source Code Analysis and Manipulation, Sept. 2003, pp. 118-127.
C. Cifuentes, D.Simon, and A. Fraboulet, “Assembly to high-level language translation,” Int. Conf. on Softw. Maint., 1998, pp. 228–237.
M. Christodorescu and S.Jha, “Static analysis of executables to detect malicious patterns,” In USENI A. X Security Symposium, 2003.
G. Balakrishnan, et al., “Model Checking x86 Executables with CodeSurfer/x86 and WPDS++,” Conference on Computer Aided Verification (CAV, Scotland, UK, July 2005.
M. Musuvathi,, D. Park, A. Chou, D. Engler, and D. Dill, ‘CMC: A pragmatic approach to model checking real code’, in Op. Syst. Design and Impl., 2002.
J.Regehr, A. Reid, and K. Webb, “Eliminating Stack Overflow by Abstract Interpretation,” ACM Transactions on Embedded Computing Systems (TECS), vol. 4, No. 4, Nov. 2005.
Tim Wilmshurst, Designing Embedded Systems with PIC Microcontrollers-Principles and applications, Newnes, Elsevier, London, UK, 2007.
Data sheet, PIC16F87X, Microchip Technology Inc.., 1999. Available:http://www.microchip.com.
Data Sheet, PIC18F2455/2550/4455/4550, Microchip Technology Inc.,2004.
PICmicro mid-range MCU family reference manual, Microchip Technology Inc., 1997.
J. P. Tremblay and R. Manohar, Discrete Mathematical Structures with Applications to Computer Science, McGraw-Hill, Singapore, 1987.
Mariamma Chacko and Poulose Jacob, "Optimization of Bank Switching Instructions in Embedded Systems through Static Analysis of Machine Codes", in Proc. of IEEE International Advance Computing Conference,Patiala, India, March 2009, pp.548-552.
J. Sosnowski, “Detection of Control Flow Errors Using Signature and Checking Instructions,” in Pro. of the IEEE International Test Conference, 1988, pp. 81-88.
A.V. Aho and J.D. Ullman, Principles of Compiler Design, Addison-Wesley/Narosa, 1985.
M. A. Schuette and J. P.Shen, “Processor Control Flow Monitoring Using Signatured Instruction Streams,” IEEE Transactions on Computers, Vol.C-36, No. 3, March 1987.
T. Sridhar and S.M. Thatte, “Concurrent checking of program flow in VLSI processors,” in Proc. of the 12th Int. Test Conf., November 1982,pp. 191-199.
Refbacks
- There are currently no refbacks.
This work is licensed under a Creative Commons Attribution 3.0 License.