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

Article

DSP address optimization using evolutionary algorithms

Authors:

Sean Leventhal,

Neal K. Bambha,

Shuvra S. Bhattacharyya,

Gang QuAuthors Info & Claims

SCOPES '05: Proceedings of the 2005 workshop on Software and compilers for embedded systems

Pages 91 - 98

https://doi.org/10.1145/1140389.1140399

Published: 29 September 2005 Publication History

Abstract

Offset assignment has been studied as a highly effective approach to code optimization in modern digital signal processors (DSPs). In this paper, we propose two evolutionary algorithms to solve the general offset assignment problem with k address registers and an arbitrary auto-modify range. These algorithms differ from previous algorithms by having the capability of visiting the entire search space. We implement and analyze a variety of existing general offset assignment algorithms and test them on a set of standard benchmarks. The algorithms we propose can achieve a performance improvement of up to 31% over the best existing algorithm. We also achieve an average of 14% improvement over the union of recently proposed algorithms.

References

[1]

B. Wess and T. Zeitlhofer, "Optimum address pointer assignment for digital signal processors," in Proceedings of the ICASSP, 2004, pp. 121--124.]]

[2]

S. Atri, J. Ramanujam, and M. Kandemir, "Improving Offset Assignment for Embedded Processors", The 13th International Workshop on Languages and Compilers for Parallel Computing, pp. 158--172, Lecture Notes in Computer Science, Springer-Verlag, UK, 2000.]]

Digital Library

[3]

D. H. Bartley, "Optimizing Stack Frame Accesses for Processors with Restricted Addressing Modes", Software -Practice and Experience, vol. 22, no. 2, 1992.]]

Digital Library

[4]

S. Liao, S. Devadas, K. Keutzer, S. Tjiang, and A. Wang, "Storage Assignment to Decrease Code Size", ACM Transaction on Programming Languages and Systems, vol. 18, no. 3, pp. 235--253, May 1996.]]

Digital Library

[5]

R. Leupers and P. Marwedel, "Algorithms for Address Assignment in DPS Coder Generation." IEEE Conference on Computer-Aided Design, pp. 109--112, Nov 1996.]]

Digital Library

[6]

R. Leupers and F. David, "A Uniform Optimization Technique for Offset Assignment Problems", International Symposium on Systems Synthesis, pp. 3--8, 1998.]]

Digital Library

[7]

R. Leupers, "Offset Assignment Showdown: Evaluation of DSP Address Code Optimization Algorithms", The 12th International Conference on Compiler Construction, LNCS 2622, Lecture Notes on Computer Science, Springer-Verlag, Poland, Apr. 2003.]]

[8]

B. Wess and M. Gotschlich, "Optimal DSP memory layout generation as a quadratic assignment problem", IEEE International Symposium on Circuit And Systems, vol. 3, pp. 1712--1715, Hong Kong, June, 1997.]]

[9]

Xiaotong Zhuang, ChokSheak Lau, and Santosh Pande, "Storage Assignment Optimizations through Variable Coalescence for Embedded Processors", Proceedings of the 2003 ACM SIGPLAN conference on Language, compiler, and tool for embedded systems, pp. 220--231, 2003.]]

Digital Library

[10]

B. Wess, "Minimization of Data Access Computation Overhead in DSP Programs", Design Automation for Embedded Systems, vol. 4, pp. 167--185, 1999.]]

Digital Library

[11]

S. Udayanarayanan and C. Chakrabarti, "Address Code Generation for Digital Signal Processors", IEEE Design Automation Conference, pp. 232--242, Jun. 2001.]]

Digital Library

[12]

Analog Devices, Inc. ADSP-2100 Family User's Manual, Sep. 1995.]]

Digital Library

[13]

Motorola, Inc. DSP56000 Digital Signal Processor Family Manual, 1992.]]

[14]

Texas Instruments, Inc. TMS320C5x User's Guide, 1997.]]

[15]

http://www.address-code-optimization.org.]]

[16]

N. K. Bambha, S. S. Bhattacharyya, J. Teich, and E. Zitzler, "Systematic integration of parameterized local search into evolutionary algorithms," IEEE Transactions on Evolutionary Algorithms, vol. 8, no.2, pp. 137--155, April 2004.]]

Digital Library

[17]

D. Whitley, "The GENITOR Algorithm and Selective Pressure: Why Rank-Based Allocation of Reproductive Trials is Best," Proceedings of the 3rd International Conference on Genetic Algorithms, D. Scheffer, ed., pp 116--121. Morgan Kaufmann, 1989.]]

Digital Library

[18]

R. Leupers, Code Optimization Techniques for Embedded Processors --- Methods, Algorithms, Tools. Kluwer Academic Press, 2000.]]

Digital Library

Cited By

Wang YJia ZChen RWang MLiu DShao Z(2014)Loop scheduling with memory access reduction subject to register constraints for DSP applicationsSoftware—Practice & Experience10.1002/spe.218644:8(999-1026)Online publication date: 1-Aug-2014
https://dl.acm.org/doi/10.1002/spe.2186
Meng Wang Zili Shao Jingling Xue (2011)On Reducing Hidden Redundant Memory Accesses for DSP ApplicationsIEEE Transactions on Very Large Scale Integration (VLSI) Systems10.1109/TVLSI.2010.204396319:6(997-1010)Online publication date: 1-Jun-2011
https://dl.acm.org/doi/10.1109/TVLSI.2010.2043963
White DArcuri AClark J(2011)Evolutionary Improvement of ProgramsIEEE Transactions on Evolutionary Computation10.1109/TEVC.2010.208366915:4(515-538)Online publication date: 1-Aug-2011
https://dl.acm.org/doi/10.1109/TEVC.2010.2083669
Show More Cited By

DSP address optimization using evolutionary algorithms
1. Computing methodologies
  1. Artificial intelligence
    1. Search methodologies

Recommendations

Supply chain optimisation using evolutionary algorithms

This paper describes the application of Evolutionary Algorithms (EAs) to the optimisation of a simplified supply chain in an integrated production-inventory-distribution system. The performance of four EAs (Genetic Algorithm (GA), Evolutionary ...
Using holey fitness landscapes to counteract premature convergence in evolutionary algorithms
GECCO '08: Proceedings of the 10th annual conference companion on Genetic and evolutionary computation

Premature convergence is a persisting problem in evolutionary optimisation, in particular - genetic algorithms. While a number of methods exist to approach this issue, they usually require problem specific calibration or only partially resolve the issue,...
Evolving evolutionary algorithms using evolutionary algorithms
GECCO '07: Proceedings of the 9th annual conference companion on Genetic and evolutionary computation

A new model for automatic generation of Evolutionary Algorithms (EAs) by evolutionary means is proposed in this paper. The model is based on a simple Genetic Algorithm (GA). Every GA chromosome encodes an EA, which is used for solving a particular ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SCOPES '05: Proceedings of the 2005 workshop on Software and compilers for embedded systems

September 2005

132 pages

ISBN:1595932070

DOI:10.1145/1140389

Conference Chairs:
Krishna Kavi
University of North Texas
,
Ron Cytron
Washington University, St. Louis

Copyright © 2005 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]

Sponsors

EDAA: European Design Automation Association
ARTEST2
SIGMICRO: ACM Special Interest Group on Microarchitectural Research and Processing
The National Science Foundation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 29 September 2005

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Acceptance Rates

Overall Acceptance Rate 38 of 79 submissions, 48%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
146
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)0

Reflects downloads up to 19 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Wang YJia ZChen RWang MLiu DShao Z(2014)Loop scheduling with memory access reduction subject to register constraints for DSP applicationsSoftware—Practice & Experience10.1002/spe.218644:8(999-1026)Online publication date: 1-Aug-2014
https://dl.acm.org/doi/10.1002/spe.2186
Meng Wang Zili Shao Jingling Xue (2011)On Reducing Hidden Redundant Memory Accesses for DSP ApplicationsIEEE Transactions on Very Large Scale Integration (VLSI) Systems10.1109/TVLSI.2010.204396319:6(997-1010)Online publication date: 1-Jun-2011
https://dl.acm.org/doi/10.1109/TVLSI.2010.2043963
White DArcuri AClark J(2011)Evolutionary Improvement of ProgramsIEEE Transactions on Evolutionary Computation10.1109/TEVC.2010.208366915:4(515-538)Online publication date: 1-Aug-2011
https://dl.acm.org/doi/10.1109/TEVC.2010.2083669
Wang MLiu DWang YShao Z(2009)Loop scheduling with memory access reduction under register constraints for DSP applications2009 IEEE Workshop on Signal Processing Systems10.1109/SIPS.2009.5336239(139-144)Online publication date: Oct-2009
https://doi.org/10.1109/SIPS.2009.5336239

View Options

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 Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents