Assignment Overview: Your portfolio will consist of: • A learni...
Question
Assignment Overview:
Your portfolio will consist of:
• A learning journal that uses the specified template.
• Your source code and data files that use the specified structure.
• It is recommended that you use a revision control system, such as subversion, for maintaining your source code. This will enable your code to be backup up and will also provide a source of evidence in your defence if collusion is suspected.
The module is assessed by evidence that you provide of:
• Analysis of supplied programs and experimentation with them.
• Capturing results and depicting them as graphs.
• Written answers to the given related theoretical questions.
• Writing programs to solve computationally expensive problems that require High Performance Computing.
• Written explanations of your results and reflections of your learning.
Two different technologies, POSIX Threads and CUDA will be combined with one application domain of password cracking. The following sections are first ordered, by technology then by application domain.
Task 1 Parallel and Distributed Systems
1. What are threads and what they are designed to solve?
2. Name and describe two process scheduling policies. Which one is preferable and does the choice of policies have any influence on the behavior of Java threads?
3. Distinguish between Centralized and Distributed systems?
4. Explain transparency in D S?
5. The following three statements contain a flow dependency, an antidependency and an output dependency. Can you identify each? Given that you are allowed to reorder the statements, can you find a permutation that produces the same values for the variables C and B? Show how you can reduce the dependencies by combining or rearranging calculations and using temporary variables.
Note: Show all the works in your report and produce a simple C code simulate the process of producing the C and B values.
B=A+C B=C+D C=B+D
6. What output do the following 2 programs produce and why?
#include <pthread.h>
#include <stdio.h>
#include <pthread.h>
#include <stdio.h>
int counter;
static void * thread_func(void * _tn)
{
int i;
int counter;
static void * thread_func(void * _tn)
{
int i;
for (i = 0; i < 100000; i++)
for (i = 0; i < 100000; i++)
counter++; counter++;
return NULL; return NULL;
}
}
int main() {
int main() {
int i, N = 5; pthread_t t[N];
for (i = 0; i < N; i++)
pthread_create(&t[i], NULL, thread_func, NULL);
for (i = 0; i < N; i++) pthread_join(t[i], NULL);
printf("%d\n", counter);
return 0;
}
int i, N = 5; pthread_t t[N];
for (i = 0; i < N; i++) {
pthread_create(&t[i], NULL, thread_func, NULL);
pthread_join(t[i], NULL);
}
printf("%d\n", counter);
return 0;
}
Task 2: Applications of Matrix Multiplication and Password Cracking using HPC- based CPU system:
Part A: Single Thread Matrix Multiplication
Study the following algorithm that is written for multiplying two matrices A and B and storing the result in C.
Now answer each of the following questions:
• Analyse the above algorithm for its complexity.
• Suggest at least three different ways to speed up the matrix multiplication algorithm given here. (Pay special attention to the utilisation of cache memory to achieve the intended speed up).
• Write your improved algorithms as pseudo-codes using any editor. Also, provide a reasoning as to why you think the suggested algorithm is an improvement over the given algorithm.
• Write a C program that implements matrix multiplication using both the loop as given above and the improved versions that you have written.
• Measure the timing performance of these implemented algorithms. Record your observations. (Remember to use large values of N, M and P – the matrix dimensions when doing this task).
Part B: Write a code to implement matrix multiplication using multithreading
• Write a C program to implement matrix multiplication using multithreading. The number of threads should be configurable at run time, for example, read via an external file.
• The code should print the time it takes to do the matrix multiplication using the given number of threads by averaging it over multiple runs.
• Plot the time it takes to complete the matrix multiplication against the number of threads and identify a sweet spot in terms of the optimal number of threads needed to do the matrix multiplication.
(In doing this exercise, you should use matrices of large sizes e.g. 1024 * 1024 sized matrices).
Part C: Password cracking using POSIX Threads
You will be provided with a template code of encrypting a password using SHA-512 algorithm. You are asked to run a code using the given template to encrypt a password contains TWO uppercase letters and TWO integer numbers (total 4 digits). Afterwards, you need to run the given code to crack the password, i.e. find the plain- text equivalents. An example password is AS12.
1. Run the given cracking program 10 times and calculate the mean running time (Using 2 uppercase letters and 2 integer numbers).
2. In your learning journal make an estimate of how long it would take to run on the same computer if the number of initials were increased to 3. Include your working in your answer.
3. Modify the program to crack the three-initials-two-digits password given in the three_initials variable. An example password is HPC19.
4. Write a short paragraph to compare the running time (average of 10 times) of your three_initials program with your earlier estimate. If your estimate was wrong explain why you think that is.
5. Modify the original version of the program to run on 2 threads. It does not need to do anything fancy, just follow the following algorithm.
• Record the system time a nano second timer
• Launch thread_1 that calls kernel_function_1 that can search for passwords starting from A-M
• Launch thread_2 that calls kernel_function_2 that can search for passwords starting from N-Z
• Wait for thread_1 to finish
• Wait for thread_2 to finish
• Record the system time using a nano second time and print the elapsed time.
6. Compare the results of the mean running time of the original program, (obtained by step no. 1), with the mean running time of the multithread version (10 running times).
Task 3: Applications of Password Cracking and Image Blurring using HPC-based CUDA system
Part A: Password cracking using CUDA
Using the same concept as before, you will now crack passwords using CUDA. Your program will take in an encrypted password and decrypt using many threads. CUDA allows multidimensional thread configurations so your kernel function (which runs on the GPU) will need to be modified according to how you configure the execution command.
Crack passwords using CUDA
Comparison, analysis and evaluation of CUDA version for password cracking (compare with normal and “pthread” version)
Part B: Image blur using multi dimension gaussian matrices (multi-pixel processing)
Your program will decode a PNG file into an array (or 2D array) and apply the gaussian blur filter. Blurring an image reduces noise by taking the average RGB values around a specific pixel and setting its RGB to the mean values individually. For this assessment, you will use a 3x3 matrix however, higher marks will be given to those who allow the user to specify the blur matrix dimensions. This could be 5x5, 7x7, 9x9 etc.
Here is an example of how the blur works:
Suppose you have a 5x5 image such as the following (be aware that the coordinate values may change how you format your 2-dimensional array):
0,4 1,4 2,4 3,4 4,4
0,3 1,3 2,3 3,3 4,3
0,2 1,2 2,2 3,2 4,2
0,1 1,1 2,1 3,1 4,1
0,0 1,0 2,0 3,0 4,0
The shaded region above represents the matrix blur position, the yellow highlighted pixel is the one we want to blur, in this case, we are focusing on pixel 1,2 (x,y) (Centre of the matrix). To apply the blur for this pixel, you would sum all the Red values from the surrounding coordinates including 1,2 (total of 9 R values) and find the average (divide by 9). This is now the new Red value for coordinate 1,2. You must then repeat this for Green and Blue values. This must be repeated throughout the image. If you are working on a pixel which is not fully surrounded by pixels (8 pixels), you must take the average of however many neighbouring pixels there are.
Applying gaussian blur with 3x3 matrix using CUDA
Applying gaussian blur with multiple dimension matrices using CUDA
Your portfolio will consist of:
• A learning journal that uses the specified template.
• Your source code and data files that use the specified structure.
• It is recommended that you use a revision control system, such as subversion, for maintaining your source code. This will enable your code to be backup up and will also provide a source of evidence in your defence if collusion is suspected.
The module is assessed by evidence that you provide of:
• Analysis of supplied programs and experimentation with them.
• Capturing results and depicting them as graphs.
• Written answers to the given related theoretical questions.
• Writing programs to solve computationally expensive problems that require High Performance Computing.
• Written explanations of your results and reflections of your learning.
Two different technologies, POSIX Threads and CUDA will be combined with one application domain of password cracking. The following sections are first ordered, by technology then by application domain.
Task 1 Parallel and Distributed Systems
1. What are threads and what they are designed to solve?
2. Name and describe two process scheduling policies. Which one is preferable and does the choice of policies have any influence on the behavior of Java threads?
3. Distinguish between Centralized and Distributed systems?
4. Explain transparency in D S?
5. The following three statements contain a flow dependency, an antidependency and an output dependency. Can you identify each? Given that you are allowed to reorder the statements, can you find a permutation that produces the same values for the variables C and B? Show how you can reduce the dependencies by combining or rearranging calculations and using temporary variables.
Note: Show all the works in your report and produce a simple C code simulate the process of producing the C and B values.
B=A+C B=C+D C=B+D
6. What output do the following 2 programs produce and why?
#include <pthread.h>
#include <stdio.h>
#include <pthread.h>
#include <stdio.h>
int counter;
static void * thread_func(void * _tn)
{
int i;
int counter;
static void * thread_func(void * _tn)
{
int i;
for (i = 0; i < 100000; i++)
for (i = 0; i < 100000; i++)
counter++; counter++;
return NULL; return NULL;
}
}
int main() {
int main() {
int i, N = 5; pthread_t t[N];
for (i = 0; i < N; i++)
pthread_create(&t[i], NULL, thread_func, NULL);
for (i = 0; i < N; i++) pthread_join(t[i], NULL);
printf("%d\n", counter);
return 0;
}
int i, N = 5; pthread_t t[N];
for (i = 0; i < N; i++) {
pthread_create(&t[i], NULL, thread_func, NULL);
pthread_join(t[i], NULL);
}
printf("%d\n", counter);
return 0;
}
Task 2: Applications of Matrix Multiplication and Password Cracking using HPC- based CPU system:
Part A: Single Thread Matrix Multiplication
Study the following algorithm that is written for multiplying two matrices A and B and storing the result in C.
Now answer each of the following questions:
• Analyse the above algorithm for its complexity.
• Suggest at least three different ways to speed up the matrix multiplication algorithm given here. (Pay special attention to the utilisation of cache memory to achieve the intended speed up).
• Write your improved algorithms as pseudo-codes using any editor. Also, provide a reasoning as to why you think the suggested algorithm is an improvement over the given algorithm.
• Write a C program that implements matrix multiplication using both the loop as given above and the improved versions that you have written.
• Measure the timing performance of these implemented algorithms. Record your observations. (Remember to use large values of N, M and P – the matrix dimensions when doing this task).
Part B: Write a code to implement matrix multiplication using multithreading
• Write a C program to implement matrix multiplication using multithreading. The number of threads should be configurable at run time, for example, read via an external file.
• The code should print the time it takes to do the matrix multiplication using the given number of threads by averaging it over multiple runs.
• Plot the time it takes to complete the matrix multiplication against the number of threads and identify a sweet spot in terms of the optimal number of threads needed to do the matrix multiplication.
(In doing this exercise, you should use matrices of large sizes e.g. 1024 * 1024 sized matrices).
Part C: Password cracking using POSIX Threads
You will be provided with a template code of encrypting a password using SHA-512 algorithm. You are asked to run a code using the given template to encrypt a password contains TWO uppercase letters and TWO integer numbers (total 4 digits). Afterwards, you need to run the given code to crack the password, i.e. find the plain- text equivalents. An example password is AS12.
1. Run the given cracking program 10 times and calculate the mean running time (Using 2 uppercase letters and 2 integer numbers).
2. In your learning journal make an estimate of how long it would take to run on the same computer if the number of initials were increased to 3. Include your working in your answer.
3. Modify the program to crack the three-initials-two-digits password given in the three_initials variable. An example password is HPC19.
4. Write a short paragraph to compare the running time (average of 10 times) of your three_initials program with your earlier estimate. If your estimate was wrong explain why you think that is.
5. Modify the original version of the program to run on 2 threads. It does not need to do anything fancy, just follow the following algorithm.
• Record the system time a nano second timer
• Launch thread_1 that calls kernel_function_1 that can search for passwords starting from A-M
• Launch thread_2 that calls kernel_function_2 that can search for passwords starting from N-Z
• Wait for thread_1 to finish
• Wait for thread_2 to finish
• Record the system time using a nano second time and print the elapsed time.
6. Compare the results of the mean running time of the original program, (obtained by step no. 1), with the mean running time of the multithread version (10 running times).
Task 3: Applications of Password Cracking and Image Blurring using HPC-based CUDA system
Part A: Password cracking using CUDA
Using the same concept as before, you will now crack passwords using CUDA. Your program will take in an encrypted password and decrypt using many threads. CUDA allows multidimensional thread configurations so your kernel function (which runs on the GPU) will need to be modified according to how you configure the execution command.
Crack passwords using CUDA
Comparison, analysis and evaluation of CUDA version for password cracking (compare with normal and “pthread” version)
Part B: Image blur using multi dimension gaussian matrices (multi-pixel processing)
Your program will decode a PNG file into an array (or 2D array) and apply the gaussian blur filter. Blurring an image reduces noise by taking the average RGB values around a specific pixel and setting its RGB to the mean values individually. For this assessment, you will use a 3x3 matrix however, higher marks will be given to those who allow the user to specify the blur matrix dimensions. This could be 5x5, 7x7, 9x9 etc.
Here is an example of how the blur works:
Suppose you have a 5x5 image such as the following (be aware that the coordinate values may change how you format your 2-dimensional array):
0,4 1,4 2,4 3,4 4,4
0,3 1,3 2,3 3,3 4,3
0,2 1,2 2,2 3,2 4,2
0,1 1,1 2,1 3,1 4,1
0,0 1,0 2,0 3,0 4,0
The shaded region above represents the matrix blur position, the yellow highlighted pixel is the one we want to blur, in this case, we are focusing on pixel 1,2 (x,y) (Centre of the matrix). To apply the blur for this pixel, you would sum all the Red values from the surrounding coordinates including 1,2 (total of 9 R values) and find the average (divide by 9). This is now the new Red value for coordinate 1,2. You must then repeat this for Green and Blue values. This must be repeated throughout the image. If you are working on a pixel which is not fully surrounded by pixels (8 pixels), you must take the average of however many neighbouring pixels there are.
Applying gaussian blur with 3x3 matrix using CUDA
Applying gaussian blur with multiple dimension matrices using CUDA
Solution Preview
These solutions may offer step-by-step problem-solving explanations or good writing examples that include modern styles of formatting and construction of bibliographies out of text citations and references.
Students may use these solutions for personal skill-building and practice.
Unethical use is strictly forbidden.
/*
* matrix_utils.c
*/
#include <stdio.h>
#include <stdlib.h>
void print_matrix(float** matrix, int n_rows, int n_columns)
{
for (int i = 0; i < n_rows; i++)
{
for(int j = 0; j < n_columns; j++)
{
printf("%2.2f ", matrix[i][j]);
}
printf("\n");
}
printf("\n");
}
float** random_matrix(const int n_rows, const int n_columns)
{
float** matrix = (float**)malloc(sizeof(float*) * n_rows);
for(int i = 0; i < n_rows; i++)
{
matrix[i] = (float*)malloc(sizeof(float) * n_columns);
for(int j = 0; j < n_columns; j++)
{
matrix[i][j] = rand() % 10;
}
}
return matrix;
}
float** zero_matrix(const int n_rows, const int n_columns)
{
float** matrix = (float**)malloc(sizeof(float*) * n_rows);
for(int i = 0; i < n_rows; i++)
{
matrix[i] = (float*)malloc(sizeof(float) * n_columns);
for(int j = 0; j < n_columns; j++)
{
matrix[i][j] = 0;
}
}
return matrix;
}
void delete_matrix(float** matrix, const int n_rows, const int n_columns)
{
for(int i = 0; i < n_rows; i++)
{
free(matrix[i]);
}
free(matrix);
}
* matrix_utils.c
*/
#include <stdio.h>
#include <stdlib.h>
void print_matrix(float** matrix, int n_rows, int n_columns)
{
for (int i = 0; i < n_rows; i++)
{
for(int j = 0; j < n_columns; j++)
{
printf("%2.2f ", matrix[i][j]);
}
printf("\n");
}
printf("\n");
}
float** random_matrix(const int n_rows, const int n_columns)
{
float** matrix = (float**)malloc(sizeof(float*) * n_rows);
for(int i = 0; i < n_rows; i++)
{
matrix[i] = (float*)malloc(sizeof(float) * n_columns);
for(int j = 0; j < n_columns; j++)
{
matrix[i][j] = rand() % 10;
}
}
return matrix;
}
float** zero_matrix(const int n_rows, const int n_columns)
{
float** matrix = (float**)malloc(sizeof(float*) * n_rows);
for(int i = 0; i < n_rows; i++)
{
matrix[i] = (float*)malloc(sizeof(float) * n_columns);
for(int j = 0; j < n_columns; j++)
{
matrix[i][j] = 0;
}
}
return matrix;
}
void delete_matrix(float** matrix, const int n_rows, const int n_columns)
{
for(int i = 0; i < n_rows; i++)
{
free(matrix[i]);
}
free(matrix);
}
This is only a preview of the solution.
Please use the purchase button to see the entire solution.
Please use the purchase button to see the entire solution.
By purchasing this solution you'll be able to access the following files:
Solution.zip
Purchase Solution
$50.00
View Available
Computer Science Tutors 529 tutors matched
Ionut
(ionut)
Hi! MSc Applied Informatics & Computer Science Engineer. Practical experience in many CS & IT branches.Research work & homework
5/5 (5,654+ sessions)
2 hours avg response
Leo
(Leo)
Hi!
I have been a professor in New York and taught in a math department and in an applied math department.
4.9/5 (5,652+ sessions)
2 hours avg response
Pranay
(math1983)
Ph.D. in mathematics and working as an Assistant Professor in University. I can provide help in mathematics, statistics and allied areas.
4.6/5 (5,512+ sessions)
1 hour avg response