PARALLEL.RU

Дискуссионный клуб по параллельным вычислениям
Текущее время: 19 ноя 18 4:27

Часовой пояс: UTC + 4 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ Сообщений: 5 ] 
Автор Сообщение
СообщениеДобавлено: 17 ноя 11 0:15 
Не в сети

Зарегистрирован: 16 ноя 11 23:34
Сообщения: 2
В задаче требуется перемножить элементы двух массивов (A[d], B[d]) и заполнить наибольшими произведениями массив C[n] (n<d*d).
Пишу в VS(С++) c OpenMP, ни как не получается распараллелить, я в этом деле новичок, даже не знаю возможно ли это распараллелить хотя задачка не сложная.
Код:
#include<iostream>;
#include<ctime>;
#include <omp.h>;
   using namespace std;            //*****************************************************//
int main()                         //  В задании требуется создать массив(С) максимальных //
{                                  //  значений, произведений элементов двух исходных     //
   setlocale(LC_ALL, "Russian");   //  массивов(А и В)используя параллельное вычисление.  //
   srand(time(0));                 //*****************************************************//

   const int d=30;
   int i,j,n,A[d],B[d],T,k,min;
   
   cout<<"\n  Размер массива С: ";
   cin>>n;
   int *C = new int[n];            

   for(i=0;i<d;i++)               
   {                           
      A[i]=rand()%9+1;            
      B[i]=rand()%9+1;            
   //   cout<<A[i]<<"\t"<<B[i]<<endl;
   }
#pragma omp parallel for
   for(i=0;i<d;i++)               //   Начало фрагмента для распараллеливания
      for(j=0;j<d;j++)
      {
         T=A[i]*B[j];
         if((i*d+j+1)<=n)
            C[i*d+j]=T;
         else
         {
            min=0;
            for(k=1;k<n;k++)
               if(C[min]>C[k])
                  min=k;
            if(T>C[min])
               C[min]=T;
         }
      }                           //   Конец фрагмента для распараллеливания
   /*for(k=0;k<n;k++)
      cout<<C[k]<<" ";
   cout<<endl;*/
   system("pause");
}

Как я понял проблема в нахождении и замене min-ого элемента.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: 27 ноя 11 12:28 
Не в сети

Зарегистрирован: 26 ноя 11 23:34
Сообщения: 3
В таком алгоритме одного "omp parallel for" недостаточно, т.к. есть связи между итерациями (т.е. исполнение k-ой итерации зависит от результатов выполнения предыдущих). Все процессы редактируют весь массив С, и это дело надо как-то синхронизировать, что бы они друг другу не мешали.

Например такие моменты:
Код:
if((i*d+j+1)<=n)
    C[i*d+j]=T;

При параллельном исполнении нет гарантий, что сначала произойдут проходы с выполнением этого условия. Может выйти так, что поток, который будет обрабатывать i с большими значениями, выполнится раньше, чем поток с низкими значениями i. Соответственно, потом выполнится поток, который будет обрабатывать i начиная с 0, и он просто перезапишет С своими значениями без проверки на максимальность.

Переменная min, как я понимаю, объявлена как общая для всех процессов. В этом куске кода процессы будут хаотически перезаписывать переменную min:
Код:
         {
            min=0;
            for(k=1;k<n;k++)
               if(C[min]>C[k])
                  min=k;
            if(T>C[min])
               C[min]=T;
         }

Т.е. один процесс начинает выполнение, доходит до какого-то k < n, находит какой-то минимум среди эл-тов 0 - k, записывает в min его номер, а в этот момент другой процесс тоже начинает выполнение этого куска и делает min = 0; первый процесс про это не знает и продолжает искать минимум в остальной части массива С (от k до n), но сравнивает его не с найденным минимумом, а с C[0].

Вобщем надо сначала продумать как разделить работу между процессами, так что бы они друг другу не мешали, а потом уже параллелить это с omp.

Если значения A и B неотрицательные, я бы просто заполнил сначала C нулями и убрал бы вообще этот if: "if((i*d+j+1)<=n)". Потом объявил бы переменную min?как общую для всех процессов, но перерасчитывал бы её только если Т оказалось больше C[min], и на время перерасчёта и добавления эл-та запрещал бы остальным процессам добавлять эл-ты в массив С и сравнивать с min.

Если я в чём-то не прав, прошу исправить, я тоже новичок в этом деле :-)


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: 27 ноя 11 12:43 
Не в сети

Зарегистрирован: 26 ноя 11 23:34
Сообщения: 3
Хотя есть ещё другой более простой способ распараллелить: в каждом потоке создаём свой массив С, заполняем его максимальными значениями с которыми сталкивается этот поток (получается что зависимостей между потоками нет), а потом ищем n максимальных эл-тов среди этих массивов.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: 27 ноя 11 22:55 
Не в сети

Зарегистрирован: 16 ноя 11 23:34
Сообщения: 2
Спасибо за ответы! (наконец-то дождался)

Хотел бы, более точнее спросить.
Как реализовать поиск min-а, так чтобы только один "процесс"("нить") его искал в С массиве (а после если нужно заменил элемент), а остальные "процессы" ждали/не проходили мимо!!!/ завершения и только после завершения приступал к поиску/замене следующий "процесс". (т.е. пропускать "нити" поочереди через определенный код)???

(Если кому-то покажется, что эта модель не эффективна, скажу только, что операция произведения элементов, это условна, на самом деле в задаче более сложное преобразование)


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: 29 ноя 11 0:05 
Не в сети

Зарегистрирован: 26 ноя 11 23:34
Сообщения: 3
Я бы написал примерно так:
Код:
//объявление переменных и т.п.

min = 0;
for (k = 0; k < n; k++) C[k] = 0;

#pragma omp parallel for private(T)
    for(int i=0;i<d;i++)               //   Начало фрагмента для распараллеливания
        for(int j=0;j<d;j++)
        {
            T=A[i]*B[j];
            #pragma omp critical
            {
                if(C[min]<T)
                {
                    C[min] = T;
                    min = 0;
                    for(int k=1;k<n;k++)
                        if(C[min]>C[k])
                            min=k;
                }
            }
        }                           //   Конец фрагмента для распараллеливания

private(T) объявляет переменную T как private для каждоро процесса. Т.е. для каждого процесса будет создан свой экземпляр этой переменной.
Переменные i,j,k объявляются внутри параллельного блока и поэтому тоже должны быть private.
Переменные C, min, n являются общими для всех процессов. Если один процесс меняет переменную, то это сказывается на всех других.
"#pragma omp critical" объявляет регион в скобках критическим - пока он исполняется одним процессом, другие в него зайти не могут. Вообще для этого есть и другие инструменты, посмотрите например ф-цию omp_set_lock(). Если ф-ция вычисления T не очень сложная, то это место будет сильно тормозить процесс, т.к. тут все процесы будут ждать друг друга.

Вообще стоит прочитать какое-нибудь руководство или учебник по openMP. Там не очень много всего, зато должно снять много вопросов.


Вернуться к началу
 Профиль  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 5 ] 

Часовой пояс: UTC + 4 часа [ Летнее время ]


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 1


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  
cron
Создано на основе phpBB® Forum Software © phpBB Group
Русская поддержка phpBB