Новости
О Центре
Кластер
Обучение
Основной курс по параллельному программированию
Учебные курсы
Магистратура
Дополнительное образование
Работы студентов
Библиотека
Исследования
Конференции
Полезные ссылки
NVIDIA
Контакты
О сайте
Имя:
Пароль:
запомнить:
Забыли пароль? Регистрация

Параллельная реализация

Алгоритм делит исходный массив на n частей по количеству доступных приложению процессоров. Далее следует параллельная область, в которой каждый поток  выполняет сортировку слиянием независимо друг от друга. В конце области обеспечивается синхронизация потоков – выполняется ожидание завершения вычислений всех потоков; далее все потоки завершаются – дальнейшие вычисления продолжает выполнять только основной поток. Им и выполняется слияние n частей массива в один упорядоченный.

 

void merge (int *mas,int first,int mid,int last)

{

      int *Temp_mas = new int[Max_size];

      int first1=first;

      int last1=mid;

      int first2=mid+1;

      int last2=last;

 

      int index=first1;

      for (;(first1<=last1) && (first2<=last2);++index)

      {

            if (mas[first1]<mas[first2])

            {

                  Temp_mas[index]=mas[first1];

                  ++first1;

            }

            else

            {

                  Temp_mas[index]=mas[first2];

                  ++first2;

            }

      }

 

      for (;first1<=last1;++first1,++index)

            Temp_mas[index]=mas[first1];

      for (;first2<=last2;++first2,++index)

            Temp_mas[index]=mas[first2];

      for (index=first;index<=last;++index)

            mas[index]=Temp_mas[index];

 

      delete[] Temp_mas;

}

 

void mergesort (int *mas,int first,int last)

{

      if (first<last)

      {

            int mid=(first+last)/2;

           

            mergesort(mas,first,mid);

            mergesort(mas,mid+1,last);

            merge(mas,first,mid,last);

      }

}

 

void parallel_mergesort(int *mas, int count)

{

 

      int count_stream=omp_get_num_procs();

      int part= count/count_stream;

      int first, last;

           

      #pragma omp parallel private(first,last)

      {

     #pragma omp for

       for(int i=0; i<count_stream; i++)

       {

            first=i*part;

            if(i==(count_stream-1)) last=count-1;

            else last=first+part-1;

            mergesort(mas,first,last);

       }

      }

      int mas_iter[100];

 

      for(int i=0; i<count_stream;i++)

      {

            first=i*part;

            mas_iter[i]=first;

      };

 

      int *tmp_mas = new int[Max_size];

      bool flag= true;

      int j=0;

      while(flag==true)

      {

 

            int tmp_val=10000;

            int tmp_iter=-2;

            for(int i=0; i<count_stream; i++)

            {

                  if((mas_iter[i]!=-1)&&(mas[mas_iter[i]]< tmp_val))

                  {

                        tmp_val=mas[mas_iter[i]];

                        tmp_iter=i;

                  }

            }

 

            last=-3;

            if(tmp_iter==(count_stream-1))last=count-1;

            else last=tmp_iter*part +part -1;

 

            if(tmp_iter>=0)

            {

                  tmp_mas[j]=mas[mas_iter[tmp_iter]];

                  j++;

            }

 

            if(mas_iter[tmp_iter]<last) mas_iter[tmp_iter]++;

            else mas_iter[tmp_iter]=-1;

 

 

            flag=false;

            for(int i=0; i<count_stream; i++)

                  if(mas_iter[i]!=-1) flag=true;

      }

 

      for(int i =0 ; i<count; i++)

            mas[i]=tmp_mas[i];

 

      delete[] tmp_mas;

}

 

Новости

22.10.2012
04.09.2012
05.04.2012
06.03.2012
02.03.2012