Static analysis of processor stall cycle aggregation

ABSTRACT

Processor Idle Cycle Aggregation (PICA) is a promising approach for low power execution of processors, in which small memory stalls are aggregated to create a large one, and the processor is switched to low-power mode in it. We extend the previous proposed approach in two dimensions. i) We develop static analysis for the PICA technique and present optimum parameters for five common types of loops based on steady-state analysis. ii) We show that software only control is unable to guarantee its correctness in a varying runtime environment, potentially causing deadlocks. We enhance the robustness of PICA with minimal hardware extension, ensuring correct execution for any loops and parameters, which greatly facilitates exploration based parameter optimization. The combined use of our static analysis and exploration based fine-tuning makes the PICA technique applicable, to any memory-bound loop, with energy reduction. We validate our analytical models against simulation based optimization and also show through our experiments on embedded application benchmarks, that our technique can be applied to a wide range of loops with average 20% energy reductions compared to executions without PICA.

REFERENCES

• 1: K. Choi et al. Fine-grained dynamic voltage and frequency scaling for precise energy and performance tradeoff based on the ratio of off-chip access to on-chip computation times. IEEE Trans. CAD, 24(1):18--28, 2005.
• 2: Michael K. Gowan , Larry L. Biro , Daniel B. Jackson, Power considerations in the design of the Alpha 21264 microprocessor, Proceedings of the 35th annual conference on Design automation, p.726-731, June 15-19, 1998, San Francisco, California, United States [doi>10.1145/277044.277226]
• 3: Aviral Shrivastava , Eugene Earlie , Nikil Dutt , Alex Nicolau, Aggregating processor free time for energy reduction, Proceedings of the 3rd IEEE/ACM/IFIP international conference on Hardware/software codesign and system synthesis, September 19-21, 2005, Jersey City, NJ, USA [doi>10.1145/1084834.1084876]
• 4: A. Azevedo , I. Issenin , R. Cornea , R. Gupta , N. Dutt , A. Veidenbaum , A. Nicolau, Profile-Based Dynamic Voltage Scheduling Using Program Checkpoints, Proceedings of the conference on Design, automation and test in Europe, p.168, March 04-08, 2002
• 5: Thomas D. Burd , Robert W. Brodersen, Design issues for dynamic voltage scaling, Proceedings of the 2000 international symposium on Low power electronics and design, p.9-14, July 25-27, 2000, Rapallo, Italy [doi>10.1145/344166.344181]
• 6: Intel Corporation. Intel XScale® Core: Developer's Manual. {Online}. Available: http://www.intel.com/design/intelxscale/273473.htm.
• 7: Intel Corporation. Intel 80200 Processor based on Intel XScale Microarchitecture. {Online}. Available: http://www.intel.com/design/iio/manuals/273411.htm.
• 8: J. Rabaey and M. Pedram, editors. Low Power Design Methodologies. Kluwer Academic Publishers, 1996.
• 9: Todd C. Mowry , Monica S. Lam , Anoop Gupta, Design and evaluation of a compiler algorithm for prefetching, Proceedings of the fifth international conference on Architectural support for programming languages and operating systems, p.62-73, October 12-15, 1992, Boston, Massachusetts, United States
• 10: Steven P. Vanderwiel , David J. Lilja, Data prefetch mechanisms, ACM Computing Surveys (CSUR), v.32 n.2, p.174-199, June 2000 [doi>10.1145/358923.358939]
• 11: E. Brockmeyer , M. Miranda , H. Corporaal , F. Catthoor, Layer Assignment echniques for Low Energy in Multi-Layered Memory Organisations, Proceedings of the conference on Design, Automation and Test in Europe, p.11070, March 03-07, 2003
• 12: Ilya Issenin , Erik Brockmeyer , Miguel Miranda , Nikil Dutt, Data Reuse Analysis Technique for Software-Controlled Memory Hierarchies, Proceedings of the conference on Design, automation and test in Europe, p.10202, February 16-20, 2004
• 13: M. Kandemir , A. Choudhary, Compiler-directed scratch pad memory hierarchy design and management, Proceedings of the 39th conference on Design automation, June 10-14, 2002, New Orleans, Louisiana, USA [doi>10.1145/513918.514077]
• 14: Aviral Shrivastava , Ilya Issenin , Nikil Dutt, Compilation techniques for energy reduction in horizontally partitioned cache architectures, Proceedings of the 2005 international conference on Compilers, architectures and synthesis for embedded systems, September 24-27, 2005, San Francisco, California, USA [doi>10.1145/1086297.1086310]
• 15: V. Zivojnovic et al. DSPstone: A DSP-oriented benchmarking methodology. In ICSPAT, 1994.
• 16: SPEC 95. Standard Performance Evaluation Corporation. http://www.spec.org/.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS
      Subjects: Real-time and embedded systems

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers; Code generation; Optimization

General Terms:
Algorithms, Design, Experimentation, Performance

Keywords:
code transformation, embedded systems, low power, memory bound loops, processor free time, stall cycle aggregation