МОДЕЛ (774295), страница 3

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 3)

Лекция №8

Мы получили систему дифференциальных уравнений первого порядка:

(1)

(2)

(3)

Одно из этих уравнений необходимо отбросить и добавить уравнение нормировки:

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

Изменить

Если наблюдать за системой достаточно долго, то можно говорить о некотором стационарном поведении системы. Решается эта система достаточно сложно. Стационарные характеристики такой системы получаются достаточно легко: для n<¥ этот предел всегда существует, если же n®¥, то предел не всегда существует. Пусть , тогда взяв предел от левой и правой части каждого уравнения системы получим:

Следовательно:

(1*)

(2*)

(3*)

Решим получившуюся систему уравнений. Из (3*) => . Решаем (1*) и (3*) при i=1:

Отсюда следует:

ДЗ. Пусть l=m. Чему равняется вероятность пребывания в том либо в другом состоянии ? Чему равно среднее время выполнения команды этой системой.

Пусть n=¥. Чему равны Р_i при 1) l=m 2) l<m 3) l>m ? Чему равно среднее число команд в системе при n<¥ ?

Вложенные цепи Маркова.

Произвольная функция распределения.

Время одного из устройств описывается произвольной функцией распределения ( например ОП ), а время другого - экспоненциальным законом (ЦП). Если наблюдать за системой в любой момент времени t, то время выборки команды из ОП зависит от того, сколько она этим уже занималась. Существует прием, который позволяет решать такие системы, который заключается в том, что мы наблюдаем за системой не в любой малый интервал времени (Dt), а в «специальный». В качестве «специального» будем считать время, непосредственно перед появлением команды из ОП. Для описания системы введем вероятность Р_i - вероятность того, что в БП+ЦП находиться i команд в момент времени перед появлением очередной из ОП и q_i - вероятность того, что за время выборки одной команды ОП ЦП выполнит ровно i команд. Следовательно поведение системы может быть описано с помощью матрицы переходных вероятностей.

Номер столбца - состояние системы после завершения работы ОП и номер строки - состояние системы до появления команды из ОП. Предположим система находится в состоянии 0. Из этого состояния можно попасть только в состояние 0 или 1 с вероятностями 1-q₀ и q₀ соответственно. Если система находиться в состоянии 1, то из него она может попасть в состояние или 0, или 1 или 2 с вероятностями 1-q₀-q₁ и q₁ и q₀ соответственно и т.д.

При i=n+1 команда, которая должна быть считана из ОП не может поступить в БП, следовательно происходит блокировка работы ОП, при этом сама команда останется в ОП. После выполнения одной команды ЦП, система перейдет в состояние n, следовательно к таблице надо приписать еще одну строку:

Время блокировки равно времени выполнения, которое осталось для обслуживания команды в ЦП. Время пребывания системы в i-ом (i=0,1,2,...,n) равно времени выполнения одной команды ОП. Время пребывания системы в состоянии n+1 равно времени выполнения одной команды ОП плюс одной команды в ЦП.

Среднее время выполнения одной команды системой:

, где Т_ОР - среднее время выборки одной команды ОП, а 1/m - среднее время выполнения одной команды в ЦП.

Необходимо определить Р_n+1, если q_i известны. Для этого решим систему:

В этой системе одно уравнение линейно зависимо, следовательно надо отбросить любое уравнение и добавить уравнение нормировки.

Лекция №9.

Необходимо вычислить q_i. Время выборки команды из ОП является случайной величиной, подчиняющейся произвольной функции распределения F(t). Пусть время выборки одной команды равно t. Разобьем это время на m одинаковых интервалов по Dt (Dt*m=t). Вероятность того, что за время Dt будет выполнена ровно одна команда в условиях экспоненциального закона распределения, равна: . Вероятность того, что за время t выполнится ровно i команд, равна:

Экспоненциальный закон распределения

для случая «нелинейной» программы.

Рассмотрим команду условного перехода (УП), результатом ее выполнения может быть либо выполнение команды с меткой, указанной в команде УП, либо выполнение следующей (по написанию) команды за командой УП. Так как же быть в данной ситуации? Пусть мы в БП заносим следующие команды за командой УП, тогда только после выполнения команды УП будет ясно угадано направление или нет, если не угадано, то необходимо аннулировать все команды, которые были занесены в БП, и изменить АО. Опишем эту модель математически: любая команда, которая выполняется в ЦП, является с некоторой вероятностью командой перехода, а с дополнительной вероятностью - командой следования. Если в настоящее время выполняется команда условного перехода, то с некоторой вероятностью она не меняет порядок выполнения команд и с дополнительной - меняет, следовательно вероятность того, что надо будет уничтожать команды, находящиеся в БП, после выполнения одной из команд равна произведению вероятности того, что текущая команда является командой условного перехода, и вероятности того, что она изменит порядок выполнения команд. Обозначим ее через n.

Для стационарного случая:

ДЗ. Р_n+2(t)-?

Модель конвеерной обработки.

Средняя задержка команды на входе равна средней задержке команды на входе. Среднюю задержку (латентность) мы находим из графа переходов конвейера. Найдем нижнюю (L_min) и верхнюю (L_max) границу средней латентности (L).

Теорема: L_min£L£L_max, где L_max - число единиц в начальном векторе столкновений, а L_min находится из таблицы занятости - подсчитывается число меток в каждой строке и выбирается максимальное число.

Доказательство:

1. L_min£L. Пусть L - средняя латентность, тогда r=1/L - темп поступления или выдачи команд (количество инициаций). Введем к_i - коэффициент использования i ступени. Пусть d_i-число меток в i-ой строке. Оно характеризует, как использовать i-ый сегмент. будем считать, что это неравенство действует для любого числа i, т.е. , где

2. L£L_max. Докажем это утверждения для случая, когда граф состояний представляет собой простой, замкнутый цикл (простой цикл - это цикл в котором любое из состояний не повторяется). Докажем, что для такого цикла (жадная стратегия) L_max = числу единиц в начальном векторе столкновения. Рассмотрим модифицированный граф (только инициации). Обозначим за L₁ задержку при переходе от S₁ к S₂. L₁ - число единиц до первого нуля. В каждом состоянии существует свой вектор столкновения (S_i). Обозначим за L₁ задержку при переходе от S₁ к S₂. L₁ - число единиц до первого нуля. S₂ получается путем сдвига S₁ на L₁ позиций и прибавлением к нему начального вектора столкновений. Пусть x_i - число единиц в векторе столкновения, отвечающему i-ому состоянию. х - число единиц в начальном векторе столкновений.

Замкнем круг

Что и требовалось доказать.

Характеристики

Список файлов лекций