Parallelizing Code

Writing parallel code can be challenging. The traditional methods would require you to define threads which are part of a program that can be run concurrently while sharing some resources (memory) but that are still part of one program or process. A multithreaded program needs to be written to manage its threads and ensure that they all execute correctly as well as managing shared resources to ensure threads do not interfere with each other. If you are interested in what this looks like in C, view the source code for the crackParallel.c program you built and ran.

Fortunately, we can utilize a library to do most of this work for us. OpenMP is an open-source standard that is utilized in many programming languages to make writing multithreaded programs easier. To get exposure to how ridiculously easy this is, we'll walk you through and example. Consider again the crackSequential program that you built and ran to break passwords. We'll modify this program using OpenMP so that it can be run in parallel.

Instructions

1. Open the crackParallel-openmp.c in an editor and briefly compare it to the crackSequential.c. We recommend you use the pico editor. From the command line use:
   
   pico crackParallel-open.c
   
   This will open a TUI (Text User Interface) editor. You can start typing/deleting. When you are done, exit the editor using control-X and it will prompt you if you want to save or not; type Y to save.
   
   Some code to support the number of threads as a command line argument has already been provided for you.
2. Include the OpenMP library by adding the following include statement.
   #include <omp.h>
3. After the dictionary has been loaded (the call to the initDictionary()), add the following line. This will setup OpenMP to use the specified number of threads.
   omp_set_num_threads(numThreads);
4. Now for the magic. Add the following line above the for loop:
   #pragma omp parallel for private(password,j,hash),shared(hashedPassword,m,DICTIONARY),schedule(guided, 2000)
   Let's understand what this is doing:
   • #pragma is a "pragmatic" that tells the compiler to use features of the OpenMP library. It essentially adds the necessary code to make your loop parallel.
   • private(password,j,hash) tells OpenMP which variables should be not be shared between threads and instead makes distinct copies for each thread. For example, the password and j are variables that are updated inside the for loop and are unique to each thread. It wouldn't work if the same value of j were used by all threads.
   • shared(hashedPassword,m,DICTIONARY) specifies variables that are shared among each thread. None of these variables are changed inside the loop and so the same value can be used by all threads. By default, variables are considered shared unless you specify them private so this isn't strictly necessary, but for illustrative purposes, we identified all variables explicitly (and it is best practice).
   • schedule(guided, 2000) tells OpenMP how to split up the work. The outer for loop will execute 247,406 times, once for each word in the dictionary. This line splits it up so that each thread will process (at least) 2,000 words. This is known as a chunk of work. The guided is a strategy by which chunks are divided among threads (but we won't get into specifics on this).
5. Now when your program runs, OpenMP will split the work of testing 247,406 dictionary words among the specified number of threads. For example, if you specify 8 threads, each one will be responsible for checking about about 247,406 / 8 = 30,925 words. You can expect your program to run about 8 times as fast!
6. Let's actually run your program now. Build this OpenMP program by running the following command:
   make crackOpenMP
   which produces an executable called crackOpenMP
7. Run your program similar to how you ran the other version:
   time ./crackOpenMP "0x618e0fcd87c82dea5cbc48b6ca32415951c79d21fc17a9a2e8a6170994b0cb0b" 8

Congratulations on writing your first multithreaded program!