HPC OpenMP Project: PinFinder

Introduction

Congratulations -- you have just been hired as a software consultant by the ACME Corporation -- a company well known for their fine products!

To maintain corporate security, ACME:

• Requires every employee to authenticate using a randomly-generated 8-digit personal identification number (PIN).
• Saves the encrypted hash of each employee's PIN in their employee database, not the actual PIN itself.
• Forbids employees from writing down their PINs anywhere -- writing down one's PIN is a fireable offense.

The problem is that employees keep forgetting their PINs, and keep contacting the IT department about it. Having to deal with this problem is consuming too much of the ACME IT department's time.

The IT department tried to solve the problem by writing a pinFinder program to find an employee's PIN by brute-force. Given the hash of a forgetful employee's PIN (retrievable from the employee database), this program uses a loop to go through every possible PIN one at a time, hashing the current PIN, and then comparing the current PIN's hash to the employee's hash. When the two hashes match, the current PIN must be the employee's PIN, so the program displays it.

This program works, but it has some deficiencies. Running on an IT department workstation, the pinFinder program finds some employee PINs quickly but takes a long time for others, depending on the PIN's numerical value. For example, given dd4b21e9ef71e1291183a46b913ae6f2 (the hash of 00000000), the program finds the PIN in less than a second, but given ef775988943825d2871e1cfa75473ec0 (the hash of 999999999), the program takes over a minute. Since the PINs are generated randomly, the IT department's program is taking roughly 30 seconds on average, which is too long.

As a consultant, your primary task is to speed up the pinFinder program. The IT department expects you to use parallelism to "even out" the execution times as much as possible, regardless of an employee's PIN. They will be running your program on a single IT dept workstation, so you should use OpenMP to provide the needed speed boost. Regardless of a PIN's value, your program should terminate as soon as the PIN is found.

Getting Started

The IT department's program is in the file pinFinder.c in the source folder for this project. To speed the compilation, the program's functionality is divided between pinFinder.c and helperFunctions.c. The folder also contains several other files, including tests.c that provides some basic functionality tests, genHash.sh, a shell-script that takes a PIN and produces its hash, and a README file that provides information about the project.

Make a new project folder and download the files from the source folder to your project folder. Starting with the README file, look over each file to get a sense of how the project is structured.

Use the provided Makefile to build the programs; then run pinFinder and tests using the info in the README file. Note that you will need to provide pinFinder with a PIN's hash; you can generate the hash of an arbitrary PIN value using the genHash.sh script.

Start by measuring how long this sequential program is taking to find a given PIN. OpenMP has the omp_get_wtime() function that returns the 'wall clock time', similar to MPI_Wtime(). Modify the program by adding calls to omp_get_wtime() before and after the call to findPinFromHash() to compute how long that function takes. Then modify the final printf() so that it displays both the PIN and the time the program takes to find the PIN.

(Since omp_get_wtime() is an OpenMP function, you will need to #include <omp.h> as well. Hint: if you put this directive in helperFunctions.h, you can call OpenMP functions in either pinFinder.c or helperFunctions.c, since both files #include the helperFunctions.h header file. The Makefile is already set up to link to the OpenMP library.)

When you have this much working, open up a spreadsheet, and for the hashes of the following 'random' PINs: 00000000, 33333333, 55555555, 77777777, and 99999999, run your program three times, record the times in the spreadsheet, and then use the spreadsheet to compute those times' median values. We will use these as baseline values to compare against your parallel version, and as the T₁ values in our Speedup_P computations.

Next, figure out how you are going to speed up this program. This week's lab provides the information you need to solve this problem.

Modify the printf() before the call to findPinFromHash() to have it display the number of threads being used.

When you are ready to test your solution, you can run it with 2 threads by entering:

   OMP_NUM_THREADS=2 ./pinFinder

   OMP_NUM_THREADS=3 ./pinFinder

What happens if the user just runs ./pinFinder without giving OMP_NUM_THREADS=P before it?

Run your program a few times with different numbers of threads (and without OMP_NUM_THREADS=P) to verify that it is working correctly.

When you have your program fully debugged, you are ready to begin collecting performance data to present to the ACME IT department and executive team!

Data Collection and Visualization

Data Collection. For the hash of each PIN-value 00000000, 33333333, 555555555, 77777777, and 99999999, for each thread-value P = 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, and 12: run your program three times and record those times in your spreadsheet.

Then use the spreadsheet to compute the medians of those times.

Then use those medians and the medians you computed for the original sequential version to compute the Speedup_P for each value of P.

Next, use your Speedup_P values to compute the Efficiency_P for each value of P.

Visualization. To visualize your data, use your spreadsheet to create the following line-charts:

1. A chart in which you compare the wall-clock times of your program, with Time on the Y-axis and P (the number of threads) on the X-axis.
2. A chart in which you compare the Parallel Speedup_P of your program, with Speedup on the Y-axis and P on the X-axis.
3. A chart in which you compare the Parallel Efficiency_P of the two versions, with Efficiency on the Y-axis and P on the X-axis.

As always, give your charts descriptive titles and label their axes. Make certain the lines for each version can be clearly distinguished on a gray-scale printer by using different line-styles (e.g., solid vs. dashed vs. dotted vs. ...).

Analysis

Things to discuss as you analyze your results:

1. What aspect of this problem prevented you from using OpenMP's #pragma omp parallel for? How did you work around that limitation?
2. Is your program exhibiting the speedup you expected? Why or why not?
3. How effective is your program at "evening out" the times to find different PINs? How do the values of P and the employee's PIN affect this?
4. To solve this problem, you had to choose between the 'chunks' parallel loop and the 'slices' parallel loop. (Or you could try both and use the faster of the two.) Which did you choose, and why? What specific aspects of this problem favor one over the other, or doesn't it matter?
5. What aspect of this problem made it challenging compared to other problems we have examined?
6. Which 'law' applies in this situation: Amdahl's or Gustafson's? Cite your relevant Speedup calculations in your answer.
7. Did you solve this problem using a Data Decomposition or a Task Decomposition strategy? Explain your answer.
8. Did you make any other unexpected or surprising discoveries while completing this project?

Hand In

Hard copies of:

1. Your 2-to-3 page written analysis in which you discuss your program's performance, including its raw performance as the number of threads increases, its respective speedups and efficiencies, what you have learned about which OpenMP parallel loop to use, and anything else you discovered that was interesting, unexpected, or surprising. As always, make your analysis as quantitative as you can, citing specific values from the data you collected to support your claims.
2. If you used AI on this project, add an extra 1-2 pages in which you discuss your use of it, as indicated in the course policies page.
3. Your spreadsheet charts and data showing your programs' timing results, speedups, and efficiencies. As always, print your charts one per page, as large as possible, to maximize the amount of detail that can be seen.
4. A printout of your program's source code, including each file you changed but omitting files you did not change.
5. A screen capture that shows your program's outputs using 10 threads to find the PINs 00000000, 33333333, 55555555, 77777777, and 99999999.

Please staple these pages together and make certain that your name is on each page.

CS > 374 > Exercises > 05 > Homework Project