Содержание к диссертации
Введение
1. Проблема оценки времени выполнения взаимодействующих параллельных вычислительных процессов в параллельных вычислительных системах 13
1.1. Системы реального времени, некоторые аспекты технологии их проектирования 13
1.2. Понятие аппаратно-программного дуализма 17
1.3. Параллельные вычислительные процессы 20
1.4. Бортовые мультипроцессорные вычислительные системы и проблемы их моделирования 23
1.5. Имитационное моделирование вычислительных систем 28
1.6. Основные понятия и формальное описание сетей Петри , 34
1.7. Сравнительный анализ известных модификаций формализма сетей Петри 39
Выводы 58
2. F-сети петри 60
2.1. Принципы расширения сетей Петри до F-сетей 60
2.2. Формальное описание F-сетей 65
2.3. F-сети и сети автоматов 76
2.4. Вербальное описание основных примитивов 84
2.5. Формальное описание процедур срабатывания переходов 88
2.6. Операции на F-сеіих 107
2.7. Анализ F-сетей Петри, алгоритм построения дерева достижимых маркирований , 110
Выводы 116
3. Принципы создания комплекса программ для имитационного моделирования мультипроцессорных вычислительных систем на основе использования f-сетей 118
3.1, Основные принципы создания комплекса программ 118
3.2, Проблемы построения подсистемы эмуляции для моделирования МВС и принципы их разрешения при использовании аппарата F-сетей 122
3.3. Таблицы решений и их использование в автоматах F-сетей для описания, разбора и исполнения двоичного кода 132
3.4. Технические предложения по архитектуре подсистемы эмуляции 143
Выводы 152
4. Примеры использования f-сетей для моделирования вычислительных систем 153
4.1. Многомашинная бортовая вычислительная система с кольцевой магистралью и маркерным методом доступа 153
4.2. Бортовая вычислительная система ЦВМ 80-400 165
4.3. Моделирование раоты юш-памяти 169
4.4. Методика построения F-сетевых имитационных моделей . 179
Выводы 182
Заключение 183
Список литературы
- Понятие аппаратно-программного дуализма
- Основные понятия и формальное описание сетей Петри
- Таблицы решений и их использование в автоматах F-сетей для описания, разбора и исполнения двоичного кода
- Моделирование раоты юш-памяти
Введение к работе
Решаемая научно-техническая проблема - это моделирование в общем случае неоднородных мультипроцессорных вычислитальных систем, что позволяет осуществлять комплексное тестирование разрабатываемого программного обеспечения для систем реального времени параллельно с проведением работ по созданию аппаратных средств.
Актуальность темы диссертационной работы связана с необходимостью иметь эффективные, простые и удобные методы и средства, которые бы позволяли разработчикам моделировать мультипроцессорные вычислительные системы (МВС) реального времени на уровне выполнения параллельных взаимодействующих программ, что позволяет ускорить проектные работы и снизить затраты на их проведение.
При создании современных вычислительных комплексов и систем, в том числе и распределенных бортовых вычислительных комплексов (РБВК), разработчики сталкиваются с целым комплексом сложнейших проблем. Расширяющийся перечень задач, решаемых средствами вычислительной техники, децентрализация средств их решения, широкое распараллеливание вычислительных процессов, возрастающие требования по производительности и обеспечению надежности - вес эти факторы вызывают не только увеличение производительности средств вычислительной техники за счет повышения тактовой частоты процессоров, но и рост числа вычислителей, устройств ввода-вывода, другого автоматизированного оборудования, что, в свою очередь, выдвигает на первый план проблему создания эффективных и высоконадежных вычислительных систем. Довольно часто возникает необходимость в заказных вычислительных систем, выполняющих ограниченный узко специализированный набор функций в заданных условиях эксплуатации. Речь идет, прежде всего, о бортовых цифровых вычислительных системах и комплексах (БЦВС). а также системах передачи информации. Подобные БЦВС обладают рядом характерных отличий, среди которых следует выделить:
функционирование в реальном масштабе времени, что объясняется ограничениями, накладываемыми на время выполнения ряда функций системы;
наличие нескольких источников входных задач (ввод-вывод информации в каналы связи, обработка данных с датчиков, выполнение команд контроллеров и устройств ввода-вывода и т. д.), при
этом БЦВС должна эффективно распределять свои ресурсы, ограниченность которых (вычислительная мощность, емкость ОЗУ, пропускная способность каналов связи и магистралей) является причиной конкуренции задач за данные ресурсы;
дублирование выполнения наиболее важных функций и некоторых
оїдельньїх вычислителей и подсистем для повышения надежности и
живучести БЦВС.
В последние годы появились комплексы вычислительного оборудования, которые разрабатываются в виде вычислительных модулей, модулей памяти, модулей ввода/вывода и т.д.. Модули являются информационно, электрически и конструктивно совместимыми и представляют собой ряд унифицированных модулей, на основе которых могут быть созданы вычислительные системы различной конфигурации (ярким примером этого подхода являются компоненты, на основе которых создаются разнообразные конфигурации персональных компьютеров). Гарантией производительной и безотказной работы всей системы являются не только удачное архитектурное решение и надежность самих компонентов, но и четкое выполнение спецификаций ее архитектурной основы - системного интерфейса, а также базового системного программного обеспечения (ПО).
Современные вычислительные системы имеют несколько параллельно функционирующих активных компонентов, таких как центральный процессор или множество процессорных элементов (их может быть несколько в мультипроцессорной ВС), процессоры и контроллеры ввода-вывода для управления различными периферийными устройствами, а также - сами внешние устройства (датчики и исполнительные механизмы). При проектировании таких сложных вычислительных систем и, в частности, при разработке ПО, непосредственно связанного с управлением объектами и процессами, естественно возникают задачи моделирования их работы с целью проверить правильность алгоритмов и программ с учетом их взаимодействия, оценить реальное быстродействие системы и имеющиеся резервы, по возможности найги наиболее эффективные пути и способы увеличения производительности как отдельных компонентов, так и всей системы в целом, а где возможно, то и снизить требования по быстродействию. Особенно важное значение по возможным последствиям от ошибочных результатов оценки предлагаемых решений приобретет моделирование на самых начальных этапах проектирования и, в частности, на этапе составления технического задания на вычислительную систему в целом и ее отдельные компоненты.
Порядок и скорость обмена синхросигналами и данными между компонентами вычислительной системы (в особенности, мультипроцессорной) зависят не только от их быстродействия и принятых протоколов взаимодействия на аппаратном уровне, но и от программ, организующих этот обмен, и даже от функциональных (прикладных) программных модулей. Другими словами, иа эффективность обмена влияют как архитектура МВС (ее структура, принятые интерфейсы, система команд и форматы данных) и ее конфигурация, так и программное обеспечение. Более того, если разработка аппаратных и программных компонентов РБВС осуществляется параллельно, то при использовании соответствующих инструментально-технологических средств появляется возможность влиять на эффективность работы системы в целом, изменяя либо алгоритмы (многократно исполняемые протоколы взаимодействия, канальные программы и драйверы), либо параметры быстродействия отдельных модулей аппаратуры, либо используя другой системный интерфейс.
Очевидно, что для решения такой нетривиальной задачи необходимо иметь адекватный математический аппарат, методы его использования и модели-примитивы, а также соответствующие инструментально-технологические средства. Для исследования дискретных параллельных асинхронных процессов, которые характерны для вычислительных систем, активно используют аппарат сетей Петри. Сети Петри являются одним из современных и перспективных формализмов, посредством которого могут решаться многочисленные научные и практические задачи. Более того, некоторые задачи могут быть успешно решены только с привлечением методов и алгоритмов анализа объектов, разработанных в рамках теории сетей Петри. Известны комплексы программ, с помощью которых можно решать отдельные задачи, но зачастую их возможности далеки от желаемых- В настоящее время исследования и разработки в данной области прежде всего проводятся за рубежом (преимущественно в США, Германии, Франции, Италии, Украине, Литве, Канале, Бразилии. Австралии, Чехии, Польше, Южно-Африканской республике и в ряде других развитых стран), и в России (Новосибирск, Москва, Санкт-Петербург, Пермь, Пенза и др.). Однако, при этом теоретические и прикладные возможности данного математического аппарата находятся все еще в стадии интенсивного развития и настоятельно требуют расширения как круга своих исследователей, так и различных пользователей из разнообразных предметных областей.
Ііель диссертационной работы состоит в разработке новых методов и средств моделирования, которые позволят исследовать мультипроцессорные вычислительные системы не только на уровне традиционного подхода к имитационному моделированию, но и на уровне исполнения машинного кода процессорными элементами и оценивать функционирование системы с учетом масштаба реального времени и взаимодействия параллельных вычислительных процессов.
Основные задачи. В процессе выполнения исследований в рамках диссертационной работы решались следующие задачи:
Анализ состояния работ по созданию методов и соответствующих программно-инструментальных средств моделирования, анализа и отладки архитектуры и конфигурации вычислительных систем (в том числе и бортовых) с учетом конкретных параллельных вычислительных процессов (системных и прикладных), развивающихся и взаимодействующих при функционировании системы.
Анализ различных модификаций сетей Петри с целью определения возможности и целесообразности их использования для моделирования МуЛЬТИПрОцеССОрНЫХ ВЫЧНСЛИТеЛЪНЫХ СНСТЄМ (С уЧСГОМ ОСО-
бенносгей выполнения параллельных вычислительных процессов) и использования в новой модификации сетей Петри - F-сетях,
Разработка нового формализма, позволяющего адекватно моделировать развитие дискретных параллельных асинхронных процессов и преобразование информации при функционировании системы.
Разработка методов и средств эмуляции программ с учетом архитектуры не только вычислительного комплекса в целом, но и архитектурных особенностей отдельных процессоров и подсистем на основе настраиваемых таблиц решений эмулятора и представления системы в виде сетевых моделей для оценки качества программно-аппаратных средств с учетом реального времени.
Разработка моделей (примитивов) основных компонентов мультипроцессорных вычислительных систем и некоторых других сложных систем, методики и средств автоматизированного построения F-сетевых моделей.
Разработка концепции, архитектуры и макета программно-инсгрументальных средств для ПЭВМ типа IBM PC для моделирования и оценки качества вычислительных систем и комплексов автоматизированного оборудования (в том числе и бортового) на различных уровнях их представления.
Методы исследования» Для решения поставленных задач использовались методы дискретной математики (в частности, теории множеств, теории графов, теории автоматов), алгоритмизации и программирования
(теория алгоритмов, теории параллельных взаимодействующих процессов), основ вычислительной техники, теории сетей Петри.
Научная новизна. Б ходе выполнения исследований в рамках диссертационной работы получены следующие научные результаты:
разработан метод моделирования неоднородных мультипроцессорных и многомашинных вычислительных систем на уровне параллельного исполнения программного кода, заключающийся в разборе и исполнении машинных команд с помощью таблиц решений, и синхронизации работы компонентов аппаратуры с помощью специально модифицированных сетей Петри;
разработана модификация сетей Петри - F-сети, которые дают возможность моделировать и осуществлять количественный и качественный анализ сложных систем с параллельными дискретными процессами с учетом масштаба времени и отображением с необходимой детализацией основных нюансов их функционирования;
предложен алгоритм построения дерева достижимых маркирований F-сетевых моделей для анализа систем, представляемых F-сетями;
создана методика построения F-сетевых моделей сложных систем с дискретными параллельными процессами, заключающаяся в использовании как операций объединения ранее созданных сетевых фрагментов, так и заранее созданных библиотечных модулей, специально ориентированных на решение определенных задач из заданной предметной области;
предложен метод создания алгоритмов и программ для решения задач, представленных таблицами решений.
Практическая значимость работы. В результате выполненной диссертационной работы можно констатировать следующее:
Создано несколько программных макетов и законченных про
граммных средств для моделирования и анализа систем, представ
ленных F-сетями Петри:
"Подсистема имитационного моделирования бортовых цифровых вычислительных систем на основе модифицированных сетей Петри", 1990 г. - по заказу НИИАО;
Электронный учебник Ь1Сети Петри: Моделирование и анализ", 1992 г. - по заказу РосНИИИС;
"Интегрированная система моделирования и анализа на основе сетей Пеіри", 1994 і\ - по заказу С.-Пб. РФНТР;
"Сети Петри для Windows11 (версии КО, 1995г. и 2.2, 1996г.) по заказу РосНИИИС.
в процессе проведения ряда НИР промоделировано несколько сис
тем, в том числе микропроцессорная система диспетчерского кон-
[J
троля и управления устройствами электроснабжения железных дорог, варианты бортовых цифровых вычислительных систем ЦВМ 80-400 и СБ3541, перспективной РБВС "ь Кентавр** (работы проводились в рамках НИР-781, утвержденной приказом МинВУЗа РСФСР N 00147 от 12.11.87г.) и др., что позволило оценить и подтвердить правильность и эффективность проектных решений.
Комплекс программ "Сети Петри для Windows"» который имеет все
Необходимые ВСТрОеННЫе СреДСТВЭ обуЧСНИЯ. ИЄПОЛЬЗуЄТСЯ ЛрИ ІІОД-
готовке магистров по направлению 552800 в рамках специализации "Высокопроизводительные вычислительные системы". Названный комплекс программ используется в Санкт-Петербургском государственном техническом университете на кафедре автоматики и вычислительной техники при подготовке студентов по специальности 22,01 "Вычислительные машины, комплексы, системы и сети11 и в Санкт-Петербургском электротехническом университете на кафедре АСОИиУ при подготовке студентов по специальности 22.02 "Автоматизированные системы обработки информации и управления".
Основные результаты диссертационной работы реализованы в программном комплексе моделирования и анализа "Сети Петри для Windows1'. Программный комплекс предназначен для построения F-сетевых моделей различных систем, содержащих параллельно протекающие асинхронные процессы, имитационного моделирования со сбором статистики, анализа построенных моделей, а также для обучения методам имитационного моделирования. Программный комплекс функционирует на персональной ЭВМ типа IBM PC/AT при наличии не менее 4 Мб ОЗУ и 1800 Кб свободного пространства на жестком диске под управлением MS DOS в графической среде MS Windows 3.x или в Windows-95 и позволяет решать следующие задачи: ввод и редактирование моделей на основе F-сстсй в графическом режиме; хранение построенных сетевых моделей в виде файлов на диске; создание из сетевых моделей библиотек примитивов с приложением описаний и подсказок в формате Windows; автоматизированное построение модели системы из заранее созданных моделей подсистем и примитивов; моделирование функционирования F-сетей со сбором статистических данных в автоматическом режиме и в режиме пошагового прогона модели с целью ее отладки; анализ модели на основе классических сетей Петри; построение дерева достижимости для моделей на основе F-сстей.
Основные положения, выносимые на защиту:
Формализм новой модификации оценивающих сетей - F-сети, ко
торые ориентированы на имиїационное моделирование сложных
систем с дискретными асинхронными процессами с учетом масштаба времени и, прежде всего, для мної процессорных и многомашинных вычислительных систем.
Метод моделирования мультипроцессорных и многомашинных вычислительных систем на уровне параллельного исполнения программного кода, заключающийся в разборе и исполнении машинных команд с помощью таблиц решений, и синхронизации работы компонентов аппаратуры с помощью специально модифицированных сетей Петри,
Алгоритм построения дерева достижимых маркирований F-еетевых моделей для анализа систем с дискретными параллельными асинхронными процессами, для которых важен учет масштаба времени,
Принципы создания комплекса программ и алгоритмы работы основных модулей системы моделирования и анализа объектов с дискретными параллельными асинхронными процессами, представляемых F-сетями, методика построения F-сетевых моделей сложных систем.
Внедрение. Результаты диссертационной работы использованы в следующих организациях:
НИИВМПУ , в/ч 25970 (НИР-524, шифр темы Экзамен-РВО);
п/я Ю-9539 (НИ Р-781, шифр темы Нева);
СПбПЭТУ (НИР-429, НИР-483, НИР-648, шифр темыЖердь-РВО);
в учебном процессе в СПбГТУ, СПбГЭТУ, СПбГУАП при подготовке студентов по специальности 22.01 и 22.02,
Апробация работы. Основные результаты и положения диссертационной работы докладывались и обсуждались на следующих научно-технических конференциях, семинарах и симпозиумах:
Общеинститутская научно-іехническая конференция ЛИ АГТ "НТК-37", Ленинград, 1987г.;
Совещание-семинар по учебно-исследовательским САПР, Ленинград, 1938;
Научно-практический семинар 'Технология проектирования программных и аппаратных средств вычислительных систем". ЛДНТП, Ленинград, 1989, 1990 гг.
X Симпозиум по проблеме избыточности в информационных системах. Ленинград, 1989.
111 Всесоюзная конференция ''Качество программных средств1'. Дагомыс, 1991.
Всероссийская научно-техническая конференция с международным участием "Информационно-управляющие и вычислительные ком-
плексы на основе новых технологий. Conference Inter Aero Space Systems". Санкт-Петербург, 1992.
Научно-техническая конференция "Техническое диаглостирование-93". Санкт-Петербург, 1993.
Научное совещание по проблемам безопасности программного обеспечения, в/ч 30895, 1993,
Научно-техническая конференция "Диагностика, информатика и метрология -94". Санкт-Петербург, 1994.
Вторая международная школа-семинар "Новые информационные технологии". Гурзуф, 1994.
Научно-техническая конференция "Диагностика, информатика и метрология -95". Санкт-Петербург, 1995.
Научная воєнно-техническая конференция "Автоматизация процессов управления соединениями и частями ПВО, информационные технологии.'1 Санкт-Петербург, 1996.
Международный симпозиум по проблемам модульных информационных компьютерных систем и сетей. Санкт-Петербург, 1997.
Публикации. По теме диссертационной работы опубликовано 17 статей и тезисов докладов, 1 учебное пособие и 3 электронных монографии:
Электронный учебник "Сети Петри: Моделирование и анализ", 1992 г. - по заказу РосНИИИС;
"Интегрированная система моделирования и анализа на основе сетей Петри", 1994 г. - по заказу С.-Пб. РФНТР;
"Сети Петри для Windows" (версия 2.2, 1996г.) по заказу РосНИИИС.
Основные положения диссертационной работы отражены в ряде отчетов по НИР, выполненных в ГУАП (ГААП, ЛИАП), СевероЗапад-ном центре новых информационных технологий (СЗРЦНИТ, Санкт-Петербург), СПбИИТ, СПбГУ и СПбГЭТУ в 1986-95 гг..
В частности, в материалах по НИР-657 (ЛИАП), выполненной в 1987г., были изложены методы и средства системного и функционального моделирования для решения задач проектирования цифровой аппаратуры. Методика построения сетевых имитационных моделей для исследования структуры вычислительных систем была разработана в процессе выполнения НИР-781. Материалы этой темы были изложены в отчетах ГР № Х74995 (промежуточный отчет) и ГР № Г22499 (заключительный отчет). В отчетах приведены сетевые примитивы для построения моделей, разработанные имитационные модели различных вычислительных систем и результаты их моделирования.
В материалах НИР, проводимых с НИИЛО, были изложены основные принципы и архитектура подсистемы имитационного моделирования для исследования и разработки интегрированных систем навигации, посадки, связи и опознавания.
При выполнении в 1992 г. работ по заказу НИЦ информационных систем (Москва) были исследованы вопросы разработки программно инструментальных средств создания бортовых вычислительных систем и комплексов автоматизированного оборудования.
Разработанные в диссертационной работе формализм F-сетей и методы моделирования дискретных параллельных систем на его основе были применены при выполнении НИР по заказу СПбГЭТУ (ЛЭТИ) "Разработка методов и алгоритмов моделирования и анализа для исследования компонентов и подсистем автоматизированной системы обработки информации в комплексах сигнально информационных средств с целью повышения их тактико - технических характеристик", которые проводились в 1991-1995 гг. Результаты этой работы (Методы и алгоритмы моделирования и анализа развития событий на контролируемой іерритории в ЦОРИ КРСС) имеются в 01 четах СПбГЭТУ, имеются акты об использовании результатов диссертационной работы.
Ряд результатов диссертационной работы был получен и использован при выполнении НИР по заказу НИИ вычислительной математики и процессов управления при Санкт-Петербургском государственном университете. Работы выполнялись в рамках НИР "Поисковые исследования и разработка математических методов многокритериального оценивания вариантов управленческих и организационных решений по проектированию и созданию СВТС с целью повышения их эффективности и качества в условиях неполной информации71.
В отчетах по НИР СЗРЦ новых информационных технологий (Санкт-Петербург) за 1992г. представлены экспертно-имитационные модели системы диспетчерского контроля и телемеханического управления устройствами электроснабжения железных дорог, которые были разработаны по заказу Санкт-Петербургского университета путей сообщения.
Результаты разработки математических методов, моделей и программных средств поддержки анализа и прогнозирования вариантов развития кризисных и конфликтных ситуаций с использованием нечисловой: неточной и неполной информации изложены в отчетах ЗАО "Академия".
Понятие аппаратно-программного дуализма
Рассмотрим одно из представлений фундаментального понятия информатики - понятия алгоритма как о некотором детерминирован-ном устройстве, способном выполнять в каждый отдельный момент лишь весьма примитивные операции. Такое представление не оставляет сомнений в однозначности алгоритма и элементарности его шагов. Кроме того, эвристика этой модели наиболее близка к вычислительной технике и. следовательно, к инженерной интуиции [ 145 ]. Основной такой теоретической моделью алгоритма, созданной в 30-х годах XX века английским математиком Аленом Тьюрингом, является машина Тьюринга. Машина Тьюринга. Машина Тьюринга состоит из следующих компонентов [ 97 ]:
управляющего устройства (автомата), которое может находится в одном из состояний, образующих конечное множество Q Q=f4j 4i Ч qH} ;
бесконечной ленты, разбитой на ячейки, в каждой из которых может быть записан один из символов конечного алфавита А А=}а],а2,„,,а};
устройства обращения к ленте, т.е. считывающей и пишущей го ловки, которая в каждый момент времени обозревает ячейку лен ты и, в зависимости от символа в этой ячейке и состояния управ ляющего устройства, записывает в ячейку символ (быть может, совпадающий с прежним, или пустой, т.е. стирает символ), сдви гается на ячейку влево или вправо или остается на месте. При тгом управляющее устройство переходит в новое состояние (или остается в старом).
Память машины Тьюринга - это конечное множество состояний автомата (внутреняя память) и лента (внешняя память). Данные машины Тьюринга - это слова в алфавите лентьт. На ленте записываются и исходные данные, и промежуточные, и окончательные результаты. Схематично машина показана на рис.1.3,
Элементарные шаги машиньг- это считывание и запись символов, сдвиг головки на ячейку влево или вправо, а также переход управляющего устройства в следующее состояние. Последовательность шагов машины описывается системой правил (продукций), имеющих вид if (qi aj then (ц\ aTj dk) (где dk - перемещение головки чте ния-записи на один шаг вправо или влево), либо таблицей, строкам которой соответствуют состояния, столбцам - входные символы, а на пересечении строки q( и столбца а; располагаются символы (qt а = dk).
Машина Тьюринга полезна как формальное "уточнение" понятия алгоритма, К недостатку модели Тьюринга обычно относят тот факт, что программа работы машины Тьюринга мало напоминает нам понятие алгоритма именно как последовательности действий. Программа ее работы представляется в виде совокупности продукций, а не в виде четкой последовательности команд. Другими словами, здесь мы скорее имеем дело с множеством правил ее работы, т. е. с так называемым продукционным, а не с алгоритмическим подходом к программированию.
Машина Поста. "Конструктивно" машина Поста полностью аналогична машине Тьюринга, т.е. также состоит из управляющего автомата с головкой чтения и записи, и внешней памяти в виде ленты с записанными на ней словами. Однако в алгоритмического подхода к программированию и вместо правил работы автомата мы описываем алгоритм ее работы (программу) в виде последовательности однозначно понятных противоположность машине Тьюринга, машина Поста существенно ближе к парадигме действий.
Программы состоят из команд. Запись команд дія машины Поста имееі три поля: номер команды, операция и отсылка. Команды нумеруются, начиная с 1. Выполнение программы начинается с команды номер 1. Отсылка показывает, какую команду нужно выполнять после текущей. Что касается видов операциий, то определены следующие пягь элементарных операций [ 144 ]: — - движение головки на одну ячейку ленты вправо; движение головки относительно ленты на одну ячейку влево; S - запись в обозреваемую ячейку ленты произвольного символа S из алфавита А машины Поста, s є А ; fsi Ni 7 - операция передачи управления (команда разветвления)
Здесь sji, Sj2 -некоторыесимволы из алфавита А ; Ni, N2 - отсылки. По этой команде анализируется обозреваемый в ячейке символ. Если он совпадает cs;i .то следующей будет выполнятся команда с номером N1, При этом головка никуда не перемешается и на ленту ничего не записывается. Если в ячейке ленты оказался некоторый символ Sjk, неупомянутый в текущей команде разветвления, то происходит аварийный останов машины;
Stop - завершение работы машины Поста; в отсылке не нуждается. В своей работе Пост говорил не о машине» но о некотором решателе проблемы или исполнителе алгоритма. В обоих рассмотренных случаях на ленте записываются данные, которые обрабатываются в соответствии с этим алгоритмом. И в машине Тьюринга, и в машине Поста исполнитель алгоритма представляется как некий автомат, однако операции машины Поста более примитивны по сравнению с машиной Тьюринга, автомат машины Поста имеет меньшее число состояний и , как правило, программа решения задачи для машины Поста имеет большее количество шагов [ 144].
В общем случае в обеих машинах переход автомата (исполнителя, вычислительной машины) из одного состояния в другое определяется не только заданием этого автомата - алгоритмом решения задачи, но и теми данными, которые обрабатываются по алгоритму. Другими словами, функционирование вычислительной системы и текущее состояние ее компонентов определяются и работой аппаратуры, и программным обеспечением, и обрабатываемыми данными, т, е, вычислительными процессами, в ней протекающими. Назовем это аппаратно-программным дуализмом. Адекватный математический аппарат, моделирующий функционирование вычислительной системы, в идеале должен отображать эту особенность - протекание информационных процессов на уровне исполнителя (аппаратуры), и в виде информационной сущности вычислительного процесса. Для машины фон Неймана адекватной моделью может выступать автомат, но для параллельных вычислительных структур с парахтельным взаимодействующими вычислительными процессами нужны другие модели.
Наконец, заметим, что если говорить о любой возможной практической реализации автомата (вычислительной системы), то очевидным становится тезис о том, что время выполнения программы будет зависеть как от алгоритма и исходных данных, так и от времени выполнения элементарных операций машины (системы).
Основные понятия и формальное описание сетей Петри
Среди многих существующих методов описания и анализа параллельных систем уже более 35 лет значительное место занимают сетевые модели, восходящие к сетям специального вида, предложенных в 1962 г. Карлом Петри для моделирования асинхронных информационных потоков в системах преобразования данных [95, 118, 135].
Взаимодействие событий в параллельных асинхронных дискретных системах имеет, как правило, сложную динамическую структуру. Эти взаимодействия описываются более просто, если указывать не непосредственные связи между событиями, а те ситуации, при которых данное событие может реализоваться. При этом глобальные ситуации в системе формируются с помощью локальных операций, называемых условиями реализации событий. Условие соответствует таким ситуациям в моделируемой системе, как состояние того или иного компонента системы (занято - свободно, готово не готово, и т.д.), наличие данного для операции в команде или в программе, наличие нужного тома в накопителе данных и т.п. [ 95 ]. Определенные сочетания условий разрешают реализоваться некоторому событию (предусловия события), а реализация события изменяет некоторые условия (постусловия события), т.е. события взаимодействуют с условиями, а условия - с событиями. Таким образом, предполагается, что для решения задач достаточно представить системы как структуры, образованные из элементов двух типов - событий и условий.
В сетях Петри события и условия представлены абстрактными символами из двух непересекающихся алфавитов, называемых соответственно множеством переходов и множеством позиций. Имеется несколько формальных представлений сетей Петри [ 125]: іеорегико-множесгвенное; графовое - бихроматический (двудольный ориентированный) граф и, соответственно, графическое; матричное.
При использовании теоретико-множественного подхода к описанию сети Петри (поскольку эта модель представляет и структуру, и функционирование системы) она формально может быть определена как двойка вида: N= S, Мп . Здесь S - это структура сети, которая представляется двудольным ориентированным мультиграфом S = (V, U), где V-вершины этого графа, U-ero дуги, Mfl - начальное состояние сети Петри, которое также называется начальной маркировкой- В силу того, что граф S является двудольным, можно перейти к формальному описанию структуры сети Пегри в виде тройки: S= P,T,Y , где Р - конечное множество позиций, P = {ps}, і = 1,п ; Т -конечное множество переходов, Т= JtjK j = l,m; TL)P = V, ТПР-0, i.e. Т и Р - два типа вершин биграфа S ; Y - конечное множество дуг, заданное отношениями между вершинами графа S : Y e(P T)U(T Р)
Поскольку двудольный мультиграф S является ориентированным, то любой переход tj, j-1,m соединяется с позициями Pj еР через входные и выходные дуги, которые задаются через функцию предшествования В : (Р Т)- {0,1,2...} и через функцию следования Е : (Т Р)- J0,1,2...J, являющиеся отображениями из множества переходов в комплекты позиций [ 125 ] (синонимом термина комплект является понятие мультимножества). Эти функции определяют комплекты позиций {pj єР, связанных с переходом t: єТ через множество дуг Kpi,tj)]h ГДЄ 1 {(Pi,tj) : і, j — const}! , W и комплекты позиций рьїєР, связанных с переходом tj єТ через множество дуг HtpPkhb гДе 1 ifttj,Pk) : j, k = con$tj W\ Здесь W - мультичисло графа S; Р - пространство комплектов, заданное на множестве Р функциями Е и В; (Pi,tj)v - v-ая дуга, выходящая из позиции р, и входящая в переход tp (tj,pk)T - v-ая дуга, выходящая из перехода tj и входящая в позицию рк.
Таким образом, теперь структура S сети Петри N может быть представлена как четверка: S= P,T,B,E . Представим множество позиций Р как объединение двух пересекающихся множеств: p=IUO; ІПО 0 . Здесь мы через I и О обозначим следующие множества: m іл i=UKtj); о=ио , І=І j=i rael tj)4Pi : B(Pi,tj) l, і-МІ, і = Гт; (Xtj)-!pb : E(t,,pk)al, k=MK І-Мі; (Pj,t:) - дуга с весом w W, выходящая из вершины р и входящая в вершину t-,; (tjiPb) " дуга с весом w W, выходящая из вершины t и входящая В ВерШИну рк, Т.Є. I(tj) И 0(tj) - КОМПЛеКТЫ СООТВетСТВенНО входных и выходных позиций перехода t j.
Элементы множества Т обычно представляют собой те возможности (возможные ситуации, условия), при которых могут быть реализованы интересующие нас процессы (действия).
Начальная маркировка М0 (как и текущая маркировка М, которая соответствует некоторому состоянию сети в текущий момент модельного времени) определяется одномерной матрицей-вектором, число компонентов которого равно числу позиций сети п, п = Р[, а значение і-го компонента, 1 і , п, есть натуральное число т(р{), которое определяет количество маркеров (меток) в позиции рі, т.е. М0 -(m0(p1),ni0(p2),...mu(pn»; VI-(m(p1),m(p2),...m{pn))1 где т0(р}),т(р;) EZ ; Z - множество неотрицательных целых чисел.
Таблицы решений и их использование в автоматах F-сетей для описания, разбора и исполнения двоичного кода
В соответствии с одной из распространенных технологий создания сложных информационно-управляющих вычислительных систем, в том числе и бортовых, разработчики ведут параллельные работы над проектированием и изготовлением опытного образца аппаратной части и соответствующим функциональным и системным ПО [ 85, 102. Ill, 150 ). Как правило, функциональное ПО разрабатывается в основном на языках высокого уровня (на ассемблере пишутся только драйверы низкого уровня, отдельные наиболее часто используемые подпрограммы, требующие минимального времени исполнения, и аппаратно-зависимые модули системного монитора/операционной сисгемы) и к момешу завершения работ по проектированию бортовой вычислительной системы (БЦВС) осуществляется генерация двоичных кодов программных модулей с помошью соответствующих кросс-систем. При
этом закономерно возникает проблема отладки ПО, и, в общем случае, можно выделить следующие два этапа [ 32. 85, 102т 111т 128т 150];
автономная отладка ПО каждого процессорного блока при имитации данных, поступающих с других процессорных блоков, с помощью средств отладки с использованием эмулятора; при этом производится отладка функционального ПО по детерминированным тестам, проверяется вычислительная и логическая часть программных модулей, приближенно оцениваются и вычисляются их статические и временные характеристики;
испытания на микроЭВМ в условиях реального окружения или полунатурный эксперимент на стенде, имитирующем внешние условия применения микроЭВМ; при этом производится окончательная отладка ПО микропроцессорной системы в целом.
Для моделирования выполнения программ в микропроцессорных системах, в том числе и с параллельными вычислительными процессами, без использования самих аппаратных средств, существует ряд эмуляторов, в том числе и внутрисхемных, по они в большинстве своем ориентированы на конкретный тип микропроцессора и определенную конфигурацию вычислительной среды [ 38, 70, 71, 85, 93, 113 ]. В тех же случаях- когда допускается некоторая гибкость в конфигурации системы, требуется ее дополнительное описание на специально разработанном языке, что естественно.
К системам отладки программ микропроцессоров предъявляются следующие требования: применимость средств отладки для микропроцессоров различных типов (универсальность) ; возможность наращивания и совершенствования функций отладки без изменений основной структуры ; простота общения с системой отладки .
В связи с многообразием типов микропроцессоров и высокой стоимостью отладочных средств, становится актуальным вопрос универсальности средств отладки ПО, разрабатываемого параллельно с созданием аппаратной части будущей БЦВС. Как правило, адаптация средств проектирования к различным микропроцессорам производится заменой соответствующей части программы или заменой/настройкой внутрисхемного эмулятора микропроцессора. Разработка кросс-систем, ориентированных на одну конкретную микроЭВМ. требует существенных трудозатрат (5-И0 человеко-лет). Наиболее перспективным направлением построения кросс-систем, а следовательно и эмуляторов, является использование принципа универсальности, т.е. настройки на заданную архитектуру и систему команд объектной ЭВМ. Универсальные кросс-систсмы сушественно ускоряют пронесе создания программного обеспечения микроЭВМ и, тем самым, уменьшают их стоимость. Однако эмуляторы универсальных кросс-систем существенно проигрывают в производительности внутрисхемным эмуляторам.
Основной недостаток кросс-систем связан с невозможностью полного воспроизведения на инструментальной ЭВМ специфических временных соотношений и условий внешнего окружения объектной машины. По этой причине стали разрабатывать и активно использовать внутрисхемные эмуляторы, в состав которых включаются следующие основные блоки: замещаемый микропроцессор или его функциональный аналог, выполненный в другом конструктивном исполнении; устройства, повторяющие отдельные внутренние узлы эмулируемого микропроцессора, что делает4 их доступными управлению и контролю: специальные средства распознавания событий, вызывающие прерывания выполнения программы (микропрограммы): модуль памяти логических последовательностей, предназначенной для логического анализа состояний шин разрабатываемой микропроцессорной системы в режиме выполнения программы в масштабе реального времени: средства связи с шиной системы проектирования; буферные и мультиплексирующие схемы.
Внутрисхемный эмулятор включается вместо создаваемого микропроцессора и выполняет в разрабатываемой системе ее функции. С точки зрения процесса отладки ПО он выполняет следующие функции: управление ходом вычислительного процесса в макетном образце микропроцессорной системы, т. е. инициализацию начального состояния управляющих и информационных регистров микропроцессора и запуск программы (микропрограммы) отлаживаемой системы по шагам или до выполнения заданного условия;
Моделирование раоты юш-памяти
Рассмотрим задачу моделирования и оценки архитектуры многомашинной ВЫЧИСЛИТеЛЬНОЙ Системы С ВЬїСОКОнаДЄЖНОЙ КОЛЬЦЕВОЙ МЭГИ-стралью и маркерным методом доступа. Система строится по принципам ГОрячегО резервирования, параЛЛЄЛЬНЬ[Х ВЫЧИСЛениЙ И ПОСЛЄДуЮЩИХ Об менов и сравнений полученных результатов. Структурная схема этой системы приведена нарис, 4.1,
В состав системы входят восемь вычислительных модулей, два модуля внешних запоминающих устройства (ВЗУ) и отказоустойчивый блок питания. Связь между модулями обеспечивается через отказоустойчивую кольцевую магистраль. Входящие в состав системы адаптеры канала связи (АКС) обеспечивают согласование модулей с системным интерфейсом, выполнение протокола интерфейса, а также изоляцию отказавших модулей по результатам контроля и самоконтроля. Все модули имеют аппаратно-программные средства контроля. Кроме того, группы модулей обеспечивают взаимный контроль друг друга,
В рассматриваемой системе возможны несколько режимов взаимодействия между процессорными модулями: - один с одним, один с несколькими. Информация между модулями передается блоками, размер коюрых ограничен (ввиду оіраниченносш буферов АКС). Если модулю необходимо передать более одного блока информации, то каждый раз для передачи блока он должен осуществлять процесс захвата магистрали.
Опишем используемый в системе маркерный метод доступа.
От одного абонента к другому передается маркер. Только тот модуль, который в настоящее время владеет маркером, может передавать сообщение в сеть. При этом невозможно пересечение передаваемых разными абонентами сообщений, т.к. в каждый момент времени будет активным только один передатчик. Этот метод имеет ряд преимуществ по сравнению с другими возможными методами доступа: невозможность пересечения передаваемых сообщений; облегчена передача циркулярных сообщений; достаточно просты реализация и описания метода.
Согласно принятой в концепции открытых систем классификации, рассматриваемый протокольный уровень является физическим уровнем локальной сети с кольцевым моноканалом. Основная сервисная функция этого уровня - это надежная передача последовательности байтов сооб щений, поступающих из одной ЭВМ (передающая машина) в одну или несколько других ЭВМ (принимающая машина).
Для передачи информации в канал интерфейсный автомат - адаптер канала связи (АКС) должен осуществлять захват канала, используя маркерный метод доступа с соответствующей системой приоритетов. После захвата канала захвативший его АКС приобретает статус ведущего и начинает передачу информации в свой выходной канал. В самом начале работы системы в одном из модулей происходит выдача сигнала УМ (установка После этого данный модуль испускает маркер М\ в канал (маркер есть однозначно интерпретируемый битовый код), маркера). После этого данный модуль испускает маркер М\ в канал (маркер есть однозначно Интерпретируемый биТОВЫЙ КОД). В Случае текущей работы СИС темы источником начального маркера М\ является текущий задатчик. только что завершивший передачу блока информации.
Каждый модуль, получив на своем входе из канала маркер М\, осуществляет проверку наличия сигнала запроса на передачу сообщения. Если такого запроса нет, то он остается в исходном состоянии и выдает Л/i па выход в канал, как бы пропуская его через себя. Если же модуль имеет запрос, то он приобретает статус "конкурента11 и выдает на выход в канал сначала маркер Мг, а затем информацию о своем приоритете Ас.
Если модуль, находящийся в исходном состоянии, J юлу часі на свой вкод маркер А/:, а затем текущий максимальный номер приоритета (N), то он в случае отсутствия запроса становится "иаблюдаїелем" и транслирует Мг и Лг со своего входа на выход в канал, в противном случае он становился "конкурентом", выдаст в канал Мі, а за і ем номер приориіеіа (iV) максимальный из двух: номер своего приоритета Ас и номер принятого из канала приоритета N.
Если модуль, находящийся в состоянии "наблюдатель" получает на вход Мг и -V, то он осгаеіся в і ом же состоянии, передавая на выход полученные Мг и N. Если же модуль, находящийся в состоянии " конкурент" получает на входе из канала маркер Мг и TV. то в случае, если его собственный приоритет /Vc не меньше принятого N. он выдает в канал маркер Л#з и открывает передачу адресов приемников в канал, становясь "задатчиком", а в противном случае транслирует в канал Mi и N.
Модуль, находящийся в статусе "наблюдатель" пропускает маркер А/з через себя и приобретает статус "приемника-паблгодатсля", открывая прием адреса из канала. Модуль, находящийся в статусе "конкурент", пропускает маркер Мл и становится "приемником—конкурентом", также открывая прием адреса из канала. Модуль, ставший "задатчиком", получив на входе их канала маркер Ms становится также "потенциальным приемником11 и открывает прием адреса из канала, т, к. "задатчик", прерывая сообщение, может адресоваться также к самому себе, например, с целями контроля. Таким образом завершается процесс захвата и начинается собственно передача сообщения.
Статус "приемника-конкурента" введен для того, чтобы отличить приемника, который сам имеет запрос на передачу сообщения, но в данный момент не может овладеть каналом из-за недостаточно высокого приоритета. Для предотвращения бесконечного ожидания из-за низкого приоритета введен механизм динамического наращивания приоритета, т.е. после завершения работы "задатчика" все модули, имеющие статус "приемник-конку рен і" повьішаюі на 1 номер своего приоритета. Таким образом, обеспечивается режим справедливого распределения ресурса моноканала между модулями.
