| Date | Description |
| 7-Jan-11 | Original posting |
The purpose of this assignment is to familiarize you with the basics of the pthreads Application Programmer Interface (API). In the process, you will implement an embarrassingly parallel application that performs primality testing on a long list of numbers, determining whether or not each number is prime. You'll also report the scalability of your application, that is, the observed speedup as a function of the number of cores. Scalability doesn't get much better than for this application, and you should observe perfect scaling up to the maximum number of cores provided by the hardware.
You may develop your code wherever you wish, but your code will be graded based on behavior observed on ieng6-203.ucsd.edu, the 8-core multiprocessor based on the Intel Xeon multicore processor that will be used in this course. This machine should not be confused with ieng6.ucsd.edu, which is a different machine and will produce different performance results.
We will use the naive algorithm. To determine if a number N is prime, we divide it by all integers M in the range 2 to √ N , excluding even integers M > 2. If we find no divisor, then the number is prime, else it is a composite number (not prime). For N sufficiently large (see the provided input run_64.sh), the calculation will take sufficient time that you will obtain linear speedups.
A working serial version of the code has been provided on ieng6-203.ucsd.edu in $PUB/HW/A1, where, upon login, $PUB will be defined for you as follows
/home/linux/ieng6/cs160w/public
Port the provided serial code to use pthreads. Your code design should handle the case where the numbers of threads does not divide N, the size of the input.
The code accepts all of its input in the form of command line arguments. The first argument is the number of threads and the remainder are the candidate prime numbers. The following invocation will test 4 candidate primes on 5 threads (see init.cpp).
primes 6 2 3 17 31 34155013283297
To build your code, use the provided Makefile, as it sets up the appropriate flags for the Gnu compiler. At the moment we are using version 4.1.2 of gcc and g++, so keep this in mind if you are trying to develop your code on another machine.
You'll notice that the Makefile includes the file $(PUB)/Arch/arch.gnu.pthread, which we call the "arch" file. The arch file contains various settings needed to compile and built executables and should not normally be changed.
If you would like to develop your code on a different machine, make a copy of the provided "arch" file, and modify the Makefile to include it. (Be sure to restore the include when you submit your code, so that it includes the arch file mentioned above). If you run into compiler errors, post to the A1 Moodle Forum and a solution will be worked out. (The provided arch file should work without change on MacOS systems, at least they have been tested on version 10.6)
We will grade your machine on ieng6-203.ucsd.edu. Be sure to do your final testing on that machine, to avoid any surprises at turnin time.
Run your code with 1, 2, 4, and 8 threads on the 64-input list of prime numbers as shown in run_64.sh. Verify that the speedup is in fact linear in the number of threads. If it isn't, then you have some performance debugging to do!
Test your code to ensure that the results are independent of the number of threads, by comparing against the provided serial code. Also try inputs that include some composite (non-prime) numbers. To facilitate testing, the program outputs the essential information--the number of primes along with the numbers themselves--into the file Log.txt It will also tell you if all numbers were identified as primes, which can be handy to do quick checks with long lists of numbers. (Any previous copy of Log.txt will be overwritten, so if you are doing automated testing, be sure to rename the files between invocations.) Be sure to test the case where the number of threads doesn't divide the input size.
When grading your assignment, we will test your code against one public input (run_64.sh) plus other inputs that will not be made public.
If the system is heavily loaded, as in the day the assignment is due, you may observe performance anomalies, including non-linear speedups. Try testing at another time of day. Try using the at(1) command, which enables you to schedule a job to run at a pre-determined time, say, in the middle of the night. The output (stdout and stderr) will be mailed to your account. (We are experiencing some problems with the at(1) command on ieng6-203, so the mailing feature doesn't work at this time.) To reduce the likelihood that you will run at the same time as others (which might re-introduce the problem you were trying to avoid), schedule a time of day such that the last digit of the time is the same as the last digit of your AID, i.e. if your AID is 12345678. Your runs should not last more than about 30 seconds, and this is reasonable given the computational workload. We use the mv(1) command to rename the output Log.txt file, since it would otherwise be overwritten by successive runs.
% at 7.52 -m < run.sh job 39 at 2011-01-05 07:52 % atq 39 2011-01-05 07:52 a cs160w % date Wed Jan 5 07:50:07 PST 2011 % atq % date Wed Jan 5 07:54:26 PST 2011 % cat run.sh #!/bin/csh pwd printenv date ./primes 2 3 17 31 34155013283297 mv Log.txt Test_5.txt ./primes 34155013283297 34155013283401 mv Log.txt Test_2.txt date
We have provided high resolution timers based on gettimeofday(). The timer in Timer.cpp allows you to time a individual threads and you can see how it is used in the provided serial code. Recall that the running time of the application is determined by the last core to finish. Consequently, we have provided variant of the timer in parTimer.cpp, that uses barrier synchronization to ensure that we correctly account for that last thread. To use this timer, you must initialize some internal state (the barrier). Make the following call exactly once prior to spawning your threads
initTimer(NT);
where NT is the number of threads. When you are finished using the timer, and all spawned threads have been joined, invoke FinalizeTimer() exactly once.
In the spirit of friendly competition, post your performance results to the A1 Moodle forum.
We have provided a serial version of the code. The organization of the code is described in a README file. Included is a placeholder for the thread function, called prime_thr.cpp. Don't change the signature of this function.
To ensure that your program is correctly graded, there are 3 files that you must not change:
Timer.cpp parTimer.cpp Report.cpp
We have also provided scripts to run with 8 and 64 candidate primes, respectively, both serial and parallel versions
run8_serial.sh run64.sh run8.sh run64.sh
The provided Makefile includes targets for both serial and parallel versions. Do not change the target names. You may add additional code files if you wish, or change the names of the object files, except for the 3 files mentioned above.
Turn in your source code electronically not later than the deadline at 9pm on the day the assignment is due. We will provide instructions about the electronic turnin procedure on Moodle early next week.
The timestamp on the electronic turnin establishes the time that you handed in the assignment, and successive turnins will overwrite any existing turnin. Once the deadline has passed (with a few minutes' grace period), the script will be disabled, and you will not be able to turn in your assignment. Be careful to turn in on time.
Don't wait until the last minute to attempt a turnin for the first time. The turnin program will ask you various questions, and it will check for the presence of certain required files, as well as your source code. It will also build the source code if you like, to catch any obvious build errors. Try out the turnin process early on so you are sure that you you are familiar with the process, and that all the required additional files are present.
Your turnin must include a valid team self-evaluation discussing the division of labor and other aspects of how you worked together as a team. A copy of the form is available in $PUB/turnin/teameval.txt. This form is mandatory, as the turnin process will not complete without it. You must also provide a MEMBERS file that identifies your team members, with your full names and email addresses. A template showing the format can be found in $PUB/turnin/MEMBERS Empty forms, or formed not diligently fill out will result in a 10% penalty being assessed, in addition to holding up the grading process.
When reporting performance results, it is important to identify the hardware and software testbeds used. Though we will all be using the same hardware when reporting our results, some may be developing on alternative resources. In case of difficulties compiling or running the code, it is a good idea to be informed about your hardware and software environment, To this end, you run a suite of commands to identify the hardware and the environment you used to develop and run your code.
On some Linux systems (such as ieng6-203.ucsd.edu) you can find useful information about the processor in the file /proc/cpuinfo. For example, here is part of ieng6-203's cpuinfo file:
cpu family : 6 model : 15 model name : Intel(R) Xeon(R) CPU X5355 @ 2.66GHz stepping : 7 cpu MHz : 2660.137
The contents of cpuinfo enable you to identify the specific processor, and the identifying information may be used to obtain other details from on-line resources. For example, ieng6-203 is a quad-core 2.66GHz Intel Xeon X5355 processor. (There is additional information in procinfo: family, model, and stepping. So in this case the family is 6, the model is 15, and the stepping is 7. This will allow you to explore smaller scale changes to the processor’s design that occurred over time.)
We may learn more by accessing Intel's ARK Database. Once at the ARK web site, search on "X5355" in the search window at the top of the page. You'll obtain various information; for example, the processor has 4 cores, and a 8 MB L2 cache shared among all cores. (The 2.66 GHz clocks speed matches that listed in the cpuinfo file).
Additional information, such as the L1 cache size, can be obtained from a set of many files:
/sys/devices/system/cpu/cpu*/cache/index*/*
For example, by inspecting the files /sys/devices/system/cpu/cpu0/cache/index1/*, we can determine that the L1 cache size is 32KB, is 8-way set associative, and has a 64 byte line size, and that there are separate instruction and data caches (the I-cache is described in the files /sys/devices/system/cpu/cpu0/cache/index1)
If you are using a non-Intel processor see if you can locate the information, and I will post links to the resources here.
Copyright © 2011 Scott B. Baden Fri [Wed Jan 5 09:58:32 PST 2011]