Parallel programming for non-parallel programmers
We believe that in the long run, for general-purpose parallel programming (i.e., arbitrary programs written by ordinary programmers), the language must make it effortless to express huge amounts of parallelism. The reasons are twofold:

1) No matter what architectural support there may be for shared-memory, movement of data across the machine will always be slow, compared to instruction execution times and local memory access times. Abundant parallelism permits the processor to perform useful work on one thread while another may be waiting for data to be moved.

This is analogous to the situation in operating systems today: when one process encounters a page fault, the processor switches to another process while the first one waits for the page to arrive from disk.

2) In arbitrary parallel programs, synchronization waits (waiting to acquire a lock) are as unpredictable as nonlocal memory accesses; again, we need an adequate number of threads so that the processor can continue useful work while some are waiting for synchronization events.

Since manual synchronization in the face of massive parallelism is too tedious to be feasible (except for programs with extremely simple, rigid; structures), this, too, is something that the programmer should not have to manage explicitly.

The bottom line is that for general-purpose, scalable, parallel computing, architectures need to support fine-grain threads with fine-grain synchronization, and programming languages and implementations need to exploit this capability.

Although these architectural features will benefit all parallel programming languages, existing languages do not make it easy to express or to exploit fine-grain parallelism. Declarative programming languages such as pH appear to be most promising approach towards this goal.

Next in Part 8: Turning pH into a production programming language
To read Part 1, go to How sequential languages obscure parallelism.
To read Part 2, go to How to achieve parallel execution?
To read Part 3, go to Explicit Parallelism: Shared-Memory Programming with Threads and Locks
To read Part 4, go to Explicit Parallelism: Message-Passing programming
To read Part 5, go to Implicit parallelism: Declarative programming languages
To read Part 6, go to "So, why aren't we using functional languages yet?"

Rishiyur S. Nikhil and Arvind are the coauthors of Implicit Parallel Programming in pH, published by Elsevier/Morgan Kaufmann.

Rishiyur is Chief Technical Officer at ESL specialist Bluespec Inc. Previous to its acquisition by Broadcom he led the Bluespec technology team at Sandburst Corp. For the previous 9 years he was at Cambridge Research Laboratory (DEC/Compaq), including over a year as Acting Director. Earlier, he was an Associate Professor of Computer Science and Engineering at MIT. He holds several patents in functional programming, dataflow and multithreaded architectures, parallel processing and compiling.

Arvind is the Johnson Professor of Computer Science and Engineering at the Massachusetts Institute of Technology. His work laid the foundations for Bluespec, centering on high-level specification and description of architectures and protocols using Term Rewriting Systems (TRSs), encompassing hardware synthesis as well as verification of implementations against TRS specifications. Previously, he contributed to the development of dynamic dataflow architectures, the implicitly parallel programming languages Id and pH, and compilation of these languages on parallel machines. He was also president and founder of Sandburst Corp.

To read more on this topic on Embedded.com go to More about multicores, multithreading and multiprocessing.

References:
[1] "Microsoft: Parallel Programming Model Ten Years off," by Rick Merritt, Embedded.com, July 23, 2007
[2] "The Problem with Threads" by Edward A. Lee, IEEE Computer, 39:5, May 2006, pp 33-42
[3] "Why threads are a bad idea (for most purposes)," J.K. Ousterhout, Invited Talk, USENIX Technical Conference, January, 1996
[4] S. Ahuja, N. Carriero, and D. Gelernter. "Linda and Friends," IEEE Computer, 19(8):26-34, August 1986.
[5] Z. Ariola and Arvind. "Properties of a First-order Functional Language with Sharing." Theoretical Computer Science, 146(1-2):69-108, July 1995.
[6] J. Armstrong. "The Development of Erlang." In Proc. Intl. Conf. on Functional Programming (ICFP), Amsterdam, The Netherlands, pages 196-203, 1997.
[7] J. Armstrong, R. Virding, and M. Williams. "Concurrent Programming in Erlang." Prentice Hall, 1993. ISBN: 0-13-285792-8.
[8] K. Arnold and J. Gosling. The Java Programming Language, second edition. Addison-Wesley, 1998. ISBN 0-201-31006-6.
[9] Arvind, A. Caro, J.-W. Maessen, and S. Aditya. A Multithreaded Substrate and Compilation Model for the Implicitly Parallel Language pH. In Proc. Wkshp. on Languages and Compilers for Parallel Computing (LCPC), August 1996.
[10] Arvind, K. P. Gostelow, and W. Plouffe. The (preliminary) Id Report. Technical Report 114, Dept. of Information and Computer Science, Univ. of California, Irvine CA, USA, 1978.
[11] Arvind and R. S. Nikhil. Executing a Program on the MIT Tagged-Token Dataflow Architecture. IEEE Trans. on Computers, 39(3):300-318, March 1990.
[12] R. D. Blumofe, C. F. Joerg, B. C. Kuszmaul, C. E. Leiserson, K. H. Randall, and Y. Zhou. Cilk: An Efficient Multithreaded Runtime System. In Proc. 5th. ACM Symp. on Principles and Practice of Parallel Programming (PPOPP), Santa Barbara CA, USA, pages 207-216, July 19-21 1995.
[13] D. E. Culler, A. Dusseau, S. C. Goldstein, A. Krishnamurthy, S. Lumetta, T. von Eicken, and K. Yelick. Parallel Programming in Split-C. In Proc. Supercomputing 93, Portland OR, USA, November 1993.
[14] A. Geist, A. Begeulin, J. Dongarra, W. Jiang, R. Manchek, and V. S. Sundaram. PVM Parallel Virtual Machine. A User's Guide and Tutorial for Network Parallel Computing. MIT Press, Cambridge MA, USA, 1994.
[15] R. H. Halstead. Multilisp: A Language for Concurrent Symbolic Computation. ACM Trans. on Programming Languages and Systems (TOPLAS), 7(4):501-539, October 1985.
[16] High Performance Fortran Forum. High Performance Fortran Language Specification, Version 1.0. Technical Report CRPC-TR92225, Center for Research on Parallel Computation, Rice University, Houston TX, USA, May 3 1993.
[17] C. Hoare. Monitors: an Operating System Structuring Concept. Communications of the ACM, 17(10):549-557, October 1974.
[18] R. Hughes. Why Functional Programming Matters. The Computer Journal, 32(2):98-107, 1989.
[19] Threads standard POSIX 1003.1c-1995 (also ISO/IEC 9945-1:1996), 1996.
[20] Message Passing Interface Forum. MPI: A Message-Passing Interface Standard, May 1994.
[21] R. S. Nikhil. "Cid: A Parallel 'Shared-memory' C for Distributed Memory Machines."  In Proc. 7th. Ann. Wkshp. on Languages and Compilers for Parallel Computing (LCPC), Ithaca NY, USA (Springer Verlag LNCS 892), pages 376-390, August 8-10 1994.
[22] R. S. Nikhil and Arvind. Id: a Language with Implicit Parallelism. In A Comparative Study of Parallel Programming Languages: The Salishan Problems, John Feo (editor), pages 169-215. North Holland, 1992.
[23] R. S. Nikhil, K. Pingali, and Arvind. Id Nouveau. Technical Report CSG Memo 265, Computation Structures Group, MIT Lab. for Computer Science, Cambridge MA 02139, USA, July 1986.
[24] OpenMP Architecture Review Board. OpenMP Specifications, 1997 (Fortran), 1998 (C/C++)
[25] S. L. Peyton Jones. The Implementation of Functional Programming Languages. Prentice Hall, 1987.
[26] S. L. Peyton Jones (editor), J. Hughes (editor), L. Augustsson, D. Barton, B. Boutel, W. Burton, J. Fasel, K. Hammond, R. Hinze, P. Hudak, T. Johnsson, M. Jones, J. Launchbury, E. Meijer, J. Peterson, A. Reid, C. Runciman, and P. Wadler. Haskell 98: A Non-strict, Purely Functional Language, February 1999.
[27] M. C. Rinard and P. C. Diniz. Commutativity Analysis: A New Analysis Framework for Parallelizing Compilers. ACM Trans. on Programming Languages and Systems (TOPLAS), 19(6):942-991, November 1997.
[28] M. C. Rinard, D. J. Scales, and M. S. Lam. Jade: A High-Level, MachineIndependent Language for Parallel Programming. IEEE Computer, 26(6):28-38, June 1993.
[29] N. Wirth. Programming in Modula-2. Springer Verlag, Berlin, Germany, 1982.

Reader Response

---

Very interesting set of articles. There is no denying the power and elegance of functional languages. However, my main concern regarding their use in parallel programming is that they encourage only a coarse-grain, thread-based approach to parallelism at a time when the computer industry should be focusing its research muscle into developing fine-grain, auto-scalable multicore CPUs using an MIMD execution model. My second objection is that the very thing that FP proponents are railing against (state changes) will turn out to be their Achilles' heel with regard to safety-critical applications. The only way to implement a mechanism for the automatic discovery and resolution of data dependencies (a must for reliability) is to adopt a purely reactive software model that allows the use of state variables. This is especially important when maintaining unfamiliar legacy systems where data dependencies are not obvious. One man's opinion, of course.

-Louis Savain
Software Engineer
Miami, FL

---