Введение к работе
Актуальность темы. Существует широкий класс задач, решение которых носит комбинаторный характер. Очевидна возрастающая с каждым годом потребность решения задач в областях дискретной оптимизации, исследования операций, моделирования процессов и систем в экономике, физике, химии и т. д. Важную роль в данных задачах играют комбинаторные объекты.
Использование комбинаторных объектов подразумевает их создание и обработку. Проблема заключается в том, что комбинаторные алгоритмы часто характеризуются большим объемом производимых вычислений. Повышение быстродействия программного обеспечения, использующего комбинаторные алгоритмы, может производиться за счет повышения эффективности алгоритмов, положенных в основу данного программного обеспечения.
При рассмотрении работ, ведущихся в направлении создания эффективных комбинаторных алгоритмов, ориентированных на использование вычислительных комплексов с различной архитектурой, можно выделить следующие тенденции. В области разработки алгоритмов сохраняются попытки создания новых алгоритмов на основе новых идей и улучшения существующих алгоритмов. В области создания новых архитектур делаются попытки построить комбинированные архитектуры (кластеры на базе SMP-машин, GRID-системы на базе гетерогенных вычислительных ресурсов). Применение вычислительных комплексов с такой архитектурой налагает особые требования на создаваемые программные средства. В области создания параллельных алгоритмов можно отметить работы отдельных групп университетов и научных институтов по созданию библиотек параллельных реализаций некоторых классов алгоритмов: линейной алгебры (ATLAS, ScaLAPACK, PLAPACK), разбиения графов (PARMETIS), генерации случайных чисел (SPRNG), генетических алгоритмов (PGAPACK, GALOPPS) и т. д. Однако среди данных библиотек нет библиотек параллельной генерации комбинаторных объектов (кроме генерации случайных чисел), параллельных алгоритмов на матроидах, графах (кроме параллельных алгоритмов разбиения графов).
рос национальная! библиотека x
SnszM
Цель работы. Основной целью работы является повышение эффективности алгоритмов генерации и обработки комбинаторных объектов за счет использования их параллельных форм в кластерных системах.
Основные задачи исследования:
-
Обзор существующих библиотек параллельных реализаций алгоритмов и анализ архитектур, позволяющих производить параллельные вычисления.
-
Анализ существующих алгоритмов генерации и обработки комбинаторных объектов, разработка их эффективных последовательных реализаций.
-
Разработка методов распараллеливания последовательных алгоритмов генерации и обработки комбинаторных объектов в гомогенных и гетерогенных кластерах.
-
Решение задачи выбора оптимального количества узлов кластера для выполнения параллельных алгоритмов: Флойда и «жадного» алгоритма на матричном матроиде.
-
Проектирование и реализация библиотеки эффективных параллельных комбинаторных алгоритмов.
Методы исследования. При выполнении диссертационной работы использовались теория множеств, теория графов, теория матрои-дов, линейная алгебра, технологии программирования.
Научная новизна работы состоит в следующем:
-
Предложен обобщенный метод распараллеливания алгоритмов генерации комбинаторных объектов (подмножеств л-элементного множества, Л-подмножеств, перестановок), дающий возможность повысить эффективность использования узлов гомогенного и гетерогенного кластеров.
-
Предложен способ учета производительности узлов гетерогенного кластера при выполнении параллельных алгоритмов генерации комбинаторных объектов, позволяющий сбалансированно распределять задачи между узлами данного кластера
-
Разработаны методы распараллеливания на основе параллелизма данных алгоритмов: Флойда и «жадного» алгоритма на матричном матроиде, - обеспечивающие эффективность реализаций за счет оптимальной загрузки узлов гомогенного и гетерогенного кластеров.
4. Разработан метод определения оптимального количества узлов кластера для выполнения параллельных алгоритмов: Флойда и «жадного» алгоритма на матричном матроиде, - дающий возможность учесть такие параметры кластера, как пропускная способность коммуникационной сети, производительность отдельных узлов кластера.
Практическая значимость работы заключается в следующем:
-
Разработана объектно-ориентированная библиотека параллельных алгоритмов генерирования и обработки комбинаторных объектов, позволяющая ускорить процесс разработки использующих генерирование и обработку комбинаторных объектов программ, программных комплексов и пакетов прикладных программ для гомогенных и гетерогенных кластеров.
-
С использованием разработанной библиотеки проведена экспериментальная оценка эффективности предложенных методов распараллеливания комбинаторных алгоритмов, показавшая почти линейный рост ускорения параллельных комбинаторных алгоритмов с увеличением числа используемых узлов кластера (в случае алгоритмов, работающих с матрицами, такой рост наблюдается при количестве узлов не больше расчетного).
Реализация и внедрение результатов работы. Результаты работы внедрены в НПФ «КРУГ» (г. Пенза).
Апробация работы. Основные положения и результаты работы докладывались на следующих конференциях: VI Международной научно-технической конференции «Новые информационные технологии и системы» (г. Пенза, 2004 г.); XI Всероссийской научно-технической конференции (г. Н. Новгород, 2004 г).
Основные положения, выносимые на защиту:
-
Методы распараллеливания алгоритмов генерации комбинаторных объектов: перестановок, подмножеств «-элементного множества, ^-подмножеств - на основе параллелизма данных.
-
Методы учета производительности узлов гетерогенного кластера для выполнения алгоритмов генерации.
-
Методы распараллеливания алгоритмов Флойда и «жадного» алгоритма на матричном матроиде на основе параллелизма данных для выполнения в гомогенных и гетерогенных кластерах.
-
Методы расчета оптимального числа используемых узлов кластера для работы параллельных алгоритмов: Флойда и «жадного» алгоритма на матричном матроиде.
-
Программные инструментальные средства, позволяющие ускорить процесс разработки программ, программных комплексов и пакетов прикладных программ, использующих генерирование и обработку комбинаторных объектов.
Публикации. По теме диссертации опубликовано 15 печатных работ, из них 6 статей и 9 тезисов. Результаты работы зарегистрированы в Отраслевом фонде алгоритмов и программ (получено 3 свидетельства).
Структура и объем диссертации. Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы, включающего 104 наименования, и 4 приложений. Основная часть работы изложена на 192 страницах машинописного текста и содержит 32 рисунка, 62 таблицы.
