УПРАВЛЕНИЕ ПОСЛЕДОВАТЕЛЬНОСТЬЮ КОМАНД

6.1 Ключевые (основные) вопросы (моменты)

— управление вычислительным процессом;

— управление последовательностью команд;

6.2 Текст лекции

6.2.1 Управление вычислительным процессом

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

1) команда выполняется, после того как выполнена предшествующая ей команда последовательности (используется принудительный или естественный способ перехода к следующему оператору);

2) команда выполняется, когда становятся доступными ее операнды (механизм управления данными);

3) команда выполняется, когда другим командам требуется результат ее выполнения (механизм управления по запросу)

6.2.2 Управление последовательностью команд

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

В таких машинах вычисления выполняются на основе принципа Джона фон Неймана (John von Neumann), который требует, чтобы в процессоре было устройство управления, содержащее счетчик команд, чтобы команды (указанные счетчиком) последовательно считывались и декодировались по заранее заданному в виде программы алгоритму, вычисления выполнялись в операционном устройстве и данные последовательно перезаписывались в запоминающее устройство с линейной одномерной структурой. Подобная модель вычислений была впервые использована в Германии Конрадом Цузе (Konrad Zuse), создавшим в 1941 году первый в мире полностью функциональный, программно-управляемый компьютер Z-3.

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

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

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

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

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

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

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

Пусть для информационного графа изображенного на рис.5.1 задана программа, представляющая следующую последовательность команд:

Op1(D₁,D₂,R₁);

Op2(D₃,D₄,R₂);

Op3(D₅,R₃);

Op4(R₁,R₂,R₄);

Op5(R₂,R₃,R₅);

Op6(R₄,R₃,R₆).

При технической реализации каждая из этих команд может иметь собственную длину, которая зависит от разрядности поля кода операции, количества адресов в команде, количества разрядов, отводимых для записи каждого адреса, и разрядности поля, определяющего способ адресации. Минимальная разрядность поля кода операции равна ]log₂Op[, где Op – общее число выполняемых операций. Разрядности адресной части и поля способа адресации определяются аналогично и зависят, соответственно, от числа ячеек памяти или регистров общего назначения, которые необходимо адресовать, и количества способов адресации.

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

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

соncurrent (Op1(D₁,D₂,R₁),Op2(D₃,D₄,R₂),Op3(D₅,R₃));

соncurrent (Op4(R₁,R₂,R₄),Op5(R₂,R₃,R₅));

Op6(R₄,R₃,R₆).

В данном случае явно указывается, какие части последовательно выполняемой программы должны выполняться параллельно. При этом предполагается, что аппаратные средства вычислительной системы поддерживают выполнение соncurrent (параллельных) инструкций, то есть функционально совместимые операции, представленные на информационном графе, совместимы на структурном уровне. На идее параллельного выполнения нескольких простых команд фиксированного формата, объединенных в одну сверхдлинную команду, базируется архитектура VLIW (Very Long Instruction Word) – с командным словом очень большой длины, а также подобной ей архитектура EPIC (Explicitly Parallel Instruction Computing) – вычислений с явным параллелизмом команд.

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

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

7 Лекция №6

Дата добавления: 2014-11-24; просмотров: 477; Нарушение авторских прав

Мы поможем в написании ваших работ!