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

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

    Раздел 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 тестов. При некорректных аргументах в ответе возможно снижение оценки.