research-article

Exploiting finite precision information to guide data-flow mapping

Authors:

David Novo,

Min Li,

Robert Fasthuber,

Praveen Raghavan,

Francky CatthoorAuthors Info & Claims

DAC '10: Proceedings of the 47th Design Automation Conference

Pages 248 - 253

https://doi.org/10.1145/1837274.1837338

Published: 13 June 2010 Publication History

Get Access

Abstract

Advanced handheld applications are demanding for implementations of higher energy efficiency and higher performance. In typical implementations, the finite precision information is only known after fixed-point refinement, once the data-flow has been frozen. Instead, in this paper we suggest the propagation of finite precision information to drive data-flow transformations in order to achieve a higher mapping efficiency. Then, provided a flexible architecture with low run-time switching overhead, the data-flow under execution can opportunistically be tuned to provide the instantaneous computational accuracy required by the application. Thereby, the average number of operations and the precision of those is minimized. This principle is demonstrated with the implementation of the 128-point FFT present in a WLAN receiver. Compared to a conventional implementation, a reduction of 49% to 65% of the number of cycles can be achieved depending on conditions external to the receiver.

References

[1]

D. Bacon, S. Graham, and O. Sharp. Compiler transformations for high-performance computing. ACM Computing Surveys (CSUR), 26(4):420, 1994.

Digital Library

Google Scholar

[2]

P. Behrooz. Computer arithmetic: Algorithms and hardware designs. Oxford University Press, 19:512583--512585, 2000.

Digital Library

Google Scholar

[3]

F. Catthoor, D. Lanneer, and H. De Man. Application-specific microcoded architectures for efficient fixed-rate DFT and FFT. In IEEE International Symposium on Circuits and Systems, 1989.

Crossref

Google Scholar

[4]

A. Chandrakasan, M. Potkonjak, R. Mehra, J. Rabaey, and R. Brodersen. Optimizing power using transformations. IEEE TCAD, 14(1):12--31, 1995.

Digital Library

Google Scholar

[5]

S. Cherry. Edholm's law of bandwidth. IEEE Spectrum, 41(7):58--60, 2004.

Digital Library

Google Scholar

[6]

A. Gaffar, O. Mencer, W. Luk, and P. Cheung. Unifying bit-width optimisation for fixed-point and floating-point designs. In Proc. of FCCM, pages 79--88, 2004.

Digital Library

Google Scholar

[7]

A. Nayak, M. Haldar, A. Choudhary, and P. Banerjee. Precision and error analysis of MATLAB applications during automated hardware synthesis for FPGAs. In Proc. Design Automation and Test in Europe, 2001.

Digital Library

Google Scholar

[8]

M. Puschel, J. Moura, J. Johnson, D. Padua, M. Veloso, B. Singer, J. Xiong, F. Franchetti, A. Gacic, Y. Voronenko, et al. SPIRAL: Code generation for DSP transforms. Proceedings of the IEEE, 93(2):232--275, 2005.

Crossref

Google Scholar

[9]

P. Raghavan, A. Lambrechts, M. Jayapala, F. Catthoor, and D. Verkest. Distributed loop controller for multi-threading in uni-threaded ilp architectures. IEEE Transactions on Computers, 58(3):311--321, March 2009.

Digital Library

Google Scholar

[10]

P. Raghavan, A. Lambrechts, M. Jayapala, F. Catthoor, D. Verkest, and H. Corporaal. Very wide register: An asymmetric register file organization for low power embedded processors. In Proc. of DATE, 2007.

Digital Library

Google Scholar

[11]

R. Rocher, D. Menard, N. Herve, and O. Sentieys. Fixed-point configurable hardware components. EURASIP Journal on Embedded Systems, 2006(1):20--20, 2006.

Digital Library

Google Scholar

[12]

N. Shanbhag. Algorithms transformation techniques for low-power wireless VLSI systems design. International Journal of Wireless Information Networks, 5(2), 1998.

Crossref

Google Scholar

[13]

J. Tseng and K. Asanović. A speculative control scheme for an energy-efficient banked register file. IEEE Transactions on Computers, pages 741--751, 2005.

Digital Library

Google Scholar

[14]

S. Yoshizawa and Y. Miyanaga. Tunable wordlength architecture for a low power wireless OFDM demodulator. IEICE Transactions, 89(10):2866, 2006.

Digital Library

Google Scholar

Cited By

View all

Novo DFarahpour NIenne PAhmad UCatthoor FFettweis GNebel W(2014)Energy efficient MIMO processingProceedings of the conference on Design, Automation & Test in Europe10.5555/2616606.2616861(1-6)Online publication date: 24-Mar-2014
https://dl.acm.org/doi/10.5555/2616606.2616861
Liu ZLi THan J(2013)A novel reconfigurable data-flow architecture for real time video processingJournal of Shanghai Jiaotong University (Science)10.1007/s12204-013-1405-218:3(348-359)Online publication date: 4-Jun-2013
https://doi.org/10.1007/s12204-013-1405-2
Fasthuber RCatthoor FRaghavan PNaessens FFasthuber RCatthoor FRaghavan PNaessens F(2013)Front-End Design Flow: Bridging the Algorithm-Architecture GapEnergy-Efficient Communication Processors10.1007/978-1-4614-4992-8_7(251-277)Online publication date: 30-May-2013
https://doi.org/10.1007/978-1-4614-4992-8_7
Show More Cited By

Index Terms

Exploiting finite precision information to guide data-flow mapping
1. Hardware
  1. Communication hardware, interfaces and storage
    1. Signal processing systems

Recommendations

Finite Precision Rational Arithmetic: Slash Number Systems

Fraction number systems characterized by fixed-slash and floating-slash formats are specified. The structure of arithmetic over such systems is prescribed by the rounding obtained from "best rational approximation." Multitiered precision hierarchies of ...
Analysis of Chaotic Sequence Period Generated by Logistic Map under Finite Precision
ICECC '12: Proceedings of the 2012 International Conference on Electronics, Communications and Control

The rule of chaotic sequence period is discovered with Monte Carlo method, which is generated by Logistic map under finite precision, and a scheme is presented to use chaos under finite precision. The relationship between precision and initial value ...
Solving linear programs with finite precision: II. Algorithms

We describe an algorithm that first decides whether the primal-dual pair of linear programsminc^Txmaxb^Tys.t.Ax=bs.t.A^Ty= =0is feasible and in case it is, computes an optimal basis and optimal solutions. Here, A@__ __R^m^x^n,b@__ __R^m,c@__ __R^n are ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

DAC '10: Proceedings of the 47th Design Automation Conference

June 2010

1036 pages

ISBN:9781450300025

DOI:10.1145/1837274

General Chair:
Sachin Sapatnekar
Univ. of Minnesota, Minneapolis, MN

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

Publication History

Published: 13 June 2010

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

DAC '10

Sponsor:

EDAC
SIGDA

DAC '10: The 47th Annual Design Automation Conference 2010

June 13 - 18, 2010

California, Anaheim

Acceptance Rates

Overall Acceptance Rate 1,770 of 5,499 submissions, 32%

Upcoming Conference

DAC '25

Sponsor:
sigda

62nd ACM/IEEE Design Automation Conference

June 22 - 26, 2025

San Francisco , CA , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
116
Total Downloads

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

Reflects downloads up to 11 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Novo DFarahpour NIenne PAhmad UCatthoor FFettweis GNebel W(2014)Energy efficient MIMO processingProceedings of the conference on Design, Automation & Test in Europe10.5555/2616606.2616861(1-6)Online publication date: 24-Mar-2014
https://dl.acm.org/doi/10.5555/2616606.2616861
Liu ZLi THan J(2013)A novel reconfigurable data-flow architecture for real time video processingJournal of Shanghai Jiaotong University (Science)10.1007/s12204-013-1405-218:3(348-359)Online publication date: 4-Jun-2013
https://doi.org/10.1007/s12204-013-1405-2
Fasthuber RCatthoor FRaghavan PNaessens FFasthuber RCatthoor FRaghavan PNaessens F(2013)Front-End Design Flow: Bridging the Algorithm-Architecture GapEnergy-Efficient Communication Processors10.1007/978-1-4614-4992-8_7(251-277)Online publication date: 30-May-2013
https://doi.org/10.1007/978-1-4614-4992-8_7
Fasthuber RCatthoor FRaghavan PNaessens FFasthuber RCatthoor FRaghavan PNaessens F(2013)The Proposed DSIP Architecture Template for the Wireless Communication DomainEnergy-Efficient Communication Processors10.1007/978-1-4614-4992-8_3(69-135)Online publication date: 30-May-2013
https://doi.org/10.1007/978-1-4614-4992-8_3

View Options

Login options

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

Cited By

Index Terms

Recommendations

Finite Precision Rational Arithmetic: Slash Number Systems

Analysis of Chaotic Sequence Period Generated by Logistic Map under Finite Precision

Solving linear programs with finite precision: II. Algorithms