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

Создать новую статью

27.10.2011 12:00


Введение

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

http://software.intel.com/en-us/articles/intel-cilk-plus/
http://software.intel.com/file/38484

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

  • 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
2000 6
6000 59
12000 233
20000 731
60000 6872

Произведя анализ с помощью 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 потоков
2000 3 1 1 0 1
6000 33 10 7 5 6
12000 125 36 22 15 15
20000 393 108 63 45 37
60000 3615 1254 688 408 325

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

3.jpg

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

Анализ

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

N, элементов Последовательный алгоритм, ms Параллельный алгоритм
2 потока 8 потоков 16 потоков 32 потока 40 потоков
Время Ускор-е Время Ускор-е Время Ускор-е Время Ускор-е Время Ускор-е
2000 6,0 3,0 2,0 1,0 6,0 1 6,0 0,0 6,0 1,0 6,0
6000 59,0 33,0 1,8 10,0 5,9 7 8,4 5,0 11,8 6,0 9,8
12000 233,0 125,0 1,9 36,0 6,5 22 10,6 15,0 15,5 15,0 15,5
20000 731,0 393,0 1,9 108,0 6,8 63 11,6 45,0 16,2 37,0 19,8
60000 6872,0 3615,0 1,9 1254,0 5,5 688 10,0 408,0 16,8 325,0 21,1

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

2.png

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

Вывод

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

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

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



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