1 Message descrambling

The following is a scrambled message:

Zpv!uijol!zpvs!qbjo!boe!zpvs!ifbsucsfbl!bsf!voqsfdfefoufe!jo!uif!ijtupsz!pg!uif!xpsme-!cvu!uifo!zpv!sfbe/

This code was used for encryption:

#include <cstdio>  // Import the printf function
#include "omp.h"   // Import the OpenMP library functions

// Start of program
int main()
{

   // This is a "character array", consisting of 105 letters in byte form.
   char mymessage[] = "This is a placeholder of the original message";

   // The message is encoded by shifting all letters by one, i.e. 
   // A becomes B, c becomes d and so forth. This shift is easy to implement
   // in byte form as all you need to do is to add 1 to a character.
   // To printf a single character, use e.g. 
   //       printf("%c\n", mymessage[0]);
   // To printf the whole array do e.g.   (subtle difference between %c and %s)
   //       printf("%s\n", mymessage);

   /* MISSING CODE: for loop over the 105 characters and adding the value 1 to each entry; */
    
   printf("%s\n", mymessage); // This prints a character array to screen

   return 0; // Exit program
}

1.1 Write decoder

Hint:

  • Analyse the encoder code and undo the encryption.

1.2 Parallelise the decoder with OpenMP

Use suitable pragmas and run the decryption thread-parallel.

Insert a statement in the for-loop that prints the current thread number and decryption result.

Run the code repeatedly and vary the number of threads (OMP_NUM_THREADS). What do you observe?

2 Image decryption

In the blackboard folder “OpenMP training material” you will find two encrypted images (PGM type) as well as the file “CImg.h”. You need to download those to the machine you are working on. See below for a brief explanation of CImg and PGM.

PGM Images in Portable Gray Map (PGM) format store a single grayscale value between 0 and 255 in each pixel.

CImg CImg is a lightweight, header-only, image library for C/C++. Among other things it allows to read, manipulate and write images. Once loaded, the individual pixels of an image can be accessed using the pixel coordinates \(0\leq x\lt w\) and \(0\leq y\lt h\), where \(w\) and \(h\) are image width and height, respectively. CImg is available here: https://cimg.eu/

The following code has been used for encryption:

#define cimg_display  0 // This gets around the need to link to X11

#include "CImg.h"      // import the image library
#include <cstdio>      // import printf

using namespace cimg_library;  // this just saves a lot of typing, e.g.
                               // it allows to just state CImg instead of 
                               // cimg_library::CImg


int main(int argc, char * argv[]) // The main function this time knows about
{                                 // command line arguments

  // Load image.
  CImg<float> img = CImg<float>(argv[1]); // the first argument on the command
                                          // line is the image, e.g.
                                          //  ./a.out  image.pgm
  
  const int w = img.width();      // the width of the image in number of pixels
  const int h = img.height();     // the height of the image in number of pixels
  
  // To access the colour value of a single pixel of the image, you can
  // do:
  //     float data =  img(x,y);
  //
  // x can be any integer with 0 <= x < w
  // y can be any integer with 0 <= y <h
                                          

  // Encode
  for (int r=0;r<300;r++)         // The encoding is done 300 times
  {
      for (int y=0;y<h;y++)       // this loop iterates along the y-direction
      {
          for (int x=0;x<w;x++)   // this loops iterates along the x-direction
          {
            // We swap the colour values of two pixels:
              // 1. store the value at coordinates [(x+r+y)%w , y ] in a temporary variable 'buf'
              float buf = img( (x+r+y)%w, y); // (x+r+y)%w ensures that the first coordinate is < w
               // 2. replace the colour values at [(x+r+y)%w , y] with that of [x,y]
              img( (x+r+y)%w, y) = img(x, y);
              // 3. replace the colour value at [x,y] with that of the original value at [(x+r+y)%w]
              img(x , y) = buf;
          }
      }
  }

  // Write encoded image
  img.save("encoded.pgm");

  return 0;
}

2.1 Write decoder program

Hints:

  • Reverse the encoding operations.
  • Use the smaller of the encoded images to test the correctness of you program.
  • To check for correctness, save the decoded image and view on e.g. your laptop.
  • Use the smaller of the two images to develop you code as the program will run faster with it.

You need these commands on hamilton to compile with g++:

module load gcc/9.3.0
g++ decoder.cxx  -I . -lpthread -fopenmp -o decoder

./decoder encoded.pgm

2.2 Parallelise decoder program with OpenMP

Hint:

  • Analyse the code to see what pragmas are suitable.
  • Not all for-loops can be parallelised

2.3 Measure performance of decoder as function of the number of threads

Hint:

  • You can use omp_get_wtime() that comes with OpenMP for measurements.

  • Use OMP_NUM_THREADS to set the number of threads

  • Suggestion: put all commands into a slurm submission script, e.g.

    #SBATCH ...
...
OMP_NUM_THREADS=1 ./decoder image.pgm
OMP_NUM_THREADS=2 ./decoder image.pgm
OMP_NUM_THREADS=4 ./decoder image.pgm
...

3 Summing up a billion times

The task is to sum all numbers between 1 and \(10^9\) in parallel. We can cross-check our result using the relation \(\sum\limits_{i=1}^N = \frac{N\cdot(N+1)}{2}\)

3.1 Explicit computation

#include <cstdio>
#include "omp.h"

int main()
{
    unsigned long N = 1000000000;
    unsigned long SUMS[4] = {0,0,0,0};

    #pragma omp parallel for
    for (unsigned long i=1;i<N+1;i++)
    {
        SUMS[omp_get_thread_num()]+=i;
    }

    unsigned long result = SUMS[0] + SUMS[1] + SUMS[2] + SUMS[3];

    printf("Result: %lu\n", result);

    return 0;
}
  • Under what circumstances ts this program correct?