Таб.2 Эффект десятикратного ускорения.

Алгоритм	Временная сложность	Максимальный размер задачи
		до ускорения	после ускорения
А1 A2 A3 A4 A5	n nlog2n n2 n3 2n	s1 s2 s3 s4 s5	10s1 Примерно 10s2 для больших s2 3,16s3 2,15s4 s5+3,3

Вместо эффекта увеличения скорости рассмотрим теперь эффект применения более действенного алгоритма. Вернемся к таб.1. Если в качестве основы для сравнения взять 1 мин, то, заменяя алгоритм А₄ алгоритмом А₃, можно решить задачу большую в 6 раз большую, а заменяя А₄ на А₂, можно решить задачу, большую в 125 раз. Эти результаты производят гораздо большее впечатление, чем двукратное улучшение, достигаемое за счет десятикратного увеличения скорости. Если в качестве основы для сравнения взять 1 ч, то различие оказывается еще значительнее. Отсюда мы заключаем, что асимптотическая сложность алгоритма служит важной мерой качественности алгоритма, причем такой мерой, которая обещает стать еще важнее при последующем увеличении скорости вычислений.

Не вдаваясь в детали обсуждения, можно сказать, что по сложности получения решения все дискретные задачи делятся на два класса. В класс Р (Polynomial – полиномиальный) входят задачи, решение которых находится за полиномиальное число переборов от характерного размера задачи. В класс NP (Nonpolynomial – неполиномиальный) входят все переборные задачи. Очевидно, что P NP. В классе NP имеются задачи, решение которых может быть найдено с помощью перебора всех вариантов, но относительно которых неизвестно, можно ли найти их решение за полиномиальное число переборов. Более того, в классе NP выявлены так называемые универсальные (NP – сложные, NP – полные) задачи, к которым полиномиально сводится любая задача из NP. В настоящее время установлена универсальность многих задач, эквивалентных между собой с точностью до полиномиальной сходимости. Если бы удалось доказать, что хотя бы одна такая задача принадлежит классу Р, то тем самым было бы доказано, что Р совпадает с NP, и можно было бы в принципе надеяться на построение эффективных методов решения различных классов дискретных задач. Опыт решения дискретных задач дает основание считать, что NP – сложные задачи и задачи из класса Р сильно различаются по трудоемкости решения, но в строгом смысле это различие не доказано.

К сожалению, нужно констатировать, что среди рассмотренных нами задач на графах имеются NP – сложные. Пусть заданы два графа G₁=(V₁,E₁), G₂=(V₂,E₂) и ставится вопрос: можно ли из графа G₁ получить граф G₂ с помощью операций простого гомоморфизма? Пользуясь нашей терминологией, этот же вопрос можно задать иначе: можно ли алгоритм, заданный графом G₁, эффективно реализовать на вычислительной системе, заданной графом G₂? Оказывается, что эта задача является NP – сложной даже в том случае, когда граф есть треугольник G₂. Среди NP – сложных задач она известна как задача "гомоморфизм графов".

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

Прежде чем делать окончательные выводы, полезно понять, откуда все же возникает NP – сложность задач в наших исследованиях и появляется ли она по существу или из-за того, что мы недостаточно хорошо знаем задачи, которые собираемся решать. Вернемся снова к задаче "гомоморфизм графов". Ее NP – сложность доказана в том случае когда графы G1 и G2 произвольные. Напомним, что G₁ есть граф алгоритма.. Если допустить, что этот граф является произвольным, то записать соответствующий алгоритм можно, лишь записав независимо друг от друга все операции и связи между ними. В практической деятельности не приходится иметь дела с большими алгоритмами подобного рода, причем именно потому, что их невозможно записать в компактном виде. Поэтому используемые в действительности алгоритмы нельзя отнести к произвольным. Они обладают рядом характерных отличий, связанных, например, с существованием периодически повторяемых участков вычислений. Следовательно, есть основания предполагать, что изучая реальные алгоритмы и выделяя их специфику, удастся избежать NP – сложности больших дискретных задач и найти эффективные методы решения общей задачи, по крайней мере в практически важных случаях.

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

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

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

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

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

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

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

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

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

К особенностям функционирования этой схемы взаимодействия следует отнести:

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

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

Посылка сообщений обычно выполняется посредством копирования содержимого блока памяти одного процессора в память другому, используя некоторые средства взаимодействия. Однако этот способ, несмотря на его простоту, достаточно медленный для больших сообщений. По этой причине в большинстве случаев использовались прерывания процессора для получения доступа в память – так называемый прямой доступ в память (ПДП). Оригинальное объединение процесса копирования из памяти в память и одновременное исключение обоих процессоров из обмена, реализованное фирмой INMOS, привело к созданию линка. Линк - это высокоскоростной канал (» 20 Мбит/с) с двумя контроллерами прямого доступа в память (один для ввода и один для вывода). В линке осуществляется двухточечная связь или соединение одного процессора с другим или некоторым устройством, снабженному линком. Теперь уже не требуется никакого арбитража по доступу к разделяемым данным.

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

К особенностям данной схемы взаимодействия следует отнести:

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

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

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

2