Задать вопрос
wataru

Wataru

Разработчик на С++, экс-олимпиадник.
Ответы пользователя по тегу Параллельные вычисления

  • Как найти компоненты связности в графе в распределенной памяти?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Простой подход, если у вас есть выделенный лидер и по графу распространяется одна волна в каждый момент времени.

    Лидер опрашивает остальные сервера по очереди (включая себя), и справшивает их, есть ли у них еще непокрашенные вершины. Если есть, инструктирует их запустить волну. Когда волна закончится, справшивает опять. Когда сервер говорит, что больше непокрашенных вершин нет - лидер переходит к следующему серверу.

    Когда сервер запускает волну - он обходит все вершины у себя, если встречает призрачное ребро, то посылает сообщение другому серверу запустить обход у себя с присоеденненной вершины.
    Чтобы отследить конец волны, перед запуском обхода в другом сервере, каждый сервер отслывает лидеру сообщение, что вот тот сервер теперь будет работать. Когда волна в каком-то сервере заканчивается, он присылает лидеру сообщение, что все закончилось. Лидер поддерживает счетчик - сколько еще серверов работает. Когда счетчик достигает 0, надо еще подождать немного (скажем, пол секунды), на случай реордеринга сообщений. Если в течении этой пол секунды никаких сообщений не пришло, можно запускать новую волну.

    Более сложный вариант - когда у вас сразу запускаются все волны. Опять же, без лидера совсем сложно будет.
    Тут, наверно стоит сначала в каждом отдельном параграфе найти все компоненты связности отдельно. Это будут промежуточные варианты.

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

    Когда сервер получает сообщение о номере по призначному ребру, если этот номер меньше текущего у компоненты, она перекрашивается. И сообщение рассылается по всем остальным призрачным ребрам, торчащим из этой компоненты. Рано или поздно, все вершины одной компоненты по всем серверам будут помечены минимальным номером.

    Чтобы определить, что все закончилось, можно разбить процесс на фазы. В первой фазе все рассылают свои номера. Во второй фазе только те, у кого номера обновились. И т.д. Фаза на сервере начинается после сообщения от лидера. Каждый сервер отправляет на лидер сообщение, когда он закончил рассылать свои номера и были ли там вообще обновления. Сообщения надо делать по tcp с подтверждением. Когда лидер заметит, что никто никаких сообщений больше не рассылал в предыдущей фазе - все сошлось.
    Ответ написан
    1 комментарий
    1 комментарий

  • Как убедиться что атомарные операции будут выполнены точно правильно?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Когда вам важен порядок операций в разных потоках их надо синхронизировать по-другому. Атомарые операции тут точно не помогут. Нужны события. Один поток должен ожидать события, второй - сигнализировать его.

    В стандартной библиотеке самое близкое к этом - std::condition_variable.

    Платформо зависимое решение может быть эффективнее. Какие-нибудь WaitForSingleObject/CreateEvent в винде, например.
    Ответ написан
    Комментировать
    Комментировать

  • Как умно распараллелить вложенный цикл OpenMP?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Внешний цикл по итерацийм не распараллелить, потому что каждая итерация зависит от предыдущей.

    Внутри можно циклы по i объединить все в один.

    Ну и параллельте цикл по i через pragma omp for.
    Ответ написан
    2 комментария
    2 комментария

  • Ошибка Unhandled exception at 0x0099B514 in ConsoleApplication15.exe: 0xC0000094: Integer division by zero. Как исправить это?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Не делить на ноль.

    Засуньте ошибку в переводчик, если по английски не понимаете. Ну не умеют компьютеры нарушать законы математики - еще в школе же учат, что на ноль делить нельзя.

    Очевидно, что size/3 оказывается 0, потому что size меньше 3.

    Надо менять логику. Или отдельно обрабатывать случай size = 0,1,2 или не делить на 3. Вообще, неясно, откуда в этом коде 3 вылезло и что оно означает.
    Ответ написан
    Комментировать
    Комментировать

  • В чем преимущества процессов над потоками?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Главное приемущество: независимость процессов. Потоки делят между собой одну память и ресурсы системы (всякие хандлеры в винде, например).

    Если один из процессов завершится или, что чаще происходит, упадет - остальные не будут затронуты. Плюс эта независимость позволяет делать песочницы для безопасности. Так, все современные браузеры запускают js и вообще каждую вкладку в отдельном процессе. Даже если куллхацкер полностью взломает браузер через специальный сайт, он окажется в процессе, который особо прав никаких не имеет, библиотеки особо интересные туда не загружены, а все общение с внешним миром - через жестко прописанные протоколы ipc (inter-process communication). Так что злодею придется взламывать еще и их.

    Эта же независимость позволяет выполнять работу даже после завершения основного процесса. Так, если вы хотите сделать автообновятор программы, то после скачки/установки нового приложения, надо будет перезапустить основное приложение, чтобы перезаписать исполняемый файл (по крайней мере в винде). Но поток завершится вместе с программой и кто же тогда потом будет ее запускать? А вот процесс останется работать.

    Недостатки тут - ресурсоемкость. С точки зрения системы поднять и поддерживать процесс гораздо больше работы чем сделать это с потоком. Плюс упомянутое выше ipc - это лишняя работа на каждый чих.
    Ответ написан
    Комментировать
    Комментировать

  • Сработает ли деструктор, присвоив atomic?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Не совсем понятно, а чего вы вообще пытаетесь добиться зануляя value? После деструктора весь объект и его член value уничтожаются. Любое обращение к ним - это UB. Соотвтественно вы этот новый 0 никак снаружи пощупать не сможете.

    Теоретически компилятор мог бы понять, что эта инструкция не может иметь никаких эффектов и удалить ее нафиг. Но даже если он этого не сделает - как это должно проверять на висящие указатели, я не понимаю.

    Единственный способ бороться с этим, кажется, это использовать умные указатели. Всякие WeakPtr, которые не уничтожают блок счетчиков при удалении объекта. Если же вы опустились до сырых указателей, то это тупо адрес (число). И просто по нему никак не понять, а что по этому адресу лежит - оригинальный объект или что-то левое.
    Ответ написан
    15 комментариев
    15 комментариев

  • Как завершить все потоки сразу после завершения одного из потоков в си, используя толлько pthread_detach и pthread_join?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Если вызвать exit какой-нибудь, то программа завершится и система прибъет все потоки.
    Ответ написан
    2 комментария
    2 комментария

  • Как здесь распараллелили сортировку OpenMP?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Сортируют параллельно куски массива. В конце объединяют отсортированные части операцией слияния (эта часть не параллельна).

    Надо сказать, реализация ужасна. Последняя часть - слияние, похоже, вообще выполняется за квадрат. Т.е. этот подход сильно медленнее непараллельной сортировки всегда.

    Если уж и параллелить radix sort, то надо параллельно считать сколько в каждом куске каждой цифры, потом высчитать, куда каждая цифра из каждого куска должна попасть, и потом параллельно каждый кусок перетасовать в нужные места.
    Ответ написан
    Комментировать
    Комментировать

  • Как распараллелить цикл for с помощью OpenMP?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Что за A(i, j)?
    Похоже у вас там алгоритм Гаусса, и это должен быть массив.

    Внешний цикл по i нельзя параллелить в Гауссе, а вот вычитание строк можно.
    Допишите перед циклами по j и k это:
    #pragma omp parallel for collapse(2)

    В последних двух циклах тоже нельзя внешний цикл параллелить, ибо результат последующих вычислений зависит от предыдущих итераций. А вот перед внутренним циклом смело втыкайте #pragma omp parallel for.
    Ответ написан

  • Как распараллелить тройной цикл for с помощью OpenMP?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    В вашем примере скорее всего достаточно распаралеллить только циклы по i.

    Но, если у вас n меньше количества потоков, то можно использовать диррективу collapse. Подробнее можете почитать в документации (на странице 185).

    Или можете расплющить 3 вложенных цикла в один руками так:
    int n3 = (n-2)*(n-2)*(n-2);
for (int iteration = 0; iteration < n3; ++iteration) {
  i = iteration / ((n-2)*(n-2)) + 1;
  j = iteration / (n-2) % (n-2) + 1;
  k = iteration % (n-2) + 1;
  // тут идет содержимое трех циклов по i,j,k = 1..n-2
}

    Это просто перенумерация всех троек значений. Каждую тройку индексов i,j,k можно рассматривать как трехзначное число в (N-2)-ичной системе счисления. Поэтому можно каждое число от 0 до (n-2)^3 разложить в n-2)-ичную систему счисления через / и % и получить три индекса.

    Но collapse и, тем более, ручной вариант будут иметь накладные расходы на вычисление индексов. Поэтому их имеет смысл использовать только если у вас n меньше количества доступных потоков.
    Ответ написан
    Комментировать
    Комментировать