Открытая распараллеливающая система (обзор)

В этой теме 0 ответов, 1 участник, последнее обновление  Васильев Владимир Сергеевич 3 мес., 2 нед. назад.

  • Автор
    Сообщения
  • #5641
    @admin

    Не так давно я писал статьи-учебники о параллельном программировании: Учебник по OpenMP и Основы технологии MPI на примерах, но те, кто попробовал писать параллельный код понимают что все это очень сложно. Однако, есть ряд проектов, нацеленных на упрощение этого процесса и даже автоматизацию. В этой статье-заметке мы посмотрим на такой продукт как Оптимизирующая распараллеливающая система.

    Для распределенной модели вычислений (SPMD) разработчики распараллеливающих компиляторов сталкиваются со значительными трудностями, связанными в первую очередь с самой моделью, требующей полного контроля над параллелизмом со стороны программиста.

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

    1. Предназначение Оптимизирующей распараллеливающей системы

    Оптимизирующая распараллеливающая система (ОРС) представляет собой программный инструментальный комплекс, ориентированный на автоматическое распараллеливание программ с процедурных языков программирования на параллельные компьютеры (на данный момент реализована поддержка языка C и небольшое подмножество языков Fortran и Pascal).

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

    • Параллельный код на языке C
    • Код C с процедурами MPI (экспериментально) Код C с выделенными циклами ParDo
    • Код C с выделенными конвейеризуемыми циклами

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

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

    2. Внутреннее представление ОРС

    Основой Оптимизирующей распараллеливающей системы является внутреннее представление. Внутреннее представление ориентируется на многоязыковой вход (Fortran, Pascal, C), на удобство разработки преобразований программ и на возможность генерации кода различных целевых архитектур. На сегодняшний момент в ОРС включены парсеры для языков C (на основе clang с поддержкой C99), Fortran и Pascal (конвертируются через внутреннее представление ОРС). Также внутреннее представление может быть трансформировано для поддержки других языков, в том числе объектно-ориентированных.

    Внутреннее представление (ВП) – это структура данных для хранения информации о программе, а также алгоритмы, облегчающие выполнение преобразований программ. Внутреннее представление ОРС было спроектировано с применением шаблонов проектирования и реализовано на языке C++. ВП представляет связную древовидную структуру и является композицией из четырех деревьев: типов, идентификаторов, выражений и операторов. Каждое из четырех деревьев хранит информацию о какой-то части анализируемой программы. Дерево типов содержит информацию о типах в языке программирования, в том числе о пользовательских типах. Дерево идентификаторов – об именах в программе, их распределение по областям видимости. Дерево выражений представляет выражения в программе, узлы соответствуют операциям, а листья – операндам. Дерево операторов представляет операторы в программе.

    Поскольку С++ не поддерживает автоматическое управление памятью:

    • Все объекты-узлы всех деревьев создаются в динамической памяти.
    • Узел при удалении ответственен за освобождение памяти всех своих поддеревьев.

    Данное решение оправдано с точки зрения единообразия выделения и освобождения памяти, а также легче в реализации чем управление памятью на стеке. На ранних этапах разработки также рассматривалась стратегия с использованием «умных указателей», но на практике такой подход оказался неэффективным.

    Поскольку внутреннее представление ОРС разработано для хранения информации о программах, написанных на языках высокого уровня, то оно должно содержать высокоуровневые конструкции, такие как циклы, массивы, абстрактные типы данных. Большинство конструкций во внутреннем представлении перешли из языка C.

    Например, цикл for во внутреннем представлении называется StmtFor и характеризуется узлом с четырьмя потомками: выражение инициализации (InitExpr), выражение условия (CondExpr), выражение инкремента (IncrExpr) и тело цикла (Body). Соответственно цикл

    for (int i = 1; i <= 10; ++i)

    может быть представлен следующим образом

    InitExpr: i = 1
    CondExpr: i <= 10
    IncrExpr: ++i
    Body: …

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

    3. Библиотека преобразований ОРС

    Библиотека преобразований программ – это основная ценность ОРС. На сегодняшний день библиотека состоит из более чем двух десятков преобразований. Эти преобразования делятся на группы, в зависимости от вида фрагментов исходного текста, к которым они применяются. Написанные преобразования автоматически проверяют условия эквивалентности, основанные на графе информационных связей или на решетчатом графе. Также в ОРС реализованы смешанные вычисления и стандартизация выражений, позволяющие отождествлять выражения вида k+1+1 и 2+k, что бывает необходимо при определении информационных зависимостей в поисках коэффициентов перед переменными.

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

    Подстановка вперед – это преобразование, подставляющее правую часть оператора присваивания вместо последующих выражений левой части этого же оператора (если это не нарушает равносильности). В результате такого преобразования исчезают некоторые информационные зависимости, что может способствовать распараллеливанию, и уменьшается объем выполняемого кода.

    Пример. Данный фрагмент программы

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

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

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

    свою очередь преобразование «вынос общих подвыражений» наоборот направлено на поиск одинаковых выражений и их замену при помощи специально заведенных переменных.

    Пример. Данный оператор

    d = (a + b + c) * (a + b)

    будет заменен на фрагмент

    x = a + b
    d = (x + c) * x

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

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

    Для взаимодействия с ОРС можно воспользоваться диалоговым высокоуровневым оптимизирующим распараллеливателем (ДВОР). Проект ДВОР представляет собой программный инструментальный комплекс, ориентированный на разработку распараллеливающих и оптимизирующих компиляторов с языков программирования высокого уровня (C, Fortran и др.) систем полуавтоматического распараллеливания [5]. ДВОР содержит ряд инструментов, позволяющих автоматически определять возможности параллельного выполнения разных частей программ (в основном циклов). Также стоит отметить то, что данный инструмент позволяет проверить лишь корректность распараллеливания, а вопросы его целесообразности и эффективности возлагаются на пользователя.

    4.1 Граф информационных связей

    В качестве одного из механизмов определения распараллеливаемости участков программ применяется граф информационных связей (ГИС) – ориентированный граф, вершины которого соответствуют вхождениям переменных, а дуга соединяет пару вершин (u, v) если выполняются условия:

    1. Эти вхождения обращаются к одной и той же ячейке памяти (т.е. порождают информационную зависимость);
    2. На графе потока управления программы существует путь от u к v.

    Пример.

    for (i = 1; i < N; ++i)
      A[i] = A[i-1]

    Вхождения переменной A в теле цикла порождают информационную зависимость, поскольку оба обращаются к ячейке памяти A[1]: вхождение A[i] – на первой итерации цикла, а A[i-1] – на второй.

    Информационная зависимость между вхождениями называется циклически независимой (loop independent dependence), если эти вхождения обращаются к одной и той же ячейке памяти на одной и той же итерации цикла. В противном случае дуга называется циклически порожденной.

    4.2 Условия распараллеливания циклов

    Для определения возможности параллельного выполнения итераций цикла на архитектурах SIMD и MIMD используется ГИС. Доказано, что итерации цикла можно выполнять параллельно, если на ГИС не существует циклически порожденных рассматриваемым циклом дуг зависимости [6, c. 3]. Но данное условие является лишь достаточным, поскольку для более точного анализа необходимо учитывать архитектуру целевой системы.

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

    • Границы цикла должны быть известны на этапе компиляции.
    • В теле цикла могут присутствовать только операторы присваивания и циклы DO с единственным входом и единственным выходом.
    • На ГИС рассматриваемого цикла не должно быть дуг зависимости, ведущих от вхождений, выполняющихся раньше, к вхождениям, выполняющимся позже.

    На рисунке приведен пример визуализации графа информационных связей в системе ДВОР.

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

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

    4.3 Реализация распараллеливания в ДВОР

    Поскольку ДВОР использует ОРС, как основу для своих инструментов распараллеливания, его внутреннее представления имеет древовидную структуру. Следовательно, каждому циклу исходной программы соответствует узел ВП. Для применения алгоритмов автоматического определения распараллеливаемости используется механизм пометки узлов ВП. После применения таких алгоритмов каждый цикл может быть помечен набором меток, в зависимости от архитектуры машины, на которой итерации цикла можно выполнять параллельно [6, c.5]. После прохода алгоритма все циклы разделяются на две группы:

    • Не помеченные – циклы, параллельное выполнение которых невозможно ни на одной из поддерживаемых архитектур.
    • Помеченные – циклы, итерации которых можно параллельно выполнять на одной или нескольких архитектурах.

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

    5 Пример использования ДВОР для автоматического распараллеливания программы на языке C

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

    #include <stdlib.h>
    #include <stdio.h>
    #include <time.h>
    
    #define N 1000
    
    void matrix_mul(float** C, float** A, float** B) {
      int i, j, k;
    
      for (i = 0; i < N; ++i) {
        for (j = 0; j < N; ++j) {
          C[i][j] = 0;
          for (k = 0; k < N; ++k) {
            C[i][j] += A[i][k] * B[k][j];
          }
        }
      }
    }
    
    float** init_matrix() {
      float** M = (float**)malloc(sizeof(float*) * N);
    
      for (int i = 0; i < N; ++i) {
        M[i] = (float*)malloc(sizeof(float) * N);
        for (int j = 0; j < N; ++j) {
          M[i][j] = 0 + ((float)rand() / RAND_MAX) * 128;
        }
      }
      return M;
    }
    
    int main(int argc, char const* argv[]) {
      srand(time(0));
      float **A, **B, **C;
      clock_t start = clock();
    
      A = init_matrix();
      B = init_matrix();
      C = init_matrix();
    
      matrix_mul(C, A, B);
      for (int i = 0; i < N; ++i) {
        free(A[i]);
        free(B[i]);
        free(C[i]);
      }
    
      free(A);
      free(B);
      free(C);
    
      clock_t end = clock();
      printf("time: %lf", (double)(end - start) / CLOCKS_PER_SEC);
      return 0;
    }

    Подробнее остановимся на самой функции умножения.

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

    Сгенерированный код функции matrix_mul с включением директив OpenMP:

    void matrix_mul(float** C, float** A, float** B)
    {
        int i;
        int j;
        int k;
    #pragma omp parallel for private(j)
        for (i = 0; i < 1000; i = i + 1)
        {
    #pragma omp parallel for
            for (j = 0; j < 1000; j = j + 1)
            {
                C[i][j] = 0;
    #pragma omp parallel for
                for (k = 0; k < 1000; k = k + 1)
                {
                    C[i][j] = C[i][j] + A[i][k] * B[k][j];
                }
            }
        }
    }

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

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

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

Для ответа в этой теме необходимо авторизоваться.