SoftSig: software-exposed hardware signatures for code analysis and optimization

ABSTRACT

Many code analysis techniques for optimization, debugging, or parallelization need to perform runtime disambiguation of sets of addresses. Such operations can be supported efficiently and with low complexity with hardware signatures.

To enable flexible use of signatures, this paper proposes to expose a Signature Register File to the software through a rich ISA. The software has great flexibility to decide, for each signature,which addresses to collect and which addresses to disambiguate against. We call this architecture SoftSig. In addition, as an example of SoftSig use, we show how to detect redundant function calls efficiently and eliminate them dynamically. We call this algorithm MemoiSE. On average for five popular applications, MemoiSE reduces the number of dynamic instructions by 9.3%, thereby reducing the execution time of the applications by 9%.

REFERENCES

• 1: David Bernstein , Doron Cohen , Dror E. Maydan, Dynamic memory disambiguation for array references, Proceedings of the 27th annual international symposium on Microarchitecture, p.105-111, November 30-December 02, 1994, San Jose, California, United States [doi>10.1145/192724.192737]
• 2: Burton H. Bloom, Space/time trade-offs in hash coding with allowable errors, Communications of the ACM, v.13 n.7, p.422-426, July 1970 [doi>10.1145/362686.362692]
• 3: Luis Ceze , James Tuck , Josep Torrellas , Calin Cascaval, Bulk Disambiguation of Speculative Threads in Multiprocessors, Proceedings of the 33rd annual international symposium on Computer Architecture, p.227-238, June 17-21, 2006
• 4: Luis Ceze , James Tuck , Pablo Montesinos , Josep Torrellas, BulkSC: bulk enforcement of sequential consistency, Proceedings of the 34th annual international symposium on Computer architecture, June 09-13, 2007, San Diego, California, USA
• 5: Daniel A. Connors , Hillery C. Hunter , Ben-Chung Cheng , Wen-mei W. Hwu, Hardware support for dynamic activation of compiler-directed computation reuse, Proceedings of the ninth international conference on Architectural support for programming languages and operating systems, p.222-233, November 2000, Cambridge, Massachusetts, United States
• 6: Daniel A. Connors , Wen-mei W. Hwu, Compiler-directed dynamic computation reuse: rationale and initial results, Proceedings of the 32nd annual ACM/IEEE international symposium on Microarchitecture, p.158-169, November 16-18, 1999, Haifa, Israel
• 7: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
• 8: Yonghua Ding , Zhiyuan Li, A Compiler Scheme for Reusing Intermediate Computation Results, Proceedings of the international symposium on Code generation and optimization: feedback-directed and runtime optimization, p.279, March 20-24, 2004, Palo Alto, California
• 9: David M. Gallagher , William Y. Chen , Scott A. Mahlke , John C. Gyllenhaal , Wen-mei W. Hwu, Dynamic memory disambiguation using the memory conflict buffer, Proceedings of the sixth international conference on Architectural support for programming languages and operating systems, p.183-193, October 05-07, 1994, San Jose, California, United States
• 10: Jian Huang , David Lilja, Exploiting Basic Block Value Locality with Block Reuse, Proceedings of the 5th International Symposium on High Performance Computer Architecture, p.106, January 09-12, 1999
• 11: Intel Corporation, Intel 64 and IA-32 Architectures Software Developer's Manual. Volume 3B: System Programming Guide, Part II, November 2007.
• 12: Venkata Krishnan , Josep Torrellas, A Chip-Multiprocessor Architecture with Speculative Multithreading, IEEE Transactions on Computers, v.48 n.9, p.866-880, September 1999 [doi>10.1109/12.795218]
• 13: Jin Lin , Tong Chen , Wei-Chung Hsu , Pen-Chung Yew, Speculative register promotion using Advanced Load Address Table (ALAT), Proceedings of the international symposium on Code generation and optimization: feedback-directed and runtime optimization, March 23-26, 2003, San Francisco, California
• 14: Mikko H. Lipasti , Christopher B. Wilkerson , John Paul Shen, Value locality and load value prediction, Proceedings of the seventh international conference on Architectural support for programming languages and operating systems, p.138-147, October 01-04, 1996, Cambridge, Massachusetts, United States
• 15: Mikko H. Lipasti , John Paul Shen, Exceeding the dataflow limit via value prediction, Proceedings of the 29th annual ACM/IEEE international symposium on Microarchitecture, p.226-237, December 02-04, 1996, Paris, France
• 16: Chi-Keung Luk , Robert Cohn , Robert Muth , Harish Patil , Artur Klauser , Geoff Lowney , Steven Wallace , Vijay Janapa Reddi , Kim Hazelwood, Pin: building customized program analysis tools with dynamic instrumentation, Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementation, June 12-15, 2005, Chicago, IL, USA
• 17: D. Michie, ""Memo" Functions and Machine Learning," in Nature, April 1968.
• 18: Chi Cao Minh , Martin Trautmann , JaeWoong Chung , Austen McDonald , Nathan Bronson , Jared Casper , Christos Kozyrakis , Kunle Olukotun, An effective hybrid transactional memory system with strong isolation guarantees, Proceedings of the 34th annual international symposium on Computer architecture, June 09-13, 2007, San Diego, California, USA
• 19: Andreas Moshovos , Gokhan Memik , Alok Choudhary , Babak Falsafi, JETTY: Filtering Snoops for Reduced Energy Consumption in SMP Servers, Proceedings of the 7th International Symposium on High-Performance Computer Architecture, p.85, January 20-24, 2001
• 20: Naveen Neelakantam , Ravi Rajwar , Suresh Srinivas , Uma Srinivasan , Craig Zilles, Hardware atomicity for reliable software speculation, Proceedings of the 34th annual international symposium on Computer architecture, June 09-13, 2007, San Diego, California, USA
• 21: Jih-Kwon Peir , Shih-Chang Lai , Shih-Lien Lu , Jared Stark , Konrad Lai, Bloom filtering cache misses for accurate data speculation and prefetching, Proceedings of the 16th international conference on Supercomputing, June 22-26, 2002, New York, New York, USA [doi>10.1145/514191.514219]
• 22: Matthew Postiff , David Greene , Trevor Mudge, The store-load address table and speculative register promotion, Proceedings of the 33rd annual ACM/IEEE international symposium on Microarchitecture, p.235-244, December 2000, Monterey, California, United States [doi>10.1145/360128.360152]
• 23: J. Renau, B. Fraguela, J. Tuck, W. Liu, M. Prvulovic, L. Ceze, S. Sarangi, P. Sack, K. Strauss, and P. Montesinos, "SESC Simulator," January 2005. http://sesc.sourceforge.net.
• 24: S. Sastry, R. Bodik, and J. Smith, "Characterizing Coarse-Grained Reuse of Computation," in Workshop on Feedback-Directed and Dynamic Optmization, 2000.
• 25: Simha Sethumadhavan , Rajagopalan Desikan , Doug Burger , Charles R. Moore , Stephen W. Keckler, Scalable Hardware Memory Disambiguation for High ILP Processors, Proceedings of the 36th annual IEEE/ACM International Symposium on Microarchitecture, p.399, December 03-05, 2003
• 26: Avinash Sodani , Gurindar S. Sohi, Dynamic instruction reuse, Proceedings of the 24th annual international symposium on Computer architecture, p.194-205, June 01-04, 1997, Denver, Colorado, United States
• 27: Avinash Sodani , Gurindar S. Sohi, An empirical analysis of instruction repetition, Proceedings of the eighth international conference on Architectural support for programming languages and operating systems, p.35-45, October 02-07, 1998, San Jose, California, United States
• 28: Gurindar S. Sohi , Scott E. Breach , T. N. Vijaykumar, Multiscalar processors, Proceedings of the 22nd annual international symposium on Computer architecture, p.414-425, June 22-24, 1995, S. Margherita Ligure, Italy
• 29: Bogong Su , Stanley Habib , Wei Zhao , Jian Wang , Youfeng Wu, A study of pointer aliasing for software pipelining using run-time disambiguation, Proceedings of the 27th annual international symposium on Microarchitecture, p.112-117, November 30-December 02, 1994, San Jose, California, United States [doi>10.1145/192724.192738]
• 30: Youfeng Wu , Dong-Yuan Chen , Jesse Fang, Better exploration of region-level value locality with integrated computation reuse and value prediction, Proceedings of the 28th annual international symposium on Computer architecture, p.98-108, June 30-July 04, 2001, Göteborg, Sweden
• 31: Luke Yen , Jayaram Bobba , Michael R. Marty , Kevin E. Moore , Haris Volos , Mark D. Hill , Michael M. Swift , David A. Wood, LogTM-SE: Decoupling Hardware Transactional Memory from Caches, Proceedings of the 2007 IEEE 13th International Symposium on High Performance Computer Architecture, p.261-272, February 10-14, 2007 [doi>10.1109/HPCA.2007.346204]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.0 GENERAL

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.0 General

General Terms:
Design, Performance

Keywords:
memory disambiguation, multi-core architectures, runtime optimization