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

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

Мультипроцессоры:

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

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

Параллелизм в приложениях:

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

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

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

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

Параллелизм на уровне цикла:

На уровне гнезда циклов есть несколько инструментов для модификации циклов с целью использования преимущества параллелизма. Вот некоторые из этих инструментов:

• Обмен циклами: возможность замены одного цикла другим без изменения порядка его выполнения. Это достигается за счет сохранения данных в памяти и считывания из них по мере необходимости при каждом проходе кода.
• Развертывание цикла: удаление неиспользуемых переменных из тела цикла путем замены их константами вместо переменных (или функций). Это можно сделать либо вручную, либо автоматически с помощью оптимизатора времени компиляции на основе анализа структуры кода.
• Распределение: процесс, при котором процессоры распределяют рабочую нагрузку (т. е. выполняют код) между собой; это включает в себя распределение задач между различными процессорами в одной системе или между несколькими системами путем их соединения через сети, такие как сети Ethernet/TCP/IP, с использованием специализированных устройств, называемых балансировщиками нагрузки, чтобы каждый процессор имел доступ только тогда, когда это необходимо, вместо того, чтобы тратить ресурсы на ожидание между запросами.

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

Местоположение данных:

Локальность данных программы — это степень, в которой ссылки на данные программы локализованы в памяти. Локальность данных важна для производительности, поскольку она позволяет процессору обращаться к данным в одной и той же строке кэша.

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

Введение в теорию аффинных преобразований:

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

Аффинное преобразование определяется:

Свойство зависимости от данных (DDP) утверждает, что каждый элемент в массиве зависит только от своих непосредственных соседей. Это означает, что если вы знаете значения одного индекса, вы можете вычислить значение других индексов, потому что все они связаны зависимостями со своими соседями.

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

DDP и ISP вместе достаточны для того, чтобы компилятор мог выполнять загрузку и сохранение параллельно, не беспокоясь о недостающих данных. Единственным исключением является то, что если существуют зависимости между различными областями памяти, которые не могут быть нарушены компилятором, то он должен дождаться, пока все они не будут вычислены, прежде чем выдавать инструкцию загрузки или сохранения.

Чтобы распараллеливание стало возможным, компилятор должен уметь определять, к каким частям массива можно обращаться независимо, а к каким нельзя. Это можно сделать, применив алгоритм анализа зависимостей. Этот алгоритм сообщит нам, есть ли какие-либо зависимости между двумя индексами и, следовательно, могут ли они храниться параллельно или нет.

Методы компиляции для использования параллелизма и локальности

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

• Использование теории аффинного преобразования для разделения данных .
• Использование теории аффинных преобразований для разделения циклов .
• Использование теории аффинных преобразований для разделения пространства итераций .
• Использование теории аффинных преобразований для разделения пространства данных .

Вывод

Методы оптимизации, описанные в этой статье, помогут сделать код максимально эффективным. Кроме того, их можно комбинировать с другими оптимизациями компилятора для достижения еще лучших результатов.