В развитии компьютерной архитектуры на ближайшую перспективу определился ряд доминирующих тенденций: количество ядер в процессорах будет расти, а отдельные компьютеры будут объединяться в различного рода сетевые инфраструктуры, кластеры и гриды. Иначе говоря, наблюдается что-то подобное переходу от одноклеточных организмов к многоклеточным или от одиночного существования к коммунальному, произошедшему в природе более 500 миллионов лет назад. С грядущей коммунальностью в ИТ связаны и новые проблемы: предстоит научиться управлять разнообразными распределенными инфраструктурами, найти способы интеграции миллионов ядер и распределения нагрузки между ними и т. п.

Сейчас в ИТ преобладает инженерный подход к решению такого рода задач, но имеется и множество других — в частности, построенных на принципах бионики путем сочетания инженерных и биологических начал. В бионических алгоритмах, подсказанных природой (Nature Inspired Algorithms, NIA), на машинном уровне воспроизводят поведение колоний насекомых, птиц или рыб. NIA не новость — они нашли применение в разного рода оптимизационных приложениях, а в последнее время распространяются и на управление (см. рисунок). А если учесть, что природные процессы обладают естественным параллелизмом, то выполнение NIA может быть заметно ускорено при использовании больших пулов графических процессоров и технологий типа MapReduce.

Этапы формирования NIA
Этапы формирования NIA

 

В большинстве своем NIA имитируют свойства сообществ, состоящих из примитивных особей, — точнее, их удивительную способность к децентрализованному принятию решения. Сообщества простых организмов представляют яркий пример синергетического эффекта, когда совокупная способность сообщества больше суммы способностей отдельных частей — из мелких составляющих образуется коллективный интеллект, или интеллект роя (Swarm Intelligence, SI). Благодаря SI рой демонстрирует поведение и принятие таких решений, которые по своей сложности заведомо недоступны одной отдельно взятой особи. Кто не наблюдал за поведением муравьев или необыкновенными пируэтами птичьих стай?

Раскрыть лежащие в основе слаженного поведения секреты удалось совсем недавно, в начале 90-х годов, Деборе Гордон, исследователю из Стэнфордского университета. Она изучала механизм SI на примере деятельности муравьев-термитов, каждый из которых не обладает каким-либо интеллектом, но их колония в целом действует весьма разумно. Выяснилось, что SI является порождением какой-то структурной сложности и образуется за счет системы простейших коммуникаций между членами сообщества. Обмена несколькими байтами оказалось достаточно для организации целесообразного децентрализованного коллективного поведения. Последовавшие в конце прошлого века многочисленные исследования показали, что примерно на тех же принципах основано коллективное поведение пчелиных семей, птичьих стай и даже человеческих сообществ. О последних хорошо написал Джеймс Шуровьески в книге «Мудрость толпы», объясняющей феномен краудсорсинга.

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

Первые опыты практического применение SI для оптимизационных приложений датируются серединой девяностых годов прошлого века, а во втором десятилетии века нынешнего открылись возможности для распространения методов SI на такие инфраструктуры, как кластеры или гриды. Огромный потенциал NIA здесь очевиден — имеется прямая аналогия между множеством так или иначе объединенных процессоров и колониями животных. Еще одну область возможного применения SI в ИТ открывает проблема Больших Данных, где технологии на базе NIA могут поддерживать модели распределенных вычислений MapReduce. Ограниченность существующих реализаций MapReduce в том, что они используют конкретное число ядер, отсюда следуют неизбежность пакетного режима и структуризация выходных данных. Но если бы идею MapReduce реализовал рой, состоящий из нескольких типов узлов, способных справиться с любыми входными данными в сочетании со способностью к самоорганизации, то такой рой вполне мог бы работать в режиме реального времени, причем без какой-либо предварительной организации данных. Интеллект роя открывает принципиально новые возможности в области анализа данных, однако этот подход не распространяется на транзакционные системы, где критичны требования ACID (Atomicity — «атомарность», Consistency — «согласованность», Isolation — «изоляция», Durability — «долговечность хранения»).

Оптимизация на основе SI

За время использования SI в оптимизационных задачах были созданы десятки различных подходов, и из их разнообразия можно выделить три основных типа алгоритмов: муравьиный алгоритм (Ant Colony Optimization, ACO), метод оптимизации роем частиц (Particle Swarm Optimization, PSO) и пчелиный алгоритм (Bee Colony Optimization, BCO).

Муравьиный алгоритм. В начале 90-х Марко Дориго, ученый из Брюссельского свободного университета, первым применил математические процедуры, основанные на SI, для решения близких по смыслу задач, таких как организация грузоперевозок, управление авиалиниями, координация действий боевых роботов. Дориго — автор алгоритмов метаэвристической (metaheuristic — «поиск за пределами») оптимизации, базирующейся на подражании муравьиной колонии, которая оказалась эффективной для нахождения приближенных решений задачи, сводящихся к задаче коммивояжера. Суть подхода заключается в анализе и использовании модели поведения муравьев, ищущих пути от колонии к источнику питания. Первая версия алгоритма, предложенная Дориго в 1992 году, была направлена на поиск оптимального пути в графе.

Сущность ACO чрезвычайно проста — все дело в феромонах, биологически активных веществах, выделяемых животными и специфически влияющих на поведение других особей. Феромоны используются насекомыми для подачи самых разных сигналов — например, для обозначения пройденного пути. По специальным меткам, оставляемым по дороге, муравей может найти путь обратно в муравейник. Метки показывают муравейнику и дорогу к найденной добыче. Если на прямом пути от муравейника к источнику пищи поставить барьер так, что обход с одной стороны будет длиннее, чем с другой, то сначала выбор направления обхода будет случайным, но потом окажется, что с той стороны, где путь короче, плотность потока муравьев будет больше — насекомые выделяют больше фермента, еще сильнее привлекая в нужную сторону оставшихся. Через какое-то время колония будет пользоваться только коротким путем. Примерно так же решаются и более сложные задачи — например, распределение работы по добыче еды и ремонту муравейника. Система моделирования Ant Colony System, предложенная Дориго, имитирует эту схему на графах, в ней могут видоизменяться способы распространения и восприятия «феромонов».

Метод оптимизации роем частиц. Метод возник из попыток объяснить синхронное перемещение птичьих или рыбьих стай и был предложен психологом Джеймом Кеннеди и инженером Расселом Эберхартом, которые в 1995 году выпустили книгу «Swarm Intelligence». В основе их метода лежит эволюционный алгоритм (Evolutionary Algorithm, EA), имитирующий социальное поведение особей стаи. Поведение группы в целом складывается из поведения каждой особи в занимаемом ею пространстве. Поведение не носит антагонистического характера, поэтому складывается своего рода кооперация, где за счет небольших ущербов для каждого вся популяция в целом выигрывает.

В PSO моделируется аналогичное перемещение частиц в многомерном пространстве решений — изменение положения отдельной частицы определяется стремлением живых существ конкурировать между собой в борьбе за ресурсы и коррелируется с поведением и опытом соседей. Каждая частица стремится занять оптимальный участок пространства решений, но при этом все они могут улучшить собственное положение за счет превосходства достижений соседних частиц. Сообщество приобретает системный эффект, «эмерджентное» свойство (от английского emergent — неожиданно появляющийся). В SI используются виртуальные стаи, воспроизводящие поведение реальных стай, — при машинном моделировании PSO частицы имеют в этом пространстве некоторое положение и вектор скорости. Для каждого положения частицы вычисляется значение целевой функции, в соответствии с которым и по определенным правилам частица меняет свое положение и скорость в пространстве поиска ресурсов.

Пчелиный алгоритм. BCO имеет более чем десятилетнюю историю, этим направлением занимаются десятки групп исследователей в разных странах, среди них, казалось бы, неожиданные — например, Сербия и Турция. Отличие BCO от ACO и PSO в том, что здесь воспроизводится более сложная иерархическая система отношений, состоящая из особей с разным статусом: матка, рабочие пчелы и трутни.

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

В апреле 2013 года состоялся симпозиум IEEE Swarm Intelligence Symposium, тематика выступлений которого позволяет судить о сфере применения SI: робототехника, биоинженерия, биоинформатика, бизнес и финансы, условная оптимизация, «раскопки» и кластеризация данных, распределенные инфраструктуры, динамические среды, эволюционирующее аппаратное обеспечение, информационная безопасность, машинное обучение, беспроводные сети и многое другое. Разберем здесь распределенные инфраструктуры, использующие графические процессоры и MapReduce.

Гриды и SI

Гриды являются одной из составляющих распределенных ИТ-инфраструктур, отличаясь от традиционных систем хранения распределением ресурсов по узлам, в том числе и географическим, что накладывает особые требования к управлению ими, которое может быть децентрализованным. Если для отдельных компьютеров и ОС системы управления создаются исходя из представления о полной доступности сведений о среде и о ее полной подчиненности, то в гридах все может быть не так — они могут быть распределены между разными административными доменами, неоднородны, узлы могут иметь разную надежность и т. д. Здесь возникает обычная дилемма между централизованным или децентрализованным управлением. У каждого из подходов свои преимущества и недостатки, но если оценить эволюционный процесс в целом, то заметно движение от централизованных систем к децентрализованным, и в том числе управляемым с использованием муравьиного алгоритма.

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

По типу организации системы управления можно разделить на три класса: централизованные, децентрализованные и иерархические — что характерно не только для компьютерных систем. В идеале степень централизации должна быть минимальной, но обеспечивающей достижение поставленной цели, однако и у децентрализованного управления есть недостаток — увеличенное время адаптации системы, что весьма существенно для быстро меняющихся сред. То, что в централизованных системах можно сделать за короткое время, в децентрализованной будет осуществляться медленнее. К тому же недостатком централизованного подхода является сложность управления из-за огромного потока данных, подлежащих переработке в старшей по иерархии системе управления. Поэтому в сложной конфигурации обычно присутствуют два уровня управления. Если обстановка меняется медленно, то децентрализованная часть системы успешно справляется с адаптацией к среде и с достижением глобальной цели системы за счет оперативного управления, а при резких изменениях среды осуществляется централизованное управление по переводу системы в новое состояние. Централизованное управление эффективно, но хуже отражает изменения в среде — в частности, плохо масштабируется. Децентрализованное в этом отношении лучше, поэтому для максимальной эффективности всей системы в целом должно быть налажено взаимодействие между локальными центрами управления. Иерархическая система, пример которой мы можем видеть в бизнесе и в государственном управлении, сочетает обе модели управления.

С момента появления компьютерных сетей велись разработки централизованных подходов к управлению, основанные на эвристических алгоритмах: круговая перестановка (Round-Robin scheme), минимальное время исполнения (Minimum Execution Time), минимальное время завершения (Minimum Completion Time) и др. Главное достоинство этих классических алгоритмов — простота, но по той же причине они малоэффективны, поэтому были разработаны альтернативные централизованные решения, способные осуществлять поиск в среде. Наиболее известны два решения — использующие генетические алгоритмы (Genetic Algorithms, GA) и основанные на табуированном поиске (Tabu Search, TS). Генетические алгоритмы позволяют осуществлять поиск оптимальных параметров с использованием механизмов, аналогичных естественному отбору в природе. Алгоритмы TS отличаются тем, что в процессе поиска выделяются области, близкие к оптимальным, и для исключения лишней рекурсии дальнейшая работа с ними запрещается (на них накладывается табу). Оба алгоритма обеспечивают высокое качество балансировки, но для гридов с очень большим количеством узлов они не подходят — требуются децентрализованные решения.

С появлением SI открылась теоретическая возможность для децентрализации управления гридами — существует около десятка решений для децентрализованной балансировки, базирующихся на муравьином алгоритме. Одной из первых была созданная в 2002 году в Болонском университете система Messor (Messor — род муравьев), полностью воспроизводящая поведение насекомых в муравейнике. Муравьи поделены на два подмножества: Search-Max ищут максимально загруженные узлы, а Search-Min — недогруженные, они обмениваются «феромонами», и таким образом происходит выравнивание нагрузки. Позже была создана система Multiple Ant Colony Optimization (MACO), а затем ABC (Ant-Based Control system), Ant-Net и ASGA, отличающиеся моделями поведения муравьев и использованием или неиспользованием GA и TS. Большая часть этих работ находится на уровне академических исследований.

GPU, MapReduce и SI

Сегодня постоянно возрастает необходимость в аналитике реального времени, что требует более производительных компьютеров. Здесь могут помочь GPU, поскольку задачи анализа большей части природных и тестовых данных могут быть распараллелены на много тредов, вычислительная мощность каждого из которых может быть невелика. Исследования, связанные с использованием GPU, ведутся сейчас в нескольких университетах, и одна из первых работ — ClusterFlockGPU, построенная на имитации птичьей стаи, — уже на уровне эксперимента позволила ускорить обработку данных на два порядка. В работах [1, 2] детально рассмотрены методы анализа данных на GPU с поддержкой SI.

Использование MapReduce в качестве платформы для PSO позволяет решить проблемы готовности и распределения нагрузки между узлами кластера, исследования в этом направлении начались с работы, выполненной под руководством Эндрю Макнабба [3].

***

Интеллект роя — не единственный пример NIA, наряду с ним в область, которую называют soft computing («мягкие вычисления»), входят нейронные сети, нечеткая логика, эволюционное моделирование, теория хаоса и другие методы. Все они различаются по степени готовности к практическому использованию, но SI пока относится к числу наиболее перспективных.

Литература

  1. Robin M. Weiss. GPU-Accelerated Data Mining with Swarm Intelligence, Macalester College, May 2010. URL: http://metislogic.net/thesis.pdf (дата обращения: 11.02.2014).
  2. Chad Hantak. GPU-Based Platform for Swarm Intelligence Simulation. URL: http://www.hantak.com/projects/papers/SwarmGPU.pdf Chad (дата обращения: 11.02.2014).
  3. Andrew W. McNabb, Christopher K. Monson, Kevin D. Seppi. Parallel PSO Using MapReduce. URL: http://www.cs.york.ac.uk/rts/docs/CEC-2007/html/pdf/1802.pdf (дата обращения: 11.02.2014).

Леонид Черняк (osmag@osp.ru) — научный редактор, «Открытые системы. СУБД» (Москва).