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

7.2. МОДЕЛИ И МЕТОДЫ

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

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

Принципы построения и свойства моделей. Модель - физическая или абстрактная система, адекватно представляющая объект исследования. В теории вычислительных систем используются преимущественно абстрактные модели - описания объекта исследования на некотором языке. Абстрактность модели проявляется в том, что компонентами модели являются не физические элементы, а понятия, в качестве которых наиболее широко используются математические. Абстрактная модель, представленная на языке математических отношений, называется математической моделью. Математическая модель имеет форму функциональной зависимости Y=F(X), где Y = {y1,...,yM} и X = {x1,..., xN} -

соответственно характеристики и параметры моделируемой системы и F - функция, воспроизводимая моделью. Построение модели сводится к выявлению функции F и представлению ее в форме, пригодной для вычисления значений Y=F(X). Модель позволяет оценивать характеристики Y для заданных параметров X и выбирать значения параметров, обеспечивающие требуемые характеристики, с использованием процедур оптимизации. Модель создается исходя из цели исследования, устанавливающей:

1)состав воспроизводимых характеристик Y = {y1,..., yM } ,

2)состав параметров X = { x1,..., xN}, изменение которых должно влиять на характеристики Y;

3)область изменения параметров xn е x*,n = 1,...,N, - область определения модели.

4)точность - предельная допустимая погрешность оценки характеристик Y на основе модели.

Состав характеристик Y определяется в зависимости от исследуемых свойств системы

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

модель в отношении задач, которые можно решать с ее использованием. Предельные допустимые погрешности оценки характеристик и точность задания параметров определяют требования к точности модели. Так, если изменения характеристик в пределах 10% несущественны для выбора того или другого варианта построения системы, то точность определения характеристик должна составлять ±5%. В большинстве случаев параметры, в первую очередь параметры рабочей нагрузки, могут быть заданы лишь приблизительно, с относительной погрешностью 10-25%. В таких случаях чет смысла предъявлять высокие требования к точности воспроизведения моделью характеристик системы и погрешности их оценки на уровне 5-15 % вполне приемлемы.

Модель, удовлетворяющая вышеперечисленным требованиям по составу характеристик и параметров и точности воспроизведения характеристик во всей области определения, называется адекватной системе. Свойство адекватности модели является относительным, связанным с целью исследования. Больше всего адекватность проявляется в точности воспроизведения характеристик системы моделью. Существенное влияние на адекватность оказывает область определения модели. Практически любая модель обеспечивает высокую точность воспроизведения характеристик в пределах малой окрестности точки X = {х1,...,xN}, но только высококачественные модели гарантируют

точность характеристик в широком диапазоне параметров X. Чем шире область определения модели, тем меньше шансов, что некоторая модель окажется адекватной системе.

Другое свойство модели - сложность. Сложность модели принято характеризовать двумя показателями: размерностью и сложностью вычислений, связанных с определением характеристик. Размерность модели - число величин, представляющих в модели параметры и характеристики. Так, если модель FA служит для вычисления двух характеристик, зависящих от 5 параметров, а модель FB - двух характеристик, зависящих от 10 параметров, то размерность модели FA равна 7, а модели Fn - 12 и модель FB рассматривается как более сложная. Сложность вычислений, выполняемых при расчете характеристик Y=F(X), оценивается числом операций, приходящихся на одну реализацию оператора Р. Обычно сложность вычислений связывается с затратами ресурсов ЭВМ и характеризуется числом процессорных операций и емкостью памяти для хранения информации, относящейся к модели. Сложность вычислений - монотонно возрастающая функция размерности модели. Поэтому более сложной модели присущи одновременно большая размерность и сложность вычислений.

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

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

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

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

Случайные величины, соответствующие параметрам, характеристикам и другим элементам моделей, могут представляться на разных уровнях, среди которых наиболее широко используются следующие четыре: 1) статистическая выборка а\,..., an,

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

Марковские модели. Основополагающими в теории вычислительных систем являются модели и аппарат теории марковских процессов. Марковским называется случайный процесс, состояние которого в очередной момент времени t + S зависит только от текущего состояния в момент времени t. Это означает, что поведение марковского процесса в будущем определяется текущим состоянием процесса и не зависит от предыстории процесса - состояний, в которых пребывал процесс до момента t.

В классе марковских процессов выделяют процессы с дискретными состояниями, называемые марковскими цепями. Когда множество состояний процесса S = {s...,sK}

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

цепь называют непрерывной; во втором - только в фиксированные моменты времени, обозначаемые порядковыми номерами t = 0,1,2,..., и цепь называется дискретной. Дискретная марковская цепь определяется:

1)множеством состояний S = sK}

2).матрицей вероятностей переходов (переходных вероятностной) характеризующей вероятности перехода процесса с текущим состоянием st в следующее состояние s,;

S2

SK

(7.3)

3) вектором начальных вероятностей (начальным распределением) ;г0 ={p{0),...,pK°j

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

находится в состоянии Sj.

Марковская цепь изображается в виде графа, вершины которого соответствуют состояниям цепи и дуги - переходам между состояниями. Дуги (j, ,), связывающие вершины st и S}, отличаются вероятностями переходов pjj. На рис. 7.2 представлен граф марковской

цепи с множеством состояний S = {s1,..., s5}, матрицей вероятностей переходов