Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Курсовая работа

Оптимизация параллельного программного кода



Введение

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

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

В настоящее время имеются различные стандарты интерфейса обмена данными в параллельном программировании: MPI, OpenMP, OpenACC [2] и т.д. Стандартом программирования называют библиотеку функций, необходимых для использования вычислительной мощи параллельных систем. Для каждого стандарта существуют различные реализации, позволяющие использовать распараллеливание максимально эффективно в той или иной системе. Например Intel MPI, реализация стандарта MPI, работает гораздо лучше с системами, основанными на продуктах Intel.

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

Сокращение времени исполнения программного кода - задача, невыполнимая без его оптимизации.

Цель: Сократить время исполнения параллельного программного кода, используя средства оптимизации.

Задачи:

1. Изучить средства и методы оптимизации;

2. Использую до-программные методы оптимизации подготовить фундамент для выполнения последующих процедур;

3. Сократить время исполнения параллельного программного кода, используя программные методы;

3.1. Используя ключи оптимизации компилятора GCC, оптимизировать программный код

3.2. Получить удовлетворительные результаты;

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

В качестве платформы для исследований будет применятся Вычислительный кластер ДВФУ, с установленным на нём GCC компилятором. От сюда и вытекает выбор основного метода оптимизации в виде использования флагов и ключей соответствующего компилятора.



1. Средства оптимизации

компилятор программный код

Весь процесс оптимизации можно разделить на три основных этапа:

1) До-программная оптимизация;

2) Программная оптимизация;

1.1 До-программная оптимизация

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

– Подборка более подходящих алгоритмов.

Простая сортировка вставками быстрее сортировки пузырьком, а худшая из сложных сортировок, сортировка Шелла еще лучше. [1]

– Аппроксимация.

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

– Переписывание на другой язык.

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

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

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

2. Измеримость. Должен быть выбран правильный, достоверный метод измерения производительности приложения при прогоне рабочей задачи. Используемые метрики зависят от типа тестируемого приложения. Например, игра может использовать показатель частоты фреймов в секунду. Программа электронной коммерции - количество транзакций в секунду. Сетевой фильтр - количество пакетов в секунду. Произвольный код - время его исполнения.

3. Среда разработки. Очень важно выбрать среду разработки для максимальной эффективности работы программы. Так математические вычисления удобнее, проще и, в некотором, рациональнее использовать MATLAB и стандарт MDCE.

4. Верный метод измерения. Разные функции измерения работают по разному. Если нам необходимо измерить время исполнения отдельного кода элемента, то и использовать надо соответствующую функцию. Иной вариант - иная функция.

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

6. Соответственно необходимо тестировать результат. Соберите необходимые данные и сравните их с базовыми измерениями, тщательно обдумайте результаты и, при необходимости, вернитесь назад.

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

1.2 Программная оптимизация

Каждая среда разработки имеет свои встроенные средства оптимизации. Обычно они выражены в различных функциях компилятора, иногда в дополнительных средствах оптимизации. Пример средств оптимизации от Intel и его Intel MPI Compiler:

– Анализатор Intel VTune [8]

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

– Библиотека Intel Integrated Performance Primitives [9] [10]

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

– Библиотека Intel Math Kernel Library [11]

Широко используется для решения вычислительно сложных задач, где от платформ Intel требуется максимальная производительность

– Анализатор Intel Thread Checker [12]

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

Каждая среда имеет средства оптимизации, но у каждой они выражены по разному. Среда разработки GCC в качестве средств оптимизации имеет, так называемые, «Ключи».



2. GCC и ключи оптимизации

GNU Compiler Collection (обычно используется сокращение GCC) - набор компиляторов для различных языков программирования, разработанный в рамках проекта GNU. GCC является свободным программным обеспечением, распространяется фондом свободного программного обеспечения (FSF) на условиях GNU GPL и GNU LGPL и является ключевым компонентом GNU toolchain. Он используется как стандартный компилятор для свободных UNIX-подобных операционных систем.

Изначально названный GNU C Compiler поддерживал только язык Си. Позднее GCC был расширен для компиляции исходных кодов на таких языках программирования, как C++, Objective-C, Java, Фортран и Ada.

Начало GCC было положено Ричардом Столлманом, который реализовал первый вариант GCC в 1985 году на нестандартном и непереносимом диалекте языка Паскаль; позднее компилятор был переписан на языке Си Леонардом Тауэром и Ричардом Столлманом и выпущен в 1987 году как компилятор для проекта GNU, который сам по себе являлся свободным программным обеспечением. Разработка GCC курируется Free Software Foundation.

В настоящее время GCC поддерживается группой программистов со всего мира. GCC является лидером по количеству процессоров и операционных систем, которые он поддерживает.

Будучи официальным компилятором системы GNU, GCC также является главным компилятором для сборки ряда других операционных систем; среди них - различные варианты Linux и BSD, а также ReactOS, Mac OS X, OpenSolaris, NeXTSTEP, BeOS и Haiku.

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

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

2.1 Основные методы программной оптимизации

Методы автоматической оптимизации можно разделить на следующие классы:

– Оптимизация, удаляющая «лишний» код. К этому классу относятся методы оптимизации, удаляющие недоступный код, удаление повторяющихся подвыражений (common sub-expression elimination, CSE). Сюда же относятся такие методы, как вычисление выражений, содержащих константы, на этапе компиляции (constant folding) и, иногда, встраивание функций.

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

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

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

– Оптимизация вызова функций. Включает управление формированием стекового фрейма, передачу аргументов в регистрах, оптимизацию кода возврата из функции и встраивание функций (function inlining).

– Интеллектуальная оптимизация. Включает такие методы, как перестановка блоков (block reordering) и исключение концевой рекурсии.

Все указанные выше типы оптимизации реализованы в компиляторе GCC.

Подробную информацию о флагах, используемых при оптимизации GCC можно получить после ввода команды man gcc.

Для gcc версий 3.x и выше существует только 5 уровней оптимизации: - O0 (без оптимизации), - O1, - O2 и - O3 (O3 - самый высокий уровень), а так же - Os.

- O0

Отключает оптимизацию. Только переменные, объявленные register, сохраняются в регистрах.

- O(-O1)

Включает оптимизацию. Пытается уменьшить размер кода и ускорить работу программы. Соответственно увеличивается время компиляции. При указании - O активируются следующие флаги:

- fauto-inc-dec - fcprop-registers - fdce - fdefer-pop - fdelayed-branch - fdse - fguess-branch-probability - fif-conversion2 - fif-conver ?sion

- finline-small-functions - fipa-pure-const - fipa-reference - fmerge-constants - fsplit-wide-types - ftree-builtin-call-dce

- ftree-ccp - ftree-ch - ftree-copyrename - ftree-dce - ftree-dominator-opts - ftree-dse - ftree-fre - ftree-sra - ftree-ter

- funit-at-a-time

На тех машинах, которые способны поддерживать отладку даже без указателя на стек функции, также включается опция - fomit-frame-pointer.

На других машинах могут быть включены и другие флаги.

- O2

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

- O2 включает все флаги оптимизации наследованные от - O. Также включает следующие флаги оптимизации:

- fthread-jumps

- falign-functions - falign-jumps - falign-loops - falign-labels - fcaller-saves - fcrossjumping - fcse-follow-jumps - fcse-skip-blocks

- fdelete-null-pointer-checks - fexpensive-optimizations - fgcse - fgcse-lm - findirect-inlining - foptimize-sibling-calls - fpeephole2

- fregmove - freorder-blocks - freorder-functions - frerun-cse-after-loop - fsched-interblock - fsched-spec - fschedule-insns - fsched ?ule-insns2 - fstrict-aliasing - fstrict-overflow - ftree-switch-conversion - ftree-pre - ftree-vrp

- O3

Оптимизирует еще немного. Включает все оптимизации - O2 и также включает флаги

- finline-functions - funswitch-loops - fpredictive-commoning - fgcse-after-reload - ftree-vectorize

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

- Os

Включает оптимизацию по размеру. - Os флаг активирует все флаги оптимизации из - O2, в основном те, которые не увеличивают размер выходного файла. В дальнейшем выполняются оптимизации по уменьшению размера кода.

- Os выключает следущие флаги оптимизации:

- falign-functions - falign-jumps - falign-loops - falign-labels - freorder-blocks

- freorder-blocks-and-partition - fprefetch-loop-arrays - ftree-vect-loop-version



3. Применение методов оптимизации

Практическая часть будет выполнятся на вычислительном кластере ДВФУ. Его Архитектура приведена в таблице 1.

Таблица 1. Архитектура кластера ДВФУ

Модули	Sun Blade 6000 Chassis; х6
Модуль	Sun Blade X6250 Server Module; х10
Лезвие	Память - 8 Гб Процессоры - 2 x Intel(R) Xeon(R) CPU E5345 @ 2.33GHz
Лезвия соединены гигабитной сетью Ethernet также имеется соединение Infiniband

Для проведения оптимизации возьмем программу [Приложение А], сортирующую большой целочисленный массив методом пузырька. Размер массива: 800 000 целочисленных элементов от 0 до 1000 000.

3.1 До-программная оптимизация

Выбор метода пузырька выбран из-за его простого алгоритма и общей его известности. Результаты исследований [1] показали медленность данного метода в сравнении с другими, но в работе используется именно он, по изложенным выше причинам.

В рамках до-программной оптимизации произведены следующие действия:

– В качестве языка программирования был выбран С++. Причиной тому послужил предустановленный на кластере компилятор GCC, а поддержка данной сборки языка Fortran не была установлена;

– Используемая библиотека параллельного программирования: MPI. Выбрана в виду её наличии на вычислительном кластере и активном использовании в течении учебного семестра;

– Для измерения времени работы программы выбрана функция MPI_Wtime. Эта функция универсальна, поскольку она возвращает секунды, а не количество тактовых импульсов. Именно поэтому используется именно она;

На вычислительном кластере, в течение проведения тестов, никаких настроек не проводилось.

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

3.2 Программная оптимизация

На вычислительном кластере ДВФУ установлен компилятор GCC, который, как описывалось в теоретической части, имеет свои ключи оптимизации: - O0, O1, O2, O3, Os.

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

Проведение тестов будет проходить на узле n2 с использованием 8 процессоров.

Ход работы: Общая формула для расчета среднего времени выполнения программы

Формула расчета коэффициента эффективности оптимизации



Тест1. Уровень оптимизации: - O0. Оптимизация отсутствует. Результаты данного теста будут взяты за основополагающие и приведены в таблице 2. Ход теста представлен на рисунке 1.

Рисунок 1. Ход теста №1

Таблица 2 - Результаты теста №1

№	TIME (с.)	TIME ср. (с.)
1	140,904885	140,9426429
2	138,034446
3	139,0893
4	141,932382
5	138,806332
6	142,767528
7	140,296884
8	146,709019
9	141,597774
10	139,287879

TIME-1 (ср) = 140,9426429 (с.)



Тест2. Уровень оптимизации: - O (O1). Результаты в таблице 3. Ход теста представлен на рисунке 2.

Рисунок 2. Ход теста №2

Таблица 3. Результаты теста №2

№	TIME (с.)	TIME ср. (с.)
1	55,951421	59,2096633
2	58,734356
3	61,677451
4	58,201392
5	57,89876
6	61,486022
7	58,154872
8	59,753287
9	60,427423
10	59,811649

TIME-2 (ср)=59,2096633 (с.)

Тест3. Уровень оптимизации: - O2. Результаты в таблице 4. Ход теста представлен на рисунке 3.



Рисунок 3. Ход теста №3

Таблица 4. Результаты теста №3

№	TIME (с.)	TIME ср. (с.)
1	55,835931	56,9265952
2	56,640399
3	56,904378
4	57,591109
5	58,448865
6	55,999147
7	59,280328
8	58,290903
9	57,909722
10	52,36517

TIME-3 (ср)=56,9265952 (с.)

Тест4. Уровень оптимизации: - O3. Результаты в таблице 5. Ход теста представлен на рисунке 4.



Рисунок 4. Ход теста №4

Таблица 5. Результаты теста №4

№	TIME (с.)	TIME ср. (с.)
1	58,336757	58,5256081
2	58,437055
3	60,718092
4	59,298555
5	55,016083
6	57,809691
7	59,358523
8	58,416387
9	58,547829
10	59,317109

TIME-4 (ср)=58,5256081 (с.)

Тест5. Уровень оптимизации: - Os. Результаты в таблице 6. Ход теста представлен на рисунке 5.



Рисунок 5. Ход теста №5

Таблица 6. Результаты теста №5

№	TIME (с.)	TIME ср. (с.)
1	54,817634	56,2030987
2	57,290801
3	60,46147
4	57,445684
5	55,26759
6	56,496591
7	57,618434
8	54,9938
9	58,612457
10	57,126313
11	52,361683

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

TIME-5 (ср)=56,2030987 (с.)

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

Таблица 7. Итоговые результаты оптимизации

Уровень	TIME ср. (с.)	Q
-O0	140,9426429
-O1	59,2096633	2,380399331
-O2	56,9265952	2,475866375
-O3	58,5256081	2,408221759
-Os	56,2030987	2,507737939



Заключение

Поставленная цель достигнута. Получено ускорение выполнения программы в более чем 2 раза (Q=2,507737939).

Также по результатам исследования выявлен самый эффективный уровень оптимизации ключами компилятора GCC. При уровне оптимизации - Os, как и ожидалось, исходя из теории, получены самые хорошие результаты (Q=2,507737939). Также подтвержден факт неэффективности оптимизации ключом - O3, результаты его применения (Q=2,408221759) оказались хуже уровней - O2 и - Os. До-программные процедуры позволили нам получить максимальную точность исследований.



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

1. Репина И.Г. Курсовая работа на тему «Сравнительный анализ алгоритмов сортировки методом простых вставок и методом пузырька» / Кафедра Радиоэлектроники и Системотехники / Самарский государственный аэрокосмический университет [Электронный ресурс]/ Филиал в г. Тольятти http://baza-referat.ru/Сравнительный_анализ_алгоритмов_сортировки_методом_простых_вставок_и_методом_пузырька;

2. Портал overclockers.ru [Электронный ресурс]/ Статья / Создание OpenACC стандарта. http://www.overclockers.ru/itnews/44558/NVIDIA_Cray_PGI_i_CAPS_predstavili_standart_parallelnogo_programmirovaniya_OpenACC.html;

3. Gentoo Foundation, Inc. [Электронный ресурс] / Статья / Оптимизации GCC http://wiki.gentoo.org/wiki/GCC_optimization/ru;

4. Васильева М.В., Захаров П.Е. Параллельное программирование на основе библиотек [Электронный ресурс] / Учебное пособие / Области применения параллельного программирования http://edu.chpc.ru/parallel/mainse1.html#x5-40001.1;

5. Википедия, Свободная Энциклопедия [Электронный ресурс] / 5 октября 2014 год https://ru.wikipedia.org/wiki/Параллельные_вычисления;

6. Академик / Электронный ресурс / Статья http://dic.academic.ru/dic.nsf/ruwiki/61467;

7. Intel Corp. [Электронный ресурс] / Статья / Этапы подготовки к оптимизации параллельного программного кода https://software.intel.com/ru-ru/articles/the-three-stages-of-preparation-for-optimizing-parallel-software;

8. Intel Corp. [Электронный ресурс] / Статья / Анализатор Intel VTune https://software.intel.com/en-us/intel-vtune-amplifier-xe;

9. Intel Corp. [Электронный ресурс] / Статья / библиотека intel integrated performance primitives http://habrahabr.ru/company/intel/blog/186780/;

10. Intel Corp. [Электронный ресурс] / Статья / библиотека intel integrated performance primitives http://ru.wikipedia.org/wiki/Integrated_Performance_Primitives;

11. Intel Corp. [Электронный ресурс] / Статья / Библиотека Intel Math Kernel Library https://software.intel.com/ru-ru/articles/parallelism-in-the-intel-math-kernel-library;

12. Intel Corp. [Электронный ресурс] / Статья / Анализатор Intel Thread Checker https://software.intel.com/ru-ru/videos/intel-thread-checker;

13. Википедия, Свободная Энциклопедия [Электронный ресурс] / Статья/ алгоритм сортировки пузырьком https://ru.wikipedia.org/wiki/Сортировка_пузырьком;

14. Гурьянова Ольга. Сортировка пузырьком [Электронный ресурс] / Студентка группы 83-03 факультет ВМК/ 2010 год / Лабораторная работа http://www.hpcc.unn.ru/? dir=897;

15. Alex Otwagin [Электронный ресурс] / Статья/ Таймеры и синхронизация/ 2002-12-10/ http://skif.bas-net.by/bsuir/mpi-1-std/node143.html;

Размещено на Allbest.ru

...