Article

Optimal memoryless encoding for low power off-chip data buses

Authors:

Yeow Meng Chee,

Charles J. Colbourn,

Alan C. H. LingAuthors Info & Claims

ICCAD '06: Proceedings of the 2006 IEEE/ACM international conference on Computer-aided design

Pages 369 - 374

https://doi.org/10.1145/1233501.1233575

Published: 05 November 2006 Publication History

Abstract

Off-chip buses account for a significant portion of the total system power consumed in embedded systems. Bus encoding schemes have been proposed to minimize power dissipation, but none has been demonstrated to be optimal with respect to any measure. In this paper, we give the first provably optimal and explicit (polynomial-time constructible) families of memoryless codes for minimizing bit transitions in off-chip buses. Our results imply that having access to a clock does not make a memoryless encoding scheme that minimizes bit transitions more powerful.

References

[1]

R. Ahlswede and G. O. H. Katona. Contributions to the geometry of Hamming spaces. Discrete Math., 17:1--22, 1977.

[2]

R. Ahlswede and L. H. Khachatrian. The complete intersection theorem for systems of finite sets. European J. Combin., 18(2):125--136, 1997.

Digital Library

[3]

L. Benini, G. de Micheli, E. Macii, D. Sciuto, and C. Silvano. Asymptotic zero-transition activity encoding for address busses in low-power microprocessor-based systems. In GLSVLSI '97: Proceedings of the 7th Great Lakes Symposium on VLSI, pages 77--82. IEEE Computer Society, 1997.

Digital Library

[4]

F. Catthoor, S. Wuytack, E. De Greef, F. Balasa, L. Nachtergaele, and A. Vandecappelle. Custom Memory Management Methodology -- Exploration of Memory Organization for Embedded Multimedia System Design. Kluwer Acad. Publ., Boston, 1998.

Digital Library

[5]

W.-C. Cheng and M. Pedram. Memory bus encoding for low power: A tutorial. In ISQED 2001: Proceedings of the 2nd International Symposium on Quality of Electronic Design, pages 199--204. IEEE Computer Society, 2001.

Digital Library

[6]

W.-C. Cheng and M. Pedram. Power-optimal encoding for a DRAM address bus. IEEE Trans. Very Large Scale Integr. Syst., 10(2):109--118, 2002.

Digital Library

[7]

P. Erdős, C. Ko, and R. Rado. Intersection theorems for systems of finite sets. Quart. J. Math. Oxford Ser. (2), 12:313--320, 1961.

[8]

P. G. Farrell. Linear binary anticodes. Electron. Lett., 6:419--421, 1970.

[9]

W. Fornaciari, M. Polentarutti, D. Sciuto, and C. Silvano. Power optimization of system-level address buses based on software profiling. In CODES '00: Proceedings of the Eighth International Workshop on Hardware/Software Codesign, pages 29--33. ACM Press, 2000.

Digital Library

[10]

P. Frankl. The Erdős-Ko-Rado theorem is true for n = ckt. In Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976), Vol. I, volume 18 of Colloq. Math. Soc. János Bolyai, pages 365--375. North-Holland, Amsterdam, 1978.

[11]

G. O. H. Katona. The Hamming-sphere has minimum boundary. Studia Sci. Math. Hungar., 10(1--2):131--140, 1975.

[12]

D. J. Kleitman. On a combinatorial conjecture of Erdős. J. Combin. Theory, 1:209--214, 1966.

[13]

T. Lindkvist, J. Lofvenberg, H. Ohlsson, K. Johansson, and L. Wanhammar. A power-effcient, low-complexity, memoryless coding scheme for buses with dominating inter-wire capacitances. In IWSOC '04: Proceedings of the 4th IEEE International Workshop on System-on-Chip for Real-Time Applications, pages 257--262. IEEE Computer Society, 2004.

Digital Library

[14]

R. Murgai and M. Fujita. On reducing transitions through data modifications. In DATE '99: Proceedings of the Conference on Design, Automation and Test in Europe, pages 82--88. ACM Press, 1999.

Digital Library

[15]

A. Nijenhuis and H. S. Wilf. Combinatorial Algorithms. Academic Press, New York, 1978.

[16]

K. N. Patel and I. L. Markov. Error-correction and crosstalk avoidance in DSM busses. IEEE Trans. Very Large Scale Integr. Syst., 12(10):1076--1080, 2004.

Digital Library

[17]

Y. Shin, S.-I. Chae, and K. Choi. Partial bus-invert coding for power optimization of system level bus. In ISLPED '98: Proceedings of the 1998 International Symposium on Low Power Electronics and Design, pages 127--129. ACM Press, 1998.

Digital Library

[18]

M. R. Stan and W. P. Burleson. Bus-invert coding for low-power I/O. IEEE Trans. Very Large Scale Integr. Syst., 3(1):49--58, 1995.

Digital Library

[19]

M. R. Stan and W. P. Burleson. Coding a terminated bus for low power. In GLSVLSI '95: Proceedings of the Fifth Great Lakes Symposium on VLSI, pages 70--73. IEEE Computer Society, 1995.

Digital Library

[20]

P. Subrahmanya, R. Manimegalai, V. Kamakoti, and M. Mutyam. A bus encoding technique for power and cross-talk minimization. In VLSI Design 2004: 17th International Conference on VLSI Design, pages 443--448. IEEE Computer Society, 2004.

Digital Library

[21]

R. M. Wilson. The exact bound in the Erdős-Ko-Rado theorem. Combinatorica, 4(2--3):247--257, 1984.

Cited By

Ajmal MZhang X(2021)New optimal error-correcting codes for crosstalk avoidance in on-chip data busesAdvances in Mathematics of Communications10.3934/amc.202007815:3(487)Online publication date: 2021
https://doi.org/10.3934/amc.2020078
Chee YColbourn CLing AZhang HZhang X(2015)Optimal low-power coding for error correction and crosstalk avoidance in on-chip data busesDesigns, Codes and Cryptography10.1007/s10623-015-0084-477:2-3(479-491)Online publication date: 1-Dec-2015
https://dl.acm.org/doi/10.1007/s10623-015-0084-4

Index Terms

Optimal memoryless encoding for low power off-chip data buses

Recommendations

Power efficient encoding techniques for off-chip data buses
CASES '03: Proceedings of the 2003 international conference on Compilers, architecture and synthesis for embedded systems

Reducing the power consumption of computing devices has gained a lot of attention recently. Many research works have focused on reducing power consumption in the off-chip buses as they consume a significant amount of total power. Since the bus power ...
Energy-efficient encoding techniques for off-chip data buses
Energy-efficient encoding techniques for off-chip data buses

Reducing the power consumption of computing devices has gained a lot of attention recently. Many research works have focused on reducing power consumption in the off-chip buses as they consume a significant amount of total power. Since the bus power ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

ICCAD '06: Proceedings of the 2006 IEEE/ACM international conference on Computer-aided design

November 2006

147 pages

ISBN:1595933891

DOI:10.1145/1233501

General Chair:
Soha Hassoun
Tufts Univ., Medford, MA

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

SIGDA: ACM Special Interest Group on Design Automation
IEEE-CAS: Circuits & Systems
IEEE-CS: Computer Society

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 05 November 2006

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

ICCAD06

Sponsor:

SIGDA
IEEE-CAS
IEEE-CS

ICCAD06: The International Conference on Computer-Aided Design 2006

November 5 - 9, 2006

California, San Jose

Acceptance Rates

Overall Acceptance Rate 457 of 1,762 submissions, 26%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
95
Total Downloads

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

Reflects downloads up to 07 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Ajmal MZhang X(2021)New optimal error-correcting codes for crosstalk avoidance in on-chip data busesAdvances in Mathematics of Communications10.3934/amc.202007815:3(487)Online publication date: 2021
https://doi.org/10.3934/amc.2020078
Chee YColbourn CLing AZhang HZhang X(2015)Optimal low-power coding for error correction and crosstalk avoidance in on-chip data busesDesigns, Codes and Cryptography10.1007/s10623-015-0084-477:2-3(479-491)Online publication date: 1-Dec-2015
https://dl.acm.org/doi/10.1007/s10623-015-0084-4

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.

Figures

Tables

Media

View Table of Conten