авторефераты диссертаций БЕСПЛАТНАЯ  БИБЛИОТЕКА

АВТОРЕФЕРАТЫ КАНДИДАТСКИХ, ДОКТОРСКИХ ДИССЕРТАЦИЙ

<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ

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

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

имени M.В.Ломоносова

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

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

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

МЕТОДЫ РАЗРАБОТКИ ПАРАЛЛЕЛЬНЫХ ПРОГРАММ

НА ОСНОВЕ МАШИННОГО ОБУЧЕНИЯ

Специальность 05.13.11 математическое и программное обеспечение

вычислительных машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-математических наук

Москва 2009 г.

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

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

Официальные оппоненты: доктор технических наук, профессор Гергель Виктор Павлович, кандидат физико-математических наук Малинаускас Костас Костович

Ведущая организация: Межведомственный суперкомпьютерный центр РАН

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

С диссертацией можно ознакомиться в библиотеке факультета ВМК МГУ.

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

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

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

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

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

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

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

Пусть в параллельной программе, реализующей заданный алгоритм, мо жет быть выделен наиболее трудоемкий этап, для выполнения которого мо жет использоваться один из заданного набора подалгоритмов. Назовем такие подалгоритмы решателями. Примерами решателей могут служить функции математических библиотек. Выбор используемого решателя и определение значений его параметров влияют на эффективность параллельной програм мы. В условиях многопроцессорных систем такой выбор должен выполняться как с учетом особенностей входных данных решателя, так и с учетом пара метров вычислительной системы, на которой предполагается выполнение па раллельной программы. Важным параметром, связанным с эффективностью параллельной программы, является число процессоров, необходимых для вы полнения параллельной программы на рассматриваемой, целевой МВС. Про L. Oliker et al. Scientic 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 факультета ВМК МГУ, а также на вы сокопроизводительном кластере СКИФ-МГУ Чебышев.

Апробация работы. Основные результаты настоящей работы обсужда лись на научно-исследовательском семинаре кафедры Автоматизации систем вычислительных комплексов факультета вычислительной математики и ки бернетики МГУ под руководством чл.-корр. РАН Л. Н. Королева, совместном семинаре факультета ВМК МГУ и 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 Scientic Compu ting Applications (NASCA 2009) (г. Агадир, Марокко, май 2009 г.), 8. 8-я международная конференция European Numerical Mathematics and Advanced Applications (ENUMATH-09) (г. Уппсала, Швеция, июль 2009 г.), 9. Международная конференция International Conference on High Perfor mance Computing, Networking and Communication Systems (HPCNCS-09) (г. Орландо, США, июль 2009 г.), 10. Международная конференция International Conference on Parallel Com puting (ParCo-2009) (г. Лион, Франция, сентябрь 2009 г.).





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

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

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

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

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

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

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

Определение 1 Признаком fi входных данных A называется значение некоторой действительной функции fi = Gi (A).

Обозначим вектор признаков входных данных F (A) = {f1,..., fl }T.

Определение 2 Пусть требуется выполнить параллельную программу с входными данными A на n процессорах целевой МВС H с применением ре шателя S S. Функцией сложности решателя назовем зависимость C : (n, F, S, H) P, (1) где F –признаки входных данных A.

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

После построения функции сложности выполняется определение решателя и его параметров Si S, для которого достигается минимум min C(n, F, Si, H) (2) Si S Для поиска минимума предложен генетический алгоритм.

Раздел 1.2 посвящен методу выбора числа процессоров для решателя па раллельной программы. Критерием выбора числа процессоров является ве личина эффективности распараллеливания решателя T (n1, F, S, H) (3) T (n, F, S, H)(n n1) при выполнении программы на n1 и n n1 процессорах, где T –время выпол нения решателя. Предложен метод определения числа процессоров из задан ного диапазона n (n1, n2], на котором для заданного решателя достигается наибольшее значение (3). Предложенный метод основан на решении задачи бинарной классификации. Пусть {(n, F, S, H, T )}–выборка, полученная пу тем проведения вычислительного эксперимента на целевой МВС H для дан ного решателя S, числа процессоров n [n1, n2], входных данных из заданно го множества A A. Каждой паре значений T1 = T (n1, F, H),Tn = T (n, F, H) для заданного порога эффективности распараллеливания [0, 1] ставится в соответствие одна из двух меток класса y = {y +, y }:

T (n1, F, H) y + = {n (n1, n2] : } T (n, F, H)(n n1 ) T (n1, F, H) y = {n (n1, n2] : };

T (n, F, H)(n n1) Полученные элементы {F, H, n1, n,, y} добавляются в обучающую выборку T r. В соответствии с указанным алгоритмом обучающая выборка T r форми руется для каждого значения порога эффективности из множества E = {i :

0 1 · · · k }.

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

f : (F, n1, n, ) {y +, y }.

Далее для каждого значения n (n1, n2] определяется максимальное зна чение n E, для которого f (F, n1, n, n) = y +. Результат выбора числа процессоров n = arg maxn(n1,n2 ] (n).

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

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

В разделе 1.4 рассматриваются особенности реализации разработанных методов построения параллельных программ. Поскольку методы опорных векторов формируют параметрическое семейство моделей, для повышения точности применяются алгоритмы отбора моделей с целью выбора конкрет ного вида классификатора или функции сложности. Предложен эвристиче ский алгоритм отбора моделей опорных векторов путем выбора значений па раметров, допускающий распаралелливание. Алгоритм заключается в выбо ре начального множества значений рассматриваемых параметров V 0, оценке точности модели опорных векторов для каждого элемента v V 0 и выбора среди них комбинации значений v0, соответствующих модели с наибольшей точностью. На основе значений v0 формируется множество V 1 значений пара метров модели, которые расположены в окрестности v0, и шаг повторяется. В результате после k итераций результатом алгоритма будут значения парамет ров vk. После этого модель с наибольшей точностью на обучающей выборке выбирается из моделей с параметрами {v0, v1,..., vk }.

Для повышения точности построения функции сложности предложено V. Vapnik, C. Cortes. Support Vector Networks // Machine Learning. 1995. Vol. 20, P. 273–297.

разбивать множество решателей S на m непересекающихся подмножеств S = k=1,...,m Sk. Для каждого подмножества методом регрессии опорных векто ров строится функция сложности Ck, в результате решение (1) заменяется решением m задач на множествах меньшей размерности. В результате де композиции каждая функция сложности Ck (n, F, S) соответствует одному из подмножеств решателей на одной из целевых МВС. Это позволяет снизить время построения функции и применения генетического алгоритма.

В разделе 1.5 сформулированы выводы данной главы.

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

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

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

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

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

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

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

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

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

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

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

Алгоритм отбора моделей обладает естественным параллелизмом по дан ным, пространство поиска параметров разбивается на подмножества для неза висимой обработки на каждом ядре, последующего выбора наилучшей моде ли среди полученных на каждом ядре. Предложена параллельная реализация генетического алгоритма, основанная на островной модели3.В рамках парал лельной реализации каждый остров особей выделяется на ядро процессора, стадии миграции особей между островами требуют синхронных обменов дан ными между островами. Практическая реализация указанных параллельных 10 выборка 100 элементов выборка 100 элементов выборка 200 элементов выборка 200 элементов 9 выборка 500 элементов выборка 500 элементов выборка 1000 элементов выборка 1000 элементов 8 выборка 5000 элементов выборка 5000 элементов Ускорение, раз Ускорение, раз 7 линейное ускорение линейное ускорение 6 5 4 3 2 1 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 Число ядер Число ядер (a) (b) Рис. 2: Ускорение времени выполнения алгоритма отбора моделей опорных векторов для бинарного классификатора (a) и регрессии (b) 80 особей 160 особей 240 особей линейное ускорение Ускорение, раз 1 2 3 4 5 6 7 Число ядер Рис. 3: Ускорение времени выполнения генетического алгоритма при увеличении числа нитей алгоритмов выполнена на основе интерфейса программирования OpenMP.

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

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, N. 1. P. 33– Раздел 2.3 посвящен реализации алгоритмов отбора признаков входных данных для повышения точности предложенных методов. Для отбора призна ков в методе выбора числа процессоров для решателя предложено использо вать метод f-score4. В методе выбора и настройки параметров решателя отбор признаков применяется при построении функции сложности C. Предложен подход на основе алгоритма частичного сингулярного разложения (truncated SVD) и последующего выбора числа признаков для достижения наибольшей точности построения функции сложности. В результате применения указан ных алгоритмов отбора признаков на рассматриваемых выборках данных по лучено повышение точности методов не менее чем на 4%, время построения методов сократилось в среднем на 17%.

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

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

В разделе 3.1 представлены результаты применения предложенных мето дов для набора прикладных задач на основе решения разреженных СЛАУ.

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

В разделе 3.2 описывается задача моделирования сетей распределения пи тания СБИС. Проблема моделирования заключается в определении потенци алов в узлах многоуровневой металлической структуры, которая подключает активные устройства интегральной схемы к источнику питания [6].Характер ной особенностью данной задачи является необходимость моделирования се тей питания с числом элементов порядка 105 108 различных конфигураций и размеров, что требует использования МВС и делает актуальным приме нение предложеных методов для сокращения времени моделирования. Для Y.W. Chen, C.J. Lin. Combining SVMs with various feature selection strategies // Studies In Fuzziness And Soft Computing. 2006. Vol. 207. P. 315– T. Davies. University of Florida sparse matrix collection // NA digest. 1997. Vol. 97, N. 23, P. 7.

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

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

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

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

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

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

В заключении перечислены основные результаты диссертационной ра n*= * n = фактическое ускорение фактическое ускорение прогнозируемое ускорение прогнозируемое ускорение линейное ускорение линейное ускорение ускорение ускорение 64 128 256 32 64 128 256 512 число ядер число ядер (a) (b) Рис. 4: Результаты применения метода выбора числа процессоров для одного шага пере ходного процесса на МВС Blue Gene/P (a) и МВС Чебышев (b). Для МВС BlueGene/P рассматривается модель сети питания c10000, режим запуска программ SMP, построение метода на выборке решения моделей сетей c9000, c6000, c4000, c3000. Для МВС Чебышев рассматривается модель сети питания b9000, построение метода на выборке решения мо делей сетей b6000, b4000, b3000. n обозначает полученное методом число процессоров для решения задачи.

Таблица 1: Результаты применения метода выбора и настройки параметров решателя на Blue Gene/P для n=512 ядер, модель c10000;

обучение на статистике решения моделей c3000, c4000, c6000, c9000 для одного шага моделирования переходного процесса Niter Ppredict tf act tdef ault tmethod teconomy 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ч Обозначения: Niter –кол-во итераций генетического алгоритма, Ppredict –значение функции сложности для полученного методом решателя S, сек. * Мб tf act –фактическое время моделирования для найденного решателя (в скобках указан про цент улучшения по сравнению с решателем по умолчанию), сек.

tdef ault –время моделирования для решателя, используемого по умолчанию, сек.

talgorithm –время выполнения метода, сек.

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

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

обучение на статистике решения моделей b3000, b4000, b6000, b9000 для одного шага моделирования переходного процесса Niter Ppredict tf act tdef ault tmethod teconomy 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ч Обозначения: Niter –кол-во итераций генетического алгоритма, Ppredict –значение функции сложности для полученного методом решателя S, сек. * Мб tf act –фактическое время моделирования для найденного решателя (в скобках указан про цент улучшения по сравнению с решателем по умолчанию), сек.

tdef ault –время моделирования для решателя, используемого по умолчанию, сек.

tmethod –время выполнения метода, сек.

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

боты.

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

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



 

Похожие работы:





 
2013 www.netess.ru - «Бесплатная библиотека авторефератов кандидатских и докторских диссертаций»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.