View Full Document

BitValue Inference: Detecting and Exploiting Narrow Bitwidth Computations



View the full content.
View Full Document
View Full Document

9 views

Unformatted text preview:

BitValue Inference Detecting and Exploiting Narrow Bitwidth Computations Mihai Budiu Seth Copen Goldstein June 2000 CMU CS 00 141 School of Computer Science Carnegie Mellon University Pittsburgh PA 15213 An abridged version of this text appeared in the Proceedings of 6th International Euro Par Conference August 2000 published in LNCS 1900 by Springer Verlag Abstract We present a compiler algorithm called BitValue which can discover unused and constant bits in dusty deck C programs BitValue uses forward and backward dataflow analyses generalizing constant folding and dead code detection at the bit level This algorithm enables compiler optimizations targeting special processor architectures for computing on non standard bitwidths Using this algorithm we show that up to 36 of the computed bytes are thrown away also we show that on average 26 8 of the values computed require 16 bits or less 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 This work was supported by DARPA contract DABT63 96 C 0083 and an NSF CAREER grant Keywords Compilation dataflow analysis reconfigurable hardware CAD tools 1 Introduction As the natural word width of processors increases so grows the gap between the number of bits used and those actually required for a computation Recent architectural proposals have addressed this inefficiency by providing collections of narrow functional units or the ability to construct functional units on the fly For example instruction set extensions which support subword parallelism e g 10 Application Specific Instruction set Processors ASIPs e g 9 and reconfigurable devices e g 11 all allow operations on operands which are smaller than the natural word size Reconfigurable computing devices are the most efficient at supporting arbitrary size data because they can be programmed post fabrication to implement functions directly



Access the best Study Guides, Lecture Notes and Practice Exams

Loading Unlocking...
Login

Join to view BitValue Inference: Detecting and Exploiting Narrow Bitwidth Computations and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view BitValue Inference: Detecting and Exploiting Narrow Bitwidth Computations and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?