This was an fairly basic introduction to the theory of writing parallel programs. It started with chapters covering the strategies for writing parallel programs, and how to check the correctness and measure the performance of a parallel solution. Breshears gives eight simple rules for designing parallel applications and later gives four criteria for evaluating the design of a parallel algorithm – efficiency, simplicity, portability, scalability. The book then moves on to looking at parallel implementations of a number of algorithms – parallel sum and prefix scan, map reduce, sorting, searching and graph algorithms. Generally the author starts with a sequential algorithm, modifies it a little and then shows how a number of standard techniques can be used for covering it into a parallel algorithm.
These algorithms are implemented on top of a number of different libraries – Open MP, TBB, windows threads and pthreads. None of these libraries were covered in a great deal of detail, but the examples gave a nice flavour of what the libraries offered.
Looking at the various correctness criteria for the algorithms, got me thinking again about the .NET memory model and the needs for various types of memory barriers. While surfing the internet, I came across the following paper which is the best I have read on the subject of the interaction between the software and hardware, and why memory barriers are needed. The author has a great example where a thread moves between CPUs, demonstrating the need for the operating system to put in memory barriers during context switches. The .NET 2 memory model only guarantees that stores will not be reordered with regard to other stores, which corresponds to a guarantee the x86 architecture makes. However, barriers also effect the compiler optimisations that may be applied, preventing the compiler, for example, moving loads and stores across barriers.
This book recommends some other more advanced books that cover the analysis and design of a number of other algorithms. I will be following up some of these recommendations in the near future,