2
edits
Changes
→Progress
== Progress ==
=== Assignment 1 ===
I profiled a code found on http://www.dreamincode.net/forums/topic/76816-image-processing-tutorial/
There are multiple functions available within the code, and I decided to try three of them (enlarge, flip, and rotate image)
0.00 0.52 0.00 1 0.00 0.00 ppma_write_header(std::basic_ofstream<char, std::char_traits<char> >&,
std::string, int, int, int)
=== PI calculation ===
I've chosen to profile the algorithm for estimating the value of PI as described on this page: https://computing.llnl.gov/tutorials/parallel_comp/#ExamplesPI
The run time of the program is determined by the number of samples (random points generated) that are used to estimate pi. Greater number of samples results in a a more accurate value of pi.
In my trial runs, doing ~10 million samples results in a value accurate to 3 decimal places.
Run time for this algorithm increases in a linear fashion, and as such the proportion of time taken up by each function remains the same.
Here are average values for percentage of run time taken up by a given function:
main(): 22%
getRandom(): 60%
insideCircle(): 15%
main() includes some simple set up and result calculation, but I'm going to guess that the loop control takes up most of the run time, in fact, it's actually more than the
insideCircle() function which uses the Pythagorean theorem to check if a point is inside the circle.
getRandom() generates a random float value between 0 and 1, and takes up most of the time. It is called twice to generate a single point.
Recommendation:
The largest hot spot is the generation of random numbers, which is something that GPU can do quite well. The other functions comprise a smaller portion but will be sped up as well.
Judging from the profiling data, this algorithm will greatly benefit from being run on the GPU, because every point is generated and evaluated independently of others.
The technique of reduction can be used to solve this problem.
Step 1: Generate 2 * n random floats between 0 and 1 where n is the number of samples that the user wishes to use
Step 2: Reduce this array of random numbers by applying the Pythagorean theorem to pairs of numbers
Step 3: Reduce again to count how many values in step 2 were below 1
Step 4: Plug the answer into the formula mentioned on the web page to get the result, this can be done on the CPU
=== Assignment 2 ===
=== Assignment 3 ===
