Возникли проблемы с использованием переменной синхронизации в часовне во время распараллеливания

Question

Возникли проблемы с использованием переменной синхронизации в часовне во время распараллеливания

Итак, я работаю над этим проектом и пишу на языке вычислений Chapel. Я уже написал программу, и она отлично работает, когда работает без распараллеливания.

Но потом, когда я добавляю forall утверждения, которые мне нужно распараллелить, программа работает намного быстрее, но не дает нужных мне результатов. Что я знаю, потому что у меня есть состояние гонки на шагах 1, 3, 5 и 7, когда я делаю j = j - 1; поэтому я пытаюсь сделать j синхронизируемая переменная, чтобы это состояние гонки не испортило мои результаты, а затем я скомпилировал и запустил, и моя программа никогда не выходит за пределы шага 1, где находится первая синхронизируемая переменная, поэтому у меня есть основания полагать, что это из-за синхронизируемая переменная, j,

Если у кого-то есть понимание того, как я должен вместо этого распараллеливать или синхронизировать, чтобы сортировать мой последний меш, это было бы здорово. Вот код:

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

3

arrays parallel-processing synchronization chapel

Источник

user3431527 30 мар '14 в 20:38

1 ответ

Другие вопросы по тегам arrays parallel-processing synchronization chapel

user1387346 05 дек '14 в 17:18 2014-12-05 17:18 · Answer 1 · 2014-12-05 17:18

Это не имеет ничего общего с синхронизированными переменными. Ваши двойные петли выглядят так:

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], но поскольку другой i с тем же a может выполнять итерацию одновременно, он может изменить это значение одновременно, что приведет к неопределенным результатам.

Для каждого из этих циклов вы должны разрешить только одного работника на блок (таким образом, на значение 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 :)