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

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

r i =Ti / T ( 1.1 )

где Т - общая продолжительность работы системы, а Ti— время, в течение которого работало i-е устройство. Очевидно, что загрузка . Если загрузка устройста равна соответственно, то количество работы, выполняемой устройствами с быстродействием за единицу времни, равно

( 1.2 )

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

Последовательность случайных величин X₁, X₂, …, X_n принимающих значения из множества p ={1,2,…N}називают цепью Маркова с конечным числом состояний, если для всех n=1,2,…. и всех возможных значений случайных величин выполняется равенство [1]

(2.1)

Рассматриваемая последовательность случайных величин образует конечную цепь Маркова, если вероятность того, что следующее значение, равное Х_n. зависит только от текуцего значення X_n-1 и не зависит от предыдущих значений.

Пусть имеется физическая система S, которая может находиться в состояниях S₁, S₂, … S_n, причем переходы системы из состояния в состояние возможны только в фиксированные моменты t₁, t₂, …, t_n . Будем называть эти моменты шагами процесса и рассматривать случайный процесс, происходящий в системе S, как функцию целочисленного аргумента 1, 2 ..., k (номера шага). Обозначим через событие, состоящее в том, что после k шагов система находится в состоянии S_i. При любом k события образуют полную группу и несовместны. Процесс, происходящий в системе, можно представить как последовательность (цепочку) событий, например:

Такая случайная последовательность событий образует дискретную цепь Маркова с конечным числом состояний, если для каждого шага вероятность перехода из состояния S_i в состояние Sj не зависит от того, как система пришла в состояние S_i.

- вероятность (абсолютная) того. что система S на k-м шаге будет находиться в состоянии S_i. Назовем ее вероятностью состояния S_i, а вектор

( 2.3 )

- вероятность (условная) перехода из состояния S_i, в котором она находилась на (k-1)-м шаге, в состояние S_j на k-м шаге. Будем называть эти вероятности переходными вероятностями цепи Маркова.

, , ,(2.5)

В дальнейшем ограничимся рассмотрением процессов, описываемых однородными цепями Маркова, в которых условная вероятность (2.4) появления события на k-м шаге при условии, что на (k-1)-м шаге осуществилось событие не зависит от номера шага, т.е. переходная вероятность Pij зависит только от і и j.

1) множеством состояний S={S₁, S₂, … , S_n};

определяющим распределение вероятностей того, что в начальный момент времени t = 0 процесс находится в состояний S_i .

Случайный процесс (марковскую цепь) можно представить следующим образом: как будто точка, изображающая систему S, случайным образом перемещается (блуждает) по графу, перескакивая из состояния в состояние в моменти t₁, t₂, …, а иногда и задерживаясь какое-то число шагов в одном и том же состоянии.

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

т.е. вероятности всех состояний равны нулю, кроме вероятности начального состояния S_i, которая равна единице.

Найдем вероятности состояний после первого шага. Перед первым шагом система заведомо находится в состоянии S_i, значит, за первый шаг она перейдет в состояния S₁, S₂, …, S_n с вероятностями , записанными в i-й строке матрицы переходных вероятностей. Таким образом, вероятности состояний после первого шага будут:

Предположим, что известны вероятности застать систему в состоянии на k-м шаге. Тогда вероятность того, что система на (k+1)-м шаге окажется в состоянии S_j, находится по формуле полной вероятности

Таким образом, зная начальное распределение вероятностей состояний, по рекурентной формуле (2.8) можно определить распределение вероятностей состояний для любого шага k.

                                                    ( 2.9 )

применяя последовательно формулу (2.9) , начиная с k = 0. получим

                                       ( 2.10 )

                                    ( 2.11 )

если этот предел существует. Условие существования единственного предельного вектора (2.11) заключается в том, что для произвольного состояния цепи Маркова вероятность перейти в любое другое состояние за некоторое конечное число шагов должна быть отлична от нуля. Марковские цепи, обладающие этим свойством, называют неприводимыми и непериодическими. Необходимым и достаточным условием выполнения указанного свойства является требование положительности всех элементов n-й степени матрицы при некотором целом n [5].

Если условия существования и единственности вектора соблюдаются, то из (2.9) в пределе при получим систему уравнений для определения стационарных вероятностей состояний цепи Маркова:

                                                                ( 2.12 )

                                         ( 2.13 )

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

Поскольку матрица перехода является стохастической, т.е. для каждой ее строки выполняется условие (2.5), то отсюда следует, что матрица системы уравнений (2.12) вырождена. Так как ранг этой матрицы равен N - 1, т.е. имеет место линейная независимость между одним из уравнений системы и остальными, то нужное нам решение получаем с помощью дополнительного условия нормировки:

                                                                        (2.14 )

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

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

                                          ( 2.15 )

Данная формула задает геометряческое распределение длительностей времен пребывания в состоянии S_i.

Найдем среднее время пребывания в этом состоянии. Пусть время шага равно t, тогда среднее время пребывания T_i, в cостоянии S_i вычислим по формуле

             (2.16)

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

На временной диаграмме (рис. 1.5) до момента t₁ выполнялись команды АЛУ, а в момент t₁ - команда вывода. На интервале (t₁, t₂) передается и принимается выводимое слово в буфер. УУ выдает сигнал на печать слова из буфера ВНУ и выборку очередной команды программы. Заметим, что интервал времени (t₁, t₂) составляет небольшую часть времени выполнения команды АЛУ, и поэтому его обычно не учитывают при рассмотрении совместной работы АЛУ и ВНУ. На интервале (t₂, t₃) АЛУ и ВНУ работают одновременно. В момент t₃ в программе появляется команда обращения к рассматриваемому ВНУ. В этот момент оно занято. Поэтому на интервале (t₃, t₄) АЛУ простаивает, ожидая освобождения затребованного программой ВНУ. Его работа заканчивается в момент t₅ , после чего рассмотренный процесс может повториться. Мы описали совмещение работы АЛУ с одним из ВНУ, на самом же деле возможна совместная работа нескольких ВНУ. Временную диаграмму для общего случая можно построить аналогично.

S₁ - работает АЛУ, внешнее уcтройство не работает. В программе не было еще команды обращения к ВНУ, а если была, то ее выполненме закончилось (интервал 0t₁ на рис. 1.5);

S₂ - одновременно работает АЛУ и устройство вывода (интервал t₂,t₃)

S₃ - устройство вывода работает, АЛУ простаивает, так как появилась команда обращения к занятому устройству.

Предположим, что смена состояний возможна через интервалы времени, равные t - такту средней команды АЛУ. Будем считать известной вероятность появления в выполняемой программе команды, обрабатываемой АЛУ, которую обозначим через р₁, вероятность появления в очередной такт команды обращения к ВНУ обозначим через р₂. Очевидно, что в рассматриваемом случае имеет место равенство р₁ + р₂ = 1, так как эти два события образуют полную группу несовместных событий.

Среди внешних устройств, обслуживающих программу, будем различать устройства двух типов. Для первого из них время обслуживания запроса постоянно, например: печать числа, ввод перфокарты. Для второго это время является случайной величиной, например: запись на магнитную ленту или диск. В рассматриваемом примере примем, что длительность времен обслуживания запроса ВНУ имеют геометрическое распределение со средним, равним Т. Тогда по формуле (2.16) можно определить вероятность того, что в очередной такт ВНУ завершит обслуживание и вероятность того, что обслуживание будет продолжено в следующем такте r = 1-q, так как процесc марковский.

Для состояния S₁ уже установили, что в очередной такт возможно наступление одного из событий:

1) появление команды, обрабатываемой АЛУ; вероятноcть события р₁;состояние системы при этом не изменится;

2) появление команды обращения к ВНУ; вероятность события р₂; система перейдет в состояние S₁. Соответствующие переходы из состояния S₁ изображены на рис. 1.6,а.

Для состояния S₂ полная группа попарно несовместимых событий, наступление одного из которых возможно в очередном такте, содержит следующие четыре события:

1) очередная команда программы должна обрабатываться АЛУ, а ВНУ не закончило обслуживание запроса; вероятность наступления события равна ; состояние системы не изменится;

2) очередная команда программы - обращение к ВНУ и оно не закончило обслуживание запроса; вероятность события равна произойдет переход в состояние S₃;

3) очередная команда программы должна обрабатываться АЛУ и ВНУ закончило обслуживание запроса; вероятность события равна произойдет переход в состояние S₁;

4) очередная команда - обращение к ВНУ и оно закончило обслуживание предшествующего запроса; вероятность наступления события равна ; состояние системы не изменится.

Для состояния S₃ легко найти вероятности переходов. Граф цепи Маркова для рассматриваемой модели совмещения приведен на рис. 1.6,а. Непосредственно по графу составим уравнение для определения стационарных вероятностей состояний [см. (2.13)]

Составлены уравнения для состояний 1 и 3 с заменой уравнения для состояния 2 условием нормировки. Выразив из первых двух уравнений и через

,                     (3.1)

и подставив эти значения в условие нормировки, определим ,

                                (3.2)

Рассмотрим использование полученных вероятностных характеристик для оценки эффективности одновременной работы АЛУ и ВНУ. В п.1.2 было установлено, что стационарная вероятность состояния представляет собой долю времени, которое система находится в состоянии S_i. Поэтому загрузку АЛУ в соответствии с (1.1) можно определить формулой так как в состоянии S₁ и S₂ АЛУ работает, а загрузку ВНУ - соответственно . В рассматриваемом примере номинальная производительность АЛУ и ВНУ составляет соответственно и , поэтому системная производительность в соответствия с (1.2) будет равна

и                               (3.3)

Можно найти увеличение загрузки и реальной производительности устройств, обусловленное совмещением работы АЛУ и ВНУ. Посмотрим граф цепи Маркова, описывающий работу АЛУ и ВНУ без совмещения (рис. 1.6,б). В этом случае следует ввести два состояния S₁: АЛУ работает, ВНУ не работает и S₂: ВНУ работает, АЛУ ждет окончания работы ВНУ. Для стационарных вероятностей состояний и по графу рис. 1.6, б можно получить:

Загрузки устройств в этом случае будут равны и Если принять, например, что команды обращения к ВНУ встречаются в программе в тысячу раз реже, чем команды АЛУ, т.е. р₁=0,999 и р₂ = 0,001. а среднее время обработки одного запроса ВНУ равно времени выполнения тысячи команд АЛУ, т.е. q = 0,001 и r = 0,999, то загрузка АЛУ для модели с совмещением будет равна р₁ = 0,667, а без совмещения р₂ = 0,5. Выигрыш, как видно из примера, заметный. При работе с совмещением увеличивается загрузка ВНУ. Поскольку увеличиваются загрузки, то возрастает и системная производительность ВС, работающей в режиме совмещения. Из полученных в примере результатов не следует делать общих выводов. Для этого необходимо определить зависимость загрузки устройств от параметров реальных программ, определящих частоты появления команд АЛУ и обращений к ВНУ.

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

Перейдем к построению марковской модели совместной работы АЛУ и одного из ВНУ такого типа. Пусть, как и в предыдущем примере, смена состояний может происходить через интервалы времени t , равные средней продолжительности команд АЛУ, а время обслуживания запроса внешним устройством составляет k тактов, т.е.T = kt . Вероятности появления команд АЛУ и ВНУ в программе примем теми же, т.е. р₁ и р₂. Состояние системы в рассматриваемом случае должно содержать наряду с признаками, определяющими состояние каждого из ее устройств (работает или не работает), также время, оставшееся до окончания (или время, прошедшее с начала) обслуживания запроса ВНУ, если оно работает. Чтобы свести описанный случайный процесс к марковскому, определим состояние системы вектором (a, n), где компонента а определяет состояние АЛУ, а = 1 соответствует тому, что АЛУ выполняет команду, а = 0 - АЛУ простаивает, ожидая освобождения ВНУ. Временная компонента п определяет число тактов, оставшихся до окончания обслуживания запроса внешним устройством, .

Граф цепи Маркова для рассматриваемой модели приведен на рис. 1.7.

Состояние (1,0) соответствует тому, что АЛУ работает, а ВНУ простаивает. Если в этом состоянии в очередной такт появляется команда обращения к ВНУ, а вероятность события p₂, то начинает работать ВНУ, а АЛУ выбирает очередную команду программы. В этом случае происходит переход в состояние (1, k), в котором АЛУ продолжает, а ВКУ начинает работать, и до окончания обслуживания запроса внешним устройством осталось k тактов. Если очередной командой программы будет команда АЛУ (вероятность p₁), то АЛУ и ВНУ продолжат свою работу, произойдет переход в состояние (1,k-1), до окончания работа ВНУ останется (k-1) такт. Если очередная команда - обращение к ВНУ (вероятность р₂), то работа АЛУ прекращается до освобождения ВНУ, т.е. на (k-1) такт. В этом случае система перейдет в состояние (О, k-1). Переходы из остальных состояний можно рассмотреть аналогично. Получим непосредственно по ориентированному и связному графу рис. 1.7 уравнения для стационарных вероятностей состоянии с индексами, которые соответствуют обозначениям состояний. Уравнения для состояний и имеют вид

                                                                    ;            ;

                                                                                   ;

                                                                           ...                                     ....

                                                                          ;            ;

                                                                                         ;

                                                                           ...                                     ....

( 3.4 ):

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

(3.5)

Сложив уравнения записанные в первой и j-й строках, получим

;

,

Отсюда следует, что

(3.6)

Составим уравнение для состояния (1.0)

Подставляя выражение для по формуле (3.6), найдем

Вероятности всех состояний виражена через , которую сможем найти из условия нормировки

;

Подставляя сюда выражение для по формуле (3.7) и заменяя выражения, входящие под знак суммы по формуле (3.6), получим

( 3.9 )

так как в каждом из состояний, вероятности которых входят в правую часть выраження, АЛУ работает. После подстановки выражений по формулам (3.5), (3.8) и (3.9) получим

(3.11)

Вычислим значения p₁ и p₂ для тех же значений, которые были использованы в предыдущем примере, т.е. p₁=0,999, p₂ = 0,001. Чтобы среднее время обслуживания ВНУ, в предыдущем примере обозначенное через было равно времени обслуживания в рассматриваемом случае Т = kt. необходимо положить k=1000, так как q=0,001. Тогда по формулам (3.10) и (3.11) получим соответственно p₁=0.732, p₂ =0,735. Доля времени, когда работает только АЛУ, равна; в нашем случае = 0.265. Доля времени, когда работает только ВНУ, равна

(3.12)

Загрузка АЛУ в предыдущем примере, в котором длительности обслуживания ВНУ были распределены по геометрическому закону с тем же средним значением времени, что и в рассматриваемом примере, составила p₁= 0,667. Загрузка АЛУ при работе ВНУ, время обслуживания которого постоянно, больше на 10%. Поэтому следует учитывать, что заменяя обслуживащее устройство с постоянным временем, обслуживающим устройством с геометрическим распределением длительности обслуживания, будем получать меньшие загрузки. Эти выводы сделаны на основе рассмотрения одного числового примера и поэтому не могут считаться достаточно обоснованными.

Для примера построим графики зависимости загрузки АЛУ p₁ и ВНУ p₂ для каждой из трех рассмотренных моделей

Рис. 1.8. Графики загрузки АЛУ p1 и ВНУ p2: 1-без совмещения при q=0.001; 2- с совмещением при постоянном времени цикла ОП, k=1000

На рис.1.8 приведены графики зависимости загрузок АЛУ – p₁ и ВНУ – p₂, от вероятности р₁. появления в очередной такт команда АЛУ. По этим графикам можно заключить, что при работе в режиме совмещения существенно увеличиваются загрузки устройств.

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

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

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

2) чтения команды из памяти;

Если длительность некоторой i-й фазы обозначить через ti и если полагать, что полная длительность операции составит ,где n - полное число фаз выполнения операции (в рассматриваемом примере n = 5), то быстродействие процессора составит (операций/с)

В рассматриваемом примере все фазы операции выполняются разными функциональными узлами центрального процессора, кроме второй и четвертой фаз, которые выполняются ОП. Однако ОП в современных ЭВМ обычно состоит из нескольких модулей с независимым обращением, поэтому с большой вероятностью фазы 2 и 4 тоже вытолняются разными физическими устройствами. Обозначим время такта конвейера через и будем требовать, чтобы для любых выполнялось условие . Иначе, за время такта t выберем длительность наиболее продолжительной фазы операции, а разбивку на фазы произведем таким образом, чтобы никакие две последовательнне фазы не могли быть выполнены за один такт. Если последнее условие для некоторого i не выполняется. то две соседние фазы объединим в одну.

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

Фазы выполнения команды

Рис.1.9. Модель конвейерного процесса: а - структура процесса: б - временная диаграмма коивейерной работы

Количество фаз n, на которое разделено выполнение каждой операции, называется глубиной перекрытий. В каждом такте (кроме начальних и конечных) на конвейере находится одновременно п последовательных операций. Чем больше глубина перекрнтия, тем больший выигрыш в производительности может бать получен. В частности, из условия вытекает:

а из условия с следует, что

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

Примем, что ai=1 если i-й сегмент конвейера обрабатывает i-ю фазу команды, ai=0. Если на i-м сегменте нет команды для обработки.

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

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

первая ступень конвейера, в состоянии 2 - загружена первая и вгорая - ступени и т.д. В состоянии 5 все ступени конвейера работают. Если следующей командой является команда условного перехода (вероятность р), то в половине случаев переход осущоствляется на следующую команду и с такой же вероятностью к команде, не находящейся в конвейере. В последнем случае в конвейер поступает эта команда, а все находящиеся команды в конвейере не вьшолняются. На графе этой ситуации соответствует переход в состояние 1 с вероятностью р/2. Составим уравнение для стационарных вероятностей состояний:

, , ,

Используя условие нормировки , получим для стационарных вероятностей состояний формулы

;

В состоянии 5 через такт t происходит завершение вьшолнения команды конвейером. Таким образом, представляет среднее число команд, которые, завершаясь выполнением в течение тактa t покидают конвейер. Поскольку последняя (пятая) ступень конвейера загружена только в состоянии 5, то стационарная вероятность представляет собой загрузку этой ступени. За достаточно большой промежуток времени T последняя ступень будет работать в течение времени, равного ,за это время конвейер покинет команд выполнение которых конвейером будет завершено, производительность конвейера составит

При р = 0, когда в потоке нет команд перехода, получается предельная производительность конвейєра. При р = 1 в потоке только команда перехода получают самую низкую производительность конвейера.

Рассмотренная простая задача легко обобщается на конвейер с n ступенями, для которого легко получить, что

, и

и ,

а производительность конвейера будет равна

(4.1)

Р₀ - вероятность выполнения в очередной такт команды, не являющейся условным переходом;

P₁ - вероятность того, что происходит передача управлення на следущую команду в конвейере;

Р_i .- вероятность того, что переход на і ступени назад, ;

P_n - вероятность того, что переход происходит на команду, не находящуюся в конвейере.

Здесь . Граф переходов марковской модели для рассматриваемого рaспределения вероятностей P_i приведен на рис. 1.10,б. Уравнения для стационарных вероятностей в рассматриваемом примере имеют вид

, ,

Использовав условие нормировки, найдем

( 4.2 )

Задания для самостоятельной работы

1.1

1. Построить граф состояний цепи Маркова, описывающей совместную работу АЛУ и двух внешних устройств. Вероятности появлений в очередной такт команд обращения к каждому устройству равны Pi, i=1,2,3 соответственно. Вероятность того, что ВНУ завершит обслуживание запроса, равны q2q3 соответственно. Используя граф цепи, определить загрузки АЛУ и ВНУ. Провести анаиз, сравнив полученные результаты с результатами работы ЭВМ без совмещения.

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

3. Рассмотреть модель совместной работы АЛУи n одинаковых внешних устройств. Вероятность появления в программе команды АЛУ равна р, вероятность появления команды к юбому ВНУ равна r=(1-p)/n. Вероятность завершения обслуживания запроса в очередной такт любым ВНУ равна q.

4. Решить предшествующую задачу для случая, когда имеются две группы ВНУ, содержащие по n1 и n2 устройств соответственно. Каждая группа содержит одинаковое ВНУ с вероятностями завершения, равными q1 и q2. Вероятности появления запросов в программе к любому ВНУ первой группы равны r1, к ВНУ второй группы - r2.Учесть, что p + n1r1 + n2r2 = 1.

5. Рассмотреть модель совместной работы АЛУ и n внешних устройств с различными характеристиками pi и qi, i=1,n. Вероятность появления в программе команды АЛУ равна р0. Учесть, что р0+р1+...+рn=1.

1.2

1. Вывести формулу (4.2), определяющую производительность клнвейерного процессора с n ступенями.

2. Сравнить производительность конвейера с предугадыванием перехода, определяемую по (4.1), с производительностью конвейера по (4.2) и оценить полученное при этом увеличение производительности.