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

Введение

1 Аналитический обзор

1.1 Области применения кластерных вычислительных систем.

1.1.1 Применение кластерных вычислений в системах управления базами данных.

1.1.2 Применение кластерных вычислительных систем в робототехнике

1.2 Основные подходы к программированию кластерных систем.

1.3 Обоснование необходимости разработки адаптивных алгоритмов обработки информации. Задачи, решаемые в диссертационной работе

1.4 Выводы.

2 Модель мультиагентной вычислительной системы

2.1 Модель распределенной вычислительной системы.

2.1.1 Автомат ввода-вывода

2.1.2 Автомат, моделирующий канал передачи информации.

2.1.3 Решающий автомат ввода-вывода.

2.1.4 Композиция автоматов ввода-вывода.

2.1.5 Фрагменты исполнения и следы исполнения автомата ввода-вывода

2.2 Модель вычислительного агента.

2.2.1 Взаимодействия между агентами.

2.2.2 Вопросы реализации.

2.2.3 Группировка модифицированных автоматов ввода-вывода

2.3 Выводы.

Адаптивные алгоритмы масштабирования мультиагентной вычислительной системы

3.1 Адаптивная однородная репликация данных (без ведущего).

3.1.1 Организация вычислений.

3.1.2 Алгоритм адаптации к добавлению агента в группу

3.1.3 Алгоритм адаптации к удалению агента из группы.

3.1.4 Обсуждение результатов.

3.2 Адаптивная репликация данных с ведущим.

3.2.1 Организация вычислений.

3.2.2 Алгоритм адаптации к добавлению агента в группу

3.2.3 Алгоритм адаптации к удалению агента из группы.

3.2.4 Обсуждение результатов.

3.3 Адаптивный алгоритм фрагментации данных.

3.3.1 Организация вычислений.

3.3.2 Ограничение размера вектора истории изменения хэш-функции

3.3.3 Адаптивный алгоритм добавления агента в группу.

3.3.4 Адаптивный алгоритм удаления агента из группы.

3.3.5 Обсуждение результатов.

3.4 Алгоритм адаптивной репликации вычислений

3.4.1 Обсуждение результатов.

3.5 Алгоритм адаптивной фрагментации вычислений.

3.5.1 Адаптивный алгоритм добавления агента в группу с фрагментацией вычислений

3.5.2 Адаптивный алгоритм удаления агента из группы.

3.5.3 Обсуждение результатов.

3.6 Выводы.

Информационно-поисковая система «Адривер»

4.1 Алгоритм функционирования системы.

4.2 Аппаратная конфигурация системы.

4.3 Теоретическая оценка масштабируемости системы

4.4 Масштабирование системы с целью адаптации к росту числа запросов

4.5 Выводы.

5 Алгоритмы управления развитием мультиагентной вычислительной системы

5.1 Основные принципы управления развитием мультиагентной вычислительной системы.

5.2 Модель вычислительного агента с программируемым развитием

5.3 Пример эволюции системы.

5.4 Моделирование эволюции высокопроизводительной системы обработки запросов.

5.5 Выводы.

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

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

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

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

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

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

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

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

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

1. Разработка модели вычислительного агента.

2. Разработка алгоритмов адаптации к удалению и добавлению компонентов для распределенной системы, реализующей следующие функции:

• однородную репликацию данных (без ведущего),

• репликацию данных с ведущим,

• фрагментацию данных,

• репликацию вычислений,

• фрагментацию вычислений.

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

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

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

2. На основе этой модели разработаны алгоритмы, которые, в отличие от существующих, осуществляют автоматическую корректировку процесса обработки информации без остановки вычислений:

- при добавлении нового агента в группу с целью наращивания вычислительной мощности или пространства памяти,

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

3. Разработаны и реализованы оригинальные алгоритмы:

• адаптивной однородной репликации данных (без ведущего),

• адаптивной репликации данных с ведущим,

• адаптивной фрагментации данных,

• адаптивной репликации вычислений,

• адаптивной фрагментации вычислений.

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

Теоретическая и практическая ценность диссертационной работы определяется тем, что разработаны алгоритмы адаптации к добавлению и удалению вычислительных машин для наиболее часто встречающихся методов распределения и обработки информации. Кроме этого, разработан метод программирования развития системы, который позволяет наращивать вычислительную мощность системы постепенно, по мере необходимости. Большинство предложенных алгоритмов внедрены при создании информационно-поисковой системы «Адривер» (www.adriver.ru). Некоторые результаты диссертации нашли применение в международном проекте «Multi-Agent Robotic System for Industrial Application in Transport Domain» по гранту #IC15-CT96-0702 европейской программы COPERNICUS и в гранте РФФИ #98-01-01088 «Методы интеллектуального и нейросетевого управления мультиагентными робо-тотехническими системами», а также в учебном процессе БГТУ и ГУАП.

Результаты работы докладывались и обсуждались на следующих конференциях: "Первая международная конференция по мехатронике и робототехнике "МиР'2000" (С.-Петербург, 29 мая - 2 июня 2000г.); "VI С.-Петербургская международная конференция "Региональная информатика - 98"(С.- Петербург, 2-4 июня 1998 г.); а также на научных семинарах в С.-Петербургском институте информатики и автоматизации РАН, ГУАП и БГТУ «Военмех».

По теме диссертации опубликовано восемь работ, включая 3 статьи, 3 доклада и 2 публикации тезисов докладов.

Структура диссертационной работы

В главе 1 («Аналитический обзор») обоснована необходимость обеспечения адаптивности алгоритмов управления распределением вычислений и данных. На примере существующих решений в области СУБД, таких как Oracle, DB2, Sybase, Informix, проанализирована проблема добавления новых компонентов в кластерную систему. Показано, что существующие решения не обеспечивают непрерывность работы вычислительной системы в процессе изменения ее конфигурации. Приведено обоснование целей и задач исследования.

В главе 2 («Модель мультиагентной вычислительной системы») предложена математическая модель вычислительного агента, обсуждаются его свойства и вопросы технической реализации. Под агентом понимается программно-аппаратный комплекс с устройствами связи. Агент вместе с себе подобными кооперативно участвует в вычислительном процессе. Предлагаемая в главе модель агента позволяет более просто осуществлять программирование и организацию распределенных вычислительных систем, обладающих адаптивными свойствами, которые заключаются в обеспечении работоспособности в случае отказа или удаления одного или нескольких агентов и свойстве системы автоматически реконфигурироваться при добавлении новых агентов.

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

В главе 4 («Информационно-поисковая система «Адривер») описывается система «Адривер», основным разработчиком которой является автор настоящей диссертации. Кратко излагаются принципы функционирования и структура программной реализации.

В главе 5 («Алгоритмы управления развитием мультиагентной вычислительной системы») предложен метод программирования эволюции системы, который позволяет динамически привлекать новых агентов с целью увеличения производительности и размера памяти системы. Таким образом система адаптируется к требуемым объемам вычислений. В процессе программируемой эволюции система имеет возможность изменять стратегию обработки данных в зависимости от используемого в данный момент алгоритма распределения информации.

Основные результаты диссертации докладывались на конференциях и были опубликованы в следующих работах:

1. Вересов И.Г., Колушев Ф.А. "Кластеры: Суперкомпьютеры на каждый день"// Мир Интернет N6-7 2002, СПб.:изд. «Питер», 2002 - с.60 - 65.

2. Вересов И.Г. "Распределенные вычисления в мультиагентной среде и синхронизация мультиагентных баз данных"// Тезисы докладов конференции МИР'2000, Том 2, 29 мая - 2 июня, 2000. - Санкт-Петербург, 2000 - с.64 -67.

3. Вересов И.Г., Тимофеев А.В., "Успенский С.М. "Компьютерный учебник и система моделирования нейронных сетей (NN-SIM)"// Тезисы докладов VI Санкт-Петербургской международной конференции "Региональная информатика - 98", 2-4 июня 1998. - Санкт-Петербург, 1998. - ч.2. - с.26-27

4. Богданов А.А., Вересов И.Г., Колушев Ф.А., Тимофеев А.В., Успенский С.М. "Мультиагентное планирование движения транспортных роботов в среде с препятствиями"// Информационные технологии и интеллектуальные методы. Выпуск N3. - СПб.:СПИИРАН, 1999 - с.ЮЗ - 111.

5. Вересов И.Г., Колушев Ф.А., Успенский С.М. "Мультиагентная система планирования движения траспортных роботов - структура программной реализации"// Тезисы докладов конференции МИР'2000, Том 2, 29 мая - 2 июня, 2000. - Санкт-Петербург, 2000 - с.142 - 146.

6. F.A.Koluchev, I.H.Veresov, S.M.Uspensky "Multiagent Path Planning Systems For Transport Robots - Software Structure"// Proceedings Volume 1, M&R'2000 conference, May 29 - June 2, 2000, St.Petersburg, Russia - p.191

7. I.H.Veresov "Distributed Computation and Database Synchronization in Multiagent Systems"// Proceedings Volume 1, M&R'2000 conference, May 29 -June 2, 2000, St.Petersburg, Russia - p.216

Заключение

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

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

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

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

- при добавлении нового агента в группу с целью наращивания вычислительной мощности или пространства памяти,

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

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

5. Разработанные оригинальные алгоритмы реализованы и апробированы в информационно-поисковой системе «Адривер» (http://www.adriver.ru), которая функционирует в сети Интернет.

1. Jim Gray "What Next? A Dozen 1.formation-Technology Research Goals"// Turing Award Lecture, Technical Report MS-TR-99-50, Microsoft Research, 1999, http://research.microsoft.com/~gray.

2. В.Савяк "Эффективные кластерные решения"// iXBT, 04/2002, http://www.ixbt.com/cpu/clustering.shtml.

3. А.А.Денисов, Д.Н.Колесников "Теория больших систем управления"/ JI.: Энер-гоиздат, 1982.

4. Спицнадель В.Н. "Основы системного анализа"/ СПб.:Изд. дом «Бизнес-пресса», 2000.

5. Ian Т. Foster "Designing and Building Parallel Programs: Concepts and Tools for Parallel Software Engineering"/ Addison-Wesley, 1995.

6. Вл.В. Воеводин "Суперкомпьютерная грань компьютерного мира", http: / / www. parallel. ru/par allel / vvv / intro2hpc. html.

7. Вл.В. Воеводин "Материалы к курсу лекций (параллельные вычисления, технологии параллельного программирования, параллельные компьютеры и суперЭВМ, анализ структуры программ"// http://www.parallel.ru/parallel/vvv.

8. Вересов И.Г., Колушев Ф.А. "Кластеры: Суперкомпьютеры на каждый день"// Мир Интернет N6-7 2002, СПб:изд. «Питер», 2002 с.60 - 65.

9. Вересов И.Г., Колушев Ф.А., Успенский С.М. "Мультиагентная система планирования движения траспортных роботов структура программной реализации"/ / Тезисы докладов конференции МИР'2000, Том 2, 29 мая - 2 июня, 2000.- Санкт-Петербург, 2000 с. 142 - 146.

10. F.A.Koluchev, I.H.Veresov, S.M.Uspensky "Multiagent Path Planning Systems For Transport Robots Software Structure"// Proceedings Volume 1, M&R'2000 conference, May 29 - June 2, 2000, St.Petersburg, Russia - p.191.

11. Вересов И.Г., Колушев Ф.А. "Мультиагентный алгоритм поиска кратчайшего пути на графе"// Вопросы управления и проектирования в информационных и кибернетических системах, Уфа:УГАТУ, 2002 с. 76-82.

12. A.A. Bogdanov, A.V. Timofeev "Robust Optimal Neural Control of Robots"// Proceedings of IEEE Int. Conf. IJCNN-99, Washington, D.C., July 10-16, 1999.- USA, 1999.

13. Timofeev, A.V., Bogdanov, A.A. "Methods of Non-Linear Neural Element Informativity Evaluation in Neural Networks"// Int. journal "Information theory and applications". 1996. - Vol. 4. - Pp. 22-29.

14. Ю.А.Борцов, В.Б.Второв, Д.Ю.Иншаков, А.Я.Почкаев "Транспьютерные сети в задачах управления и моделирования сложных электромеханических объектов"// Известия ГЭТУ. Сб. научн. трудов. Вып. 492. СПб. 1996. С. 86-92.

15. Ю.А.Борцов, В.Б.Второв, А.В.Савилов, Д.Ю.Иншаков "Транспьютерная реализация адаптивных структур управления роботом-манипулятором"// Электротехника. 1996. N10. С.1-5.

16. L. Itti "The Beobot Platform for Embedded Real-Time Neuromorphic Vision", // Advances in Neural Information Processing Systems, Vol. 15, (T. G. Dietterich, S. Becker, Z. Ghahramani Ed.), Cambridge, MA:MIT Press, in-press.

17. T. Ozsu, P.Valduriez "Principles of Distributed Database Systems"/ Prentice-Hall, 1999.24. «Параллелизм в поисковой архитектуре Яндекса», http://company.yandex.ru/programs/web200203.html.

18. Peter S. Pacheco "A User's Guide to MPI"// Department of Mathematics, Univ. of San Francisco.

19. Dolphin Interconnect Benchmarks, http://www.dolphinics.com/results.html.

20. W.D.Gropp "Learning from the Success of MPI"// Mathematics and Computer Science Division, Argonne National Laboratory, 2001.

21. A1 Geist, Adam Beguelin, Jack Dongarra, Weicheng Jiang, Robert Manchek, Vaidy Sunderam "PVM: Parallel Virtual Machine A Users' Guide and Tutorial for Networked Parallel Computing"/ MIT Press, 1994, http://www.netlib.org/pvm3/book/pvm-book.html.

22. Ian Foster, Carl Kesselman "Globus: A Metacomputing Infrastructure Toolkit"// Argonne National Laboratory, Univ. of Southern California, http://www.globus.org.

23. S.Leffler, R.Fabry, N.Joy, Ph.Lapsley, S.Miller, Ch.Torek "An Advanced 4.4BSD Interprocess Communication Tutorial"// Univ. of California, Berkeley, Univ. of Maryland.

24. А.Л.Ластовецкий "Программирование параллельных вычислений на неоднородных сетях компьютеров на языке трС", Интерактивный учебный курс, http: / / www. ispr as. ru/ ~ mpc / tutorial/tut or-koi. html.

25. Keith H. Randall "Cilk: Efficient Mulithreaded Computing", Ph.D. dissertation / MIT, 1998.

26. Matteo Frigo "Portable High-Performance Programs", Ph.D. dissertation / MIT, 1999.

27. Robert D. Blumofe, Philip A. Lisiecki "Adaptive and Reliable Parallel ~ Computing on Networks of Workstations", 1996, http://citeseer.nj .nec.com/blumofe97adaptive.html.

28. Aaron B. Brown, David A. Patterson "Embracing Failure: A Case for Recovery-Oriented Computing (ROC)"// Computer Science Division, University of California at Berkeley, 2001, http://www.cs.berkeley.edu/~abrown/papers/hpts01-draft.pdf.

29. J.Hennessy, David A. Patterson "Computer architecture: A Quantitative Approach, 3e (beta version)"// Morgan Faufmann, San Francisco, 2001.

30. W. Feng, M. Warren, E. Weigle "Honey, I Shrunk the Beowulf"// Los Alamos Unclassified Report 02-1210, 3/2002.

31. W. Feng, M. Warren, E. Weigle "The Bladed Beowulf: A Cost-Effective Alternative to Traditional Beowulfs"// Los Alamos Unclassified Report 02-2582, 4/2002.

32. Oracle8i Server Replication, Release 2 (8.1.6).

33. Avi Ziv "Analysis and Performance optimization of checkpointing schemes with task duplication"/ Ph.D. dissertation, Stanford University, 1995.

34. W. Wayt Gibbs "Autonomic Computing"// Scienific American, 05/2002.

35. M. Wooldridge "Intelligent Agents"// Multiagent Systems, The MIT Press, 1999.

36. M. Wolldridge, N.R.Jennings "Intelligent Agents: Theory and Practice"// Knowledge Engineering Review, 1997.

37. B.Moore, M.Noschang, J.Penix "An Annotated Bibliography of Software Agent Technology"// Dept. of Electrical and Computer Engineering, University of Cincinnati.

38. Nancy A. Lynch, Mark R. Tuttle "Hierarchical correctness proofs for distributed algorithms"/ Master's thesis, Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, Cambridge, MA 02139, April 1987.

39. Nancy A. Lynch "Distirbuted Algorithms"/ Morgan Kaufmann, San Francisco, 1997.

40. Stephen J. Garland, Nancy A. Lynch "The IOA Language and Toolset: Support for Mathematics-Based Distributed Programming"// MIT LCS, 1998.

41. Toh Ne Win, Michael Ernst "Verifying Distributed Algorithms via Dynamic Analysis and Theorem Proving"// MIT LCS, 2002, http://citeseer.nj.nec.com/win02verifying.html.

42. Nancy Lynch, Roberto Segala, Frits Vaandrager "Hybrid I/O Automata"// MIT LCS, 2002, http://citeseer.nj.nec.com/528236.html.

43. Lynch N., Merritt M., Weihl W., Fekete A. "Atomic Transactions"// Morgan Kaufmann, 1994.

44. Nancy Lynch, "Atomic Transactions for Multiprocessor Programming: A Formal Approach"// MIT LCS, 1994.

45. Rajeev Alur, David L. Dill "Automata for modeling real-time systems"// Automata, Languages and Programming: Proceeding of the 17th 1С ALP, Lecture Notes in Computer Science 443, pp. 322-335, Springer-Verilag, 1990.

46. Nick Carriero, Eric Freeman, David Gelernter and David Kaminsky "Adaptive Parallelism and Piranha"// Yale University, 3/1994, http: //www. cs. у ale. edu/Linda/ар and piranha, html.

47. Вересов И.Г. "Распределенные вычисления в мультиагентной среде и синхронизация мультиагентных баз данных"// Тезисы докладов конференции МИР'2000, Том 2, 29 мая 2 июня, 2000. - Санкт-Петербург, 2000 - с.64 - 67.

48. I.H.Veresov "Distributed Computation and Database Synchronization in Multiagent Systems"// Proceedings Volume 1, M&R'2000 conference, May 29 -June 2, 2000, St.Petersburg, Russia p.216.

49. C.Pu, A.Leff "Execution Autonomy in Distributed Transaction Processing"// Columbia University, New York, 1991.

50. C.Pu, A.Leff "Replica Control in Distributed Systems: An Asynchronous Approach"// Columbia University, New York, 1991.

51. M.Rabinovich, N.Gehani, A.Kononov "Scalable Update Propagation in Epidemic Replicated Databases"// AT&T Bell Labs, 1995.

52. D.S.Parker, G.J.Popek, G.Rudisin, A.Stoughton, B.J.Walker, E.Walton, J.M.Chow, D.Edwards, S.Kiser, C.Kline. "Detection of mutual inconsistency in distributed systems"// IEEE Trans, on Software Eng. 9(3), pp.240-246, 1983.

53. Thomas H. H. Cormen, Ronald L. Rivest, Charles E. Leiserson "Introduction to Algorithms"/ MIT Press, 1990.

54. А.Ахо, Д.Хопкрофт, Дж. Ульман "Структуры данных и алгоритмы" дательский дом "Вильяме", 2000.