Советы по реализации параллельного алгоритма - PullRequest
Новая
       25

Советы по реализации параллельного алгоритма

0 голосов
/ 27 апреля 2011

Для дипломного задания мне нужно реализовать 4 параллельных алгоритма. Я полностью новичок в параллельных алгоритмах, поэтому не знаю, что изучать, какую технологию использовать (Threads, MPI, OpenMP, ...) и т. Д.

Для ясности ниже приведен Pascal-подобный псевдокод для одного из алгоритмов. 

procedure BROADCAST(D,N,A)
  Step 1: Processor P1
          (i) reads the value in D,
         (ii) stores it in its own memory, and
        (iii) writes it in A(1)

  Step 2: for i = 0 to (logN - 1) do
             for j = 2^i + 1 to 2^(i+1) do in parallel
                Processor Pj
                   (i) reads the value in A(j - 2^i)
                  (ii) stores it in its own memory, and
                 (iii) writes it in A(j)
             end for
           end for
  • D - это данные, подлежащие распределению между процессоры.
  • N - количество процессоров.
  • A - массив длины N в разделяемом память.

1 Ответ

4 голосов
/ 27 апреля 2011

Вот очень краткий обзор трех «методов», которые вы предложили:

  • Потоки: вы получаете большой контроль над тем, что делает ваша программа, но это связано со стоимостью, котораяВы должны сами обрабатывать всю бухгалтерию (мьютексы, семафоры, убедитесь, что нет тупиков, ...).Это хороший выбор, когда у вас есть несколько потоков, которые должны общаться друг с другом.Тем не менее, в вашем случае все ваши темы будут в основном делать то же самое.Кроме того, отладка многопоточной программы очень трудна, и только когда вы думаете, что нашли все ошибки, другой тупик поднимает свою уродливую голову.

  • MPI : этобиблиотека для передачи сообщений между различными процессамиТаким образом, это не очень хорошо для того, что вы пытаетесь сделать здесь.Это было бы, однако, в случае, если вы хотите распараллелить вашу программу на компьютерном кластере.Затем данные необходимо будет передавать между процессами на разных компьютерах.Вот где светится MPI.

  • OpenMP : очень удобная библиотека, которая выполняет все распараллеливание за вас (конечно, вы должны дать ей некоторую информацию, но все же,не нужно беспокоиться о тупиках и тому подобном).Нет необходимости вести бухгалтерский учет, библиотека сделает все это за вас.Что особенно хорошо в OpenMP, так это то, что он работает с прагмами.Вы последовательно кодируете свою программу, тестируете ее, затем добавляете несколько строк #pragma, компилируете с флагом -fopenmp (или любым другим флагом, который хочет ваш конкретный компилятор), и все готово: параллельная программа.Когда вы пропустите необходимый флаг компилятора, прагмы будут игнорироваться, что также делает это очень переносимым решением.Это отлично подходит для программ, где требуется ускорение за счет распараллеливания алгоритмов, но на самом деле не нужно передавать данные между независимыми потоками.

Я бы использовал OpenMP, потому что этоочень, очень простой в использовании, позволяет вам включать / отключать многопоточность без каких-либо изменений в вашем коде, делает почти все для вас и, если повезет, уже включен в ваши библиотеки (по крайней мере, для GCC это так).Вот довольно обширный учебник: https://computing.llnl.gov/tutorials/openMP. В Google вы можете найти еще тонны, их полно в интернете:).

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

...