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



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

Ключевые слова: оптимизация вычислений, многопоточные вычисления, многоядерные процессоры, OpenCL, аппаратное ускорение, OpenMP, графический ускоритель.

1. Введение

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

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

Другим решением является использование «облачных вычислений», то есть передача за отдельную плату программного кода на выполнение сервисам, предоставляющим мощную ЭВМ. Недостатками такого решения является относительно высокая стоимость вычислений, ожидание в очереди, в случае загруженности сервиса. Так же программный код и результаты вычислений передаются третьей стороне — сервису «облачных вычислений», что не всегда является допустим.

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

− использование возможностей современных многоядерных процессоров;

− использование возможностей имеющихся графических карт или ускорителей на FPGA.

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

2. Способы оптимизации. Обзор и реализация

В качестве тестового примера рассматривалась следующая задача. Требовалось выполнить четыре арифметические операции над двумя векторами А и В , сформировав результат в третьем векторе С . Каждый из векторов содержит миллион компонент, причем компонентами векторов являются числа с плавающей запятой двойной точности. Числа сформированы случайным образом с равномерным распределением в диапазоне от 0 до величины RAND_MAX, которая равна 0x7fff. Подобную задачу часто приходится выполнять в процессе обработки графических данных для получения фотореалистичных изображений (ray trace) [1].

В распоряжении доступен компьютер со следующими основными компонентами, которые могут выступать в качестве вычислителя: ЦП — A10–7800P, с тактовой частотой 1.8 ГГц, 4 ядра, 4 потока и графический ускоритель — AMD M340DX.

Поставленная вычислительная задача реализована на языке программирования C++ с использованием компилятора MSVC v142. Для чистоты эксперимента использовалась конфигурация сборки приложения с настройками по умолчанию. Получение результирующего вектора для одной математической операции, требует выполнения 10 ⁶ вычислений над разными парами вещественных чисел, как показано на рисунке 1. Вычисление результата операции для каждой следующей пары не завит от предыдущего вычисления, в совокупности со стандартными настройками компилятора, полученные данные будут в меньшей степени зависеть от аппаратной части и, следовательно, будут универсальны.

В ходе производимых вычислений будет фиксироваться время выполнения задачи и определяться объем используемой оперативной памяти. Для нахождения более точных значений выполним 1000 прогонов программы и определим средние значения искомых величин. Такое количество прогонов программы позволит минимизировать влияние системных процессов на фиксируемые количественные характеристики.

Рис. 1. Операция над парами чисел

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

Таблица 1

Характеристики базового варианта вычислений без оптимизации

Время (мс)	882.62
Память (МБ)	34

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

Его и будем использовать в качестве базового варианта.

Для сокращения времени нахождения результата можно предложить четыре возможных способа, представленных в таблице 2. Их реализация не требует использования дополнительных аппаратных средств.

Таблица 2

Способы оптимизации

	Название	Описание способа
1	CPU	Многопоточные вычисления на ЦП с ручным делением на потоки
2	CPU_OpenMP	Многопоточные вычисления на ЦП с автоматическим делением на потоки
3	CPU_OpenCL	Многоядерные вычисления на ядрах ЦП
4	GPU	Вычисления на графическом ускорителе (GPU)

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

2.1. Использование библиотеки thread

Первый способ оптимизации (CPU) заключается в разбиении последовательного алгоритма на несколько параллельных потоков, выполняемых в рамках одного процесса [2]. Этот способ требует серьёзной модификации последовательного алгоритма и добавления дополнительных функций, которые будут выполняться в различных потоках. Реализация этого способа предполагает использование стандартных библиотек. В случае использования языка С/С++ библиотека называется thread [2]. В процессе реализации параллельного алгоритма могут встретиться ситуации, в которых предполагается обращение разных потоков к одной области памяти — критические зоны. В таком случает, поток, который инициировал обращение к памяти первым, останавливает остальные потоки, на время пока производит запись или модификацию переменных в памяти. В случае языка C++, описывать логику таких критических зон также придется вручную, с использованием библиотеки mutex [3].

Положительной стороной рассматриваемого способа является возможность полноценной отладки приложения и, следовательно, лучший контроль за ходом выполнения алгоритма. А отрицательной стороной будет сложность разработки параллельно выполняемых ветвей алгоритма, которые могут быть обременены критическими зонами. Вычисления таким способом можно ускорить в количество раз, соответствующих количеству потоков. Инициализация потоков, больше четырех (таблица 3) на процессоре с 4-мя логическими процессорами, приводит к увеличению времени, занимаемого системными процессами для переключения между потоками [4].

Таблица 3

Зависимость времени выполнения приложения от количества потоков

Название способа	Время	Кол-во потоков
Без оптимизации	882.61	1
CPU	537.30	2
CPU	343.20	3
CPU	155.53	4
CPU	251.52	5
CPU	267.10	6

Как видно из таблицы 3, инициализация более 4 потоков, приводит к тому, что на некоторые логические процессоры приходится большая нагрузка, увеличивается время получения результата из-за частого переключения потоков внутри логического процессора.

2.2. Использование библиотеки OpenMP

Второй способ оптимизации программного кода, (CPU_OpenMP), заключается в использовании библиотеки OpenMP [5]. Open Multi-Processing (OpenMP) является открытым стандартом для реализации многопоточных приложений на языках C/C++, содержит набор различных директив компилятора и глобальных переменных для работы с общей памятью. Положительной стороной рассматриваемого способа является отсутствие необходимости в модификации последовательного алгоритма. Распараллеливание происходит путем выделения с помощью директив компилятора блоков, которые необходимо распараллелить. Настройка количества потоков, критических зон и переменных также происходит с использованием директив компилятора. Отрицательной стороной данного способа является отсутствие возможности полноценной отладки такого приложения, и невозможность контролирования хода выполнения многопоточной программы. Для эффективного использования OpenMP разработчик приложения должен знать директивы компилятора и его ключевые слова.

Во время реализации в директивах OpenMP число потоков было задано вручную, равное количеству логических процессоров, ниже представлена таблица 4, в которой сравнивается время выполнения программного кода способами CPU и CPU_OpenMP.

Таблица 4

Зависимость времени выполнения от количества потоков

Время CPU	Время CPU_OpenMP	Кол-во потоков
537.30	557.80	2
343.20	368.41	3
155.53	187.03	4

Сокращение времени вычислений способами CPU и CPU_OpenMP, за счет создания дополнительных потоков, достигается задействованием логических процессоров. Для аппаратной части, которая используется в данном эксперименте, максимальное количество потоков равняется 4. В арифметико-логическом устройстве (АЛУ) каждого логического процессора имеется свой конвейер команд, а так как процесс один, то используется общее адресное пространство, т. е. в один момент времени считывать данные или записывать результат может только один поток. В потоках, инициализированных с помощью thread и OpenMP, для конечной программы внутренние ресурсы ядер/логических процессоров, а именно регистровая память и кэш первого уровня остаются недоступными для использования.

Можно заметить, что ручная оптимизация позволяет получить результаты лучшие, чем автоматическая. Связано это с подключением OpenMP и процессом деления на потоки в рамках процесса. Так, в способе CPU, главный поток команд делится на 4 явных потока, вычисляющие одинаковые интервалы по 250000 пар. В то время как автоматическая оптимизация, делит главный процесс на потоки динамически, то есть уже в процессе выполнения, что приводит к неравномерному распределению нагрузки, как показано на рисунке 2

Рис. 2. Варианты деления процесса на потоки

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

1 #pragma omp parallel for default(none) num_threads(4)

2 for (int i = 0; i < 1000000; i++)

3 {

4 tmp = omp_get_thread_num();

5 #pragma omp critical

6 id.push_back(tmp);

7 }

Листинг 1. Деление основного потока на 4

После выполнения получается массив. Визуализировав значения получается изображение, которое подтверждает утверждение о процедурной инициализации потоков и неравномерной нагрузке. Для того чтобы увидеть то, как OpenMP делит вычислительный процесс на потоки достаточно выборки в 1000 значений (рисунок 3).

Рис. 3. Визуализация распределения нагрузки на потоки OpenMP

Подсчитав количество вычислений на поток, получим график, также подтверждающий неравномерное распределение нагрузки (рисунок 4).

Рис. 4. Распределение вычислительной нагрузки между потоками OpenMP

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

2.3. Использование технологии OpenCL

Третий и четвертый способы (CPU_CL и GPU) используют один открытый стандарт OpenCL [6] для написания компьютерных программ, связанных с параллельными вычислениями на различных графических и центральных процессорах, а также FPGA. В статье [7] описанная цель OpenCL состоит в том, чтобы дополнить открытые отраслевые стандарты для трёхмерной компьютерной графики и звука OpenGL и OpenAL возможностями устройств (GPU, FPGA) для высокопроизводительных вычислений. Этот стандарт, представляет собой фреймворк, позволяющий использовать различные устройства под различные вычислительные задачи. Структура приложения, использующего OpenCL, состоит из двух частей: код, исполняемый на центральном процессоре (хост) и код, исполнение которого перекладывается на ускоряющее устройство (ядро kernel), в роли которого могут быть и другие ядра центрального процессора, встроенный или дискретный графический процессор, или же любое другое устройство, например, FPGA кристалл. Стоит отметить, что для задействования графического процессора, необходима поддержка технологии устройством. Поэтому реализовать ускоритель на старых видеокартах, скорее всего, не получится. Ниже на рисунке 5 представлена общая схема взаимодействия программного кода хоста и ускорителя.

Рис. 5. Схема взаимодействия программного кода хоста и ускорителя

Данные-аргументы, с которыми kernel будет работать, находятся в общей памяти ЭВМ. Программный код kernel’а внешне похож на функцию в языке C. Но вместо привычного типа возвращаемых данных содержит ключевое слово _ kernel . Естественно, такие функции ничего не возвращают. Так как работают они с данными в общей памяти, они модифицируют данные в памяти компьютера. Сама программа kernel может храниться либо в виде переменной строки в хостовой части программы, либо в отдельном файле, который загружается хостом.

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

Третий способ (CPU_CL), задействует ядра центрального процессора, а четвертый способ задействует графический процессор (GPU). Переключение вычислителя происходит путем изменения аргументов одной функции.

3. Анализ результатов

В процессе исполнения также фиксировались время выполнения вычислений для одного результирующего вектора и производилась фиксация занимаемого объёма оперативной памяти приложением (таблица 5). Для удобства вариант, в котором задача решалась «в лоб» одним циклом, обозначен как «Базовый».

Таблица 5

Характеристики способов

Название	Время (мс)	Память (МБайт)
Базовый	882.62	34.57
CPU	155.54	50.57
CPU_OpenMP	187.03	67.53
CPU_OpenCL	18.17	118.46
GPU	5.78	118.45

При описании способа CPU_OpenMP, было отмечено отсутствие контроля за исполнением программного кода, как раз в таблице 3 наблюдается меньшее время вычисления при ручной модификации программного кода (155,54 мс), чем при использовании автоматического распараллеливания (187,03 мс). Это означает что ручной контроль за исполнением программного кода (CPU) позволяет лучше отработать все шаги алгоритма, тем самым сократить время вычислений. Можно заметить, что необходимая оперативная память для способов CPU_OpenCL и GPU, имеет идентичные значения. Это объясняется тем, что программа хоста, которая отвечает за инициализацию устройств и управления ими, одинакова для обоих способов, отличаясь лишь в паре строк, поэтому сегмент данных и сегмент кода в памяти имеют практически одинаковые значения.

Способ CPU_OpenCL, справился с задачей на порядок быстрее, чем способы CPU и CPU_OpenMP, хоть OpenCL использует ту же аппаратную часть, больший прирост достигается задействованием ядер ЦП, не просто конвейеров, а еще внутреннюю регистровую память и свой кэш. Тем самым прирост наблюдается не только в скорости одновременного выполнения 4 конвейеров команд, но и в скорости взаимодействия с памятью. Адресные пространства разные, каждое ядро может взаимодействовать с памятью независимо от других ядер. Функция kernel разделяет общее адресное пространство, поэтому ядра используют свою локальную память, которая в предыдущих способах была недоступна. В один момент времени с памятью могут взаимодействовать все ядра. Именно за счет этого достигается значительное сокращение времени, необходимое для получения результата.

Далее было подсчитано процентное сокращение времени вычислений (таблица 6).

Таблица 6

Сокращение времени получения результата в процентах

Название	Сокращение времени %
Без оптимизации	0
CPU	82.38
CPU_OpenMP	70.18
CPU_OpenCL	97.94
GPU	99.35

4. Выводы

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

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

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

Литература:

1. Что значит логический процессор? [Электронный ресурс] // open-form-it.com: [сайт]. [2020]. URL: https: //open-form-it.com/chto-znachit-logicheskiy-protsessor/ (дата обращения: 16.01.2020).
2. Multithreading with C++17 and C++20 [Электронный ресурс] // modernescpp: [сайт]. [2017]. URL: https://www.modernescpp.com/index.php/multithreading-in-c-17-and-c-20 (дата обращения: 21.12.2019).
3. [C++] MUTEX: Write Your First Concurrent Code // medium. 2019. URL: https://medium.com/swlh/c-mutex-write-your-first-concurrent-code-69ac8b332288 (дата обращения: 30.10.2019).
4. wikipedia. Многопоточность [Электронный ресурс] [2019]. URL: https://ru.wikipedia.org/wiki/Многопоточность (дата обращения: 1.12.2019).
5. OpenMP. Specifications [Электронный ресурс] [2019]. URL: https://www.openmp.org/specifications/ (дата обращения: 23.11.2019).
6. inc. K. G. OpenCL Overview [Электронный ресурс] [2019]. URL: https://www.khronos.org/opencl/ (дата обращения: 16.12.2019).
7. Wikipedia. OpenCL [Электронный ресурс] [2019]. URL: https://ru.wikipedia.org/wiki/OpenCL (дата обращения: 11.11.2019).
8. wikipedia. Временная многопоточность [Электронный ресурс] // wikipedia.org: [сайт]. [2019]. URL: https://ru.wikipedia.org/wiki/Временная_многопоточность (дата обращения: 27.11.2019).
9. Давлеткалиев Р. Ускорения параллельных вычислений [Электронный ресурс] [19]. URL: https://habr.com/ru/post/127007/ (дата обращения: 11.11.19).
10. «Хакер» Ж. CUDA мы катимся: технология NVIDIA CUDA [Электронный ресурс] [2019]. URL: https://xakep.ru/2009/03/18/47507/ (дата обращения: 16.11.19).
11. Косихин В. удар по ядрам: обзор архитектуры GCN [Электронный ресурс] [2011]. URL: https://3dnews.ru/621828 (дата обращения: 1.12.2019).
12. Wikipedia. Ray_tracing_(graphics) [Электронный ресурс] [2019]. URL: https://en.wikipedia.org/wiki/Ray_tracing_(graphics) (дата обращения: 3.1.2020).