CS 5984 Advanced Computer Graphics, Fall 2011

Programming Assignment 3: Reduction

Due: 11:59pm, October 3rd, 2011 (Monday)

Introduction

The goal of this assignment is to

• be familiar with NVIDIA CUDA programming framework.
• be able to apply the knowledge learned from the class into a practical programming example. The following GPGPU programming concepts are going to be practiced in this assignment:
  • Computation-to-Core Mapping
  • Coalesced Global Memory Access
  • Bank Conflict for Shared Memory Access
  • Divergent Branching

Description

You are asked to write a program to find the maximum, minimum and median value of an array of numbers. The program should follow these steps:

1. Load an array of numbers from an ASCII file
2. Transfter the array from host memory to device memory
3. Find the maximum, minimum and median value of the array by calling CUDA kernel functions
4. Output the result

At step 3, your host code can call as many kernel functions as necessary. You can also implement some functionalities on CPU, if you think the performance is better this way.

Median value of an array is the value of middle number of the array if it is sorted. If the total number of the array is odd, the median value is the middle number. Otherwise, there is a pair of middle values. In this case, the median number is the average of this pair of numbers.

Test Data Generation and Format

When grading your assignment, we will use three arrays. The size of these arrays are 480, 4095 and 118755. These arrays will be stored in three ASCII files. You can use these ASCII files to test your program. Please access these files from here: a480.dat, a4095.dat, a118755.dat.

Each line of these ASCII files includes one number of an array. The line is ended with the character '\n'. Please open one of the test files as an example of format.

Program input and output

Your program should take two parameter as inputs. The first one is the file name of the ASCII file, which contains an array of numbers. The second one is the size of the array.

The program should print out the maximum, minimum and median value of the array. In case the median value is the average of a pair of numbers, you can print it as a float instead of an integer.

Your program should also print out the execution time for the following procedures of your program:

1. Memory transfer from host to device
2. Total computation to find maximum, minimum and median value (Start after the data is really in the right memory location, and stop when the result is ready)
3. Memory transfer from device to host
4. Overall execution: include input file loading and exclude printing out result.

What and how to submit:

Put your solution in one compressed file(zip or tgz), including all source files, project file (for Visual studio), makefile (for Linux and MacOS). Please also include a README file, if you have specific instructions for how to compile or run your program. Please do NOT include your test data file.

To submit your assignment, simply upload your compressed file onto the the dropbox of the class scholar site.

Grading:

• Documentation and Readability (10%)
• Correctness (40%)
• Performance (50%)