Ориентированная задержка цикла. Уравновешенный цикл

Задание вектора реализации порождает некоторый вектор задержек . В этом случае величину невязки - можно трактовать как время незапланированного простоя в процессе использования в качестве аргумента -ой операции результата, полученного -ой операцией. Аналогичная трактовка имеет смысл и в случае произвольного вектора задержек . Если какой-то результат не используется, то его надо где-то хранить, поэтому невязки - характеризуют времена дополнительного хранения данных, как входных, так и промежуточных, обусловленные взаимной «несогласованностью» развертки и вектора задержек . Согласно утверждению 6, временная развертка минимизирует каждое из таких времен.

Выясним, какие свойства графа алгоритма приводят к совместимости системы (3).

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

Пример. Пусть . На рис.15.1(а) дан пример уравновешенного цикла, а на рис. 15.1(б) – неуравновешенного.

 

2. Условие совпадения множеств и с точностью до параллельного переноса

Утверждение 7. СЛАУ (3) совместна тогда и только тогда, когда все циклы графа алгоритма уравновешены, или граф алгоритма не имеет циклов.

Доказательство. Предположим, что СЛАУ (3)

 

-

 

совместна и вектор задает ее решение. Выберем в графе алгоритма любой цикл, если он в нем имеется, и установим направление обхода. Каждому проходу -ой дуги в положительном направлении поставим в соответствие равенство - , каждому проходу той же дуги в отрицательном направлении поставим в соответствие равенство - . Просуммируем все равенства согласно обходу дуг цикла. В правой части суммы будет стоять ориентированная задержка цикла. Левая часть суммы будет равна нулю, т.е. цикл уравновешенный. Действительно, при каждом проходе соседних дуг цикла инцидентная им вершина учитывается дважды. Соответствующая этой вершине величина всегда будет встречаться в двух соседних или последнем и первом уравнениях также дважды: сначала со знаком «+», а затем со знаком «-» (рис.15.2). На рис.15.2(а): дуге соответствует - , следующей дуге : - . При сложении в левой части взаимно уничтожается.

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

Пусть теперь граф алгоритма либо не имеет циклов, либо все его циклы уравновешены. Покажем, что СЛАУ (3) будет совместной. Не ограничивая общности будем считать граф алгоритма односвязным. Возьмем, например, первую вершину и припишем какое-нибудь значение. Предположим, что построен односвязный подграф, и его вершинам приписаны такие значения , что уравнения из (3) выполняются для всех дуг подграфа. Добавим новую дугу, у которой хотя бы одна вершина принадлежит построенному подграфу. Если вторая вершина не принадлежит подграфу, то соответствующее ей значение однозначно определяется из того уравнения (3), которое соответствует добавленной дуге.

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

Решение системы (3) в случае односвязности графа однозначно определяется при фиксации значения любой из его координат и остается решением при добавлении вектора (1,1,...,1).