Difference between revisions of "Three-Star"
(→Assignment 2) |
(→Assignment 1) |
||
| Line 11: | Line 11: | ||
==== Calculation of Pi ==== | ==== Calculation of Pi ==== | ||
| − | Chosen to profile calculation of pi as shown here: https://computing.llnl.gov/tutorials/parallel_comp/#ExamplesPI | + | Chosen to profile calculation of pi as shown here: https://computing.llnl.gov/tutorials/parallel_comp/#ExamplesPI . |
| − | Based on the example program MPI Program in C: mpi_pi_reduce.c https://computing.llnl.gov/tutorials/mpi/samples/C/mpi_pi_reduce.c | + | |
| + | Based on the example program MPI Program in C: mpi_pi_reduce.c https://computing.llnl.gov/tutorials/mpi/samples/C/mpi_pi_reduce.c . | ||
| + | |||
| + | ==== LZW Data Compression Algorithm ==== | ||
| + | |||
| + | Timothy Moy profiled. | ||
| + | |||
| + | Original algorithm: https://codereview.stackexchange.com/questions/86543/simple-lzw-compression-algorithm | ||
| + | |||
| + | Summary of Profiles | ||
| + | {| class="wikitable" | ||
| + | |- | ||
| + | ! Size (MB) !! Compress() time in seconds | ||
| + | |- | ||
| + | | 10 || 0.96 | ||
| + | |- | ||
| + | | 15 || 1.35 | ||
| + | |- | ||
| + | | 20 || 1.8 | ||
| + | |- | ||
| + | | 25 || 2.14 | ||
| + | |- | ||
| + | | 30 || 2.64 | ||
| + | |- | ||
| + | | 35 || 3.16 | ||
| + | |- | ||
| + | | 40 || 3.45 | ||
| + | |- | ||
| + | | 45 || 4.24 | ||
| + | |- | ||
| + | | 50 || 4.23 | ||
| + | |} | ||
| + | |||
| + | The compress function seems to have some room for improvement as can be seen in the source code below | ||
| + | |||
| + | 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"); | ||
| + | // Possible area for improvement via reduction | ||
| + | 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(); | ||
| + | } | ||
| + | |||
| + | Note the comment above the second for loop notes we can do something like this: | ||
| + | |||
| + | for (int i = 1; i < n; i+=) a[0] += a[i]; | ||
| + | |||
| + | changed to | ||
| + | |||
| + | for (int s = 1; s <= n/2; s*=2) | ||
| + | for(int j = 0; j < n; j +=2 * s) | ||
| + | a[j] += a[j + s]; | ||
| + | |||
| + | The first for loop is constant and probably won't show much improvement if we parallelize it. As such, the major hotspot in this function is the second for loop. This is especially true since the file might be very large and we may be dealing with millions of characters! | ||
=== Assignment 2 === | === Assignment 2 === | ||
=== Assignment 3 === | === Assignment 3 === | ||
Revision as of 00:20, 21 February 2018
GPU610/DPS915 | Student List | Group and Project Index | Student Resources | Glossary
Contents
Three-Star
Team Members
Progress
Assignment 1
Calculation of Pi
Chosen to profile calculation of pi as shown here: https://computing.llnl.gov/tutorials/parallel_comp/#ExamplesPI .
Based on the example program MPI Program in C: mpi_pi_reduce.c https://computing.llnl.gov/tutorials/mpi/samples/C/mpi_pi_reduce.c .
LZW Data Compression Algorithm
Timothy Moy profiled.
Original algorithm: https://codereview.stackexchange.com/questions/86543/simple-lzw-compression-algorithm
Summary of Profiles
| Size (MB) | Compress() time in seconds |
|---|---|
| 10 | 0.96 |
| 15 | 1.35 |
| 20 | 1.8 |
| 25 | 2.14 |
| 30 | 2.64 |
| 35 | 3.16 |
| 40 | 3.45 |
| 45 | 4.24 |
| 50 | 4.23 |
The compress function seems to have some room for improvement as can be seen in the source code below
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");
// Possible area for improvement via reduction
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();
}
Note the comment above the second for loop notes we can do something like this:
for (int i = 1; i < n; i+=) a[0] += a[i];
changed to
for (int s = 1; s <= n/2; s*=2) for(int j = 0; j < n; j +=2 * s) a[j] += a[j + s];
The first for loop is constant and probably won't show much improvement if we parallelize it. As such, the major hotspot in this function is the second for loop. This is especially true since the file might be very large and we may be dealing with millions of characters!
