Implicitly parallel programming models for thousand-core microprocessors

ABSTRACT

This paper argues for an implicitly parallel programming model for many-core microprocessors, and provides initial technical approaches towards this goal. In an implicitly parallel programming model, programmers maximize algorithm-level parallelism, express their parallel algorithms by asserting high-level properties on top of a traditional sequential programming language, and rely on parallelizing compilers and hardware support to perform parallel execution under the hood. In such a model, compilers and related tools require much more advanced program analysis capabilities and programmer assertions than what are currently available so that a comprehensive understanding of the input program's concurrency can be derived. Such an understanding is then used to drive automatic or interactive parallel code generation tools for a diverse set of parallel hardware organizations. The chip-level architecture and hardware should maintain parallel execution state in such a way that a strictly sequential execution state can always be derived for the purpose of verifying and debugging the program. We argue that implicitly parallel programming models are critical for addressing the software development crises and software scalability challenges for many-core microprocessors.

REFERENCES

• 1: M. Barnett, K. R. M. Leino, and W. Schulte. The Spec# programming system: An overview. In Proc. of Construction and Analysis of Safe, Secure and Interoperable Smart Devices, volume 3362 of LNCS, pages 49--69. Springer, March 2004.
• 2: F. Bodin, T. Kisuki, P. Knijnenburg, M. O'Boyle, and E. Rohou. Iterative compilation in a non-linear optimisation space. In Proceedings of the Workshop on Profile and Feedback-Directed Compilation, October 1998.
• 3: D. Carmean. The Pentium 4 processor. Hot Chips 13, Stanford University, Palo Alto, CA, August 2001.
• 4: David E. Culler , Anoop Gupta , Jaswinder Pal Singh, Parallel Computer Architecture: A Hardware/Software Approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1997
• 5: Datamonitor, 2006. http://www.datamonitor.com.
• 6: Richard A. Hankins , Gautham N. Chinya , Jamison D. Collins , Perry H. Wang , Ryan Rakvic , Hong Wang , John P. Shen, Multiple Instruction Stream Processor, Proceedings of the 33rd annual international symposium on Computer Architecture, p.114-127, June 17-21, 2006
• 7: CORPORATE IEEE, Inc. Staff, Information Technology-Portable Operating System Interface, IEEE Standards Office, New York, NY, 1990
• 8: T. G. Mattson, B. A. Sanders, and B. L. Massingill. Patterns for Parallel Programming. Addison-Wesley Professional, 2004.
• 9: Cameron McNairy , Don Soltis, Itanium 2 Processor Microarchitecture, IEEE Micro, v.23 n.2, p.44-55, March 2003 [doi>10.1109/MM.2003.1196114]
• 10: Message Passing Interface Forum. MPI-2: extensions to the message-passing interface, July 1997.
• 11: N. Mitchell. Philips TriMedia: A digital media convergence platform. In Proceedings of WESCON, pages 56--60, November 1997.
• 12: G. E. Moore. Cramming more components onto integrated circuits. Electronics, April 1965.
• 13: NVIDIA Corporation. CUDA Programming Guide, February 2007.
• 14: OpenMP Architecture Review Board. OpenMP application program interface, May 2005.
• 15: Gregory F. Pfister, In search of clusters (2nd ed.), Prentice-Hall, Inc., Upper Saddle River, NJ, 1998
• 16: William Pugh, The Omega test: a fast and practical integer programming algorithm for dependence analysis, Proceedings of the 1991 ACM/IEEE conference on Supercomputing, p.4-13, November 18-22, 1991, Albuquerque, New Mexico, United States [doi>10.1145/125826.125848]
• 17: S. Ryoo, S.-Z. Ueng, C. I. Rodrigues, R. E. Kidd, M. I. Frank, and W. W. Hwu. Automatic Discovery of Coarse-Grained Parallelism in Media Applications. Transactions on HiPEAC I, LNCS 4050, 2007.
• 18: A. Sangiovanni-Vincentelli. Defining platform-based design. EEDesign of EETimes, February 2002.
• 19: Niraj Shah , William Plishker , Kaushik Ravindran , Kurt Keutzer, NP-Click: A Productive Software Development Approach for Network Processors, IEEE Micro, v.24 n.5, p.45-54, September 2004 [doi>10.1109/MM.2004.53]
• 20: Sun Microsystems. Java. http://java.sun.com.
• 21: William Thies , Michal Karczmarek , Saman P. Amarasinghe, StreamIt: A Language for Streaming Applications, Proceedings of the 11th International Conference on Compiler Construction, p.179-196, April 08-12, 2002
• 22: Spyridon Triantafyllis , Manish Vachharajani , Neil Vachharajani , David I. August, Compiler optimization-space exploration, Proceedings of the international symposium on Code generation and optimization: feedback-directed and runtime optimization, March 23-26, 2003, San Francisco, California
• 23: J. Turley and H. Hakkarainen. TI's new 'C6x DSP screams at 1,600 MIPS. Microprocessor Report, 11(2):14--17, February 1997.
• 24: Hongtao Zhong , Steven A. Lieberman , Scott A. Mahlke, Extending Multicore Architectures to Exploit Hybrid Parallelism in Single-thread Applications, Proceedings of the 2007 IEEE 13th International Symposium on High Performance Computer Architecture, p.25-36, February 10-14, 2007 [doi>10.1109/HPCA.2007.346182]

INDEX TERMS

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

General Terms:
Design, Human Factors, Languages

Keywords:
parallel programming