Logo Questions Linux Laravel Mysql Ubuntu Git Menu
HTML CSS JAVASCRIPT SQL PYTHON PHP BOOTSTRAP JAVA JQUERY R React Kotlin
 

Having trouble using a sync variable in Chapel during parallelization

Tags:

arrays

synchronization

parallel-processing

chapel

So, I am working on this project and I am writing in Chapel computing language. I already wrote the program and it works perfectly when run un-parallelized.

But then when I add the forall statements that I need to parallelize, the program does run a helluva lot faster but it doesn't provide the results I need. Which I know is because I have a race condition in steps 1, 3, 5 and 7 when I do j = j - 1; so I try and make j a synced variable to prevent this race condition from ruining my results and then I compile, and run and my program never makes it out of step 1, which is where the first synced variable is so I have reason to believe that it is because of the synced variable, j.

If anybody has any insight about how I should parallelize or sync instead so that my final mesh is sorted that would be great. Here's the code:

//SlideSort.chapel_version
//

use Random;
use Time;

config const seed = 2345;
var rs = new RandomStream(seed);
var num: int;
var transferMesh:[0..36530] int;
var copyMesh:[0..36530] int;
var mesh:[0..37883] int;
var i: int;
var z: int;



   proc slideSort(){
      writeln("\nSorting..\n");
/*-------------------------Step 1-------------------------------*/
      writeln("Step 1");
      forall i in 0..36530{
         transferMesh[i] = mesh[i+677];
      }//end for

      forall i in 0..1352{
         forall a in 0..26{
            var value: int = transferMesh[1353*a+i];
            var j$: int = 1353*a+i-1;
               while j$>= 1353*a && transferMesh[j$] > value{
                  transferMesh[j$+1] = transferMesh[j$];
                  j$ = j$ - 1;
               }//end While
               transferMesh[j$+1] = value;
         }//end a_for
      }//end i_for

      forall k in 0..36530{
         mesh[k+677] = transferMesh[k];
      }//end For_k
/*--------------------------Step 2--------------------------------*/
      writeln("Step 2");
         forall k in 677..37207{
            transferMesh[k-677] = mesh[k];
         }//end k_for

         forall k in 0..1352{
            for z in 0..26{
               copyMesh[k+1353*z] = transferMesh[27*k+z];
            }//end z_for
         }//end k_for

         forall k in 0..36530{
            mesh[k+677] = copyMesh[k];
         }//end k_for
/*--------------------------Step 3--------------------------------*/
      writeln("Step 3");
         forall i in 0..36530{
            transferMesh[i] = mesh[i+677];
         }//end for

         forall i in 0..1352{
            forall a in 0..26{
               var value: int = transferMesh[1353*a+i];
               var j: int = 1353*a+i-1;
                  while j>= 1353*a && transferMesh[j] > value{
                     transferMesh[j+1] = transferMesh[j];
                     j = j - 1;
                  }//end While
                  transferMesh[j+1] = value;
            }//end a_for
         }//end i_for

         forall k in 0..36530{
            mesh[k+677] = transferMesh[k];
         }//end For_k
/*--------------------------Step 4--------------------------------*/
      writeln("Step 4");
         forall k in 677..37207{
            transferMesh[k-677] = mesh[k];
         }//end for

         forall k in 0..1352{
            forall z in 0..26{
               copyMesh[27*k+z] = transferMesh[k+1353*z];
            }//end z_for
         }//end k_for

         forall k in 0..36530{
            mesh[k+677] = copyMesh[k];
         }//end k_for
/*--------------------------Step 5--------------------------------*/
      writeln("Step 5");
         forall i in 0..36530{
            transferMesh[i] = mesh[i+677];
         }//end for

         forall i in 0..1352{
            forall a in 0..26{
               var value: int = transferMesh[1353*a+i];
               var j: int = 1353*a+i-1;
                  while j>= 1353*a && transferMesh[j] > value{
                     transferMesh[j+1] = transferMesh[j];
                     j = j - 1;
                  }//end While
                  transferMesh[j+1] = value;
            }//end a_for
         }//end i_for

         forall k in 0..36530{
            mesh[k+677] = transferMesh[k];
         }//end For_k
/*--------------------------Step 6--------------------------------*/
      writeln("Step 6");
        /*This is the padding step, so, since I already have a padded array
          I will simply just sort my padded array in step 7
        */
/*--------------------------Step 7--------------------------------*/
      writeln("Step 7\n");
         forall k in 0..1352{
            forall a in 0..27{
               var value: int = mesh[1353*a+k];
               var j: int = 1353*a+k-1;
               while j >= 1353 *a && mesh[j] > value{
                  mesh[j+1] = mesh [j];
                  j = j - 1;
               }//end while
               mesh[j+1] = value;
            }//end a_for
         }//end k_for


   }//slideSort END
/*^^^^^^^^^^^^^^^^^^^^^^^end slidesort^^^^^^^^^^^^^^^^^^^^^^^^^^^^*/

   proc isSorted() :int{
      var sorted: int = 0;
      for i in 0..37882{
         if mesh[i+1] < mesh[i]{
            writeln("NOT SORTED :(");
            sorted = 1;
            break;
         }//if
      }//end For
      return sorted;
   }// isSorted END



proc main(){

/*Padding array with -INF*/
   for i in 0..676 do mesh[i] = -1000000;

/*Filling array with random ints*/
   for i in 677..37207{
      num = (301 * rs.getNext()): int;
      mesh[i] = num;
   }//end for

/*Padding array with +INF*/
   for i in 37208..37883 do mesh[i] = 1000000;


   writeln("\n200th Element: ", mesh[199],"\n1000th Element: ", mesh[999]);
   writeln("30000th Element: ", mesh[29999], "\n37300th Element: ", mesh[37299]);

   const startTime = getCurrentTime();
   slideSort();
   const endTime = getCurrentTime();

   writeln("\n200th Element: ", mesh[199], "\n1000th Element: ", mesh[999]);
   writeln("30000th Element: ", mesh[29999], "\n37300th Element: ", mesh[37299]);

   writeln("\n\nElapsed time was: ", (endTime - startTime));

   if(isSorted()==0) then writeln("\nYep the mesh is sorted via SlideSort :)");

   write("\nWould you like to print out every 100th element of the Mesh?\n",
           "'Y' for yes\n",
           "'N' for no\n");
   var print: string = "N";
   print = stdin.read(string);

   if print == "Y" || print == "y"{
      for i in 0..37883 by 100{
         write(mesh[i],"\n");
      }//end innerFor
   }//end if

}//end MAIN
like image 307
the warlock Avatar asked Apr 21 '26 04:04

the warlock

1 Answers

It doesn't have much to do with synced variables. Your double loops look like this :

forall i in 0..1352 do
    forall a in 0..26
    {
        var j = 1353*a+i;
        var v = transferMesh[j];

        while( j>= 1353*a )
        {
            if( transferMesh[j] <= v )
                break;

            transferMesh[j+1] = transferMesh[j];
            j--;
        }

        transferMesh[j+1] = v;
    }

This is an obvious source of data races. You test transferMesh[j], but since another i with the same a can be iterating simultaneously, it could modify that value concurrently, leading to undefined results.

For each of these loops, you should allow only one worker per block (thus per value of a). Thus, you should iterate in parallel only over a, i.e. forall a in 0..26 do for i in 0..1352 {...}

The corrected code is thus easily obtained :

//SlideSort.chapel_version
//

use Random;
use Time;

config const seed = 2345;
var rs = new RandomStream(seed);
var num: int;
var transferMesh:[0..36530] int;
var copyMesh:[0..36530] int;
var mesh:[0..37883] int;
var i: int;
var z: int;



proc slideSort()
{
  writeln("\nSorting..\n");
  /*-------------------------Step 1-------------------------------*/
  writeln("Step 1");
  forall i in 0..36530
  {
    transferMesh[i] = mesh[i+677];
  }//end for

  forall a in 0..26
  {
    for i in 0..1352
    {
      var value: int = transferMesh[1353*a+i];
      var j: int = 1353*a+i-1;
      while j>= 1353*a && transferMesh[j] > value
      {
        transferMesh[j+1] = transferMesh[j];
        j = j - 1;
      }//end While
      transferMesh[j+1] = value;
    }//end i_for
  }//end a_for

  forall k in 0..36530
  {
    mesh[k+677] = transferMesh[k];
  }//end For_k
  /*--------------------------Step 2--------------------------------*/
  writeln("Step 2");
  forall k in 677..37207
  {
    transferMesh[k-677] = mesh[k];
  }//end k_for

  forall z in 0..26
  {
    forall k in 0..1352
    {
      copyMesh[k+1353*z] = transferMesh[27*k+z];
    }//end k_for
  }//end z_for

  forall k in 0..36530
  {
    mesh[k+677] = copyMesh[k];
  }//end k_for
  /*--------------------------Step 3--------------------------------*/
  writeln("Step 3");
  forall i in 0..36530
  {
    transferMesh[i] = mesh[i+677];
  }//end for

  forall a in 0..26
  {
    for i in 0..1352
    {
      var value: int = transferMesh[1353*a+i];
      var j: int = 1353*a+i-1;
      while j>= 1353*a && transferMesh[j] > value
      {
        transferMesh[j+1] = transferMesh[j];
        j = j - 1;
      }//end While
      transferMesh[j+1] = value;
    }//end i_for
  }//end a_for

  forall k in 0..36530
  {
    mesh[k+677] = transferMesh[k];
  }//end For_k
  /*--------------------------Step 4--------------------------------*/
  writeln("Step 4");
  forall k in 677..37207
  {
    transferMesh[k-677] = mesh[k];
  }//end for

  forall k in 0..1352
  {
    for z in 0..26
    {
      copyMesh[27*k+z] = transferMesh[k+1353*z];
    }//end z_for
  }//end k_for

  forall k in 0..36530
  {
    mesh[k+677] = copyMesh[k];
  }//end k_for
  /*--------------------------Step 5--------------------------------*/
  writeln("Step 5");
  forall i in 0..36530
  {
    transferMesh[i] = mesh[i+677];
  }//end for

  forall a in 0..26
  {
    for i in 0..1352
    {
      var value: int = transferMesh[1353*a+i];
      var j: int = 1353*a+i-1;
      while j>= 1353*a && transferMesh[j] > value
      {
        transferMesh[j+1] = transferMesh[j];
        j = j - 1;
      }//end While
      transferMesh[j+1] = value;
    }//end i_for
  }//end a_for

  forall k in 0..36530
  {
    mesh[k+677] = transferMesh[k];
  }//end For_k
  /*--------------------------Step 6--------------------------------*/
  writeln("Step 6");
  /*This is the padding step, so, since I already have a padded array
    I will simply just sort my padded array in step 7
   */
  /*--------------------------Step 7--------------------------------*/
  writeln("Step 7\n");
  forall a in 0..27
  {
    for k in 0..1352
    {
      var value: int = mesh[1353*a+k];
      var j: int = 1353*a+k-1;
      while j >= 1353 *a && mesh[j] > value
      {
        mesh[j+1] = mesh [j];
        j = j - 1;
      }//end while
      mesh[j+1] = value;
    }//end k_for
  }//end a_for


}//slideSort END
/*^^^^^^^^^^^^^^^^^^^^^^^end slidesort^^^^^^^^^^^^^^^^^^^^^^^^^^^^*/

proc isSorted() :int
{
  var sorted: int = 0;
  for i in 0..37882
  {
    if mesh[i+1] < mesh[i]
    {
      writeln("NOT SORTED :(");
      sorted = 1;
      break;
    }//if
  }//end For
  return sorted;
}// isSorted END



proc main()
{

  /*Padding array with -INF*/
  for i in 0..676 do mesh[i] = -1000000;

  /*Filling array with random ints*/
  for i in 677..37207
  {
    num = (301 * rs.getNext()): int;
    mesh[i] = num;
  }//end for

  /*Padding array with +INF*/
  for i in 37208..37883 do mesh[i] = 1000000;


  writeln("\n200th Element: ", mesh[199],"\n1000th Element: ", mesh[999]);
  writeln("30000th Element: ", mesh[29999], "\n37300th Element: ", mesh[37299]);

  const startTime = getCurrentTime();
  slideSort();
  const endTime = getCurrentTime();

  writeln("\n200th Element: ", mesh[199], "\n1000th Element: ", mesh[999]);
  writeln("30000th Element: ", mesh[29999], "\n37300th Element: ", mesh[37299]);

  writeln("\n\nElapsed time was: ", (endTime - startTime));

  if(isSorted()==0) then writeln("\nYep the mesh is sorted via SlideSort :)");

}//end MAIN

Result : 

$ chpl sort.chpl ; ./a.out | tail -n 1
Yep the mesh is sorted via SlideSort :)
like image 156
Cimbali Avatar answered Apr 24 '26 00:04

Cimbali
Sign in to Comment

Related questions

Php query into json
Did the Designers of Rust ever publicly say why the syntax of indexing an array is different to indexing a tuple?
How do I initialize this 2D array with null in Java?
How can one loop in a ruby with 2 variables on Array
How to mix two numpy arrays using a boolean mask to create one of the same size efficiently?
Run recursive function on Javascript array [duplicate]
How to convert byte[] to message with javax.mail library
Find an array element and set it to last in Ruby?
Sort JSON array based on its attributes value
Using loop-for through array to push key-values nested inside, into a different array. Javascript
String to char array and to string array

Donate For Us

If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!