More Web Proxy on the site http://driver.im/

article

Free access

Simultaneous reference allocation in code generation for dual data memory bank ASIPs

Authors:

Ashok Sudarsanam,

Sharad MalikAuthors Info & Claims

ACM Transactions on Design Automation of Electronic Systems (TODAES), Volume 5, Issue 2

Pages 242 - 264

https://doi.org/10.1145/335043.335047

Published: 01 April 2000 Publication History

Abstract

We address the problem of code generation for DSP systems on a chip. In such systems, the amount of silicon devoted of program ROM is limited, so application software must be sufficiently dense. Additionally, the software must be written so as to meet various high-performance constraints, which may include hard real-time constraints. Unfortunately, current compiler technology is unable to generate high-quality code for DSPs, whose architectures are highly irregular. Thus, designers often resort to programming application software in assembly—a time-consuming task. In this paper, we focus on providing support for architectural feature of DSPs that makes code generation difficult, namely multiple data memory banks. This feature increases memory bandwith by permitting multiple data memory accesses to occur in parallel when the referenced variables belong to different data memory banks and the registers involved conform to a strict set of conditions. We present an algorithm that attempst to maximize the benefit of this architectural feature. While previous approaches have decoupled the phases of register allocation and memory bank assignment, thereby compromising code quality, our algorithm performs these two phases simultaneously. Experimental results demonstrate that our algorithm not only generates high-quality compiled code, but also improves the quality of completely-referenced code.

References

[1]

AHO, A., GANAPATHI, M., AND TJIANG, S. W. K. 1989. Code generation using tree matching and dynamic programming. ACM Trans. Program. Lang. Syst. 11, 4 (Oct. 1989), 491-516.

Digital Library

[2]

AHO, A., SETHI, R., AND ULLMAN, J. 1986. Compilers: Principles, Techniques, and Tools. Addison-Wesley, Reading, MA.

Digital Library

[3]

ANDERSON, J. M. AND LAM, M. S. 1993. Global optimizations for parallelism and locality on scalable parallel machines. SIGPLAN Not. 28, 6 (June 1993), 112-125.

Digital Library

[4]

ARAUJO, G. AND MALIK, S. 1995. Optimal code generation for embedded memory nonhomogeneous register architectures. In Proceedings of the Eighth International Symposium on System Synthesis (Cannes, France, Sept. 13-15, 1995), P. G. Paulin and F. Mavaddat, Eds. ACM Press, New York, NY, 36-41.

Digital Library

[5]

ARAUJO, G., MALIK, S., AND LEE, M. T.-C. 1996. Using register-transfer paths in code generation for heterogeneous memory-register architectures. In Proceedings of the 33rd Annual Conference on Design Automation (DAC '96, Las Vegas, NV, June 3-7), T. P. Pennino and E. J. Yoffa, Eds. ACM Press, New York, NY, 591-596.

Digital Library

[6]

ARAUJO, G., SUDARSANAM, A., AND MALIK, S. 1996. Instruction set design and optimization techniques for address computation in DSP architectures. In Proceedings of the Ninth International Symposium on System Synthesis,

Digital Library

[7]

CHAITIN, G., AUSLANDER, M., CHANDRA, A., COCKE, J., HOPKINS, M., AND MARKSTEIN, P. 1981. Register allocation via coloring. Comput. Lang. 6, 1, 47-57.

[8]

FRASER, C. W., HANSON, D. R., AND PROEBSTING, T.A. 1992. Engineering a simple, efficient code-generator generator. ACM Lett. Program. Lang. Syst. 1, 3 (Sept. 1992), 213-226.

Digital Library

[9]

GAREY, M. AND JOHNSON, D. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York, NY.

Digital Library

[10]

KnFKA, S. 1990. An assembly source level global compacter for digital signal processors. In Proceedings of the International on Acoustics, Speech, and Signal Processing,

[11]

KIRKPATRICK, S., GELATT, C. D., JR., AND VECCHI, M. P. 1983. Optimization by simulated annealing. Science 220, 4598 (May), 671-680.

[12]

LANDSKOV, D., DAVIDSON, S., SHRIVER, B., AND MALLETT, P. 1980. Local microcode compaction techniques. ACM Comput. Surv. 12, 3 (Sept.).

Digital Library

[13]

LANNEER, D., PRAET, J., SCHOOFS, K., GEURTS, W., THOEN, F., GOOSSENS, G., AND KIFLI, A. 1995. Chess: Retargetable code generation for embedded DSP rocessors. In Code Generation for Embedded Processors, P. Marwedel and J. Goosens, Eds. Kluwer Academic Publishers, Hingham, MA.

[14]

LEUPERS, R. AND MARWEDEL, P. 1996. Instruction selection for embedded DSPs with complex instructions. In Proceedings of the Conference on European Design Automation (EURO-DAC '96, Geneva, Switzerland, Sept. 16\), G. Symonds and W. Nebel, Eds. IEEE Computer Society Press, Los Alamitos, CA, 200-205.

Digital Library

[15]

LEUPERS, R., SCHENK, W., AND MARWEDEL, P. 1994. Retargetable assembly code generation by bootstrapping. In Proceedings of the Seventh International Symposium on High-Level Synthesis (ISSS '94, Niagara-on-the-Lake, Ont., Canada, May 18-20), P. G. Paulin, Ed. IEEE Computer Society Press, Los Alamitos, CA, 88-93.

Digital Library

[16]

LI, J. AND CHEN, M. 1991. Compiling communication-efficient programs for massively parallel machines. IEEE Trans. Parallel Distrib. Syst. 2, 3 (July), 361-376.

Digital Library

[17]

LIAO, S., DEVADAS, S., KEUTZER, K., AND TJIANG, S. 1995. Instruction selection using binate covering for code size optimization. In Proceedings of the 1995 IEEE/ACM International Conference on Computer-Aided Design (ICCAD-95, San Jose, CA, Nov. 5-9), R. Rudell, Ed. IEEE Computer Society Press, Los Alamitos, CA, 393-399.

Digital Library

[18]

LIAO, S., DEVADAS, S., KEUTZER, K., TJIANG, S., AND WANG, A. 1995. Storage assignment to decrease code size. In Proceedings of the Conference on Programming Language Design and Implementation (SIGPLAN '95, La Jolla, CA, June 18-21), D. W. Wall, Ed. ACM Press, New York, NY, 186-195.

Digital Library

[19]

LIAO, S., DEVADAS, S., KEUTZER, K., TJIANG, S., WANG, A., ARAUJO, G., SUDARSANAM, A., MALIK, S., ZIVOJNOVIC, V., AND MEYR, H. 1996. Code generation and optimization techniques for embedded digital signal processors. In Hardware/Software Co-Design, G. D. Micheli and M. Sami, Eds. Kluwer Academic Publishers, Hingham, MA, 165-186.

[20]

MOTOROLA 1990. DSP56000/DSP56001 Digital Signal Processor User's Manual. Motorola Inc., Phoenix, AZ.

[21]

PAULIN, P. G., LIEM, C., MAY, T. C., AND SUTARWALA, S. 1994. CodeSyn: A retargetable code synthesis system (abstract). In Proceedings of the Seventh International Symposium on High-Level Synthesis (ISSS '94, Niagara-on-the-Lake, Ont., Canada, May 18-20), P. G. Paulin, Ed. IEEE Computer Society Press, Los Alamitos, CA, 94.

Digital Library

[22]

POWELL, D., LEE, E., AND NEWMAN, W. 1992. Direct synthesis of optimized DSP assembly code from signal flow block diagrams. In Proceedings of the International Conference on Acoustics, Speech, and Signal Processing 5, 553-556.

[23]

SAGHIR, M. A. R., CHOW, P., AND LEE, C. G. 1996. Exploiting dual data-memory banks in digital signal processors. ACM SIGOPS Oper. Syst. Rev. 30, 5, 234-243.

Digital Library

[24]

SUDARSANAM, A. AND MALIK, S. 1995. Memory bank and register allocation in software synthesis for ASIPs. In Proceedings of the 1995 IEEE/ACM International Conference on Computer-Aided Design (ICCAD-95, San Jose, CA, Nov. 5-9), R. Rudell, Ed. IEEE Computer Society Press, Los Alamitos, CA, 388-392.

Digital Library

[25]

TEXAS-INSTRUMENTS 1993. TMS320C2x User's Guide. Revision C. Texas Instruments, Austin, TX.

[26]

TESS, B. 1991. Automatic code generation for integrated digital signal processors. In Proceedings of the 1991 IEEE International Symposium on Circuits and Systems (Singapore, June 11-14), 33-36.

[27]

TESS, B. 1992. Automatic instruction code generation based on trellis diagrams. In Proceedings of the International Conference on Circuits and Systems, 645-648.

[28]

ZIVOJNOVIC, V., VELARDE, J. M., AND SCHL GER, C. 1994. DSPstone: A DSP-oriented benchmarking methodology. In Proceedings of the Fifth International Conference on Signal Processing Applications and Technology (Oct.).

Cited By

Zhang LQiu MSha EZhuge Q(2011)Variable assignment and instruction scheduling for processor with multi-module memoryMicroprocessors & Microsystems10.1016/j.micpro.2010.12.00235:3(308-317)Online publication date: 1-May-2011
https://dl.acm.org/doi/10.1016/j.micpro.2010.12.002
Srikant YAnanda Vardhan K(2009)Energy-Aware Compiler OptimizationsThe Compiler Design Handbook10.1201/9781420043839.ch7(7-1-7-36)Online publication date: 7-Dec-2009
https://doi.org/10.1201/9781420043839.ch7
Krishna Nandivada V(2009)Advances in Register Allocation TechniquesThe Compiler Design Handbook10.1201/9781420043839.ch21(21-1-21-27)Online publication date: 7-Dec-2009
https://doi.org/10.1201/9781420043839.ch21
Show More Cited By

Index Terms

Simultaneous reference allocation in code generation for dual data memory bank ASIPs
1. Software and its engineering
  1. Software notations and tools
    1. Compilers
      1. Source code generation

Recommendations

Register allocation for write activity minimization on non-volatile main memory for embedded systems

Non-volatile memories are good candidates for DRAM replacement as main memory in embedded systems and they have many desirable characteristics. Nevertheless, the disadvantages of non-volatile memory co-exist with its advantages. First, the lifetime of ...
Write-once-memory-code phase change memory
DATE '14: Proceedings of the conference on Design, Automation & Test in Europe

This paper describes a write-once-memory-code phase change memory (WOM-code PCM) architecture for next-generation non-volatile memory applications. Specifically, we address the long latency of the write operation in PCM --- attributed to PCM SET --- by ...
Fast, frequency-based, integrated register allocation and instruction scheduling

Instruction scheduling and register allocation are two of the most important optimization phases in modern compilers as they have a significant impact on the quality of the generated code. Unfortunately, the objectives of these two optimizations are in ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Design Automation of Electronic Systems

ACM Transactions on Design Automation of Electronic Systems Volume 5, Issue 2

April 2000

150 pages

ISSN:1084-4309

EISSN:1557-7309

DOI:10.1145/335043

Editor:
Mary Jane Irwin
Pennsylvania State Univ. University Park, PA

Issue’s Table of Contents

Copyright © 2000 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Journal Family

ACM Journals for the Design of Smart and Connected Systems

Publication History

Published: 01 April 2000

Published in TODAES Volume 5, Issue 2

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

57
Total Citations
View Citations
531
Total Downloads

Downloads (Last 12 months)58
Downloads (Last 6 weeks)3

Reflects downloads up to 17 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Zhang LQiu MSha EZhuge Q(2011)Variable assignment and instruction scheduling for processor with multi-module memoryMicroprocessors & Microsystems10.1016/j.micpro.2010.12.00235:3(308-317)Online publication date: 1-May-2011
https://dl.acm.org/doi/10.1016/j.micpro.2010.12.002
Srikant YAnanda Vardhan K(2009)Energy-Aware Compiler OptimizationsThe Compiler Design Handbook10.1201/9781420043839.ch7(7-1-7-36)Online publication date: 7-Dec-2009
https://doi.org/10.1201/9781420043839.ch7
Krishna Nandivada V(2009)Advances in Register Allocation TechniquesThe Compiler Design Handbook10.1201/9781420043839.ch21(21-1-21-27)Online publication date: 7-Dec-2009
https://doi.org/10.1201/9781420043839.ch21
Qiu MZhang LSha ERosenstiel WWakabayashi K(2009)ILP optimal scheduling for multi-module memoryProceedings of the 7th IEEE/ACM international conference on Hardware/software codesign and system synthesis10.1145/1629435.1629473(277-286)Online publication date: 11-Oct-2009
https://dl.acm.org/doi/10.1145/1629435.1629473
Qiu MLiu MHu FLiu SWang L(2009)Energy Aware Loop Scheduling for High Performance Multi-Module MemoryProceedings of the 2009 Sixth IFIP International Conference on Network and Parallel Computing10.1109/NPC.2009.13(16-22)Online publication date: 19-Oct-2009
https://dl.acm.org/doi/10.1109/NPC.2009.13
Qiu MGuo MLiu MXue CYang LSha E(2009)Loop scheduling and bank type assignment for heterogeneous multi-bank memoryJournal of Parallel and Distributed Computing10.1016/j.jpdc.2009.02.00569:6(546-558)Online publication date: 1-Jun-2009
https://dl.acm.org/doi/10.1016/j.jpdc.2009.02.005
Ozturk OKandemir M(2008)ILP-Based energy minimization techniques for banked memoriesACM Transactions on Design Automation of Electronic Systems10.1145/1367045.136705913:3(1-40)Online publication date: 25-Jul-2008
https://dl.acm.org/doi/10.1145/1367045.1367059
Meikang Qiu Jiande Wu Chun Jason Xue Jingtong Aaron Hu Wei-Che Tseng Sha E(2008)Loop scheduling and assignment to minimize energy while hiding latency for heterogeneous multi-bank memory2008 International Conference on Field Programmable Logic and Applications10.1109/FPL.2008.4629983(459-462)Online publication date: Sep-2008
https://doi.org/10.1109/FPL.2008.4629983
Lee YChen C(2007)An effective and efficient code generation algorithm for uniform loops on non-orthogonal DSP architectureJournal of Systems and Software10.1016/j.jss.2006.06.00280:3(410-428)Online publication date: 1-Mar-2007
https://dl.acm.org/doi/10.1016/j.jss.2006.06.002
Lee YChen C(2007)An Efficient Code Generation Algorithm for Non-orthogonal DSP ArchitectureJournal of VLSI Signal Processing Systems10.1007/s11265-007-0053-x47:3(281-296)Online publication date: 1-Jun-2007
https://dl.acm.org/doi/10.1007/s11265-007-0053-x
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Media

Figures

Other

Tables

View Issue’s Table of Contents