3

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
4

1 に答える 1

2

同期された変数とはあまり関係がありません。二重ループは次のようになります。

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;
    }

これはデータ競合の明らかな原因です。をテストtransferMesh[j]しますが、同じ a を持つ別の i を同時に反復できるため、その値が同時に変更され、未定義の結果が生じる可能性があります。

これらのループごとに、ブロックごとに (つまり、a の値ごとに) ワーカーを 1 つだけ許可する必要があります。したがって、a に対してのみ並列で反復する必要があります。つまり、forall a in 0..26 do for i in 0..1352 {...}

したがって、修正されたコードは簡単に取得できます。

//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

結果 ：

$ chpl sort.chpl ; ./a.out | tail -n 1
Yep the mesh is sorted via SlideSort :)
于 2014-12-05T17:18:59.507 に答える