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

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ имени М.В.Ломоносова

ФАКУЛЬТЕТ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ И КИБЕРНЕТИКИ

0034874Э1

Воронов Василий Юрьевич

На правах рукописи /

МЕТОДЫ РАЗРАБОТКИ ПАРАЛЛЕЛЬНЫХ ПРОГРАММ НА ОСНОВЕ МАШИННОГО ОБУЧЕНИЯ

Специальность 05.13.11 — математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

1 О ДЕК 2009

Москва - 2009 г.

003487491

Работа выполнена на кафедре автоматизации систем вычислительных ко плексов факультета вычислительной математики и кибернетики Московского г сударственного университета имени М. В. Ломоносова.

Научный руководитель:

Официальные оппоненты:

Ведущая организация:

кандидат физико-математических наук, доцент Попова Нина Николаевна

доктор технических наук, профессор Гергель Виктор Павлович.

кандидат физико-математических наук Малинаускас Костас Костович

Межведомственный суперкомпьютерный центр РАН

Защита диссертации состоится "18" декабря 2009 г. в 11 часов на заседании ди сертационного совета Д 501.001.44 при Московском государственном университе имени М. В. Ломоносова по адресу: 119991, ГСП-1 Москва, Ленинские горы, МГ имени М.В. Ломоносова, 2-й учебный корпус, факультет ВМК, аудитория 685.

С диссертацией можно ознакомиться в библиотеке факультета ВМК МГУ. текстом автореферата можно ознакомиться на официальном сайте ВМК МГ имени М. В. Ломоносова http://cs.msu.ru в разделе "Наука"- "Работа диссертац онных советов"-"Д 501.001.44".

Автореферат разослан "18" ноября 2009 г.

Ученый секретарь диссертационного совета профессор

¿Ч""7 Н. П. Трифонов

Общая характеристика работы

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

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

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

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

'L. Oliker et al. Scientific Application Performance on Candidate PetaScale Platforms // Technical report LBNL-62952. 2007. Ernest Orlando Lawrence Berkeley National Laboratory, Berkeley, USA

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

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

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

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

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

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

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

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

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

Научная новизна. Все основные результаты работы новые и заключаются в следующем:

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

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

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

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

Апробация работы. Основные результаты настоящей работы обсуждались на научно-исследовательском семинаре кафедры Автоматизации систем вычислительных комплексов факультета вычислительной математики и кибернетики МГУ под руководством чл.-корр. РАН JI. Н. Королева, совместном семинаре факультета ВМК МГУ и IBM Zurich Research Laboratory, а также докладывались и обсуждались на следующих конференциях:

1. Научная конференция «Тихоновские чтения» (г. Москва, ноябрь 2004 г.),

2. Всероссийские научные конференции «Научный Сервис в сети Интернет» (г. Новороссийск, сентябрь 2004 г., сентябрь 2005 г., сентябрь 2008 г.),

3. Летняя школа по научным вычислениям совместно с Waterford Institute of Technology (г. Москва, август 2006 г.),

4. Международная школа Ph.D. Winter School 2008 (г. Москва, ноябрь 2008 г.),

5. Международная конференция «International Conference on Computing (CIC 2008)» (г. Мехико, Мексика, декабрь 2008 г.),

6. Международная конференция «International Conference on Computing in Engineering, Science and Information (ICCEIS 2009)» (г. Лос-Анджелес, США, апрель 2009 г.),

7. Международная конференция «Numerical Analysis and Scientific Computing Applications (NASCA 2009)» (г. Агадир, Марокко, май 2009 г.),

8. 8-я международная конференция «European Numerical Mathematics and Advanced Applications (ENUMATH-09)» (г. Уппсала, Швеция, июль 2009 г.),

9. Международная конференция «International Conference on High Performance Computing, Networking and Communication Systems (HPCNCS-09)» (г. Орландо, США, июль 2009 г.),

10. Международная конференция «International Conference on Parallel Computing (ParCo-2009)» (г. Лион, Франция, сентябрь 2009 г.).

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

Структура и объем работы. Текст работы состоит из введения, трех глав, заключения, списка литературы и приложений. Диссертация изложена на 144 страницах, содержит 21 рисунок и 24 таблицы. Список литературы содержит 109 наименований, включая работы автора.

Содержание работы.

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

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

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

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

В разделе 1.1 представлен метод выбора решателя и настройки его параметров. Пусть задано множество целевых МВС {Нх,..., Нк}- Рассматривается множество решателей 5 параллельной программы, имеющих входные данные А.

Определение 1 Признаком /г входных данных А называется значение некоторой действительной функции = Сг(Л).

Обозначим вектор признаков входных данных Р(А) = {/ь ...,

Определение 2 Пусть требуется выполнить параллельную программу с входными данными А на п процессорах целевой МВС Н с применением решателя Б е 5. Функцией сложности решателя назовем зависимость

С:(тг,РДЯ)->Р, (1)

где F-признаки входных данных А.

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

С(п, F, S, Н) = Р.

После построения функции сложности выполняется определение решателя и его параметров S* 6 <S, для которого достигается минимум

minC (n,F,ShH) (2)

Для поиска минимума предложен генетический алгоритм.

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

T(ni,F,S, Н)

Т{п, F, S, Н)(п - щ)

при выполнении программы на щ и п > щ процессорах, где Г-время выполнения решателя. Предложен метод определения числа процессоров из заданного диапазона п* € (щ, пг], на котором для заданного решателя достигается наибольшее значение (3). Предложенный метод основан на решении задачи бинарной классификации. Пусть {(n,F, 5, Н, Т)}-выборка, полученная путем проведения вычислительного эксперимента на целевой МВС Я для данного решателя S, числа процессоров п G [rai, щ], входных данных из заданного множества А Е Л. Каждой паре значений Т\ = T(ni, F, Н),Тп = Т(п, F, Н) для заданного порога эффективности распараллеливания е £ [0,1] ставится в соответствие одна из двух меток класса у — {у+, у~}:

+ г / 1 T{nuF,H) ^ ,

- г , 1 T{nuF,H) .

У ={neM:T(n,F,H)(n-ni)<£}]

Полученные элементы {F, Н, ni,n, е,у} добавляются в обучающую выборку

TV. В соответствии с указанным алгоритмом обучающая выборка TV формируется для каждого значения порога эффективности из множества Е = {e¿ : О < £х < ••• < £*}.

Для элементов сформированной обучающей выборки Тг строится бинарный классификатор:

/ : {F,nhn,e) -» {у+,у~}.

Далее для каждого значения п € (пьпг] определяется максимальное значение еп 6 Е, для которого f(F,ni,n,en) = у+■ Результат выбора числа процессоров п* = argmaxn^n^fo,).

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

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

В разделе 1.4 рассматриваются особенности реализации разработанных методов построения параллельных программ. Поскольку методы опорных векторов формируют параметрическое семейство моделей, для повышения точности применяются алгоритмы отбора моделей с целью выбора конкретного вида классификатора или функции сложности. Предложен эвристический алгоритм отбора моделей опорных векторов путем выбора значений параметров, допускающий распаралелливание. Алгоритм заключается в выборе начального множества значений рассматриваемых параметров Vo, оценке точности модели опорных векторов для каждого элемента v Е Vo и выбора среди них комбинации значений v¡¡, соответствующих модели с наибольшей точностью. На основе значений Vq формируется множество V1 значений параметров модели, которые расположены в окрестности v¡, и шаг повторяется. В результате после к итераций результатом алгоритма будут значения параметров v*k. После этого модель с наибольшей точностью на обучающей выборке выбирается из моделей с параметрами {ujiuí>■ • •>vl}-

Для повышения точности построения функции сложности предложено

3V. Vapnüt, С. Cortes. Support Vector Networks // Machine Learning. 1995. Vol. 20, P. 273-29Г.

разбивать множество решателей 5 на т непересекающихся подмножеств 5 = и^х Для каждого подмножества методом регрессии опорных векто-

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

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

- Модуль извлечения признаков из входных данных параллельной програм-

мы. Модуль устанавливается на каждой целевой МВС;

- Модуль генерации обучающей выборки. Осуществляет сбор результатов и

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

- Ядро программной системы, в котором реализованы предложенные методы.

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

- Хранилище. Служит для накопления статистики о выполнении параллель-

ных программ. Модуль устанавливается на сервере системы; Архитектура программной системы представлена на рис. 1.

Рис. 1: Архитектура программной системы

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

Предложена, реализация модуля формирования признакового пространства разреженных СЛАУ на основе системы АпаМос!.

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

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

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

3 4 5 Число ядер

3 4 5 Число ядер

(а)

(Ь)

Рис. 2: Ускорение времени выполнения алгоритма отбора моделей опорных векторов для бинарного классификатора (а) и регрессии (Ь)

Число ядер

Рис. 3: Ускорение времени выполнения генетического алгоритма при увеличении числа нитей

алгоритмов выполнена на основе интерфейса программирования ОрепМР. Анализ параллельных реализаций обоих алгоритмов на восьмиядерной платформе с двумя процессорами Intel 5472 3.2GHz, 16 Gb RAM показывает ускорение при переходе от 1 до 8 нитей до 4,8 раз.

3\Vhitley D., Rana S., Hechendorn E. В. The island Model Genetic algorithm: On separability, population size and convergence // CIT. Journal oi computing and information technology. 1999. Vol. 7, N. 1. P. 33-47

Раздел 2.3 посвящен реализации алгоритмов отбора признаков входных данных для повышения точности предложенных методов. Для отбора признаков в методе выбора числа процессоров для решателя предложено использовать метод f-score4. В методе выбора и настройки параметров решателя отбор признаков применяется при построении функции сложности С. Предложен подход на основе алгоритма частичного сингулярного разложения (truncated SVD) и последующего выбора числа признаков для достижения наибольшей точности построения функции сложности. В результате применения указанных алгоритмов отбора признаков на рассматриваемых выборках данных получено повышение точности методов не менее чем на 4%, время построения методов сократилось в среднем на 17%.

В разделе 2.5 представлены выводы данной главы.

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

В разделе 3.1 представлены результаты применения предложенных методов для набора прикладных задач на основе решения разреженных СЛАУ. Сформирован набор разреженных СЛАУ, взятых из репозитория разреженных СЛАУ5, возникающих в различных приложениях (структурная механика., квантовая химия, гидродинамика, анализ ДНК, моделирование интегральных схем и др.). Для данных СЛАУ на целевых МВС проведен вычислительный эксперимент и собрана обучающая выборка, необходимая для построения методов. В результате применения построенных методов время решения рассматриваемых задач сокращено в среднем на 7%. На основе полученных результатов сформулированы рекомендации к решению данных задач на целевых МВС с использованием рассматриваемых библиотек.

В разделе 3.2 описывается задача моделирования сетей распределения питания СБИС. Проблема моделирования заключается в определении потенциалов в узлах многоуровневой металлической структуры, которая подключает активные устройства интегральной схемы к источнику питания [6].Характерной особенностью данной задачи является необходимость моделирования сетей питания с числом элементов порядка 105 - 108 различных конфигураций и размеров, что требует использования МВС и делает актуальным применение предложеных методов для сокращения времени моделирования. Для

4Y.W. Chen, С-J- Lin. Combining SVMs with various feature selection strategies // Studies In Fuzziness And Soft Computing. 2006. Vol. 207. P. 315-324

5T, Davies. University of Florida sparse matrix collection // NA digest. 1997. Vol. 97, N. 23, P. 7.

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

В разделе 3.3 рассматриваются особености применения предложенных методов в задаче моделирования сетей питания СБИС.

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

В разделе 3.4 обсуждаются результаты применения предложенных методов для параллельной программы моделирования сетей питания СБИС.

Метод выбора числа процессоров для решателя в задаче позволил получить на рассматриваемых наборах сетей питания совпадающие с фактическими значения числа процессоров (рис. 4(a),(Ь)) с погрешностью определения значения в среднем 18,7%. Применение метода выбора и настройки решателя для моделирования рассматриваемых наборов сетей питания на МВС Blue Gene/P приводит к сокращению времени вычисления в среднем на 16000 процессор-часов (таблица 1) и в среднем на 3500 процессор-часов на МВС СКИФ-МГУ «Чебышев» (таблица 2) при моделировании 1000 шагов переходного процесса в сети питания.

В разделе 3.5 приводятся выводы данной главы.

В заключении перечислены основные результаты диссертационной ра-

фактическое ускорение • прогнозируемое ускорение —* линейное ускорение -

фактическое ускорение • прогнозируемое ускорение линейное ускорение •

32 64 128 256 512 1024 64 128 256 512

число ядер число ядер

(а) (Ь)

Рис. 4: Результаты применения метода выбора числа процессоров для одного шага переходного процесса на МВС Blue Gene/P (а) и МВС «Чебышев» (Ь). Для МВС BlueGene,/P рассматривается модель сети питания сЮООО, режим запуска программ SMP, построение метода на выборке решения моделей сетей сЭООО, сбООО, с4000, сЗООО. Для МВС «Чебышев» рассматривается модель сети питания 69000, построение метода на выборке решения моделей сетей ¡>6000, М000,63000. п' обозначает полученное методом число процессоров для решения задачи.

Таблица 1: Результаты применения метода выбора и настройки параметров решателя на Blue Gene/P для п=512 ядер, модель сЮООО; обучение на статистике решения моделей сЗООО, с4000, сбООО, сЭООО для одного шага моделирования переходного процесса

Niter Ppredict ijact t default £method t economy

50 12949743,5 931,17 (10,74%) 1043,3 131,46 112,13 * 512 и 15,9ч

100 12412730,1 957,29 (8,25%) 1043,3 273,55 86,01 * 512 « 12,23ч

200 11716675,0 867,14 (16,88%) 1043,3 568,26 176,16* 512 и 25,05ч

500 11820381,9 905,31 (13,22%) 1043,3 1417,29 137,99 * 512 « 19,62ч

Обозначения: ЛГ«ег-кол-во итераций генетического алгоритма,

■Ррт-ейс1_значение функции сложности для полученного методом решателя 5*, сек. * Мб ^фактическое время моделирования для найденного решателя (в скобках указан процент улучшения по сравнению с решателем по умолчанию), сек. 'л/вий-время моделирования для решателя, используемого по умолчанию, сек. 1а1догИкт~ъремя выполнения метода, сек.

¿ссопоту-еокрашение машинного времени в моделировании СБИС при использовании решателя, найденного предложенным методом, в сравнении с решателем по умолчанию, процессор-часы.

Таблица 2: Результаты применения метода выбора и настройки параметров решателя на СКИФ-МГУ «Чебышев» для п=512 ядер, модель ЫОООО; обучение на статистике решения

№цег РогаИЛ аа 1йе)аиН ^теЬкод, ^есопоту

50 8564505 159,31 (9,06%) 175,2 157,21 15,89 * 512 » 2,25ч

100 7903257 147,01 (8,25%) 175,2 298,44 28,19 * 512 и 4,00ч

200 8139264 151,40 (16,09%) 175,2 641,13 23,8 * 512 « 3,38ч

500 7863475 146,27 (16,51%) 175,2 1981,44 28,93 * 512 « 4,11ч

Обозначения: /Уйег-кол-во итераций генетического алгоритма,

•РргеЛс(-значение функции сложности для полученного методом решателя 5*, сек. * Мб ¿/ос(-фактическое время моделирования для найденного решателя (в скобках указан процент улучшения по сравнению с решателем по умолчанию), сек. £&/<иЛ-время моделирования для решателя, используемого по умолчанию, сек. ^те№о1Гвремя выполнения метода, сек.

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

боты.

Основные результаты работы.

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

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

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

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

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

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

Публикации

1. Попова Я. Н., Воронов В. Ю., Джосан О. В., Медведев М. А. Сравнительный анализ эффективности параллельных вычислений с использованием современных параллельных математических библиотек на примере решения систем линейных уравнений // Труды Всероссийской научной конференции «Научный Сервис в Сети Интернет-2004». - М: Изд-во МГУ, 2004.

2. Медведев М. А., Попова Я. Я., Воронов В. Ю., Игумнов В. Н. Практический анализ параллельных методов решения СЛАУ для различного класса матриц на MIMD и SMP платформах // Труды Всероссийской научной конференции «Научный Сервис в Сети Интернет-2005». - М: Изд-во МГУ, 2005.

3. Воронов В. Ю., Попова Н. Н. Переносимость параллельных научных библиотек на платформы с мультиядерными процессорами на примере пакета PETSc // Труды Всероссийской научной конференции «Научный Сервис в Сети Интернет-2007». — М: Изд-во МГУ, 2007. - С. 184-187.

4. Воронов В. Ю., Попова Н. Н. О применении методов машинного обучения для автоматической настройки параметров решателей СЛАУ в параллельной библиотеке научных вычислений PETSc // Труды Всероссийской научной конференции «Научный Сервис в Сети Интернет-2008». - М: Изд-во МГУ, 2008. - С. 233-236.

5. Воронов В. Ю. Метод автоматического выбора и настройки разреженных решателей СЛАУ // йестник Московского Университета. Серия 15. Вычислительная математика и кибернетика. — 2009. — Т. 2. — С. 49-56.

6. Воронов В. Ю., Попова Н. Я. Моделирование сетей распределения питания СБИС на многоядерном вычислителе // Вычислительные методы и программирование. — 2009.-№2.-С. 51-60.

7. Voronov V. Y, Popova N. N. Parallel Power Grid Simulation on Platforms with Multi Core Processors (accepted) // Proceedings of IEEE International Conference on Computing in Engineering, Science and Information (ICCEIS09). — 2009.

8. 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.

9. 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.

10. Voronov V. Y., 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.

11. 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-09). - 2009. - P. 29.

Напечатано с готового оригинал-макета

Издательство ООО "МАКС Пресс" Лицензия ИД N 00510 от 01.12.99 г. Подписано к печати 17.11.2009 г. Формат 60x90 1/16. Усл.печл. 1,0. Тираж 70 экз. Заказ 637. Тел. 939-3890. Тел./факс 939-3891 119992, ГСП-2, Москва, Ленинские горы, МГУ им. М.В. Ломоносова, 2-й учебный корпус, 627 к.

Введение

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-62952. 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 позволил сократить время, необходимое для решения задачи, в среднем на 16000 процессор-часов для системы 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 für Plasmaphysik, Garching bei München. — 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. 117126.

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., Giménez D., González 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. 146159.

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., César 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 98052: 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. Benzi M., Тита M. A comparative study of sparse approximate inverse pre-conditioners // Appl. Numer. Math. — 1999. — Vol. 30, no. 2-3,— Pp. 305340.

70. Gilbert J. R., Toledo S. An Assessment of Incomplete-LU Preconditioners for Nonsymmetric Linear Systems // Informática. — 2000. — Vol. 24. — Pp. 409425.

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 24479. — 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 О., Gärtner К. 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-12853, ORNL Oak Ridge National Laboratory (US), 1995.