Project 4 – CS 352 (Fall 2010)

Worth: 100 points

Assigned: Monday, November 29th, 2010

Due: 9:00 am, Friday, December 10th, 2010

Purpose

The purpose of this project is to give you some experience tailoring code to a variety of architectures. In doing so, you will learn about the trade-offs involved in coding for heterogeneous architectures and unusual memory systems.

Problem

In this project, you will be working with a toy particle simulation code. This program uses an algorithm that can be applied to a number of science simulations, including the motion of stars and galaxies, fluids, and molecules. The algorithm, at its core, calculates an interaction force between each pair of particles. Because it involves calculations between all pairs, it is a O(n2) approach – meaning that using it on a large number of particles requires either a different algorithm, or a lot of compute horsepower. (Or both!)

Performance Reporting

For each of the optimization steps that follow, you will need to report back graphs of the amount of time the program takes versus relevant optimization parameters (i.e. tile size, number of threads, etc.). You can gather these results by using the “time” command in Linux, or by using the inline timing code inside the program (“-t”).

As you work through the project, collect your results in a single Excel file, with each subsection’s results on a different sheet. Additionally, there are some questions within each section – answer them in a document of some kind. You will include both of these in your submission.

1. CPU Baseline

Log on to servername_here. From your home directory, execute this command:

cp -r ~ernstdj/cs352/particles .

Use the makefile (type “make”) to build the program. Except for some basic correctness testing, you SHOULD NOT actually execute it on the login node! For your proper performance baseline, we need to make sure that:

Your code is running on the same type of CPU that we’ll be comparing to later (which the head node is not using!), and

Your code is running without the interference of anyone else’s code.

In order to guarantee these two things, you will need to submit your jobs to the queuing system on ebwilson. Within your starter files, there will be a file named “cpu.qsub”, which is a batch submission script. Open it with your favorite Linux text editor and change the two very obviously notated pieces of the file to match your username and e-mail. When you’re ready to run your code on a compute node, simply execute:

qsub cpu.qsub

When it completes (use “qstat” to see if it’s done yet), the results of your computation will come as two files – “particleCPU.o####” will hold the results from standard out, while “particleCPU.e####” will hold the standard error output. Note that “time” dumps its results to this second file!

You will need to run a wide parameter sweep and present results and analysis for different parameters, such as:

How does performance change with # of particles?

How does performance change with # of time steps?

Is there any interaction between the two?

Please note that your jobs will have a 10 minute runtime limit, so do not worry about parameter values that cause you to exceed that amount of time.

2. CPU Cache Tuning

We start with an easy task – modify the code to use blocking to improve cache behavior. This code modification will look very similar to the one used to discuss blocking in class! Re-run a portion of the parameter sweeps from Part 1, making note of any changes in performance. Can you explain them?

3. Multi-threading for Multi-core

Your next task is to spread the program’s work out to the many processor cores available to you on each node of clustername. Each node contains 16 cores (two eight-core chips) with 32GB of memory.

The most basic way to work with multiple threads is by using the pThreads library, which allows you to spawn and control multiple individual threads. However, for our purposes (just getting performance, without needing that level of control), the easiest way to split up heavy looping tasks over multiple threads is to use OpenMP, now a standard part of most C/C++ compilers and IDEs.

You will need to investigate the basics of OpenMP (check the website’s references page!) to figure out how to break up for loop iterations. In particular, you’ll want to look at the omp parallel for pragma.

Spread the particle simulation work out across varying numbers of cores (OpenMP has a function for setting the number of threads) and record the results in your spreadsheet. How well does the code do?

4. GPU Baseline

Your next task is to benchmark the baseline GPU (CUDA) code provided to you that we will discuss in class. This code spreads the force calculations for each time step out across an array of CUDA cores. To get a copy of the code for yourself, you can execute this command from your clustername home directory:

cp -r ~ernstdj/cs352/particles_gpu .

To run this code, you will need to submit your job using the slightly different script included in the directory, as the node with the proper hardware is different than the others.

Run jobs to establish a baseline for GPU performance, much as you did in Part 1. In your Excel sheet, produce the following graphs:

For one simulation, vary the number of threads per block. Graph performance versus threads per block.

Graph the speedup of the best GPU version versus the CPU version for varying numbers of particles.

5. GPU Shared Memory

Your final technical task is to modify the baseline CUDA code to make use of the per-SM fast shared memory on the GPU. To do this, you will have to declare a __shared__ array, and then use it to “cache” the operations (somewhat similar to part 2, only with an explicit copy). Compare these results with those from the GPU baseline from part 4 for a few different block sizes.

6. Turning in the Project

Create a folder for turn-in. Name it something relevant (like “project4_person1_person2”). For each of the above sections, place the code and makefile in separate sub-folders of this main project folder. Include your Excel sheet, with graphs in the folder as well. Additionally, include a short document (Word/PDF) that answers these questions:

What did you learn from these experiments about the value of laying your code out on different processors? on different memory systems?

Compared to the amount of code written, do you think the performance boost from using a GPU is worth the effort? Why or why not?

The project may be turned in by dropping the top-level folder into:

Network Drive Folder

Project 1--CS 352 (Fall 2006)

Dan Ernst

2010-11-27

dje

UWEC