Changes

DPS915/CodeCookers

, 18:06, 3 October 2014
no edit summary
== Progress ==
=== Assignment 1 ===
'''Norbert''':Calculation of 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:

[[File:Example.jpg]]

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

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 ===