Introduction to TBB, continued
CS 300, Parallel and Distributed Computing (PDC)
Due Monday, January 19, 2015
______
______
______
______
______
______
______
______
______
______
______
On a 32-core computer (either a thing or the MTL), create a
lab8 subdirectory of your personal
directory for work on the lab,
and change
directory to that directory.
Begin with a copy of a version
tbbprimesn.cpp from the previous lab, where
n ≥ 4. Make a copy of that program in your
lab8 directory, naming the copy
sieve.cpp.
Add a TBB parallel_for to parallelize the
for loop for initializing your "premarked[]"
array, i.e., the "marked[]" array of char
that you use for precomputing an initial subset of primes.
Notes:
This requires replacing that loop by a call to
parallel_for; see the main() in trap-tbb.cpp for an
example.
The range object for this call to parallel_for
needs to be constructed with the correct arguments. For example, if
your loop were
for (int i = 7; i <= N; i++) {
...
}
then the range object can be constructed with the call
blocked_range<size_t>(7, N+1);
The body object for this call to parallel_for
can be a member of a class named, for example,
InitPremarked. That class is responsible for performing
initialization on a range of indices for the array
premarked[].
Therefore, the class InitPremarked will need a
(private) state
variable for holding a copy of the (address of the) array
premarked, perhaps named my_premarked.
Also, the constructor must initialize my_premarked from
its argument. The state variable and constructor argument can have
type char*, but they should not be const
char*, because the purpose of InitPremarked
is to make changes in the (characters pointed to by that) array.
Compile, run, benchmark, record observations in a file lab8/README, and copy
to tbbprimes10.cpp
Next, use TBB's parallel_for to parallelize the
loop for marking multiples of a given prime p in the array
premarked[].
For this loop, you will need a class, perhaps named
SievePrime; an object of that class will be used as the
second argument of this call of parallel_for.
The iteration for this loop needs to increment by p
instead of incrementing by 1. You can accomplish this by constructing
blocked_range<size_t> object for generating integer
values that are 1/p of the index values you want to
mark in the array premarked[]. For example, if your
loop was
for (int k = p*p; k < maximum; k += p) {
...
}
then you can generate such a range object using the call
blocked_range<size_t>(p, maximum/p);
then multiplying index values from that range by p,
e.g, premarked[p*i]. Be sure to adjust both the starting
and ending values for this range.
The body class for this loop will need two state variables,
premarked and p, both passed in the
constructor.
Compile, run, benchmark, record observations in a file lab8/README, and copy
to tbbprimes11.cpp
Next, use TBB's parallel_for to parallelize the loop
that assigns the starter set of primes to your (thread-safe!)
concurrent_queue variable.
This will require defining and using a body class, perhaps named
PushPrimes. That class will need state variables for
both premarked and your queue variable. Here, we
don't want to construct new copies of that queue, so use
reference types concurrent_queue& for both
the constructor argument and the state variable for that queue. (Use
a pointer type for premarked, as before.)
Compile, run, benchmark, record observations in a file lab8/README, and copy
to tbbprimes12.cpp
Parallelize at least one more loop in the program, aiming to
improve performance the most when compared to
tbbprimes12.cpp.
Compile, run, benchmark, record observations in a file lab8/README, and copy
to tbbprimes13.cpp
If your 32-core machine is a thing, submit your work
using the following command on your thingn
$ cd ~ $ labsubmit.cs300 lab8
Otherwise, if you are using MTL, make a tar archive of
your work, scp that archive to a Link computer (or
shelob), unpack the tar archive, and use the
labsubmit.cs300 command above to submit from that
St. Olaf computer.
This lab is due by Monday, January 19, 2015.