Tomasulo's algorithm

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

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

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

Концепции реализации [ править ]

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

Общая шина данных [ править ]

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

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

Порядок инструкций [ править ]

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

Переименование регистрации [ править ]

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

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

Исключения [ править ]

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

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

Жизненный цикл инструкции [ править ]

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

Легенда [ править ]

RS — Статус резервирования
RegisterStat — Статус регистра; содержит информацию о регистрах.
regs[x] - Значение регистра x
Mem[A] - Значение памяти по адресу A

rd - номер регистра назначения
rs, rt — регистрационные номера источников
imm - знак расширенного непосредственного поля
r - станция резервирования или буфер, которому назначена инструкция

Поля станции бронирования [ править ]

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

Поля статуса регистрации [ править ]

Qi - станция резервирования, результат которой должен быть сохранен в этом регистре (если пусто или 0, в этот регистр не предназначены никакие значения)

Этап 1: проблема [ править ]

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

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

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

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

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

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

Псевдокод ^[3] ^: 180
Состояние инструкции	Подожди до	Действия или бухгалтерия
Операция ФП	(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
- Если результат имеется, то: записать его в ЦБД и оттуда в регистры и любые станции резервирования, ожидающие этого результата
В противном случае, если инструкция была сохранением, то: на этом этапе запишите данные в память.

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

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

Подожди до

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

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

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

	∀  x  (  if   (  RegisterStat  [  x  ].  Qi   =   r  )   { 
		 regs  [  x  ]   ←   результат  ; 
		 RegisterStat  [  x  ].  Qi   =   0 
	 }); 
	  ∀  x  (  if   (  RS  [  x  ].  Qj   =   r  )   { 
		 RS  [  x  ].  Vj   ←   результат  ; 
		 RS  [  x  ].  Qj   ←   0  ;  
	 }); 
	  ∀  x  (  if   (  RS  [  x  ].  Qk   =   r  )   { 
		 RS  [  x  ].  Vk   ←   результат  ; 
		 RS  [  x  ].  Qk   ←   0  ; 
	 }); 
	  РС  [  р  ].   Занято   ←   нет  ;

Магазин

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

	Мем  [  RS  [  р  ] .   А  ]   ←   RS  [  р  ].   Вк  ; 
	  РС  [  р  ].   Занято   ←   нет  ;

Улучшения алгоритма [ править ]

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

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

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

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

Приложения и наследие [ править ]

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

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

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

См. также [ править ]

Ссылки [ править ]

^ Перейти обратно: ^а ^б ^с ^д Томасуло, Роберт Марко (январь 1967 г.). «Эффективный алгоритм использования нескольких арифметических единиц». Журнал исследований и разработок IBM . 11 (1). ИБМ: 25–33. дои : 10.1147/рд.111.0025 . ISSN 0018-8646 . S2CID 8445049 .
^ «Роберт Томасуло – лауреат премии» . Награды АКМ . АКМ . Проверено 8 декабря 2014 г.
^ Перейти обратно: ^а ^б ^с ^д ^Это Хеннесси, Джон Л.; Паттерсон, Дэвид А. (2012). Компьютерная архитектура: количественный подход . Уолтем, Массачусетс: Elsevier . ISBN 978-0123838728 .
^ «CSE P548 — Томасуло» (PDF) . Вашингтон.edu . Вашингтонский университет. 2006 год . Проверено 8 декабря 2014 г.
^ Руководство разработчика программного обеспечения для архитектур Intel 64 и IA-32 (отчет). Интел. Сентябрь 2014 года . Проверено 8 декабря 2014 г.
^ Йога, Адарш. «Различия между алгоритмом Томасуло и динамическим планированием в микроархитектуре Intel Core» . Пьяница . Проверено 4 апреля 2016 г.

Дальнейшее чтение [ править ]

Савард, Джон Дж. Г. (2018) [2014]. «Конвейерное и внеочередное выполнение» . четырехблок . Архивировано из оригинала 3 июля 2018 г. Проверено 16 июля 2018 г.

Внешние ссылки [ править ]

Динамическое планирование - алгоритм Томасуло в Wayback Machine (архивировано 25 декабря 2017 г.)
Java-апплет HASE, симулирующий алгоритм Томасуло

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

[2] «Роберт Томасуло – лауреат премии» . Награды АКМ . АКМ . Проверено 8 декабря 2014 г.

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

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

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

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

[1]

[2]

[3]

[4]

[5]

[6]