ABSTRACT
CONTENTS 7.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 277
7.1.1 The Monte Carlo Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 279 7.1.2 Computational Topics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 281
7.2 Exploring the Random Process . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 281 7.3 Generating Offspring . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 284
7.3.1 Checking the Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 286 7.3.2 Considering Alternative Implementations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 287
7.4 Profiling and Improving Our Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 289 7.5 From One Job’s Offspring to an Entire Generation . . . . . . . . . . . . . . . . . . . . . . . . . . . 290 7.6 Unit Testing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 292 7.7 A Structure for the Function’s Return Value . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 293 7.8 The Family Tree: Simulating the Branching Process . . . . . . . . . . . . . . . . . . . . . . . . . . 294 7.9 Replicating the Simulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 299
7.9.1 Analyzing the Simulation Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 301 7.10 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 306
Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 308
7.1 Introduction Parallel computing allows us to break up our programs into smaller pieces that can run simultaneously on different CPUs. Sometimes a program spawns another program/job that needs to wait before it can begin its work because it requires the results of another program that has not completed. In this situation even where there are ‘infinitely’ many CPUs available, a queue of interdependent tasks will form. Tsitsiklis, Papadimitriou, and Humblet [6] studied the behavior of systems of interdependent jobs. One of the questions that interested them was: what is the distribution of the length of time that a computational process, including all of its subtasks, takes to complete? The answer to this kind of question may help developers design code that can run efficiently in a parallel fashion or design queuing systems for managing jobs on a compute cluster. Similar problems arise with, e.g., Web servers with multiple queues and database requests where a request to update information must wait for earlier requests that are working with the same information.
