Московский Государственный Технический Университет

имени Н. Э. Баумана

Лобусов Е. C.

“Теоретические и алгоритмические основы параллельной

обработки”.

1999 г.

Содержание.

Введение…………………………………………………………………………..3

1. Способы организации параллельной обработки…………………………..…9

2. Способы описания алгоритмов обработки вычислительных сетей……….12

2.1. Предварительные математические сведения…………………………….12

2.1.1. Теоретико-множественные понятия…………………………………..12

2.1.2. Некоторые понятия теории графов…………………………………..14

2.1.3. Наиболее распространенные алгоритмы на графах………………....19

2.2. Представление алгоритмов обработки…………………………………...24

2.2.1. Представление численных процедур интегрирования……………....28

2.3. Представление вычислительных сетей…………………………………..32

2.3.1. Представление процессоров с совмещением вычислений и ввода-вывода……………………………………………………………………………...35

3. Методы отображения алгоритмов обработки……………………………….37

3.1. Статистические методы…………………………………………………...37

3.1.1. Распределение компонент алгоритма обработки…………………….37

3.1.1.1. Распределение алгоритмов обработки, основанных на методах численного интегрирования. …………………………………………………….42

3.1.1.2. Некоторые общие замечания по распределению…………………47

3.1.2. Составление расписания………………………………………………48

3.1.2.1. Составление расписания для процессоров с совмещением операций ввода-вывода………………………………………………………………....53

3.1.2.2. Составление расписания ля процессоров с совмещением операций ввода-вывода и квазипараллельной работой (обработкой)……………….54

3.2. Динамические методы……………………………………………………55

4. Программная реализация и сравнение параллельных алгоритмов………..60

5. Дискретное преобразование Фурье и его параллельная реализация………………………………………………………………………..61

5.1. Основные соотношения и алгоритмы ДПФ…………………………..…61

5.2. Алгоритмы ДПФ для однородных распределённых вычислительных структур……………………………………………………………………………63

Литература……………………………………………………………………….69

Введение.

Введение

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

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

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

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

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

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

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

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

Поэтому представим решение задачи отображения в виде трех уровней:

• математический (или уровень получения математического описания исходных данных );

• алгоритмический (или уровень нахождения алгоритма решения задачи отображения);

• программный (или уровень реализации найденного решения на сети).

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

Данное представление алгоритма обработки или вычислительной сети приводит к конкретной модели, обычно, в виде ориентированного графа.

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

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

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

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

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

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

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

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

Именно асимптотическая сложность алгоритма определяет в итоге размер задач, которые можно решить этим алгоритмом. Если алгоритм обрабатывает входы размера n за время cn², где с – некоторая постоянная, то говорят, что временная сложность этого алгоритма есть O(n²) (читается "порядка n²"). Точнее, говорят, что (неотрицательная) функция g(n) есть O(f(n)), если существует такая постоянная с, что g(n)  сf(n) для всех, кроме конечного (возможно пустого) множества, неотрицательных значений n.

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

Допустим, у нас есть пять алгоритмов А₁ – А₅ со следующими временными сложностями:

Алгоритм Временная сложность

А₁ n

A₂ nlog₂n

А₃ n²

А₄ n³

А₅ 2ⁿ

Здесь временная сложность – это число единиц времени, требуемого для обработки входа размера n. Пусть единицей времени будет одна миллисекунда. Тогда алгоритм А₁ может обработать за одну секунду вход размера 1000, в то время как А₅ – вход размера не более 9. В таб.1 приведены размеры задач, которые можно решить за одну секунду, одну минуту и один час каждым из этих пяти алгоритмов.

Таб.1 Границы размеров задач, определяемые скоростью роста сложности.

Предположим, что следующее поколение вычислительных машин будет в 10 раз быстрее нынешнего. В таб.2 показано, как возрастут размеры задач, которые мы сможем решить благодаря этому увеличению скорости. Заметим, что для алгоритма А₅ десятикратное увеличение скорости увеличивает размер задачи, которую можно решить, только на три, тогда как для алгоритма А₃ размер задачи более чем утраивается.