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

research-article

ILP optimal scheduling for multi-module memory

Authors:

Edwin H.-M. ShaAuthors Info & Claims

CODES+ISSS '09: Proceedings of the 7th IEEE/ACM international conference on Hardware/software codesign and system synthesis

Pages 277 - 286

https://doi.org/10.1145/1629435.1629473

Published: 11 October 2009 Publication History

Abstract

In high-end digital signal processing (DSP) system, multi-module memory provides high memory bandwidth and low power operating mode for energy savings. However, making full use of these architectural features is a challenging problem for code optimization. In this paper, we propose an integer linear programming model to optimize the performance and energy consumption of multi-module memories by solving variable assignment, instruction scheduling and operating mode setting problems simultaneously. The combined effect of performance and energy saving requirements also has been considered. We develop two optimization techniques to improve the computation efficiency of our ILP model. The experimental results show that the optimal performance and energy solution can be achieved within a reasonable amount of time.

References

[1]

. DSP56301 24-bit Digital Signal Processor datasheet, Motorola Inc., Phoenix, AZ, Oct. 2006.

[2]

. H. Koc, O. Ozturk, M. Kandemir, S. H. K. Narayanan, and E. Ercanli, "Minimizing energy consumption of banked memories using data recomputation," in ISLPED '06 Proc., pp. 358--362, 2006.

Digital Library

[3]

. L. Zhang, M. Qiu, W. Tseng and E. H.-M. Sha, "Variable partitioning and scheduling for MPSOC with virtually shared scratch pad memory", Journal of Signal Processing Systems, pp. 1 -- 19, 2009.

Digital Library

[4]

. M. Qiu and E. H.-M. Sha, "Cost minimization while satisfying hard/soft timing constraints for heterogeneous embedded systems", ACM Transactions on Design Automation of Electronic Systems (TODAES), Vol. 14, No. 2, pp. 25:01 -- 25:30, 2009.

Digital Library

[5]

. R. Leupers and D. Kotte, "Variable partitioning for dual memory bank DSPs," Proc. IEEE Int"l Conf. Acoustics Speech and Signal Processing, pp. 1121--1124, May 2001.

Digital Library

[6]

. Q. Zhuge, E. Sha, B. Xiao, and C. Chantrapornchai, Efficient variable partitioning and scheduling for dsp processors with multiple memory modules," IEEE Trans. on Signal Processing., vol. 52, no. 4, pp. 1090--1099, Apr. 2004.

Digital Library

[7]

. A. Sudarsanam and S. Malik, "Simultaneous reference allocation in code generation for dual data memory bank asips," ACM Transactions on Design Automation of Electronic Systems (TODAES), vol. 5, no. 2, pp. 242--264, 2000.

Digital Library

[8]

. V. DelaLuz, M. Kandemir, and I. Kolcu, "Automatic data migration for reducing energy consumption in multi-bank memory systems," in DAC '02 Proc., pp. 213--218, 2002.

Digital Library

[9]

. V. Delaluz, M. Kandemir, N. Vijaykrishnan, and M. J. Irwin, Energyoriented compiler optimizations for partitioned memory architectures," in CASES, Proc., pp. 138--147, 2000.

Digital Library

[10]

.Z. Wang and X. S. Hu, "Energy-aware variable partitioning and instruction scheduling for multibank memory architectures," ACM Trans. Des. Autom. Electron. Syst., vol. 10, no. 2, pp. 369--388, 2005.

Digital Library

[11]

.Z. Wang, E. H.-M. Sha and Y. Wang, "partitioning and scheduling DSP applications with maximal memory access hiding", Eurasip Journal on Applied Signal Processing (EJASP), No. 9, pp. 926--935. 2002.

Digital Library

[12]

.M. Qiu, M. Guo, M. Liu, C. Xue, L. Yang, E. H.-M. Sha, Loop scheduling and bank type assignment for heterogeneous multi-bank memory", Journal of Parallel and Distributed Computing, In Press, Available online Mar. 2009.

Digital Library

[13]

.C-T Hwang, J-H Lee, Y-C Hsu, "A formal approach to the scheduling problem in high level synthesis", Proc. IEEE Transactions On Computer-Aided Design, Vol. 10, No. 4, pp. 464--475, 1991.

Digital Library

[14]

.D. Kastner and S. Winkel, "ILP-based instruction scheduling for IA-64," SIGPLAN Notices, vol. 36, no. 8, pp. 145--154, 2001.

Digital Library

[15]

.K. Wilken, J. Liu, and M. Heffernan, "Optimal instruction scheduling using integer programming," in PLDI, Proc., pp. 121--133, 2000.

Digital Library

[16]

."36mb sync. pipelined burst SRAM specification," Samsung Inc., 2000.

[17]

.G. D. Micheli, "Synthesis and optimization of digital circuits," McGraw--Hill, Inc., pp. 198--202, 1997.

[18]

.N. Mladenovic and P. Hansen, "Variable neighborhood search," Comput. Oper. Res., vol. 24, no. 11, pp. 1097--1100, 1997.

Digital Library

[19]

.S. Y. Kung, T. Kailath, and H. J. Whitehouse, "VLSI and modern signal processing," Prentice Hall, pp. 342--347,1984.

Digital Library

[20]

."Dspstone, http://www.iss.rwthaachen.de/Projekte/Tools/DSPSTONE/dspstone.html.

[21]

."Trimaran," http://www.trimaran.org.

[22]

."CPLEX," http://www.ilog.com.

Cited By

Chen QZhang HYan KGuo FYang HBai YHou L(2023)DCE: A High-Performance, Scalable, Enterprise-Level Cloud Native Operating System2023 IEEE 8th International Conference on Smart Cloud (SmartCloud)10.1109/SmartCloud58862.2023.00044(208-213)Online publication date: 16-Sep-2023
https://doi.org/10.1109/SmartCloud58862.2023.00044
Gao XGu HLiu FHu W(2023)Offloading Algorithm for Edge Computing Tasks Based on Energy Optimization2023 IEEE 8th International Conference on Smart Cloud (SmartCloud)10.1109/SmartCloud58862.2023.00016(45-50)Online publication date: 16-Sep-2023
https://doi.org/10.1109/SmartCloud58862.2023.00016
Huang CFu QWang CLi Z(2023)Joint Task Offloading and Scheduling Algorithm in Vehicular Edge Computing Networks2023 IEEE 10th International Conference on Cyber Security and Cloud Computing (CSCloud)/2023 IEEE 9th International Conference on Edge Computing and Scalable Cloud (EdgeCom)10.1109/CSCloud-EdgeCom58631.2023.00061(318-323)Online publication date: Jul-2023
https://doi.org/10.1109/CSCloud-EdgeCom58631.2023.00061
Show More Cited By

Index Terms

ILP optimal scheduling for multi-module memory
1. Computer systems organization
  1. Embedded and cyber-physical systems
  2. Real-time systems

Recommendations

Variable assignment and instruction scheduling for processor with multi-module memory

Multi-module memory has been employed in high-end digital signal processing system (DSP). It provides high memory bandwidth and low power operating mode for energy savings. However, making full use of these architectural features is a challenging ...
Instruction Scheduling for Low Power

Reducing energy consumption has become an important issue in designing hardware and software systems in recent years. Although low power hardware components are critical for reducing energy consumption, the switching activity, which is the main source ...
A Heuristic Ceiling Point Algorithm for General Integer Linear Programming

This paper first examines the role of ceiling points in solving a pure, general integer linear programming problem P. Several kinds of ceiling points are defined and analyzed and one kind called "feasible 1-ceiling points" proves to be of special ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

CODES+ISSS '09: Proceedings of the 7th IEEE/ACM international conference on Hardware/software codesign and system synthesis

October 2009

498 pages

ISBN:9781605586281

DOI:10.1145/1629435

Program Chairs:
Wolfgang Rosenstiel
University of Tübingen, Germany
,
Kazutoshi Wakabayashi
NEC, Japan

Copyright © 2009 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

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 11 October 2009

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

ESWeek '09

Sponsor:

ESWeek '09: Fifth Embedded Systems Week

October 11 - 16, 2009

Grenoble, France

Acceptance Rates

Overall Acceptance Rate 280 of 864 submissions, 32%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

9
Total Citations
View Citations
231
Total Downloads

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

Reflects downloads up to 21 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Chen QZhang HYan KGuo FYang HBai YHou L(2023)DCE: A High-Performance, Scalable, Enterprise-Level Cloud Native Operating System2023 IEEE 8th International Conference on Smart Cloud (SmartCloud)10.1109/SmartCloud58862.2023.00044(208-213)Online publication date: 16-Sep-2023
https://doi.org/10.1109/SmartCloud58862.2023.00044
Gao XGu HLiu FHu W(2023)Offloading Algorithm for Edge Computing Tasks Based on Energy Optimization2023 IEEE 8th International Conference on Smart Cloud (SmartCloud)10.1109/SmartCloud58862.2023.00016(45-50)Online publication date: 16-Sep-2023
https://doi.org/10.1109/SmartCloud58862.2023.00016
Huang CFu QWang CLi Z(2023)Joint Task Offloading and Scheduling Algorithm in Vehicular Edge Computing Networks2023 IEEE 10th International Conference on Cyber Security and Cloud Computing (CSCloud)/2023 IEEE 9th International Conference on Edge Computing and Scalable Cloud (EdgeCom)10.1109/CSCloud-EdgeCom58631.2023.00061(318-323)Online publication date: Jul-2023
https://doi.org/10.1109/CSCloud-EdgeCom58631.2023.00061
Li ZZhang SXiong NLiang W(2023)Achieving Efficient and Secure Task Allocation Scheme in Mobile Crowd Sensing2023 IEEE 10th International Conference on Cyber Security and Cloud Computing (CSCloud)/2023 IEEE 9th International Conference on Edge Computing and Scalable Cloud (EdgeCom)10.1109/CSCloud-EdgeCom58631.2023.00022(78-84)Online publication date: Jul-2023
https://doi.org/10.1109/CSCloud-EdgeCom58631.2023.00022
Kunqi ZChunyan TXiaokang CHao W(2023)An Individual-differences-based Method for Discovering Viewpoints on Interactive Behavior2023 IEEE 9th Intl Conference on Big Data Security on Cloud (BigDataSecurity), IEEE Intl Conference on High Performance and Smart Computing, (HPSC) and IEEE Intl Conference on Intelligent Data and Security (IDS)10.1109/BigDataSecurity-HPSC-IDS58521.2023.00036(153-162)Online publication date: May-2023
https://doi.org/10.1109/BigDataSecurity-HPSC-IDS58521.2023.00036
Shouzhen Gu Qingfeng Zhuge Juan Yi Jingtong Hu Sha E(2015)Optimizing Task and Data Assignment on Multi-Core Systems with Multi-Port SPMsIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2014.235619426:9(2549-2560)Online publication date: 1-Sep-2015
https://dl.acm.org/doi/10.1109/TPDS.2014.2356194
Gu SZhuge QHu JYi JSha E(2013)Efficient task assignment and scheduling for MPSoC DSPS with VS-SPM considering concurrent accesses through data allocation2013 IEEE International Conference on Acoustics, Speech and Signal Processing10.1109/ICASSP.2013.6638129(2615-2619)Online publication date: May-2013
https://doi.org/10.1109/ICASSP.2013.6638129
Li JZhang ZQiu MZhang PQuan GZhu Y(2012)Optimizing Scheduling in Embedded CMP Systems with Phase Change MemoryProceedings of the 2012 IEEE 18th International Conference on Parallel and Distributed Systems10.1109/ICPADS.2012.78(532-539)Online publication date: 17-Dec-2012
https://dl.acm.org/doi/10.1109/ICPADS.2012.78
Qiu MWu GXue CHu JTseng WSha E(2009)Energy Minimization and Latency Hiding for Heterogeneous Parallel MemoryProceedings of the 2009 15th International Conference on Parallel and Distributed Systems10.1109/ICPADS.2009.132(503-510)Online publication date: 8-Dec-2009
https://dl.acm.org/doi/10.1109/ICPADS.2009.132

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