PARALLEL.RU

Дискуссионный клуб по параллельным вычислениям
Текущее время: 21 июл 18 8:55

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




Начать новую тему Ответить на тему  [ Сообщений: 6 ] 
Автор Сообщение
 Заголовок сообщения: параллельные вычисления, С++
СообщениеДобавлено: 7 окт 11 21:09 
Не в сети

Зарегистрирован: 7 окт 11 21:03
Сообщения: 3
Здравствуйте!
У меня вопрос по параллельным вычислениям.

Задача:
дана последовательность комплексных чисел длины N, нужно найти максимальное по модулю число (или числа), используя P потоков. Нужно выписать все элементы с максимальным по модулю значением и их позиции в векторе.
Сложность должна быть O( N/P+lg(P) )

Пишу в С++.

Мое решение:
последовательность пусть будет vector<double>.
я разбиваю этот вектор на части и посылаю каждому потоку по одной из частей (точнее позиции элементов), каждый поток находит максимальный по модулю элемент (или элементы) в своей части и запоминает их позиции в векторе. Далее используя эти же потоки, сравниваем данные, полученные каждым потоком. Например, первый поток обрабатывает результаты своей работы и второго потока ( например, если его максимальное значение больше, то про результаты второго забываем, если они равны, то объединяем результаты...), третий работает со своими результатами и результатами четвертого потока и.т.д, затем первый обрабатывает свои результаты и бывшего третьего, ну и т.д.

Что возвращают потоки? я бы написала структуру:

Код:
struct data{
  vector<int > index;   // тут сохраняем позиции элементов с макс. по модулю значением
  double max_val;  // а это само значение модуля
};


Вопрос: можно ли это все написать лучше?

Как бы вы решили эту задачу? Можно ли как-то оптимизировать решение, т.е. как-то лучше хранить результаты потоков, может быть лучше использовать другую структуру данных?

И ещё, какие есть хорошие книги по данной теме, по параллельным вычислениям и где можно найти хорошие примеры решения задач?

Заранее спасибо! :)


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: параллельные вычисления, С++
СообщениеДобавлено: 10 окт 11 14:17 
Не в сети

Зарегистрирован: 11 дек 02 19:37
Сообщения: 872
Откуда: НИВЦ МГУ
Вариантов может быть много - пробуйте!


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: параллельные вычисления, С++
СообщениеДобавлено: 12 окт 11 1:20 
Не в сети

Зарегистрирован: 7 окт 11 21:03
Сообщения: 3
Да пробую я, пробую :)
Возникла такая проблема... Пусть у меня есть 4 потока (созданных в main функции). Каждый поток выполняет какую-то задачу (например, находит максимальное число в своей части массива ). После завершения работы, я бы хотела, чтобы 1 поток сравнил свой результат с результатом 3 потока, а 2 с результатом 4. При этом сравнение выполняется в 1 и во 2 потоках соответственно, а 3 и 4 уничтожаются.
Но вот проблема, как сделать так, чтобы потоки дожидались друг друга. Если ставить барьеры, то нужно ждать пока закончат работу все потоки, а pthread_join() тоже не подходит, так как если ставить pthread_join() в 1 потоке, чтобы тот дожидался 3, нет гарантии что 3 закончит работу раньше, чем произойдет вызов pthread_join()...

Что можно сделать? Или нужно ждать пока все потоки закончил работу и вернут результаты в main? (Такое сравнение мне нужно, чтобы получить сложность указанную выше)


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: параллельные вычисления, С++
СообщениеДобавлено: 12 окт 11 10:18 
Не в сети

Зарегистрирован: 11 дек 02 19:37
Сообщения: 872
Откуда: НИВЦ МГУ
Kirgudu писал(а):
Но вот проблема, как сделать так, чтобы потоки дожидались друг друга. Если ставить барьеры, то нужно ждать пока закончат работу все потоки

Сделайте семафоры - на каждую группу потоков свой.

Цитата:
а pthread_join() тоже не подходит, так как если ставить pthread_join() в 1 потоке, чтобы тот дожидался 3, нет гарантии что 3 закончит работу раньше, чем произойдет вызов pthread_join()...

Читайте доки, они рулят:
Код:
  The  pthread_join()  function  waits  for  the  thread specified by thread to terminate.  If that thread has
       already terminated, then pthread_join() returns immediately.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: параллельные вычисления, С++
СообщениеДобавлено: 12 окт 11 20:18 
Не в сети

Зарегистрирован: 7 окт 11 21:03
Сообщения: 3
Спасибо за ответы!!!
Всё, разобралась :D Все оказалось гораздо проще, чем я предполагала...

Но меня мучает ещё одна вещь...
Я пишу в С++. Когда создаю поток, я посылаю в поток какую-то структуру с необходимыми данными:
pthread_create( &threads[count], NULL, hadamard, (void *)threads_data[count] )

Память для этой структуры выделяю динамически с помощью new. Но тут слышала, что якобы не надо использовать для этого new, а лучше malloc...
Правда ли это? Насколько я знаю, и new, и malloc выделяют память в куче, только вот new ещё и инициализирует данные с помощью конструктора.

Вот вопрос, есть ли разница в употреблении функций в данном случае или нет?


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: параллельные вычисления, С++
СообщениеДобавлено: 26 окт 11 12:50 
Не в сети

Зарегистрирован: 11 дек 02 19:37
Сообщения: 872
Откуда: НИВЦ МГУ
Kirgudu писал(а):
Вот вопрос, есть ли разница в употреблении функций в данном случае или нет?


Разницы действительно нет в Вашем случае.


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

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


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

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


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

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