Содержание к диссертации
Введение
Глава 1. Обзор методов исследования выполнения параллельных программ 12
1.1 Основные методы исследования параллельных программ 12
1.2 Основные подходы к анализу характеристик параллельных программ 16
1.3 Инструментальные средства, применяемые при анализе работы параллельной программы 19
1.4 Понятие масштабируемости параллельных программ и его свойства 27
1.5 Подходы и методы, применяемые для исследования масштабируемости 30
1.6 Выводы 37
Глава 2. Обобщение понятия масштабируемости параллельных программ 38
2.1 Недостатки классических определений масштабируемости 38
2.2 Введение определения «обобщенной» масштабируемости 43
2.3 Свойства понятия масштабируемости в предложенной интерпретации
2.3.1 Связь с классическими определениями 50
2.3.2 Преимущества использования нескольких динамических характеристик 53
2.3.3 Преимущества использования нескольких параметров запуска
2.4 Основные принципы исследования масштабируемости 56
2.5 Особенности использования введенного понятия масштабируемости 58
2.6 Апробация предлагаемого подхода к анализу масштабируемости параллельной программы 59
2.7 Выводы 69
Глава 3. Применение данных системного мониторинга для анализа масштабируемости параллельных программ 71
3.1 Методика проведения исследований данных системного мониторинга 71
3.1.1 Применение системного мониторинга для исследования масштабируемости программ 71
3.1.2 Инструментарий, использованный при исследованиях 73
3.1.3 Основные факторы, влияющие на масштабируемость программ 74
3.1.4 Условия проведения экспериментов 75
3.2 Результаты исследования факторов, влияющих на масштабируемость
приложений 79
3.2.1 Исследование характеристик коммуникационной сети 79
3.2.2 Исследование компонентов вычислительного узла компьютера 89
3.2.3 Факторы, связанные с характеристиками примененного алгоритма или исследуемой программы 97
3.3 Выводы 101
Глава 4. Разработка принципов сравнения масштабируемости приложений 103
4.1 Подход к исследованию масштабируемости приложений 103
4.2 Метрика масштабируемости параллельного приложения 104
4.2.1 Целесообразность ввода понятия «метрика масштабируемости» 104
4.2.2 Вывод метрики и оценки масштабируемости
4.3 Алгоритм проведения исследований масштабируемости приложений 114
4.4 Результаты проведенных экспериментов
4.4.1 Условия проведения исследования 117
4.4.2 Результат анализа масштабируемости программы, реализующей блочное перемножение матриц 118
4.4.3 Результат анализа масштабируемости программы, реализующей скалярное произведение векторов 120
4.4.4 Результат анализа масштабируемости программы, реализующей разложение Холецкого 122
4.4.5 Результат анализа масштабируемости Linpack Benchmark 124
4.4.6 Результат анализа масштабируемости программы, реализующей метод Гаусса решения СЛАУ, прямой ход 126
4.4.7 Результаты сравнения масштабируемости 128
4.5 Выводы 131
Заключение 132
Список литературы 134
- Подходы и методы, применяемые для исследования масштабируемости
- Свойства понятия масштабируемости в предложенной интерпретации
- Инструментарий, использованный при исследованиях
- Целесообразность ввода понятия «метрика масштабируемости»
Введение к работе
Актуальность темы
Современные научные и индустриальные приложения и пакеты прикладных программ используют очень большие объемы данных, для обработки которых зачастую необходимы колоссальные объемы вычислений. Решать эти задачи часто приходится в близком к реальному времени темпе, что дополнительно повышает требования к производительности вычислительных систем. Это требует применения вычислительных устройств с очень высокой производительностью. Сейчас для этих целей, как правило, применяют многопроцессорные вычислительные системы, выполняющие большой набор различных параллельных программ. Вместе с этим, эффективность выполнения этих программ на существующих вычислительных системах, как правило, крайне низка. Чаще всего это связано со сложностью создания программ, оптимально сочетающих алгоритм решаемой задачи и его реализацию в программном коде. Проблема заключается в необходимости эффективного использования параллельной программой десятков миллионов компонентов больших вычислительных систем, которые или имеются уже сейчас, или неизбежно появятся в ближайшем будущем.
Суперкомпьютерный кодизайн – это процесс разработки параллельных приложений, в котором учитываются и согласуются особенности алгоритмов, технологий программирования, реализации в коде и аппаратном обеспечении для создания высокоэффективных программ для вычислительных систем. Современные концепции суперкомпьютерного кодизайна требуют, чтобы особенности функционирования каждой составляющей вычислительной системы принимались во внимание при разработке параллельной программы. Поэтому при создании параллельных программ требуется анализ и учет большого объема информации о свойствах каждой составляющей вычислительного процесса. Требования к параллелизму работы должны быть учтены на всех этапах решения задачи: в алгоритмах, в программах, в архитектуре компьютеров и – ключевой вопрос — в согласованности между собой найденных особенностей на каждом из этапов во время выполнения программы.
Вопрос эффективного использования вычислительных систем, способных справиться с большими и сложными расчетами, напрямую связан с понятием «масштабируемость». Масштабируемость – свойство параллельной программы, характеризующее зависимость е динамических характеристик от параметров запуска этой программы. Анализ масштабируемости программы позволяет делать выводы о качестве ее работы. Нельзя оптимизировать параллельную программу без учета параметров запуска программы и других факторов, влияющих на е динамические характеристики. Особенно актуаль-
но это при разработке сложных программных комплексов, в которых изменения кода в процессе оптимизации в одной части программы вполне могут снижать масштабируемость других ее частей и всего программного комплекса в целом.
При разработке больших программных комплексов часто возникает вопрос правильного выбора алгоритма и его реализации. Для выбора эффективного варианта реализации разрабатываемой программы необходимо иметь простую и надежную методику сравнения свойств масштабируемости различных реализаций программы. Это может дать возможность целенаправленно выбирать наиболее удачные реализации использованного алгоритма или даже использовать алгоритмы другого класса и, при необходимости, скорректировать конфигурацию аппаратной платформы. Следовательно, для решения этих задач необходимо иметь конструктивный подход для учета всех факторов, влияющих на масштабируемость программы.
Сегодня параллельные вычисления встречаются повсеместно: многоядерные процессоры используются даже в наручных часах, а восьмиядерный процессор в мобильном телефоне становится стандартным. Степень параллелизма в вычислительных системах высокого уровня достигает нескольких миллионов, и создание эффективных программ требует тщательного анализа их свойств. Все это в совокупности говорит о том, что вопрос разработки методов исследования масштабируемости параллельных программ на сегодня является крайне актуальным.
Степень разработки темы
Вопросу исследования масштабируемости как небольших программ, так и больших программных комплексов в настоящее время посвящено немало исследований, результаты которых приведены во множестве научных публикаций. В этих работах даны различные определения этого свойства, причем большое разнообразие имеющихся в литературе определений масштабируемости говорит о необходимости дальнейшего поиска более простого и универсального определения, приемлемого для широкого круга пользователей и разработчиков параллельных программ.
Каждый из использованных авторами этих публикаций подходов к анализу масштабируемости специфичен для своей области применения, хотя они и содержат общие элементы. Одни методы просты в применении, но дают существенные погрешности результатов. Другие методы дают приемлемые результаты, но очень сложны и, следовательно, достаточно дороги. И часто они все равно не позволяют сделать однозначных выводов о причинах найденных особенностей масштабируемости. Технологии суперкомпьютерного кодизайна предполагают проведение наиболее полного анализа особенностей работы программ на всех этапах разработки для согласованной работы программ и аппаратного обеспечения. Но такой анализ обычно не направ-
лен на исследование масштабируемости программ. Поэтому, несмотря на значительное многообразие существующих методов исследования масштабируемости, этот вопрос все еще требует дальнейшего и всестороннего развития. Не менее важно, чтобы методы анализа были универсальны и применимы для анализа большинства параллельных программ. Желательно, чтобы исследование по подобной методике могло быть проведено по принципу «черного ящика», а его проведение могло бы быть на каких-то стадиях автоматизировано.
Многие российские и зарубежные исследователи внесли серьезный вклад в исследование понятия масштабируемости, среди них: В.В.Воеводин, В.А.Крюков, И.Б.Задыхайло, В.П.Ильин, В.Э.Малышкин, М.В.Якобовский, J.Dongarra, T.Sterling, B.Gropp, T.Hoefler и другие.
Цель работы и вытекающие из нее задачи
Целью данной работы является развитие методов исследования свойства масштабируемости параллельных программ, разработка подходов для определения причин и степени влияния на масштабируемость программных и аппаратных факторов с использованием технологий суперкомпьютерного кодизайна, а также разработка методики сравнения масштабируемости различных параллельных программ для их последующей оптимизации.
Для достижения указанной цели в процессе работы решались следующие задачи:
разработка подхода к анализу масштабируемости параллельных приложений на основе технологий суперкомпьютерного кодизайна для анализа свойств и характеристик выполнения приложений;
разработка подхода к анализу причин, ограничивающих масштабируемость параллельных приложений, на основе данных системного мониторинга как источника данных о состоянии аппаратного обеспечения во время работы программы;
разработка метода сравнения масштабируемости параллельных приложений для получения критериев оценки вносимых изменений в приложение или аппаратную платформу, а также для сравнения масштабируемости различных программ;
проведение апробации предложенных в работе подходов и методов в рамках анализа тестовых параллельных программ, параллельных реализаций типовых алгоритмов и пользовательских программ из потока задач суперкомпьютерного комплекса Московского университета.
Научная новизна
Научная новизна предлагаемой работы заключается в разработке и обосновании определения масштабируемости параллельной программы, обобщающего существующие определения этого свойства. Разработаны методики сбора и анализа данных о масштабируемости параллельных программ. Вве-
дены понятия параметров запуска параллельной программы, конфигурации запуска, динамических характеристик, предложена классификация данных понятий. С использованием технологий суперкомпьютерного кодизайна разработана методика анализа данных системного мониторинга, позволяющая не только выявлять проблемы масштабируемости параллельных программы, но и находить причины этих проблем путем сопоставления информации о различных характеристиках программ и сбора данных с различных источников программно-аппаратной среды супекомпьютера. В работе предложены подход к сравнению масштабируемости различных параллельных программ и методика расчета метрики масштабируемости, основанная на собранных данных о масштабируемости программы.
Новые научные результаты и положения, выдвигаемые для публичной защиты
Основными результатами работы являются:
-
Предложен и обоснован подход к анализу масштабируемости параллельных приложений на основе технологий суперкомпьютерного кодизайна.
-
Предложен подход к выделению истинных причин, ограничивающих масштабируемость параллельных приложений, на основе согласованного анализа данных системного мониторинга.
-
Предложен метод сравнения масштабируемости параллельных приложений, основанный на анализе изменения эффективности их реализаций. Метод позволяет не только оценивать эффект от внесенных в программу изменений, но и сравнивать масштабируемость любых параллельных программ между собой.
-
Предложенные в работе подходы и методы прошли успешную апробацию в рамках анализа тестовых параллельных программ, параллельных реализаций типовых алгоритмов и пользовательских программ из потока задач суперкомпьютерного комплекса Московского университета.
Теоретическая и практическая значимость работы
Разработанный подход к исследованию масштабируемости позволяет определять свойства масштабируемости параллельных программ по многим параметрам запуска, а также сочетать в единой структуре данные о влиянии различных параметров запуска программ на их выполнение. Разработанный подход представляет теоретическую ценность как расширение понятия масштабируемости параллельных программ, позволяющее конструктивно подойти к исследованию их свойств. Предлагаемый подход позволяет делать выводы о причинах найденных проблем масштабируемости параллельных программ, проводить сравнение программ по данному свойству. С использованием предложенного подхода к анализу масштабируемости в работе предложен метод сравнения масштабируемости различных программ, что пред-
ставляет практическую ценность при разработке параллельных масштабируемых приложений.
Методология и методы исследования
Для выполнения поставленной цели в данной работе применялся подход, основанный на:
методах анализа структуры алгоритма решаемых задач;
методах синтаксического анализа исходного кода программ;
анализе динамических характеристик программ;
анализе данных реальных трасс выполнения параллельных программ;
- сопоставлении найденных особенностей программы на разных этапах
решения задачи с применением технологий кодизайна.
Степень достоверности и апробация работы
Предложенные в работе подходы и методики прошли апробацию и обсуждение:
на научных семинарах НИВЦ МГУ и кафедры СКИ факультета ВМК МГУ;
на спецсеминаре «Вопросы распределенной обработки информации» факультета ВМК МГУ;
на Научной конференции «Ломоносовские чтения» (г. Москва, 2012, 2013, 2014 гг);
на Всероссийской научной конференции «Научный сервис в сети Интернет: поиск новых решений» (г. Новороссийск, 2012г.);
на Всероссийской научной конференции «Научный сервис в сети Интернет: все грани параллелизма» (г. Новороссийск, 2013г.);
на Всероссийской научной конференции «Научный сервис в сети Интернет: многообразие суперкомпьютерных миров» (г. Новороссийск, 2014г.);
на XIV Международной конференции «Высокопроизводительные параллельные вычисления на кластерных системах», ПНИПУ, (г. Пермь, 2014г.);
на IX Международной конференции «Параллельные вычислительные технологии (ПаВТ'2015)», (г. Екатеринбург 2015)
на научном семинаре «Методы суперкомпьютерного моделирования» (г. Таруса, 2015г.)
Личный вклад автора. Все исследования, результаты которых изложены в диссертационной работе, проведены лично автором в процессе научной деятельности. Из совместных публикаций в результаты диссертационной работы включен лишь тот материал, который непосредственно принадлежит автору.
Структура и объем работы. Диссертация состоит из введения, 4 глав, заключения и списка литературы. Общий объем диссертации – 141 страница. Список литературы включает 54 наименования.
Подходы и методы, применяемые для исследования масштабируемости
В опубликованных научных работах приведено большое разнообразие методов, применяемых для анализа выполнения параллельных программ. Все методы исследования можно условно разделить на три основные группы: аналитические, статический анализ исходного текста и эмпирические. Применяются и смешанные методы, сочетающие свойства разных групп.
Аналитические методы исследования работы программы применяются, как правило, когда необходимо исследовать параллельную программу для определения ее основных характеристик выполнения, не используя большого количества вычислительных ресурсов. Аналитические методы подразумевают получение данных о качестве выполнения программы с помощью моделирования хода ее выполнения по какому-либо заранее определенному принципу на менее мощной (инструментальной) вычислительной системе. Создание модели может быть проведено, как на основе данных о реальном прогоне исследуемого приложения, так и на основании статического анализа исходного кода программы, графа алгоритма или другой информации о работе программы [89]. При этом основными источниками данных являются сведения о декомпозиции задачи, о ресурсе параллелизма алгоритма и о распределении вычислений между процессами. Также в аналитических методах важно учитывать основные ограничивающие законы – Амдала и Густавсона-Барсиса. По результатам этого моделирования строится прогноз работы данной программы на штатной вычислительной системе. Точность полученных результатов при аналитических методах исследования обычно ниже, чем у методов, использующих данные реального выполнения программ.
При использовании аналитических методов строятся теоретические модели, дающие возможность вычислять (предсказывать) время выполнения программы или представлять ее динамические характеристики как функцию, зависящую от параметров запуска программы. При этом необходимо найти такую функцию, чтобы динамические характеристики вычислялись с наименьшей погрешностью. При анализе программы значение получаемого ускорения при значительно большем числе процессоров обычно вычисляется путем экстраполяции.
В качестве аналитических методов чаще всего используются: - алгебраический анализ [84] – математическое моделирование вычислительных и коммуникационных операций в программе; - абстрактная интерпретация [82] – замена алгебраическими выражениями только вычислительных блоков кода, симулируя при этом все коммуникационные операции; - синтаксический разбор [85] исходного текста программы, т.е. анализ свойств построенного графа алгоритма на основе текста программы; - симулирование выполнения [92] – выполнение на вычислительной системе меньшего размера вычислений исследуемой программы, моделируя при этом накладные расходы на полноразмерной системе.
Нужно отметить, что аналитические методы применимы в основном на этапе разработки программы. Прежде всего, потому что на этапе разработки алгоритма они позволяют получать предварительные оценки качества его выполнения, выявлять основные проблемы, связанные с ограниченностью параллелизма в алгоритме программы, и принимать решение о необходимости оптимизации программы еще до ее реализации. Однако, как правило, такие методы оценки не обладают высокой точностью, так как они не могут в достаточной мере учитывать особенности возможной реализации программы на конкретной аппаратной платформе.
При статическом анализе исходного текста проводится анализ текста программы без реального ее выполнения [90]. Такой способ анализа работы параллельной программы основан на анализе характеристик графа алгоритма, построенного по тексту программы. Эти данные используются для того, чтобы оценить потенциальный уровень параллелизма программы, накладные расходы и другие показатели качества выполнения, основанные на модели, построенной по тексту программы. Для составления модели используются знания о потенциальных накладных расходах, связанных с определенными синтаксическими конструкциями, а также анализируется декомпозиция данных, чтобы оценить возможное ускорение параллельной программы.
Анализ программы, основанный на синтаксическом разборе, как правило, имеет преимущество в том, что по тексту программы анализ может быть произведен один раз, и после этого характеристики выполнения могут быть предсказаны на основе построенной модели работы программы. Однако такой подход сильно ограничен возможностями корректного описания особенностей языка, на котором написана программа, и конструкций, использованных для создания программы, а также связанными с этим накладными расходами.
При эмпирических методах исследования [80] основными интересующими показателями являются порядок выполнения операций и время выполнения программы или каких-то отдельно взятых ее частей. Эмпирические методы подразумевают, что для проведения исследования нужно выполнить большое число реальных запусков исследуемой программы с замерами каких-либо характеристик ее работы на данной системе. Поэтому одним из главных минусов этих методов является необходимость длительного и достаточно дорогого использования мощной вычислительной системы. Вместе с тем, эмпирические методы имеют и много плюсов. По результатам таких исследований можно вести отладку и сбор данных о ходе выполнения всей программы. Для них не нужно составлять и реализовывать сложную модель параллельного выполнения, построение которой может занять порой больше времени, чем разработка самой программы. Полученные результаты будут представлять собой реальные данные о работе вычислительной системы при выполнении исследуемой программы. И эти данные могут быть использованы для анализа качества выполнения программы. То есть, нет необходимости теоретически детально изучать программу и выделять по отдельности влияние на динамические характеристики программы алгоритма и архитектуры системы. Что еще очень важно, такие методы в некоторых случаях могут быть автоматизированы. В силу того, что данные для анализа собираются на основе реального выполнения программы, точность эмпирических методов является более высокой, чем аналитических. Для уменьшения влияния на производительность различных случайных изменений при исследовании проводят по несколько одинаковых запусков программы.
При комбинировании эмпирического и аналитического исследования получают так называемые смешанные методы исследования. В них используется информация как о структуре программы и ее алгоритме, так и данные о реальном выполнении программы на вычислительной системе. Комбинируя эту информацию можно давать достаточно точные предсказания о качестве выполнения программы. Накладные расходы при этом могут экстраполироваться, исходя из реальных данных о выполнении, по какому-то закону, основанному на особенностях структуры алгоритма. Но различия методов сводятся не только к способам получения данных. В условиях сильно ограниченного доступа к дорогостоящим вычислительным ресурсам более выигрышным будет метод, основанный на построении аналитической модели и выполнении исследований на доступных компьютерах меньшей стоимости и производительности. Но во многих случаях продуманный эмпирический метод будет наиболее разумным, если доступна вычислительная система, обладающая необходимой производительностью [79].
Свойства понятия масштабируемости в предложенной интерпретации
Важным моментом при исследовании параллельной программы является и выбор рассматриваемого показателя работы программы. Во многих определениях масштабируемости важной характеристикой работы параллельной программы называют изменение эффективности ее работы на вычислительной системе. Зависимость эффективности работы программы от нескольких параметров позволяет найти те области значений параметров запуска, при которых работа программы остается на приемлемом уровне эффективности, а также те области, на которых она является недостаточной. Области приемлемого уровня значений легко получить, отсекая все значения, при которых эффективность ниже этого уровня.
Но для определения основных причин особенностей масштабируемости параллельных программ можно использовать не только такие интегральные характеристики как производительность, ускорение или эффективность. Для определения причин снижения производительности можно рассматривать изменение характеристик более низкого уровня. Например, можно рассматривать изменение активности использования программой коммуникационной сети или обращения программы к жесткому диску при изменении параметров запуска.
Динамическими характеристиками параллельной программы будем называть такие характеристики ее работы, которые характеризуют выполнение программы. К динамическим характеристикам можно отнести, например, такие характеристики как время выполнения, ускорение, производительность, эффективность. Это могут быть средние характеристики, рассчитанные за какой-то промежуток времени, или моментальные характеристики, актуальные в какой-то определенный момент работы аппаратуры при выполнении данной параллельной программы. Динамические характеристики можно разделить на группы несколькими способами. К примеру, можно поделить их по способу получения значений на две группы.
К первой группе можно отнести измеряемые характеристики. Примерами таких характеристик могут быть время выполнения, количество кэш-промахов, количество переданных за время работы байт по сети или по шине данных, количество обращений в память за время работы и т.п.
Ко второй группе можно отнести вычисляемые характеристики, значения которых можно получить, из измеряемых характеристик. Такие характеристики используются для лучшего понимания качества работы программы и для лучшего представления результатов. Они могут быть получены также из нескольких измеряемых характеристик. Примерами могут быть ускорение, производительность, скорость передачи данных, кэш-промахов в секунду, моментальная и средняя эффективность и т.п.
Для понимания свойств параллельной программы и причин найденных особенностей масштабируемости важно рассматривать все доступные изменяемые параметры запуска и все доступные динамические характеристики. Нужно рассматривать масштабируемость как более общее свойство параллельной программы, включающее в себя как зависимость значений динамических характеристик от различных параметров запуска, так и рассмотрение связей между изменениями значений различных динамических характеристик.
Поэтому масштабируемостью целесообразно называть свойство параллельной программы, характеризующее зависимость изменения всей совокупности динамических характеристик работы этой программы от множества параметров ее запуска.
Использование при анализе свойств параллельной программы термина «масштабируемость» в такой формулировке позволяет охарактеризовать выполнение параллельной программы и получить представление о том, как меняется использование вычислительных ресурсов при изменении различных параметров запуска программы, и делать выводы о факторах, влияющих на эффективность работы программы.
Рассмотрение изменения большого числа динамических характеристик при изменении нескольких параметров запуска требует наличия значительного объема сведений о выполнении программы и, следовательно, проведения большого числа экспериментов. Это вызвано необходимостью получения данных о работе исследуемой программы на каждой конфигурации в рассматриваемой области значений параметров запуска. Преимуществом предложенного подхода является тот факт, что, характеризуя те же самые данные о выполнении параллельной программы, для иллюстрации свойств может быть выбрана наиболее подходящая из динамических характеристик.
Сопоставляя предлагаемую формулировку масштабируемости с определениями, имеющимися в научных публикациях, становится понятно, что предложенный подход устраняет разногласия других определений в использовании различных показателей качества выполнения программы. Для построения зависимости качества выполнения программы от некоторых параметров запуска может использоваться любая из предложенных в классических определениях масштабируемости динамических характеристик: время выполнения, ускорение, производительность, эффективность и т.д. А в качестве аргумента может быть использован любой из параметров запуска параллельной программы, указанных в формулировках других научных публикаций. Фактически масштабируемость является многомерной зависимостью, отражающей изменение динамических характеристик при рассмотрении всего многообразия факторов, влияющих на выполнение этой параллельной программы. Все другие формулировки термина «масштабируемость» являются только частными случаями предлагаемого определения. На рисунках 2,3,4 приведено трехмерное представление масштабиуремости параллельной программы, выполняющей перемножение плотных матриц. Из графиков видно, что понятия сильной масштабируемости, масштабируемости вширь и слабой масштабируемости являются только частными случаями сечения полученной многомерной поверхности при изменении одного из параметров запуска и при фиксированных других параметрах. Сечение поверхности обобщенной масштабируемости перемножения матриц плоскостью при фиксированном размере задачи образует сильную масштабируемость (Рисунок 3). Сечение поверхности обобщенной масштабируемости перемножения матриц при фиксированном числе процессоров образует масштабируемость вширь (Рисунок 4).
Инструментарий, использованный при исследованиях
Сдерживающими факторами при использовании оперативной памяти могут быть е объм, пропускная способность каналов доступа, их количество и характеристики каналов доступа к памяти. Наиболее сильно эти свойства памяти будут ограничивать масштабируемость приложений для SMP-систем, где оперативная память может стать узким местом в масштабируемости всей системы. Для распределнной системы задержки доступа и число каналов доступа не будут оказывать такого сильного влияния, но могут существенно снижать слабую масштабируемость программы, ограничивая возможный объм данных для использования в программе.
В системе JobDigest аппаратные ограничения оперативной памяти отражаются на графиках чтения и записи в оперативную память.
Для тестирования данного фактора была выбрана одна из программ реального потока задач, использующая для вычислений большое число чтений из различных частей большого массива. То есть, чтений из памяти должно быть много при низком числе промахов в кэш-память. На графике количества операций с плавающей точкой (Рисунок 32) видна не очень большая производительность. Только на одном участке работы приложения скорость превышает 50 миллионов операций в секунду.
Число промахов в кэш-память первого уровня не очень большое почти на всм времени работы приложения (Рисунок 33). Это подтверждает предположение, что большинство обращений шло напрямую в оперативную память.
График количества чтений из памяти (Рисунок 34) показывает, что число чтений на протяжении всей работы программы не превышает 2200 миллионов. Важно отметить, что на графике число чтений на протяжении всей работы находится на стабильном уровне. Это может указывать на то, что число чтений может быть ограничено аппаратными характеристиками оперативной памяти.
В рассмотренном приложении мы видим, что амплитуда изменения максимального значения числа чтений из памяти меняется в течение времени. То есть при изменении амплитуды меняется и влияние использования оперативной памяти в процессе работы программы.
Таким образом, на графиках JobDigest можно увидеть ограничения и оценить степень влияния характеристиками оперативной памяти в процессе работы параллельной программы.
Существенное влияние характеристики кэш-памяти будут оказывать при использовании вычислений, в которых объм данных не очень большой. В этом случае данные могут уложиться в кэш-память, и тогда доступ к ним будет занимать значительно меньше времени. При этом средняя производительность работы приложения должна стать значительно выше.
Был произведен запуск одного и того же приложения на примере перемножения матриц, но с матрицами разного размера. В первом случае запуск осуществлялся с размером матрицы 10240, а во втором – 1024.
При первом запуске на графике количества операций с плавающей точкой в секунду (Рисунок 35) видно, что максимальное число операций в секунду составляет 1,5 Гфлопс, но среднее число операций в секунду не превышает 250 Мфлопс.
При запуске с малым размером задачи (Рисунок 36) максимальное число операций в секунду находится на уровне 2 Гфлопс, но среднее число операций в секунду значительно выше запуска с большим размером задачи. На малом размере задачи среднее число операций с плавающей точкой превышает 760 Мфлопс, а минимальное – 550 Мфлопс, что существенно отличается от запуска с большой матрицей, где минимальное число операций не превышает 52 Мфлопс.
Запуск задачи с большим размером матрицы (Рисунок 37) показывает не очень большое число кэш-промахов первого уровня. Это связано с тем, что общая производительность меньше и операций в секунду выполняется меньше. Количество кэш-промахов L1 в секунду (длина 10240), перемножение матриц При запуске программы с малым размером матрицы (Рисунок 38) число кэш-промахов первого уровня значительно больше, что соответствует большей производительности, которую показывает приложение при запуске с малым размером матрицы.
Число кэш-промахов второго уровня при запуске программы с большим размером матрицы (Рисунок 39) показывает стабильно высокий уровень числа кэш-промахов. Это подтверждает предположение о том, что данные полностью не укладываются в кэш-память и требуют подкачки.
При запуске с малым размером матрицы (Рисунок 40) тест демонстрирует значительно меньший уровень промахов в кэш-память второго уровня. Это подтверждает предположение, что данные значительно лучше уложились в
Следовательно, на графиках JobDigest можно увидеть ограничения, накладываемые на масштабируемость программы характеристиками кэшпамяти разного уровня. Факторы, связанные с характеристиками примененного алгоритма или исследуемой программы 1) Дисбаланс вычислительной нагрузки Дисбаланс является очень сильным фактором, сдерживающим масштабируемость программы, так как при этом полезно работает только часть процессов, а другая часть процессов периодически простаивает. Причм многие алгоритмы разработаны так, что с ростом числа процессов будет соответственно расти и число периодически простаивающих процессов.
Кроме того, при использовании глобальных синхронизаций время на выполнение каждой операции, использующей синхронизацию, будет возрастать с ростом числа взаимодействующих процессов. Чем больше будет взаимодействовать процессов, тем больше вырастет и время, затрачиваемое на один и тот же набор операций. Переход от глобальных синхронизаций к локальным помогает уменьшить влияние этого фактора.
Для того, чтобы определить степень влияния дисбаланса нагрузки, можно рассматривать различные динамические характеристики параллельных программ - как интегральные, так и уровня данных системного мониторинга. При дисбалансе нагрузки важно рассмотреть поведение среднего значения характеристик. Как правило, дисбаланс проявляется в том, что среднее значение отличается от максимального значения и имеет значение ближе к минимальному показателю любой характеристики. Это свидетельствует о том, что часть узлов бездействует и поэтому не показывает высоких показателей рассматриваемой характеристики. Например, это может проявляться в такой характеристике как Loadavg, которая указывает на число нитей, одновременно готовых к исполнению.
Был проанализирован запуск программы, при котором вычисления распределялись не равномерно между всеми процессами, а только между частью этих процессов. Рассмотрим работу программы, реализующей метод Гаусса со скошенным параллелизмом.
На рисунке 41 можно увидеть изменение показателя Loadavg во время работы программы. В начале работы, когда работа достается всем процессам, загружены все нити, но видно, что к концу программы показатель падает. Это свидетельствует о том, что в процессе работы часть нитей начинает бездействовать, приводя к дисбалансу нагрузки.
Целесообразность ввода понятия «метрика масштабируемости»
На графике масштабируемости блочного перемножения матриц (Рисунок 47) присутствуют особенности его масштабируемости, выявленные в выводах из оценки масштабируемости. Область с большим размером задачи и малым числом процессов соответствует конфигурациям запуска, на которых задача не помещалась полностью в память узла, и поэтому эффективность выполнения на графике дополнена нулями.
Результат анализа масштабируемости программы, реализующей скалярное произведение векторов Область значений изменяемых параметров запуска: - число процессоров [4: 1024] с шагом 8; - размер вектора [134217728: 2013265920] с шагом 134217728. В результате проведенных экспериментов был получен следующий диапазон эффективности реализации алгоритма: - минимальная эффективность 9,54 %; - максимальная эффективность 24,52%.
По результату анализа построим оценки метрики масштабируемости выбранной реализации скалярного произведения векторов: - по числу процессов: +0.00414. При увеличении числа процессов эффективность увеличивается на рассмотренной области изменений параметров запуска, однако, в целом увеличение не интенсивное. Увеличение эффективности на рассмотренной области работы параллельной программы объясняется тем, что при увеличении числа процессоров декомпозиция данных в какой-то момент приводит к тому, что данные лучше укладываются в кэш память. Это подтверждает проявление этого явления и при увеличении вычислительной сложности задачи, но со смещением по числу процессов. - по размеру задачи: -0.01385. При увеличении размера задачи эффективность в целом уменьшается на рассматриваемой области. Это объясняется тем, что при малом размере задачи, данные хорошо укладываются в кэш-память, что и приводит к высокой эффективности работы приложения при малом размере задачи. При увеличении размера задачи эффективность уменьшается при выходе за границы кэш-памяти. - по двум направлениям: -0.000169. При рассмотрении увеличения, как вычислительной сложности, так и числа процессов на всей рассмотренной области значений эффективность уменьшается, однако интенсивность ее уменьшения небольшая. Однако разница между максимальной и минимальной эффективностью на рассмотренной области значений параметров составляет почти 15%. Это говорит о том, что на поверхности присутствуют области с очень интенсивным изменением эффективности, но очень малые по площади. На остальной поверхности изменения эффективности незначительны и находятся приблизительно на одном и том же уровне. На графике максимальной эффективности работы приложения (Рисунок 48) присутствуют особенности масштабируемости, выявленные в выводах из оценки масштабируемости. Область с большим размером задачи и малым числом процессов соответствует конфигурациям запуска, на которых задача не помещалась полностью в память узла, поэтому на графике эффективность выполнения дополнена нулями.
Область значений изменяемых параметров запуска: - число процессоров [4; 256] с шагом 4; - размер матрицы [1024; 5120]. В результате анализа проведенных экспериментов был получен следующий диапазон эффективности реализации алгоритма: - минимальная эффективность реализации 0,11%; - максимальная эффективность реализации 2,65%. Построим оценки метрики масштабируемости выбранной реализации разложения Холецкого: - по числу процессов: -0,000593. При увеличении числа процессов эффективность на рассмотренной области изменений параметров запуска уменьшается, однако, в целом уменьшение не очень быстрое. Малая интенсивность изменения объясняется крайне низкой общей эффективностью работы приложения с максимумом в 2,65%, и значение эффективности на рассмотренной области значений быстро доходит до десятых долей процента (или уменьшается почти в 25 раз). Это свидетельствует о том, что на большей части области значений снижение эффективности интенсивно, хотя и численно само по себе мало. Это объясняется также тем, что с ростом вычислительной сложности падение эффективности становится не таким быстрым. Уменьшение эффективности на рассмотренной области работы параллельной программы объясняется быстрым ростом накладных расходов на организацию параллельного выполнения. С ростом вычислительной сложности задачи эффективность снижается также быстро, но при больших значениях числа процессов. Это подтверждает предположение о том, что накладные расходы начинают сильно превалировать над вычислениями. - по размеру задачи: +0,06017. При увеличении размера задачи эффективность возрастает и возрастает тем быстрее, чем большее число процессов используется для выполнения. Это подтверждает предположение о том, что размер задачи сильно влияет на эффективность выполнения приложения. Оценка показывает, что с ростом размера задачи эффективность на рассмотренной области значений параметров запуска сильно увеличивается. Также, учитывая разницу максимальной и минимальной эффективности в 2,5% (или почти в 25 раз), можно сделать вывод, что рост эффективности при увеличении размера задачи наблюдается на большей части рассмотренной области значений. - по двум направлениям: +0,000403. При рассмотрении увеличения, как вычислительной сложности задачи, так и числа процессов на всей рассмотренной области эффективность увеличивается. Однако скорость ее увеличения небольшая. В совокупности с тем фактом, что разница между максимальной и минимальной эффективностью на рассмотренной области параметров небольшая, эффективность с увеличением масштабов возрастает, но медленно и с небольшими перепадами.