Методы и средства распараллеливания комбинаторных алгоритмов в кластерных системах тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат технических наук Еманов, Алексей Николаевич

• Еманов, Алексей Николаевич
• кандидат технических наук
• 2005

Оглавление диссертации кандидат технических наук Еманов, Алексей Николаевич

Введение.

Глава 1. Обзор существующих архитектурных и программных платформ

1.1 Использование комбинаторных алгоритмов.

1.2 Способы реализации алгоритмов.

1.3 Существующие архитектуры параллельных компьютеров.

1.3.1 SMP (Symmetric Multiprocessing).

1.3.2 МРР (Massive Parallel Processing).

1.3.3 NUMA (неоднородный доступ к памяти).

1.3.4 cc-NUMA (неоднородный доступ к памяти с поддержкой когерентности кэшей).

1.3.5 PVP (параллельно-векторные системы).

1.3.6 Кластеры.

1.3.7 GRID (вычислительная сеть).

1.3.8 Выводы.

1.4 Способы организации взаимодействия процессов.

1.4.1 Стандарты.

1.4.2 Технологии.

1.4.3 Высокоуровневые средства разработки.

1.4.4 Выводы.

Выводы по главе 1.

Глава 2. Создание высокоэффективных реализаций параллельных комбинаторных алгоритмов генерации комбинаторных объектов.

2.1 Эффективная реализация параллельной генерации перестановок N-элементного множества.

2.2 Эффективная реализация параллельной генерации всех подмножеств TV-элементного множества.

2.3 Эффективная реализация параллельной генерации ^-элементных подмножеств.

2.4 Генерация комбинаторных объектов в гетерогенной кластерной среде.

2.4.1 Учет производительности узлов кластера при распараллеливании алгоритма.

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

2.5 Вычислительный эксперимент. Генерация комбинаторных объектов в гетерогенной среде.

2.6 Метаалгоритм генерации комбинаторных объектов.

2.6.1 Фаза сбора данных.

2.6.2 Эффективное распределение задач.

2.6.3 Конструирование метаалгоритма управления распараллеливанием генерации комбинаторных объектов.

Выводы по главе 2.

Глава 3. Эффективные реализации параллельных алгоритмов на графах и матроидах.

3.1 Эффективная реализация параллельного алгоритма Флойда.

3.1.1 Метод распараллеливания.

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

3.1.3 Вычислительный эксперимент.

3.2 Эффективная реализация параллельного жадного алгоритма на матроидах.

3.2.1 Метод распараллеливания.

3.2.2 Вычисление оптимального количества узлов для параллельного выполнения жадного алгоритма на матричном матроиде.

3.2.3 Вычислительный эксперимент.

3.3 Выполнение параллельных алгоритмов Флойда и жадного алгоритма на матричном матроиде в гетерогенной кластерной среде.

Выводы по главе 3.

Глава 4. Библиотека параллельных реализаций комбинаторных алгоритмов.

4.1 Общее назначение библиотеки.

4.2 Требования, предъявляемые к библиотеке.

4.3 Выбор языка реализации.

4.4 Особенности проектирования и реализации программ в среде стандарта MPI и MPI-2.

4.4.1 Программа конфигурирования гетерогенной кластерной среды с использованием средств MPI.

4.4.2 Реализация метаалгоритма генерации комбинаторных объектов

4.4.3 Реализация распараллеливания алгоритма Флойда в среде MPI

4.4.4 Реализация распараллеливания жадного алгоритма на матричных матроидах в среде MPI.

4.4.5 Тестирование реализаций параллельных алгоритмов.

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

Выводы по главе 4.

Введение диссертации (часть автореферата) на тему «Методы и средства распараллеливания комбинаторных алгоритмов в кластерных системах»

В последние десятилетия получены теоретические результаты, свидетельствующие о том, что для широкого класса задач не существует достаточно «эффективных алгоритмов», и способ их решения носит комбинаторный характер. С другой стороны, налицо - возрастающая с каждым годом потребность решения задач в областях: дискретной оптимизации, исследования операций, моделирования процессов и систем в экономике, физике, химии и т.д. [1,2,3]

Центральными в решении данных задач являются комбинаторные объекты, которые можно условно разделить на несколько классов:

• элементарные комбинаторные объекты (перестановки множества, подмножества множества, k-элементные подмножества, разбиения множества, разбиения чисел);

• графы;

• матроиды.

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

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

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

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

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

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

Цель работы - повышение эффективности алгоритмов генерации и обработки комбинаторных объектов за счет использования их параллельных форм в кластерных системах

Задачи исследования. Для достижения поставленной цели были решены следующие задачи:

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

2. Анализ существующих алгоритмов генерации и обработки комбинаторных объектов, разработка их эффективных последовательных реализаций;

3. Разработка методов распараллеливания последовательных алгоритмов генерации и обработки комбинаторных объектов в гомогенных и гетерогенных кластерах;

4. Решение задачи выбора оптимального количества узлов кластера для выполнения параллельных алгоритмов: Флойда и "жадного" алгоритма на матричном матроиде;

5. Проектирование и реализация библиотеки эффективных параллельных комбинаторных алгоритмов;

Методы исследования. При выполнении диссертационной работы использовались: теория множеств, теория графов, теория матроидов, линейная алгебра, технологии программирования.

Для оценки производительности полученных реализаций последовательных и параллельных алгоритмов использовалась РТ-метрика. При проектировании и реализации библиотеки эффективных реализаций использовался язык моделирования UML, объектно-ориентированный подход.

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

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

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

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

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

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

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

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

Реализация и внедрение результатов работы. Результаты работы внедрены в НПФ «КРУГ» г. Пенза.

Основные положения, выносимые на защиту:

1. Методы распараллеливания алгоритмов генерации комбинаторных объектов: перестановок, подмножеств n-элементного множества, 1с-подмножеств,- на основе параллелизма данных;

2. Методы учета производительности узлов гетерогенного кластера для выполнения алгоритмов генерации;

3. Методы распараллеливания алгоритмов Флойда и жадного алгоритма на матричном матроиде на основе параллелизма данных для выполнения в гомогенных и гетерогенных кластерах;

4. Методы расчета оптимального числа используемых узлов кластера для работы параллельных алгоритмов: Флойда и жадного алгоритма на матричном матроиде;

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

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

Заключение диссертации по теме «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей», Еманов, Алексей Николаевич

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

1. общая структура библиотеки;

2. библиотека классов PCOL (Parallel Combinatorial Object Library), включающая эффективные реализации:

• параллельной генерации комбинаторных объектов: перестановки множества, подмножества множества, k-элементные подмножества п-элементного множества;

• алгоритма поиска кратчайших путей на базе алгоритма Флойда, распараллеленного по методу, описанному в главе 3;

• жадного алгоритма на матричном матроиде, распараллеленного по методу, описанному в главе 3.

3. динамически подключаемая библиотека PCOGen.dll, позволяющая, не вникая в структуру библиотеки, использовать ее основные функции и алгоритмы сторонними программами, написанным на других языках программирования (отличными от С++).

Заключение

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

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

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

2. Разработан метод сбалансированного разбиения задачи генерации 1с-элементных подмножеств на основе использования треугольника Паскаля;

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

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

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

6. Решена задача определения оптимального количества используемых узлов кластера для выполнения алгоритма Флойда и жадного алгоритма на матричном матроиде в зависимости от размерности задачи, производительности узлов кластера и пропускной способности сети;

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

Спроектированная и реализованная в ходе работы библиотека разрабатывалась в соответствии с предъявлявшимися к ней требованиями, что позволяет отметить следующие ее свойства:

1. эффективность включенных в нее последовательных и параллельных реализаций комбинаторных алгоритмов;

2. возможность эффективного использования алгоритмов библиотеки в гомогенных и гетерогенных кластерах;

3. кроссплатформенность;

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

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

Дальнейшие исследования по рассматриваемой проблеме целесообразно производить в следующих направлениях:

1. Увеличение числа включенных в библиотеку параллельных алгоритмов: генерации комбинаторных объектов, алгоритмов на графах и матроидах;

2. Усовершенствование методов учета производительности узлов гетерогенного кластера;

3. Усовершенствование механизма распределения подзадач на узлы кластера;

4. Создание версии библиотеки для платформы .NET.

Список литературы диссертационного исследования кандидат технических наук Еманов, Алексей Николаевич, 2005 год

1. Хованов К.Н., Корников В.В., Серегин И.А. Случайные композиции и их применение // Обозрение прикладной и промышленной математики. 2000. Том 7. Вып. 1. С. 152-153.

2. Гэри Антее. Магия исследования onepa4Hfi.//Computerworld Россия, 22 Марта 2005

3. Sergey A. Maidanov, Andrey Naraikin. Making the Monte Carlo Approach Even Easier and Faster (http://www.mtel.com/cd/ids/developer/asmo-na/eng/)

4. Воеводин B.B. Суперкомпьютеры: вчера, сегодня, завтра. // Сборник научно-популярных статей <Российская наука на заре нового века>. Под редакцией академика В.П. Скулачева. М.: научный мир, 2001. С. 475483

5. Бочаров Н.В. Технологии и техника параллельного программирования // Программирование. 2003. №1. С. 5-23.

6. Ортега Дж. Введение в параллельные и векторные методы решения линейных систем. -М.: Мир, 1991

7. Воеводин Вл. В. Курс лекций в Международном Университете г.Дубна.

8. Андрей Кузнецов. Параллельные миры (http://www.ccc.ru/magazine/depot/00 08/)

9. Специализированные параллельные библиотеки (http://www.parallel.ru/tech/tech dev/par libs.html)

10. Г.И. Шпаковский, Н.В. Серикова. Программирование для многопроцессорных систем в стандарте MPI. Минск, БГУ, 2002, -324с.

11. Основные классы современных параллельных компьютеров (http://parallel.ru/computers/classes.html)

12. Кластер: какой он есть (http://www3.diadema.ru/cluster/old/)

13. A.H. Еманов, E.H. Еманов. Практическое использование кластерных систем // Труды международной научно-технической конференции CIT conference "Современные информационные технологии" Пенза, 2003, с. 140-145.

14. Andrew Binstock. Multiprocessors, Clusters, Grids, and Parallel Computing: What's the Difference (http://www.intel.com/cd/ids/developer/asmo-na/eng/)

15. Christine Chudnow Grid Computing // Computer Technology News, 2002 March

16. Ananth Grama, Anshul Gupta, George Karypis, Vipin Kumar. Introduction to Parallel Computing, Addison Wesley, 2003, ISBN 0-201-64865-2

17. A.H. Еманов. Современные средства разработки параллельных программ //Труды международной научно-технической конференции CIT conference "Современные информационные технологии" Пенза, 2003, с. 105-107.

18. А.Н. Еманов. Средства обучения параллельному программированию // Труды международной научно-технической конференции CIT conference "Современные информационные технологии" Пенза, 2003, с. 125-126.

19. Стивене У. UNIX: разработка сетевых приложений. СПб: "Питер", 2004. - 1088 с.

20. Галатенко В.А. Программирование в стандарте POSIX. Курс лекций. Учебное пособие :М. ,2004,560с Изд-во "Интернет-Университет Информационных Технологий", ISBN: 5-9556-0011-6

21. Сергей Романюк. Сюрпризы POSIX //Открытые системы #09-10, 1999 год

22. В.О. Gallmeister. Posix. 4: Programming for the Real World. O'Reilly & Associates, 1995

23. R. Chandra, L. Dagurn, D. Kohr, D. Maydan, J. McDonald, and R.M. (editors). Parallel Programming in OpenMP. Morgan Kaufmann Publishers, 2000

24. Cameron Hughes. Parallel and Distributed Programming Using С++. Addison-Wesley Professional, 2003. 1st Edition, ISBN: 0131013769

25. W. Gropp, E. Lusk, and A. Skjellum. Using MPI. MIT Press, 1999. 2nd Edition.

26. Richard Grimes. Professional DCOM Programming. Peer Information Inc., 1997. 1st Edition, ISBN: 186100060X

27. Steve Teixeira, Xavier Pacheco. Delphi 5 Developer's Guide (Developer's Guide). Sams, 1999, ISBN: 0672317818

28. A.Lastovetslcy. Parallel Computing on Heterogeneous Networks. John Wiley & Sons, 423 pages, 2003, ISBN: 0-471-22982-2

29. Tao Pang. An Introduction to Computational Physics. Cambridge University Press, 393 pages, 1997, ISBN: 0-521-48143-0

30. Николай Коновалов, Виктор Крюков. Параллельные программы для вычислительных кластеров и сетей //"Открытые Системы" №3 2002

31. И.Г.Евсеев. Организация параллельных вычислений на базе программного обеспечения PVM (http://chip.csa.ru/~il/Parallei/)

32. W. D. Gropp and E. Lusk. User's Guide for mpich, a Portable Implementation of MPI. Mathematics and Computer Science Division, Argonne National Laboratory. ANL-96/6. 1996.

33. Дуйсекулов A.E., Елизарова Т.Г. Использование многопроцессорных вычислительных систем для реализаций кинетически-согласованных разностных схем газовой динамики. // Математическое моделирование, 1990, т. 2,| 7, с. 139-147.

34. Ильин В.П. О стратегиях распрараллеливания в математическом моделировании. // Программирование. 1999, № 1, с. 41-46.

35. Тарнавский Г.А., Шпак С.И. Декомпозиция методов и распараллеливание алгоритмов решения задач аэродинамики и физической газовой динамики: вычислительная система <Поток-3>. // Программирование. 2000, № 6, с. 45-57.

36. Э. Рейнгольд, Ю. Нивергельт, Н. Део. Комбинаторные алгоритмы, теория и практика. М.: Изд-во «Мир», 1980

37. В. Липский. Комбинаторика для программистов. М.: Изд-во «Мир», 1988.

38. Lipski W. More on permutation generation methods. Computing, 1979, 23, s. 357-365.

39. Johnson S.M. Generation of permutations by adjacent transpositions. Math. Сотр., 1963, 17, s. 282-285

40. Trotter H. F. Perm (Algorithm 115), Comm. ACM, 1962, 5, s. 434-435.

41. Tadao Takaoko. An 0(1) Time Algorithm for Generating Multiset Permutations //Algorithms and Computation: 10th International Symposium, Isaac 99, Chennal, India, December 16-18, 1999, Proceedings (Lecture Notes in Computer Science)

42. J. Keller. Fast Parallel Permutation Algorithms. 1993, CS-R9303, ISSN 0169-118X

43. Zbigniew Kokosinski: On Generation of Permutations through Suffix/Prefix Reversing in a Cellular Network. // Parallel Processing and Applied Mathematics: 5th International Conference, 2003, ISBN: 3-540-21946-3, pp249-254

44. Lin C-J.: Parallel algorithm for generating permutations on linear array. //Information Processing Letters 35 (1990) 167-170

45. Gupta P., Bhattacharjee G.P.: Parallel generation of permutations.//The Computer Journal 26 (1983) 97-105

46. Kapralski A.: New methods for generation peremutations, combinations and other combinatorial objects in parallel.//Journal of Parallel and Distributed Computing 17 (1993) 315-326

47. A.H. Еманов, Б.Д. Шашков. Параллельная генерация перестановок // Труды международной научно-технической конференции CIT conference "Современные информационные технологии" Пенза, 2004, с. 115-117.

48. А.Н. Еманов. Учет особенностей комбинаторных алгоритмов при создании их параллельных форм //Труды VI международной научно-технической конференции "Новые информационные технологии и системы" Пенза, 2004, с. 55-58.

49. S.G. Akl. The Design and Analysis of Parallel Algorithms. Prentice-Hall, 1989

50. A.H. Еманов. Методы распараллеливания некоторых комбинаторных алгоритмов //Материалы одиннадцатой Всероссийской научно-технической конференции. Н. Новгород, 2004, с.40.

51. Tadao Takaoko. 0(1) Time Algorithm for Combinatorial Generation by Tree Traversal.//Computer Journal, vol. 42, no. 5, pp400-408, 1999

52. S.G. Akl, D. Gries, and I. Stojmenovic. An optimal parallel algorithm for generating combinations. //Information Processing Letters, 33:135-139, 1989

53. Z. Kokosinski. Algorithms for unranlting combinations and their applications.//International Conference Parallel and Distributed Computing and Systems, pages 216-224, 1995

54. B.B. Zhou, R. Brent, X.Qu, and W.F. Liang. A novel parallel algorithm for enumerating combinations .//International Conference on Parallel Processing, volume 2, pages 70-73, 1996

55. S.G. Aid. Adaptive and optimal parallel algorithms for enumerations permutations and combinations.//The сотр. J., 30:433-436, 1987.

56. Martha Torres, Alfredo Goldman. A parallel algorithm for enumerating combinations.//Proceeding of the 2003 International Conference on Parallel Processing (ICPP'03)

57. М.Я. Выгодский. Справочник по элементарной математике. -М.: «Большая Медведица», 2001

58. А.Н. Еманов. Параллельное генерирование k-подмножеств // Труды международной научно-технической конференции CIT conference "Современные информационные технологии" Пенза, 2005, с. 49-52.

59. А.Н. Еманов. Выполнение параллельных комбинаторных алгоритмов в гетерогенной среде // Труды международной научно-технической конференции CIT conference "Современные информационные технологии" Пенза, 2005, с. 56-59.

60. Э. Дийкстра. Языки программирования. -М:."Мир", 1972

61. Конкурентное программирование (http ://traceproj ect.h 14.ru/concurprog.shtml)

62. Лафоре P. Объектно-ориентированное программирование в С++. Классика Computer Science. 4-е изд. СПб.: Питер, 2003. - 928 е.: ил.

63. Гамма Э., Хелм Р., Джонсон Р., Влиссидес Дж. Приемы объектно-ориентированного проектирования. Паттерны проектирования. СПб: Питер, 2001. - 368 е.: ил. (Серия "Библиотека программиста").70.0ре О. Теория графов. -М.: Наука, 1968

64. Харари Ф. Теория графов. -М.: Мир, 1973

65. Уилсон Р. Введение в теорию графов. -М.:Наука, 1977.

66. Берж К. Теория графов и ее применения. -М.: ИЛ, 1962

67. Белов В.В., Воробьев Е.М., Шаталов В.Е. Теория графов. -М.: Высшая школа, 1976

68. Floyd R. W. Algorithm 97: Shortest path. Comm. ACM. 1962, 5, s. 345.

69. Dijkstra E. W. A note on two problems in connexion with graphs. Numer. Math., 1959, l,s. 269-271.

70. Фундаментальные алгоритмы на С++. Алгоритмы на графах. Роберт Седжвик. СПб: ООО "ДиаСофтЮП", 2002

71. Форд Л.Р., Фалкерсон В.Р. Потоки в сетях. -М.: Мир, 1965

72. Malhotra V. М., Kumar P. М., Maheshwari S. N. An 0(|V|3) algorithm for finding maximum flows in networks. Information Processing Lett., 1978, 7, s. 277-278.г/9

73. Hopcroft J., Karp R. M. An n algorithm for maximum Matchings in bipartite graphs. SLAM J. Comput., 1973, 2, s. 225-231.

74. M.O. Асанов, B.A. Баранский, B.B. Расин Дискретная математика: графы, матроиды, алгоритмы. Ижевск: НИЦ "РХД", 2001

75. Murchland J.D. (1967), The once-through method of finding all shortest distances in a graph from single origin.//London Graduate School of Business Studies, Report LBS-TNT-56

76. H. Кристофидес. Теория графов. Алгоритмический подход. -М.:Мир, 1978

77. J. Jenq and S. Sahni. All Pairs Shortest Paths on a Hypercube Multiprocessor. //In International Conference on Parallel Processing, pages 713-716,1987

78. D. P. Bertsekas and J. N. Tsitsiklis. Parallel and Distributed Computation: Numerical Methods. Prentice-Hall, NJ, 1989.

79. V. Kumar and V. Singh. Scalability of parallel algorithms for the all-pairs shortest path problem. Journal of Parallel and Distributed Computing, 13(2):124-138, October 1991.

80. Kumar V., Grama A., Gupta A. and Karypis G. Introduction to Parallel Programming Design and Analysis of Algorithms, Benjamin Cummings Publishing, 1994, ISBN 0-8053-3170-0.

81. K. N. Levitt and W. T. Kautz. Cellular arrays for the solution of graph problems. Communications of the ACM, 15(9):789-801, September 1972.

82. K. M. Chandy and J. Misra. Distributed computation on graphs: Shortest path algorithms. Communications of the ACM, 25(11):833-837, November 1982.

83. A.H. Еманов. Некоторые приемы распараллеливания алгоритмов на графах //Труды VI международной научно-технической конференции "Новые информационные технологии и системы" Пенза, 2004, с. 53-55.

84. А. Ахо, Дж. Хопкрофт, Дж. Ульман. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979

85. А.Н. Еманов. Определение оптимального количества узлов кластера для распределенного выполнения алгоритма Флойда // Труды международной научно-технической конференции CIT conference "Современные информационные технологии" Пенза, 2004, с. 196-198.

86. Whitney Н. On the. abstract properties of linear independence. Amer. J. Math., 1935,57, s. 509-533.

87. Tutte W. T. Introduction to the Theory of Matroids. New York, American Elsevier 1970.

88. Lawler E. L. Combinatorial Optimization: Networks and Matroids. New York, Holt, Rinehart and Winston 1976.

89. Welsh D. J. A. Matroid Theory. London, Academic Press 1976.

90. Gale D. Optimal assignments in an ordered set: an application of matroid theory. J. Combinatorial Theory, 1968, 4, s. 176-180.

91. Edmonds J. Matroids and the greedy alrorithms. Math. Programming, 1971, 1, s. 127-136.

92. Айгнер M. Комбинаторная теория. M., Мир, 1982

93. А.Н. Еманов. Параллельный жадный алгоритм на матричных матроидах // Труды международной научно-технической конференции

94. CIT conference "Современные информационные технологии" Пенза, 2005, с. 53-56.

95. Еманов А.Н. Программа конфигурирования MPI-среды для генерации комбинаторных объектов в гетерогенном кластере. -М.: ВНТИЦ, 2005. -№50200501224

96. Еманов А.Н. Библиотека классов для параллельной генерации комбинаторных объектов. -М.: ВНТИЦ, 2005. -№50200501225

97. Еманов А.Н. Разработка С++ класса для работы с распределенной матрицей в среде MPI// Труды международной научно-технической конференции CIT conference "Современные информационные технологии" Пенза, 2004, с. 199-201.

98. Еманов А.Н. Библиотека классов для параллельной обработки некоторых комбинаторных объектов в матричной форме. -М.: ВНТИЦ, 2005. -№50200501226