Увеличение производительности

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

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

Кеш-память

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

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

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

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

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

Рис. 4.25. Система с тремя уровнями кэш-памяти

Обычно все содержимое кэш-памяти первого уровня находится в кэш-памяти второго уровня, а все содержимое кэш-памяти второго уровня находится в кэш-памяти третьего уровня.

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

Во всех типах кэш-памяти используется следующая модель. Основная память разделяется на блоки фиксированного размера, которые называются строками кэш-памяти. Строка кэш-памяти состоит из нескольких последовательных байтов (обыч-но от 4 до 64). Строки нумеруются, начиная с 0, то есть если размер строки составляет 32 байта, то строка 0 — это байты с 0 по 31, строка 1 — байты с 32 по 63 и т. д. В любой момент несколько строк находится в кэш-памяти. Когда происходит обращение к памяти, контроллер кэш-памяти проверяет, есть ли нужное слово в данный момент в кэш-памяти. Если есть, то можно сэкономить время, требуемое на доступ к основной памяти. Если данного слова в кэш-памяти нет, то какая-либо строка из нее удаляется, а вместо нее помещается нужная строка из основной памяти или из кэш-памяти более низкого уровня.

Кеш-память прямого отображения

Самый простой тип кэш-памяти — это кэш-память прямого отображения. Каждый элемент (ряд) может вмещать ровно одну строку из основной памяти.

Каждый элемент кэш-памяти состоит из трех частей:

1. Бит достоверности указывает, есть ли достоверные данные в элементе или нет. Когда система загружается, все элементы маркируются как недостоверные.

2. Поле «Тег» состоит из уникального 16-битного значения, указывающего соответствующую строку памяти, из которой поступили данные.

3. Поле «Данные» содержит копию данных памяти. Это поле вмещает одну строку кэш-памяти в 32 байта.

Рис. 4.26. (а) Кэш-память прямого оттображения; (б) 32-битный виртуальный адрес

В кэш-памяти прямого отображения данное слово может храниться только в одном месте. Если дан адрес слова, то в кэш-памяти его можно искать только в одном месте. Если его нет на этом определенном месте, значит, его вообще нет в кэш-памяти. Для хранения и удаления данных из кэш-памяти адрес разбивается на 4 компонента, как показано на рис. 4.26, б:

1. Поле «ТЕГ» соответствует битам, сохраненным в поле «Тег» элемента кэш-памяти.

2. Поле «СТРОКА» указывает, какой элемент кэш-памяти содержит соответствующие данные, если они есть в кэш-памяти.

3. Поле «СЛОВО» указывает, на какое слово в строке производится ссылка.

4. Поле «БАЙТ» обычно не используется, но если требуется только один байт, поле сообщает, какой именно байт в слове нужен. Для кэш-памяти, поддерживающей только 32-битные слова, это поле всегда будет содержать 0.

Когда центральный процессор выдает адрес памяти, аппаратное обеспечение выделяет из этого адреса 11 битов поля «СТРОКА» и использует их для поиска в кэш-памяти одного из 2048 элементов. Если этот элемент действителен, то производится сравнение поля «Тег» основной памяти и поля «Тег» кэш-памяти. Если поля равны, это значит, что в кэш-памяти есть слово, которое запрашивается. Такая ситуация называется удачным обращением в кэш-память. Вслучае удачного обращения слово берется прямо из кэш-памяти, и тогда не нужно обращаться к основной памяти. Из элемента кэш-памяти берется только нужное слово. Остальная часть элемента не используется. Если элемент кэш-памяти недействителен (недостоверен) или поля «Тег» не совпадают, то нужного слова нет в памяти. Такая ситуация называется промахом кэш-памяти. В этом случае 32-байтная строка вызывается из основной памяти и сохраняется в кэш-памяти, заменяя тот элемент, который там был. Однако если существующий элемент кэш-памяти изменяется, его нужно отписать обратно в основную память до того, как он будет отброшен.

Ассоциативная кеш память с множественным доступом

Различные строки основной памяти конкурируют за право занять одну и ту же область в кэш-памяти. Если программе, которая применяет кэш-память, изображенную на рис. 4.26, а, часто требуются слова с адресами 0 и 65 536, то будут иметь место постоянные конфликты и каждое обращение потенциально повлечет за собой вытеснение какой-то определенной строки кэш-памяти. Чтобы разрешить эту проблему, нужно сделать так, чтобы в каждом элементе кэш-памяти помещалось по две и более строк. Кэш-память с n возможными элементами для каждого адреса называется n-входовой ассоциативной кэш-памятью. Четырех-входовая ассоциативная кэш-память изображена на рис. 4.27.

Рис. 4.27.Четырехвходовая ассоциативная кеш память

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

Использование ассоциативной кэш-памяти с множественным доступом ставит разработчика перед выбором. Если нужно поместить новый элемент в кэш-память, какой именно из старых элементов нужно убрать? Для многих целей хорошо подходит алгоритм LRU (Least Recenly Used — алгоритм удаления наиболее давно использовавшихся элементов). Имеется определенный порядок каждого набора ячеек, которые могут быть доступны из данной ячейки памяти. Всякий раз, когда осуществляется доступ к любой строке, в соответствии с алгоритмом список обновляется и маркируется элемент, к которому произведено последнее обращение. Когда требуется заменить какой-нибудь элемент, убирается тот, который находится в конце списка, то есть тот, который использовался давно по сравнению со всеми другими.

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

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

Прогнозирование ветвления

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

i f (1=0)

к=1;

else

к=2;

Листинг 4.4 Фрагмент программы

СМР 1, 0 сравнение 1 с 0

BNE Else переход к Else, если они не равны

Then MV k,1 присваивание значения 1 переменной к

BR Next безусловный переход к Next

Else MV k,2 присваивание значения 2 переменной к

Next

Листинг 4.5. Перевод фрагмента программы на язык ассемблер

Видно, что две из пяти команд являются переходами. Более того, одна из них, BNE, — это условный переход (переход, который осуществляется тогда и только тогда, когда выполняется определенное условие, в данном случае это равенство двух операндов предыдущей команды СМР). Самый длинный линейный код состоит здесь из двух команд. Вследствие этого вызывать команды с высокой скоростью для передачи в конвейер очень трудно. На первый взгляд может показаться, что безусловные переходы, например команда BR Next в листинге 4.5, не влекут за собой никаких проблем. Вообще говоря, в данном случае нет никакой двусмысленности в том, куда дальше идти.

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

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

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

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

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

Динамическое прогнозирование ветвления

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

Статическое прогнозирование ветвления

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

Можно пойти другим путем и призвать на помощь компилятор. Когда компилятор получает такое выражение, как:

for (1=0 1 < 1000000, 1++) { }

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

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

Исполнение с изменением последовательности и подмена регистров

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

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

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

Чтобы определить, можно ли запускать эту команду, применяются следующие правила:

1. Если какой-нибудь операнд записывается, запускать команду нельзя (RAW-взаимозависимость).

2. Если считывается регистр результатов, запускать команду нельзя (WAR-взаимозависимость).

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

Уже рассматривались RAW-взаимозависимости, имеющие место, когда команде в качестве источника нужно использовать результат предыдущей команды, которая еще не завершилась. Два других типа взаимозависимостей менее серьезные. По существу, они связаны с конфликтами ресурсов. В WAR-взаимозависимости (Write After Read — запись после чтения) одна команда пытается перезаписать регистр, который предыдущая команда еще не закончила считывать. WAW-взаимозависимость (Write After Write — запись после записи) сходна с WAR-взаимозависимостыо. Этого можно избежать, если вторая команда будет помещать результат где-либо в другом месте еще (возможно, временно). Если ни одна из трех упомянутых ситуаций не возникает и нужный функциональный блок доступен, то команду можно выпустить.

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

Рассмотрим альтернативный подход: исполнение с изменением последовательности. В такой разработке выполнение команд может начинаться в произвольном порядке и завершаться также в произвольном порядке. Вводится новый метод для решения этой проблемы: подмена

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

Спекулятивное выполнение

Компьютерные программы можно разбить на базовые элементы, каждый из которых представляет собой линейную последовательность команд с точкой входа в начале и точкой выхода в конце. Базовый элемент не содержит никаких управляющих структур (например, условных операторов i f или операторов цикла whi I e), поэтому при трансляции на машинный язык нет никаких ветвлений. Базовые элементы связываются операторами управления.

Программа в такой форме может быть представлена в виде ориентированного графа, как показано на рис. 4.30.

Рис. 4.30. Граф базового элемента для фрагмента программы (слева)

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

Дата добавления: 2014-01-20