Parallel Thinking

With the advent of Multicores we are riding a third or fourth wave of parallel computing, and perhaps unlike previous ones this one will break. Many if not most computer science classes, however, remain case studies in how to push students into thinking sequentially. At the earliest stages, for example, we teach students that taking the dot product of two vectors or merging two lists involves starting at one end and sequentially traversing to the other.

In reality many problems, applications and even algorithms are inherently parallel. The languages and models we use, however, push us to describe and conceptualize them sequentially. In this talk I will describe some of the core concepts in parallel algorithms. I will point out that these ideas transcend any particular model and are thus largely robust against uncertainties in what parallel machines might look like. I will also discuss how programming languages can affect the way we think about the algorithms. This work has developed from a PROBE on “Parallel Thinking” at the Carnegie Mellon Center for Computational Thinking (Sponsored by Microsoft). The goal of the PROBE is to better understand what are the core long-term ideas in parallelism so that they might be used to help guide curriculum development. Ideas from the audience will be appreciated.