Abstract
To improve the overall performance, many of the modern advanced digital signal processors (DSPs) are equipped with on-chip multiple data memory banks which can be accessed in parallel in one instruction. In order to effectively exploit this architectural feature, the compiler must partition program variables between the memory banks appropriately – two parallel memory accesses always must take place on different memory banks. There is some research work that addresses this issue, however, most of this has been proposed as a post-pass (machine dependent) optimization. We attempt to resolve this problem by applying an algorithm which operates on the high-level intermediate representation, independent of the target machine. The partitioning scheme is based on the concepts of the interference graph which is constructed utilizing the control flow, data flow, and alias information. Partitioning of the interference graph is modeled as a Max Cut problem. The variable partitioning algorithm has been designed as an optional optimization phase integrated in the C compiler for a digital signal processor. This paper describes our efforts. The experimental results demonstrate that our partitioning algorithm finds a fairly good assignment of variables to memory banks. For small kernels from the DSPstone benchmark suite the performance is improved from 10% to 20%, for FFT filters by about 10%.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Panis, C., Laure, G., Lazian, W., Krall, A., Grünbacher, H., Nurmi, J.: DSPxPlore – Design Space Exploration for a Configurable DSP Core. In: Proceedings of the GSPx, Dallas, Texas, USA (2003)
Leupers, R., Kotte, D.: Variable Partitioning for Dual Memory Bank DSPs. In: Proceedings of the IEEE International Conference on Acoustics, Speech, and Signal Processing (ASSP), vol. 2, pp. 1121–1124 (2001)
Powell, D.B., Lee, E.A., Newman, W.C.: Direct Synthesis of Optimized DSP Assembly Code from Signal Flow Block Diagrams. In: Proceedings of the IEEE International Conference on Acoustics, Speech, and Signal Processing (ASSP), vol. 5, pp. 553–556 (1992)
Saghir, M.A.R., Chow, P., Lee, C.G.: Automatic Data Partitioning for HLL DSP Compilers. In: Proceedings of the 6th International Conference on Signal Processing Applications and Technology, pp. I–866–871 (1995)
Saghir, M.A.R., Chow, P., Lee, C.G.: Exploiting Dual Data-Memory Banks inDigital Signal Processor. In: ACM SIGOPS Operating Systems Review, Proceedings of the 7th International Conference on Architectural Support for Programming Languages and Operating Systems, vol. 30(5), pp. 234–243 (1996)
Sudarsanam, A., Malik, S.: Memory Bank and Register Allocation in Software Synthesis for ASIPs. In: Proceedings of the IEEE/ACM International Conference on Computer Aided Design, pp. 388–392 (1995)
Sudarsanam, A., Malik, S.: Simultaneous Reference Allocation in Code Generation for Dual Data Memory Bank ASIPs. Journal of the ACM Transactions on Automation of Electronic Systems (TODAES) 5, 242–264 (2000)
Cho, J., Paek, Y., Whalley, D.: Efficient Register and Memory Assignment for Non-orthogonal Architectures via Graph Coloring and MST Algorithm. In: Proceedings of the International Conference on the LCTES and SCOPES, Berlin, Germany (2002)
Zhuang, X., Pande, S., Greenland, J.S.: A Framework for Parallelizing Load/Stores on Embedded Processors. In: Proceedings of the International Conference on Parallel Architectures and Compilation Techniques (PACT), Virginia (2002)
Zhuge, Q., Xiao, B., Sha, E.H.-M.: Variable Partitioning and Scheduling of Multiple Memory Architectures for DSP. In: Proceedings of the IEEE International Parallel and Distributed Processing Symposium (IPDPS) (2002)
Sahni, S., Gonzales, T.: P-complete Approximation Problems. Journal of the ACM 23, 555–565 (1976)
Goemans, M.X., Williamson, D.P.: 0.878-Approximation Algorithms for MAXCUT and MAX 2SAT. In: Proceedings of the 26th Annual ACM Symposium on Theory of Computing, pp. 422–431 (1994)
Goemans, M.X., Williamson, D.P.: Improved Approximation Algorithms for MAX CUT and Satisfiability Problems Using Semidefinite Programming. Journal of the ACM 42, 1115–1145 (1995)
Frieze, A., Jerrum, M.: Improved Approximation Algorithms for Max k-Cut and Max Bisection. Algorithmica 18, 61–77 (1997)
Hromkovic, J.: Algorithmics for Hard Problems. Springer, Berlin (2001)
Fujisawa, K., Kojima, M., Nakata, K., Yamashita, M.: SDPA (Semidefinite Programming Algorithm), vers. 4.10, Research Report on Mathematical and Computing Sciences, Tokyo Institute of Technology, Japan (1998)
Burer, S., Monteiro, R.D.C., Zhang, Y.: Rank-two Relaxation Heuristics for Max-Cut and Other Binary Quadratic Programs. SIAM Journal on Optimization 12, 503–521 (2001)
Burer, S., Monteiro, R.D.C., Zhang, Y.: CirCut vers. 1.0612, Fortran 90 Package for Finding Approximate Solutions of Certain Binary Quadratic Programs (2000)
Zivojnovic, V., Velarde, J.M., Schager, C., Meyr, H.: DSPstone – A DSP oriented Benchmarking Methodology. In: Proceedings of the 6th International Conference on Signal Processing Applications and Technology (1994)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Sipkova, V. (2003). Efficient Variable Allocation to Dual Memory Banks of DSPs. In: Krall, A. (eds) Software and Compilers for Embedded Systems. SCOPES 2003. Lecture Notes in Computer Science, vol 2826. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-39920-9_25
Download citation
DOI: https://doi.org/10.1007/978-3-540-39920-9_25
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-20145-8
Online ISBN: 978-3-540-39920-9
eBook Packages: Springer Book Archive