Содержание к диссертации
Введение
Глава 1 Проблема архитектурно-зависимой декомпозиции графа данных программы и ее место в области высокопроизводительных вычислений 18
1.1. Проблемы управления данными параллельной программы в высокопроизводительной вычислительной среде 18
1.2. Содержательная постановка задачи архитектурно-зависимой декомпозиции
1.2.1. Граф данных параллельной программы 22
1.2.2. Архитектура вычислительной сети 25
1.2.3. Проблема архитектурно-зависимой декомпозиции графа данных программы 28
1.3. Задачи и методы их решения в проблематике повышения эффективности высокопроизводительных вычислений 29
1.3.1. Задачи, связанные с повышением эффективности высокопроизводительных вычислений 29
1.3.2. Методы решения задач, связанных с повышением эффективности высокопроизводительных вычислений 31
1.4. Итоги главы 1 43
Глава 2 Формализация задачи архитектурно-зависимой декомпозиции 44
2.1. Обобщенная математическая модель архитектурно-зависимой декомпозиции 44
2.1.1. Графовая модель исходной структуры данных параллельной программы 44
2.1.2. Гиперграфовая модель структуры вычислительной сети 45
2.1.3. Матричное представление структуры вычислительной сети 48
2.1.4. Пространство решений задачи архитектурно-зависимой декомпозиции 48
2.2. Критерии задачи архитектурно-зависимой декомпозиции 50
2.2.1. Балансировка загрузки вычислительных ресурсов 50
2.2.2. Минимизация загрузки коммуникационной среды 51
2.3. Частные случаи задачи архитектурно-зависимой декомпозиции 52
2.3.1. Задачи разбиения графа 52
2.3.2. Задачи о назначениях 53
2.4. Итоги главы 2 56
Глава 3 Многоуровневые методы архитектурно-зависимой декомпозиции 57
3.1. Многоуровневая схема решения задачи АЗД 57
3.2. Метод редукции исходной задачи к квадратичной задаче о назначениях
3.2.1. Группировка элементов задачи методом решения задачи разбиение графа 60
3.2.2. Технология перехода к квадратичной задачи о назначениях 61
3.2.3. Многоуровневый метод снижения размерности квадратичной задачи о назначениях 62
3.3. Алгоритмы решения квадратичной задачи о назначениях 63
3.3.1. Алгоритм ветвей и границ 64
3.3.2. Гибридный генетический алгоритм на порядковом представлении решений 71
3.3.3. Улучшающий гибридный генетический алгоритм на бинарном представлении решений.. 77
3.4. Восстановление решений задач архитектурно-зависимой декомпозиции 83
3.4.1. Проекция решения редуцированной задачи в пространство решений исходной задачи 83
3.4.2. Уточнение решения методом локальной оптимизации 85
3.5. Итоги главы 3 88
Глава 4 Программная реализация, её апробация и эксплуатация 90
4.1. Аспекты программной реализации системы архитектурно-зависимой декомпозиции 90
4.1.1. Программная модель исходных данных задачи 90
4.1.2. Основные программные интерфейсы 92
4.1.3. Примеры использования системы для решения задач архитектурно-зависимой декомпозиции 94
4.2. Тестовые задачи и вычислительный эксперимент 95
4.2.1. Тестовые задачи 95
4.2.1.1. Тестовые исходные данные в терминах квадратичной задачи о назначениях 96
4.2.1.2. Тестовые исходные данные для задачи архитектурно-зависимой декомпозиции 96
4.2.2. Вычислительный эксперимент 100
4.2.2.1. Сравнение алгоритмов решения редуцированных задач 100
4.2.2.2. Настройка алгоритмов и выбор режимов работы 114
4.2.2.3. Апробация многоуровневого алгоритма 121
4.2.2.4. Выводы 123
4.3. Особенности эксплуатации программы архитектурно-зависимой декомпозиции 123
4.3.1. Проблема эффективного извлечения исходных данных 123
4.3.2. Иерархическое представление архитектуры вычислительной системы 125
4.4. Итоги главы 4 127
Заключение 127
Литература 129
- Граф данных параллельной программы
- Матричное представление структуры вычислительной сети
- Многоуровневый метод снижения размерности квадратичной задачи о назначениях
- Тестовые исходные данные для задачи архитектурно-зависимой декомпозиции
Введение к работе
Актуальность темы. Современные вычислительные системы – это разделяемый ресурс, на котором одновременно могут выполняться много процессов, конкурирующих за процессорное время, память, коммуникации. Для их эффективного использования требуется решать разнообразные проблемы, в том числе связанные с планированием и запуском заданий, назначением программ и распределением данных по узлам вычислительной системы. Выполняемые в высокопроизводительной среде процессы могут быть как независимые, так и взаимодействующие. В случае независимых процессов важно добиться сбалансированной работы процессоров, в то же время для взаимодействующих процессов помимо сбалансированности значимость приобретают межпроцессорные коммуникации, издержки на которые необходимо снижать. В ряде случаев, когда распараллеливание программы выполнено заранее и изменению не подлежит, добиться значимого снижения потерь от простоя процессоров и коммуникационных издержек можно за счет перераспределения графа данных параллельной программы по узлам физической топологии участка вычислительной сети, в рамках которого исполнятся параллельный код. В результате возникает проблема отображения
графа данн х параллельной программ на физическу топологи выделенного участка вычислительной сети с целью наибольшего сокращения
ы
с времени ее работы с учетом издер ек на поиск и реализаци такого отображения. Подобные проблемы будем называть задачами архитектурно-зависимой декомпозиции (АЗД).
. есмотря на NP-трудность задачи АЗД и многих ее частных случаев
в, в
В работе рассмотрена обобщенная постановка задачи и интересные с практической точки зрения ее частные случаи, которые формулируются в терминах квадратичной задачи о назначениях и задачи сбалансированного разбиения графа.
следует отметить определенн е успехи в развитии точн х методов, особенно
аспекте их адаптации для в сокопроизводительн х в числительн х систем. На практике размеры графов данных параллельных задач достигают 106-109 вершин.
i, в
а, в
P-трудность и размеры прикладных задач ЗД накладыва т ограничения на практическое применение точных и даже ряда приближенных методов. Это явилось стимулом развития эвристических алгоритмов. S. Chen и M.M. Eshaghian предлагают конструктивный рекурсивный алгоритм решения задачи АЗД. B. Hendrickson и T. Kolda используют спектральные методы для решения задачи декомпозиции графа. Большой интерес вызывают итерационные алгоритмы. Примером могут послужить работы S. Bokhari J.K.Aggarval, S.Y. Lee. Для решения квадратичной задачи о назначениях работах C.A.S. Oliveira, P.M. Pardalos, M.G.C. Resende, Y. Li, T. Sttzle, J.Skorin-Kapov, E. Taillard, T.P. Gevezes, L.S. Pitsoulis, I.M. Whittley, G.D. Smith, M.Czapiski предложен ряд алгоритмов, которые построены на последовательном улучшении начального решения. Главной проблемой итерационных алгоритмов является отсутствие возможности преодоления локальных экстремумов. Решение этой проблемы состоит в развитии метаэвристик. Среди них можно выделить методы имитации отжига алгоритмы, работающие с группами решений и имитирующие процессы биологических системах, и др. В работах M.R. Wilhelm, T.L. Ward, J.C. Wang, D.T. Connolly, M. Hammami, K. Ghdira, B. Robi, J. ilc, А.Б. Клименко, Р.В.Троценко предлагаются алгоритмы, основанные на методе имитации отжига для решения квадратичной задачи о назначениях, задачи декомпозиции графа, задачи планирования параллельных процессов, задачи назначения параллельных процессов на вычислители, задачи оптимизации ресурсов и планирования вычислений. Среди алгоритмов, имитирующих процессы в биологических системах, наиболее известными являются муравьиные и пчелиные алгоритмы. Эти алгоритмы представлены в работах V. Maniezzo, A.Colorni, L.M. Gambardella, E.G. Talbi, O. Roux, C. Fonlupt, D. Robillard, M.Mirzazadeha, G.H. Shirdelb, B. Masoumic, S. Tsutsui, L. Liu для квадратичной задачи о назначениях, в работах M.S. Soliman, G. Tan, A.E. Langham, P.W. Grant, J.D. McCaffrey для задачи декомпозиции графа, в работах O. Sammoud, C.Solnon, K. Ghdira, S. Fidanova, M. Durchova, T. Davidovi, M. elmi, D.Teodorovi, D. Ramljak, S.S. Kim, J.H. Byeon, H. Liu для задачи отображения графов и задачи планирования параллельных процессов. В работе Бершадского А.М. для решения задачи балансировки нагрузки предложена неклассическая
прогностическая модель, основанная на синергетическом подходе и использующая фрактальные методы описания динамики нагрузки, и синтетический обобщенный подход к составлению прогнозов изменения нагрузки. Большой класс составляют эволюционно-генетические алгоритмы, представленные в работах H. Mhlenbein, C. Fleurent, J.A. Ferland, A. Misevicius, U. Tosuna, T. Dokeroglua, A. Cosara, J. Hines, J.T. Thorpe, F.C. Harris, K.B.Winiecki, R.K. Ahuja, J.B. Orlin, A. Tiwari, L.Y. Tseng, S.C. Liang, T.N.Bui, B.R. Moon, P. Neuhaus, T. Chockalingam, S. Arunkumar. В нашей стране эти алгоритмы развивали Д.И. Батищев, В.В. Курейчик, В.М. Курейчик, А.В.Пантелеев и др. Многие прикладные задачи характеризуются большими размерами, что затрудняет использование даже эвристических методов их решения. На большеразмерных задачах декомпозиции и архитектурно-зависимой декомпозиции графа хорошо показали себя многоуровневые алгоритмы, которые сводят исходную задачу к задаче меньшей размерности или меньшей сложности, когда становится возможным применить более качественные алгоритмы поиска решения, находят решение упрощенной задачи и восстанавливают его к решению исходной задачи, применяя локальную оптимизацию (ЛО). Впервые идея многоуровневости была предложена B.Hendrickson, кроме него значительный вклад в развитие многоуровневой оптимизации внесли R. Leland, G. Karypis, V. Kumar, C. Walshaw. В нашей стране это направление развивали М.В. Якобовский, Н.В. Старостин, А.В.Филимонов, А.А. Пазников, М.Г. Курносов, М.С. Куприянов, А.А. Гуленок и другие ученые. Существует ряд коммерческих программных библиотек, решающих задачу декомпозиции графа многоуровневыми методами. Самые известные Metis, Chaco, Jostle и Scotch. Многие проекты сконцентрированы на решении классических задач декомпозиции графов, в то же время для практических целей интерес представляют продукты, учитывающие специфику конкретных предметных областей.
В этом аспекте следует отметить, что попытка учета ключевых характеристик и особенностей рассматриваемой предметной области, таких как топология и коммуникационные показатели сети, производительности процессоров, объемы информационных зависимостей в графе данных параллельной программы, вычислительные издержки в процессе исполнения
кода, приводят к о утимому усло нени не только математической модели и алгоритма решения задачи, но и к технологиям сбора и актуализации данных для повышения эффективности высокопроизводительных расчетов.
Научной проблемой, на решение которой направлено диссертационное исследование, является проблема разработки многоуровневых методов решения задач АЗД в области высокопроизводительных вычислений.
Целью работы является создание прикладных методов построения многоуровневых средств решения большеразмерных задач АЗД, возникающих в области высокопроизводительных вычислений.
В соответствии с целью работы определены следующие задачи:
ЗД; средств
Разработка алгоритмических средств и реализация программных инструментов, для решения задач АЗД;
Апробация разработанных решений в рамках современных высокопроизводительных вычислительных систем.
Объектом исследования являются большеразмерные оптимизационные
и
в
Построение и исследование гиперграфовой модели АЗД, учитывающей ключевые особенности предметной области, постановка оптимизационных задач, направленных на сокращение вычислительных издержек в высокопроизводительной среде при выполнении параллельных расчетов;
Разработка методологии и структуры формирования данных предметной области в терминах модели АЗД;
задачи на графах в области в сокопроизводительных параллельн х систем.
Предметом исследования являются большеразмерные задачи АЗД, возникающие в области высокопроизводительных параллельных систем; методология, методы, алгоритмы, обеспечивающие решение рассматриваемых задач.
Достоверность и обоснованность результатов диссертационной работы обеспечивается строгими математическими доказательствами выдвигаемых
положений, проведением вычислительных экспериментов на тестах производительности (бенчмарках) и сравнением с известными аналогами.
Научная новизна.
1. Математическая модель АЗД, в рамках которой поставлены различные оптимизационные задачи на гиперграфах. Предложена гиперграфовая модель вычислительной системы, позволяющая наиболее точно отразить топологию и коммуникационные характеристики вычислительной сети. Предложено ее матричное представление. (Соответствует областям исследований: 2, 3 паспорта специальности);
2. етодология представления данн х предметной области в
терминах модели АЗД. В отличие от известных представлений структуры
вычислительной сети в виде взвешенных графов, предложено иерархическое
описание структуры вычислительной сети, что позволяет компактно и в
достаточной степени детализации описать вычислительную инфраструктуру.
(Соответствует областям исследований: 1, 4 паспорта специальности);
3. Алгоритмические средства решения задач АЗД: предложены
многоуровневые методы (метод редукции графа данных программы и метод
редукции графа топологии вычислительной системы) и многоуровневый
алгоритм решения общей задачи АЗД, которые на разных уровнях иерархии
обеспечивают возможность использовать точных, приближенных и
эвристических алгоритмов; алгоритмы, основанные на методе ветвей и границ;
генетические алгоритмы, в том числе улучшающий генетический алгоритм на
бинарном представлении; создан итерационный алгоритм локальной
оптимизации. (Соответствует областям исследований: 5, 9 паспорта
специальности).
сновн е поло ения, в носим е на за иту.
1. Гиперграфовая модель АЗД, в рамках которой ставятся оптимизационные задачи распределения графа данных параллельной программы по процессорам высокопроизводительной вычислительной системы;
2. етодология извлечения и представления данных предметной
области (структуры вычислительной сети) в терминах модели АЗД;
-
Многоуровневые методы решения оптимизационных задач АЗД, а также генетические алгоритмы решения квадратичной задачи о назначениях, точный и приближенный алгоритмы решения квадратичной задачи о назначениях, алгоритм локальной оптимизации (ЛО) полученного решения задачи АЗД, синтезированные в общий многоуровневый алгоритм поиска решений задачи;
-
Программная библиотека разработанных алгоритмов решения задач АЗД, а также форматы представления исходных данных задачи.
Практическая значимость. Предложен подход, который может быть использован в системах планирования и управления ресурсами высокопроизводительных вычислительных систем.
Результаты работы используются в учебном процессе подготовки бакалавров и магистров по направлению "Прикладная информатика" в рамках дисциплин «Теория систем и системный анализ» и «Методы и технологии суперкомпьютерных вычислений» кафедры Информатики и автоматизации научных исследований в Нижегородском государственном университете им. Н.И. Лобачевского института информационных технологий, математики и механики.
Результаты диссертационной работы апробированы в РФЯЦ-ВНИИЭФ (справка об использовании результатов диссертационной работы). Получено свидетельство о государственной регистрации программы для ЭВМ №2017616817.
сновное теоретическое и практическое содержание диссертации опубликовано в 16 печатных работах, в том числе 4 статьях, 3 из которых изданиях, рекомендованных ВАК РФ, 1 свидетельство о государственной регистрации программы для ЭВМ.
и в
Публикация результатов.
трации программ для ЭВ .
Апробация результатов работы.
о
сновные результат диссертационной работы докладывались и обсуждались на следующих научно-технических семинарах и конференциях: V,
I Всероссийская студенческая научно-техническая конференция " рикладная информатика и математическое моделирование" (Москва, Московский университет печати им.И.Федорова, 2011, 2012); XII Всероссийская конференция "Высокопроизводительные параллельные вычисления на кластерных системах" (Нижний Новгород, ННГУ им. Н.И.Лобачевского, 2012); XIX, XX, XXI Международная научно-техническая конференция «Информационные системы и технологии» (Нижний Новгород, НГТУ им. Р.Е. Алексеева, 2013, 2014, 2015); Международная конференция “Numerical Computations: Theory and Algorithms” (Италия, Фалерна, 2013); XII Международная научно-техническая конференция «Будущее технической науки» (Нижний Новгород, НГТУ им. Р.Е. Алексеева 2013); Всероссийские чтения-конкурс памяти нижегородских ученых (Нижний Новгород, ННГУ им. Н.И.Лобачевского, 2013); Семинар «Методы суперкомпьютерного моделирования» (Таруса, база «Интеркосмос» ИКИ РАН, 2014).
Свидетельство о государственной регистрации программ для ЭВМ.
Получено свидетельство о государственной регистрации программы для ЭВМ №2017616817.
Личный вклад автора заключается в разработке основных теоретических положений, выносимых на защиту. Автор принимал непосредственное участие в постановке задач и разработке алгоритмов. Автором решались задачи проведения экспериментов и разработки компонент программного обеспечения. Все представленные в диссертации положения, выносимые на защиту, получены лично автором, либо при его непосредственном участии.
Структура и объем работы. Диссертационная работа состоит из введения, четырех глав, заключения из списка использованной литературы из 188 наименований, а также приложения. Объем диссертации составляет 128 страниц машинописного текста, общий объём диссертации составляет 167 страниц.
Граф данных параллельной программы
Исходными данными рассматриваемой задачи являются граф данных параллельной программы и граф вычислительной сети (участка вычислительной сети, выделенного для выполнения программы). Граф данных параллельной программы описывает структуру зависимостей между элементами исходных данных. При этом каждый элемент моделируется вершиной, которая характеризуется числовой оценкой вычислительной сложности расчета, связанного с этими данными. Расчётные зависимости в данных моделируются ребрами графа с числовой оценкой объёма данных, которые требуется передать в процессе коммуникационной пересылки.
Вычислительная сеть характеризуется количеством вычислителей, их вычислительной мощностью, а также структурой коммуникационной топологии. Под структурой коммуникационной топологии вычислительной сети понимается расположение коммуникаторов, физических связей между коммуникаторами и вычислителями, коммуникационных шин между вычислителями, а также коммуникационные характеристики коммуникаторов и шин (скорость передачи данных).
Особенностями исходных данных являются большой размер параллельной программы (количество вершин графа данных, как уже отмечалось, достигает 106-109), необходимость распределенного хранения данных программы, разреженный неструктурированный характер коммуникаций между параллельными частями программы.
В задаче АЗД требуется так распределить все вершины графа данных по вычислителям так, чтобы время, затрачиваемое параллельной программой на межпроцессорные коммуникации и простой вычислителей, было минимально. Коммуникационное требование как правило формулируется в виде критерия, минимизирующего суммарную стоимость коммуникаций (аддитивный критерий) или максимальную стоимость коммуникаций (минимаксный критерий). Требование равномерной загрузки вычислителей формулируется с учетом разной мощности вычислителей и разной сложности расчета, которая зависит от объема и вида данных программы. Очевидно, что далеко не всегда возможно сбалансированно разделить параллельные части программы по вычислителям. Простым примером может послужить программа, состоящая из двух параллельных частей разной вычислительной сложности и вычислительная система, состоящая из двух вычислителей одинаковой мощности. Для практических целей условие балансировки может быть сформулировано как в виде ограничения с заранее заданным допустимым отклонением от идеально сбалансированного разбиения, так и виде критерия, который направлен на минимизацию разбалансированности.
Параллельная программа представляет собой множество взаимодействующих параллельных процессов. Программа осуществляет управление работой процессов, организует обмен данными между ними. Исходные данные задач, рассматриваемых в работе, являются настолько объемными, что не дает возможности хранить весь набор данных на каждом вычислителе. Соответственно, исходные данные параллельной программы являются декомпозированными, и каждый вычислитель хранит свой набор данных. Такая реализация выполнения параллельной программы называется параллельным алгоритмом на распределенной модели данных. Очевидно, что от структуры, объема, способа декомпозиции данных, а также от производительности вычислителя, на котором происходит расчет этих данных, зависит время их обработки. Таким образом, для эффективного использования параллельной вычислительной системы необходимо осуществлять сбалансированную декомпозицию данных с учетом производительности вычислителей. Между исходными данными параллельной программы существуют зависимости (для расчета одних данных нужно знать результат расчета других), что приводит к необходимости коммуникаций в процессе параллельного расчета. Существуют синхронная и асинхронная модели организации коммуникаций. При синхронной модели происходит выполнение всех процессов до необходимой коммуникации (выполнение расчетов), ожидание процессами друг друга1 и одновременная (по возможности) пересылка и прием информации2. Тогда время выполнения всей программы можно разделить на две основные части: время выполнения расчета и время коммуникаций. В данной модели время выполнения расчета определяется временем самого длинного расчета, поскольку процессы ожидают окончания расчета друг друга. Соответственно, уменьшения этого времени можно добиться посредством сбалансированной декомпозиции данных и загрузки вычислителей. Общее время коммуникаций трудно точно рассчитать, поскольку сложно заранее предсказать, какие коммуникации будут происходить последовательно, какие параллельно, возникновение коллизий, маршруты передачи данных. Время коммуникаций можно попытаться уменьшить, назначив интенсивно коммуницирующие ветви программы на топологически «близкие» процессоры.
При асинхронной модели коммуникации между ветвями программы осуществляются по мере возникновения необходимости, во время расчетов других веток программы, не участвующих в данной коммуникации. Поэтому четкого разделения общего времени выполнения программы на две части, как при синхронной модели, нет. Однако, очевидно, что для сокращения времени работы программы целесообразно пользоваться приемами, описанными выше, поскольку и в данном случае несбалансированная загрузка вычислителей приведет к ожиданию завершения самого долгого процесса и простоем остальных вычислителей, а длинные коммуникации приостановят выполнение расчета на коммуницирующих вычислителях на более долгое время.
Матричное представление структуры вычислительной сети
Поскольку большинство современных параллельных вычислительных систем имеют гибридную архитектуру и многоуровневую организацию, то под термином вычислитель будем понимать неделимое физическое устройство, на котором происходит обработка части исходных данных параллельной программы (одноядерный процессор, ядро многоядерного процессора, ядро графического ускорителя).
В основу математической модели вычислительной системы предлагается положить взвешенный гиперграф H(Y,A,p,w), где Y = {у1,...,ук}- множество вершин, моделирующих вычислители системы; А 2- множество гиперребер, моделирующих коммуникационные связи между вычислителями (в некоторых случаях коммуникационные каналы представляют собой программно-аппаратные реализации разделяемых шин, в рамках которых осуществляется передача данных между вычислителями (примером может послужить архитектура связей ядер многоядерного процессора). В таких случаях множество вершин гиперграфа, соответствующих этим вычислителям, образуют гиперребро); веса вершин p:Y —» (0,1] - моделируют относительную производительность вычислителей; веса гиперребер w:A N- определяют скорость пересылки данных (в общем случае может быть вектор характеристик коммуникационной среды (способ передачи информации (сообщениями или пакетами), время подготовки информации к отправке, скорость передачи единицы информации, время передачи служебной информации и т.п.)).
Структура вычислительной сети подробно отражается в гиперграфовой модели. Из данной модели можно получить информацию о производительности вычислителей, о структуре их соединения, о расположении и характеристиках коммуникационных устройств, о методах передачи данных и алгоритмах маршрутизации, используемых коммуникационными устройствами, о физическом расположении устройств и т.п. В прикладной задаче архитектурно-зависимой декомпозиции требуется информация о «стоимости» (скорость, время) передачи данных между вычислителями. Такая информация в явном виде не содержится в гиперграфовой модели, ее необходимо рассчитывать. Стоимость передачи данных между парой вычислителей зависит от методов передачи данных, используемых коммуникационными устройствами, с помощью которых будет транслироваться информация, от характеристик этих устройств, от длины маршрута, что в свою очередь зависит от маршрута, найденного алгоритмом маршрутизации.
Среди алгоритмов маршрутизации можно выделить оптимальные алгоритмы, определяющие кратчайшие пути передачи данных, и неоптимальные алгоритмы маршрутизации, которые в свою очередь делятся на детерминированные и адаптивные методы выбора маршрутов [25].
Выделим основные параметры, от которых зависит время передачи данных [25]: время начальной подготовки данных для передачи tн, время передачи служебных данных tс между двумя соседними процессорами, время передачи одной единицы данных по одному каналу передачи данных tк. Выделяют два основных способа передачи данных [120]. Первый ориентирован на передачу сообщений как неделимых блоков информации. Время пересылки данных tпд в данном случае для передачи сообщения размером m по маршруту длиной l определяется выражением tпд = tн + (mtк + tс)l (2.1) При достаточно длинных сообщениях временем передачи служебных данных можно пренебречь и выражение для времени передачи данных может быть записано в более простом виде tпд = tн + mtкl (2.2) Второй способ коммуникации основывается на представлении пересылаемых сообщений в виде блоков информации меньшего размера (пакетов). Время пересылки данных при использовании метода передачи пакетов будет определяться выражением tпд = tн + mtк + tсl (2.3)
По полной гиперграфовой модели вычислительной системы теоретически можно точно вычислить время t(i, j, m) передачи данных объемом m между вычислителями i и j. Однако, на практике нередко оказывается очень сложно гарантировано рассчитать маршрут передачи данных, совпадающий с маршрутом, выбранным маршрутизатором, учесть коллизии, возникающие во время передачи, задержки на сетевых устройствах. Поэтому приходится пользоваться оценками искомого времени, рассчитывая кратчайший маршрут передачи данных без учета коллизий и отказываясь от некоторых характеристик вычислительной сети. Но и при данных допущениях будет необходимо каждый раз пересчитывать время передачи данных между одной и той же парой вычислителей для данных разного объема, поскольку функцию зависимости времени передачи от объема данных на практике редко оказывается возможным описать некоторой формулой.
Поэтому предлагается допустить, что время передачи данных не сильно изменяется при небольшом изменении объема данных. Будем использовать интерполяцию функции t, вычислив ее значения при некоторых значениях параметра m. Если неизвестна детальная информация о топологии или коммуникационных характеристиках устройств вычислительной системы, то целесообразность использования аналитической формы функции расчета времени передачи данных вызывает сомнения. В таком случае предлагается альтернативный способ, основанный на вычислении значений функции опытным путем с помощью замеров времени передачи данных между парой вычислителей, и построением аппроксимации искомой функции. Обратим внимание, что функции (2.1), (2.2), (2.3) имеют линейный характер. Конечно, на практике на время передачи данных оказывают влияние разного рода факторы и процессы ВС, но тем не менее, можно принять, что зависимость времени передачи данных от их объема является в основном линейной. Следует также отметить, что в задаче АЗД важно оценить относительные издержки на коммуникации, а не их абсолютные значения. Исходя из вышесказанного, предлагается использовать линейную интерполяцию (аппроксимацию) функции t. Тогда для каждой пары вычислителей необходимо хранить всего один коэффициент наклона полученной прямой sih и время передачи данных объема т между этими вычислителями можно вычислить по формуле ґ(7, у, т) = stjm.
Предлагается матричное представление гиперграфовой модели вычислительной системы, основанное на линейной интерполяции (аппроксимации) функции времени пересылки данных между парой процессоров. В основу матричной модели вычислительной системы на к вычислителях положена матрица = ( .)м. Элементы матрицы st N,i,j = 1,k являются коэффициентами линейной аппроксимации (интерполяции) функции зависимости временных затрат на пересылку от объема пересылаемых данных. Удобство описанной модели обосновывается низкими издержками, связанными с расчетом временных затрат на пересылки данных определенного объема между парой вычислителей.
Многоуровневый метод снижения размерности квадратичной задачи о назначениях
Цикл работы GA (строка 4) не прекращается до тех пор, пока не наступят условия останова. В основу функции ga_stop() положена тривиальная логика, ограничивающая число итераций алгоритма. Цикл (строки 4 – 11) осуществляет традиционный генетический поиск. Процедура evaluate(p) (строка 6) оценивает функцию приспособленности особей. Процедура breeding() (строка 7) выполняет отбор родительских пар. В экспериментах использовалась стратегия панмиксия – право сформировать родительскую пару имеют все особи популяции с равной вероятностью. Процедура crossover() (строка 8) рекомбинацией родительских строк получает две новые строки потомков. Процедура mutation() (строка 9) генерирует случайные изменения в строках потомков. Все новые решения оцениваются, и в процедуре select() (строка 10) происходит замена худших решений из текущего поколения на новые решения, полученные в рамках текущей итерации. Лучшее найденное решение возвращается как результат работы алгоритма (строка 13).
Итоговая вычислительная сложность предлагаемого генетического алгоритма составляет O(n2) за счет операции подсчета критерия, кроссовера и ЛО. В работе предлагается генетический алгоритм, реализующий итерационный поиск решения задачи. Работа итерационных алгоритмов основана на исследовании локальной окрестности текущего решения, поиска лучшего решения в данной окрестности и повторения данной процедуры для найденного решения [168]. Существуют вариации данного метода с несколькими начальными решениями, с элементами рандомизации для расширения пространства поиска [144, 126], с запретами неперспективных зон пространства поиска [159, 171, 81, 158] и т.д.
Преимуществом таких алгоритмов является быстрая сходимость. Однако, это же свойство может быть и недостатком, поскольку алгоритм может быстро "скатиться" в локальный оптимум и не сможет оттуда выйти. Эта особенность существенно ограничивает возможность исследовать все пространство поиска и отыскать глобальный оптимум.
Предлагается алгоритм, который на каждой итерации генетическим поиском исследует окрестность текущего решения КЗН. Особями генетического алгоритма являются бинарные строки, кодирующие переход от текущего решения КЗН к новому решению. Таким образом, окрестность текущего решения определяется особями текущего поколения генетического алгоритма, из чего следует, что окрестность каждого следующего решения строится по-разному, и решения, попавшие в такую окрестность, могут достаточно сильно отличаться от текущего решения, что позволяет шире охватить пространство поиска и избежать преждевременного скатывания в локальный оптимум. Алгоритм, основанный на подобной стратегии, будем называть улучшающим генетическим алгоритмом (УГА).
На рисунке 3.9 демонстрируется схема исследования пространства поиска УГА. Когда УГА стартует с некоторого начального решения (см. a), то внутренний цикл осуществляет генетический поиск в окрестности начального решения. Результат работы внутреннего цикла УГА – это новый рекорд, который принимается новым начальным решением (см. b), при этом решения текущего поколения отображаются в новую окрестность. Внутренний цикл УГА исследует окрестность нового решения и находит новый рекорд (см. с), который является кандидатом на новое начальное решение. Таким образом, УГА перебирает одну окрестность за другой, пока не наступят условия останова.
Рассмотрим подробнее схему кодирования решений УГА. Решение исходной задачи кодируется перестановкой. Особи в УГА представляют собой бинарные строки. Длина бинарных строк совпадает с длиной перестановки, кодирующей решение исходной задачи. Каждая бинарная строка кодирует схему перехода из текущего решения исходной задачи (перестановки) в новое решение, тем самым набор бинарных строк текущего поколения УГА определяет локальную окрестность исходного решения, в которой будет происходить поиск.
Опишем процесс перехода в новое решение по схеме, закодированной в бинарной строке. Если некоторый элемент бинарной строки равен 1, это означает, что соответствующий элемент перестановки, кодирующей текущее решение КЗН, будет изменен согласно принципу "жадности". Будем называть такие элементы изменяемыми. Для каждого изменяемого элемента будет произведен перебор всевозможных парных обменов данного элемента перестановки с остальными и выбран лучший обмен с точки зрения критерия КЗН. Когда данная процедура будет произведена со всеми изменяемыми элементами перестановки, будет получено новое решение исследуемой окрестности. Очевидно, что элементы перестановки, которым соответствует 0 в бинарной строке, тоже могут быть переставлены, если обмен с этим элементом окажется выгодным для одного из изменяемых элементов. На рисунке 3.10 представлен пример получения двух новых решений локальной окрестности из одного базового решения с помощью двух бинарных строк. Стрелками показаны наиболее выгодные обмены для каждой изменяемой позиции перестановки.
Функцией приспособленности особей УГА (бинарных строк) является значение критерия КЗН на перестановке, полученной путем перехода из текущего решения по схеме, закодированной в оцениваемой особи. Очевидно, что одна и та же бинарная строка будет иметь разные значения функции приспособленности при разных базовых решениях (перестановках). Отсюда следует, что необходимо пересчитывать функции приспособленности всех особей УГА при переходе к новой итерации, поскольку на данном этапе происходит смена базового решения.
Стартовое поколение УГА генерируется случайным образом, что позволяет шире охватить пространство поиска. В качестве схемы формирования родительских пар также была выбрана панмиксия. Для репродукции решений используется одноточечный кроссовер для бинарных строк [20], который в случайно выбранной точке осуществляет разрыв и перекрёстную склейку родительских строк. Вычислительная сложность описанного кроссовера составляет O(n).
Мутация [20] вносит случайные изменения в бинарные строки, кодирующие полученных потомков. В ходе мутации случайно выбирается некоторое заранее заданное число позиций бинарной строки, и в значения этих позиций случайным образом записывается значение 0 или
В ходе работы улучшающего генетического алгоритма к решениям, получаемым из базовой перестановки по схеме, закодированной в бинарных строках, применяется ЛО, описанная в пункте 3.3.2. Отбор особей для следующего поколения осуществляется по их функции приспособленности, определенное количество лучших особей переходит в следующее поколение. Вычислительная сложность функции оценки приспособленности особей составляет O(n2), поскольку она представляет собой подсчет критерия КЗН. Условием останова предлагаемого алгоритма является ограничение количества поколений, сгенерированных в ходе решения задачи, а также превышения заданного параметра стагнации (количество итераций УГА, в которых не происходит изменения рекорда).
Тестовые исходные данные для задачи архитектурно-зависимой декомпозиции
Приближенный алгоритм тестировался на 50 примерах, ему удалось достичь 32 известных рекорда.
Следует отметить, что как алгоритм ветвей и границ, так и приближенный алгоритм требуют много временных ресурсов. Следовательно, для их применения необходимо значительно редуцировать исходную задачу (после редукции размер КЗН не должен превышать 20).
Для решения прикладных КЗН были предложены гибридные схемы на основе генетических алгоритмов: гибридный генетический алгоритм на порядковом представлении решений и гибридный улучшающий генетический алгоритм на бинарном представлении решений.
Для тестирования и сравнения предложенных в работе генетических алгоритмов, был проведен ряд вычислительных экспериментов. Целью первой серии вычислительных экспериментов было выявление основных параметров алгоритмов, влияющих на качество их работы. Для генетического алгоритма на порядковом представлении основными параметрами являются: количество поколений, размер популяции и количество итераций ЛО. Для улучшающего генетического алгоритма основными параметрами являются: количество итераций алгоритма, количество поколений, размер популяции и количество итераций ЛО, глубина ЛО. Следует отметить, что одним из важных параметров генетического алгоритма является выбранный кроссовер. В работе в предложенном гибридном генетическом алгоритме на порядковом представлении используется оригинальный кроссовер, описанный в главе 3, а для гибридного улучшающего генетического алгоритма на бинарном представлении использовался классический одноточечный кроссовер. Поскольку тестирование алгоритмов производится на широко известных тестовых примерах, на которых уже тестировались другие генетические алгоритмы с альтернативными операторами кроссовера [47], то сравнение используемых кроссоверов с другими производится косвенным образом при сравнении получаемых решений тестовых задач.
В качестве параметров генетических алгоритмов были выбраны: размер популяции 10, количество потомков в каждом поколении 5, количество мутантов 5, вероятность мутации 10%, количество итераций ЛО 10. Количество поколений, необходимых для работы генетического алгоритма определяется скоростью его сходимости, что напрямую влияет на разнообразие решений в каждом поколении. На графике (рис. 4.7) представлено разнообразие решений в поколениях для типового примера КЗН. По горизонтали указаны номера поколений, по вертикали количество различных решений в поколениях. Подобная динамика обеспечивает алгоритму 50 – 60 итераций эффективного поиска.
Для улучшающего генетического алгоритма важным параметром, влияющим на скорость и качество его работы, является количество его итераций. На графике (рис. 4.8) представлена типовая картина сходимость алгоритма для тестового набора задач КЗН. По горизонтали указаны номера итераций, по вертикали – рекордное значение критерия.
Целью следующей серии вычислительных экспериментов было сравнение качества работы предложенных генетических алгоритмов. Алгоритмы запускались на тестовых примерах из библиотеки QAPLIB с параметрами, подобранными выше. На каждом тестовом примере алгоритмы запускались по 10 раз. Для каждого тестового примера указано среднее время работы алгоритмов, среднее качество полученных решений, частота нахождения оптимального или рекордного решения. В таблице 4.4 показаны результаты работы генетических алгоритмов на выбранных тестовых примерах.
Каждый алгоритм на каждом примере выполнялся по 10 раз. В таблице указано среднее и рекордное значение критерия, частота достижения известного рекорда или оптимума и среднее время работы алгоритма. Из таблицы видно, что генетический алгоритм на порядковом представлении показывает более стабильные результаты, но требует больше временных ресурсов. Улучшающий генетический алгоритм на бинарном представлении также показывает неплохие результаты, а также требует меньше временных ресурсов и позволяет настраивать размер окрестности поиска, что дает возможность управлять временем работы алгоритма и качеством получаемых решений. По умолчанию в реализации многоуровневого алгоритма было принято решение использовать генетический алгоритм на порядковом представлении решений для получения более стабильных результатов.
Генетические схемы в предложенных алгоритмах являются основой для реализации направленного локального поиска с элементами рандомизации. Для подтверждения необходимости использования таких гибридных схем необходимо сравнить предложенные алгоритмы с более простым алгоритмом случайного локального поиска. В качестве такого алгоритма был выбран метод Монте-Карло [135]. Суть метода состоит в генерации заданного количества случайных решений и применении к каждому из них ЛО. Данное сравнение проводилось в третьей серии вычислительных экспериментов. Метод Монте-Карло сравнивался с гибридным генетическим алгоритмом на порядковом представлении. В ходе вычислительного эксперимента генетический алгоритм запускался при разных значениях параметра Количество поколений, который фактически определяет количество просмотренных решений за время работы алгоритма. Применялись следующие значения данного параметра: 10, 20, 30, 40, 50, 60, 70, 80, 90, 100. Остальные параметры генетического алгоритма соответственно равны: размер популяции 10, количество потомков в каждом поколении 5, количество мутантов 5, вероятность мутации 10%, количество итераций ЛО 10. Для каждого значения параметра Количество поколений количество просмотренных решений равно соответственно: 100, 200, 300, 400, 500, 600, 700, 800, 900, 1000 (в каждом поколении генерируется 5 новых потомков и 5 новых мутантов). Соответственно для организации одинаковых условий при запуске алгоритмов, в методе Монте-Карло генерировалось такое же количество случайных решений, что и количество решений, просмотренных генетическим алгоритмом при определенном количестве поколений. При каждом значении параметра алгоритмы запускались по 10 раз. Для каждой серии экспериментов при одном значении параметра рассчитывалось среднее значение качества полученных решений (рис. 4.9), рекордное значение критерия (рис. 4.10), частота получения известного оптимального решения (количество решений с оптимальным значением критерия в отношении к количеству запусков алгоритма) (рис. 4.11) и среднее время работы алгоритма (рис.4.12). На графиках (рис. 4.9 - 4.12) показаны данные результаты для типового примера (ММК - метод Монте-Карло, ГА – генетический алгоритм, по горизонтальной оси указано количество поколений генетического алгоритма, по вертикальной - соответствующая характеристика).