Mark Twain once observed, “The past does not repeat itself, but it does rhyme.” And so it is with computer programs: code may not be reused over and over without change, but patterns do emerge.
Condensing years of parallel programming experience into patterns is not an exact science. However, we can explain parallel programming approaches in more detail than just talking about task versus data decomposition.
Object-oriented programming has found value in the Gang of Four (Gamma, Helm, Johnson, and Vlissides) and their landmark work, Design Patterns: Elements of Reusable Object-Oriented Software (Addison Wesley). Many credit that book with bringing more order to the world of object-oriented programming. The book gathered the collective wisdom of the community and boiled it down into simple “patterns” with names, so people could talk about them.
A more recent book, Patterns for Parallel Programming, by Mattson et al. (Addison Wesley), has similarly collected the wisdom of the parallel programming community. Its point is that the field of parallel programming has moved from chaos to established practice. Experts use common tricks and have their own language to talk about these tricks. With these patterns in mind, programmers can quickly get up to speed in this new field, just as object-oriented programmers have done for years with the famous Gang of Four book.
Patterns for Parallel Programming is a serious and detailed look at how to approach parallelism. Tim Mattson often lectures on this topic, and he helped me summarize how the patterns relate to Threading Building Blocks. This will help connect the concepts of this book with the patterns for parallelism that his book works to describe.
Mattson et al. propose that programmers need to work through four design spaces when moving from first thoughts to a parallel program (Table 2-1 summarizes these explanations):
- Finding concurrency
This step was discussed earlier in this chapter, in the section "Decomposition.” Threading Building Blocks simplifies finding concurrency by encouraging you to find one or more tasks without worrying about mapping them to hardware threads. For some algorithms (e.g.,
parallel_for), you will supply an iterator that determines how to make a task split in half when the task is considered large enough. In turn, Threading Building Blocks will then divide large data ranges repeatedly to help spread work evenly among processor cores. Other algorithms, such astbb::pipeline, help express the opportunity to create lots of tasks differently. The key for you is to express parallelism in a way that allows Threading Building Blocks to create many tasks.- Algorithm structures
This step embodies your high-level strategy. Figure 2-16 shows an organizational view for decompositions. In the “Decomposition” section, Figure 2-4 illustrated a Pipeline and Figure 2-2 illustrated Task Parallelism. Threading Building Blocks is a natural fit for these two patterns. Threading Building Blocks also excels at recursion because of its fundamental design around recursion, so the patterns of Divide and Conquer and Recursive Data are easily handled. The Event-Based Coordination pattern is a poor fit for parallelism because it is unstructured and unpredictable. In some cases, using the task scheduler of Threading Building Blocks directly may be an option.
- Supporting structures
This step involves the details for turning our algorithm strategy into actual code. For the traditional parallel programmer, these issues are critical and have an impact that reaches across the entire parallel programming process. But Threading Building Blocks offers enough support for this design pattern that the programmer rarely has to be concerned with it.
- Implementation mechanisms
This step includes thread management and synchronization. Threading Building Blocks handles all the thread management, leaving you free to worry only about tasks at a higher level of design. The design encourages implicit synchronization so as to reduce the need for explicit locking. Chapter 7 describes the use of synchronization with Threading Building Blocks.
Table 2-1. Design spaces and Threading Building Blocks
|
Design space |
Key |
Your job or not? |
|---|---|---|
|
Finding concurrency |
Think Parallel |
Your job |
|
Algorithm structures |
You express yourself using the algorithm templates; the rest is taken care of for you | |
|
Threading Building Blocks | ||
|
Write code to avoid the need for explicit synchronization, or use mutual exclusion from Chapter 7 |
Threading Building Blocks does most of the work for you |
Our envelope-stuffing example from Figure 2-8 can be translated into code by addressing these four design spaces. For the finding concurrency design space, the concurrency is both data parallelism (the materials: envelopes, stamps, papers) and task parallelism (the jobs of folding, stuffing, etc.). For the algorithm structures design space, we chose a pipeline. With Threading Building Blocks, we can use tbb::pipeline. Because the synchronization is all implicit, there is no need for locks. Therefore, Threading Building Blocks handles the last two design spaces—supporting structures and implementation mechanisms—for us.