Parallel Computing in the Computer Science Curriculum > Modules > Concurrent Access to Data Structures in C++

Concurrent Access to Data Structures in C++

Dick Brown and Pat Garrity, St. Olaf College
Author Profile

Summary

This module enables students to experiment with creating a task-parallel solution to the problem of crawling the web by using C++ with Boost threads and thread-safe data structures available in the Intel Threading Building Blocks (TBB) library. We provide enough code for a sequential solution, which the students can use as the basis for creating a task-parallel threaded solution. We provide some code to get students started with the threaded solution, because in a typical use case this may the first threaded program those students have encountered.

Learning Goals

Context for Use

This module is typically implemented in an introductory (2nd course) or intermediate-level Java-based course. It may be taught while introducing the concepts of threads and thread-safe data structures. An instructor could present the materials (handout, slideshow presentation) in class and assign exercises as a lab or homework.

Description and Teaching Materials

You can visit the module in your browser:
Concurrent Access to Data Structures in C++

or you can download the module in either PDF format or latex format.
PDF Format: Concurrent Access to Data Structures in C++.pdf.
Latex Format: Concurrent Access to Data Structures in C++.tar.gz.
Word Format: Concurrent Access to Data Structures in C++.docx.

This is the code you can use to get students started on a lab or homework assignment:
CDS C++ student code 20120301 (gzip Archive 5kB Mar1 12)

Instructors: If you want example completed code, please contact Dick Brown, rab at stolaf dot edu.

Teaching Notes and Tips

This module utilizes the Boost package, a library of enhanced capabilities for C++. Several of these capabilities have become incorporated in the new C++11 standard, including the Boost support for programming with threads (which we will use). The module also uses a TBB Container data structure in order to obtain a thread-safe implementation, and the CURL library for conveniently accessing web information.

In the code archive:

The concept of the lab/homework is that students should have worked out a sequential version of the Spider already. You could do this by explaining it to them, or by having them work on that first. We have used this in the past by staging assignments so that they get some parts of the code and then must complete to make a working spider. What is provided here is the already working sequential version.

You may feel like using different data structures for parts of this assignment- we realize there are other ways to hold the information kept by the crawler. However, the TBB Containers data structures we chose for the threaded version fit the problem well. (Feedback/suggestions? Please enter below.)

The lecture/class materials present the concepts of using multiple threads that share data structures in memory. Since the intended audience is introductory to intermediate students, we include a rather gentle introduction to the issue of "data race condition" errors, and explain how the designers of the data structures in the TBB Containers library avoided such errors.


Assessment


References and Resources

Boost threads documentation

TBB documentation

CURL documentation

See more Modules »



Comment? Start the discussion about Concurrent Access to Data Structures in C++