Kernal Blas

GPU610/DPS915 | Student List | Group and Project Index | Student Resources | Glossary

Kernal Blas

Team Members

1. Shan Ariel Sioson
2. Joseph Pham

Email All

Progress

Assignment 1

Calculation of Pi

For this assessment, we used code found at helloacm.com

In this version, the value of PI is calculated using the Monte Carlo method. This method states:

1. A circle with radius r in a squre with side length 2r
2. The area of the circle is Πr² and the area of the square is 4r²
3. The ratio of the area of the circle to the area of the square is: Πr² / 4r² = Π / 4
4. If you randomly generate N points inside the square, approximately N * Π / 4 of those points (M) should fall inside the circle.
5. Π is then approximated as:

• N * Π / 4 = M
• Π / 4 = M / N
• Π = 4 * M / N

For simplicity the radius of the circle is 1. With this, we randomly generate points within the area and count the number of times each point falls within the circle, between 0 and 1. We then calculate the ratio and multiply by 4 which will give us the approximation of Π.

When we run the program we see:

1st Run

1000            3.152 - took - 0 millisecs
10000           3.1328 - took - 0 millisecs
100000          3.14744 - took - 9 millisecs
1000000         3.141028 - took - 96 millisecs
10000000        3.1417368 - took - 998 millisecs
100000000       3.1419176 - took - 10035 millisecs

The first column represents the "stride" or the number of digits of pi we are calculating to.

With this method, we can see that the accuracy of the calculation is slightly off. This is due to the randomization of points within the circle. Running the program again will give us slightly different results.

2nd Run

1000            3.12 - took - 0 millisecs
10000           3.1428 - took - 0 millisecs
100000          3.13528 - took - 9 millisecs
1000000         3.143348 - took - 106 millisecs
10000000        3.1414228 - took - 1061 millisecs
100000000       3.14140056 - took - 8281 millisecs

The hotspot within the code lies in the loops. There iteration for the loops is O(n²)

Potential Speedup:

Using Gustafson's Law:

P = 50% of the code
P = 0.50
n = ?

S(n)= n - ( 1 - P ) ∙ ( n - 1 )
Sn = n - ( 1 - .5 ) ∙ ( n - 1 )
Sn =

Data Compression

For this suggested project we used the LZW algorithm from one of the suggested projects.

The compress dictionary copies the file into a new file with a .LZW filetype which uses ASCII

The function that compresses the file initializing with ASCII

void compress(string input, int size, string filename) {
	unordered_map<string, int> compress_dictionary(MAX_DEF);
	//Dictionary initializing with ASCII
	for (int unsigned i = 0; i < 256; i++) {
		compress_dictionary[string(1, i)] = i;
	}
	string current_string;
	unsigned int code;
	unsigned int next_code = 256;
	//Output file for compressed data
	ofstream outputFile;
	outputFile.open(filename + ".lzw");

	for (char& c : input) {
		current_string = current_string + c;
		if (compress_dictionary.find(current_string) == compress_dictionary.end()) {
			if (next_code <= MAX_DEF)
				compress_dictionary.insert(make_pair(current_string, next_code++));
			current_string.erase(current_string.size() - 1);
			outputFile << convert_int_to_bin(compress_dictionary[current_string]);
			current_string = c;
		}
	}
	if (current_string.size())
		outputFile << convert_int_to_bin(compress_dictionary[current_string]);
	outputFile.close();
}

The results of the compression from:

Parallelizing

From one of the suggested improvements in the algorithm post link. A potential improvement is changing from char& c to a const char in the for loop

	for (char& c : input) {

since char& c is not being modified.