A fundamental turn towards parallel programming and its implications

Parallel programming is a core area of computer science which has seen tremendous progress over the last decades, mainly due to the widespread presence of multicore processors in both laptop and desktop computers nowadays. Unfortunately, the sequential programming approach that is currently widely used and taught cannot take full advantage of the architectural changes that come with multicore processors. The problem lies in the fact that parallel programming requires a process of thinking that is more difficult for humans to comprehend. Moreover, today’s languages are deficient in offering guidance on converting sequential programs into parallel ones. In recent years, several possible solutions for this important problem have emerged, which build on two already known programming paradigms: functional and imperative. As such, parallel programming techniques have deep consequences and implications for both programming languages and programmers.

The solution may lie in higher-level abstractions that would help build parallel programs. Herb Sutter (2005) [1] presents evidence that suggests that the parallel programming revolution will be even more troublesome than the object-oriented revolution. He concludes this on the basis that concurrent programming is proven to be more difficult than sequential difficult. Moreover, they require both synchronization-sensitive and context-sensitive analysis. Ramalingam states that “Context-sensitive synchronization-sensitive analysis is undecidable” [2] through its paper’s title. Sutter describes that unstructured parallelism is the most general and least predictable form of concurrency. This is due to the fact that data accesses need to be coordinated through explicit synchronization. The author describes possible solutions for this problem, which are based on either imperative or functional programming. Both solutions have advantages and disadvantages. In imperative programming, race conditions and deadlocks can occur due to the fact that the application’s shared memory is usually manipulated by different objects. The usage of Java’s Threads and Locks represents a partial workaround. On the other hand, functional programming is naturally suited for parallel programming since it manipulates immutable object instances, which do not raise any concurrency problems. The downside to this approach is that they usually hinder performance. The author concludes that neither of these solutions is optimal and more thought needs to be put into programming tools.

Java threads are part of the problem, not part of the solution. Lee (2006) [3] points out that threads dominate all other approaches to concurrent programming. This is due to the fact that they are supported modern computers, programming languages and operating systems. Although they can be used effectively to tackle certain simpler problems, the author proves that from a fundamental perspective they are flawed as a computational model. This is mainly due to their nondeterministic nature. Lee strongly believes that programmers should distance themselves from this approach. Although many working parallel applications are developed using threads, better tools can be created which would further improve these applications. Similar to all imperative languages, Java’s threads will always be vulnerable to data races and deadlocks because they contain mutable variables. Lee suggests several improvements that can be made in order to fix some of the problems. Although promising, these improvements require considerable expertise in order to be implemented. Moreover, they do not solve the problem entirely but merely a small part of it. Several alternatives to threads are then suggested by the author, all based on imperative programming (Rendezvous director, PN director, SR director and DE director). All four suggestions eliminate the nondeterministic component of the problem. The author also points out that although functional languages may provide a solution this problem, they are less explicitly concurrent and may be more challenging to use. The author concludes that although we should not replace existing languages, building on them using only libraries (such as threads) is unsuitable.

Functional languages promote the development of correct, deterministic parallel programs. Blelloch (1996) [4] proposed the idea of a functional parallel language (NESL) that would be useful for teaching as well as implementing parallel algorithms. He points out that analyzing performance is a key part of the language. In order to evaluate performance, a formal modal is needed to account for costs. Most common models are based on a set of processors connected by a shared memory, named PRAM. They are viewed as a virtual model that can be mapped onto more realistic machines by simulating multiple processors of the PRAM on a