Open main menu

CDOT Wiki β

Changes

DPS915/CodeCookers

2,244 bytes removed, 19:10, 3 October 2014
no edit summary
'''Norbert''':Calculation of PI
Problem Description
[[Image:https://computing.llnl.gov/tutorials/parallel_comp/images/pi1.gif|thumb|widthpx| ]]
For this assignment, I selected one application that I wished to parallelize. I profiled it to find the hotspot of the application and determine if it was feasible to speed up using the GPU.
My application that I selected is a PI approximation method. PI can be approximated in a number of ways however I chose to use the dartboard algorithm. Although not the fastest, the algorithm is very feasible to parallelize. The main idea behind it can be compared to a dartboard – you throw a random number (n) of darts at the board and note down the darts that have landed within it and those that have not. The image below demonstrates this concept:
[[File:Example.jpg]]
Program execution
 
Number of iteration
 
pi() function execution on seconds
 
Approximate value of PI
 
10000000
{| class="wikitable"| Program execution|-| |-| Number of iteration|-| |-| pi() function execution on seconds|-| |-| Approximate value of PI|-| |-| 10000000|-| |-| 0.52|-| |-| 3.142|-| |-| 50000000|-| |-| 2.6|-| |-| 3.1414|-| |-| 100000000|-| |-| 5.15|-| |-| 3.1418|-| |-| 500000000|-| |-| 25.04|-| |-| 3.1417|-| |-| 1000000000|-| |-| 50.15|-| |-| 3.1416|-| |-| 5000000000|-| |-| 110.47|-| |-| 3.1416|-| |-| 10000000000|-| |-| 108.83|-| |-| 3.1415|}
3.142
 
50000000
 
2.6
 
3.1414
 
100000000
 
5.15
 
3.1418
 
500000000
 
25.04
 
3.1417
 
1000000000
 
50.15
 
3.1416
 
5000000000
 
110.47
 
3.1416
 
10000000000
 
108.83
 
3.1415
http://www.mesham.com/article/Dartboard_PI
Problem Description For this assignment, I selected one application that I wished to parallelize. I profiled it to find the hotspot of the application and determine if it was feasible to speed up using the GPU. My application that I selected is a PI approximation method. PI can be approximated in a number of ways however I chose to use the dartboard algorithm. Although not the fastest, the algorithm is very feasible to parallelize. The main idea behind it can be compared to a dartboard – you throw a random number (n) of darts at the board and note down the darts that have landed within it and those that have not. The image below demonstrates this concept: The ratio of the randomly thrown dart is: (hits within dartboard) vs. (hits within square) is equal to the ratio between the two areas i.e. PI/4. The more darts we throw, the better we can approximate PI. Based on the Blaise Barney's pseudo code (shown above), I created an application which simulates the dart throwing n number of times, providing the approximate value of PI. Program execution During the execution, the program takes the number of iterations through the command line. It generates two random decimal numbers between 0 and 1 and determines if the randomly generated coordinates are inside in the circle. Then it calculates the size of PI. As we increase the number of iteration we are getting a more realistic value of PI. I created a screenshot from the first execution, the rest of the execution is summarized on the table and the chart below. Program execution Number of iteration pi() function execution on seconds Approximate value of PI 10000000 0.52 3.142 50000000 2.6 3.1414 100000000 5.15 3.1418 500000000 25.04 3.1417 1000000000 50.15 3.1416 5000000000 110.47 3.1416 10000000000 108.83 3.1415 As we can see the hotspot of the program is the pi () function, which takes 100% of the execution time. This function is containing a single for loop, which is calculating the size of the PI. This can be executed independently, because it has no data dependency, therefor it is possible to parallelize with CUDA to speed up the processing time. Conclusion In the above assignment, I described the dartboard algorithm to calculate the size of the PI. I explained and demonstrated the application which I created based on this algorithm. Finally I located the hotspot of the application and defined that it feasible to speed up using GPU. References: https://computing.llnl.gov/tutorials/parallel_comp/#ExamplesPI http://www.mesham.com/article/Dartboard_PI
=== Assignment 2 ===
=== Assignment 3 ===