Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

Fast track is a software speculation system that enables unsafe optimization of sequential code. It speculatively runs optimized code to improve performance and then checks the correctness of the speculative code by running the original program on multiple processors. We present the interface design and system implementation for Fast Track. It lets a programmer or a profiling tool mark fast-track code regions and uses a run-time system to manage the parallel execution of the speculative process and its checking processes and ensures the correct display of program outputs. The core of the run-time system is a novel concurrent algorithm that balances exploitable parallelism and available processors when the fast track is too slow or too fast. The programming interface closely affects the run-time support. Our system permits both explicit and implicit end markers for speculatively optimized code regions as well as extensions that allow the use of multiple tracks and user defined correctness checking. We discuss the possible uses of speculative optimization and demonstrate the effectiveness of our prototype system by examples of unsafe semantic optimization and a general system for fast memory-safety checking, which is able to reduce the checking time by factors between 2 and 7 for large sequential code on a 8-CPU system.

REFERENCES

• 1: Lawrence Rauchwerger , David Padua, The LRPD test: speculative run-time parallelization of loops with privatization and reduction parallelization, Proceedings of the ACM SIGPLAN 1995 conference on Programming language design and implementation, p.218-232, June 18-21, 1995, La Jolla, California, United States
• 2: Manish Gupta , Rahul Nim, Techniques for speculative run-time parallelization of loops, Proceedings of the 1998 ACM/IEEE conference on Supercomputing (CDROM), p.1-12, November 07-13, 1998, San Jose, CA
• 3: Marcelo Cintra , Diego R. Llanos, Design Space Exploration of a Software Speculative Parallelization Scheme, IEEE Transactions on Parallel and Distributed Systems, v.16 n.6, p.562-576, June 2005 [doi>10.1109/TPDS.2005.69]
• 4: Chen Ding , Xipeng Shen , Kirk Kelsey , Chris Tice , Ruke Huang , Chengliang Zhang, Software behavior oriented parallelization, Proceedings of the 2007 ACM SIGPLAN conference on Programming language design and implementation, June 10-13, 2007, San Diego, California, USA
• 5: Chen Tian , Min Feng , Vijay Nagarajan , Rajiv Gupta, Copy or Discard execution model for speculative parallelization on multicores, Proceedings of the 2008 41st IEEE/ACM International Symposium on Microarchitecture, p.330-341, November 08-12, 2008 [doi>10.1109/MICRO.2008.4771802]
• 6: Craig Zilles , Gurindar Sohi, Master/slave speculative parallelization, Proceedings of the 35th annual ACM/IEEE international symposium on Microarchitecture, November 18-22, 2002, Istanbul, Turkey
• 7: Antonia Zhai , Christopher B. Colohan , J. Gregory Steffan , Todd C. Mowry, Compiler optimization of scalar value communication between speculative threads, Proceedings of the 10th international conference on Architectural support for programming languages and operating systems, October 05-09, 2002, San Jose, California
• 8: Carlos García Quiñones , Carlos Madriles , Jesús Sánchez , Pedro Marcuello , Antonio González , Dean M. Tullsen, Mitosis compiler: an infrastructure for speculative threading based on pre-computation slices, Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementation, June 12-15, 2005, Chicago, IL, USA
• 9: 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
• 10: Ken Kennedy , John R. Allen, Optimizing compilers for modern architectures: a dependence-based approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2001
• 11: Chengliang Zhang , Kirk Kelsey , Xipeng Shen , Chen Ding , Matthew Hertz , Mitsunori Ogihara, Program-level adaptive memory management, Proceedings of the 5th international symposium on Memory management, June 10-11, 2006, Ottawa, Ontario, Canada [doi>10.1145/1133956.1133979]
• 12: Chris Grzegorczyk , Sunil Soman , Chandra Krintz , Rich Wolski, Isla Vista Heap Sizing: Using Feedback to Avoid Paging, Proceedings of the International Symposium on Code Generation and Optimization, p.325-340, March 11-14, 2007 [doi>10.1109/CGO.2007.20]
• 13: D. Michie, "Memo functions and machine learning," Nature, vol. 218, pp. 19-22, 1968.
• 14: 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
• 15: 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
• 16: Tipp Moseley , Alex Shye , Vijay Janapa Reddi , Dirk Grunwald , Ramesh Peri, Shadow Profiling: Hiding Instrumentation Costs with Parallelism, Proceedings of the International Symposium on Code Generation and Optimization, p.198-208, March 11-14, 2007 [doi>10.1109/CGO.2007.35]
• 17: Steven Wallace , Kim Hazelwood, SuperPin: Parallelizing Dynamic Instrumentation for Real-Time Performance, Proceedings of the International Symposium on Code Generation and Optimization, p.209-220, March 11-14, 2007 [doi>10.1109/CGO.2007.37]
• 18: Edmund B. Nightingale , Daniel Peek , Peter M. Chen , Jason Flinn, Parallelizing security checks on commodity hardware, Proceedings of the 13th international conference on Architectural support for programming languages and operating systems, March 01-05, 2008, Seattle, WA, USA
• 19: H. Patil and C. Fischer, "Efcient run-time monitoring using shadow processing," 1995, presented at AADEBUG'95.
• 20: Jenn-Yuan Tsai , Zhenzhen Jiang , Pen-Chung Yew, Compiler Techniques for the Superthreaded Architectures, International Journal of Parallel Programming, v.27 n.1, p.1-19, Feb. 1999 [doi>10.1023/A:1018730501763]
• 21: Karthik Sundaramoorthy , Zach Purser , Eric Rotenburg, Slipstream processors: improving both performance and fault tolerance, Proceedings of the ninth international conference on Architectural support for programming languages and operating systems, p.257-268, November 2000, Cambridge, Massachusetts, United States
• 22: Steve S.W. Liao , Perry H. Wang , Hong Wang , Gerolf Hoflehner , Daniel Lavery , John P. Shen, Post-pass binary adaptation for software-based speculative precomputation, Proceedings of the ACM SIGPLAN 2002 Conference on Programming language design and implementation, June 17-19, 2002, Berlin, Germany
• 23: Alok Garg , Michael C. Huang, A performance-correctness explicitly-decoupled architecture, Proceedings of the 2008 41st IEEE/ACM International Symposium on Microarchitecture, p.306-317, November 08-12, 2008 [doi>10.1109/MICRO.2008.4771800]
• 24: Jeffrey Oplinger , Monica S. Lam, Enhancing software reliability with speculative threads, Proceedings of the 10th international conference on Architectural support for programming languages and operating systems, October 05-09, 2002, San Jose, California
• 25: Pin Zhou , Feng Qin , Wei Liu , Yuanyuan Zhou , Josep Torrellas, iWatcher: Efficient Architectural Support for Software Debugging, Proceedings of the 31st annual international symposium on Computer architecture, p.224, June 19-23, 2004, München, Germany
• 26: S. Lee and J. Tuck, "Parallelizing Mudflap using thread-level speculation on a CMP," 2008, presented at the Workshop on the Parallel Execution of Sequential Programs on Multicore Architecture, co-located with ISCA.
• 27: J. Mellor-Crummey, "Compile-time support for efficient data race detection in shared memory parallel programs," Rice University, Tech. Rep. CRPC-TR92232, September 1992.
• 28: Dejan Perkovic , Peter J. Keleher, A Protocol-Centric Approach to on-the-Fly Race Detection, IEEE Transactions on Parallel and Distributed Systems, v.11 n.10, p.1058-1072, October 2000 [doi>10.1109/71.888645]
• 29: Robert Wahbe , Steven Lucco , Susan L. Graham, Practical data breakpoints: design and implementation, Proceedings of the ACM SIGPLAN 1993 conference on Programming language design and implementation, p.1-12, June 21-25, 1993, Albuquerque, New Mexico, United States
• 30: Chen Ding , Ken Kennedy, Improving cache performance in dynamic applications through data and computation reorganization at run time, Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation, p.229-241, May 01-04, 1999, Atlanta, Georgia, United States
• 31: Matthew Arnold , Barbara G. Ryder, A framework for reducing the cost of instrumented code, Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation, p.168-179, June 2001, Snowbird, Utah, United States
• 32: Trishul M. Chilimbi , Martin Hirzel, Dynamic hot data stream prefetching for general-purpose programs, Proceedings of the ACM SIGPLAN 2002 Conference on Programming language design and implementation, June 17-19, 2002, Berlin, Germany
• 33: Kai Li, Shared virtual memory on loosely coupled multiprocessors, Yale University, New Haven, CT, 1986
• 34: Pete Keleher , Alan L. Cox , Sandhya Dwarkadas , Willy Zwaenepoel, TreadMarks: distributed shared memory on standard workstations and operating systems, Proceedings of the USENIX Winter 1994 Technical Conference on USENIX Winter 1994 Technical Conference, p.10-10, January 17-21, 1994, San Francisco, California

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Optimization

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

General Terms:
Design, Experimentation, Measurement, Performance