Питерсон Дж. - Теория сетей Петри и моделирование систем - 1984, страница 10

Устройство управления ЭВМ организует одновремепиоефуикцпоиированне нескольких независимых блоков. В качестве примера рассмотрим следующтю последовательность инструкций для вычислительной системы СВС 6600: 1. Умножить Х1 иа Х1, результат поместить в ХО. 2. Умножить ХЗ иа Х1, результат поместить в ХЗ.

Сеги ггеггггг для лоделираеаяия 3. Слонщть Х2 с Х4, результат помеспггь в Х4. 4. Сложить ХО с ХЗ, результат поместить в ХЗ. 5. Разделить ХО на Х4, результат поместить в Х6. Для выполнения инструкций устройство управления выдаеч первую инструкцию в блок умножения.

Поскольку существуют два блока умножения, можно выдать также вторую инструкцию. При этом обоим блокам досчуппо содержггчое Х1. Инструкция 3 может быть выдана блоку сложения. Теперь, для того, чтобы выдать инструкцию 4, мы должны ждать, пока инструкции 1, 2 и 3 ие будут завершены, так как инструкция 4 использует блок сложения (занятый выполнением инструкции 3), ХО (вычисляемый инструкцией 1) и ХЗ (вычисляемый инструкцией 2). Инструкция 5 должна ждать выполнения инструкции ! (вычисление ХО) и инструкции 3 (вычисление Х4). Организация параллелизма этого типа (выполнение нескольких инструкций программы одновременно) должна быть такой, чтобы результат выполнения программы с использованием параллелизма и без него был бы одинаков.

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

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

Каждому функциональному блоку и каждому репгстру поставим в соответствие позицию: если блок или регпсчр свободен — в позицию будет помещена фишка, если нет — фишки в позиции не будет. Кратныс идентичные функциональные блоки показываются соответствующим числом фишек в позициях. На рис. 3.20 изображена часть сети Петри, которая может быть использована для моделирования выполнения инструкции, использующей блок и и регнст- Глава 3 /атадиаста деиадиройатг следами/аю ниструииию //игтируища испол/гает Блан и сйойодеи Регистр й сйайадеи Регистр/' сйайадеи Региетр /г сйойодеи йотает юрами Рнс.

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

Таким образом, максимальный параллелизм в этой схеме может быть не получен [1631. Однако существуют другие схемы, с помощью которых это достигается. Такие более сложные схемы также моделируются (более сложными) сетями Петри. Зги сети могут быть очень велики. СГ1С 6600, например, имеет 24 различных регистра и 64 различных инструкции.

Если для каждой инструкции и тройки регистров требуется позиция, соответствуннцая условию «блок и оперирует регистрами г, / и /зе, то необходимо более полумиллиона позиций и переходов. Главная трудность заключается в представлении того факта, что содержимое внутренних регистров может определять, какие регистры и блоки будут использоваться (индексирование). (Однако никакая программа не использует все возможные комбинации регистров и блоков. Зто позволило (274) промоделировать вычислительную систему СОС 6600 с помощью сетей Петри. Эта модель сети Петри была затем использована для оптимальной генерации кода компилятором с Фортрана, что мы увидим в равд. З.б.) Сети Петри дяя моделирования шие возможности для практического применения.

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

ЗА.1. Блок-схемы Вырожденным случаем параллельной системы обработки является система с одним процессом. Сначала рассмотрим, как сетью Петри может быть представлен отдельный процесс, а затем путем комбинации сетей Петри, представлякицих несколько процессов, получим систему параллельных процессов. Отдельный процесс описывается программой. Эта программа может быть написана на многих языках, но для удобства примем общецелевой язык, такой, кзк Алгол, Фортран, Р?Л, Кобол, Паскаль, Бэйсик или даже язык ассемблера. Программа представляет два различных аспекта процесса: вычисление и управление.

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

Поэтому оиа игнорирует все возможные специфические детали. Если бы моделировались все детали, тогда модель была бы дубликатом моделируемой системы, а не абстракцией. Стандартный способ представления структуры управления программ — это блок-схемы. Блок-схема представляет поток управления в программе. Например, программа на рис. 3.21 представляется блок-схемой на рис. 3.22. Заметим, что блок-схема на рис. 3.22 не указывает конкретные вычисления, которые надо произвести, а только определяет структуру программы. Такая блок-схема является абстрактной. Рис.

3.23 показывает, как можно проинтерпретировать блок-схему (рис. 3.22) программы, представленной на рис. 3.21. Каждая последовательная программа может быть представлена в виде блок-схемы. Тащем образом, показывая, как Бе~и 1при2( у,); 1прп2( У2)' У3 .=1; ийсу1>о гЬ Ьсдтп (ГогЫ ( у~) гйел Ьех(л УЗ Уз У2 У~ .= У1 етгл; У2 У2 У2 У~ =У~ — 2; елгг; Оцгрнг ( Уз)' есЫ; Рис. 3.2П Простая программа.

Зта программа предсгавлеиа блок-схемой иа рис. 3.22 п сетью Петри иа рис. 3.25. блок-схема может быть представлена сетью Петри, мы дадим представление сетью Петри программы. Оказывается блок-схема во многом подобна сети Петри: блоксхема представима в виде узлов двух типов (прннятия решения, показанные ромбами, и вычисления, показанные прямоугольниками) и дуг между ними.

Удобный способ выполнения блок-схемы — введение фишки, которая представляет текущую инструкцию. По мере выполнения инструкций фишка передвигается по блок-схеме. Из сходства между графическими представлениями программы и сети Петри может показаться, что для получения зквнвалентной сети Петри можно заменить узлы блок-схемы на позиции, а дуги — ва переходы. Такой подход использовался для превращения конечного автомата в сеть Петри (равд. 3.3.1). Однако заметим, что в сети Петри действия моделируются переходамн, тогда как в блок-схеме действия моделируются узлами.

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