DEVELOPMENT OF MODELS AND ALGORITHMS OF INTELLIGENT DESIGN OF SOFTWARE AND HARDWARE COMPLEXES OF INFORMATION PROCESSING IN DISTRIBUTED HIGH-PERFORMANCE SYSTEMS

全文:

В последние годы четко сформировалась опреде- ленная тенденция развития средств вычислительной техники: рост производительности компьютеров про- исходит в основном не за счет увеличения производи- тельности единственного вычислительного узла (цен- трального процессора), а за счет распараллеливания вычислительного процесса по нескольким узлам ком- пьютера или даже по компьютерной сети. Такой под- ход не содержит принципиальных ограничений в по- вышении скорости и точности работы систем обра- ботки информации. Однако одновременно с ростом производительности вычислительных систем растет и сложность решаемых с их помощью задач. Особенно актуальными сейчас, в свете повсеместного распро- странения компьютерных сетей и Интернета, являют- ся задачи обработки и анализа информации в распре- деленных системах. Разнообразие задач обработки и анализа данных не позволяет говорить о какой-либо универсальной аппаратно-программной реализации вычислительного комплекса, которому были бы по силам все задачи. Таким образом, массовое использо- вание технологий анализа данных сдерживается труд- ностями разработки вычислительных комплексов, предназначенных для решения конкретных задач, что во многом объясняется отсутствием математиче- ского аппарата моделирования функционирования специализированных распределенных вычислитель- ных систем. Можно утверждать, что сегодня в области боль- ших вычислений конкурируют две идеи. Первая идея предполагает использование централизованных вы- числительных комплексов (суперкомпьютеров), вто- рая – использование распределенных вычислитель- ных систем. Особенностью распределенных много- процессорных вычислительных систем, в отличие от локальных суперкомпьютеров, является возможность неограниченного наращивания производительности за счет масштабирования. Так, проект BOINC (Berkeley Open Infrastructure for Network Computing), являю- щийся примером реализации распределенных вычис- лений, обладает средней производительностью 5 000 TeraFLOPS, что сравнимо с производительностью суперкомпьютера, возглавляющего рейтинг TOP500 (8 162 TeraFLOPS). По доступности для использования суперкомпью- теры также можно сравнивать с распределенными вычислительными системами. Если для суперкомпь- ютеров естественным ограничением является их стоимость, то применение распределенных вычисле- ний связано лишь с организационными и алгоритми- ческими сложностями. Проведен патентный поиск и выполнен аналити- ческий обзор данной предметной области. Исследова- ния позволили сделать следующие выводы: – при проектировании распределенных систем и алгоритмов используются в основном подходы к по- вышению производительности вычислений частного запроса (выбор вычислительного элемента (процессо- ра), оптимизация нагрузки на систему, структура кон- тролера и т. д.). При этом не оптимизируется архитек- тура комплекса в целом, а, как известно, транзакци- онные издержки и режим работы главного сервера могут замедлять систему в целом даже при сверхпро- изводительных локальных серверах; – разработчики не используют распараллеливание задач на уровне алгоритмов (островные модели, коо- перационные и конкурирующие схемы, комитеты ре- шателей), которые существенно повышают эффек- тивность решения задач даже на последовательных компьютерах; – комплексные решения предлагаются крупными разработчиками (IBM, Deutsche Telecom, Intel и др.) и в общем случае являются системами, ориентиро- ванными исключительно на специфику, технологии и технические решения разработчика, что существен- но снижает область применения; – проблема обработки слабо структурированной информации практически не рассматривается; * Работа выполнена при финансовой поддержке ФЦП «Исследования и разработки по приоритетным направлениям раз- вития научно-технологического комплекса России» на 2007−2013 гг. НИР 2011-1.9-519-005-042 и ФЦП «Научные и научно- педагогические кадры России» НИР 2011-1.2.1-113-025, 2011-1.2.2-215-021. 77 Математика, механика, информатика – говоря об интеллектуальных информационных системах, разработчики чаще всего имеют в виду ис- пользование разных эвристик в предметной области. При этом методы обработки информации могут быть традиционными, не связанными с интеллектуальными информационными технологиями. Семантика решае- мых задач не используется; – частные работы по применению методов и алго- ритмов интеллектуальных информационных техноло- гий не ориентированы на широкое распространение, так как требуют привлечения специалистов и пред- метных экспертов как на этапе проектирования ин- теллектуальных технологий, так и при их настройке и использовании. Таким образом, очевидно, что задача проектиро- вания аппаратно-программных комплексов обработки информации в распределенных системах является актуальной. В [1] проводится обзор существующих математи- ческих моделей многопроцессорных систем, рассмат- риваются различные подходы к созданию таких моде- лей. Подробно исследуется модель, где процесс функционирования многопроцессорных систем пред- ставляется замкнутой системой массового обслужи- вания. Предполагается, что состав и характеристики узлов вычислительного комплекса напрямую зависят от специфики решаемой задачи. Так, для реализации наиболее часто применяемых алгоритмов и операций используются специализированные процессоры, с индивидуальными характеристиками. Приводятся алгоритмы расчета производительности, надежности и стоимости проектируемых комплексов. Таким обра- зом, в [1] задача проектирования эффективного вы- числительного комплекса формулируется в виде зада- чи оптимизации: Пв(n, m1, …, mi, …, mN, T01, ...,T0i, ..., T0N) → max, Нв(n, m1, …, mi, …, mN, T01, ...,T0i, ..., T0N) → max, Св(n, m1, …, mi, …, mN, T01, ...,T0i, ..., T0N) → min. В данной модели приняты следующие обозначе- ния: Пв – критерий оценки производительности; Нв – критерий оценки надежности; Св – критерий оценки стоимости; n – количество шин; mi – количество про- чи необходимо учитывать следующие факторы: пере- менные задачи выражены в различных шкалах изме- рения (целочисленные и вещественные переменные), оптимизация производится по нескольким экстре- мальным критериям одновременно, априорные сведе- ния о свойствах целевых функционалов отсутствуют (оптимизация производится только по измерениям функционалов в фиксированных точках). Метод оп- тимизации должен учитывать условия, накладывае- мые на критерии. Таким образом, при выборе эффек- тивной конфигурации вычислительного комплекса возникает необходимость решения задачи многокри- териальной условной оптимизации с алгоритмически заданными функциями разношкальных переменных высокой размерности. В [2] процесс функционирования распределенной вычислительной системы (ГРИД-системы) представ- лен в виде системы массового обслуживания. Приво- дятся модели расчета производительности и надежно- сти ГРИД-системы. Процесс проектирования эффек- тивной конфигурации ГРИД-системы также сводится к решению многокритериальной задачи условной оп- тимизации. Всеми необходимыми качествами для решения та- ких задач обладают многоагентные методы стохасти- ческой оптимизации, имитирующие естественный отбор и поведение социальных групп в природе. К таким методам относятся генетический алгоритм, алгоритм генетического программирования, алгоритм оптимизации роем частиц (PSO). Однако задача эф- фективного применения данных методов сравнима по сложности с исходной задачей проектирования вы- числительных комплексов, требуется разработка и исследование методов автоматического проектиро- вания и настройки интеллектуальных информацион- ных технологий. Данная проблема может быть реше- на с использованием самонастраивающихся много- агентных стохастических алгоритмов, включая коэво- люционные схемы и вероятностные алгоритмы [3; 4]. Одним из примеров программы-агента для задач однокритериальной условной и безусловной оптими- зации с алгоритмически заданными целевыми функ- циями вещественных, целочисленных, бинарных или цессоров i-го типа, 1 ≤ mi ≤ 16, i = 1, N ; T0i – среднее смешанных переменных, программы, обладающей время выполнения одной команды в процессоре i-го значительно меньшим, чем стандартный генетический алгоритм, числом настраиваемых параметров, являет- типа, T0i > 0 , i = 1, N ; определяется исходя из реали- ся так называемый коэволюционный генетический зуемой в специализированном процессоре функции. В реальных задачах количество типов процессоров может достигать нескольких десятков, а количество специализированных процессоров каждого типа – многих десятков. Допустим, что имеется десять типов спецпроцессоров и возможно включение в систему до 20 спецпроцессоров каждого типа. Тогда при исполь- зовании рассматриваемой в [1] аналитической модели имеется около 2010 возможных комбинаций. Если осуществлять поиск оптимальной конфигурации не только по структуре вычислительного комплекса, но и по быстродействию спецпроцессоров, то общее число вариантов системы возрастет примерно до 1028. Кроме того, при выборе метода решения данной зада- алгоритм [5]. Основная проблема использования эволюционных процедур – высокая сложность настройки параметров алгоритма для решения конкретной задачи оптимиза- ции. Поэтому использование эволюционных проце- дур, в том числе генетических алгоритмов, требует очень высокой квалификации лица, принимающего решения (ЛПР), как в области данных алгоритмов, так и в проблемной области, Нужны также значительные временные затраты. Одним из перспективных подхо- дов для решения указанной проблемы является коэво- люционный алгоритм. Ранее были разработаны ко- эволюционные алгоритмы, решающие задачи безус- 78 Вестник Сибирского государственного аэрокосмического университета имени академика М. Ф. Решетнева ловной оптимизации [4]. Однако большинство прак- тических задач относится к классу задач условной оптимизации, т. е. имеются ограничения в виде нера- венств или равенств. Коэволюционный генетический алгоритм – это не- сколько параллельно действующих стандартных гене- тических алгоритмов. Отдельный генетический алго- ритм называется подпопуляцией. Каждая из подпопу- ляций оптимизирует заданную функцию и обладает своей стратегией оптимизации. При этом популяции «борются» за ресурс, который в течение работы алго- ритма перераспределяется в пользу более эффектив- ной из них. Стандартный коэволюционный алгоритм состоит из следующих этапов [4]: – выбора индивидуальных алгоритмов; – задания параметров коэволюционного алгорит- ма (размера общего ресурса, величины интервала адаптации, размера штрафа «проигравшего» алгорит- ма, размера «социальной карты») для всех индивиду- альных алгоритмов; – работы выбранных алгоритмов в течение интер- вала адаптации; – оценки алгоритмов; – перераспределения ресурсов; – миграции лучших индивидов во все подпопуля- ции. Перераспределение ресурсов позволяет «домини- ровать» алгоритму, обладающему наилучшими на- стройками для оптимизации имеющейся целевой функции. Миграция позволяет одновременно исполь- зовать преимущества различных алгоритмов – в пер- вую очередь, локальную и глобальную сходимости. Изменение размеров ресурсов происходит путем со- кращения каждой проигравшей популяции на некото- рый процент (определенный заранее размер штрафа) и увеличением победившей популяции на число, рав- ное сумме потерь проигравших. Иными словами, после каждого интервала адаптации определяется один побе- дивший алгоритм (подпопуляция). При этом размер ка- ждой подпопуляции не может быть меньше определен- ного уровня, называемого «социальной картой». В [5] предлагается новый метод перераспределе- ния ресурсов между алгоритмами, получивший на- звание «турнирный». Суть метода заключается в том, что после каждого интервала адаптации не определя- ется единственный победивший алгоритм, а происхо- дит перераспределение ресурсов в каждой паре под- популяций («турнир каждого с каждым»). Данный метод перераспределения ресурсов позволяет провес- ти ранжирование подпопуляций по эффективности оптимизации для текущей целевой функции. Резуль- тат такого ранжирования – перераспределение ресур- сов между всеми подпопуляциями в соответствии с их эффективностью. Турнирный метод перераспределе- ния ресурсов тестировался в сравнении со стандарт- ным на десяти тестовых функциях (задачах безуслов- ной оптимизации). В качестве показателя эффектив- ности работы алгоритма использовалась надежность – отношение числа запусков, в которых с заданной точ- ностью был найден оптимум, к общему числу запус- ков. По ранговому критерию Вилкоксона турнирный метод оказался значимо лучше стандартного на четы- рех тестовых функциях и не хуже на оставшихся шес- ти, что свидетельствует о целесообразности предло- женного подхода. Для адаптации генетического алгоритма к реше- нию задач условной оптимизации необходимо ввести в процедуру специальные методы учета ограничений, используемые в ГА. В данной работе рассматривались следующие: метод «смертельных» штрафов, «лече- ние» локальным поиском, метод статических штра- фов, метод динамических штрафов, метод адаптивных штрафов. Для апробации предложенного алгоритма была решена задача проектирования распределенной вы- числительной сети для решения задачи прогнозирова- ния объемов продаж товаров в аптеках ГПКК «Гу- бернские аптеки» [6]. Данные по задаче следующие: – средняя вычислительная сложность одной ите- рации вычислений на одной ветви алгоритма решения задачи – 10 000 оп.; – средняя вычислительная сложность управления одной ветвью алгоритма решения задачи – 5 000 оп.; – средний объем данных клиент-серверного обме- на – 200 КБ. Для построения GRID-системы имеется в наличии 153 клиентских узла, параметры которых варьируют- ся в следующих пределах: – производительность от 4 200 до 17 345 MFLOPS; – скорость каналов передачи данных от 10 до 27 МБит/с; – стоимость аренды за 1 ч использования от 1,03 руб. до 3,82 руб. По надежности все клиентские узлы разбиваются на две группы с интенсивностями отказов 0,000 01 и 0,000 001. Также задано расписание работы всех клиентских узлов. Выбор серверного узла проектируемой GRID- системы не производится по причине того, что пред- приятие-заказчик предоставляет свой серверный узел со следующими параметрами: – количество процессоров – 2; – производительность каждого процессора сервера – 11 500 MFLOPS; – стоимость аренды – 0; – интенсивность отказов процессоров сервера – 0,000 001. На проектируемую GRID-систему наложены сле- дующие ограничения: – количество клиентских узлов GRID-системы должно быть не менее 15 и не более 20; – коэффициент готовности GRID-системы не ме- нее 99,9 %; – минимальная производительность GRID-сис- темы не менее 50 GFLOPS. При решении задачи была получена аппроксима- ция парето-множества, состоящая из шести точек, а также фронта Парето. По значениям стоимости и производительности по- лученных конфигураций GRID-систем был выбран ва- риант состава проектируемой системы (см. таблицу). 79 Математика, механика, информатика Состав выбранной конфигурации GRID-системы Производительность, MFLOPSСкорость канала дан- ных, МБит/сСтоимость 1 часа аренды, руб.Время работыИнтенсивность отказов Производительность, MFLOPSСкорость канала дан- ных, МБит/сСтоимость 1 часа аренды, руб.Начало работыКонец работыИнтенсивность отказов 5 295121,248:0018:000,000 01 7 600161,648:0019:000,000 01 6 420211,49круглосуточно0,000 01 7 020151,6822:009:000,000 01 8 410191,9512:0019:000,000 01 10 250252,359:0021:000,000 001 9 330231,939:0021:000,000 01 8 465121,878:0018:000,000 001 6 930151,6522:009:000,000 01 11 270182,388:0019:000,000 001 9 430152,049:0019:000,000 001 7 515201,60круглосуточно0,000 01 10 650242,2112:0019:000,000 001 8 800191,908:0019:000,000 01 6 900111,539:0021:000,000 01 6 750211,42круглосуточно0,000 01 11 000272,3619:008:000,000 01 11 000272,3619:008:000,000 01 11 000272,3619:008:000,000 01 17 345243,640:006:000,000 001 Построенная конфигурация GRID-системы обла- дает следующими характеристиками: – средняя производительность – 81,522 GFLOPS; – стоимость – 466,71 руб. в сутки; – коэффициент готовности – 99,92 %; – минимальная производительность – 51 GFLOPS. Таким образом, полученный в ходе решения зада- чи вариант распределенной вычислительной системы полностью удовлетворяет исходным ограничениям. Несмотря на растущую популярность и множество успешных проектов по реализации распределенных вычислений, отсутствует формальное обоснование эффективности применяемых решений. Часто для успешного решения вычислительных задач распреде- ленными или централизованными многопроцессор- ными системами используются аппаратные средства, заведомо превышающие необходимый уровень. Это многократно повышает стоимость таких проектов и в целом снижает их эффективность. Описываемое в данной статье исследование направлено на повыше- ние обоснованности применения распределенных вы- числительных систем. Разработка математического и алгоритмического обеспечения интеллектуального проектирования аппаратно-программных комплексов обработки информации в распределенных высоко- производительных системах позволит значительно повысить эффективность их работы и расширить сфе- ру их применения.

作者简介

I. Panfilov

Email: crook_80@mail.ru.

N. Smirnov

Email: smirnov@sibsau.ru.

V. Terskov

Email: crook_80@mail.ru.

参考

补充文件