Visualizing potential parallelism in sequential programs

ABSTRACT

This paper presents ParaMeter, an interactive program analysis and visualization system for large traces. Using ParaMeter, a software developer can locate and analyze regions of code that may yield to parallelization efforts and to possibly extract performance from multicore hardware. The key contributions in the paper are (1) a method to use interactive visualization of traces to find and exploit parallelism, (2) interactive-speed visualization of large-scale trace dependencies, (3) interactive-speed visualization of code interactions, and (4) a BDD variable ordering for DD-compressed traces that results in fast visualization, fast analysis, and good compression. ParaMeter's effectiveness is demonstrated by finding and exploiting parallelism in 175.vpr. Measurements of ParaMeter's visualization algorithms show that they are up to seventy-five thousand times faster than prior approaches.

REFERENCES

• 1: Saman Amarasinghe, Multicores from the Compiler's Perspective: A Blessing or a Curse?, Proceedings of the international symposium on Code generation and optimization, p.137-137, March 20-23, 2005 [doi>10.1109/CGO.2005.22]
• 2: Todd M. Austin , Gurindar S. Sohi, Dynamic dependency analysis of ordinary programs, Proceedings of the 19th annual international symposium on Computer architecture, p.342-351, May 19-21, 1992, Queensland, Australia
• 3: Robert K. Brayton , Gary D. Hachtel , Alberto L. Sangiovanni-Vincentelli , Fabio Somenzi , Adnan Aziz , Szu-Tsung Cheng , Stephen A. Edwards , Sunil P. Khatri , Yuji Kukimoto , Abelardo Pardo , Shaz Qadeer , Rajeev K. Ranjan , Shaker Sarwary , Thomas R. Shiple , Gitanjali Swamy , Tiziano Villa, VIS: A System for Verification and Synthesis, Proceedings of the 8th International Conference on Computer Aided Verification, p.428-432, August 03, 1996
• 4: Randal E. Bryant, Graph-Based Algorithms for Boolean Function Manipulation, IEEE Transactions on Computers, v.35 n.8, p.677-691, August 1986 [doi>10.1109/TC.1986.1676819]
• 5: Martin Burtscher , Nana B. Sam, Automatic Generation of High-Performance Trace Compressors, Proceedings of the international symposium on Code generation and optimization, p.229-240, March 20-23, 2005 [doi>10.1109/CGO.2005.6]
• 6: John Giacomoni , Tipp Moseley , Manish Vachharajani, FastForward for efficient pipeline parallelism: a cache-optimized concurrent lock-free queue, Proceedings of the 13th ACM SIGPLAN Symposium on Principles and practice of parallel programming, February 20-23, 2008, Salt Lake City, UT, USA [doi>10.1145/1345206.1345215]
• 7: Justin E. Harlow, III , Franc Brglez, Design of experiments in BDD variable ordering: lessons learned, Proceedings of the 1998 IEEE/ACM international conference on Computer-aided design, p.646-652, November 08-12, 1998, San Jose, California, United States [doi>10.1145/288548.289103]
• 8: IYER, M., ASHOK, C., STONE, J., VACHHARAJANI, N., CONNORS, D. A., AND VACHHARAJANI, M. Finding parallelism for future EPIC machines. In Proceedings of the 4th Workshop on Explicitly Parallel Instruction Computing Techniques (EPIC) (March 2005).
• 9: JEONG, S.-W., PLESSIER, B., HACHTEL, G., AND SOMENZI, F. Variable ordering for binary decision diagrams. In Proceedings of the 3rd European Design Automation Conference (1992), pp. 447--451.
• 10: Monica S. Lam , Robert P. Wilson, Limits of control flow on parallelism, Proceedings of the 19th annual international symposium on Computer architecture, p.46-57, May 19-21, 1992, Queensland, Australia
• 11: James R. Larus, Whole program paths, Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation, p.259-269, May 01-04, 1999, Atlanta, Georgia, United States
• 12: Guilherme Ottoni , Ram Rangan , Adam Stoler , David I. August, Automatic Thread Extraction with Decoupled Software Pipelining, Proceedings of the 38th annual IEEE/ACM International Symposium on Microarchitecture, p.105-118, November 12-16, 2005, Barcelona, Spain [doi>10.1109/MICRO.2005.13]
• 13: POSTIFF, M., TYSON, G., AND MUDGE, T. Performance limits of trace caches. Tech. Rep. CSE-TR-373-98, University of Maryland, Department of Electrical Engineering and Computer Science, CSE, September 1998.
• 14: Graham Price , Manish Vachharajani, A Case for Compressing Traces with BDDs, IEEE Computer Architecture Letters, v.5 n.2, p.18, July 2006 [doi>10.1109/L-CA.2006.17]
• 15: Ram Rangan , Neil Vachharajani , Manish Vachharajani , David I. August, Decoupled Software Pipelining with the Synchronization Array, Proceedings of the 13th International Conference on Parallel Architectures and Compilation Techniques, p.177-188, September 29-October 03, 2004 [doi>10.1109/PACT.2004.14]
• 16: Richard Rudell, Dynamic variable ordering for ordered binary decision diagrams, Proceedings of the 1993 IEEE/ACM international conference on Computer-aided design, p.42-47, November 07-11, 1993, Santa Clara, California, United States
• 17: SOMENZI, F. CUDD: Colorado University Decision Diagram package, release 2.30. Tech. rep., University of Colorado at Boulder, http://vlsi.colorado.edu/~fabio/CUDD/, 1998.
• 18: VACHHARAJANI, N., IYER, M., ASHOK, C., VACHHARAJANI, M., AUGUST, D. I., AND CONNORS, D. A. Chip multi-processor scalability for single-threaded applications. In Proceedings of the 2005 Workshop on Design, Architecture and Simulation of Chip Multi-Processors (dasCMP) (November 2005).
• 19: WALL, D. W. Limits of instruction-level parallelism. Tech. Rep. 93/6, DEC WRL, November 1993.
• 20: John Whaley , Monica S. Lam, Cloning-based context-sensitive pointer alias analysis using binary decision diagrams, Proceedings of the ACM SIGPLAN 2004 conference on Programming language design and implementation, June 09-11, 2004, Washington DC, USA
• 21: Xiangyu Zhang , Rajiv Gupta , Youtao Zhang, Precise dynamic slicing algorithms, Proceedings of the 25th International Conference on Software Engineering, May 03-10, 2003, Portland, Oregon
• 22: Xiangyu Zhang , Rajiv Gupta , Youtao Zhang, Efficient Forward Computation of Dynamic Slices Using Reduced Ordered Binary Decision Diagrams, Proceedings of the 26th International Conference on Software Engineering, p.502-511, May 23-28, 2004
• 23: 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

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.2 Design Tools and Techniques

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming

General Terms:
Performance

Keywords:
parallel programming, thread extraction, visualization