Лекция 14

5.3. Поток управления

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

5.3.1. Последовательный поток управления и переходы

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

Если программа содержит переходы, то счетчик команд уже не является монотонно возрастающей функцией времени. В результате последовательность выполнения команд из самой про­граммы не видна. Чем труднее увидеть последовательность выполнения, тем больше вероятность возникновения ошибок. Такое на­блюдение (Дейкстра) дало толчок революции в программировании, одним из нововведений которой было устранение оператора goto более структурирован­ными формами потока управления, например циклами while. Тем не менее такие программы компилируются в программы машинного уровня, которые могут содержать многочисленные переходы, поскольку реализация операторов if, while и других структур языков высокого уровня требует совершения переходов.

5.3.2. Подпрограммы

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

Особый интерес представляет рекурсивная подпрограмма. Это подпрограмма, которая вызывает сама себя непосредственно либо посредством цепочки других подпрограмм. С помощью рекурсивной подпрограммы легко решается, например, древняя задача о “Ханойской башне”.

5.3.3. Сопрограммы

В обычной последовательности вызовов существует различие между вызы­вающей и вызываемой процедурами. Пусть есть процедура A, кото­рая вызывает процедуру В. После полного выполнения В управление возвращается в А к точке вызова. Если процедура A вызы­вает процедуру В много раз, то процедура В каждый раз начинается с начала, а про­цедура А уже никогда больше с начала не начинается. Когда A вызывает B, она использует команду вызова процедуры (CALL), которая помещает адрес возврата в доступное место, например, в вершину стека. Затем она заносит адрес процедуры B в счетчик команд, чтобы окончательно оформить вызов. Для выхода из процедуры B используется команда (RETURN), которая выталкивает адрес возврата из стека и помещает его в счетчик команд.

---

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

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

Обычные команды (CALL и RETURN) не подходят для вызова сопрограмм. Для этого подошла бы коман­да замены вершины стека на счетчик команд. Такая команда встречается редко, и в большинстве случаев ее приходится моделировать имеющимися командами.

5.3.4. Ловушки

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

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

Ловушку можно реализовать путем регулярной проверки, выполняемой микро­программой (или аппаратным обеспечением). Если обнаружено переполнение, адрес ловушки загружается в счетчик команд. Таким образом, то, что является ловушкой на од­ном уровне, может находиться под контролем программы на более низком уровне. Проверка на уровне микропрограммы требует меньше времени, чем проверка под контролем пользовательской программы, поскольку она может выполняться одновременно с ка­ким-либо другим действием. Кроме того, такая проверка экономит память, т.к. она может присутствовать только в одном месте, например, в основном цикле микропрограммы, независимо от того, сколько арифметических команд встреча­ется в основной программе.

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

---

5.3.5. Прерывания

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

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

5.4. Архитектура Intel IA-64

В заключение этого раздела мы кратко рассмотрим новую архитектуру, разработкой которой занимается фирма Intel. Эта архитектура по прогнозам должна не только постепенно вытеснить IA-32, но и оказать влияние на разработки других фирм в компьютерной индустрии.

Это новая 64-разрядная компьютерная архитектура, которая создавалась совместно компаниями Intel и Hewlett Packard. Первый процессор этого типа имел кодовое имя Merced, впоследствии официальное – Itanium. Ожидается полный спектр соответствующих процессоров разного уровня.

Как неоднократно подчеркивалось выше, архитектура IA-32 имеет много серьезных проблем, главной предпосылкой которых является длительность периода разработок с поддержкой обратной совместимости. Огромное количество транзисторов в процессорах Pentium предназначено для преобразова­ния CISC-команд в современные RISC-команды, разрешения конфликтов, прогнозирования переходов, исправления неправильных предсказаний и решения многих других задач подобного рода, при этом остается лишь незначительное число транзисторов на долю реальной работы, нужной пользователю. Поэтому компания Intel пришла к следующему выводу: нужно выбросить IA-32 и начать все заново.

5.4.1. Явный параллелизм

Merced – это двухрежимный процессор, который может выполнять как программы IA-32, так и программы IA-64. Мы в основном будем говорить об архитектуре IA-64. Это архитектура типа загрузка/сохранение с 64-битными адресами и регистрами. В ней имеется 64 регистра общего назначе­ния, доступных для программ IA-64 (и дополнительные регистры для программ IA-32). Все отдельные команды имеют фиксированный формат: код операции, два 6-битных поля для задания входных регистров, одно 6-битное поле для указания выходно­го регистра и еще одно дополнительное 6-битное поле. Большинство команд оперируют двумя регистровыми операндами-источниками и помещают результат в третий регистр-приемник. Имеется много функциональных блоков для параллельного выполне­ния операций. Большинство RISC-процессоров имеют сходную архитектуру. В последующих версиях процессора Itanium количество регистров было увеличено до 128, соответственно изменился формат команды (7-битные поля для номеров общих регистров).

---

Новой в IA-64 является концепция пучка связанных команд. Команды посту­пают на выполнение пучками – обычно группами по три штуки. Каждый 128-битный пучок содержит три 40-битные команды фиксированного формата и 8-битный шаблон. Пучки могут быть связаны вместе (при этом ис­пользуется бит конца пучка), поэтому в одном пучке может присутствовать и более трех команд. Формат содержит информацию о том, какие команды могут выпол­няться параллельно. При такой системе и при наличии большого числа регистров компилятор может выделять блоки команд и сообщать процессору о том, какие из них можно выполнять параллельно. Таким образом, компилятор должен переупо­рядочивать команды, проверять, нет ли взаимозависимостей, проверять доступ­ность функциональных блоков и т. д. вместо аппаратного обеспечения. Идея состоит в том, что работа упорядочивания и распределения RISC-команд пере­дается от аппаратного обеспечения компилятору. Эта технология названа EPIC (Explicitly Parallel Instruction Computing – технология парал­лельной обработки команд с явным параллелизмом). Она может считаться следующей по отношению к RISC.

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

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

5.4.2. Предикация

Еще одна особенность архитектуры IA-64 - новый способ обработки условных переходов. Вообще чем таких команд меньше, тем цент­ральный процессор становится проще и работает быстрее. На пер­вый взгляд устранить условные переходы невозможно, по­скольку в программах всегда много операторов if. Однако в архитектуре IA-64 используется специальная технология, названная предикацией, которая позво­ляет существенно сократить их число.

---

В современных ЭВМ все команды являются безусловными в том смысле, что когда центральный процессор выбирает команду, он ее просто выполняет. Здесь никогда не решается вопрос “выполнять или не выполнять?”. В архитектуре с предикацией команды содержат условия, которые сообщают, в каком случае нужно выполнять команду, а в каком - нет. Замена безуслов­ных команд командами с предикацией позволяет избавиться от многих условных переходов. Вместо того чтобы выбирать ту или иную последовательность без­условных команд, все команды рассматриваются как одна последовательность команд с пре­дикацией.

Для понимания этой идеи рассмотрим пример, в котором показано условное выполнение команд. Оператор if:

if (Rl == 0) R2 = R3;

соответствующий код на ассемблере:

CMP R1, 0

BNE L1

MOV R2, R3

L1:

Использование условной команды:

CMOVZ R2, R3, R1

Условная команда CMOVZ проверяет, равен ли третий регистр (R1) нулю. Если да, то команда копирует R3 в R2. Если нет, то команда не выполняет никаких действий.

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

Оператор if:

if (Rl ==0) { R2=R3: R4=R5; }

else { R6=R7; R8=R9; }

код на ассемблере:

CMP R1, 0

BNE L1

MOV R2, R3

MOV R4, R5

BR L2

L1: MOV R6, R7

MOV R8, R9

L2:

условное выполнение:

CMOVZ R2, R3, R1

CMOVZ R4, R5, R1

CMOVN R6, R7, R1

CMOVN R8, R9, R1

Здесь показаны лишь очень простые условные команды (взятые из Pentium II), однако в архитектуре IA-64 все команды являются предикатными. Дополнительное 6-битное поле в команде, о котором сказано выше, содержит номер одного из 64-х 1-битных предикатных регистров. Таким образом, любой оператор if может быть скомпилирован в код, который устанавливает один из предикатных регистров в 1, если условие истинно, и в 0, если условие ложно. Одновременно с этим автоматически устанавливается другой предикатный регистр в обратное значение. При использовании предикации машинные команды, реализующие ветки then и else, будут помещаться в единый поток команд, часть из них - с использованием самого предиката, остальная часть - с использованием его обратного значения.

Следующий пример показывает использование предикации для устранения переходов. Команда CMPEQ сравнивает два регистра и устанавливает предикатный регистр P4 в 1, если операнды равны, и в 0, если они не равны. Кроме того, команда устанавливает парный регистр, например Р5, в обратное условие. Теперь команды частей if и then можно поместить одну за другой, причем каждая из них связывается с каким-нибудь предикатным регистром (регистр указывается в угловых скобках). Сюда можно поместить любой код, при условии что каждая команда предсказывается правильно.

---

Смотрите также файлы

• L15.doc

• L06.doc

• L05.doc

• L11.doc

• L03.doc