Communication optimizations for global multi-threaded instruction scheduling

ABSTRACT

The recent shift in the industry towards chip multiprocessor (CMP) designs has brought the need for multi-threaded applications to mainstream computing. As observed in several limit studies, most of the parallelization opportunities require looking for parallelism beyond local regions of code. To exploit these opportunities, especially for sequential applications, researchers have recently proposed global multi-threaded instruction scheduling techniques, including DSWP and GREMIO. These techniques simultaneously schedule instructions from large regions of code, such as arbitrary loop nests or whole procedures, and have been shown to be effective at extracting threads for many applications. A key enabler of these global instruction scheduling techniques is the Multi-Threaded Code Generation (MTCG) algorithm proposed in [16], which generates multi-threaded code for any partition of the instructions into threads. This algorithm inserts communication and synchronization instructions in order to satisfy all inter-thread dependences.

In this paper, we present a general compiler framework, COCO, to optimize the communication and synchronization instructions inserted by the MTCG algorithm. This framework, based on thread-aware data-flow analyses and graph min-cut algorithms, appropriately models andoptimizes all kinds of inter-thread dependences, including register, memory, and control dependences. Our experiments, using a fully automatic compiler implementation of these techniques, demonstrate significant reductions (about 30% on average) in the number of dynamic communication instructions in code parallelized with DSWP and GREMIO. This reduction in communication translates to performance gains of up to 40%.

REFERENCES

• 1: Saman P. Amarasinghe , Monica S. Lam, Communication optimization and code generation for distributed memory machines, Proceedings of the ACM SIGPLAN 1993 conference on Programming language design and implementation, p.126-138, June 21-25, 1993, Albuquerque, New Mexico, United States
• 2: Andrea Capitanio , Nikil Dutt , Alexandru Nicolau, Partitioned register files for VLIWs: a preliminary analysis of tradeoffs, Proceedings of the 25th annual international symposium on Microarchitecture, p.292-300, December 01-04, 1992, Portland, Oregon, United States
• 3: Soumen Chakrabarti , Manish Gupta , Jong-Deok Choi, Global communication analysis and optimization, Proceedings of the ACM SIGPLAN 1996 conference on Programming language design and implementation, p.68-78, May 21-24, 1996, Philadelphia, Pennsylvania, United States
• 4: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 5: Jeanne Ferrante , Karl J. Ottenstein , Joe D. Warren, The program dependence graph and its use in optimization, ACM Transactions on Programming Languages and Systems (TOPLAS), v.9 n.3, p.319-349, July 1987 [doi>10.1145/24039.24041]
• 6: L. R. Ford, Jr. and D. R. Fulkerson. Flows in Networks. Princeton University Press, 1962.
• 7: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 8: M. Kandemir , P. Banerjee , A. Choudhary , J. Ramanujam , N. Shenoy, A global communication optimization technique based on data-flow analysis and linear algebra, ACM Transactions on Programming Languages and Systems (TOPLAS), v.21 n.6, p.1251-1297, Nov. 1999 [doi>10.1145/330643.330647]
• 9: Jens Knoop , Oliver Rüthing , Bernhard Steffen, Lazy code motion, Proceedings of the ACM SIGPLAN 1992 conference on Programming language design and implementation, p.224-234, June 15-19, 1992, San Francisco, California, United States
• 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: Walter Lee , Rajeev Barua , Matthew Frank , Devabhaktuni Srikrishna , Jonathan Babb , Vivek Sarkar , Saman Amarasinghe, Space-time scheduling of instruction-level parallelism on a raw machine, Proceedings of the eighth international conference on Architectural support for programming languages and operating systems, p.46-57, October 02-07, 1998, San Jose, California, United States
• 12: Walter Lee , Diego Puppin , Shane Swenson , Saman Amarasinghe, Convergent scheduling, Proceedings of the 35th annual ACM/IEEE international symposium on Microarchitecture, November 18-22, 2002, Istanbul, Turkey
• 13: Erik Nystrom , Alexandre E. Eichenberger, Effective cluster assignment for modulo scheduling, Proceedings of the 31st annual ACM/IEEE international symposium on Microarchitecture, p.103-114, November 1998, Dallas, Texas, United States
• 14: E. M. Nystrom, H.-S. Kim, and W.-M. Hwu. Bottom-up and top-down context-sensitive summary-based pointer analysis. In Proceedings of the 11th Static Analysis Symposium, August 2004.
• 15: Guilherme Ottoni , David August, Global Multi-Threaded Instruction Scheduling, Proceedings of the 40th Annual IEEE/ACM International Symposium on Microarchitecture, p.56-68, December 01-05, 2007 [doi>10.1109/MICRO.2007.17]
• 16: 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]
• 17: D. A. Penry, M. Vachharajani, and D. I. August. Rapid development of a flexible validated processor model. In Proceedings of the 2005 Workshop on Modeling, Benchmarking, and Simulation, June 2005.
• 18: Ram Rangan , Neil Vachharajani , Adam Stoler , Guilherme Ottoni , David I. August , George Z. N. Cai, Support for High-Frequency Streaming in CMPs, Proceedings of the 39th Annual IEEE/ACM International Symposium on Microarchitecture, p.259-272, December 09-13, 2006 [doi>10.1109/MICRO.2006.47]
• 19: 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]
• 20: Kevin D. Rich , Matthew K. Farrens, Code Partitioning in Decoupled Compilers, Proceedings from the 6th International Euro-Par Conference on Parallel Processing, p.1008-1017, August 29-September 01, 2000
• 21: Vivek Sarkar, A Concurrent Execution Semantics for Parallel Program Graphs and Program Dependence Graphs, Proceedings of the 5th International Workshop on Languages and Compilers for Parallel Computing, p.16-30, August 03-05, 1992
• 22: John W. Sias , Sain-zee Ueng , Geoff A. Kent , Ian M. Steiner , Erik M. Nystrom , Wen-mei W. Hwu, Field-testing IMPACT EPIC research results in Itanium 2, Proceedings of the 31st annual international symposium on Computer architecture, p.26, June 19-23, 2004, München, Germany
• 23: 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
• 24: Michael Bedford Taylor , Walter Lee , Saman P. Amarasinghe , Anant Agarwal, Scalar Operand Networks, IEEE Transactions on Parallel and Distributed Systems, v.16 n.2, p.145-162, February 2005 [doi>10.1109/TPDS.2005.24]
• 25: Spyridon Triantafyllis , Matthew J. Bridges , Easwaran Raman , Guilherme Ottoni , David I. August, A framework for unrestricted whole-program optimization, Proceedings of the 2006 ACM SIGPLAN conference on Programming language design and implementation, June 11-14, 2006, Ottawa, Ontario, Canada
• 26: N. Vachharajani, M. Iyer, C. Ashok, M. Vachharajani, D. I. August, and D. A. Connors. Chip multi-processor scalability for single-threaded applications. In Proceedings of the Workshop on Design, Architecture, and Simulation of Chip Multi-Processors, November 2005.
• 27: Neil Vachharajani , Ram Rangan , Easwaran Raman , Matthew J. Bridges , Guilherme Ottoni , David I. August, Speculative Decoupled Software Pipelining, Proceedings of the 16th International Conference on Parallel Architecture and Compilation Techniques, p.49-59, September 15-19, 2007 [doi>10.1109/PACT.2007.66]
• 28: Youfeng Wu , James R. Larus, Static branch frequency and program profile analysis, Proceedings of the 27th annual international symposium on Microarchitecture, p.1-11, November 30-December 02, 1994, San Jose, California, United States [doi>10.1145/192724.192725]
• 29: Javier Zalamea , Josep Llosa , Eduard Ayguadé , Mateo Valero, Modulo scheduling with integrated register spilling for clustered VLIW architectures, Proceedings of the 34th annual ACM/IEEE international symposium on Microarchitecture, December 01-05, 2001, Austin, Texas
• 30: 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
• 31: 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.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Code generation

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Multiple-instruction-stream, multiple-data-stream processors (MIMD)

  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Optimization; Compilers

General Terms:
Algorithms, Languages, Performance

Keywords:
communication, data-flow analysis, graph min-cut, instruction scheduling, multi-threading, synchronization