Article

BitValue Inference: Detecting and Exploiting Narrow Bitwidth Computations

Authors:

Seth Copen GoldsteinAuthors Info & Claims

Euro-Par '00: Proceedings from the 6th International Euro-Par Conference on Parallel Processing

Pages 969 - 979

Published: 29 August 2000 Publication History

Abstract

We present a compiler algorithm called BitValue, which can discover both unused and constant bits in dusty-deck C programs. Bit-Value uses forward and backward dataflow analyses, generalizing constant-folding and dead-code detection at the bit-level. This algorithm enables compiler optimizations which target special processor architectures for computing on non-standard bitwidths.

Using this algorithm we show that up to 31% oft he computed bytes are thrown away (for programs from SpecINT95 and Mediabench). A compiler for reconfigurable hardware uses this algorithm to achieve substantial reductions (up to 20-fold) in the size of the synthesized circuits.

References

[1]

J. Babb, M. Rinard, A. Moritz, W. Lee, M. Frank, R. Barua, and S. Amarasinghe. Parallelizing applications into silicon. In IEEE/FCCM Symposium on Field-Programmable Custom Computing Machines, Napa Valley, CA, April 1999. MIT.

[2]

K. Bondalapati and V.K. Prasanna. Dynamic precision management for loop computations on reconfigurable architectures. In IEEE/FCCM Symposium on Field-Programmable Custom Computing Machines, Napa Valley, CA, April 1999. Organization: University of Southern California.

[3]

D. Brooks and M. Martonosi. Dynamically exploiting narrow width operands to improve processor power and performance. In HPCA-5, January 1999. Princeton University.

[4]

M. Budiu and S.C. Goldstein. Fast compilation for pipelined reconfigurable fabrics. In ACM/FPGA Symposium on Field Programmable Gate Arrays, Monterey, CA, 1999.

[5]

M. Budiu and S.C. Goldstein. BitValue -- Detecting and Exploiting Narrow Bitwidth Computations. Technical Report CMU-CS-00-141, Carnegie Mellon University, June 2000.

[6]

M. Damiani and G. de Micheli. Don't care specifications in combinational and synchronous logic circuits. In IEEE Transactions on CAD/ICAS, pages 365-388, 1992.

[7]

S.C. Goldstein, H. Schmit, M. Moe, M. Budiu, S. Cadambi, R.R. Taylor, and R. Laufer. Piperench: A coprocessor for streaming multimedia acceleration. In Proceedings of the 26th Annual International Symposium on Computer Architecture, pages 28-39, May 1999.

[8]

C. Lee, M. Potkonjak, and W.H. Mangione-Smith. Mediabench: a tool for evaluating and synthesizing multimedia and communications systems. In Micro-30, 30th annual ACM/IEEE international symposium on Microarchitecture, pages 330-335, 1997.

[9]

P. Marwedel and G. Goossens, editors. Code generation for embedded processors. Kluwer Academic Press, 1995.

[10]

A. Peleg, S. Wilkie, and U. Weiser. Intel MMX for multimedia PCs. Communications of the ACM, 40(1):24-38, 1997.

[11]

Rahul Razdan. PRISC: Programmable reduced instruction set computers. PhD thesis, Harvard University, May 1994.

[12]

http://www.specbench.org/osg/cpu95/.

[13]

M. Stephenson, J. Babb, and S. Amarasinghe. Bitwidth analysis with application to silicon compilation. In Proceedings of the SIGPLAN conference on Programming Language Design and Implementation, June 2000.

[14]

E. Stoltz, M. P. Gerlek, and M. Wolfe. Extended SSA with Factored Use-Def chains to support optimization and parallelism. In Proceedings Hawaii International Conference on Systems Sciences, Maui, Hawaii, Jan. 1994.

[15]

R. Wilson, R. French, C. Wilson, S. Amarasinghe, J. Anderson, S. Tjiang, S.-W. Liao, C.-W. Tseng, M. Hall, M. Lam, and J. Hennessy. SUIF: An inf rastructure for research on parallelizing and optimizing compilers. In ACM SIGPLAN Notices, volume 29, pages 31-37, December 1994.

Cited By

Pauget BPearce DPotanin AKell SMarr S(2018)Towards compilation of an imperative language for FPGAsProceedings of the 10th ACM SIGPLAN International Workshop on Virtual Machines and Intermediate Languages10.1145/3281287.3281291(47-56)Online publication date: 4-Nov-2018
https://dl.acm.org/doi/10.1145/3281287.3281291
Voitsechov DZulfiqar AStephenson MGebhart MKeckler S(2018)Software-Directed Techniques for Improved GPU Register File UtilizationACM Transactions on Architecture and Code Optimization10.1145/324390515:3(1-23)Online publication date: 24-Sep-2018
https://dl.acm.org/doi/10.1145/3243905
Bhagat IGibert ESánchez JGonzález A(2011)Global productiveness propagationACM SIGPLAN Notices10.1145/2016603.196770046:5(161-170)Online publication date: 11-Apr-2011
https://dl.acm.org/doi/10.1145/2016603.1967700
Show More Cited By

BitValue Inference: Detecting and Exploiting Narrow Bitwidth Computations
1. Software and its engineering
  1. Software notations and tools

Recommendations

An evaluation of speculative instruction execution on simultaneous multithreaded processors

Modern superscalar processors rely heavily on speculative execution for performance. For example, our measurements show that on a 6-issue superscalar, 93% of committed instructions for SPECINT95 are speculative. Without speculation, processor resources ...
Converting thread-level parallelism to instruction-level parallelism via simultaneous multithreading

To achieve high performance, contemporary computer systems rely on two forms of parallelism: instruction-level parallelism (ILP) and thread-level parallelism (TLP). Wide-issue super-scalar processors exploit ILP by executing multiple instructions from a ...
A Front-end Execution Architecture for High Energy Efficiency
MICRO-47: Proceedings of the 47th Annual IEEE/ACM International Symposium on Microarchitecture

Smart phones and tablets have recently become widespread and dominant in the computer market. Users require that these mobile devices provide a high-quality experience and an even higher performance. Hence, major developers adopt out-of-order ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

Euro-Par '00: Proceedings from the 6th International Euro-Par Conference on Parallel Processing

August 2000

3356 pages

ISBN:3540679561

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 29 August 2000

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

33
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 16 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Pauget BPearce DPotanin AKell SMarr S(2018)Towards compilation of an imperative language for FPGAsProceedings of the 10th ACM SIGPLAN International Workshop on Virtual Machines and Intermediate Languages10.1145/3281287.3281291(47-56)Online publication date: 4-Nov-2018
https://dl.acm.org/doi/10.1145/3281287.3281291
Voitsechov DZulfiqar AStephenson MGebhart MKeckler S(2018)Software-Directed Techniques for Improved GPU Register File UtilizationACM Transactions on Architecture and Code Optimization10.1145/324390515:3(1-23)Online publication date: 24-Sep-2018
https://dl.acm.org/doi/10.1145/3243905
Bhagat IGibert ESánchez JGonzález A(2011)Global productiveness propagationACM SIGPLAN Notices10.1145/2016603.196770046:5(161-170)Online publication date: 11-Apr-2011
https://dl.acm.org/doi/10.1145/2016603.1967700
Bhagat IGibert ESánchez JGonzález AVitek JDe Sutter B(2011)Global productiveness propagationProceedings of the 2011 SIGPLAN/SIGBED conference on Languages, compilers and tools for embedded systems10.1145/1967677.1967700(161-170)Online publication date: 11-Apr-2011
https://dl.acm.org/doi/10.1145/1967677.1967700
Cardoso JDiniz PWeinhardt M(2010)Compiling for reconfigurable computingACM Computing Surveys10.1145/1749603.174960442:4(1-65)Online publication date: 23-Jun-2010
https://dl.acm.org/doi/10.1145/1749603.1749604
Kettle NKing ABarrett Cde Moura LBabic DGoel A(2008)Bit-precise reasoning with affine functionsProceedings of the Joint Workshops of the 6th International Workshop on Satisfiability Modulo Theories and 1st International Workshop on Bit-Precise Reasoning10.1145/1512464.1512474(46-52)Online publication date: 7-Jul-2008
https://dl.acm.org/doi/10.1145/1512464.1512474
McCamant SErnst M(2008)Quantitative information flow as network flow capacityACM SIGPLAN Notices10.1145/1379022.137560643:6(193-205)Online publication date: 7-Jun-2008
https://dl.acm.org/doi/10.1145/1379022.1375606
McCamant SErnst MGupta RAmarasinghe S(2008)Quantitative information flow as network flow capacityProceedings of the 29th ACM SIGPLAN Conference on Programming Language Design and Implementation10.1145/1375581.1375606(193-205)Online publication date: 7-Jun-2008
https://dl.acm.org/doi/10.1145/1375581.1375606
Özer ENisbet AGregg D(2008)A stochastic bitwidth estimation technique for compact and low-power custom processorsACM Transactions on Embedded Computing Systems10.1145/1347375.13473877:3(1-30)Online publication date: 8-May-2008
https://dl.acm.org/doi/10.1145/1347375.1347387
Cooprider NRegehr J(2007)Offline compression for on-chip ramACM SIGPLAN Notices10.1145/1273442.125077642:6(363-372)Online publication date: 10-Jun-2007
https://dl.acm.org/doi/10.1145/1273442.1250776
Show More Cited By

View Options

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

Media

Figures

Other

Tables

View Table of Contents