3.3. Аппаратное обеспечение ЭВМ

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

3.3.1. Конечные автоматы

На низком уровне вычислительные системы могут быть описаны автоматами. Автомат — это пятерка где

конечное множество состояний

конечный входной алфавит;

конечный выходной алфавит;

функция следующего состояния, отображающая текущее состояние и текущий вход в следующее состояние;

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

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

Входной алфавит определяет входы автомата из внешнего мира, а выходной алфавит — выходы автомата во внешний мир.

В качестве примера рассмотрим автомат, изображенный на рис. 3.9. Этот автомат преобразует двоичное число, представленное последовательностью бит, начиная с младшего, в дополнение до двух. В данном случае входной и выходной алфавит состоит из трех символов: Автомат начинает работать в состоянии Символ сброса означает конец (или начало) числа и возвращает автомат в исходное состояние. Выход автомата для символа сброса является просто его повторением.

Рис. 3.9. Граф переходов для конечного автомата, вычисляющего дополнение до двух двоичного числа.

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

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

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

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

Рис. 3.11. Общий подход к моделированию связи между сетью Петри и внешним миром.

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

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

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

Рис. 3.12. Альтернативный подход представления связи между сетью Петри и внешним миром, где вместо позиций используются переходы.

Рис. 3.13. Сеть Петри, эквивалентная автомату на рис. 3.9.

Для конечного автомата мы определили сеть Петри таким образом:

Эта сеть Петри является моделью конечного автомата.

На рис. 3.13 изображена сеть Петри, соответствующая автомату с рис. 3.9. На рис. 3.14 — сеть Петри, соответствующая автомату с рис. 3.10.

При сравнении сетей Петри на рис. 3.13, 3.14 с эквивалентными автоматами на рис. 3.9, 3.10 возникают некоторые вопросы. Прежде всего: почему модель сети Петри предпочтительнее описания конечным автоматом? Описание автоматом более понятно, чем описание сетью Петри, в которой 6 переходов, 24 дуги и 7 или 8 позиций. Это верно. Однако мы показали, что сети Петри могут представлять любую систему, представимую автоматом, и это свидетельствует о больших возможностях сетей Петри.

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

Рис. 3.14. Сеть Петри, эквивалентная автомату на рис. 3.10.

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

Рис. 3.15. Составной автомат, представляющий последовательную композицию автоматов, изображенных на рис. 3.9, 3.10.

четность. Такая композиция является автоматом с составными состояниями, компоненты которых — это состояния, обоих подавтоматов. В сетях Петри такая композиция есть просто совмещение выходных позиций первой сети с входными позициями второй. На рис. 3.15 показана композиция автоматов, а на рис. 3.16 — составная сеть Петри.

Другое преимущество представления сети Петри связано с иными формами композиции. Например, параллельная композиция позволяет компонентам композиции автоматов работать одновременно. В этом случае вновь получаем автомат с составными состояниями, в то время как для сети Петри — это просто дублирование фишек во входах, соответствующих входным символам, и использование их во всех компонентах сети Петри. Наконец, на выходе мы просто выбираем соответствующие позиции выхода. Например, если мы хотим соединить параллельно две сети Петри (рис. 3.13 и 3.14), то в результате получим сеть Петри, подобную изображенной на рис. 3.17, которая вычисляет дополнение числа до двух и его четность. Если на входе появляется символ сброса, то выходом является четность.

Упражнения

(см. скан)

3.3.2. ЭВМ с конвейерной обработкой

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

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

(кликните для просмотра скана)

(кликните для просмотра скана)

В качестве примера рассмотрим сложение двух чисел с плавающей точкой. Основные шаги этой операции предполагают:

1. Выделить экспоненты обоих чисел.

2. Сравнить экспоненты и изменить, если необходимо, должным образом порядок большей и меньшей экспонент.

3. Сдвинуть точку в числе с меньшей экспонентой для их уравнения.

4. Сложить дроби.

5. Нормализовать результат.

6. Проверить экспоненту на переполнение и сформировать экспоненту и дробь результата.

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

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

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

• входной регистр заполнен;

• входной регистр пуст;

• выходной регистр заполнен;

• выходной регистр пуст;

• блок занят;

• блок свободен;

• пересылка осуществлена.

На рис. 3.18 и 3.19 показано, как можно промоделировать асинхронный конвейер такого типа. На рис. 3.18 приведена блок-схема конвейера, моделируемого сетью Петри на рис. 3.19.

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

Рис. 3.18. Блок-схема устройства управления асинхронной ЭВМ с конвейерной обработкой.

Рис. 3.19. Модель сети Петри устройства управления асинхронной ЭВМ с конвейерной обработкой.

3.3.3. Кратные функциональные блоки

Конвейерная структура управления, рассмотренная в предыдущем разделе, — это один из подходов к построению очень больших быстродействующих вычислительных систем. Другой подход, использованный, например, в CDC 6600 [291] и IBM 360 [10], использует кратные функциональные блоки. В CDC 6600 имеется 10 функциональных блоков: блок ветвления (для условных переходов); булев блок (для булевых операций); блок сдвига; блок сложения с плавающей точкой; блок сложения с фиксированной точкой; 2 блока умножения; блок деления и 2 блока приращения (для индексирования). Кроме того, имеется несколько регистров, для хранения входных и выходных значений функциональных блоков. Устройство управления ЭВМ организует одновременное функционирование нескольких независимых блоков.

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

1. Умножить XI на XI, результат поместить в

2. Умножить на XI, результат поместить в

3. Сложить результат поместить в

4. Сложить результат поместить в

5. Разделить на результат поместить в

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

1) и (вычисляемый инструкцией 2). Инструкция 5 должна ждать выполнения инструкции 1 (вычисление и инструкции 3 (вычисление

Организация параллелизма этого типа (выполнение нескольких инструкций программы одновременно) должна быть такой, чтобы результат выполнения программы с использованием параллелизма и без него был бы одинаков. Некоторые инструкции в программе требуют результата предыдущей инструкции до выполнения последующей. Система, которая организует параллелизм в последовательной программе таким способом для получения правильных результатов, обладает свойством детерминированности. Условия поддержания детерминированности были рассмотрены Бернстайном [28]. Вот они: для двух операций таких, что а предшествует на линейном участке программы, может начать выполняться прежде, чем выполнена а, тогда и только тогда, когда входные .данные не требуют результата а и результаты не изменят ни входных данных, ни результатов а.

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

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

Рис. 3.20. Часть сети Петри, моделирующая устройство управления для ЭВМ с кратными регистрами и кратными функциональными блоками.

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

Схема, описанная выше, представляет собой очень простой способ введения параллелизма и не рассматривает, например, тот факт, что кратные функциональные блоки могут использовать одновременно одинаковые входные регистры. Таким образом, максимальный параллелизм в этой схеме может быть не получен [153]. Однако существуют другие схемы, с помощью которых это достигается. Такие более сложные схемы также моделируются (более сложными) сетями Петри. Эти сети могут быть очень велики. например, имеет 24 различных регистра и 64 различных инструкции. Если для каждой инструкции и тройки регистров требуется позиция, соответствующая условию «блок и оперирует регистрами , то необходимо более полумиллиона позиций и переходов. Главная трудность заключается в представлении того факта, что содержимое внутренних регистров может определять, какие регистры и блоки будут и с пол оваться (индексирование).

(Однако никакая программа не использует все возможные комбинации регистров и блоков. Это позволило [274] промоделировать вычислительную систему CDC 6600 с помощью сетей Петри. Эта модель сети Петри была затем использована для оптимальной генерации кода компилятором с Фортрана, что мы увидим в разд. 3.5.)