Алгоритм Томасуло — это аппаратный алгоритм компьютерной архитектуры для динамического планирования инструкций, который позволяет выполнять внеочередное выполнение и обеспечивает более эффективное использование нескольких исполнительных блоков. Он был разработан Робертом Томасуло из IBM в 1967 году и впервые был реализован в модуле с плавающей запятой IBM System/360 Model 91 . [1]
Основные нововведения алгоритма Томасуло включают переименование регистров в аппаратном обеспечении, станции резервирования для всех исполнительных устройств и общую шину данных (CDB), по которой вычисленные значения транслируются всем станциям резервирования, которым они могут понадобиться. Эти разработки позволяют улучшить параллельное выполнение инструкций, которые в противном случае останавливались бы при использовании табло или других более ранних алгоритмов.
Роберт Томасуло получил премию Экерта-Мокли в 1997 году за работу над алгоритмом. [2]
Ниже приведены концепции, необходимые для реализации алгоритма Томасуло:
Общая шина данных (CDB) соединяет станции резервирования непосредственно с функциональными блоками. По словам Томасуло, он «сохраняет приоритет, одновременно поощряя параллелизм». [1] : 33 Это имеет два важных эффекта:
Инструкции выполняются последовательно, так что последствия последовательности инструкций, такие как исключения , вызванные этими инструкциями, происходят в том же порядке, как и на процессоре с правильным порядком, независимо от того, что они выполняются вне очереди. порядке (т.е. непоследовательно).
Алгоритм Томасуло использует переименование регистров для правильного выполнения внеочередного выполнения. Все регистры станций общего назначения и резервирования содержат либо реальное значение, либо значение-заполнитель. Если реальное значение недоступно для регистра назначения на этапе выдачи, первоначально используется значение-заполнитель. Значение-заполнитель — это тег, указывающий, какая станция резервирования выдаст реальное значение. Когда модуль завершит работу и отправит результат в CDB, заполнитель будет заменен реальным значением.
Каждый функциональный блок имеет одну станцию резервирования. Станции резервирования содержат информацию, необходимую для выполнения одной инструкции, включая операцию и операнды. Функциональная единица начинает обработку, когда она свободна и когда все исходные операнды, необходимые для инструкции, действительны.
На практике могут быть исключения, для которых недостаточно информации о состоянии исключения, и в этом случае процессор может вызвать специальное исключение, называемое «неточным» исключением. Неточные исключения не могут возникать в реализациях по порядку , поскольку состояние процессора изменяется только в порядке программы (см. Исключения конвейера RISC ).
Программы, в которых возникают «точные» исключения, в которых можно определить конкретную инструкцию, вызвавшую исключение, могут перезапуститься или повторно выполниться в точке исключения. Однако те, у кого возникают «неточные» исключения, обычно не могут перезапустить или выполнить повторное выполнение, поскольку система не может определить конкретную инструкцию, которая приняла исключение.
Три этапа, перечисленные ниже, представляют собой этапы, через которые проходит каждая инструкция с момента ее выдачи до момента завершения ее выполнения.
На этапе выдачи инструкции выдаются для выполнения, если все операнды и станции резервирования готовы или они остановлены. На этом этапе регистры переименовываются, что устраняет опасности WAR и WAW.
На этапе выполнения выполняются командные операции. На этом этапе инструкции задерживаются до тех пор, пока не станут доступны все их операнды, что исключает опасность необработанных данных. Корректность программы поддерживается за счет эффективного расчета адресов для предотвращения опасностей, связанных с памятью.
На этапе записи результатов результаты операций ALU записываются обратно в регистры, а операции сохранения записываются обратно в память.
Концепции станций резервирования, переименования регистров и общей шины данных в алгоритме Томасуло представляют собой значительный прогресс в разработке высокопроизводительных компьютеров.
Станции резервирования берут на себя ответственность за ожидание операндов при наличии зависимостей данных и других несоответствий, таких как различное время доступа к хранилищу и скорость передачи данных, тем самым освобождая функциональные блоки. Это улучшение устраняет длительные задержки с плавающей запятой и доступ к памяти. В частности, алгоритм более толерантен к промахам в кэше. Кроме того, программисты освобождаются от необходимости реализации оптимизированного кода. Это результат совместной работы общей шины данных и станции резервирования для сохранения зависимостей, а также поощрения параллелизма. [1] : 33
Отслеживая операнды для инструкций на станциях резервирования и переименовывая регистры на аппаратном уровне, алгоритм сводит к минимуму чтение после записи (RAW) и устраняет риски компьютерной архитектуры, связанные с записью после записи (WAW) и записью после чтения (WAR) . Это повышает производительность за счет сокращения потерь времени, которое в противном случае потребовалось бы для остановок. [1] : 33
Не менее важным улучшением алгоритма является то, что проектирование не ограничивается конкретной структурой конвейера. Это улучшение позволяет более широко использовать алгоритм процессорами, обрабатывающими множество задач. Кроме того, алгоритм легко расширяется для включения спекуляций ветвей. [3] : 182
Алгоритм Томасуло за пределами IBM не использовался в течение нескольких лет после его реализации в архитектуре System/360 Model 91. Однако в 1990-е годы его использование значительно возросло по трем причинам:
Многие современные процессоры реализуют схемы динамического планирования, производные от оригинального алгоритма Томасуло, включая популярные чипы Intel x86-64 . [5] [ не удалось пройти проверку ] [6]