Contents xiii 5.7.3 The dynamic and guided schedule types............. 239 5.7.4 The runtime schedule type............................ 239 5.7.5 Which schedule?........................................ 241 5.8 Producers and Consumers..................... 241 5.8.1 Queues.… 241 5.8.2 Message-passing............. 242 5.8.3 Sending messages ..................................... 243 5.8.4 Receiving messages.................................... 243 5.8.5 Termination detection.................................. 244 58.6 Startup.… 244 5.8.7 The atomic directive................................... 245 5.8.8 Critical sections and locks............................. 246 5.8.9 Using locks in the message-passing program......... 248 5.8.10 critical directives,atomic directives, 0rl0Cks2.… 249 5.8.11 Some caveats.… 249 5.9 Caches,Cache Coherence,and False Sharing................. 251 5.10 Thread-Safety.… 256 5.10.1 Incorrect programs can produce correct output....... 258 5.11 Summary.… 259 5.12 Exercises.… 263 5.13 Programming Assignments................................ 267 CHAPTER 6 Parallel Program Development............ 271 6.1 Two n-Body Solvers............................. 271 6.l.1 The problem.… 271 6.1.2 Two serial programs.................................. 273 6.1.3 Parallelizing the n-body solvers....................... 277 6.1.4 A word about I/O............................. 280 6.1.5 Parallelizing the basic solver using OpenMP......... 281 6.1.6 Parallelizing the reduced solver using OpenMP...... 284 6.1.7 Evaluating the OpenMP codes....................... 288 6.1.8 Parallelizing the solvers using pthreads............... 289 6.1.9 Parallelizing the basic solver using MPI.............. 290 6.1.10 Parallelizing the reduced solver using MPI........... 292 6.1.11 Performance of the MPI solvers....................... 297 6.2 Tree Search.................. 299 6.2.1 Recursive depth-first search............................ 302 6.2.2 Nonrecursive depth-first search........................ 303 6.2.3 Data structures for the serial implementations........ 305 6.2.4 Performance of the serial implementations........... 306 6.2.5 Parallelizing tree search.............................. 306Contents xiii 5.7.3 The dynamic and guided schedule types............. 239 5.7.4 The runtime schedule type ............................ 239 5.7.5 Which schedule?........................................ 241 5.8 Producers and Consumers........................................ 241 5.8.1 Queues................................................... 241 5.8.2 Message-passing ........................................ 242 5.8.3 Sending messages ...................................... 243 5.8.4 Receiving messages .................................... 243 5.8.5 Termination detection .................................. 244 5.8.6 Startup ................................................... 244 5.8.7 The atomic directive ................................... 245 5.8.8 Critical sections and locks ............................. 246 5.8.9 Using locks in the message-passing program ......... 248 5.8.10 critical directives, atomic directives, or locks? ................................................. 249 5.8.11 Some caveats............................................ 249 5.9 Caches, Cache Coherence, and False Sharing ................. 251 5.10 Thread-Safety...................................................... 256 5.10.1 Incorrect programs can produce correct output ....... 258 5.11 Summary ........................................................... 259 5.12 Exercises ........................................................... 263 5.13 Programming Assignments ...................................... 267 CHAPTER 6 Parallel Program Development ............................... 271 6.1 Two n-Body Solvers .............................................. 271 6.1.1 The problem............................................. 271 6.1.2 Two serial programs .................................... 273 6.1.3 Parallelizing the n-body solvers ....................... 277 6.1.4 A word about I/O ....................................... 280 6.1.5 Parallelizing the basic solver using OpenMP ......... 281 6.1.6 Parallelizing the reduced solver using OpenMP ...... 284 6.1.7 Evaluating the OpenMP codes......................... 288 6.1.8 Parallelizing the solvers using pthreads ............... 289 6.1.9 Parallelizing the basic solver using MPI .............. 290 6.1.10 Parallelizing the reduced solver using MPI ........... 292 6.1.11 Performance of the MPI solvers ....................... 297 6.2 Tree Search ........................................................ 299 6.2.1 Recursive depth-first search............................ 302 6.2.2 Nonrecursive depth-first search........................ 303 6.2.3 Data structures for the serial implementations........ 305 6.2.4 Performance of the serial implementations ........... 306 6.2.5 Parallelizing tree search ................................ 306