1

I have a C code for maze generation and I want to use Openmp to parallelise it. I don't understand how to go about it. It doesn't even work if I set all the variables in the loop to private either. I don't understand how the slave threads are gonna start off. The master thread has an initialisation to start off. And can I collapse the nested for loops? Totally newbie to parallelisation.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <omp.h>

int main() {

  clock_t start, end;
  double cpu_time_used;
  int width, height;
  int *maze;
  start = clock();
  printf("enter maze width\n");
  scanf("%d", &width);
  printf("enter maze height\n");
  scanf("%d", &height);
  width = width *2 +1;
  height = height*2 +1;

  /* Validate the size. */
  if(width < 7 || height < 7) {
    printf("error: illegal maze size\n");
    exit(EXIT_FAILURE);
  }

  /* Allocate the maze array. */
  maze = (int*)malloc(width * height * sizeof(char));



  /* Initialize the maze. */
  int x, y;
  for(x = 0; x < width * height; x++) {
    maze[x] = 1;
  }
  maze[1 * width + 1] = 0;

  /* Seed the random number generator. */
  srand(time(0));

  /* Carve the maze. */
  int x1, y1;
  int x2, y2;
  int dx, dy;
  int dir, count;

  /* Set up the entry and exit. */
  maze[0 * width + 1] = 0;
  maze[(height - 1) * width + (width - 2)] = 0;

  #pragma omp parallel for
  for(y = 1; y < height; y += 2) {
    for(x = 1; x < width; x += 2) {

      dir = rand() % 4;
      count = 0;
      while(count < 4) {
        dx = 0; dy = 0;
        switch(dir) {
        case 0:  dx = 1;  break;
        case 1:  dy = 1;  break;
        case 2:  dx = -1; break;
        default: dy = -1; break;
        }
        x1 = x + dx;
        y1 = y + dy;
        x2 = x1 + dx;
        y2 = y1 + dy;
        if(   x2 > 0 && x2 < width && y2 > 0 && y2 < height
            && maze[y1 * width + x1] == 1 && maze[y2 * width + x2] == 1) {
          maze[y1 * width + x1] = 0;
          maze[y2 * width + x2] = 0;
          x = x2; y = y2;
          dir = rand() % 4;
          count = 0;
        } else {
          dir = (dir + 1) % 4;
          count += 1;
        }
      }
    }
  }

  /* Display the maze. */
  /* Graphical view. */
  printf("\n\nMaze in graphical form \n\n");
  for(y = 0; y < height; y++) {
    for(x = 0; x < width; x++) {
      if(maze[y * width + x]){
        printf("##");
      }
      else{
        printf("  ");
      }
    }
    printf("\n");
  }
  /* Matrix View */
  printf("\n\nMaze in matrix form: 0s = wall, 1s =space\n\n");
  for(y = 0; y < height; y++) {
    for(x = 0; x < width; x++) {
      printf("%i ",!maze[y * width + x]);
    }
    printf("\n");
  }

  /* Clean up. */
  free(maze);
  end = clock();
  cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC;
  printf("\ntime taken by program(in milliseconds) to run is %f\n\n",cpu_time_used*1000);

}
SiggiSv
  • 1,219
  • 1
  • 10
  • 20
  • 3
    *Totally newbie to parallelisation* I suggest you start with a much simpler code and build your expertise over a graded sequence of further examples of increasing complexity, introducing more features of OpenMP as you go. As it stands your question is entirely close-worthy for being too broad. – High Performance Mark May 06 '18 at 10:06
  • I know i should start with a much simpler code. Actually i had to check performance between serial and parallel version of the same code. while i wrote the serial code with ease, i dont understand how to use openmp on it. I just need help with the privatising of variables part to get the correct result and hopefully some speed up. – Anshuman Acharya May 06 '18 at 10:26
  • This may help: https://stackoverflow.com/questions/23890539/is-there-any-difference-between-variables-in-a-private-clause-and-variables-defi – Ruud Helderman May 06 '18 at 11:53
  • Besides private variable issues which are easy to fix you will have a bigger problem with `rand`. You can fix that with `rand_r` but it requires a bit more effort https://stackoverflow.com/a/4288024/2542702 – Z boson May 07 '18 at 10:49
  • You define `maze` as a pointer to int buts only allocate it as chars. – Z boson May 07 '18 at 10:52
  • Working code http://coliru.stacked-crooked.com/a/88ceb24cb6132a86 – Z boson May 07 '18 at 12:01
  • Thank you Z boson – Anshuman Acharya May 07 '18 at 12:16
  • Possible duplicate of [Computing entries of a matrix in OpenMP](https://stackoverflow.com/questions/50663749/computing-entries-of-a-matrix-in-openmp) – Yunnosch Jun 03 '18 at 07:26

0 Answers0