Intel Parallel Programming Professional (Introduction)

Intel Parallel Programming Professional (Introduction)

2-е издание, исправленное

Гергель В.П.
Воеводин В.В.
Сысоев А.В.
Баркалов К.А.
Линев А.В.
Кудин А.В.
Кустикова В.Д.
Козинов Е.А.
Сиднев А.А.
Мееров И.Б.

Национальный Открытый Университет “ИНТУИТ”
2016

2

Intel Parallel Programming Professional (Introduction)/ В.П. Гергель , В.В. Воеводин, А.В. Сысоев, К.А.
Баркалов, А.В. Линев, А.В. Кудин , В.Д. Кустикова, Е.А. Козинов, А.А. Сиднев, И.Б. Мееров - М.:
Национальный Открытый Университет “ИНТУИТ”, 2016

В рамках курса рассматриваются математические основы параллельных вычислений, архитектурные
аспекты параллелизма, поддержка параллелизма в ОС, основные технологии параллельных
вычислений. Рассматриваются основные ошибки, возникающие при разработке параллельных
программ, приводятся способы их решения с помощью инструментов Intel. Рассматривается
использование полученных знаний на примере классических разделов численных методов.
Решение огромного количества задач стало возможным благодаря повсеместному внедрению
многоядерных архитектур, а также возрастанию числа вычислительных кластеров. Вычислительные
мощности растут, одни задачи решаются, появляются другие, более сложные и трудоемкие. Для
решения задач, в которых требуется грамотно использовать потенциал платформы, используемой для
их решения, необходимы квалифицированные специалисты, которые обладали бы знаниями как в
прикладных областях, так и в области параллельного программирования.

(c) ООО “ИНТУИТ.РУ”, 2012-2016
(c) Гергель В.П., Воеводин В.В., Сысоев А.В., Баркалов К.А., Линев А.В., Кудин А.В., Кустикова
В.Д., Козинов Е.А., Сиднев А.А., Мееров И.Б., 2012-2016

3

Математические основы параллельных вычислений

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

Цель лекции: Лекция направлена на знакомство слушателей математическими
основами параллельных вычислений.

Презентация к лекции скачать:
http://old.intuit.ru/department/supercomputing/ppinteltt/1/1.pdf

Видеозапись лекции скачать:
http://old.intuit.ru/department/supercomputing/ppinteltt/1/1.zip - (объем - 113 МБ).

Пользователь: почему?

Aijk = Ai-1jk + Bjk + Bjk, i=1,40; j=1,40; k=1,1000

Cray C90, пиковая производительность 960 Mflop/s

do k = 1, 1000
  do j = 1, 40
    do i = 1, 40
      A(i,j,k) = A(i-1,j,k)+B(j,k)+B(j,k)
      

Производительность: 20 Mflop/s на Cray C90

Aijk = Ai-1jk + Bjk + Bjk, i=1,40; j=1,40; k=1,1000

Cray C90, пиковая производительность 960 Mflop/s

do i = 1, 40, 2
  do j = 1, 40
    do k = 1, 1000
      A(i,j,k) = A(i-1,j,k)+2 ∗ B(j,k)
      A(i+1,j,k) = A(i,j,k)+2 ∗ B(j,k)
      

Производительность: 700 Mflop/s на Cray C90

Умножение матриц: все ли просто?

Фрагмент исходного текста:
Возможен ли порядок:

( i, k, j) - ?ДА

4

for( i = 0; i < n; ++i)
   for( j = 0; j < n; ++j)
      for( k = 0; k < n; ++k)
         A[i][j] = A[i][j] + B[i][k]∗C[k][j]

( k, i, j) - ?ДА

( k, j, i) - ?ДА

( j, i, k) - ?ДА

( j, k, i) - ?ДА

Порядок циклов: ( i, j, k)

Почему возможен другой порядок?
А зачем нужен другой порядок?

(сравнение с порядком ( i, j, k) )

Решение задачи на компьютере

5

Графовые модели программ

Будем представлять программы с помощью графов: набор вершин и множество
соединяющих их направленных дуг.

Вершины: процедуры, циклы, линейные участки, операторы, итерации циклов,
срабатывания операторов…

Вершины: итерации циклов.

for( i = 0; i < n; ++i) {
   A[i] = A[i – 1] + 2;
   B[i] = B[i] + A[i];
}
Каждая вершина соответствует двум операторам (телу цикла),
выполненным на одной и той же итерации цикла.

Вершины: срабатывания операторов.

for( i = 0; i < n; ++i) {
   A[i] = A[i – 1] + 2;
   B[i] = B[i] + A[i];
}

Каждая вершина соответствует одному из двух операторов тела
данного цикла, выполненному на некоторой итерации.

Дуги: отражают связь (отношение) между вершинами.

6

Выделяют два типа отношений:

операционное отношение,
информационное отношение.

Дуги: операционное отношение:

Две вершины A и B соединяются направленной дугой тогда и только тогда, когда
вершина B может быть выполнена сразу после вершины A.

Операционное отношение = отношение по передаче управления.

x(i) = a + b(i)        (1)
y(i) = 2∗x(i) – 3      (2)
t1 = y(i)∗ y(i) + 1    (3)
t2 = b(i) – y(i)∗a     (4)

Дуги: информационное отношение:

Две вершины A и B соединяются направленной дугой B тогда и только тогда, когда
вершина использует в качестве аргумента некоторое значение, полученное в вершине
A.

Информационное отношение = отношение по передаче данных.

x(i) = a + b(i)        (1)
y(i) = 2∗x(i) – 3      (2)
t1 = y(i)∗ y(i) + 1    (3)
t2 = b(i) – y(i)∗a     (4)

Четыре основные модели программ

Граф управления программы.

7

Вершины: операторы

Дуги: операционное отношение

for( i = 0; i < n; ++i) {
   A[i] = A[i – 1]+ 2;          (1) 
   B[i] = B[i] + A[i];          (2)
}

Информационный граф программы.

Вершины: операторы

Дуги: информационное отношение

for( i = 0; i < n; ++i) {
   A[i] = A[i – 1]+ 2;          (1) 
   B[i] = B[i] + A[i];          (2)
}

Операционная история программы.

Вершины: срабатывания операторов

Дуги: операционное отношение

for( i = 0; i < n; ++i) {
   A[i] = A[i – 1]+ 2;          (1) 
   B[i] = B[i] + A[i];          (2)
}

Информационная история программы.

Вершины: срабатывания операторов

Дуги: информационное отношение

for( i = 0; i < n; ++i) {
   A[i] = A[i – 1]+ 2;          (1) 
   B[i] = B[i] + A[i];          (2)
}

8

Несколько вопросов…

Может ли информационная история некоторого фрагмента программы иметь 100
вершин и ни одной дуги?

ДА.

for( i = 0; i < 100; ++i)
A[i] = B[i] + C[i]∗x;

Может ли информационная история некоторого фрагмента программы иметь 67
вершин и 3 дуги?

ДА.

for( i = 0; i < 63; ++i)
A[i] = B[i] + C[i]∗x;
x1 = 10;
…
x2 = x1+1;
x3 = x2+2;
x4 = x3+3;

Может ли информационная история некоторого фрагмента программы иметь 20
вершин и 200 дуг?

НЕТ.

Модель некоторого фрагмента программы в качестве подграфа содержит следующий
граф:

Какой моделью могла бы быть исходная модель?

9

Множество графовых моделей программ

Какое отношение выбрать для описания свойств программ?

Операционное отношение?

x(i) = a + b(i)        (1)
y(i) = 2∗x(i) – 3      (2)
t1 = y(i)∗ y(i) + 1    (3)
t2 = b(i) – y(i)∗a     (4)

Информационная структура – это основа анализа свойств программ и алгоритмов.

x(i) = a + b(i)        (1)
y(i) = 2∗x(i) – 3      (2)
t1 = y(i)∗ y(i) + 1    (3)
t2 = b(i) – y(i)∗a     (4)

10