Помощь в написании студенческих работ
Антистрессовый сервис

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

Диссертация: Методы разработки параллельных программ на основе машинного обучения
ДиссертацияПомощь в написанииУзнать стоимостьмоей работы

Образец применения методов машинного обучения с использованием характеристик разреженной СЛАУ—работы, авторы которых решают задачу приближенного определения числа обусловленности матрицы СЛАУ на основе алгоритмов машинного обучения. Задача формулируется в виде проблемы классификации, предлагается алгоритм прогнозирования в выбранном пространстве признаков. Результаты обучения и тестирования… Читать ещё >

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

Содержание

  • 1. Разработка и исследование методов построения параллельных программ на основе машинного обучения
    • 1. 1. Метод выбора и настройки параметров решателей для параллельной программы
      • 1. 1. 1. Модель параллельного решателя
      • 1. 1. 2. Алгоритм отыскания минимума функции сложности
    • 1. 2. Метод выбора числа процессоров для запуска решателя
    • 1. 3. Построение классификатора и функции сложности на основе методов опорных векторов
      • 1. 3. 1. Классификатор опорных векторов
      • 1. 3. 2. Регрессия опорных векторов
      • 1. 3. 3. Параметры методов опорных векторов
    • 1. 4. Повышение точности предложенных методов построения параллельной программы
      • 1. 4. 1. Скользящий контроль для обучения моделей опорных векторов
      • 1. 4. 2. Алгоритм отбора моделей опорных векторов
      • 1. 4. 3. Декомпозиция пространства решателей
    • 1. 5. Выводы
  • 2. Методы и алгоритмы инструментальной программной системы для построения параллельных программ на основе предложенных методов и алгоритмов машинного обучения
    • 2. 1. Архитектура программной системы
    • 2. 2. Распараллеливание предложенных методов построения параллельной программы
      • 2. 2. 1. Параллельная реализация генетического алгоритма
      • 2. 2. 2. Параллельная реализация отбора моделей опорных векторов
      • 2. 2. 3. Оценка ускорения предложенных параллельных реализаций
    • 2. 3. Понижение размерности признакового пространства при построении моделей опорных векторов
      • 2. 3. 1. Реализация отбора признаков классификаторов опорных векторов
      • 2. 3. 2. Реализация понижения размерности для регрессии опорных векторов
    • 2. 4. Выводы
  • 3. Исследование эффективности предложенных методов на примере решения практических задач
    • 3. 1. Исследование предложенных методов для решения практических задач на основе систем линейных уравнений
      • 3. 1. 1. Эффективность метода выбора и настройки параметров решателя
      • 3. 1. 2. Точность метода выбора числа процессоров для решателя
    • 3. 2. Постановка задачи моделирования сетей распределения питания СБИС большой размерности
      • 3. 2. 1. Физическая структура и численная модель сетей питания СБИС
      • 3. 2. 2. Разработка параллельных методов решения задачи для МВС с общей памятью
      • 3. 2. 3. Разработка параллельных методов моделирования сетей питания СБИС на МВС с распределенной памятью
    • 3. 3. Исследование эффективности предложенных методов для решения задачи моделирования сетей питания СБИС
      • 3. 3. 1. Формирование признакового пространства
      • 3. 3. 2. Эффективность метода выбора и настройки параметров решателя
      • 3. 3. 3. Определение числа процессоров для решения задачи моделирования сетей питания СБИС
    • 3. 4. Выводы

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

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

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

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

XL. Oliker et al. Scientific Application Performance on Candidate PetaScale Platforms // Technical report LBNL-62 952. 2007. Ernest Orlando Lawrence Berkeley National Laboratory, Berkeley, USA тических библиотек.

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

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

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

3. Каким образом изменится производительность параллельной программы при переходе на другую МВС.

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

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

Работы, направленные на повышение эффективности параллельных программ, активно ведутся как у нас в стране, так и за рубежом. Одним из лидирующих направлений исследований в этой области является проблема автоматической настройки эффективности параллельных программ. Различные аспекты проблемы автоматической настройки эффективности паралллсьных программ рассматриваются в работах Дж. Деммеля, В. Эйкхота, Дж. Донгарра, К. Елик, М. Фриго, Т. Катагири и др. В системах, реализующих данный подход (ATLAS, OSKI) автоматическая настройка эффективности осуществляется на основе сбора и анализа статистики о выполнении параллельной программы.

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

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

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

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

Полиалгоритмы.

Одно из первых исследований по выбору алгоритма из нескольких возможных на основе анализа характеристик данных программы представлено в работе [1]. Авторы в рамках развиваемой ими проблемно-ориентированной системы NAPSS предлагают т.н. полиалгоритм (polyalgorithm) — композицию численных методов, осуществляющую решение задачи. В отдельных точках полиалгоритма содержатся условия, определяющие выбор того или иного численного метода на следующем этапе работы. Определение точек альтернатив, а также выбор методов выполнены с привлечением эксперта. Авторы представляют несколько полиалгоритмов для решения достаточно простых проблем.

Композиционный подход развивают авторы работы [2], описывающие технику т.н. мулътиметодов (multi-methods). Данная техника заключается в последовательном применении доступных численных методов. Последовательность применения методов определяется исходя из накопленной статистики применения. Заметим, что в данной модели не учитываются характеристики входных данных.

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

В работах [5, 6] предложен пакет итерационных решателей СЛАУ LINSOL. Данный пакет предоставляет восемь итерационных методов, применение которых к СЛАУ реализовано в форме полиалгоритма. Полиалгоритм в данном пакете подразумевает смену итерационного метода по ходу решения СЛАУ на основании анализа значений нормы невязки на каждой итерации решения. Алгоритм смены итерационного метода сформирован на основе сбора и анализа статистики по итерациям решения задачи. Следует отметить, что представленный авторами подход не предусматривает изначального анализа входной СЛАУ, а также не учитывает предобусловливания СЛАУ.

Исследование [7] посвящено общему подходу создания методов автоматической настройки итерационных решателей СЛАУ с предобусловливателем. Авторы предлагают ранжировать решатели по производительности (в выбранной метрике Memory х Time) и устойчивости (сходимость приближенного решения к точному для заданных условий). При этом выбор метода в основе базируется на анализе характеристик входных данных. Следует отметить, что пространство поиска настроек состоит из одного решателя (GMRES с параметром перезапуска) и одного предобусловливателя.

Обзор подходов автоматизации в коммуникационных библиотеках.

Несколько другой подход предлагается в работе [8]. Авторы рассматривают вопросы использования методов машинного обучения для выбора коллективных MPI-операций. Авторы рассматривают модель исходной проблемы в виде набора характеристик метода и вычислительной платформы. В качестве механизма поиска оптимальных значений характеристик авторы ограничиваются деревьями решений. Идея автоматической настройки примитивов коллективных операций MPI реализована в системе STAR-MPI [9]. Предлагаемый подход заключается в создании многих реализаций коллективных операций и механизма выбора конкретной реализации операции для заданного приложения. Алгоритм выбора является статическим, то есть условия применения каждого из алгоритмов определены изначально в виде метаданных. С помощью мониторинга коллективных операций формируются значения параметров, которые определяют наиболее производительную реализацию операции. Более простой механизм настройки производительности MPI-приложения доступен и в реализации Intel MPI. Так, утилита rnpitune осуществляет запуск пользовательского приложения с различными значениями внутренних настроек и определяет наилучшую для заданной платформы комбинацию.

Существующие система построения программ на основе операций линейной алгебры.

Цикл работ [10−13] посвящен анализу производительности и созданию автоматически настраиваемых программ линейной алгебры. В [10] авторы анализируют влияние параметров итерационного метода GMRES на производительность решения разреженной СЛАУ для архитектур с распределенной памятью. Основное внимание уделяется зависимости параметров перезапуска и ортогонализации в итерационном методе, влиянию параметров итерационного метода на выбор предобусловливателя из трех рассматриваемых типов, а также влиянию на произоводительность решения СЛАУ деталей реализации операций MPI и оптимизации кода компилятором. Представлены результаты эксперимента по решения нескольких классов СЛАУ с трсхдиагональнои матрицей.

В работах [11, 13] описывается параллельный пакет ILIB решения задач на собственные значения pi разреженных СЛАУ с механизмами автоматической настройки параметров. Настройка параметров производится динамически на этапе счета задачи. Изменяемые параметры в задаче—тип коллективных операций пересылки, фактор развертки цикла в алгоритме матрично-векторного умножения, фактор развертки цикла в реализации алгоритма тридиагона-лизации Хаусхолдера. Определения наилучшей комбинации этих параметров из некоторого диапазона значений выполняется путем вариации значений параметров и выбора комбинации параметров, соответствующих получаемому приложению с наименьшим временем счета.

Для выбора наилучшего предобусловливателя к линейной системе применяются все доступные реализации и выбирается та, которая соответствует наименьшей величине начальной нормы невязки. Настройка итерационного решателя GMRES (m) выполняется за счет запуска решателя с разными значениями параметра перезапуска и реализацией алгоритма ортогонализации, из которых затем выбирается реализация с наилучшей производительностью.

Работы [14, 15] описывают инструментальную систему автоматической настройки производительности параметров прямого решателя СЛАУ RAO-SS.

Инструментальная система выполняет настройку производительности прямых решателей СЛАУ из пакета 8ирегЫ1 [16]. При этом автоматически выбирается тип алгоритма переупорядочивания. Выбор алгоритма переупорядочивания осуществляется на основании величины разреженности матрицы СЛАУ ппг/М2, где N—размерность матрицы СЛАУ, ппг—количество ненулевых элементов матрицы СЛАУ. Выбор основан на применении нечетких правил над некоторым множеством значений характеристик матрицы СЛАУ, определенных экспертом. В качестве основной характеристики в системе используется разреженность (доля ненулевых элементов матрицы СЛАУ).

В статье [17] представлена методология автоматической настройки производительности функций умножения «матрица-матрица» РШРАСК. Вместо настройки параметров в библиотеке функций, РНлРАСК предлагает набор параметризированных шаблонов функций, из которых для целевой платформы генерируется адаптированная библиотека функций. Значения параметров определяются переборной стратегией по результатам замеров производительности генерируемых функций-кандидатов. Алгоритм поиска параметров учитывает такие характеристики платформы, как количество регистров и иерархия кэш-памяти. Первоначально выполняется поиск размеров блока (Мо, А^о), для которого наилучшим образом используются регистры. Далее для найденного блока выполняется поиск значений пары параметров (М^ТУх) Э (Мо, А^о), при которых наилучшим образом используется кэшпамять первого уровня, и так далее.

На примере пакета РНлРАСК в работах [18, 19] авторы представляют статистический подход к настройке производительности операций линейной алгебры. На основании обучающей выборки экспериментальных значений предлагается формировать полиномиальную зависимость времени выполнения задачи в зависимости от параметров, определяющих применяемую реализацию функции.

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

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

Механизм автоматической настройки производительности реализован в пакете FFTW [20]. В нем представлены алгоритмы преобразования Фурье, которые учитывают особенности вычислительной платформы. Алгоритм преобразования в пакете реализован в виде набора оптимизированных блоков на языке С, называемых подлетами (codelets). Каждый кодлет реализует некоторую часть алгоритма преобразования, причем кодлеты для одной и той же части являются взаимозаменяемыми. Специальный алгоритм динамически формирует набор кодлетов, называемый планом, составляющих алгоритм преобразования. Набор планов-кандидатов оценивается исходя из минимизации времени выполнения преобразования. Существенное значение в предложенном подходе занимает реализованная автоматическая генерация кодлетов.

Пакеты ATLAS [21, 22] и OSKI [23] являются наиболее известными и широко применяемыми представителем приложений автоматической настройки параметров численных библиотек. В этих пакетах реализована идея автоматической настройки функций пакета базовых операций линейной алгебры BLAS, настройке подвергаются операции вида «матрица-вектор» и «матрица-матрица» с целыо более эффективного использования кэш-памяти и других особенностей платформы. В пакете ATLAS настройка осуществляется двумя основными способами: варьирование параметров функций с выбором оптимальных настроек на этапе выполнения программы и создание множества реализаций функции, с выбором определенной реализации функции для дайной архитектуры.

К отличительным особенностям пакета OSKI следует отнести возможность использования априорной информацию пользователя о структуре заполнения матрицы, о характере и потоке вычислений в приложении. В результате работы OSKI осуществляется более эффективное использование кэшпамяти, кроме того пакет выполняет преобразование исходной матрицы, причем пользователь имеет возможность получить это преобразование явно в виде кода на языке OSKI-Lua и затем использовать во внешнем приложении. Авторы замечают, что настройка умножения требует в среднем в 40 раз больше операций с плавающей точкой, чем умножение «матрица-вектор», целесообразность применения настройки в конкретном случае должен определять пользователь исходя из специфики своего приложения.

Система PYTHIA-II [24] автоматически формирует для заданной СЛАУ рекомендуемый решатель. Решатели выбираются из библиотеки PELLPACK [25], ориентированной на численное решение эллиптических дифференциальных уравнений в частных производных. Для формирования рекомендаций система собирает статистику о производительности решения СЛАУ с выбранными решателями. Алгоритм рекомендации выполняет поиск закономерностей в базе статистики.

Схожая по функциональности система ITBL представлена в статье [26]. Основной принцип настройки производительности в ITBL—анализ структуры ненулевых элементов матрицы СЛАУ и определение на ее основе наиболее производительного решателя.

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

Система автоматически настраиваемых решателей задач на собственные значения FIBER [14, 29]. В данной системе реализовано три уровня настройки производительности: на этапе инсталляции пакета, статический до запуска и на этапе выполнения. Для настройки производительности строится аппроксимация функции времени от входных параметров. Метод построения функции заключается в следующем: среди всех параметров, которые подвергаются настройке, фиксируются значения нескольких (назовем их первой группой параметров) и путем вариации значений остальных параметров (второй группы) строится аппроксимация времени выполнения в виде полиномиальной функции. Затем выбирается полином с наилучшей точностью аппроксимации, его значения при вариации первой группы параметров и фиксированных значениях второй группы используются для построения полинома, аппроксимирующего время выполнения. Настройка параметров на этапе инсталляции осуществляется с использованием средств ABCLib [30, 31] .

Образец применения методов машинного обучения с использованием характеристик разреженной СЛАУ—работы [32, 33], авторы которых решают задачу приближенного определения числа обусловленности матрицы СЛАУ на основе алгоритмов машинного обучения. Задача формулируется в виде проблемы классификации, предлагается алгоритм прогнозирования в выбранном пространстве признаков. Результаты обучения и тестирования классификатора показывают ошибку прогнозирования в среднем 55%, однако такого качества прогнозирования достаточно чтобы судить о характере обусловленности матрицы без трудоемкого вычисления обращения матрицы. Данный подход находит применение в системе IPRS, разрабатываемой авторами в University of Kentucky, Lexington для автоматического выбора предобусловли-вателя СЛАУ. Система IPRS [34] предоставляет пользователю рекомендации по выбору предобусловливателя. Общая схема работы системы IPRS заключается в сборе статистики решения набора СЛАУ с различными решателями. СЛАУ сопоставляются характеристики (в основном численных характеристик) и на основании их значений СЛАУ пользователя соотносится к одной из групп СЛАУ для того, чтобы выбрать решатель, наиболее эффективно показывающий себя для задач дайной группы. В работе представлены результаты интенсивных вычислительных экспериментов с более чем 300 СЛАУ, проанализировано влияние значений различных характеристик СЛАУ на применение решателей, а также указаны основные направления для автоматизации выбора решателя на основании извлечения характеристик СЛАУ. К таким направлениям авторы причисляют техники извлечения знаний, в том числе ассоциативные правила, искусственные нейронные и другие.

Пакет SALSA [35, 36] — пример системы адаптивной настройки параметров итерационных решателей и предобусловливания СЛАУ на основе функциональности научной библиотеки PETSc и некоторых библиотечиых реализаций методов. SALSA состоит из нескольких модулей:

1. Модуль AnaMod [37] для анализа СЛАУ и извлечения из нее различных математических характеристик. Функциональность модуля предоставляет спектральные характеристики матрицы, вычисление норм, характеристик структуры заполнения матрицы.

2. Модуль NdMod обеспечивает единообразное представление метаданных, связанных с численной задачей.

3. Модуль IPre осуществляет выбор предобусловливателя для СЛАУ. Принцип выбора предобусловливателя в SALSA основан на сборе статистики о решении СЛАУ с применением разных решателей и значений параметров. Данный процесс является этапом обучения системы и, очевидно, имеет очень высокую вычислительную сложность. По результатам обучения каждая СЛАУ соотносится к определенному классу решателей, на котором достигается наибольшая производительность решения СЛАУ. Далее для каждого класса решателей вычисляются средние характеристики со-ответсвующих им СЛАУ и формируется апостериорная функция распределения. Эта функция позволяет оценить вероятность того, что СЛАУ с заданными признаками имеет наилучший решатель из данного класса. Таким образом, для определения наилучшего решателя для заданной СЛАУ необходимо найти минимум функции распределения по рассматриваемым классам решателей.

Другим примером подобного подхода является система, представленная в [38, 39]. Данная система выполняет поиск параметров, обеспечивающих наилучшее решение разреженной СЛАУ, на основе сбора статистики выполнения решателя СЛАУ для различных данных. Применяемые методы основаны на алгоритмах распознавания образов и предполагает соотнесение матрицы СЛАУ к одному из 6 типов согласно предлагаемым авторами характеристикам СЛАУ Ключевым элементом предложенной системы является т.н. база знаний, в которой собрана статистика запуска различных решателей СЛАУ для различных задач. Для каждой новой СЛАУ происходит вычисление признаков и на основе методов извлечения данных СЛАУ соотносится к одному из известных классов СЛАУ, для которых из базы знаний берется наиболее производительный решатель. Приведенные результаты экспериментов основаны на анализе некоторых матриц СЛАУ малой размерности, что пока не позволяет судить о применимости подхода авторов к реальным программам.

Цели диссертационной работы.

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

1. Разработка методов выбора решателя и настройки его параметров для эффективного выполнения параллельной программы на многопроцессорных и многоядерных вычислительных системах;

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

3. Разработка инструментальной программной системы, реализующей предложенный подход;

4. Исследование применимости и эффективности предложенных методов на примерах решения конкретных прикладных задач.

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

Структура диссертационной работы.

Диссертационная работа состоит из данного введения, трех глав, заключения и приложений.

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

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

Глава 3 посвящена исследованию предложенных методов для примеров параллельных программ. Представлены результаты применения методов в параллельных программах, основанных на решении систем линейных уравнений с разреженной матрицей коэффициентов (разреженных СЛАУ). Рассматривается задача моделирования параметров сетей питания СБИС большой размерности. Представлены результаты исследования эффективности предложенных методов в данном крупномасштабном приложении.

В заключении сформулированы основные результаты диссертационной работы, выносимые на защиту.

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

3.4 Выводы.

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

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

Заключение

.

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

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

2. Разработана распределенная инструментальная программная система для построения эффективных параллельных программ, реализующая предложенные методы. Система поддерживает разработку параллельных программ для высокопроизводительных вычислительных систем на основе использования высокоуровневых математических библиотек. Разработанная система поддерживает разработку параллельных программ для вычислительных систем IBM Blue Gene/P и СКИФ-МГУ «Чебышев» и имеет возможность подключения других многопроцессорных и многоядерных систем.

3. Проведено исследование эффективности предложенных методов и разработанной инструментальной системы для класса прикладных задач, основанных на решении разреженных систем линейных уравнений с применением математических библиотек PETSc, HYPRE. Получено сокращение времени решения задач в среднем на 7,8%.

4. С применением разработанной системы выполнено решение задачи моделирования сетей питания СБИС. Выбраны решатели и параметры их настройки. Разработана параллельная программа для проведения моделирования на системах СКИФ-МГУ «Чебышев» и Blue Gene/P. Предложенный подход в применении к моделям сетей питания СБИС с числом элементов порядка 108 позволил сократить время, необходимое для решения задачи, в среднем на 16 000 процессор-часов для системы Blue Gene/P и на 3500 процессор-часов для МВС СКИФ-МГУ «Чебышев» при моделировании 1000 шагов переходного процесса в сети питания.

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

Показать весь текст

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

  1. Rice J. R., Rosen S. NAPSS. A numerical analysis problem solving system // Proceedings of the 1966 21st national conference. — 1966. — Pp. 51−56.
  2. Mclnnes L., N orris В., Bhoiumick S., Raghavan P. Adaptive sparse linear solvers for implicit CFD using Newton-Krylov algorithms // 2nd MIT Conference on Computational Fluid and Solid Mechanics, Cambridge, MA (US), 06/17/2003−06/20/2003. 2003.
  3. Bhowmick S., Raghavan P., Teranishi K. A combinatorial scheme for developing efficient composite solvers // Lecture notes in computer science. — 2004.
  4. Bhowmick S., Eijkhout V., Freund Y., Fuentes E., Keyes D. Application of machine learning to the selection of sparse linear solvers. — 2006.
  5. Schonauer W., Hafner H., Weiss R. LINSOL, a parallel iterative linear solver package of generalized CG-type for sparse matrices / / Proc. Eighth SI AM Conference on Parallel Processing for Scientific Computing, Minneapolis, MN, March. 1997.
  6. Hafner H., Schonauer W., Weiss R. The parallel and portable linear solver package LINSOL // Proceedings of the Fourth European SGI/Cray MPP Workshop, IPP R/46, Max Planck -Institut fur Plasmaphysik, Garching bei Munchen. — 1998.
  7. George Т., Sarin V. An approach recommender for preconditioned iterative solvers // 2007 International Conference on Preconditioning Techniques for Large Sparse Matrix Problems in Scientific and Industrial Applications. — 2007.
  8. Pjesivac-Grbovic J., Angskun Т., Bosilca G., Fagg G. E., Gabriel E., Don-garra J. Performance Analysis of MPI Collective Operations // Parallel and
  9. Distributed Processing Symposium, 2005. Proceedings. 19th IEEE International. — 2005. — Pp. 272a-272a.
  10. Faraj A., Yuan X., Lowenlhal D. STAR-MPI: self tuned adaptive routines for MPI collective operations // Proceedings of the 20th annual international conference on Supercomputing / ACM Press New York, NY, USA. — 2006. — Pp. 199−208.
  11. Kuroda H., Katagiri T., Kanada Y. Performance of Automatically Tuned Parallel GMRES (m) Method on Distributed Memory Machines // Hakken Kagaku A05-han. Heisei 11 Nendo. Dai2kai Kaigi Koen Yoshishu. — 1999. — Pp. 11−19.
  12. Katagiri T., Kuroda II., Kanada Y. A Method for Automatically Tuned Parallel Tridiagonalization on Distributed Memory Vector-Parallel Machines // Vector and Parallel Processing. — 2003.
  13. Katagiri T., Kise K., Honda II., Yuba T. Effect of auto-tuning with user’s knowledge for numerical software // CF '04: Proceedings of the 1st conference on Computing frontiers. New York, NY, USA: ACM, 2004. — Pp. 12−25.
  14. Ishii Y., Katagiri T., Honda H. RAO-SS: A Run-time Auto-Tuning Facility for Sparse Solvers with Autopilot / / IP S J SI G Technical Reports. — 2005. — Vol. 2005, no. 19. Pp. 97−102.
  15. Li X. An overview of SuperLU: Algorithms, implementation, and user interface // ACM Transactions on Mathematical Software (TOMS').— 2005.— Vol. 31, no. 3.-Pp. 302−325.
  16. Bilmes J., Asanovic K., Chin C. W., DemmelJ. Optimizing Matrix Multiply
  17. Using PHiPACK: A Portable, High Performance, ANSI C Coding Methodology // Proceedings of International Conference on Supercomputing 1997. -1997. Pp. 340−347.
  18. Vuduc R., Dernmel J., Bilm. es J. Statistical models for automatic performance tuning // Lecture Notes in Computer Science.— 2001.— Pp. 117 126.
  19. Vuduc R., Demmel J., Bilmes J. Statistical models for empirical search-based performance tuning // International Journal of High Performance Computing Applications. — 2004. — Vol. 18, no. 1. — P. 65.
  20. Frigo M., Johnson S. FFTW: an adaptive software architecture for the FFT // Proceedings of the 1998 IEEE International Conference on Acoustics, Speech, and Signal Processing, 1998. ICASSP'98.— 1998. — Vol. 3.
  21. Whaley R., Dongarra J. Automatically tuned linear algebra software // Proceedings of the 1998 ACM/IEEE conference on Supercomputing (CDROM) / IEEE Computer Society Washington, DC, USA. 1998. — Pp. 1−27.
  22. Whaley R., Petitet A., Dongarra J. Automated empirical optimizations of software and the ATLAS project // Parallel Computing. — 2001.— Vol. 27, no. 1−2. Pp. 3−35.
  23. Vuduc R., Demmel J., Yelick K. OSKI: A library of automatically tuned sparse matrix kernels // Journal of Physics: Conference Series. — 2005. — Vol. 16, no. l.-Pp. 521−530.
  24. Fukui Y., Hasegawa H. Test of Iterative Solvers on ITBL // HPCASIA '05: Proceedings of the Eighth International Conference on High-Performance
  25. Computing in Asia-Pacific Region. — 2005. — P. 422.
  26. Cuenca J., Gimenez D., Gonzalez J. Architecture of an automatically tuned linear algebra library // Parallel Computing. — 2004. — Vol. 30, no. 2. — Pp. 187−210.
  27. Garcia L., Cuenca J., Gimenez. Using Experimental Data to Improve the Performance Modelling of Parallel Linear Algebra Routines // Lecture Notes in Computer Science. 2008. — Vol. 4967. — Pp. 1150−1159.
  28. Katagiri T., Kise K., Honda H., Yuba T. FIBER: A generalized framework for auto-tuning software // Lecture notes in computer science. — Pp. 146 159.
  29. Katagiri T., Kanada Y. An efficient implementation of parallel eigenvalue computation for massively parallel processing // Parallel Computing. — 2001. Vol. 27, no. 14. — Pp. 1831−1845.
  30. Katagiri T., Kise K., Honda H., Yuba T. ABCLibDRSSED: A parallel eigensolver with an auto-tuning facility // Parallel Computing. — 2006. — Vol. 32, no. 3.- Pp. 231−250.
  31. Xu S., Zhang J. A New Data Mining Approach to Predicting Matrix Condition Numbers // Commun. Inform. Systems. 2004.— Vol. 4, no. 4.— Pp. 325−340.
  32. Xu S., Lee E. J., Zhang J. An interim analysis report on preconditioners and matrices: Tech. Rep. 388−03: University of Kentucky, Lexington- Department of Computer Science, 2003.
  33. Self-adapting linear algebra algorithms and software / J. Demmel, J. Don-garra, V. Eijkhout, E. Fuentes, A. Petitet, R. Vuduc, R. Whaley, K. Yelick // Proceedings of the IEEE. 2005. — Vol. 93, no. 2. — Pp. 293−312.
  34. Eijkhout V., Fuentes E., Eidson T., Dongarra J. The Component Structure of a Self-Adapting Numerical Software System // International Journal of Parallel Programming (IJPP). 2005. — Vol. 33, no. 2−3. — Pp. 137−143.
  35. Eijkhout V., Fuentes E. A proposed standard for numerical metadata // Innovative Computing Laboratory, University of Tennessee, Tech. Rep. ICL-UT-03−02. 2003.
  36. Salawdeh I., Cesar E., Morajko A., Margalef Т., buque E. Performance Model for Parallel Mathematical Libraries Based on Historical Knowledgebase // Lecture Notes in Computer Science. — 2008. — Vol. 5168.— Pp. 110−119.
  37. Automatic performance tuning of parallel mathematical libraries.'
  38. Davies T. A. Summary of available software for sparse direct methods, http: //cise.uf1.edu/research/sparse/codes.
  39. Dongarra J., Bullari A. Freely available sofrwarc for linear algebra on the web. — 2009. http://netlib.org/utk/people/JackDongarra/la-sw. html.
  40. Scientific Application Performance on Candidate PetaScale Platforms / L. Oliker, A. Canning, J. Carter, C. Iancu, M. Lijewski, S. Kamil, J. Shalf et, al. 2007.
  41. Speck R., Gibbon P., Hoffmann M. Efficiency and scalability of the parallel barnes-hut tree code pepe // Abstract Book of International Conference on Parallel Computations (PARCO-09). 2009.
  42. В. В., Воеводин В. В. Параллельные вычисления.— БХВ-Петербург, 2002. С. 608.
  43. Wahnig Н., Kotsis G., Haring G. Performance Prediction of Parallel Programs // Messung, Modellierung und Bewertung von. — 1993. — Pp. 64−76.
  44. В. А., Трекин А. Г. Генетические алгоритмы решения задач смешанных задач целочисленной и комбинаторной оптимизации при синтезе архитектур ВС // Искуственный интеллект. — 2000. — № 2.
  45. Davis J., Goadrich М. The Relationship Between Precision-Recall and ROC curves // Proceedings of the 23rd international conference on Machine learning / ACM New York, NY, USA. 2006. — Pp. 233−240.
  46. Gupta A., Koric S., George T. Sparse Matrix Factorization om Massively Parallel Computers // Proceedings of SC09.— 2009.
  47. Malony A. D., Mertsiotakis V., Quick A. Automatic scalability analysis of parallel programs based on modeling techniques // Computer Performance
  48. Evaluation: Modelling Techniques and Tools (LNCS 794) (G. Ilaring and G. Kotsis, eds.). 1994. — Pp. 139−158.
  49. Mehra P., Schulbach C., Yan J. A comparison of two model-based performance-prediction techniques for message-passing parallel programs // ACM SIGMETRICS Performance Evaluation Review1994, — Vol. 22, no. 1, — Pp. 181−190.
  50. В. H. Восстановление зависимостей по эмпирическим данным. — М: Наука, 1979.
  51. Vapnik V. N. The Nature of Statistical Learning Theory. — Springer, 1995.
  52. Cortes C., Vapnik V. N. Support-Vector Networks // Machine Learning.— 1995. Vol. 20. Pp. 273−297.
  53. Smola A., Scholkopf B. A tutorial on support vector regression // Statistics and Computing. 2004. — Vol. 14, no. 3. — Pp. 199−222.
  54. Schoelkopf, B. and Smola, A. J. Learning with Kernels. — Cambridge, MA: The MIT Press, 2002.
  55. Schoelkopf B. Statistical Learning and Kernel Methods: Tech. Rep. MSR-TR-2000−23. — Microsoft Corporation, One Microsoft Way, Redmond, WA 98 052: Microsoft Research, 2000.
  56. Fan R., Chen P., Lin C. Working Set Selection Using Second Order Information for Training Support Vector Machines // The Journal of Machine Learning Research. — 2005. — Vol. 6. — Pp. 1889−1918.
  57. Chen P., Fan R., Lin C. A Study on SMO-Type Decomposition Methods for Support Vector Machines // IEEE Transactions on Neural Networks. — 2006. Vol. 17, no. 4. — Pp. 893−908.
  58. В. H., Червопенкис А. Я. Теория распознавания образов, — М: Наука, 1974. С. 415.
  59. Akaike H. A new look at the statistical model identification // IEEE transactions on automatic control. — 1974. — Vol. 19, no. 6. — Pp. 716−723.
  60. Schwarz K. Optimization of the statistical exchange parameter a for the free atoms H through Nb // Physical Review В. — 1972, — Vol. 5, no. 7.— Pp. 2466−2468.
  61. Stone M. Comments on model selection criteria of Akaike and Schwarz //
  62. Journal of the Royal Statistical Society. Series В (Methodological). — 1979. — Pp. 276−278.
  63. Duan K., Keerthi S., Poo A. Evaluation of simple performance measures for tuning SVM hyperparameters // Neurocomputing. — 2003.— Vol. 51, no. 1.- Pp. 41−60.
  64. Joachims T. Estimating the generalization performance of a SVM efficiently. 1999.
  65. Evolutionary Feature and Parameter Selection in Support Vector Regression // MICAI 2007, LNAI. 2007. — Vol. 4827. — Pp. 399−408.
  66. Nachtigal N., Reddy S., Trefethen L. How fast are nonsymmetric matrix iterations? // SIAM Journal on Matrix Analysis and Applications. — 1992. — Vol. 13. P. 778.
  67. Greenbaum A., Strakos Z. Any nonincreasing convergence curve is possible for GMRES // SIAM Journal of Matrix Analysis Applications. — 1996.
  68. Chow E., Saad Y. Experimental study of ILU preconditioned for indefinite matrices //J. Comput. Appl. Math. — 1997. — Vol. 86, no. 2. — Pp. 387−414.
  69. M., Тита M. A comparative study of sparse approximate inverse pre-conditioners // Appl. Numer. Math. — 1999. — Vol. 30, no. 2−3, — Pp. 305 340.
  70. Gilbert J. R., Toledo S. An Assessment of Incomplete-LU Preconditioners for Nonsymmetric Linear Systems // Informatica. — 2000. — Vol. 24. — Pp. 409 425.
  71. Wu K., Milne B. A survey of packages for large linear systems // Lawrence Berkeley National Lab., Rept. LBNL-45U6, Berkeley, CA, Feb. — 2000.
  72. Kumbhar A., Chakravarthy К., Keshavamurthy R.- Rao G. Utilization of Parallel Solver Libraries to solve Structural and Fluid problems // Tech.
  73. Rep. Cranes Software International Ltd., Bangalore. — 2005.
  74. Gould N. I. M., Scott J. A., Hu Y. A numerical evaluation of sparse direct solvers for the solution of large sparse symmetric linear systems of equations // ACM transactions on mathematical software. — 2007.— Vol. 33, no. 2.
  75. Gupta A., George T., Sarin V. An Experimental Evaluation of Iterative Solvers for Large SPD Systems of Linear Equations: Tech. Rep. RC 24 479. — Yorktown Heights, NY: IBM T. J. Watson Research Center, 2008.
  76. PETSc Web page / S. Balay, K. Buschelman, W. D. Gropp, D. Kaushik, M. G. Knepley, L. C. Mclnnes, B. F. Smith, H. Zhang // See http://www. mes. anl. gov/petsc. http://www.msc.anl.gov/petsc-2.
  77. Falgout R. D., Yang U. M. HYP RE: a Library of High Performance Pre-conditioners // Lecture Notes in Computer Science. — 2002, — Vol. 2331.— Pp. 632−641.
  78. Chang C. C., Lin C. J. — LIBSVM: a library for support vector machines, 2001.— Software available at http://www.csie.ntu.edu.tw/ cjlin/libsvm.
  79. Whitley D., Rana S., Hechendorn R. B. The island Model Genetic algorithm: On separability, population size and convergence // CIT. Journal of computing and information technology. — 1999. — Vol. 7, no. 1. — Pp. 33−47.
  80. Combining svms with various feature selection strategies // Technical Report, Department of Computer Science, National Taiwan University. — 2003.
  81. Chen J., Saad Y. Lanczos Vectors versus Singular Vectors for Effective Dimension Reduction // Knowledge and Data Engineering, IEEE Transaction on. — 2009.- Vol. 21, no. 13.— Pp. 1091−1103. http://www-users.es. umn.edu/~saad/PDF/umsi-2008−02.pdf.
  82. Davis T. University of Florida sparse matrix collection // NA Digest. — 1997. Vol. 97, no. 23. — P. 7.
  83. Qian H., Nassif S., Sapatnekar S. Power grid analysis using random walks // Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on. 2005. — Vol. 24, no. 8. — Pp. 1204−1224.
  84. Kozhaya J., Nassif S., Najm F. A multigrid-like technique for power grid analysis // Computer-Aided Design of Integrated Circuits and Systems,
  85. EE Transactions on. 2002. — Vol. 21, no. 10. — Pp. 1148−1160.
  86. Chen Т., Chen C. Efficient Large-Scale Power Grid Analysis Based on Preconditioned Krylov-Subspace Iterative Methods // Proc. Design Automation Conference. 2001. — Pp. 559−562.
  87. Zhao M., Panda R. V., Sapatnekar S. S., Blaauw D. Hierarchical analysis of power distribution networks // Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on. — 2002.— Vol. 21, no. 2.— Pp. 159−168.
  88. Sun K., Zhou Q., Mohanram K., Sorensen D. Parallel domain decomposition for simulation of large-scale power grids // Proceedings of the 2007 IEEE/ACM international conference on Computer-aided design / IEEE Press Piscataway, NJ, USA. 2007. — Pp. 54−59.
  89. M. IO., Чепурина Э. П. Методы решения СЛАУ большой размерности.— Новосибирск: Изд-во НГТУ, 2000.
  90. Schenk О., Gartner К. Solving unsymmetric sparse systems of linear equations with PARDISO // Future Generation Computer Systems. — 2004. — Vol. 20, no. 3. Pp. 475−487.
  91. В. П. Методы неполной факторизации для решения алгебраических систем, — М: Наука, Физматлит, 1995.
  92. Gupta A., Joshi М., Kumar V. WSMP: A high-performance shared and distributed-memory parallel sparse linear equation solver // Report, University of Minnesota and IBM Thomas J. Watson Research Center. — 2001.
  93. An overview of the Trilinos project / M. A. Heroux, E. T. Phipps, A. G. Salinger, H. K. Thornquist, R. S. Tuminaro, J. M. Willenbring, A. Williams et al. // ACM Transactions on Mathematical Software (TOMS). — 2005.— Vol. 31, no. 3.- Pp. 397−423.
  94. II. H., Воронов В. Ю., Дэюосан О. В., Медведев М. А. Опыт внедрения современного программного обеспечения на платформе IBM Regatta // Программные системы и инструменты. Тематический сборник N5. — 2004.
  95. П. Н., Воронов В. Ю., Игумнов В. П., Медведев М. А. Переносимый пакет поддержки распределенной обработки данных с помощью численных методов // Труды Всероссийской научной конференции «Научный Сервис в Сети Интернет-2005». — М: Изд-во МГУ, 2005.
  96. Специализированная распределенная система обработки экспериментальных данных // Труды второй Всероссийской научной конференции «Методы и средства обработки информации». — М: Изд-во МГУ, 2005. — С. 213−220.
  97. В. Ю. Метод автоматического выбора и настройки разреженных решателей СЛАУ // Вестник Московского Университета. Серия 15. Вычислительная математика и кибернетика. — 2009. — Т. 2. — С. 49−56.
  98. В. Ю.- Попова H. Н. Моделирование сетей распределения питания СБИС на многоядерном вычислителе // Вычислительные методы и програмлшрова, ние. — 2009. — № 2. — С. 51−60.
  99. Voronov V. Y., Popova N. N. Parallel Power Grid Simulation on Platforms with Multi Core Processors (acceptcd) // Proceedings of IEEE International Conference on Computing in Engineering, Science and Information (IC-CEIS09). 2009.
  100. Voronov V. Y., Popova N. N. A Hybrid Simulation of Power Grids using High-Performance Linear Algebra Packages // Abstract book of Numerical Analysis and Scientific Computing with Applications (NASCA-09) conference. 2009. — P. 90.
  101. Voronov V. Y., Popova N. N. Use of Threaded Numerical Packages for Parallel Power Grid Simulation // Proceedings of International Conference on High Performance Computing, Networking and Communication Systems (HPCNCS-09). 2009. — Pp. 39−45.
  102. Voronov V. Y., Popova N. N. Automatic Performance Tuning Approach for Parallel Applications Based on Linear Solvers // Abstract Book of International Conference on-Parallel Computations (ParCo-2009). 2009. — P. 29.
  103. Voronov V. Y. j Popova N. N. Machine Learning Approach to Automatic Performance Tuning of Power Grid Simulator // Abstract Book of 8th European Numerical Mathematics and Advanced Applications (ENUMATH-09) conference. 2009. — P. 291.
  104. Hernandez V., Roman J., Vidal V. SLEPc: A scalable and flexible toolkit for the solution of eigenvalue problems // ACM Transactions on Mathematical Software (TOMS). 2005. — Vol. 31, no. 3. — Pp. 351−362.
  105. Lee S. L. Best available bounds for departure from normality // SIMAT.— 1996. Vol. 17. — Pp. 984−991.
  106. Lee S. Bounds for Departure from Normality and the Frobenius Norm of Matrix Eigenvalues: Tech. rep.: ORNL/TM-12 853, ORNL Oak Ridge National Laboratory (US), 1995.
Заполнить форму текущей работой

Сессия? Спокойно!