Дисциплина Моделирование элементов вс

Марковская модель вычислительных процессов.

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

матрицей вероятностей переходов

и распределением вероятностей (a₀,…,a_H₊₁) состояний S₀,…,S_H₊₁ в момент времени 0.

Элементы P_ij матрицы P определяют вероятности перехода процесса из состояния S_i в состояние S_j, т.е. вероятности того, что процесс, находящийся в состоянии S_i в следующий момент времени будет находиться в состоянии S_j. Матрица P – стохастическая матрица, построчные суммы элементов которой .

Вероятности a_i определяют первое возможное состояние S_t₀ процесса. Будем считать, что вычислительный процесс развивается следующим образом. Процесс начинается с состояния S₀, т.е. программа начинает выполняться с этапа счета. Этап ввода-вывода может быть инициирован только процессором, т.е. может следовать только за этапом счета. Это одновременно означает, что после каждого этапа ввода-вывода следует этап счета. В таком случае вероятности начальных состояний (a₀,a₁,a₂,…,a_H₊₁)=(1,0,0,…,0) и матрица вероятностей переходов

Из состояния счета S₀ процесс с соответствующей вероятностью может перейти в состояния S₁,…,S_H, представляющие собой этапы обращения к файлам F₁,…,F_H, или в поглощающее состояние S_H+1. Из состояний S₁,…,S_H процесс с вероятностью 1 возвращается в состояние счета S₀. Достигнув поглощающего состояния S_H₊₁ процесс с вероятностью 1, навсегда остается в нем. Порядок смены состояний можно представить на графе марковской цепи. Переходы между состояниями S₀,…,S_H₊₁ представляются на графе дугами, на которых обозначены вероятности переходов, отличные от 1.

З
начения вероятностей P₀₁,…,P_0,_H₊₁ предопределяют ход вычислительного процесса и зависят от параметров трудоемкости алгоритма. Эти значения вычисляются следующим образом. Трудоемкость алгоритма определяет, в частности, среднее число N₁…N_H обращений к файлам F₁,…F_H. Следовательно, среднее число переходов из состояния S₀ в состояние S₁…S_H должно быть (N₁+…+N_H). Один раз процесс переходит из состояния S₀ в поглощающее состояние S_H₊₁.Таким образом, вычислительный процесс должен выходить из состояния S₀ в среднем раз, т.е. в процессе реализации алгоритма этапы счета встречаются в среднем N раз. Значение P₀_h определяет долю переходов в состояние S_h по отношению к всевозможным переходам из состояния S₀ в состояния S₁…S_H₊₁.

Эта доля равна в среднем N_h/N, где N_h- среднее число переходов в состояние Sh. Следовательно:

P_0, _h=N_h/N, h=1,2…H

P_0,H+1=1/N.

Количество работы, выполняемой на каждом из этапов, характеризуется параметрами ₁,…, _H алгоритма. Значение  определяет среднее количество процессорных операций, выполняемых за одну реализацию алгоритма, и значения ₁,…, _H – среднюю трудоемкость этапов, соответствующих состояниям S₁…S_H. Средняя трудоемкость этапа счета

₀=/N, где N-среднее число этапов счета.

Трудоемкость каждого этапа будем рассматривать как случайную величину _h с математическим ожиданием _H, h=0,1,…,H.

Т
аким образом, под моделью вычислительного процесса будем понимать марковскую цепь с (H+2) состояниями, начальным состоянием S₀ и матрицей вероятностей переходов. Реализация вычислительного процесса – случайная последовательность состояний S₀,S_t₁,S_t₂,…,S_tm, порядок смены которых определяется в вероятностном смысле матрицей вероятностей переходов. С состояниями S₀…S_H связано определенное количество работы, характеризуемое значениями случайных величин ₀…_H соответственно. Диаграмма вычислительного процесса, порождаемого марковской моделью имеет вид:

Значение _i^j определяет трудоемкость соответствующего этапа и представляет собой j-е значение случайной величины _i, математическое ожидание которой _i . В данном случае состояние S₃ является поглощающим: достигнув его, процесс прекращается.

Рассмотрим пример. Пусть задан алгоритм, трудоемкость которого характеризуется следующими параметрами:

=100 млн. операций;

N₁=19 обращений к файлу F₁;

N₂=180 обращений к файлу F₂;

₁=2000 байтов;

₂=500 байтов за обращение к файлу.

Построим марковскую модель вычислительного процесса, порождаемого этим алгоритмом. Среднее число этапов счета при одном прогоне алгоритма N=N₁+N₂+1=200. Вероятности перехода процесса из состояния счета S₀ в состояния S₁,S₂ и S₃ равны соответственно:

P₀₁=N₁/N=19/200=0,095

P₀₂=N₂/N=180/200=0,9

P₀₃=1/N=1/200=0,005

Подставляя эти значения, получаем следующую матрицу вероятностей переходов:

Из матрицы видно, что с вероятностью 0,095 за этапом счета произойдет обращение к файлу F1, с вероятностью 0,9 – F2, и с 0,005 – вычислительный процесс прекратится. Средняя трудоемкость этапа счета ₀=/N=100/200=0,5 млн. операций.

Оценка трудоемкости алгоритмов методами теории марковских цепей.

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

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

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

Приведем пример графа алгоритма:

У
словимся, вершины графа обозначать номерами 0,1,2,…,К. О - соответствует начальной вершине графа, К – конечной вершине; 1,2,…,К-1 идентифицируют операторы алгоритма. В программировании графы алгоритмов изображаются с использованием набора фигур, обозначающих тип оператора, и называются схемами алгоритмов.

Граф выделяет структуру алгоритма, определяет множество операторов

V={V₁, V₂, …, V_k-1}

и множество дуг, связывающих операторы

D={(i, j)} i=0, 1, …, K-1 j=1,2,…,K

Для оценки трудоемкости алгоритма необходимо:

Разбить множество операторов на классы:
- основных операторов

S₀={V_₁, V_₂, …, V__m₀} V__kV

операторов ввода-вывода

S_h={V_₁,V_₂, …, V__mh} h=1,2,…,H каждый из этих операторов задает обращение к одному и тому же файлу F_h.

Для каждого основного оператора V_ необходимо определить среднее количество операций k_, составляющих оператор, и для каждого оператора ввода-вывода V_ - среднее количество информации h_, передаваемой при выполнении оператора.
Переходы между операторами V_i и V_j следует рассматривать как случайные события и характеризовать их вероятностями P_ij, т.е. каждая дуга (i,j) графа алгоритма должна быть отмечена вероятностью перехода P_ij, с которой переход из вершины V_i выполняется именно по этой дуге, т.е. к вершине V_j.

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

, I=0,1,2,…,К-1

Значения P_ij определяются вероятностями значений предикатами. Другими словами, вероятности P_ij зависят от вероятностей выполнения условия, проверяемого оператором i с целью выбора пути перехода. Например, пусть оператор 2 порождает переход к оператору 3 при отрицательном значении некоторой переменной Х и к оператору 4 при Х0. Если известно, что величина Х равномерно распределена в диапазоне (-1;+3), то с вероятностью 0,25 ее знак отрицателен и с вероятностью 0,75 положителен. Из этого следует, что переход к оператору 3 происходит с вероятностью Р_2,3=0,25 и переход к оператору 4 – с вероятностью Р_2,4=0,75. Пусть далее оператор 7, замыкающий цикл, порождает переход к оператору 1 в девяти случаях, а в одном случае переход происходит в конец алгоритма (цикл, начинающийся от оператора 1 и заканчивающийся оператором 7, выполняется 10 раз). Тогда вероятности переходов P_i_,1=0,9 P_i_,_k=0,1. Если за оператором i непременно выполняется оператор j, то P_ij=1. Пусть П₁,П₂,…,П_К-1 – среднее число обращений к операторам V₁,V₂,…,V_K-1 за один прогон алгоритма. В таком случае характеристики трудоемкости могут быть вычислены следующим образом:

среднее число операций, выполняемых при одном прогоне алгоритма

среднее число обращений к файлу F_h

(h=1,2,…,H)

среднее количество информации, передаваемое при одном обращении к файлу F_h

В последних выражениях суммирование выполняется по всем вершинам, относящимся к классу основных операторов S₀ или классу операторов ввода-вывода S_h, обращающихся к файлу F_h.

Таким образом, для оценки трудоемкости алгоритма необходимо определить среднее число обращений n₁,n₂,…,n_k-1 к операторам. Допустим, что вероятности переходов Pkj постоянны и после выполнения оператора Vk (k=1,2,…,k-1) переход к следующему оператору определяется только распределением вероятностей Pkj, т.е. не зависит от хода вычислительного процесса в прошлом – до перехода к оператору Vk. При указанных допущениях процесс выполнения алгоритма является марковским процессом с К состояниями S₁,S₂,…,S_k соответствующими пребыванию процесса в вершинах V₁,V₂,…,V_k алгоритма. Состояния S₁,S₂,…,S_k-1- невозвратные (процесс после какого-то числа шагов непременно покидает их), состояние Sk – поглощающее (достигнув его, процесс прекращается). Начальным является состояние Si, определенное дугой (0,i), выходящей из начальной вершины графа. Для упрощения обозначений условимся, что i=1, т.е. начальное состояние – S1. Порядок изменения состояний определяется графом алгоритма, дуги которого отмечены вероятностями переходов Pij. Отмеченный граф алгоритма можно рассматривать как граф марковской цепи.

Среднее число П₁,П₂,…,П_k-1 пребывания марковского процесса в невозвратных состояниях S₁,S₂,…,S_k-1 определяется корнями системы линейных алгебраических уравнений

n_i=_1,i+ (i=1,2,…,k-1), где _1,i – символ Кронекера _1,i=

Система этих уравнений строится исходя из следующих соображений. Значение n_i будет равно, по крайней мере, одному, если процесс начинается от состояния с номером i=1, что отмечено символом _1,i. В остальных случаях процесс попадает в состояние Si только из других состояний j=1,2,…,k-1 с вероятностью Pij. Если процесс находился в состоянии j n_j раз и Pji0, то процесс из этого состояния попадет в состояние i в среднем P_ijn_j раз. Суммированием значений P_ijn_j по всем j находится число попаданий процесса в состояние из всех других состояний j. Значения П₁,П₂,…,П_k-1 определяются решением системы линейных алгебраических уравнений, каноническая запись которой имеет вид:

(p_1,1-1)n₁+p_2,1n₂+…+p_k-1,1n_k-1= -1

p_1,2n₁+(p_2,2-1)n₂+…+p_k-1,2n_k-1=0

…………………………………

p_1,k-1n₁+p_2,k-1n₂+…+(p_k-1,k-1-1)n_k-1=0

Для примера определим трудоемкость алгоритма, заданного ранее приведенным графом. Для простоты примем, что все операторы алгоритма – основные (операторы ввода-вывода отсутствуют) и количество операций Ki, порождаемых каждым оператором, постоянно и равно 1.

На основе графа и формы строим систему из семи линейных алгебраических уравнений:

-n₁+0,9n₂=-1

n₁-n₂=0

0,25n₂-n₃=0

0,75n₂-n₄=0

0,5n₃+0,2n₄-n₅=0

0,8n₄-n₆=0

0,5n₃+n₅+n₆-n₇=0

Решая систему, определяем среднее число попаданий вычислительного процесса в состояния S₁,S₂,…,S₇:

n₁=10; n₂=10;n₃=2,5; n₄=7,5; n₅=2,75; n₆=6; n₇=10.

Подставляя полученные значения, получаем оценку трудоемкости алгоритма:

n_i=10+10+2,5+7,5+2,75+6+10=48,75

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

следующая страница >>