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

На правах рукописи

ЕМАНОВ Алексей Николаевич

МЕТОДЫ И СРЕДСТВА РАСПАРАЛЛЕЛИВАНИЯ КОМБИНАТОРНЫХ АЛГОРИТМОВ В КЛАСТЕРНЫХ СИСТЕМАХ

Специальность 05.13.11 - Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

Автореферат диссертации на соискание ученой степени ' кандидата технических наук

1

ПЕНЗА 2005

Работа выполнена на кафедре «Математическое обеспечение и применение ЭВМ» государственного образовательного учреждения высшего профессионального образования «Пензенский государственный университет».

Научный руководитель - кандидат технических наук, профессор

Шашков Борис Дмитриевич.

Официальные оппоненты: доктор технических наук

Князьков Владимир Сергеевич; кандидат технических наук, доцент Бондаренко Леонид Николаевич.

Ведущая организация - научно-производственная фирма «КРУГ»

(г. Пенза).

Защита диссертации состоится 28 декабря 2005 г., в 14 часов, на заседании диссертационного совета Д 212.186.01 в государственном образовательном учреждении высшего профессионального образования «Пензенский государственный университет» по адресу: 440026, г. Пенза, ул. Красная, 40, корпус 1.

С диссертацией можно ознакомиться в библиотеке государственного образовательного учреждения высшего профессионального образования «Пензенский государственный университет».

Автореферат разослан 27 ноября 2005 г.

Ученый секретарь диссертационного совета доктор технических наук, /72(к. профессор <7 Савельев Б. А.

iifmi

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

При рассмотрении работ, ведущихся в направлении создания эффективных комбинаторных алгоритмов, ориентированных на использование вычислительных комплексов с различной архитектурой, можно выделить следующие тенденции. В области разработки алгоритмов сохраняются попытки создания новых алгоритмов на основе новых идей и улучшения существующих алгоритмов. В области создания новых архитектур делаются попытки построить комбинированные архитектуры (кластеры на базе SMP-машин, GRID-системы на базе гетерогенных вычислительных ресурсов). Применение вычислительных комплексов с такой архитектурой налагает особые требования на создаваемые программные средства. В области создания параллельных алгоритмов можно отметить работы отдельных групп университетов и научных институтов по созданию библиотек параллельных реализаций некоторых классов алгоритмов: линейной алгебры (ATLAS, ScaLAPACK, PLAPACK), разбиения графов (PARMETIS), генерации случайных чисел (SPRNG), генетических алгоритмов (PGAPACK, GALOPPS) и т. д. Однако среди данных библиотек нет библиотек параллельной генерации комбинаторных объектов (кроме генерации случайных чисел), параллельных алгоритмов на матроидах, графах (кроме параллельных алгоритмов разбиения графов).

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

Основные задачи исследования:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Публикации. По теме диссертации опубликовано 15 печатных работ, из них 6 статей и 9 тезисов. Результаты работы зарегистрированы в Отраслевом фонде алгоритмов и программ (получено 3 свидетельства).

Структура и объем диссертации. Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы, включающего 104 наименования, и 4 приложений. Основная часть работы изложена на 192 страницах машинописного текста и содержит 32 рисунка, 62 таблицы.

СОДЕРЖАНИЕ РАБОТЫ

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

В первой главе рассматриваются существующие способы выполнения алгоритмов (последовательный и параллельный); условия, при которых возможно распараллеливание последовательных алгоритмов. Делается вывод о целесообразности использования параллельных алгоритмов генерации и обработки комбинаторных объектов. Анализируются существующие:

• библиотеки параллельных алгоритмов. Делается вывод, что существующие библиотеки параллельных алгоритмов не содержат ряд важных комбинаторных алгоритмов;

• архитектуры многопроцессорных систем: SMP, МРР, NUMA, cc-NUMA, PVP, кластеры, GRID. Показывается, что наиболее подходящей для решения поставленных задач является кластерная архитектура, ввиду ее относительно низкой стоимости, высокой производительности и легкой расширяемости;

• способы организации взаимодействия процессов (стандарты, технологии, языки параллельного программирования). Делается вы-

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

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

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

Метод распараллеливания генерации перестановок и-элементного множества V можно описать следующим образом. Поставим в соответствие исходному множеству V некоторый вектор X из п элементов, содержащий в i'-й позиции число i. Исходный процесс генерации перестановок элементов вектора X мы можем разбить на N независимых процессов, генерирующих данные перестановки на основе N различных наборов данных. Если для однопоточного алгоритма в качестве исходных данных выступал вектор X с элементами Х0, ..., XN j, то для г'-го (0 < i < п - 1) потока многопоточной версии алгоритма исходными данными будет исходный вектор X, в котором элементы Хо и Xi подверглись транспозиции. В таком случае элемент Х0 фиксируется, и дальнейшая работа каждого потока должна будет осуществляться не на всем векторе X, а лишь на его (N- I) последних элементах. Такой подход возможен, так как все алгоритмы генерации перестановок, участвовавшие в анализе, работают в терминах позиций, а не на основе содержащихся в них элементов. Очевидно, что, применяя указанный метод к созданным поднаборам данных, мы можем увеличивать число подзадач, сохраняя их равновеликость, что дает нам возможность равномерно загружать узлы гомогенного кластера.

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

содержащий в /-й позиции 1, если г'-й элемент множества V присутствует в подмножестве, и 0, если элемент в этом подмножестве отсутствует. Всевозможные конфигурации вектора X будут соответствовать всевозможным подмножествам множества V. Создадим из исходного набора данных два поднабора, для этого в первом наборе данных установим и зафиксируем Х0 = 0, а во втором -Х0 = 1. Как и в случае с методом распараллеливания генерации перестановок, каждый из потоков будет работать не с целым вектором X, а лишь с его (ТУ - 1) последними элементами. Таким образом, вместе эти потоки создадут два непересекающихся множества конфигураций вектора X, образующих в совокупности все конфигурации исходного вектора X, и, следовательно, все подмножества множества V. Применяя итеративно указанный метод ко всем созданным поднаборам (и получая в результате 2, 4, 8... наборов данных), мы можем так же, как и в случае с распараллеливанием генерации перестановок, увеличивать число подзадач до тех пор, пока это будет иметь смысл, и сохранять их равновеликость.

Генерация ^-подмножеств «-элементного множества может создавать п- и ¿-элементные векторы в зависимости от способа представления подмножества. Метод распараллеливания процесса генерации ^-подмножеств основывается на той же идее, что и метод генерации всех подмножеств. Однако так как при разбиении исходной задачи равновеликие подзадачи получаются далеко не всегда, то в целях первичной грубой балансировки нагрузки на вычислительные узлы предлагается метод разбиения задач, основывающийся на использовании треугольника Паскаля. Суть данного метода в том, что на каждой итерации разбиваются не все подзадачи, а только одна - наиболее сложная. Сложность задачи определяется по соответствующему задаче числу в треугольнике Паскаля: чем больше число, тем сложнее задача. Такой подход к разбиению задач обеспечивает более равномерную загрузку узлов кластера, чем подход, при котором разбиваются все задачи.

Описанные выше методы распараллеливания алгоритмов и методы разбиения исходных наборов данных предлагается использовать следующим образом. Исходную задачу необходимо поместить в очередь задач. Затем необходимо выполнять следующие шаги:

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

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

2. Извлечь из очереди нужное количество наборов данных, раздать их узлам.

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

4. Ожидать завершения выполнения задач на всех узлах.

5. Если очередь задач не пуста, перейти к шагу 1.

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

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

• средствами администрирования MPI среда MPI позволяет запускать несколько процессов на одном узле. Проведенный эксперимент показал, что общее время работы, как минимум, восьми процессов, запущенных конкурентно, не больше времени работы тех же восьми процессов, запущенных последовательно. Таким образом, на каждом физическом узле кластера мы можем (с помощью средств MPI) организовать несколько виртуальных, число которых пропорционально производительности данного физического узла. Для оценки производительности узлов кластера при генерации комбинаторных объектов предлагается измерять время t, выполнения малоразмерных задач генерации комбинаторных объектов на ï-m узле. После проведения тестового замера находится максимальное время выпол-

нения задачи ¿1пах, тогда количество процессов С„ которое можно запустить на г-м узле, будет определяться по формуле

(1)

ч

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

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

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

2) создать классы-функторы с алгоритмами декомпозиции задач в очереди.

Для оценки эффективности предложенных методов на гетерогенном кластере из 5 ЭВМ был проведен эксперимент по определению зависимости времени выполнения алгоритмов от числа используемых узлов кластера и учета их производительности. Результаты эксперимента приведены на рис. 1-3.

Необходимо отметить, что использование программы МРЩе1его-£епеоизСопй§ позволило сэкономить до 40 % времени - при генерации перестановок, до 47 % времени - при генерации подмножеств, по сравнению с генерацией данных объектов без учета гетерогенности среды. Для генерации ¿-подмножеств использовался первый способ учета производительности узлов, сэкономивший до 24 % времени.

2500 00

2000 00

и 1500 00

к

2

&

Ш 1000.00

500 00

ООО

Рис. 1. Время генерации перестановок множества из 15 элементов с использованием от 1 до 5 узлов гетерогенного кластера, с учетом и без учета их производительности

В С учетом производительности, N=30 в Без учета производительности, N=30

■ С учетом производительности, N=31 в Без учета производительности, N=31

■ С учетом производительности, N=32 ■ Без учете производительности, №32

да о>

Т N

1 2 3 4 5

Количество узлов

___ 1 ф (Л и> ® <о г- сч и

1й Г-. 1Л й = о О) = <0 со г- 1 1 1 8 Г*. 1 Ю Т-

1 2 3 4 5

Количество узлов

Рис. 2. Зависимость времени генерации подмножеств множества из 30-32 элементов с использованием от 1 до 5 узлов гетерогенного кластера, с учетом и без учета их производительности

ТП - разбиение на оьнове треугольника Паскаля, ПР - простое разбиение

1

6

с 3

ш а

СО

о 5

3

2

О

15

к

п

Рис. 3. Время генерации ¿-подмножеств

«-элементного множества с использованием 5 узлов гетерогенного кластера, с учетом и без учета их производительности

В третьей главе предлагаются методы распараллеливания алгоритмов: Флойда и «жадного» алгоритма на матричном матроиде -для использования в гомогенных и гетерогенных кластерах. В основе этих методов лежит общий способ распределения исходных данных (матрицы) для алгоритмов:

• для гомогенных кластеров - на каждом узле кластера располагается приблизительно одно и то же число строк матрицы. Для алгоритма Флойда данный подход был предложен Дженком (1епс[) и Сани (БаЬш), однако он нуждается в конкретизации и обобщении на случай гетерогенности кластера;

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

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

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

Общее время выполнения алгоритма Флойда на К узлах можно вычислить по формуле

F(K) = N^- + T(.K-1)), (2)

где N - размерность матрицы, К - количество узлов, Z - время вычисления одного элемента матрицы-результата, Т - время передачи одной строки матрицы между узлами.

Значение Z можно вычислить по следующей формуле, измеряя время U выполнения алгоритма Флойда на задачах малой размерности (например, при М< 800):

Z--^. О)

М2

Реальная пропускная способность сети Speed может быть вычислена по формуле

_ , „1000000 -, _м/ ...

Speedy s S-В^ баит/с, (4)

8

Speedc = строк/с,

1250005 Вэф

Speedс =-— строк/с, (5)

4 N

где S - заявленная пропускная способность сети в Мбит/с; В^ - коэффициент эффективности пропускной способности сети (например, 5эф = 0,9 означает, что из всего объема передаваемой информации лишь 90 % являются реальными данными); 4 - размер одного элемента строки. Тогда Г может быть вычислено по формуле

Г.-L— AN с. (6)

Speed 1250005 В^

Минимизация функции Р(К) дает следующие формулы определения оптимального количества узлов кластера для алгоритма Флойда: (7), если требуется найти лишь стоимость кратчайших путей; (8), если нужно найти также и сами пути (в этом случае объем передаваемых по сети данных в два раза больше):

Ко"

Кц, =

125000 Я

эф

8

125000 Бг В.

эф

16

(7)

(8)

Для «жадного» алгоритма на матричном матроиде (из М строк и N столбцов) общее время работы на К узлах можно записать следующим образом:

Р(К) = Тх{К) + Тл{К) + Тх{К) + Ту(К)о, (9)

где ТХ(К) - время выполнения всех операций проверки одного столбца на наличие ненулевых элементов (каждая операция выполняется X с), вычисляется по формуле

ТЛЮ-^ с;

(Ю)

Т2(К) - время выполнения всех операций (вида а[1\ - = а[г] у) вычисления одного элемента матрицы (каждая операция выполняется 2 с), определяется по формуле

г2

(П)

Т2{К.) = _ с;

2 К

Ту (К) - время выполнения всех операций вида а[г] = а[/] / V (У-опе-

раций). Каждая У-операция выполняется 7 с. Ту(К) в параллельном

алгоритме не зависит от К (так как эти операции выполняются исключительно последовательно) и определяется по формуле

Шг

Tj (К) - время передачи всех строк, созданных в результате выполнения всех У-операций, определяется по формуле

8

где Speedy - эффективная пропускная способность сети в байтах/с, определяется по формуле (4); 8 - размер одного элемента матрицы в байтах.

Таким образом, с учетом формул (10)—(13) формула (9) запишется следующим образом:

N2(K-1) MN(2X + ZN) YN2 F(K) ----— +---- +-c.

312505" 2?эф 2 К 2

Минимизация функции F(K) дает формулу (14) для вычисления оптимального количества узлов кластера для выполнения данного алгоритма

К =

¡S Вэф М(2Х + ZN) V N

(14)

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

Проведенный на кластере из 5 ЭВМ эксперимент показал справедливость формул (7), (8), (14): при превышении оптимального числа используемых узлов кластера происходил спад производительности (увеличение общего времени выполнения алгоритма), связанный с неспособностью сети обеспечить требуемую пропускную способность. Графики изменения ускорения выполнения алгоритмов с увеличением числа используемых узлов кластера приведены на рис. 4, 5.

Применение описанного способа учета гетерогенности позволило сэкономить до 50 % времени - для алгоритма Флойда, до 46 % времени - для «жадного» алгоритма на матричном матроиде, по сравнению с выполнением данных алгоритмов без учета гетерогенности среды.

| ♦ N=1000 - -и- - N=2000 -а- N=3000 - -х- - N=4000

Количество узлов

Рис. 4. Ускорение выполнения алгоритма Флойда в зависимости от числа используемых узлов кластера

I—ф—1000x1000--»--1000x2000-А- 2000x3000- -х- - 3000x4000]

Количество узлов

Рис. 5. Ускорение выполнения параллельного «жадного» алгоритма на матричном матроиде в зависимости от числа используемых узлов кластера

В четвертой главе формулируются основные требования, предъявляемые к разрабатываемой библиотеке. Обосновывается выбор языка С++ в качестве языка реализации библиотеки. Описывается подробный алгоритм программы MPMeterogeneous для конфигурирования MPI-среды гетерогенного кластера. Рассматриваются особенности проектирования и реализации обобщенного алгоритма генерации комбинаторных объектов для выполнения в среде MPI. Подробно раскрываются вопросы проектирования класса, обеспечивающего распределение матрицы и удобную работу с ней в гомогенной и гетерогенной кластерных средах; развернуто представлен сам алгоритм распределения строк по узлам гомогенного и гетерогенного кластеров. Рассматриваются связанные с выполнением в среде MPI особенности реализации алгоритмов Флойда и «жадного» алгоритма на матричном матроиде.

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

Приводится общая структура спроектированной библиотеки.

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

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

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

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

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

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

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

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

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

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

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

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

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

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

* Указанные свойства библиотеки позволяют рекомендовать ее к

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

(

' По теме диссертации опубликованы следующие работы:

1. Еманов А. Н. Практическое использование кластерных систем / А. Н. Еманов, Е. Н. Еманов // Современные информационные технологии: Тр. Междунар.науч.-техн. конф. СГГ conference. - Пенза, 2003. -С.140-145.

2. Еманов А. Н. Современные средства разработки параллельных программ // Современные информационные технологии: Тр. Между-нар. науч.-техн. конф. CIT conference. - Пенза, 2003. - С. 105-107.

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

4. Еманов А. Н. Параллельная генерация перестановок / А. Н. Еманов, Б. Д. Шашков // Современные информационные технологии: Тр. Междунар. науч.-техн. конф. СГГ conference. - Пенза, 2004. -С. 115-117.

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

2004.-С. 55-58.

6. Еманов А. Н. Методы распараллеливания некоторых комбинаторных алгоритмов // Материалы XI Всерос. науч.-техн. конф. -Н. Новгород, 2004. - С. 40.

7. Еманов А. Н. Параллельное генерирование ^-подмножеств // Современные информационные технологии: Тр. Междунар. науч.-техн. конф. СГГ conference. - Пенза, 2005. - С. 49-52.

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

9. Еманов А. Н. Некоторые приемы распараллеливания алгоритмов на графах // Новые информационные технологии и системы: Тр. VI Междунар. науч.-техн. конф. - Пенза, 2004. - С. 53-55.

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

11. Еманов А. Н. Параллельный «жадный» алгоритм на матричных матроидах // Современные информационные технологии: Тр. Междунар. науч.-техн. конф. СГГ conference. - Пенза, 2005. - С. 53-56.

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

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

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

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

Еманов Алексей Николаевич

4

Методы и средства распараллеливания комбинаторных алгоритмов в кластерных системах

Специальность 05.13.11 - Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

Редактор Т. Н. Судовчихина Технический редактор Н. А. Вьялкова Корректор С Н. Сухова Компьютерная верстка Р. Б. Бердниковой

ИД №06494 от 26.12.01

Сдано в производство 24.11.05. Формат 60x84'/16. Бумага писчая. Печать офсетная. Усл. печ. л. 1,16. Заказ 723. Тираж 100.

Издательство Пензенского государственного университета. 440026, Пенза, Красная, 40.

I !

»

± по г^сскии фонд

2006-4 28621

»26349

i

л

I

Введение.

Глава 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.

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