Parallel programming and computational thinking

This chapter introduces the concept of computational thinking. It first reviews the main goals of parallel programming. It then discusses the thinking process of algorithm selection and problem decomposition. For a given problem the programmer will typically have to select from a variety of algorithms. Some of these algorithms achieve different tradeoffs while maintaining the same numerical accuracy. Others involve sacrificing some level of accuracy to achieve much more scalable running times. For the selected algorithm, different choices of problem decomposition can result in different levels of interference between threads, parallelism exposed, load imbalance, and other performance considerations during parallel execution. Computational thinking skills allow an algorithm designer to work around the roadblocks and reach a good solution.