Блог

Для дипломного задания мне нужно реализовать 4 параллельных алгоритма. Я полный новичок в параллельных алгоритмах, поэтому я не знаю, что изучать, какую технологию мне следует использовать (потоки, 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 в общей памяти.

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

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

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

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

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

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