УДК 004.42

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

Маркина Маргарита Викторовна – студент МИРЭА – Российского технологического университета

Маличенко Сергей Владимирович – аспирант МИРЭА – Российского технологического университета

Мордвинов Владимир Александрович – кандидат технических наук, профессор МИРЭА – Российского технологического университета

Аннотация: Цель статьи – создание и апробация шаблонов оптимизации исполняемых программ интенсивным масштабированием. Проведено исследование моделей повышения производительности исполняемых программ методом глубокого профилирования. Разработан и представлен обновленный набор методик эффективной оптимизации исполняемых программ, основанный на анализе исходных кодов. Показана продуктивность паттернов оптимизации с необходимостью их дальнейшей модернизации в частях, использования аппаратного обеспечения.

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

Введение

Повышение характеристик исполняемых программ относится к повседневным задачам, решаемым при проектировании сложных программно-аппаратных комплексов (ПАК). Задача улучшения действующих алгоритмов становится решающей при реализации высокопроизводительных систем. Ее эффективное решение способно ключевым образом улучшить характеристики используемых аппаратных ресурсов [1, 2] и рационализировать распределение вычислительных мощностей между исполняемыми процессами.

Согласно предположению, выдвинутым Г. Муром, удвоение вычислительной мощности процессоров происходит каждые 1,5 года [3]. При этом с уменьшением технологических размеров рост производительности замедляется из-за возникновения отрицательно влияющих физических явлений. График зависимости числа транзисторов на плате от времени представлен на рисунке 1.

Рисунок 1. Зависимость числа транзисторов (в логарифмической шкале) на кристалле микропроцессора от времени. Источник: Moore’s Law has held true for more than half a century // Our World in Data URL: https://ourworldindata.org/uploads/2020/11/Transistor-Count-over-time.png (датаобращения: 25.06.2023).

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

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

Критерии оптимизации

Утверждение, согласно которому оптимизацию программы можно проводить только по трем критериям, известно как «Треугольник оптимизации» или «Закон оптимизации Кнута». Это понятие было сформулировано в книге Дональда Кнута «Искусство программирования» (The Art of Computer Programming) [5]. Введенное Д. Кнутом понятие «Треугольник оптимизации» в фабулу обсуждаемой здесь научной тематики указывает на следующие три основных взаимосвязанных критерия оптимизации:

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

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

LoopUnrolling

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

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

Само по себе раскрытие цикла может быть выполнено по-разному, в зависимости от конкретной реализации и целевой архитектуры. Одна из самых простых форм раскрытия цикла — это простое дублирование тела цикла несколько раз. Покажем это на примере одной из авторских проектных разработок. Так, например, если имеется цикл, повторяющийся 5 раз.

Листинг 1. Линейный цикл for.

for (int i = 0; i < 5; i++) { // Тело цикла std::cout << i << std::endl; }

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

Листинг 2. Раскрытие цикла for.

std::cout << i << std::endl; std::cout << i << std::endl; std::cout << i << std::endl; std::cout << i << std::endl; std::cout << i << std::endl;

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

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

Тогда, в развитии вышеприведенного примера в качестве тестового алгоритма предлагается использовать цикл while с 50 итерациями. Замеры времени будут производиться вначале запуска потока выполнения и в конце.

Листинг 3. Тестовый цикл Whilec 50 итерациями.

int number = 50; int i = 0; while (number-- > 0) { ++i; } std::cout << i;

При запуске исполняемой программы в режиме отладки время выполнения заняло 58 мкс., что потребовало 119 Кб памяти.

Листинг 4. Результат работы программы.

/home/user/CLionProjects/prog/cmake-build-debug/prog 50 time_spent = 58 мкс. Process finished with exit code 0

Используя паттерн Loop Unrolling, можно оптимизировать работу алгоритма, придав ему следующий вид.

Листинг 5. Раскрытие цикла While.

int digit = 50; int count = digit / 4; int j = 0; switch (digit % 4) { case 0: do { ++j; case 1: ++j; case 2: ++j; case 3: ++j; } while (count-- > 0); } std::cout << j << std::endl;

Время выполнения уменьшилось до 41 мкс. при использовании 145 Кб.

Листинг 6. Результат работы программы.

/home/user/CLionProjects/prog/cmake-build-debug/prog 50 time_spent = 41 мкс. Process finished with exit code 0

При осуществлении, например, 50 итераций этот показатель является существенным. Как представляется авторами настоящей работы, объяснить подобное достижение можно следующим образом: при выполнении циклов в конце каждой итерации совершается проверка условия цикла. В рассматриваемом случае совершается проверка переменной number на положительное значение. Таким образом, выполняя Loop Unrolling, становится возможным уменьшить количество таких проверок.

SIMD

Паттерн SIMD (Single Instruction Multiple Data) используется для выполнения векторных инструкций, доступных на современных процессорах. Суть его заключается в одновременной обработке нескольких элементов данных с помощью одной инструкции, что позволяет улучшить производительность за счет их параллельной обработки.

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

Листинг 7. Элементарная функция сложения двух векторов.

void addVectorsSimple(const float* vectorA, const float* vectorB, float* result, int size) { for(int i = 0; i < size; i++) { result[i] = vectorA[i] + vectorB[i]; } }

Отсюда сделан промежуточный вывод: сложность исходного алгоритма линейная, каждый элемент первого вектора складывался с соответствующим элементом второго вектора последовательно. Таким образом, на весь процесс сложения двух векторов была затрачена 61 мкс. и 211 Кб RAM памяти.

Аналогичную операцию произведем с использованием паттерна SIMD и одновременной обработкой восьми элементов массива.

Листинг 8. SIMD функция сложения двух векторов.

void addVectorsSIMD(const float* vectorA, const float* vectorB, float* result, int size) { // Цикл, выполняющий SIMD-сложение векторов for (int i = 0; i < size; i += 8) { // Загрузка векторов из памяти auto vector1 = _mm256_load_ps(&vectorA[i]); auto vector2 = _mm256_load_ps(&vectorB[i]); // SIMD-сложение векторов auto resultVector = _mm256_add_ps(vector1, vector2); // Сохранение результата в память _mm256_store_ps(&result[i], resultVector); } }

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

ParallelComputing

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

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

Листинг 9. Параллельное суммирование векторов.

int numThreads = 4; int chunkSize = size / numThreads; std::vector<std::thread> threads(numThreads); // Создание потоков для суммирования частей векторов for (int i = 0; i < numThreads; ++i) { int start = i * chunkSize; int end = (i == numThreads - 1) ? size : (start + chunkSize); threads[i] = std::thread(sumVectors, std::ref(result), std::cref(vec1), std::cref(vec2), start, end); } … // Ожидание завершения всех потоков for (auto& thread : threads) { thread.join(); }

Изначально векторы размером 4 тыс. элементов разбиваются на четыре части, далее каждая часть помещается в отдельный поток. После чего запускается процесс суммирования в отдельном цикле. Использованием такого подхода удалось достичь времени выполнения 8 мкс., но при использовании 1,2 Мб оперативной памяти. Однако полученный результат следует воспринимать через призму значительной сложности: для реализации алгоритма с использованием методов многопоточного программирования необходимо обладать знаниями структур данных, работы потоков и прерываний.

MemoryPool

Memory Pool (Пул памяти) представляет собой структурный паттерн для оптимизации операций выделения и освобождения памяти. Вместо множественных вызовов операторов new/delete или malloc/free, используется предварительно выделенный пул памяти. Это уменьшает накладные расходы на управление памятью и улучшает производительность. Проиллюстрировать его работу можно следующим листингом – одного из многих в проектах авторов настоящей работы.

Листинг 10. Алгоритм сложения на основе пула памяти.

void addOne(std::vector<int*> &arr) { for(int* it : arr) { *it += 1; } } void addNewHundred(std::vector<int*> &arr, int size) { for(int i = 0; i < 100; i++) { if(arr.size() > size) { break; } else { arr.push_back(new int); size++; } } } … int main() { … std::vector<int*> arr; int n = 1000; while(n--) { arr.push_back(new int); } … addOne(arr); … }

Выполнение программы заняло 7 мкс. и 113 Кб памяти.

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

Листинг 11. Алгоритм сложения с выделением памяти.

… int main() { std::chrono::microseconds elapsed_ms; std::vector<int*> arr; int n = 900; while(n--) { arr.push_back(new int); } … addNewHundred(arr, 1000); addOne(arr); … }

В результате, как и предполагалось, выполнение займет 19 мкс. и 1116 Кб RAM. На выделение необходимого объема памяти затрачивается дополнительный ресурс, поэтому, в целях экономии процессорного времени, рекомендуется производить выделение памяти для всех объектов программы на начальном этапе инициализации.

AlgorithmicOptimization

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

CacheOptimization

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

Листинг 12. Обработка элементов массива с использованием кэш памяти.

constexpr int CACHE_LINE_SIZE = 64; // Размер кэш-линии (предполагаем, что это 64 байта) struct DataItem { int value1 = 1; int value2 = 1; // Дополнительные поля }; … constexpr int ARRAY_SIZE = 1000000; static std::vector<DataItem> dataArray(ARRAY_SIZE); const int cc = CACHE_LINE_SIZE / sizeof(DataItem); … // Обработка данных по блокам для повышения локальности for (int blockStart = 0; blockStart < ARRAY_SIZE; blockStart += cc) { // Обрабатываем блок данных for (int i = blockStart; i < blockStart + cc; ++i) { // Доступ к данным dataArray[i].value1 += 1; dataArray[i].value2 *= 2; // Дополнительная обработка } } …

Структура данных DataItem содержит два поля для хранения целочисленных значений. Предполагается, что размер кэш линии содержит 64 байта для хранения данных (в 64-разрядных ОС), массив dataArray содержит элементов. В цикле происходит обработка массива, в качестве вычислительной нагрузки к первому элементу структуры добавляется единица, а второй удваивается. Выделение памяти происходит статически, поэтому при частом обращении к вектору объект dataArray кэшируется. Выполнение программы занимает 2840 мкс. и 748 Кб RAM. В противном случае линейный алгоритм занял 4050 мкс. и 715 Кб, что свидетельствует о более высокой эффективности первого предложенного шаблона.

Заключение

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

Список литературы

1. Вяткин С.И., Долговесов Б.С. Прямой рендеринг трехмерных объектов на основе функций возмущения с использованием графических процессоров // Программные системы и вычислительные методы. - 2022. - №1. - С. 42-50.
2. Авагян Г.Е., Смагин Д.Е., Мешков М.В. Актуальные проблемы оптимизации алгоритмов трассировки путей на графических процессорах с помощью технологии CUDA // Инновационная наука. - 2020. - №5. - С. 9-11.
3. Близно М.В. Исследование закономерностей развития энергонезависимой памяти // Проблемы искусственного интеллекта. - 2019. - №2 (13). - С. 39-48.
4. Гольчевский Ю.В., Ушаков Д.А. Ускорение криптографических вычислений путем низкоуровневой оптимизации базовых блоков // Вестник Сыктывкарского университета. Серия 1. Математика. Механика. Информатика. - 2023. - №1 (46). - С. 30-49.
5. Donald E. Knuth The Art of Computer Programming. - 2-e изд. - Addison-Wesley, 2014. - 803 с.