Тематический план

  • Содержание учебного материала

    Раздел 1. Блочные вычисления

    Тема 1.1. Оптимизация использования структуры памяти

    Блочное перемножение матриц. Зависимость времени выполнения простых программ от соотношения времени вычислений ко времени обращений к памяти. Множественная сортировка. Неэффективность алгоритма Штрассена.

    Тема 1.2. Модель времени выполнения программы на вычислительной системе

    Архитектура современных процессоров. Сложность вычислений по обращениям к памяти.

    Тема 1.3. Алгоритмы блочных вычислений.

    Тайлинг. Решетчатые графы. Косой тайлинг. Слияние циклов для уменьшения кэш-промахов.

     

    Раздел 2. Преобразования программ

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

    Управляющий граф программы. Граф вызовов функций. Граф информационных связей. Граф зависимостей по данным.

    Тема 2.2. Преобразования линейных участков и циклов

    Подстановка. Протягивание констант. Перестановка блоков.

    Канонизация цикла. Раскрутка цикла. Развертка цикла. Гнездования цикла. Разбиение цикла. Приведение цикла к разбиваемому виду. Слияние циклов.

    Тема 2.3. Распараллеливание циклов

    Распараллеливание циклов на архитектуру MIMD.

    Распараллеливание циклов на архитектуру SIMD.

    Конвейеризация циклов.

     

    Вопросы, выносимые на самостоятельное изучение

    Применение преобразований в компиляторах с открытым кодом LLVM, GCC.


    Полезные материалы

    Учебник по преобразованиям программ

    Как из последовательной программы сделать параллельную?

    Диалоговый высокоуровневый оптимизирующий распараллеливатель

    Быстрые программы = архитектуро-ориентированные алгоритмы и данные

    Проблемы  создания эффективного параллельного программного обеспечения

    Задачи оптимизирующей компиляции для процессоров близкого будущего

  • Задания на разработку блочных и параллельных программ перемножения блочных треугольных матриц

    Блочная верхнее-треугольная матрица имеет вид

     

    А1,1

    А1,2

    А1,3

    А1,N

    0

    А2,2

    А2,3

    А2,N

    ...

    0

    0

    0

    АN,N

     

     

     

     

     

     

     

     

     

     

     

    Диагональные блоки являются верхне-треугольными матрицами.

    Блочная нижнее-треугольная матрица выглядит аналогично.

    Треугольные матрицы хранятся в памяти в виде одномерного массива, в котором подряд выписываются либо строки, либо столбцы. Блочная треугольная матрица также должна храниться в виде одномерного массива, в котором подряд выписываются блочные строки или блочные столбцы. При этом, элементы каждого блока должны лежать в памяти рядом. Элементы каждого блока размещаются, согласно стандарту языка Си, построчно. 

     

    При размещении указанной на рисунке блочной верхнее-треугольной матрицы поблочно построчно блоки расположатся в памяти в следующей последовательности:

     

     А1,1 , А1,2 ,…, А1,N , А2,1 , …, А2,N ,…, АN,N                                    

     

    При размещении этой же матрицы поблочно по столбцам блоки расположатся в памяти в следующей последовательности:

     

     А1,1 , А1,2 , А2,2 , А1,3 , …, А1,N ,…, АN,N                                    

     

    Симметричные матрицы хранятся в памяти как треугольные (либо нижняя, либо верхняя).

     

    Определить зависимость времени выполнения произведения матриц от размера блока. Построить таблицу с результатами численных экспериментов. Построить график зависимости.

    Рассмотреть размеры матриц N = 1440 и 2880 (у этих чисел много делителей). Рассматривать размеры блоков, которые являются делителями размера матриц: 1, 6, 10, 15, 20, 24, 30, 36, 40, 50, 60, 72, 80, 96, 120, 144, 160, 180, 240, 360, 480, 720. 

     

    Для случая N = 1440 рассмотреть типы элементов матриц float и double и сравнить быстродействие, а для случая N = 2880 только double.

     

    Использовать 2 разных компилятора, например, MS-VStudio и С++ семейства GCC. Пробовать разные опции компилятора. 

     

    Рассмотреть и сравнить по производительности разные способы распараллеливания.

    1. параллельно выполнять перемножение двух блоков

    1.1.          одну горизонтальную полосу левого блока в разных ядрах процессора умножать на разные вертикальные полосы второго блока;

    1.2.          разные горизонтальные полосы левого блока в разных ядрах процессора умножать на разные вертикальные полосы второго блока;

    1. в разных вычислительных ядрах параллельно выполнять произведения разных пар блоков.

    2.1.          один блок левой матрицы в разных ядрах процессора умножать на разные блоки правой матрицы;

    2.2.          разные блоки левой матрицы в разных ядрах процессора умножать на разные блоки правой матрицы;

     

    Рассмотреть скалярное (не блочное) размещение данных и блочное перемножение. Сравнить результаты с аналогичным перемножением и блочным размещением.

     

    Определить размер блока, при котором время выполнения минимально. Определить диапазон размеров блоков, в котором значения времени выполнения несущественно отличаются от минимального. 

     

    Проверить корректность (правильность) работы программы.

     

    Отчет оформить в соответствии с ГОСТ 7.32, ГОСТ 19.301-79 ЕСПД (госты старые, но актуальные).

     

    Пример

    Задание 15. Умножения треугольной и прямоугольной матриц

    Написать программу блочного умножения двух матриц C = A*B.

    Матрица  A  прямоугольная.  Хранится в виде одномерного массива по блочным столбцам.

    Матрица  B  нижне -треугольная.  Хранится в виде одномерного массива по блочным строкам.

     

    Распараллелить блочную программу умножения двух матриц C = A*B с использованием технологии OpenMP двумя способами

    ·       Распараллелить каждое перемножение блоков.

    ·       Параллельно выполнять операции над различными блоками.

    Определить оптимальные размеры блоков в обоих случаях.

     

    Провести численные эксперименты и построить таблицу сравнений времени выполнения различных программных реализаций решения задачи. Определить лучшие реализации.

    Проверить корректность (правильность) программ.

    Конец Задания.

     

    Примечание. Своевременное и качественное выполнение задания оценивается в 55 баллов. За задержку в сроках сдачи Отчета по программе снимается 10 баллов.


  • Пример тестовых заданий

         Пример 1. Фрагмент программы

          10   X(K) = A(I+1)

          15   X(K) = 1

          20   B = X(K)

    равносилен ?

          10   X(K) = A(I+1)

          15   X(K) = 1

          20   B = A(I+1)

     

         Пример  2. Фрагмент программы

            X = I+1

            K = I-1

     равносилен следующему ?

            K = I-1

            X = I+1

     

         Пример 3. Фрагмент программы

          DO 99 I = 1, 100

          IF Y(I)<0 goto 99

           K(I) = X(I-1)

    99  CONTINUE

          DO 88 I = 1, 100

            X(I) = A(I+1)

       88 CONTINUE

     эквивалентен следующему циклу?

            DO 99 I = 1, 100

            IF Y(I)<0 goto 99

            X(I) = A(I+1)

            K(I) = X(I-1)

      99  CONTINUE

     

         Пример 4. Цикл

                DO 99 I = 1, 100

    99        X(I) = A(I+1)+K(I)-X(I-1)

    эквивалентен следующему ?

                DO 99 J = 1, 50

                I = 2*J

                X(I-1) = A(I)+K(I-1)-X(I-2)

    99        X(I) = A(I+1)+K(I)-X(I-1)

     

         Пример 5. Можно ли распараллелить на архитектуру SIMD цикл

            DO 99 I = 1, 100

             X(I) = A(I)+5

    99     A(I) = X(I)+1

     

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

    За правильное выполнение тестового задания можно получить максимум 45 баллов – по 9 баллов за каждый тест. В тестовом задании приводится 5 тестов. При некорректных аргументах в ответе возможно снижение оценки.