Пространственно-временные развертки.

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

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

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

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

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

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

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

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

Будем считать, что пространственно-временные развертки обладают определеными свойствами гладкости.

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

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

Системам поверхностей уровней одной пространственно-временной развертки определяет некоторую параллельную форму алгоритма.

 

Вопросы

1. Что характеризует время дополнительного хранения данных?

2. Что называется ориентированной задержкой цикла?

3. Какой цикл называется уравновешенным?

4. Сформулировать и доказать критерий совпадения множеств и с точностью до параллельного переноса.

5. Какие временные развертки называются пространственно-временными?

 

Литература

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

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

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

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

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

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