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

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

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

Графы являются другим важным классом комбинаторных объектов. Алгоритм Флойда предназначен для решения одной из важнейших задач на графах - задачи поиска кратчайших путей между всеми вершинами. К этой задаче можно свести решение других важных задач:

• поиск всех вершин, из которых можно достичь вершину i;

• поиск всех вершин, которые можно достичь из вершины i

• поиск максимально связных компонент: вершина входит в компоненту связности, если она достижима из всех вершин и если из нее достижимы все вершины;

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

Матроиды, и в частности матричный матроид, являются комбинаторными объектами, тесно связанными с оптимизацией. Сам матроид представляет собой множество элементов и множество его линейно независимых подмножеств. Жадный алгоритм на матричном матроиде определяет для данного матричного матроида, независимое подмножество с определенными свойствами, и может быть применен к решению задачи планирования экспериментов. [6, с.87]

Большинство комбинаторных алгоритмов характеризуются большим объемом производимых вычислений. Например, генерация перестановок множества из 15 элементов занимает более 8 часов на современных компьютерах тина P-IV, генерация подмножеств 40-элементного множества при тех же условиях - более 2 часов. Таким образом, повышение эффективности используемых алгоритмов является важной проблемой, решение которой, не может осуществляться в отрыве от знаний особенностей платформы, на которой данный алгоритм будет выполняться.

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

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

Таким образом, в любой задаче есть строго последовательные части, и части, позволяющие распараллеливание. Соотношение этих частей в программе определяет, насколько может быть увеличена скорость выполнения программы в параллельной архитектуре. Предположим, что в программе доля операций, которые нужно выполнять последовательно, равна f, где 0<=f<=1 (при этом доля понимается не по статическому числу строк кода, а по числу операций в процессе выполнения). Крайние случаи в значениях/соответствуют полностью параллельным (f =0) и полностью последовательным (f =1) программам. Тогда, для того, чтобы оценить ускорение S, которое может быть получено на компьютере из Р процессоров при данном значении/ можно воспользоваться законом Амдала [1, с. 124]:

Если 9/10 программы исполняется параллельно, а 1/10 - последовательно, то получить ускорение более, чем в 10 раз невозможно вне зависимости от качества реализации параллельной части кода и числа используемых процессоров (ясно, что 10 получается только в том случае, когда время исполнения параллельной части равно 0) [2, с. 75].

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

• быть потенциально распараллеливаемой;

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

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

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

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

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

2. в области создания параллельных алгоритмов наблюдаются усилия отдельных групп университетов и научных институтов. Результатами усилий являются разработанные библиотеки параллельных реализаций некоторых классов алгоритмов [4,5. с. 69]:

• ATLAS (Automatically Tuned Linear Algebra Software) - библиотека, позволяющая автоматически генерировать и оптимизировать численное программное обеспечение для процессоров с многоуровневой организацией памяти и конвейерными функциональными устройствами. Базируется на BLAS 3 уровня (Level 3). ATLAS требует некоторого времени для изучения основных параметров архитектуры целевого компьютера, а затем на основе этих параметров получает "оптимальный" код;

• Aztec - параллельная библиотека итерационных методов для решения систем линейных уравнений. Позволяет описывать части распределенной матрицы с использованием глобальной адресации;

• BlockSolve95 - Параллельная библиотека для решения разреженных систем линейных уравнений;

• DOUG (Domain decomposition On Unstructured Grids) параллельный решатель для finite element - систем, возникающих из дифференциальных уравнений с частными производными эллиптического типа;

• GALOPPS (Genetic ALgorithm Optimized for Portability and Parallelism System) - библиотека "обобщенных" генетических алгоритмов. Доступна многопоточная версия;

• JOSTLE - библиотека для распределения расчетов на сетках (mesh partitioning software);

• NAMD - параллельная объектно-ориентированная библиотека для
  расчетов в области молекулярной динамики;

• PSPARSLIB (А Portable Library of Parallel Sparse Iterative Solvers) библиотека параллельных итеративных решателей для разреженных линейных систем;

• PARMETIS - параллельная версия библиотеки METIS, включающей ряд алгоритмов над графами (parallel graph partitioning);

• PARPACK (Parallel ARPACK) - параллельная версия библиотеки ARPACK (Amoldi Package) для решения крупноразмерных задач собственных значений на Fortran 77;

• PBLAS - Параллельные версии базовых процедур линейной алгебры (BLAS), уровней 1, 2, 3. Библиотека разработана в рамках проекта ScaLAPACK;

• PETS с - Набор процедур и структур данных для параллельного решения научных задач с моделями, описываемыми в виде дифференциальных уравнений с частными производными;

• PGAPACK (Parallel Genetic Algorithm Library) - библиотека параллельных генетических алгоритмов;

• PLAPACK - Пакет параллельных процедур линейной алгебры Включает параллельные версии процедур решения систем линейных уравнений с помощью LU и QR-разложений, разложения Холецкого;

• Библиотека ScaLAPACK включает подмножество процедур LAPACK, переработанных для использования на МРР- компьютерах, включая: решение систем линейных уравнений, обращение матриц, ортогональные преобразования, поиск собственных значений и др.; SPRNG (Scalable Parallel Random Number Generators) параллельная библиотека генераторов случайных чисел для методов Монте-Карло.

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

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

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

Литература:

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

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

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

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

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

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

1988,-200с.