Comparing Program Phase Detection Techniques

ABSTRACT

Detecting program phase changes accurately is an importantaspect of dynamically adaptable systems. Threedynamic program phase detection techniques are compared- using instruction working sets, basic block vectors(BBV), and conditional branch counts. Because programphases are difficult to define, we compare the techniquesusing a variety of metrics.BBV techniques perform better than the other techniquesproviding higher sensitivity and more stablephases. However, the instruction working set techniqueyields 30% longer phases than the BBV method, althoughthere is less stability within phases. On average, the methodsagree on phase changes 85% of the time. Of the 15%of time they disagree, the BBV method is more efficient atdetecting performance changes. The conditional branchcounter technique provides good sensitivity, but is lesseffective at detecting major phase changes. Nevertheless,the branch counter technique correlates 83% of the timewith the BBV based technique. As an auxiliary result, weshow that techniques based on procedure granularities donot perform as well as those based on instruction or basicblock granularities. This is mainly due to their inability todetect changes within procedures.

REFERENCES

• 1: David H. Albonesi, Dynamic IPC/clock rate optimization, Proceedings of the 25th annual international symposium on Computer architecture, p.282-292, June 27-July 02, 1998, Barcelona, Spain
• 2: Rajeev Balasubramonian , David Albonesi , Alper Buyuktosunoglu , Sandhya Dwarkadas, Memory hierarchy reconfiguration for energy and performance in general-purpose processor architectures, Proceedings of the 33rd annual ACM/IEEE international symposium on Microarchitecture, p.245-257, December 2000, Monterey, California, United States [doi>10.1145/360128.360153]
• 3: Se-Hyun Yang , Babak Falsafi , Michael D. Powell , Kaushik Roy , T. N. Vijaykumar, An Integrated Circuit/Architecture Approach to Reducing Leakage in Deep-Submicron High-Performance I-Caches, Proceedings of the 7th International Symposium on High-Performance Computer Architecture, p.147, January 20-24, 2001
• 4: Parthasarathy Ranganathan , Sarita Adve , Norman P. Jouppi, Reconfigurable caches and their application to media processing, Proceedings of the 27th annual international symposium on Computer architecture, p.214-224, June 2000, Vancouver, British Columbia, Canada
• 5: Toni Juan , Sanji Sanjeevan , Juan J. Navarro, Dynamic history-length fitting: a third level of adaptivity for branch prediction, Proceedings of the 25th annual international symposium on Computer architecture, p.155-166, June 27-July 02, 1998, Barcelona, Spain
• 6: Daniele Folegnani , Antonio González, Energy-effective issue logic, Proceedings of the 28th annual international symposium on Computer architecture, p.230-239, June 30-July 04, 2001, Göteborg, Sweden
• 7: Alper Buyuktosunoglu , Tejas Karkhanis , David H. Albonesi , Pradip Bose, Energy efficient co-adaptive instruction fetch and issue, Proceedings of the 30th annual international symposium on Computer architecture, June 09-11, 2003, San Diego, California
• 8: R. Iris Bahar , Srilatha Manne, Power and energy reduction via pipeline balancing, Proceedings of the 28th annual international symposium on Computer architecture, p.218-229, June 30-July 04, 2001, Göteborg, Sweden
• 9: Michael Huang , Jose Renau , Seung-Moon Yoo , Josep Torrellas, A framework for dynamic energy efficiency and temperature management, Proceedings of the 33rd annual ACM/IEEE international symposium on Microarchitecture, p.202-213, December 2000, Monterey, California, United States [doi>10.1145/360128.360149]
• 10: [10] J. E. Smith, and A. S. Dhodapkar, "Dynamic microarchitecture adaptation via co-designed virtual machines," in 2002 Intl. Solid State Circuits Conference, Digest of Technical Papers, pp. 198-199, Feb. 2002.
• 11: Ashutosh S. Dhodapkar , James E. Smith, Managing multi-configuration hardware via dynamic working set analysis, Proceedings of the 29th annual international symposium on Computer architecture, May 25-29, 2002, Anchorage, Alaska
• 12: Michael C. Huang , Jose Renau , Josep Torrellas, Positional adaptation of processors: application to energy reduction, Proceedings of the 30th annual international symposium on Computer architecture, June 09-11, 2003, San Diego, California
• 13: Vasanth Bala , Evelyn Duesterwald , Sanjeev Banerjia, Dynamo: a transparent dynamic optimization system, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.1-12, June 18-21, 2000, Vancouver, British Columbia, Canada
• 14: Matthew Arnold , Stephen Fink , David Grove , Michael Hind , Peter F. Sweeney, Adaptive optimization in the Jalapeño JVM, Proceedings of the 15th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.47-65, October 2000, Minneapolis, Minnesota, United States
• 15: [15] http://java.sun.com
• 16: [16] http://www.microsoft.com/net
• 17: [17] Timothy Sherwood, and Brad Calder, "Time varying behavior of programs," UC San Diego Technical Report UCSD- CS99-630, Aug. 1999.
• 18: [18] J. Henning, "SPEC CPU2000 memory footprint," online at http://www.spec.org/cpu2000/analysis/memory
• 19: Timothy Sherwood , Suleyman Sair , Brad Calder, Phase tracking and prediction, Proceedings of the 30th annual international symposium on Computer architecture, June 09-11, 2003, San Diego, California
• 20: Timothy Sherwood , Erez Perelman , Brad Calder, Basic Block Distribution Analysis to Find Periodic Behavior and Simulation Points in Applications, Proceedings of the 2001 International Conference on Parallel Architectures and Compilation Techniques, p.3-14, September 08-12, 2001
• 21: Timothy Sherwood , Erez Perelman , Greg Hamerly , Brad Calder, Automatically characterizing large scale program behavior, Proceedings of the 10th international conference on Architectural support for programming languages and operating systems, October 05-09, 2002, San Jose, California
• 22: [22] M. J. Hind, V. T. Rajan, and P. F. Sweeney, "Phase shift detection: a problem classification," IBM Research Report RC-22887, Aug. 2003.
• 23: Dirk Grunwald , Artur Klauser , Srilatha Manne , Andrew Pleszkun, Confidence estimation for speculation control, Proceedings of the 25th annual international symposium on Computer architecture, p.122-131, June 27-July 02, 1998, Barcelona, Spain
• 24: [24] D. Burger and T. Austin, "The SimpleScalar tool set version 2.0," University of Wisconsin-Madison Computer Sciences Department Technical Report #1342, June 1997.
• 25: John L. Henning, SPEC CPU2000: Measuring CPU Performance in the New Millennium, Computer, v.33 n.7, p.28-35, July 2000 [doi>10.1109/2.869367]
• 26: [26] M. S. Pepe, "The statistical evaluation of medical tests for classification and prediction," Oxford University Press, 2003.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: VLSI (very large scale integration)

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: Algorithms implemented in hardware

  C. Computer Systems Organization
  C.0 GENERAL
      Subjects: Instruction set design (e.g., RISC, CISC, VLIW)
  C.1 PROCESSOR ARCHITECTURES
      C.1.3 Other Architecture Styles
          Subjects: Adaptable architectures

General Terms:
Design, Performance