Intel Parallel Programming Professional (Introduction)

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

Intel Parallel Programming Professional (Introduction)/ В.П. Гергель , В.В. Воеводин, А.В. Сысоев, К.А.
Баркалов, А.В. Линев, А.В. Кудин , В.Д. Кустикова, Е.А. Козинов, А.А. Сиднев, И.Б. Мееров - М.:
Национальный Открытый Университет “ИНТУИТ”, 2016
В рамках курса рассматриваются математические основы параллельных вычислений, архитектурные
аспекты параллелизма, поддержка параллелизма в ОС, основные технологии параллельных
вычислений. Рассматриваются основные ошибки, возникающие при разработке параллельных
программ, приводятся способы их решения с помощью инструментов Intel. Рассматривается
использование полученных знаний на примере классических разделов численных методов.
Решение огромного количества задач стало возможным благодаря повсеместному внедрению
многоядерных архитектур, а также возрастанию числа вычислительных кластеров. Вычислительные
мощности растут, одни задачи решаются, появляются другие, более сложные и трудоемкие. Для
решения задач, в которых требуется грамотно использовать потенциал платформы, используемой для
их решения, необходимы квалифицированные специалисты, которые обладали бы знаниями как в
прикладных областях, так и в области параллельного программирования.
(c) ООО “ИНТУИТ.РУ”, 2012-2016
(c) Гергель В.П., Воеводин В.В., Сысоев А.В., Баркалов К.А., Линев А.В., Кудин А.В., Кустикова
В.Д., Козинов Е.А., Сиднев А.А., Мееров И.Б., 2012-2016

Математические основы параллельных вычислений
В лекции рассматриваются графовые модели программ, понятия информационной
зависимости и избыточности вычислений. Рассматриваются виды параллелизма в
зависимости от параллельной структуры программы. Также затрагиваются вопросы
эквивалентных преобразований программ.
Цель лекции: Лекция направлена на знакомство слушателей математическими
основами параллельных вычислений.
Презентация к лекции скачать:
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) - ?ДА

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) )
Решение задачи на компьютере

Графовые модели программ
Будем представлять программы с помощью графов: набор вершин и множество
соединяющих их направленных дуг.
Вершины: процедуры, циклы, линейные участки, операторы, итерации циклов,
срабатывания операторов…
Вершины: итерации циклов.
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];
}
Каждая вершина соответствует одному из двух операторов тела
данного цикла, выполненному на некоторой итерации.
Дуги: отражают связь (отношение) между вершинами.

Выделяют два типа отношений:
операционное отношение,
информационное отношение.
Дуги: операционное отношение:
Две вершины 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)
Четыре основные модели программ
Граф управления программы.

Вершины: операторы
Дуги: операционное отношение
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)
}

Несколько вопросов…
Может ли информационная история некоторого фрагмента программы иметь 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 дуг?
НЕТ.
Модель некоторого фрагмента программы в качестве подграфа содержит следующий
граф:
Какой моделью могла бы быть исходная модель?

Множество графовых моделей программ
Какое отношение выбрать для описания свойств программ?
Операционное отношение?
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)