Monte Carlo Simulations: Parallelism in CS1/CS2

The page authored by David Valentine, base on his original activity.

Initial Publication Date: September 18, 2014

Summary

Simple Monte Carlo simulations can be very appropriate assignments for CS1/CS2 (for-loops, conditionals, rand() and maybe 1D arrays). They also can be embarrassingly parallel, making them a class of algorithms that are quite easy to convert from their original sequential solutions to corresponding parallel or distributed solutions that run much faster. The videos linked below are designed for viewing by instructors and show how to use OpenMP to parallelize three 'typical' CS1/CS2 student solutions. They then give descriptions of three additional assignments for instructors to try with their students.

The written module material linked below is designed for students to use in a class or lab setting. It introduces these type of algorithms, providing some examples with C++ code for both the original sequential version and the parallelized OpenMP version.

Module Characteristics

Languages Supported: , , C++, C,
Relevant Parallel Computing Concepts: , Task Parallelism, , Shared Memory,
Recommended Teaching Level: Introductory, ,
Possible Course Use: Introduction to Computer Science, , , , ,

Share your modifications and improvements to this activity through the Community Contribution Tool »

Learning Goals

We have found that simply exposing students to a parallel solution at the introductory level pays huge dividends throughout the curriculum. They come to expect parallel solutions in the follow-on courses. It changes their technical world view of problem solving and computer programming.

Context for Use

We target CS1/CS2 using C++ and OpenMP. Other languages can find equivalent threading API's.

Students will need (a) for-loops and (b) familiarity with rand().

We treat this assignment as a digital experiment, with the computer as our laboratory instrument. They will solve the Monte Carlo program in a conventional (serial) manner.

Then we typically take one lecture (50 minutes) late in the term and just demonstrate work-sharing with OpenMP multithreading. We have realized tremendous returns on student expectations through the core curriculum: they simply expect to see parallel solutions for their multi-core systems.

Description and Teaching Materials

Instructor Videos

One set of videos focuses on how to set up Microsoft Visual Studio.NET to use Intel's Parallel Advisor XE. Videos describing the projects using these tools are at:

David Valentine's Monte Carlo OpenMP/Visual Studio/Parallel Advisor video examples for instructors

The introductory video describes how to set up Microsoft Visual Studio.NET to use Intel's Parallel Advisor XE. While Advisor XE is not essential to the projects, it is nice to demonstrate professional tools to students.

The videos solve 4 Monte Carlo simulations (coin-flip, roulette wheel, Plinko Game and Texas Hold'em hands. Then the viewer is given three Monte Carlo simulations to do on their own.

A second set of videos emphasizes the use of OpenMP to teach these Monte Carlo examples. If you are not using the Parallel Advisor tool with Visual Studio or are using linux machines to teach C++, these videos will explain the addition of OpenMP directives to existing sequential solutions and how you can demonstrate these in an introductory course. This set of videos can be found here:

David Valentine's Monte Carlo OpenMP video examples for instructors

Materials for students

We have written materials for students to read and then activities for them to try in a lab setting.

You can visit the module in your browser:

Monte Carlo Simulation Exemplar

or you can download the module in either PDF format or latex format.

PDF Format: Monte CarloSimulationExemplar.pdf.

Latex Format: MonteCarloSimulationExemplar latex.tar.gz.

Word Formats:

MonteCarloSimulationExamplar.docx.

Monte MonteCarloSimulationExamplar.doc.

Teaching Notes and Tips

The template for these solutions is:
(1) Give a Monte Carlo simulation assignment in the introductory course. Students will generate a conventional, serial solution.
(2) Grade & return that assignment in the normal way.
(3) Towards the end of the course, cycle back to their already-working serial assignment, and just show them the OpenMP pragma to parallelyze the primary work horse loop. Compare run times and show them the system monitor CPU usage for the two solutions.

TCPP Curriculum Elements

Advanced Topics:High level themes:Misc:Why and what is parallel/distributed computing?
Algorithm Topics:Parallel and Distributed Models and Completxity:Costs of computation:Time
Architecture Topics:Classes:Data vs. control parallelism:Multicore
Architecture Topics:Classes:Data vs. control parallelism:Simultaneous Multi-Threading
Programming Topics:Parallel Programming notations:Shared memory notations:Libraries
Programming Topics:Parallel Programming paradigms:By the control statements:Task/thread spawning
Programming Topics:Parallel Programming paradigms:By the target machine model:Shared memory
Programming Topics:Performance issues:Computation
Programming Topics:Semantics and correctness issues:Tasks and threads
Hyper-Threading

Share your modifications and improvements to this activity through the Community Contribution Tool »

Assessment

The goal is much like an inoculation: we want to simply expose students to the concept that their code needs to take advantage of the multi-core processor they already own. We have found that once they see the system monitor showing all core operating at 100% of the available cycles, students start to demand to see parallel solutions through the core.

References and Resources

There are many OpenMP tutorials on the web. OpenMP.org is obviously a good place to start.

See more Modules »