Techniques for efficient inline tracing on a shared-memory multiprocessor

ABSTRACT

While much current research concerns multiprocessor design, few traces of parallel programs are available for analyzing the effect of design trade-offs. Existing trace collection methods have serious drawbacks: trap-driven methods often slow down program execution by more than 1000 times, significantly perturbing program behavior; microcode modification is faster, but the technique is neither general nor portable. This paper describes a new tool, called MPTRACE, for collecting traces of multithreaded parallel programs executing on shared-memory multiprocessors. MPTRACE requires no hardware or microcode modification; it collects complete program traces; it is portable; and it reduces execution-time dilation to less than a factor 3. MPTRACE is based on inline tracing, in which a program is automatically modified to produce trace information as it executes. We show how the use of compiler flow analysis techniques can reduce the amount of data collected and therefore the runtime dilation of the traced program. We also discuss problematic issues concerning buffering and writing of trace data on a multiprocessor.

REFERENCES

• Agarwal et al. 86: A. Agarwal , R. L. Sites , M. Horowitz, ATUM: a new technique for capturing address traces using microcode, Proceedings of the 13th annual international symposium on Computer architecture, p.119-127, June 02-05, 1986, Tokyo, Japan
• Bershad et al. 88: Brian N. Bershad , Edward D. Lazowska , Henry M. Levy, PRESTO: a system for object-oriented parallel programming, Software—Practice & Experience, v.18 n.8, p.713-732, August 1988 [doi>10.1002/spe.4380180802]
• Borg et al. 89: A. Borg, R. Kessler, G. Lazana, and D. W. Wall. Long address traces from RISC machines" Generation and analysis. Technical Report 89/14, Digtal Equipment Corporation Western Research Laboratory, P alo Alto, CA, September 1989.
• Devadas & Newton 87: S. Devadas and A. Newton. Topological optimization of multiple level array logic. IEEE Transactions on Computer-Aided Design, November 1987.
• Eggers & Katz 89: S. J. Eggers , R. H. Katz, The effect of sharing on the cache and bus performance of parallel programs, Proceedings of the third international conference on Architectural support for programming languages and operating systems, p.257-270, April 03-06, 1989, Boston, Massachusetts, United States
• Hill 87: Mark Donald Hill , Alan Jay Smith, Aspects of cache memory and instruction buffer performance, 1987
• Lovett & Thakkar 88: R. Lovett and S. Thakkar. The Symmetry multiprocessory system. In Proceedings of the 1988 international Conference on Parallel Processing, pages 303-310, August 1988.
• Ma et al. 87: H.-K. T. Ma , S. Devadas , A. Sangiovanni-Vincentelli , R. Wei, Logic verification algorithms and their parallel implementation, Proceedings of the 24th ACM/IEEE conference on Design automation, p.283-290, June 28-July 01, 1987, Miami Beach, Florida, United States [doi>10.1145/37888.37931]
• Mellor-Crummey & LeBlanc 89: J. M. Mellor-Crummey , T. J. LeBlanc, A software instruction counter, Proceedings of the third international conference on Architectural support for programming languages and operating systems, p.78-86, April 03-06, 1989, Boston, Massachusetts, United States
• MIPS 86: MIPS. Languages and Programmer's Manual. MIPS Computer Systems, Inc., 1986.
• Przybylski et al. 88: S. Prybylski , M. Horowitz , J. Hennessy, Performance tradeoffs in cache design, Proceedings of the 15th Annual International Symposium on Computer architecture, p.290-298, May 30-June 02, 1988, Honolulu, Hawaii, United States
• Shustek 78: Leonard Jay Shustek, Analysis and performance of computer instruction sets., 1978
• Sites & Agarwal 88: R. L. Sites , A. Agarwal, Multiprocessor cache analysis using ATUM, Proceedings of the 15th Annual International Symposium on Computer architecture, p.186-195, May 30-June 02, 1988, Honolulu, Hawaii, United States
• Smith 82: Alan Jay Smith, Cache Memories, ACM Computing Surveys (CSUR), v.14 n.3, p.473-530, Sept. 1982 [doi>10.1145/356887.356892]
• Stunkel & Fuchs 89: C. B. Stunkel , W. K. Fuchs, TRAPEDS: producing traces for multicomputers via execution driven simulation, Proceedings of the 1989 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.70-78, May 23-26, 1989, Oakland, California, United States
• Wiecek 82: Cheryl A. Wiecek, A case study of VAX-11 instruction set usage for compiler execution, Proceedings of the first international symposium on Architectural support for programming languages and operating systems, p.177-184, March 01-03, 1982, Palo Alto, California, United States

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES

Additional Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.2 Design Styles
          Subjects: Cache memories; Shared memory

  D. Software
  D.1 PROGRAMMING TECHNIQUES
  D.2 SOFTWARE ENGINEERING
      D.2.5 Testing and Debugging
          Subjects: Tracing
      D.2.8 Metrics
          Subjects: Performance measures

General Terms:
Design, Measurement, Performance