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

На правах рукописи

РГб од

• с ПНО 1У.0

РЫБИН Сергей Владимирович

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

МОДЕЛЕЙ

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

Автореферат диссертации па соискание учёной степени кандидата технических паук.

Москва 2000 год

Работа выполнена в Московском государственном техническом университете имени Н.Э. Баумана.

Научный руководитель:

д.т.н., профессор Марков А.А.

Оф нт (налы иле 01Ш0ИС1 ггы:

д.т.н., профессор ИГУ Линьков В. М.; к.т.н., зам. директора НИИ ИСУ МПГУ им. Н.Э. Баумана Пшиков А. С.

Ведущая организация:

ВЦ РАН (г. Москва)

Защита состоится «14» декабря 2000 г. на заседании диссертационного совета К 053.15.04 в Московском государственном техническом университете им. Н.Э. Баумана но адресу: 107005, Москва, 2-я Бауманская ул., д.5. Тел. 263-69-06.

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

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

Автореферат разослан «_» ноября 2000 г.

Учёный секретарь

диссертационного совета

к.т.н., доцент С.Р. Иванов

Подписано к печати «30» октября 2000 г.

Заказ_ . Объём 1 п.л. Тираж 100 экземпляров. Типография МГТУ,

107005, г. Москва, 2-я Бауманская ул., д.5.

Общая характеристика работы

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

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

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

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

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

Основные задачи исследования:

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

- построение математической модели МПВС;

- построение математической модели процессорного модуля;

- построение математической модели межпроцессорных коммуникаций;

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

- разработка обобщённого алгоритма функционирования многоуровневой распределённой памяти МПВС и сто аналитическое описание;

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

- разработка и обоснование способа построения программно-аналитической модели МПВС (имитационной модели, содержащей аналитические фрагменты);

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

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

- способ формулирования вероятностной математической модели коммуникационного слоя, определения его дня топологий типа «Кольцо», «¿-мерный тор», «Звезда» и аналитического решения для случая экспоненциального распределения потока заявок;

- способ объединения процессорных модулей в МПВС с общей распределённой памятью на основе разработанной архитектуры памяти с использованием механизмов страничной и виртуальной памяти;

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

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

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

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

Практическая ценность. Разработанные методы, алгоритмы, модели, методики и программные средства реализованы в В/Ч 32103:

- При обосновании перспектив развития наземного автоматизированного комплекса управления (НАКУ) КА в условиях ресурсных огра-иичений;

- При разработке предложений по переоснащениго НАКУ па перспективные средства управления КА;

- В НИР «Раунд-520», поспящёшюм исследованию научно-технических проблем создания и развития перспективных космических систем;

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

Апробация работы. Содержание отдельных разделов и диссертации в целом было доложено:

- на коифсрешцш «Международная конференция 275 лет Российской Академии Наук». М., 1999.

- на конференции «3-я Межведомственная научно-практическая конференция. Моделирование и сертификация вооружения и военной техники (ВВТ). Секция: Визуализация и технологии моделирования интеллектуальных систем». М,, 2000.

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

Объём и структура работы. Диссертационная работа состоит из введения, четырёх глав, выводов и четырёх приложений, списка литературы из 92 наименований; содержит 213 страниц машинописного текста, в том числе 26 таблиц и 27 рисунков.

Содержание работы.

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

В первой главе рассмотрено текущее состояние исследуемой предметной области. Приведены классификации систем параллельной обработки данных. Даётся обзор процессоров, используемых при построении МГТВС. Рассматриваются способы взаимодействия процессорных элементов (Г1Э) в МПВС, производится обзор и классификация моделей связи и архитектур памяти в МПВС. Анализируются аппаратные средства взаимодействия ПЗ в МПВС и соответствующие им методы моделирования МПВС. Выполняется обзор литературных источников.

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

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

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

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

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

Рпс.1. Структура процессорного модуля.

Таблица 1 содержит расшифровку обозначений, приведённых на рис.1.

Коммуникационный слой объединяет процессорные модули (ИМ) или процессорные элементы (ПЭ) с локальной памятью в единую МПВС с общим адресным пространством памяти, состоящей из локальных модулей памяти, реализуя DSM архитектуру. Предполагается объединение IIM на базе оптоволоконных каналов связи. Элементная база, состоящая из отдельных приёмника и передатчика, накладывает ограничения на топологию коммупикаци-ошюго слоя.

Таблица 1.

Расшифровка обозначений на рнс.1.

Обозначите Описание

сти Центральный процессор

ЕС Внешняя кэш-память

1Л*ЛМ Локальное ОЗУ

ЬЛКЛМ Локальное ОЗУ адаптера

СОМ Коммуникационный адаптер

ЬУМ Локальная виртуальная памя'п.

РГ) Пользовательский диск

шж Устройство ввода пользовательских программ

1,р Построчно печатающее устройство

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

Сформулирована вероятностная математическая модель коммуникационного слоя и определена для топологий типа «Кольцо» (рис. 2), «(3-мерный тор» (рис. 3) и «Звезда» (рис. 4).

~Н ПЭМ1 I—{ ПЭМ Ь

Рис. 2. Топология «Кольцо».

Рис. 3. Топология «<1-мсримп тор» для (1=2

Рис. 4. Топология «Звезда».

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

Математическая модель основывается на математическом описании многопроцессорных систем с многошинной топологией, использующем марковскую (Марсан и Герла) и полумарковскую (Мудг и Ал-Садоун) модели с пуассоновским распределением потока заявок. На основашш существующих построений математических моделей многопроцессорной вычислительной системы и анализа её производительности при использовании различных протоколов (Доуд, Богинени - объединение ПМ па основе оптической WDM сети), распределение времён обслуживания может быть хорошо аппроксимировано экспоненциальным распределением. На данном уровне абстракции детальность и точность этой математической модели считается достаточной.

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

• Режим сквозного прохождения пакетов без приёма.

• Режим сквозного прохождения пакетов с приёмом (прослушивание линии).

• Режим приёма пакетов без дальнейшей передачи.

• Режим приёма при совпадении адреса без дальнейшей передачи.

• Режим приёма при широковещательном адресе с дальнейшей передачей.

• Режим приёма при широковещательном адресе без дальнейшей передачи (забрать свой широковещательный пакет).

• Передача пакета.

• Режим одновременного приёма и передачи.

Протокол реализует взаимодействие на основании маркерного доступа.

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

Выполнен сравнительный анализ топологий «Кольцо», «¿-мерный тор» и«Звезда».

Таблица 2 показывает взаимосвязь критериев оценки архитектуры МПВС от вариационных параметров коммуникационного слоя.

Таблица 2.

Зависимость критериев оценки архитектуры МПВС от вариационных параметров коммуникационного стоя.

Порядок зависимости от соответствующего критерия Значаше зависимости

Сложность аппаратной реализации увеличивается при увеличении ПЭ 1. Звезда 2. Кольцо 3. Тор

Времена реакции, установления соединения, передачи пакета возрастают при фиксированном числе ПЭ 1. Звезда 2. Гор 3. Кольцо

Время взаимодействия «точка-точка» уменьшается при большом количестве единовременно передаваемых данных 1. Асинхронное взаимодействие 2. Синхронное взаимодействие

Время взаимодействия «точка-точка» уменьшается при матом количестве единовременно передаваемых данных 1. Синхронное взаимодействие 2. Асинхронное взаимодействие

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

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

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

Рис. 5. Структура подсистемы памят и в МПВС.

Таблица 3 содержит описания обозначений на рис. 5.

Таблица 3.

Оппсапня обозначений рис.

Обозначеште Описание

СРШ, СРШ Процессоры модулей 1 и 2.

ЕС1.ЕС2 Кэш-память модулей 1 и 2.

1ЛАМ1, 1Л1АМ2 Локальное ОЗУ модулей 1 и 2.

ЬДИАШ, ЬАКАМ2 Локальная память коммуникационных адаптеров 1 и 2, расположенных в соответствующих модулях.

1ЛПАМ1, ЬШАМ2 Локальная виртуальная память на НЖМД для модулей 1 и 2.

Порядок работа памяти следующий: Информация передаётся по запросу между локальным ОЗУ и кэш-памятыо блоками размера s0, которые в общем случае являются делителями размера блоков si. Отношение размера блока Si (страницы) к размеру блока s0 (полстраницы) обычно равно степени числа 2. Если от CPU поступает ссылка на слово, не находящееся в кэш-памяти, под-страница, содержащая это слово, передаётся из локального ОЗУ в кэшпамять. Если страница, содержащая подстрашщу, на которую была ссылка, не находится в основной памяти, она должна быть извлечена из локальной памяти коммуникационного адаптера и загружена в основную память до того, как желаемая подстрашща будет передана в кэш-память. При отсутствии необходимого блока в локальной памяти коммуникационного адаптера, она загружается туда из локальной виртуальной памяти. Если необходимый для загрузки свободный блок памяти уровня i отсутствует, то он освобождается, путём выгрузки выбранной страницы в память уровня /'+/. Выбор блока для освобождения по произвольному алгоритму, Наиболее оптимальным на данный момент считается алгоритм LRU.

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

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

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

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

Таким образом, но второй главе сформулирована полная аналитическая вероятностная модель вычислительной системы и её нагрузки, лежащая в основе метода построения и анализа архитектуры МГ1ВС. Модель является основным теоретическим результатом, лежащим в основе задачи исследования. Показано определение модели для различных архитектур.

В третьем главе реализовано полное формальное описание программно-аналитической модели исследуемой МПВС.

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

В состав системы (рис.1) входит процессор CPU, оперативная память LRAM, кэш-память ЕС, коммуникационный адаптер СОМ с памятью LARAM, устройства дисковой памяти и устройства ввода и вывода. В системе используются диски:

• LVM - диск для хранения страниц программ и данных;

• PL) - пользовательский диск.

Устройства ввода и вывода, условно названные LP и RDR:

• LP - устройство передачи резу льтатов работы;

• RDR - устройство ввода запросов и информации в систему.

Конфликты при доступе процессора, коммуникационного адаптера и каналов к оперативной памяти не рассматриваются.

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

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

При замещении страниц в памяти используется стратегия локального замещения. За один раз может быть замещена только одна страница в оперативной памяти. Могут быть использованы различные алгоритмы замещения страниц (Random, FIFO, LRU, LFU).

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

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

N£C число страниц в ЕС

Nlram число страниц в LRAM

Nlram число страшщ в LARAM

Nlvm число страшщ в LVM

Тогда число свободных страшщ в уровне памяти (состояние уровня памяти)

Sxx е [0, Nxxl, где хх - тип памяти.

Соответственно число состоянии уровня памяти, без учёта перестановок, равно

Sxx = Nxx+l (1)

Общее вдело состояний памяти, с учётом состояний всех уровней

S = f[Sxx , где хх е [ЕС, LMM, LARAM, LVM] (2)

XX

или

4

s=ns(, где i - уровень памяти (3)

/=1

После каждого доступа к памяти, память переходит из состошшя S'{Si\ S2', S3', S)'} в состояние S"{Si", S2", S3", S4"}, с соответствующим изменеии-ем состояний уровней памяти.

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

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

Изложена модель подсистемы ввода-вывода.

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

Получипгая в главе три программно-аналитическая модель вычислительной систеш.1 и её нагрузки является теоретическим результатом, лежа-

тцим в основе метода анализа архитектуры М11ВС. Реализация программно-аналитической модели выполнена на основашш изложенных во второй главе математических моделей.

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

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

Обосновано объединение аналитических фрагментов в рамках имитационной модели при построении программно-аналитической модели.

Поэтапно изложена методика организации и анализа взаимодействия процессорных элементов в МПВС.

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

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

Основные результаты

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

систем с распределённой общей памятью, достигнута ! Теоретическая часть.

1. Выполнено концептуальное описание математической модели вычислительной системы в целом и её отдельных компонентов, таких как процессорный модуль и коммутшкационный слой.

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

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

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

5. Введено понятое коммуникационного слоя, как интерфейса для взаимодействия процессорных модулей, сформулирована его вероятностная математическая модель и определена для топологий тина «Кольцо», «d-мерный тор» и «Звезда». Для каждой топологии описаны времена установления соединения, длины пути информационных пакетов и вероятности выбора различных маршрутов на основании комбинаторного анализа соответствующих топологий. Описаны протоколы взаимодействия и форматы кадров для соответствующих топологий, включая алгоритм маршрутизации для топологии «d-мерный тор».

6. Обосновано объединение аналитических фрагментов в рамках имитащ!-онной модели при построении программно-аналитической модели.

Практическая часть.

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

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

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

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

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

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

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

1. Рыбин C.B. Распределённая иерархическая память. Архитектура, алгоритм работы, метод анализа // Моделирование и сертификация вооружения и военной техники (ВВТ). 3-я Межведомственная научно-практическая конференция. Секция: Визуализация и технологии моделирования интеллектуальных систем. - М., 2000. - С. 78-87.

2. Рыбин C.B. Подход к анализу информационной безопасности // 275 лет Российской Академии Наук: Сб. докладов. Международная конференция. - М., 1999. - С. 66-68.

3. Исследование и создание специального комплекса тестирования общего и общесистемного программного обеспечения информационно-вычислительных сетей: Отчёт по теме ГРЛ 821 /МГТУ. НИИ PJI; Руководитель Марков A.A. ГР № 01.99.000.6427, Инв. № 0199.0055116. -М„ 1999.- 140 с.

4. Иванов И.П., Орлов А.П., Рыбин С.13. Информационно-вычислительная сеть МП'У им. Н.Э. Баумана // Вестник МГТУ. Приборостроение. - 1998. - № 2. С. 61-70.

5. Рыбин C.B. Коммуникация интеллектуальных объектов в информационных системах с помощью ограниченного естественного языка // КомпыоЛог. - 1998. - № 2. - С. 47-55.

Введение.

Глава 1. Обзор предметной области.

1.1. Обзор литературных источников.

1.2. Классификация систем параллельной обработки данных.

1.2.1. Конвейерная и векторная обработка.

1.2.2. Машины типа SIMD.

1.2.3. Машины типа MIMD.

1.2.4. Многопроцессорные машины с SIMD-процессорами.

1.2.5. Современные тенденции использования архитектур многопроцессорных систем.

1.3. Процессоры и процессорные элементы в МПВС.

1.4. Организация взаимодействия процессоров в МПВС.

1.4.1. Механизм передачи сообщений.

1.4.2. Общее поле памяти.

1.5. Аппаратные средства взаимодействия.

1.5.1. Электронные интерфейсы.

1.5.2. Оптические интерфейсы.

1.6. Организация памяти в МПВС.

1.6.1. Модели связи и архитектуры памяти.

1.6.2. Механизм обмена.

1.6.3. Мультипроцессорная когерентность кэш-памяти.

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

1.7.1. Модели вычислительных систем.

1.7.2. Модели нагрузок.

1.8. Определение объектов исследования.

1.9. Класс решаемых задач.

1.10.Постановка задачи.

1.11 .Выводы по главе 1.

Глава 2. Разработка математической модели МПВС.

2.1. Концептуальное описание МПВС.

2.2. Модель процессорного модуля.

2.3. Модель коммуникационного слоя.

2.3.1. Топология «Кольцо».

2.3.2. Топология d-мерный тор.

2.3.3. Топология «Звезда».

2.3.4. Протокол взаимодействия.

2.3.5. Сравнительный анализ топологий.

2.4. Структура подсистемы памяти.

2.5. Математическая модель вычислительной задачи.

2.5.1. Описание вычислительной задачи.

2.5.2. Объёмы информации и интенсивности информационных потоков.

2.5.3. Формулировка математической модели вычислительной задачи.

2.6. Выводы по главе 2.

Глава 3. Построение программно-аналитической модели МПВС.

3.1. Постановка задачи построения программно-аналитической модели МПВС.

3.2. Структура модели.

3.3. Модель подсистемы памяти.

3.3.1. Описание изменений состояний памяти.

3.4. Модель устройств ввода-вывода МПВС.

3.5. Модель задания.

3.5.1. Схема задания.

3.5.2. Классы заданий.

3.6. Модель коммуникационного слоя.

3.7. Выводы по главе 3.

Глава 4. Постановка модельного эксперимента.

4.1. Постановка задачи модельного эксперимента.

4.2. Проведение модельного эксперимента.

4.2.1. Моделирование четырёхуровневой архитектуры памяти.

4.2.2. Моделирование трёхуровневой архитектуры памяти.

4.3. Оценка точности результатов моделирования.

4.4. Методика построения и анализа архитектуры МПВС.

4.4.1. Назначение и область применения методики.

4.4.2. Порядок применения методики.

4.4.3. Анализ результатов моделирования.

4.5. Выводы по главе 4.

Выводы.

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

В работе формулируются вероятностные математические модели взаимодействия процессорных элементов для высокоскоростной сети различной топологии, как-то: «Кольцо», «d-мерный тор» и «Звезда» с коммутатором. По архитектуре памяти, рассматриваемые вычислительные системы относятся к DSM системам.

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

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

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

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

Работа определяет процесс построения архитектур многопроцессорных вычислительных систем, взаимодействие компонентов которых происходит по средством высокоскоростной оптической сети.По результатам анализа предметной области выбраны направления науч ных исследований в рамках достижения цели настоящей работы. Для задач по строения МПВС это - архитектура MIMD, по классификации Флина, использо вание микропроцессоров при построении ПЭ, организация памяти в DSM архи тектуре и использование оптических интерфейсов для расширения полосы про пускания межпроцессорных каналов связи. Для задач анализа МПВС - это ве роятностные аналитические математические модели вычислительных систем.В работе вводится понятие коммуникационного слоя, как интерфейса для взаимодействия ПЭ. Использование понятия коммуникационного слоя позволя ет выделить ресурсы вычислительной системы, используемые для взаимодей ствия ПЭ и исследовать МПВС с этой точки зрения.Разработана распределённая, автоматически управляемая четырёхуровне вая иерархическая память и алгоритм её работы с использованием механизмов страничной организации и виртуальной памяти. Предложенный способ объеди нения распределённой памяти является одним из существенных элементов на учной новизны работы и позволяет упростить аппаратную поддержку органи зации DSM архитектуры за счёт встроенной функциональности микропроцес соров и сервисов операционной системы.Для получения характеристик производительности МПВС сформулирова ны математические модели ПЭ, коммуникационного слоя для топологий типа «Кольцо», «d-мерный тор» и «Звезда» и многопроцессорной вычислительной системы в целом. Определён порядок формулирования и определения ММ вы числительных нагрузок. Модели являются главным теоретическим аппаратом, лежащим в основе задачи исследования.В силу невозможности полного аналитического решения уравнений, опи сывающих модели МПВС и её нагрузки, построена программно-аналитическая модель МПВС с аналитическим описанием больших фрагментов, на основании разработанной концептуальной модели. Для этого при разработке модели был создан модифицированный метод численного расчёта для задач оценки эффек тивности программ, содержащих вероятностные схемы с повторяющимися процессами. Метод позволяет эффективно решать ряд матричных дифференци альных уравнений. Характеристики метода исследованы на матрицах размерно сти порядка 10 . Возможности метода существенно шире области его примене ния в рамках данной работы и могут быть использованы для работы с широким спектром алгоритмов и случайных процессов.Моделирование проводилось для процесса решения задачи управления войсками в условиях ведения боевых действий в крупном населённом пункте.Для этого были разработаны соответствующие математическая модель и мо дель задания. Результаты моделирования показывают рост производительности подсистемы памяти при использовании разработанной архитектуры памяти по сравнению с существующими. Этот рост быстродействия вызван наличием бы строго слоя памяти коммуникационных адаптеров, размещение коммуникаци онного адаптера на локальной шине процессора, в отличие от стандартного се тевого адаптера на системной шине и, наконец, алгоритмом объединения про цессорных модулей, осуществляемых на разных уровнях памяти.В конце работы показан порядок практического применения полученной методики построения и анализа архитектуры МПВС. Таким образом, работа содержит анализ предметной области, постановку задачи исследования, синтез математических и программно-аналитической мо делей, а также практическое применение результатов анализа и синтеза в виде методики построения и анализа архитектуры МПВС.

1. Основы теории управления войсками / Под ред. П.К.Алтухова.-М.: Воениздат, 1984.-221 с.

2. Амосов А.А., Дубинский Ю.А., Копчёнова Н.В. Вычислительные методы для инженеров.-М.:Высшая школа, 1994. - 544 с.

3. Бахвалов Н.С., Жидков Н.П., Кобельков Г.М. Численые методы.- М.:Наука, Гл. Ред. Физ.-мат. лит., 1987. - 600 с.

4. Исследование операций: В 2 т. / Р.Браун, Р.Мэзон, Э.Фламгольц и др., Пер. с англ.: Под ред. Дж. Моудера, Элмаграби.-М.:Мир, 1981. -Т. 1.-677 с.

5. Воеводин В.В., Математические основы параллельных вычислений.-М.: Издательство МГУ, 1991. - 345 с.

6. Воеводин В.В., Капитонова А.П. Методы описания и классификации архитектур вычислительных систем.-М.:Изд-во Моск. ун-та, 1994.-73 с.

7. Воеводин В.В., Кузнецов Ю.А. Матрицы и вычисления. - М.:Наука, Гл. Ред. Физ.-мат. Лит., 1984. - 320 с.

8. Вентцель Е.С. Теория вероятностей. - М.:Наука, 1969. - 576 с.

9. Гантмахер Ф.Р. Теория матриц. - М.:Наука, Гл. Ред. Физ.-мат. лит., 1988.-552 с. Ю.Грин Д., Кнут Д. Математические методы анализа алгоритмов. -М.:Мир, 1987.-119С.

10. ГГудман С, Хидетниеми Введение в разработку и анализ алгоритмов. -М.:Мир, 1981.-368

11. Дал У., Дейкстра Э., Хоар К. Структурное программирование. - М.:Мир, 1975.-247С.

12. Иванов Д.А., Савельев В.П., Шеманский П.В. Основы управления войсками в бою. - М.:Воениздат, 1977. - 389 с. М.Каханер Д., Моулер К., Нэш Численные методы и математическое обеспечение : Пер. с англ. - М.:Мир, 1998. - 575 с.

13. Управление войсками: Учебное пособие для вузов. - М.:ВВА, 1991. - 250 с.

14. Клейнрок Л. Теория массового обслуживания. - М.: Машиностроение, 1979.-432 с. П.Колмогоров А.Н. Теория информации и теория алгоритмов. - М.: Наука, 1987.-304 с.

15. Кнут Д.Э. Искусство программирования для ЭВМ: В 2 т. - М.Мир, 1976.-Т. 1.-734 с.

16. Ланкастер П. Теория матриц : Пер. с англ. - М.:Наука, Гл. Ред. Физ.- мат. лит., 1982. - 272 с.

17. Локуциевский О.В., Гавриков М.Б. Начала численного анализа. - М.:ТООЯнус, 1995.-581 с.

18. Основы теории вычислительных систем / Под ред. А.Майорова - М.:Высшая школа, 1978. - 408 с.

19. Майзер X., Эйджин Н., Тролл Р. Исследование операций: В 2 т. : Пер. с англ. / Под ред. Дж.Моудера, Элмаграби. - М.:Мир, 1981. - Т. 1. -712 с.

20. Марков А.А. Вероятностные оценки эффективности исполнения рекурсивных профамм // Вестник МГТУ. Приборостроение. -1996. - № 2. -С. 86-92.

21. Марков А.А. Повторяющиеся, параллельные и перекрёстные процессы в задачах оценки эффективности исполнения программ // Вестник МГТУ. Приборостроение. - 1997. - № 2. - 93-112.

22. Марков А.А. Вычислительные особенности и алгоритмическая сложность задач оценки эффективности исполнения повторяющихся процессов // Информационные технологии. - 1997. - Вып. 8. - 6-16.

23. Марков А.А. Моделирование информационно-вычислительных процессов. - М.:Изд-во МГТУ им. Н.Э.Баумана, 1999. - 358 с.

24. Мескон М.Х., Альберт М., Хедоури Ф. Основы менеджмента : Пер. с англ. - М.:Дело ЛТД, 1995. - 704 с.

25. Парлетт Б, Симметричная проблема собственных значений. Численные методы : Пер. с англ., - М.:Мир, 1983. - 384 с.

26. Рыбин СВ. Коммуникация интеллектуальных объектов в информационных системах с помощью ограниченного естественного языка // Ком-пьюЛог. - 1998. - № 2. - 47-55.

27. Тихонов В.И., Миронов М.А. Марковские процессы. - М.: Советское радио, 1977.-488 с.

28. Трауб Дж., Вожьняковский X. Общая теория оптимальных алгоритмов : Пер. с англ. - М.: Мир, 1983. - 382 с.

29. Уолрэнд Дж. Введение в теорию сетей массового обслуживания : Пер. с англ. - М.: Мир, 1993. - 336 с.

30. Феррари. Д. Оценка производительности вычислительных систем : Пер. с англ. - М.: Мир, 1981. - 576 с.

31. Хемминг Р.В. Численные методы для научных работников и инженеров : Пер. с англ. - М.: Наука, 1972. - 400 с.

32. Хорн Р., Джонсон Ч. Матричный анализ : Пер. с англ. - М.: Мир, 1989.-655 с.

33. Шнитман В. Современные высокопроизводительные компьютеры. -М.: Издательство МГУ, 1996. - 120 с.

34. Шоу А. Логическое проектирование операционных систем : Пер. с англ.-М.: Мир, 1981.-360 с.

35. CCITT. Recommendation G.957: Optical interfaces for equipments and systems relating to the synchronous digital hierarchy. - Geneva, 1990. - 29 p.

36. CCITT. Recommendation G.958: Digital line systems based on the synchronous digital hierarchy for use on optical fiber cables. - Geneva, 1990. - 23 p.

37. Gheith Ali Abandah. Tools for Characterization Distributed Shared Memory Applications // Computer System Laboratory, HP Laboratories. - 1996. -ReportHPL-96-157.-26p.

38. Gheith Ali Abandah. Characterizing Shared-Memory Applications: A Case Study of the NAS Parallel Benchmarks // Computer System Laboratory, HP 1.aboratories. - 1997. - Report HPL-97-24. - 21 p.

39. Gheith Ali Abandah, Edward S. Davidson. Origin 2000 Design Enhancements for Communication Intensive Applications // PACT'98. - Paris, 1998.-10 p.

40. Bogineni K. Design and Performance Analysis of Optically Interconnected Parallel Computers: PhD thesis. - NY: State University of New York at Buffalo, 1993.-21 p.

41. Bogineni K., Dowd P.W. An optically interconnected distributed shared memoiy system: Architecture and performance analysis // International Journal on High Speed Computing. - 1992. -Vol. 4. - P . 179-212.

42. Brackett C.A. Dense wavelength division multiplexing networks: Principles and applications // IEEE Journal on Selected Areas of Communications, I990.-Vol. 8 . -P . 948-964.

43. Design Optimization for High-speed Per-address Two-level Branch Predictors / I-Cheng K. Chen, Chin-Chieh Lee, Matt Postiff, Trevor Mudge. -MI: University of Michigan, 1997. - 9 p.

44. Flynn M. Some Computer Organizations and Their Effectiveness // IEEE Trans. Computers, 1972. - Vol. 21, № 9. - P. 948-960.

45. Dowd P.W., Bogineni K. Performance and simulation techniques for optically interconnected distributed shared memory computer systems // Proc. International Conference on Simulation in Engineering Education. - 1992. -P. 31-35.

46. Dowd P.W., Bogineni K., Aly K.A., Perreault J. Hierarchical scalable pho tonic architectures for high-performance processor interconnection // IEEE Transactions on Computers. - 1993. - Vol.42. - P. 1105-1120.

47. Dowd P.W. Optical interconnections for computer communications // IBM Corporation. - 1989. -Tech. Rep. TR01.A961. - 56 p.

48. Dowd P.W., I-Shyan Hwang. Memory and Network Architecture Interaction in an Optically Interconnected Distributed Shared Memoiy System. -NY: State University of New York at Buffalo, 1994. - 29 p.

49. Dragone C, Edwards C, Kistler R. Integrated optics nxn multiplexer on sili con // IEEE Photonic Technology Letters. - 1991. - Vol. 3. -P. 896-899.

50. Rod Fatoohi. Performance Evaluation of Communication Networks for Dis tributed Computing // NASA Ames Research Center Moffett Field, Califor nia. - 1995. - Report NAS-95-009. - 18 p.

51. Rod Fatoohi. Performance Evaluation of Communication Software Systems for Distributed Computing // NASA Ames Research Center Moffett Field, California. - 1996. - Report NAS-96-006. - 15 p.

52. PVM: Parallel Virtual Machine - A User's Guide and Tutorial for Network Parallel Computing/ Al Geist, Adam Beguelin, Jack Dongarra and etc. -Cambridge, Massachusetts, London, England: The MIT Press, 1994. - 279 p.

53. Green P. Fiber Optic Networks. - NY: Prentice Hall, 1993. - 170 p.

54. The Performance of the Intel TFLOPS Supercomputer / Greg Henry, Pat Fay, Ben Cole and etc. // Intel Technology Journal. - 1998. - Ql. - 11 p.

55. Bruce L. Jacob, Trevor N. Mudge. A Look at Several Memory Management Units, TLB-Refill Mechanisms, and Page Table Organizations // ASPLOS. -(CA, USA). - 1998. - VIII 10/98. - 12 p.

56. Bruce L. Jacob, Trevor N. Mudge. Notes on Calculating Computer Performance // University of Michigan. - 1995. - Tech Report CSE-TR-231-95. -10 p.

57. Jacob B.L., Mudge T.N. Software-Managed Address Translation // Proc. Third Int'l Symp. High Performance Computer Architecture (HPCA-3). -1.os Alamitos (Calif.), 1997.-P. 156-167.

58. An Analytical Model for Designing Memory Hierarchies / Bruce L. Jacob, Peter M. Chen, Seth R. Silverman and etc // IEEE Transactions on computers. - 1996. - Vol. 45, № 10. - P. 100-116.

59. Kane G., Heinrich J. MIPS RISC Architecture. - Englewood Cliffs (N.J.): Prentice-Hall, 1992. - 150 p.

60. Krishnamurthy E.V. Parallel Processing Principles and Practice. - NY:Addison-Wesley Pub. Company, 1989. - 250 p.

61. James Laudon, Daniel Lenoski. The SGI Origin: A ccNUMA Highly Scalable Server. - Mountain View (California): Silicon Graphics, Inc, 1998. -l i p .

62. John H. Mathews, Numerical methods for Mathematics, Science, and Engineering: Second Edition. - Englewood Cliffs (NJ): Prentice hall Inc., 1992. -170 p.

63. John H. Mathews, Pascal Programming Guidebook for Numerical methods. - Englewood Cliffs (NJ): Prentice hall Inc., 1995. - 73 p.

64. MIPS RIOOOO Microprocessor User's Manual: Version 2.0. - Mountain View (California): MIPS Technologies Inc., 1997. - 254 p.

65. MPI: A Message-Passing Interface Standard. - Knoxvill (Tennessee): University of Tennessee, 1995. -239 p.

66. Pentium Processor User's Manual. - USA:Intel Coфoration, 1993. - 272 p.

67. Mudge T.N., Al-Sadoun H.B. A semi-markov model for the performance of multiple-bus systems // IEEE Transactions on Computers. - 1985. - Vol. C-34 . -P . 934-942.

68. MPI: The complete reference / Marc Snir, Steve Otto, Steven Huss- 1.ederman, etc. - Cambridge (Massachusetts) - London (England): The MIT Press, 1996.-350 p.

69. Andrew Sohn, Rupak Biswas. Communication Studies of DMP and SMP Machines // NASA Ames Research Center Moffett Field (California). -1997. - Report NAS-97-005. - 16 p.

70. Using MATLAB. - USA: MathWorks Inc., 1998. - 276 p.

71. Abdul Waheed, Jerry Yan. Performance Modeling and Measurement of Parallelized Code for Distributed Shared Memory Multiprocessors // NASA Ames Research Center Moffett Field (California). - 1998. - Report NAS-98-012.-22 p.