Using complementation and resequencing to minimize transitions

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Using complementation and resequencing to minimize transitions

Full text

Pdf (316 KB)

Source

Annual ACM IEEE Design Automation Conference archive
Proceedings of the 35th annual Design Automation Conference table of contents

San Francisco, California, United States

Pages: 694 - 697

Year of Publication: 1998

ISBN:0-89791-964-5

Authors

Rajeev Murgai	Fujitsu Laboratories of America, Inc.
Masahiro Fujita	Fujitsu Laboratories of America, Inc.
Arlindo Oliveira	Cadence European Labs./IST-INESC

Sponsors

SIGDA: ACM Special Interest Group on Design Automation
EDAC : Electronic Design Automation Consortium
IEEE-CS : Computer Society

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 13, Citation Count: 4

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/277044.277219 What is a DOI?

ABSTRACT

Recently, in [3], the following problem was addressed: Given a set of data words or messages to be transmitted over a bus such that the sequence (order) in which they are transmitted is irrelevant, determine the optimum sequence that minimizes the total number of transitions on the bus. In 1994, Stan and Burleson [5] presented the bus-invert method as a means of encoding words for reducing I/O power, in which a word may be inverted and then transmitted if doing so reduces the number of transitions. In this paper, we combine the two paradigms into one — that of sequencing words under the bus-invert scheme for the minimum transitions, i.e., words can be complemented, reordered and then transmitted. We prove that this problem DOPI — Data Ordering Problem with Inversion — is NP-complete. We present a polynomial-time approximation algorithm to solve DOPI that comes within a factor of 1.5 from the optimum. Experimental results show that, on average, the solutions generated by our algorithm were within 4.4% of the optimum, and that resequencing along with complementation leads to 34.4% reduction in switching activity.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Experienced Motorola Designer. Personal comm., Apr. 95.
	2	John L. Hennessy , David A. Patterson, Computer architecture (2nd ed.): a quantitative approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1996
	3	I~ Murgai, M. Fujita, and S. C. Krishnan. Data Sequencing For Minimum-transition Transmission. InVLSI 97, Brazil.
	4	1~ Murgai, M. Fujita, and ~ Oliveira. Using Complementation And Resequencing To Minimize Transitions. hInternal Report, Fujitsu Labs of America, Inc., Nov. 97.
	5	M. R. Stan and W. P. Burleson. Limited-weight Codes for Low-power I/O. In Int. Work. on Low Power Design, Apr. 94.

CITED BY 4

	Wei-Chung Cheng , Massoud Pedram, Power-optimal encoding for a DRAM address bus, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.10 n.2, p.109-118, April 2002
	Vijay Sundararajan , Keshab K. Parhi, Reducing bus transition activity by limited weight coding with codeword slimming, Proceedings of the 10th Great Lakes symposium on VLSI, p.13-16, March 02-04, 2000, Chicago, Illinois, United States
	E. da Costa , J. Monteiro , S. Bampi, A new array architecture for signed multiplication using Gray encoded radix-2m operands, Integration, the VLSI Journal, v.40 n.2, p.118-132, February, 2007
	Rajeev Murgai , Masahiro Fujita, On reducing transitions through data modifications, Proceedings of the conference on Design, automation and test in Europe, p.19-es, January 1999, Munich, Germany