Вектор временной развертки, обобщенной временной развертки

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

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

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

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

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

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

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

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

Если определены какие-то ограничения на параметры вычислительных систем, то тем самым определяется во множестве какое-то подмножество временных разверток. Например, задание вектора или определяет подмножества или . В свою очередь в подмножествах , выделяются подмножества в зависимости от векторов начальных условий. Возможны и другие ограничения. Ясно, что в рассмотренных случаях , , а также = для некоторого вектора , выбираемого по вектору . Все эти множества и подмножества зависят от рассматриваемого алгоритма.

Время реализации алгоритма

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

Алгоритмы, считавшиеся эффективными на однопроцессорных ЭВМ, нередко становятся очень неэффективными на многопроцессорных системах.

Как оценивать время реализации алгоритма? Очевидно, что прямое его измерение на конкретной ЭВМ дает возможность сравнивавть временные характеристики различных алгоритмов только по отношению к данной ЭВМ. По отношению к другой ЭВМ аналогичное сравнение, вообще говоря, дает другие результаты. Поэтому необходимо абстрагироваться от вычислительной системы. Для однопроцессорных ЭВМ это происходит за счет сравнения количества арифметических операций. Формально можно считать, что число операций – это время реализации алгоритма на абстрактной однопроцессорной машине, у которой время реализации любой операции равно 1, а время выполнения всех других процедур (ввод-вывод данных, взаимодействие с памятью, передача данных по каналам связи и т.п.) равно 0. При этом предполагается, что операции выполняются подряд без какого-либо простоя в работе ЭВМ.

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

Есть одно принципиальное отличие между абстрактной последовательной ЭВМ и граф-машиной. Именно, на первой реализуются все алгоритимы, на второй – только один.

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

 

Вопросы

1. Можно ли любой ориентированный ациклический граф считать графом некоторого алгоритма? Почему?

2. Как должны соотносится между собой время работы алгоритма и время, которое затрачивается на его анализ?

3. В чем состоит основная проблема анализа алгоритмов при помощи соответствующих им графов?

4. Что представляет из себя вектор обобщенной временной развертки, чем он отличается от вектора временной развертки?

5. Что такое вектор реализации алгоритма? Когда вектор реализации нулевой?

6. Как временная развертка определяет время появления и время существования информации?

7. Как определяется время задержки информации на дуге? Определение вектора задержек.

8. Какие временные ограничения возникают в процессе ввода-вывода информации? Как формируется вектор начальных условий?

9. Как связаны между собой , , ? Пояснить.

10. От чего зависит время реализации алгоритма на вычислительной системе?

11. Есть ли прямая связь между эффективностью алгоритма на однопроцессорных ЭВМ и многопроцессорных системах? Пояснить.

 

Литература

1. Воеводин В.В. Параллельные вычисления / В.В.Воеводин, Вл.В.Воеводин. — СПб.: БХВ-Петербург, 2002. — 608 с.

2. Харари Ф. Теория графов / Ф.Харари; пер.с англ. В.П.Козырева. — М.: Мир, 1973. — 300 с.

3. Уилсон Р. Введение в теорию графов / Р.Уилсон. — М.: Мир, 1977. — 207 с.

4. Кристофидес Н. Теория графов. Алгоритмический подход / Н.Кристофидес. — М.: Мир, 1978. — 432 с.

5. Новиков Ф.А. Дискретная математика для программистов / Ф.А.Новиков. — СПб.: Питер, 2006. — 364 с.

6. Иванов Б.Н. Дискретная математика. Алгоритмы и программы / Б.Н.Иванов. — М.: Лаборатория Базовых Знаний, 2001. — 288с.