1.5. О моделировании вычислительных систем
Переходя к моделированшо вычислительных систем, что является основным содержанием книги, следует определить, прежде всего, предмет нашего изучения.
Как пишет известный голландский Математик Э.Дейкстра (Edsger W. Dijkstra), имея дело с ЭВМ, можно вьшелить как бы две «машины». С одной стороны, есть физическая машина (компьютер), которая требует обслуживания, питания, поддержания температурного режима. Она может ломаться и давать сбои.
С другой стороны, есть абстрактная машина, как она определена своей системой команд и архитектурой, «воображаемая» машина, для которой программист пишет программы и по отношению к которой решается вопрос о правильности программ.
Какая из них истинная? С точки зрения потребителя (пользователя, программиста), истинной является абстрактная машина, а назначение физической машины — быть «работающей моделью», аккуратно и быстро имитировать все действия, предусмотренные в абстрактной машине. Если исключить функции, выполняемые абстрактной машиной, то на долю физической машины остаются вопросы электроники и микросхемотехники элементов и узлов, их электропитания, тепловых режимов, вопросы надежности, конструирования и другие инженерные вопросы.
Отсюда следует, что для описания функционирования ЭВМ и образованных на их базе вычислительных систем требуется целый спектр моделей, которые студенты изучают в курсах электроники и схемотехники, проектирования цифровых устройств и других
Наш курс имеет дело с моделями абстрактных машин и систем, т.е. с их функциональными описаниями. Однако современные вычислительные машины, базирующиеся на больших сверхбольших интегральных схемах, настолько сложны что их полное функциональное описание практически (хоть и конечно). В то же время функционирование вычислительных систем в значительной мере определяется исполняемыми программами и не требуют описвния с точностью до машинных команд. При этом рассматриваются гораздо более крупные единицы работы — программные модули, задачи, задания [7].
Исходя из сказанного, вычислительные системы можно по традиции отнести к классу дискретных динамических систем, которые называют конечными автоматами. Автомат является математической абстракцией системы обработки информации. Автомат имеет конечное число входов, воспринимающих дискретную информацию, т.е. информацию, изображаемую я конечным числом символов из некоторого алфавита, и конечное число выходов для выдачи информации. Переработка информации осуществляется в дискретном времени, т.е. во времени, представленном в квантованной шкале.
Процесс переработки может быть разбит па этапы, каждый из которых характеризуется некоторым состоянием, в котором находится автомат. Автомат часто представляют сетями, т.е. графами со специальной интерпретацией вершин и дуг.
Понятие конечного автомата связано с понятиями алгоритма и последовательной работой системы. Для них характерен последовательный способ функционирования: система (автомат) последовательно переходит из состояния в состояние в соответствии с заданной функцией перехода и осуществляет очередной шаг алгоритма.
По мере усложнения дискретных систем все большее внимание привлекают «алгоритмические» параллельные системы с недетерминированным поведением, в которых отдельные компоненты функционируют, в основном, независимо, взаимодействуя друг с другом время от времени. Примером могут служить системы параллельной обработки информации: конвейерные и многопроцессорные вычислительные машины, параллельные программы, моделирующие параллельные дискретные системы, мультипрограммные операционные системы, асинхронные электронные схемы, системы телекоммуникаций.
Параллельно и асинхронно функционирующие системы не описываются адекватно в терминах классической теории конечных автоматов. Такие фундаментальные понятия, как состояние автомата (состояние системы) и функция перехода, неудобны для наглядного и экономного описания систем с локальными связями между независимыми параллельными процессами.
В случае систем с параллелизмом и тогда, когда нас интересует не только и не столько функция, реализуемая системой, а ее структурные характеристики и свойства, модель системы должна быть структурно подобна самой системе. При этом модель можно строить по частям, как и систему. Глобальные функции и лонятия могут определяться на основе локальных функций отдельных компонентов или подсистем; связи и отношения между фрагментами модели подобны связям и отношениям между фрагментами системы. Наконец. немаловажным фактором является возможность представления моделей систем в форме, удобной и эффективной для обработки их с помощью ЭВМ.
Таким образом, мы видим, что возможны две концепции моделирования вычислительных систем, которые мы назовем, соответственно, концепцией состояния и концепцией взаимодействия.
Предметом настоящего курса являются модели вычислительных систем (ВС), с точки зрения их функционирования, построенные на основе обеих концепций.
В ВС выделяются следующие составляющие:
- технические средства, определяемые конфигурацией системы (составом устройств и структурой связи между ними);
- режим обработки, определяемый операционной системой и задающий порядок функционирования системы;
- рабочая нагрузка, характеризующая класс обрабатываемых задач и порядок их поступления в систему.
В том случае, когда ЭВМ, вычислительный комплекс, система или сеть исследуются в целом как органическое единство. составляющих во взаимодействии с окружающей средой и при этом проявляются общесистемные свойства и характеристики, говорят, что исследование проводится на системном уровне, и это — наиболее характерная черта теории ВС.
Рассмотрим некоторые из типовых задач возникающих при моделировании ВС.
Задачи анализа. Анализ ВС на основе их моделей определение свойств, присущих системе или классу. Типичная задача анализа — оценка производительности и надежности системы с заданной конфигурацией, режимом функционирования и рабочей нагрузкой.
Другие примеры задач моделирования: определение (оценка) вероятности конфликта при доступе к общей шине; оценка распределения длительности времени занятости процессора, загрузки канала ввода/вывода.
Задачи синтеза — это выбор путем моделирования структуры системы (структурный синтез), вектора параметров характеристик системы (параметрический синтез) и стратегии управления вычислительными процессами, оптимизируюших значение критерия эффективности системы при наличии зависимостей критерия от структуры, параметров и управления.
Общая характеристика методов моделирования ВС. При описании ВС используется целый которых зависит от характера изучаемых процессоров и целей, которые ставятся при исследовании. Обычно выделяют следующие группы методов.
Аналитические методы моделирования ВС обычно состоят в их представлении как конечных автоматов, преобразующих символьные последовательности. Правила преобразования входных слов автомата в его выходные слова служат математической моделью ВС. В силу сложностей современных ВС возможности аналитического исследования подобных математических моделей обычно ограничены.
Вероятностные методы моделирования. Процесс функционирования ВС — это процесс выполнения техническими средствами некоторого набора программ (алгоритмов).
При этом как при запуске программ, так и при их выполнении, присутствует элемент случайности. Моделирование процессов, связанных с обслуживанием каких-либо запросов, с учетом случайного характера запросов и обслуживания, проводится в рамках теории массового обслуживания, являющейся разделом теории случайных процессов. В теории массового обслуживания в основном изучаются процессы, являющиеся марковскими, В пособии рассмотрена одна из наиболее известных моделей этого класса — конечные цепи Маркова.
При моделировании ВС также широко применяется имитационное моделирование, основанное на методе статистических испытаний.
Сетевые методы моделирования применяются для анализа сложных динамических систем, в которых осуществляется параллельное функционирование самостоятельных устройств. Поведение таких систем становится весьма сложным и недетерминированным. При этом моделируются не столько функция системы, сколько ее структурные характеристики и свойства. Модель системы должна быть структурно подобна объекту и строится по частям, как и система. Сетевые методы, предназначенные для этой цели, позволяют изучать явления в сложных параллельных системах. В пособии рассмотрен один из классов таких моделей, получивший название сетей Петри.
Экспериментальные методы моделирования базируются на измерении характеристик вычислительных процессов, происходящих в реальных системах, и на их обработке с целью определения интересующих исследователя зависимостей. Этот класс моделей может быть отнесен к физическим моделям и в нашем пособии не рассматривается.