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

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

На протяжении ряда лет было предпринято много попыток увеличения производительности вычислительных систем путём параллельного выполнения нескольких функций. Примером такого подхода к построению высокопроизводительной ЭВМ является использование конвейерной обработки. Этот метод обработки подобен функционированию сборочного конвейера и особенно удобен для работы с векторами и массивами. Конвейер состоит из набора операций, которые могут выполняться одновременно. Когда операция k завершается, она передаёт свой результат операции (k + 1) и ожидает от операции (k — 1) нового задания. Если каждая операция занимает t единиц времени и всего существует n операций, то завершение обработки одного операнда потребует nt единиц времени. Однако, если на конвейерную обработку продолжают поступать новые операнды, результаты могут выдаваться со скоростью один каждые t единиц времени.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

· блок занят;

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

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

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

Рис. 6.2.

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

Рис. 6.3.

Для введения параллелизма предлагается операциях parbegin и parend (рис.6.4). Структура управления была предложена Дейкстрой и имеет вид parbegin S₁; S₂;...; S_n parend, где S_i – предложение. Смысл структуры parbegin/parend заключается в параллельном выполнении каждого из предложений S₁, S₂,..., S_n.

Рис. 6.4.

Лекция 7

Задача о взаимном исключении

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

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

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

3. Первый процесс вычисляет новое значение х' = f(x);

4. Второй процесс вычисляет новое значение х" = g(x);

5. Первый процесс записывает х' в разделяемый объект;

6. Второй процесс записывает х" в разделяемый объект, уничтожая значение х'.

Результат вычисления первого процесса потерян, так как теперь значением разделяемого объекта является g(x), в то время как им должно быть либо g(f (х)), либо f(g(x)). (Представьте себе, что g(x) – «снять со счета х тысяч долл.», f(x) – «поместить на счёт х тысяч долл.», а процессы 1 и 2 – банковские операции).

Для предотвращения проблем такого рода необходимо обеспечить механизм взаимного исключения. Взаимное исключение – это метод создания таких программ, что одновременно не более чем один процесс имеет доступ к разделяемому объекту данных. Участок кода, в котором осуществляется доступ к разделяемому объекту и который требует защиты от вмешательства других процессов, называется критической секцией. Идея состоит в том, что когда процесс готов выполнить свою критическую секцию, он сначала ждёт, пока другой процесс не выполнит свою собственную критическую секцию. Затем он «блокирует» доступ к критической секции, не давая возможности никакому другому процессу войти в свою критическую секцию. Он входит в критическую секцию, выполняет её и, выйдя из неё, освобождает её для доступа со стороны других процессов.

Рис.7.1. Взаимное исключение

Эта задача может быть решена сетью Петри, как показано на рис. 7.1. Позиция m представляет собой разрешение для входа в критическую секцию. Для того чтобы какой-либо процесс вошёл в критическую секцию, он должен иметь фишку в p₁ или в p₂ соответственно, свидетельствующую о желании попасть в критическую секцию, а также должна существовать фишка в m, дающая разрешение на вход. Если оба процесса пытаются войти в критическую секцию одновременно, то переходы t₁ и t₂ вступят в конфликт, и только один из них сможет запуститься. Запуск t₁ запретит переход t₂, вынуждая процесс 2 ждать, пока первый процесс выйдет из своей критической секции и возвратит фишку обратно в позицию m.

Задача о производителе/потребителе

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

Рис. 7.2. Задача о производителе/потребителе

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

Рис. 7.3.

В другом варианте задачи о производителе/потребителе используется буфер ограниченного размера. При такой постановке задачи буфер между производителем и потребителем ограничен, т.е. имеет только n ячеек для элементов данных. Следовательно, производитель не может постоянно работать с той скоростью, которая ему нужна, а вынужден ждать, если потребитель работает медленно и буфер заполнен. На рис. 7.4 показано решение этой проблемы. Ограниченному буферу сопоставляются две позиции: B представляет количество элементов данных, которые произведены, но ещё не использованы (число заполненных ячеек). B' – количество пустых ячеек в буфере. Первоначально B' имеет n фишек, а B фишек не имеет. Если буфер заполнен, то B' фишек не имеет, а B имеет n фишек. Если теперь производитель попытается поместить ещё один элемент данных в буфер, то. он будет остановлен, так как в В' нет фишки, делающей этот переход разрешённым.

Рис. 7.4.

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

Рис.7.5

Дата добавления: 2014-12-16