Global productiveness propagation: a code optimization technique to speculatively prune useless narrow computations

ABSTRACT

This paper proposes a unique hardware-software collaborative strategy to remove useless work at 16-bit data-width granularity. The underlying motivation is to design a low power execution platform by exploiting 'narrow' computations. The proposal uses a strictly narrow bit-wide microarchitecture (16-bit integer datapath), which realizes the goal of a low cost, low hardware complexity, low power execution engine. Software dynamically maps the 64-bit computations by translating them into an equivalent 16-bit instruction stream and optimizing them.

In this paper, we propose an optimization technique, called Global Productiveness Propagation (GPP), which is a dynamic, profile-based optimization technique that infers the minimum required dataflow by pruning narrow computations that are most-probably useless (non-productive). More precisely, GPP speculatively prunes the static backward slices of selected narrow computations: computations that result in the same value (in their respective storage location) as that at the input of the region. This speculative optimization technique is formulated around the concept of 'narrow' computations because the same allow a finer granularity to distinguish between useful (productive) and useless (non-productive) work. GPP has been evaluated on an in-order narrow bit-wide execution core, achieving an average dynamic instruction stream reduction of 6.6%, while improving overall performance by 4.2%.

References

1. Brooks et al., Dynamically Exploiting Narrow Width Operands to Improve Processor Power and Performance, Proceedings of the 5th International Symposium on High Performance Computer Architecture, p.13, January 09--12, 199.
2. Brooks et al., Wattch: a framework for architectural-level power analysis and optimizations, Proceedings of the 27th annual international symposium on Computer architecture, 200.
3. Budiu et al., BitValue Inference: Detecting and Exploiting Narrow Bitwidth Computations, Proceedings from the 6th International Euro-Par Conference on Parallel Processing, p.969--979, August 29-September 01, 200.
4. Calder et al, Value profiling, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, December 01-03, 199.
5. Canal et al., Very low power pipelines using significance compression, Proceedings of the 33rd annual ACM/IEEE international symposium on Microarchitecture, p.181--190, December 200.
6. Canal et al., Software-Controlled Operand-Gating, Proceedings of the international symposium on Code generation and optimization: feedback-directed and runtime optimization, p.125, March 20--24, 200.
7. Ceze et al., Bulk Disambiguation of Speculative Threads in Multiprocessors. In Procs. of the 33th Intl Symp on Compute. Architecture, June 2006.
8. Cheng et al., Self-timed carry-lookahead adders, IEEE Transactions on Computers, 200.
9. Cintra et al., Architectural Support for Scalable Speculative Parallelization in Shared-Memory Systems, 27th Annual International Symposium on Computer Architecture (ISCA), June 2000.
10. Ergin et al., Register Packing: Exploiting Narrow-Width Operands for Reducing Register File Pressure, International Symposium on Microarchitecture, December 200.
11. Ferrante et al., The program dependence graph and its use in optimization, ACM Transactions on Programming Languages and Systems (TOPLAS), 198.
12. Kim et al., Leakage Current: Moore's Law Meets Static Power, IEEE Computer, 200.
13. Kondo et al., A Small, Fast and Low-Power Register File by Bit-Partitioning, Proceedings of the 11th International Symposium on High-Performance Computer Architecture, 2005.
14. Li et al., Bit section instruction set extension of ARM for embedded applications, Proceedings of the 2002 international conference on Compilers, architecture, and synthesis for embedded systems, October 08--11, 200.
15. Loh et al., Exploiting data-width locality to increase superscalar execution bandwidth, Proceedings of the 35th annual ACM/IEEE international symposium on Microarchitecture, November 18--22, 200.
16. Mahlke et al., Bitwidth cognizant architecture synthesis of custom hardwareaccelerators, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, November 200.
17. Moore et al., LogTM: Log-based TransactionalMemory. In Procs. of the 12th Intl Symp on High-Performance Computer Architecture, Feb. 2006.
18. Muralimanohar et al., Cacti 6.5, HP Laboratories Palo Alto, 200.
19. Pokam et al., Speculative software management of datapath-width for energy optimization, Proceedings of the 2004 ACM SIGPLAN/SIGBED conference on Languages, compilers, and tools for embedded systems, June 11--13, 200.
20. Shriraman et al., Flexible Decoupled Transactional Memory Support. In Procs. of the 35th Intl Symp on Computer Architecture, June 2008.
21. Steffan et al., A Scalable Approach to Thread-Level Speculation, International Symposium on Computer Architecture, Vancouver, BC, June, 2000.
22. Stephenson et al., Bidwidth analysis with application to silicon compilation, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, 200.
23. Segars et al., Low power design techniques for microprocessors, International Solid-State Circuits Conference Tutorial, 200.
24. Tallam et al., Bitwidth aware global register allocation, ACM SIGPLAN Notices, v.38 n.1, p.85--96, January 200.
25. Vijaykrishnan et al., Energy-driven integrated hardware-software optimizations using SimplePower, Proceedings of the 27th annual international symposium on Computer architecture, p.95--106, June 200.
26. Wang et al., Intel® atom" processor core made FPGA-synthesizable, Proceeding of the ACM/SIGDA international symposium on Field programmable gate arrays, 200.
27. Yang et al., An Embedded Low Power/Cost 16-Bit Data/Instruction Microprocessor Compatible with ARM7 Software Tools, Proceedings of the 2007 conference on Asia South Pacific design automation, p.902, 23--26 Jan. 200.
28. M. T. Yourst, PTLsim: A Cycle Accurate Full System x86-64 Microarchitectural Simulator, IEEE International Symposium on Performance Analysis of Systems & Software, 200.
29. Submission in progress. Omitted for the sake of anonymity.

Index Terms

• Software and its engineering

  • Software notations and tools

    • Compilers