Алгоритм Томасуло - Tomasulo algorithm

Алгоритм Томасуло это компьютерная архитектура аппаратное обеспечение алгоритм для динамического планирования инструкций, что позволяет внеочередное исполнение и позволяет более эффективно использовать несколько исполнительных модулей. Он был разработан Роберт Томасуло в IBM в 1967 году и впервые был реализован в IBM System / 360 Модель 91 С блок с плавающей запятой.

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

Роберт Томасуло получил Премия Эккерта – Мочли в 1997 г. за работу над алгоритмом.^[1]

Концепции реализации

Модуль с плавающей запятой Томасуло

Ниже приведены концепции, необходимые для реализации алгоритма Томасуло:

Общая шина данных

Общая шина данных (CDB) соединяет станции резервирования напрямую с функциональными блоками. По словам Томасуло, он «сохраняет приоритет, поощряя параллелизм».^[2]^:33 Это имеет два важных эффекта:

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

Порядок инструкций

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

Регистрация переименования

Алгоритм Томасуло использует зарегистрировать переименование правильно выполнять внеочередное исполнение. Все регистры станций общего назначения и резервирования содержат либо реальное значение, либо значение-заполнитель. Если реальное значение недоступно для целевого регистра на этапе выдачи, изначально используется значение-заполнитель. Значение-заполнитель - это тег, указывающий, какая станция резервирования выдаст реальное значение. Когда модуль закончит и передаст результат в CDB, заполнитель будет заменен реальным значением.

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

Исключения

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

Программы, которые испытывают «точные» исключения, когда может быть определена конкретная инструкция, вызвавшая исключение, могут перезапускаться или повторно выполняться в точке исключения. Однако те, которые испытывают «неточные» исключения, обычно не могут перезапустить или повторно выполнить, так как система не может определить конкретную инструкцию, которая приняла исключение.

Жизненный цикл инструкции

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

Зарегистрировать легенду

Op - представляет операцию, выполняемую над операндами
Qj, Qk - станция резервирования, которая создаст соответствующий исходный операнд (0 означает, что значение находится в Vj, Vk)
Vj, Vk - значение исходных операндов
A - используется для хранения информации об адресе памяти для загрузки или сохранения
Занят - 1, если занят, 0, если не занят
Qi - (Только регистровый блок) станция резервирования, результат которой должен быть сохранен в этом регистре (если пусто или 0, никакие значения не предназначены для этого регистра)

Этап 1: выпуск

На этапе выдачи инструкции выдаются для выполнения, если все операнды и станции резервирования готовы, или же они остановлены. На этом этапе регистры переименовываются, что устраняет опасности WAR и WAW.

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

Псевдокод^[3]^:180
Состояние инструкции	Подожди до	Действия или бухгалтерия
Проблема	Станция р пустой	если (RegisterStat[RS].Ци¦0) { RS[р].Qj ← RegisterStat[RS].Ци}еще { RS[р].Vj ← Regs[RS]; RS[р].Qj ← 0;}если (RegisterStat[rt].Ци¦0) { RS[р].Qk ← RegisterStat[rt].Ци;}еще { RS[р].ВКонтакте ← Regs[rt]; RS[р].Qk ← 0;}RS[р].Занятый ← да;RegisterStat[rd].Q ← р;
Загрузить или сохранить	Буфер р пустой	если (RegisterStat[RS].Ци¦0) { RS[р].Qj ← RegisterStat[RS].Ци;}еще { RS[р].Vj ← Regs[RS]; RS[р].Qj ← 0;}RS[р].А ← имм;RS[р].Занятый ← да;
Только загрузка		RegisterStat[rt].Ци ← р;
Только магазин		если (RegisterStat[rt].Ци¦0) { RS[р].Qk ← RegisterStat[rt].Ци;}еще { RS[р].ВКонтакте ← Regs[rt]; RS[р].Qk ← 0};

Пример алгоритма Томасуло^[4]

Этап 2: выполнить

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

Если один или несколько операндов еще недоступны, то: дождитесь, пока операнд станет доступным в CDB.
Когда все операнды доступны, тогда: если инструкция является загрузкой или сохранением
- Вычислить эффективный адрес, когда доступен базовый регистр, и поместить его в буфер загрузки / сохранения
  - Если инструкция является загрузкой, то: выполнить, как только станет доступен блок памяти
  - В противном случае, если инструкция является хранилищем, тогда: дождитесь сохранения значения, прежде чем отправлять его в блок памяти
В противном случае инструкция является арифметико-логическое устройство (ALU) затем: выполнить инструкцию в соответствующем функциональном блоке

Псевдокод^[3] ^:180
Состояние инструкции	Подожди до	Действия или бухгалтерия
Операция FP	(RS [r] .Qj = 0) и (RS [r] .Qk = 0)	Результат вычисления: операнды находятся в Vj и Vk
Шаг загрузки / сохранения 1	`RS [r] .Qj = 0` & r - руководитель очереди загрузки-хранилища	RS [r] .A ← RS [r] .Vj + RS [r] .A;
Шаг нагрузки 2	Шаг загрузки 1 завершен	Читать из `Mem [RS [r] .A]`

Этап 3: записываем результат

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

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

Псевдокод^[3] ^:180

Состояние инструкции

Подожди до

Действия или бухгалтерия

Работа или загрузка FP

Выполнение завершено в р & CDB доступны

	∀Икс(если (RegisterStat[Икс].Ци = р) {		regs[Икс] ← результат;		RegisterStat[Икс].Ци = 0	});	∀Икс(если (RS[Икс].Qj = р) {		RS[Икс].Vj ← результат;		RS[Икс].Qj ← 0; 	});	∀Икс(если (RS[Икс].Qk = р) {		RS[Икс].ВКонтакте ← результат;		RS[Икс].Qk ← 0;	});	RS[р].Занятый ← нет;

Магазин

Выполнение завершено в r & RS [r] .Qk = 0

	Mem[RS[р].А] ← RS[р].ВКонтакте;	RS[р].Занятый ← нет;

Улучшения алгоритма

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

Станции резервирования берут на себя ответственность за ожидание операндов при наличии зависимостей данных и других несогласованностей, таких как различное время доступа к хранилищу и скорости каналов, тем самым освобождая функциональные блоки. Это улучшение позволяет избежать длительных задержек с плавающей запятой и обращений к памяти. В частности, алгоритм более устойчив к промахам кеша. Кроме того, программисты освобождаются от реализации оптимизированного кода. Это результат совместной работы общей шины данных и станции резервирования для сохранения зависимостей, а также поощрения параллелизма.^[2]^:33

За счет отслеживания операндов для инструкций на станциях резервирования и переименования регистров аппаратно алгоритм минимизирует чтение после записи (RAW) и исключает запись после записи (WAW) и Запись после чтения (ВОЙНА) компьютерная архитектура опасности. Это улучшает производительность за счет сокращения потерь времени, которые в противном случае потребовались бы для стойл.^[2]^:33

Не менее важным улучшением алгоритма является то, что его конструкция не ограничивается конкретной структурой конвейера. Это улучшение позволяет более широко применять алгоритм обработчиками с множеством проблем. Кроме того, алгоритм легко расширяется, чтобы включить спекуляцию ветвлением.^[3] ^:182

Приложения и наследие

Алгоритм Томасуло вне IBM не использовался в течение нескольких лет после его реализации в архитектуре System / 360 Model 91. Тем не менее, в 1990-е годы его использование значительно увеличилось по трем причинам:

Когда кеширование стало обычным явлением, способность алгоритма Томасуло поддерживать параллелизм во время непредсказуемого времени загрузки, вызванного промахами в кэше, стала ценной для процессоров.
Динамическое планирование и предположения о ветвлении, что алгоритм позволяет, повысили производительность, поскольку процессоры выдают все больше и больше инструкций.
Распространение массового программного обеспечения означало, что программисты не захотели компилировать для конкретной конвейерной структуры. Алгоритм может работать с любой конвейерной архитектурой, поэтому программное обеспечение требует незначительных модификаций для конкретной архитектуры.^[3] ^:183

Многие современные процессоры реализуют схемы динамического планирования, которые являются производными от оригинального алгоритма Томасуло, включая популярные Intel x86-64 чипсы.^[5]^{[неудачная проверка ]}^[6]

Смотрите также

дальнейшее чтение

Савард, Джон Дж. Г. (2018) [2014]. «Конвейерное исполнение и исполнение вне очереди». квадиблок. В архиве из оригинала 2018-07-03. Получено 2018-07-16.

внешняя ссылка

[1] «Роберт Томасуло - лауреат премии». ACM Awards. ACM. Получено 8 декабря 2014.

[tomasulo-2] а ^б ^c Томасуло, Роберт Марко (Январь 1967 г.). «Эффективный алгоритм для использования нескольких арифметических единиц». Журнал исследований и разработок IBM. IBM. 11 (1): 25–33. Дои:10.1147 / ряд.111.0025. ISSN 0018-8646.

[hennessy-3] а ^б ^c ^d ^е Хеннесси, Джон Л .; Паттерсон, Дэвид А. (2012). Компьютерная архитектура: количественный подход. Уолтем, Массачусетс: Эльзевир. ISBN 978-0123838728.

[4] "CSE P548 - Томасуло" (PDF). Washington.edu. Вашингтонский университет. 2006 г.. Получено 8 декабря 2014.

[intel-5] Руководство разработчика программного обеспечения для архитектур Intel 64 и IA-32 (Отчет). Intel. Сентябрь 2014 г.. Получено 8 декабря 2014.

[adusan-6] Йога, Адарш. «Различия между алгоритмом Томасуло и динамическим планированием в микроархитектуре Intel Core». Выпивка. Получено 4 апреля 2016.

[1]

[2]

[3]

[4]

[5]

[6]