Написание первой параллельной программы с Intel Cilk+

Введение

Участвуя в конкурсе, я столкнулся с проблемой распараллеливания. Начав изучение данного вопроса, я нашёл набор дополнительных инструментов для среды разработки Microsoft Visual Studio и расширение для языка C++, Intel Cilk Plus.

/en-us/articles/intel-cilk-plus/
/sites/default/files/m/d/4/1/d/8/cilk_ppt.pdf

Основными командами в данном расширении являются:

  • cilk_spawn
  • cilk_sync
  • cilk_for

Умножение матрицы на вектор (последовательно)

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

for (i = 0; i < m; i++)
{
 c[i] = 0;
 for (j = 0; j < n; j++)
  {
  c[i] += A[i][j]*b[j]
  }
}

Матрично-векторное умножение - это последовательность вычисления скалярных произведений. Поскольку каждое вычисление скалярного произведения векторов длины n требует выполнения n операций умножения и n-1 операций сложения, его трудоемкость порядка O(n). Для выполнения матрично-векторного умножения необходимо осуществить m операций вычисления скалярного произведения, таким образом, алгоритм имеет трудоемкость порядка O(mn). В процессе изучения последовательного алгоритма получаем таблицу результатов:

N, элементовПоследовательно, ms
20006
600059
12000233
20000731
600006872

Произведя анализ с помощью Intel® VTune™ Amplifier XE, видим, что в основном время тратится на работу цикла:

1.jpg

Умножение матрицы на вектор (параллельно)

Очевидно, что данный процесс можно распараллелить по данным, с помощью внешнего цикла, так как операции внутри цикла независимы друг от друга, это можно сделать с помощью cilk_for.

cilk_for (int i = 0; i<N; i++)
 {
 C[i] = 0;
 for (int j = 0; j < N; j++)
  {
  C[i] += A[i][j]*B[j];
  }
}

Протестировав программу, получим время выполнения:

N, элементов

Параллельный алгоритм
2 потока8 потоков16 потоков32 потока40 потоков
200031101
60003310756
1200012536221515
20000393108634537
6000036151254688408325

Вновь проанализируем программу с помощью Intel Parallel Studio:

3.jpg

Видим, что распараллеливание удалось, так как общем время CPU, в основном, является «идеальным», по мнению анализатора Intel.

Анализ

Составим таблицу сравнения результатов.

N, элементовПоследовательный алгоритм, msПараллельный алгоритм
2 потока8 потоков16 потоков32 потока40 потоков
ВремяУскор-еВремяУскор-еВремяУскор-еВремяУскор-еВремяУскор-е
20006,03,02,01,06,016,00,06,01,06,0
600059,033,01,810,05,978,45,011,86,09,8
12000233,0125,01,936,06,52210,615,015,515,015,5
20000731,0393,01,9108,06,86311,645,016,237,019,8
600006872,03615,01,91254,05,568810,0408,016,8325,021,1

Построим график ускорения от количества потоков, для наглядной иллюстрации проделанной работы.
Вновь проанализируем программу с помощью Intel Parallel Studio:

2.png

Проведя анализ графика мы видим, что чем меньше элементов, тем раньше наступает насыщение, и дальнейшее распараллеливание приведёт к увеличению времени, в следствие overhead.

Вывод

Подводя для себя итоги участия в конкурсе Acceller8, я сделал для себя следующие выводы:

  1. Писать простые параллельные программы не так страшно.
  2. Intel Parallel Amplifier довольно удобный инструмент для разработки параллельных программ.
  3. Cilk+ очень прост в изучении и дает положительные результаты.

Буду рад видеть ваши коментарии по поводу этой статьи %)



PS: моя первая статья, не судите строго.

Para obter informações mais completas sobre otimizações do compilador, consulte nosso aviso de otimização.