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

Московский ордена Ленина, ордена Октябрьской революции и ордена Трудового Красного знамени государственный университет им. М.В.Ломоносова

Факультет вычислительной математики и кибернетики

СМЕЛЯНСКИИ Руслан Леонидович

АНАЛИЗ ПРОИЗВОДИТЕЛЬНОСТИ РАСПРЕДЕЛЕННЫХ МИКРОПРОЦЕССОРНЫХ СИСТОЛ НА ОСНОВЕ ИНВАРИАНТА ПОВЕДЕНИЯ ПРОГРАММ

Специальность 05.13.11 - Математическое и программное обеспечение вычислительных машин, комплексов, систем и сетей

Автореферат диссертации на соискание ученой степени доктора физико-математических наук

На правах рукописи УДК 519.68

Москва 1991

Работа выполнена на кафедра Автоматизации систем вычислительных комплексов факультета вычислительной математики и кибернетики Московского 1'осударствонного УНИЬ«рСИТ«Тс1 ИМ. М.Н. ЛОМОНОСОВЕ!

г-фициалыше оппоненты:

доктор физико-математических наук

чл.-корр. АН СССР В.Е.Котов

доктор физико-математических наук

чл.-корр. АН УССР А.А.Летичевский

доктор физико-математических наук

академик АН РСФСР М.Р.Шура-Бура

Защита состоится "_" _1991 г. в _ часов на

заседании Специализированного совета Д.053.05.38 N 4 по математике при МГУ им.М.В.Ломоносова по адресу: 119899, Москва, ГСП-3, Ленинские горы .МГУ, факультет вычислительной математики и кибернетики, ауд. _.

С диссертацей можно ознакомиться в библиотеке факультета вычислительной математики и кибернетики МГУ.

Автореферат разослан "___"________ 1991 г.

Ученый секретарь совета профессор

П.П.ТГИФ0И0П

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

- законы поведения программ, связь статики и динамики программ исследованы не достаточно.

- существующие математические теории и математические модели, не отражают в нужных аспектах динамику информационных процессов в вычислительных системах, не сочетают в себе

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

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

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

Основными целями втого исследования являются г

- создание формальной модели функционирования распределенных микропроцессорных систем для анализа их фукционирорвания на стадии проекта на основе динамики программ;

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

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

Результаты исследований в указанных направлениях будут полезны при:

- проектировании и выборе структуры многопроцессорной вычислительной системы под класс задач;

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

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

Результаты описанных в работе исследований послужили отправной точкой для развития нового, перспективного научного направления: исследование свойств поведения программ. Основной упор был сделан на поиске свойств поведения программ, инвариантных относительно вычислительных сред, и использование этих свойств для анализа4 сиотемной производительности распределенных вычислительных систем.

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

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

- взаимосвязь различных семантик параллелизма;

- взаимосвязь времени и поведения программ;

- предложен способ описания поведения программ на основе

операционного подхода;

- дана математическая постановка задачи анализа

производительности и разработан метод ее решения.

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

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

- оценивать системную производительность распределение

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

прогнозировать поведение программ в новой вычислительной среде на отапе ее проектирования; - дает контролируемую точность оценок.

Эта методика также применима при разработке крупных проектов, когда на отапе создания нельзя собрать в одном месте все компоненты разрабатываемой системы. Ее можно применять для проверки согласованности динамических характеристик программного обеспечения требованиям технического задания в системах реального времени.

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

Практическая значимость работы выражается в использовании разработанных методов, алгоритмов и инструментальных средств измерения, описания и анализа поведения программ в конкретных экспериментальных системах. созданных в лаборатории Вычислительных комплексов кафедры Автоматизации систем вычислительных комплексов в рамках следующих НИР: "Исследование методов обработки информации в неоднородных

вычислительных средах" (Гос.per.N 81024433 задание 05.01 ЦКП 0.Ц.027); "Исследование структур распределенных вычислительных систем и методов обработки информации в них" (Гос.per.N 01860113552 задание 06.01.А НТП 0.80.03) .

Полученные результаты использовались в прикладных НИР "Исследование структур программируемых устройств доступа в локальной сети высокопроизводительной ВС"; "Разработка и исследование комплекса моделей встроенного программного обеспечения сетевых транспорных станций и устройств"; "Исследование методов анализа поведения управляющих вычислительных комплексов".

О практической значимости работы говорит тот факт, что полученные результаты и практические наработки используются в НИР, выполняемых по важнейшей тематике в соотвествии с оощегосударственными научно-исследовательскими программами* "Разработка и исследование принципов экспериментальной оценки эффективности архитектуры вычислительных структур функциональных модулей БВКУ с использованием средств имитационного моделирования"; НИР "Салют-У"; "Пальмира"; "Создание математической модели функционирования параллельных вычислительных систем с децентрализованным управлением"; "Исследование вычислительных систем с динамической структурой и методов обработки информации в них".

Апробация работы. Полученные результаты доложены на 8 международных совещаниях, всесоюзных конференциях, Всесоюзной конференции по суперЭВМ (Минск 1987), Всесоюзной школе семинаре по сетям ЭВМ 1988,1989,1990 гг., семинаре отдела

математики ИПК АН ССОР, Ломоносовских чтениях 89.90 гг., Всесоюзной конференции по параллельным вычислениям (Новосибирск 19Й9). Советско-Болгарском семинаре (Гилечица 1990), П Научной школе по вычислительным наукам и супер ЭВМ "Лебедевские чтения"(Одесса 1990), Совещание РГ МПТ при ГКНТ СССР(Таллин 1990), семинаре ВЦКЛ АН СССР, Московском общегородском семинаре 'по программированию.

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

Структура и объем работы. Диссертация изложена на 309 страницах и имеет два приложения. Она сотоит из введения, пяти глав и заключения. Суммарный объем библиографии насчитывает 272 наименования.

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ В первой главе определены основные понятия и терминология. Вычислительная система рассматривается как совокупность из трех основных компонентов:

- физической среды: * аппаратные средства, определяемые составом устройств, и система связи между ними;

- логической среды: программное обеспечение, поддерживающее работоспособность системы, обеспечивающее выполнение заданий пользователей (ОС, run-time system, библиотеки, файловая система и т.п.);

- рабочей нагрузки: характеристики заданий пользователей, их

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

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

Формулировка задачи для общего случая дана в следующем

виде:

заданы: описание вычислительной системы СБ как комплекса физической и логической сред; набор программ Р на языке программирования высокого уровня.

требуется: найти способ оценки производительности системы СБ с контролируемой точностью на множестве программ Р без использования системы С2, ее прототипа или вмулятора системы команд.

Основные характеристики класса рассматриваемых физических сред и программ сформулированы следующим образом:

(1) Система содержит множество процессоров последовательного

с

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

(2) Каждый процессор имеет собственное устройство управления, оперативную память и может работать по

собственной программе.

(3) Конфликты доступа к общему полю оперативной памяти на уровне отдельных команд разных процессоров невозможны либо вносимые ими временные издержки пренебрежимо малы.

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

(Б) Структура связи статическая, т.е. для каждого процессора множество соседних процессоров, к памяти которых он может иметь доступ, конечно, фиксировано и в ходе работы системы не может быть изменено.

Параллельная программа - это совокупность параллельно выполняемых, ассинхронно взаимодействующих, последовательных процессов, удовлетворяющих следующим требования:

(1) Процессы не имеют общих переменных. Они могут взаимодействовать только с помощью надлежащих средств вычислительной среды.

(2) Взаимодействие мевду процессами всегда указано явно в их текстах. При етом всегда указаны инициатор, адресат и тип объекта, с помощью которого осуществляется взаимодействие:

(3) Взаимодействие осуществляется с помощью передачи сообщений и используется как для передачи данных, так и для целей синхронизации;

(4) Никаких предположений об относительной скорости выполнения процессов в программе не используется:

(5) Все процессы конечны.

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

Основу этой главы составил обзор методов и средств оценки производительности вычислительных систем с традиционной архитектурой. Цель этого обзора - подготовка к ответам на вопросы:

какие новые проблемы возникают при оценке производительности распределенных вычислительных систем по' сравнению с традиционными системами ?

- нужны ли для анализа и оценки поведения распределенных систем новые инструментальные средства или же вполне годятся старые ?

^озор охватывает 109 статей, монографий и трудов международных конференций, опубликованных за последние 15 лет.

На основе выводов из этого обзора и не формального анализа задачи сделан вывод о том, что наиболее перспективным выглядит подход когда, зная поведение программы в некоторой вычислительной среде (назовем ее инструментальной), можно прогнозировать ее поведение в другой среде (назовем ее

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

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

- по описанию поведения программы построить модель рабочей нагрузки для модели вычислительной системы;

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

- по полученной временной диаграмме вычислить нужные

характеристики производительности вычислительной системы.

Такой подход позволяет анализировать поведение одной и той же программы в различных вычислительных средах. Сохранение ь этом описании поведения всех внутренних взаимосвязей, присущих данной' программе, является залогом надежности и точности результатов моделирования.

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

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

Достижение основной цели этой главы осуществляется в виде решения трех основных задач:

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

- умения предопределять последовательность действий программы

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

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

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

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

является понятие нестационарности поведения программы, которое характеризует зависимость истории выполнения процесса от скорости развития вычислений в других процессах программы. Исследована взаимосвязь разных видов недетерминизма с нестационарностью. Предложены два метода прогнозирования последовательности действий для программ с нестационарным поведением: метод с обратной связью и метод конечного числа реакций. Отметим, что предложенная классифакация поведения программ, насколько известно автору, является первой подобной попыткой в мировой литературе. Позднее на ее основе определяются требования к инструментальным средствам для анализа описания и моделирования распределенных вычислительных систем. Она является тем "физическим смыслом", на освнове которого потом строится формальная модель.

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

- выражения не имеют общих подвыражений;

- в последовательности обращений к логическим ресурсам нет бесполезных обращений;

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

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

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

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

- не позволяют работать с распределенными событиями;

- каждое такое средство ориетировано на фиксированный набор событий;

- известные технические приемы измерения характеристик событий не адекватны особенностям поведения рассматриваемого класса программ.

Анализ средств моделирования распределенных

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

Третья глава целиком посвящена формализации исследуемого явления, т.е. выбору математических абстракций для его описания, исследованию свойств этих абстракций, строгой формулировке и решению основной задачи анализа производительности. Основные отличия предложенной здесь модели функционирования распределенных вычислительных систем от моделей Р.Мильнера, Ч.А.Р.Хоара, У.Дегано и Г.Монтанари, М.Нивата, Капитоновй Ю.В. и Летичевского A.A., Анисимова A.B. и Борейши Ю.В., Миренкова H.H., развития сетей Петри, предложенное Котовым В.Е. состоят в том, что она:

- отражает как алгоритмические, так и количественные характеристики поведения программ;

- включает время как количественную сущность;

- охватывает структурные, функциональные и емкостные свойства аппаратуры;

- отражает иерархический характер структуры вычислительных систем.

в ней четко разделены программа, физическая и логическая среды ее исполнения.

Основу модели составляют три понятия:

поведение;

испонитель;

наблюдатель.

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

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

поведение процесса описывается в виде частично-упорядоченного множества шагов, а не просто событий;

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

- каждый шаг имеет атрибут "сложность", который позволяет рассматривать развитие процесса во времени, исходя из конкретных характеристик той физической среды, кЬторая будет исполнять етот процесс;

- предложенная абстракция учитывает как внутренний, так и внешний недетерминизм в поведении программ;

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

Важным достоинством предлагаемого способа описания поведения программ является то, что он позволяет обойти

проблему неоднозначности описания поведения, указанную Р.Милнером.

Исполнитель - вто модель физической среды. Она отражает следующие свойства отой среды:

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

- распределенность, т.е. независимость функционирования устройств:

- структуру связи в физической среде;

- объем и регистровую структуру памяти устройств;-

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

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

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

Фундаментально важной при исследовании свойств наблюдателя была проблема корректности воспроизведения етим наблюдателем разных форм параллелизма. Эта проблема сводится к ксслсдоьанив взаимосвязи двух еемантик параллелизма:

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

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

В терминах построенной теории задача анализа производительности выглядит следующим образом: пусть задана вычислительная система

CS = <Bh(Р), shd, СЕ>. Требуется найти временной профиль G(t) системы CS.

Здесь: Bh(P) - поведение программы Р;

Shcl - функция распределения процессов программы в логической среде: взаимнооднозначное отображение Р ■* Dm;

СЕ - вычислительная среда:

СЕ = <LE,Bind,DEx> где: LE - поведение процессов логической среды;

Bind - привязка процессов логической среды к исполнителю;

DEx - распределенный исполнитель.

Временным профилем работы вычислительной системы CS называется вектор-функция G(t) = (g^(t), g(t)....,g(t)). где vt: isisn и g{(tj - временной профиль последовательного исполнителя SEx{eCE.

Временным профилем последовательного исполнителя S£r( называется однозначная функция g{Ct), определенная на R, с областью значений - множество кортежей вида

<р, з. q, а{>

где, р - процесс программы; з - шаг программы; q - сложность шага; а - атомарный процесс исполнителя.

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

Пусть дана распределенная вычислительная система- ' СЛь, состящая из Q последовательных исполнителей (например, процессоров).' Введем следующий набор переменных, характеризующих функционирование CS:

Т - длина периода наблюдения за работой СЙ по астрономическому времени;

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

Обозначим X = З/Ч! - пропускную способность системы СБ;

- количество астрономического времени, которое (-ый последовательный исполнитель из СЗ, был занят выполнением услуг из J.

IV( = и /Т - загрузку {- го исполнителя.

Nl - общее количество действий (действие - ето нечто что составляет услугу), выполненных (-м последовательным исполнителем в течении периода наблюдения Т.

Рш) = ~ среднее время действия на

(-ом последовательном исполнителе (ето вычислительная мощность исполнителя);

Еп( = N ЛГ - среднее число действий {-го устройства на одну услугу из J.

В втих обозначениях справедлива следующая теорема.

Теорена (о пропускной способности).

1У.

Х=--------- .

Рш Еп

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

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

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

Четвертая глава посвящена комплексному подходу к моделированию распределенных вычислительных систем. Смысл слова "комплексный" в данном случае состоит в том, что в рамках одной системы, имеющей единый набор языковых средств, анализируются как алгоритмические, так и количественные свойства объекта моделирования.

Для распределенных систем из-за особенностей их поведения ни только алгоритмический анализ ни только -количественный не являются полными. В работе эти виды анализа определены через различия тех методов, которые они используют. Количественный анализ использует методы теории расписаний, систем с очередями, теории игр и т.п. Главным" общим свойством методов, используемых при этом анализе, является то, что время в них метрическая величина. Алгоритмический анализ использует методы теории алгоритмов.

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

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

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

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

- система должна обеспечивать описание как поведения программного обеспечения так и функциональных характеристик аппаратуры для оценки количественных параметров динамики объекта моделирования;

- система должна корректно воспроизводить оба вида параллелизма: чередования (interleaving) и истинного (real concurrency);

- система должна поддерживать парадигму "запрос-ответ".

присущую функционированию вычислительных систем.

Анализ литературы показал, что ни одна из существующих систем моделирования не удовлетворяет таким требованиям. Теоретические основу решения всех втих проблем составили результаты главы III. Ь качестве основы для реализации комплексного подхода к моделированию распределенных вычислительных систем в работе разработаны и исследованы, так называемые, модели с сообщениями (везде далее

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

В работе доказано, что если ь модели используют неупорядоченные буфера, неограниченной длины, то ета модель принадлежит классу моделей сетей Петри; если к тому же ь ней

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

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

В заключении этой главы отмечено, что модели о сообщениями близки к идеологии объектно-ориентированного описания систем и процессов. Этот факт представляется важным в свете интенсивного развития объектно-ориетированной методологии в программировании.

В пятой главе описана и исследована архитектура Системы Автоматизированного Исследования Вычислительных Систем (САИВС) - комплекса инструментальных средств, построенных на базе результатов, описанных в предшествующих главах. Подробно рассматривается методика, применения САИВС.

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

Подсистема "Стенд" представляет собой комплекс • аппаратно-программных средств, которые образуют

распределенную среду для функционирования программ. Основной задачей этой среды является слежение и измерение поведения программ на уровне инварианта ее поведения.

Центральной идеей построения аппаратных средств Стенда является идея конструктора. Коструктор должен содержать блоки памяти, процессорные элементы, спецпроцессоры, магистрали, типа "общая шина". Выбор магистрально-модульного принципа организации этого конструктора объясняется тем, что он обеспечивает:

- дешевизну и техническую простоту подключения устройств:

- гибкость реконфигурации системы;

- открытость системы для измерения информационных потоков. Экспериментальная реализация этого конструктора основана на технических средствах серии "Электороника", и магистралях Unibus, Q-bus, САМАС, СОМРЕХ. На ее базе собрана шести процессорная система, работа с которой осуществляется под управлением СМ-1420 в рамках ОС Unix.

В этой главе подробно рассмотрена организация експериментальной операционной системы Стенда. В работе обосновано, что средства наблюдения и измерения поведения программ долины быть интегрированы о ОС. Здесь существенно используются результаты обзора из главы I. 'Подробно рассмотрено почему необходимо использовать для построения такой ОС методологию объектно-ориентированного подхода (02П).

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

системе.

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

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

В заключении перечислены основные результаты работы: (1) разработана математическая модель функционирования распределенных вычислительных систем. Она охватывает не только алгоритмические аспекты поведения программного обеспечения, но и характеристики физической среды распределенных вычислительных систем, явно включает время как количественную сущность. В рамках этой модели исследованы:

- взаимосвязь различных семантик параллелизма;

- взаимосвязь времени и поведения программ;

- предложен способ описания поведения программ на основе

операционного подхода;

- дана математическая постановка задачи анализа

производительности и разработан метод ее решения, корректность которого доказана.

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

(3) на основе вышеизложенных результатов разработана новая методика анализа и оценки производительности, основанная на инварианте поведения программ.

(4) разработана архитектура инструментальных средств измерения, описания и анализа поведения программ, поддерживающих разработанную методику.

Все перечисленные выше результаты являются новыми. Постановки решаемых задач, основные теоретические и прикладные результаты работ принадлежат лично Смелянскому Р.Л. Публикации:

1. Smelianeky R. On the oaloulation of transition probabilities in a program. Intern.Proo.letters N.3,1986.

2. Смелянский P.Л. Молонов В.Г. Комплексный подход к моделированию распределенных вычислительных систем. Программирование N1,1988.

3. Смелянский Р.Л. Бочков С.О. Методы отладки распределенных программ. Программирование N4,1988.

4. Смелянский Р.Л. Об инварианте поведения программ. Вестник МГУ.Серия N15, N4,1990.

5. Смелянский Р.Л. Модель функционирования распределенных

вычислительных систем. Вестник МГУ, Серия N15, N3,1990.

6. Смеллнекий Р.Л. Комплексное моделирование распределенных вычислительных систем. Тр.Всесоюз.соьещ. РАСМО, Душанбе 1991.

7. Srneliansky R. Kazakov U. Bakalov U. The combined approach to the simulation of distributed computer systems. Proc.intern.conf. on Parallel Computer Teonologies, Novosibirsk,1991.

ь. Смеллнекий P.Л. Поведение программ и распределенных вычислительных средах и инструментарий для его анализа. Актуальные вопроси технологии программирования. Ленинград,1990. 9. Смеллнекий Р.Л. Система автоматизированного исследования вычислительных систем. Новые информационные технологии в научных исследованиях и обучении. Москва,1990.

Подписано к печати 8.07.1991 г. Заказ 622-е. Объем 1,25 уч.изд. Бумапа 60x84 I/I6. Тираж 100 экз._

PHI У0П КТИРПХ.236000.Калининград обл., Советский пр.-т,1