In these features, a thread of the program attempts to read a value, but it may have to wait because the value may not be available yet ("empty" in the case of I- and M-structures). That thread can spin and wait, or it can suspend itself, which means enqueuing some state related to the thread on the empty slot.

Later, when some other thread writes data into the empty slot, it must re-enable one or more of the threads waiting on that slot. This is a central activity in any pH implementation and is called thread switching or context switching.

Because of implicit parallelism, nonstrictness, and fine-grain data synchronization in pH, this activity is extremely frequent and is necessary even in a uniprocessor implementation.

Consequently, it has to be extremely efficient, barely more expensive than a procedure call. Contrast this with conventional thread switching in POSIX threads (pthreads), or modern operating systems, where the cost is typically two or more orders of magnitude higher than the cost of a procedure call.

Implementations of pH must thus pay great attention to optimizing this operation, and the code sequences to accomplish this must usually be carefully hand-crafted. These implementation issues are considered in great detail in [25], [9] and by others.

A final point to note is that this particular efficiency issue is shared by all implementations of Haskell and other lazy functional languages, even though they may be sequential implementations. The requirement arises from non-strictness and fine-grain data synchronization, which are orthogonal to parallelism.

Interoperability and Application Domains
This series has focused on the fundamentals of implicit parallelism and, as such, the programming examples illustrate classical algorithmic problems.

Today, the world of programming is much more diverse, encompassing varied domains such as Web-based client-server programming, user interfaces, graphics, distributed computing, and so on. It is almost impossible for a single programming language to encompass such a rich diversity of application domains; instead, over the last few years we have seen the development and growth of several mechanisms for interoperability.

For example a Web browser may be written in one language, but it may interact with a "plug-in" that is written in another language. Or, a spreadsheet may be written in one language while it accesses data from a database management system (possibly on a remote server) that is written in another language.

Ultimately, the success of a programming language depends not only on its core technical advantages, but also on the facilities it provides for interoperability with the vast existing base of software (screen, keyboard and mouse control; file system access; database access; network access; and so on).

Many interoperability mechanisms are quite ad hoc (such as calls to compiled code from many "scripting" languages), but some have been designed with more principles and care.

Two such standards are CORBA from the Object Management Group and COM from Microsoft Corporation. In these standards, the programmer specifies the interaction between two "components", possibly implemented with different programming languages, using a common, language-neutral specification language called an "Interface Definition Language", or IDL.

For each component implementation language of interest, an "IDL Compiler" compiles this specification into stubs for each side of the interaction. These stubs can then be linked in with the actual code of the participant in the interaction.

Researchers in the Haskell community have done much research into interfacing Haskell to COM and CORBA [21] [22]. These Haskell solutions should carry over directly to pH. In fact, it is an open question whether pH's implicit parallelism will improve the structure of interoperating programs because many of them are reactive in nature, which fits naturally into pH's concurrent, data-driven behavior.

The Final Word
pH represents a radically different way of thinking about parallel programming. We believe that it is increasingly in tune with developments in computer hardware, where symmetric multiprocessors comprising multicore processors are becoming the norm due to the continually decreasing prices of semiconductor components and the barriers to increasing uniprocessor speed.

This vision is not a foolish dream. Despite the pessimism in some other quarters (See "Programmers stuck at C") about the near term emergence of a viable parallel programming methodology that will be widely adopted, we believe pH is a solution that is deployable now, with the right level of engineering effort. We hope that the vision presented in this series will excite researchers, students and software engineers to form a critical mass that can make this vision a reality.

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?"
To read Part 7, go to "pH: An implicitly parallel, declarative language."

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.