Алгоритм Томасуло. реферат_Томасуло_АВП. Алгоритм Томасуло. Принцип работы
 Скачать 36.66 Kb.
|
|
Министерство образования Республики Беларусь Учреждение образования БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИНФОРМАТИКИ И РАДИОЭЛЕКТРОНИКИ Факультет компьютерных систем и сетей Кафедра ЭВМ Реферат на тему: Алгоритм Томасуло. Принцип работы Выполнил: Проверил: Минск, 2022 СОДЕРЖАНИЕПредыстория формирования алгоритма 3 История появления алгоритма 3 Состав и схема процессора 4 Концепции реализации 5 Переименование регистров и станции резервирования 6 Жизненный цикл инструкций 7 Достоинства и недостатки алгоритма. Решение конфликтов 8 Компьютер IBM System/360 Model 91 9 ЗАКЛЮЧЕНИЕ 10 СПИСОК ЛИТЕРАТУРЫ 11 Предыстория формирования алгоритма История развития архитектур процессоров началась с циклического процесса последовательной обработки данных, описанного впервые Джоном фон Нейманом. Процесс заключался в последовательном осуществлении однотипного набора операций, составляющих выполнение команды. Очевидным недостатком такого подхода является нецелесообразное распределение времени работы комплекса функциональных модулей процессора, пока один или небольшое число модулей выполняет свою функцию во время обработки инструкций, остальные модули бездействуют. С целью повышения быстродействия, в центральный процессор была внедрена конвейерная архитектура. Принципом которой служит параллельное выполнение команд процессором, обработка инструкций разделена на последовательность стадий, которые выполняются на всех ступенях конвейера параллельно. Результаты работы каждой из стадий передаются через ячейки памяти на следующую стадию, и так до тех пор, пока инструкция не будет выполнена. Подобная организация процессора, при некотором увеличении среднего времени выполнения каждой инструкции, тем не менее, обеспечивает значительный рост производительности за счёт высокой частоты завершения выполнения инструкций. Однако наличие зависимостей между инструкциями, выполняемыми процессором при конвейерной архитектуре, приводит к возникновению конфликтов (hazard). Конфликт – это некоторая ситуация, при которой невозможно запустить выполнение следующей инструкции непосредственно за предыдущей, без нарушения критерия сохранения корректности программы. Конфликты подразделяются на три группы: 1. Структурные конфликты (разным инструкциям требуется доступ к одному ресурсу процессора), 2. Конфликты по данным (следствие наличия зависимостей по данным именам), 3. Конфликты по управлению (следствие наличия зависимостей по управлению). Изначально конфликты решались программно, но из-за существенных потерь в производительности и удобстве написания кода, для решения конфликтов начали изменять аппаратную часть. Первым аппаратным решением исключения всех конфликтов в архитектуре стал алгоритм Томасуло. История появления алгоритма Алгоритм Томасуло — это аппаратный алгоритм компьютерной архитектуры для динамического планирования инструкций, который допускает выполнение вне очереди и позволяет более эффективно использовать несколько исполнительных блоков. Он был разработан Робертом Томасуло в IBM в 1967 году и впервые был реализован в модуле операций с плавающей запятой IBM System / 360 Model 91. Основные нововведения алгоритма Томасуло включают переименование регистров в аппаратном обеспечении, станции резервирования для всех исполнительных блоков и общую шину данных (CDB), по которой вычисленные значения транслируются на все станции резервирования, которые могут в них нуждаться. Эти разработки позволяют улучшить параллельное выполнение инструкций, которые в противном случае остановились бы при использовании более ранних алгоритмов. Роберт Томасуло получил премию Эккерта – Мочли в 1997 году за свою работу над алгоритмом. Состав и схема процессора Схема процессора приведена в дополняющей доклад презентации. Состав процессора: - очередь планирования (Instruction queue) [ОП] - регистровый файл (FP Registers) [РФ] - станции резервирования (Reserve Station) [СР] - простое вещественное устройство (FP adder) - сложное вещественное устройство (FP Muliplier) - общая шина данных (Common Data Bus) [ОШД] - устройство вычисление адреса (Address Unit) - буфера загрузки (Load buffer) - буфера сохранения (Store buffer) - устройство работы с памятью (Memory Unit)\ Команды выполняются по очереди из модуля инструкций (Instruction queue) [ОП] и распределяются по станциям резервирования, привязанным за исполнительными модулями, а именно, простым вещественным устройством (FP adder) и сложным вещественным устройством (FP Muliplier). Для формирования адреса служит устройство вычисления адреса (Address Unit), и для работы с памятью - устройство работы с памятью (Memory Unit). Буферы загрузки и сохранения (Load buffer, Store buffer) служат для хранения поля адреса и поля адреса с ссылкой на СР соответственно. Регистровый файл (FP Registers) [РФ] и станции резервирования (Reserve Station) [СР] соединены со всеми исполнительными модулями напрямую по общей шине данных (Common Data Bus) [ОШД]. Концепции реализации Ниже приведены концепции необходимые для реализации алгоритма: 1. Общая шина данных (ОШД) соединяет станции резервирования напрямую с функциональными блоками. По словам Томасуло, он «сохраняет приоритет, поощряя параллелизм». Это имеет два важных эффекта: - Функциональные блоки могут получить доступ к результату любой операции без использования регистра с плавающей запятой, что позволяет нескольким блокам, ожидающим результата, продолжить работу, не дожидаясь разрешения конфликта за доступ к портам чтения регистров. - Обнаружение конфликтов и контроль исполнения разделены. Не отдельный специализированный модуль распознавания конфликтов, а станции резервирования контролируют, когда может выполняться инструкция. 2. Порядок выполнения инструкций не такой как в исполнении классического конвейера, инструкции планируются и выполняются только тогда, когда это позволяют сделать соответствующие модули процессора. Благодаря чему не возникает никаких конфликтов в распределении управления и данных в процессоре. 3. Переименование регистров в алгоритме Томасуло используется для корректного внеочередного выполнения инструкций. Все универсальные регистры и регистры станций резервирования содержат либо реальное значение, либо ссылку. Если реальное значение недоступно для регистра на этапе выдачи, используется ссылка, указывающая на регистр, где это значение должно появиться после вычисления. Когда вычисления закончатся, результат по ОШД, будет записан в нужную станцию резервирования. Переименование регистров и станции резервирования Файл переименования: Файл переименования находится в регистровом файле, содержит имена переименованных регистров. Он состоит из двух полей: 1. Регистр, 2. Ссылка. Если значение находится в регистре, ссылка равна нулю, если нет, ссылка указывает на станцию резервирования, прилагаемую к модулю, вычисляющему соответствующее значение. Станция резервирования: Каждый функциональный блок имеет одну станцию резервирования. Станции резервирования содержат информацию, необходимую для выполнения инструкций, включая операцию и операнды. Функциональный модуль начинает обработку, когда он свободен и когда все исходные операнды в СР, необходимые для выполнения инструкции, реальны. Станции резервирования берут на себя ответственность за ожидание операндов при наличии зависимостей данных и других несоответствий, таких как изменение времени доступа к памяти и скорости цепи, тем самым освобождая функциональные блоки. Это улучшение преодолевает длительные задержки обращения к памяти. В частности, алгоритм более терпим к промахам кэша. Кроме того, программисты освобождаются от реализации оптимизированного кода. Это результат совместной работы общей шины данных и станций резервирования. Станция резервирования состоит из двух дескрипторов операндов, дескриптор операнда содержит значение операнда, или ссылку, если значение операнда на момент планирования еще не вычислено, ссылка является номером станции резервирования, которая содержит инструкцию вычисляемую необходимый операнд. Таблица состояния станции резервирования (приведена в презентации): RS – порядковый номер СР и устройство к которому подключена СР RS tag – уникальный номер СР Busy – флаг занята СР или свободен Op – поле операции Vi, Vj – значение 1 и 2 операнда Qi, Qj – ссылки на другие СР, соответствующих операндов A – поле адреса Жизненный цикл инструкций Чтобы описать жизненный цикл инструкции в Алгоритме Томасуло следует определить разницу этапов исполнения алгоритма с этапами классического конвейера. Классический конвейер: 1. выборка инструкции 2. выборка операндов 3. исполнение 4. сохранение результата Алгоритм Томасуло: 1. выборка инструкции 2. планирование инструкции 3. ожидание готовности операндов 4. исполнение 5. сохранение результата Очевидная разница заключается в разбиении шага выборки операндов на два шага: Планирование инструкций и Ожидание готовности операндов. Эти шаги предполагают непосредственное участие станций резервирования и переименованных регистров. Выборка инструкций происходит в программном порядке по одной инструкции за такт с вершины очереди планирования [ОП], после чего происходит ее планирование: Декодирование Назначение на исполнительное устройство Выборка операндов На этапе назначения инструкции на исполнительное устройство, возможен вариант отсутствия свободной станции резервирования для планирования, в таком случае инструкция возвращается в очередь планирования (ОП) и ожидает освобождения станции резервирования (СР). На этапе выборки операндов возможна ситуация, когда операнды еще не были вычислены, в таком случае в станции резервирования заносятся ссылки на вычисляемые значения. Передача вычисленного операнда происходит по ОШД вместе с номером СР, которая его содержала, каждая станция резервирования слушает Шину данных (ОШД) и сравнивает значение номера передаваемого по ней операнда с ожидаемым номером. Если номера совпадают, станция резервирования забирает соответствующий операнд с ОШД. Когда все реальные операнды находятся в СР, инструкция отправляется на исполнение в соответствующий станции резервирования исполнительный модуль. После чего результаты сохраняются в регистровом файле и подвергаются дальнейшим операциям. Обработка и порядок исполнения инструкций загрузки и сохранения: Инструкции загрузки предполагают вычисление адреса и последующую загрузки из этого адреса, инструкции сохранения же вычисление адреса, ожидание готовности операндов и сохранение по адресу. Буфер загрузки содержит поле адреса, буфер сохранения – поле адреса и ссылку на СР. Исполнение инструкций определяется наличием зависимостей между инструкциями по ячейкам памяти. На первом этапе вычисляются адреса ячеек, после чего, инструкция загрузки ожидает завершения всех предшествующих инструкций сохранения по данному адресу, а инструкция сохранения ожидает завершения всех предшествующих инструкций загрузки и сохранения по данному адресу. Достоинства и недостатки алгоритма. Решение конфликтов За счет отслеживания операндов для инструкций на станциях резервирования и запуска инструкции только по их готовности алгоритм исключает конфликт чтения после записи (RAW). Конфликты записи после записи (WAW) и записи после чтения (WAR) разрешаются благодаря воссозданию графа зависимостей по данным между инструкциями, что достигается благодаря переименованию регистров на аппаратном уровне и использованию станций резервирования. Алгоритм Томасуло позволил значительно повысить пропускную способность и уменьшить время простоя процессоров, но достигалось это значительным увеличением аппаратных затрат на реализацию дополнительных устройств. Компьютер IBM System/360 Model 91 IBM System/360 Model 91 — модель серии компьютеров IBM System/360 компании IBM. Объявлена в 1964 году как конкурент суперкомпьютеру CDC 6600 компании Control Data Corporation. Модель 91 была самой производительной в линейке IBM S/360. Компьютер поддерживал выполнение инструкций не по порядку, а в процессоре был впервые реализован алгоритм Томасуло. В качестве операционной системы он использовал OS/360. Он был разработан для высокоскоростной обработки данных в научных целях. Это включало исследование космоса, теоретическую астрономию, субатомную физику и глобальное прогнозирование погоды. Первая модель 91 использовалась в Центре космических полетов НАСА и в то время была самым мощным компьютером в эксплуатации. Компьютер был способен выполнять до 16,6 млн инструкций в секунду. Процессор System/360 - 32-разрядный, с комплексным набором команд. Программисту доступны 16 32-раздядных регистров общего назначения (GPR0-GPR15), 16 32-раздядных регистров управления процессором (CR0-CR15) и 64-раздядный регистр состояние программы (PSW), содержащий указатель инструкции и некоторую другую информацию. Инструкции процессора должны быть выровнены на чётные адреса. Длинна инструкции варьируется от от 2 до 6 байт с шагом в два байта и определяется первыми двумя битами. Процессор имеет механизм обработки прерываний от устройств ввода-вывода, прерываний внешних устройств (например таймера), исключений в программе, исключений защиты, ошибок оборудования и системных вызовов. При возникновении прерывания процессор сохраняет текущее слово сотояния программы (PSW) по фиксированному адресу (зависящему от класса прерывания), и загружает новый PSW по другому адресу, после чего продолжает нормальное выполнение программы. ЗАКЛЮЧЕНИЕ Несмотря на то, что анонсирован алгоритм был в 1967 году, основное активное использование началось только в 1990 годы, поскольку к этому времени объем инструкций, требуемых выполнения, возрос до степени, предполагающей возможность немалых затрат на аппаратную составляющую, а также после появления кэша, способность алгоритма поддерживать параллелизм во время непредсказуемого времени загрузки стала ценным свойством процессора. В том числе аппаратное решение конфликтов, значительно превосходило требующее немалых усилий и времени аналогичное программное решение. Подводя итог, можно назвать закономерным появление такого алгоритма, поскольку неконвейерная и конвейерная архитектуры несли в себе очевидные проблемы в различных направлениях. Алгоритм Томасуло позволил удачно решить структурные конфликты и конфликты по данным, но решение конфликта управления по-прежнему допускало глобальные потери в производительности, что привело к созданию в будущем замены алгоритму, в лице спекулятивных суперскалярных процессоров с блоком предсказания переходов. Однако они берут начало именно с динамического суперскалярного алгоритма Томасуло. СПИСОК ЛИТЕРАТУРЫ Wikipedia [Электронный ресурс]. – Электронные данные. – Режим доступа: https://en.wikipedia.org/wiki/Tomasulo_algorithm Prof. Juurlink [Видеоматериал]. – Электронные данные. – Режим доступа: https://www.youtube.com/watch?v=y-N0Dsc9LmU Перцев Д.Ю.[Документ]. – Презентация на тему Алгоритм Томасуло. Osdev [Электронный ресурс]. – Электронные данные. – Режим доступа: https://osdev.fandom.com/ru/wiki/Архитектура_IBM_System/360 Wikiru [Электронный ресурс]. – Электронные данные. – Режим доступа: https://www.wikiru.wiki/blog/en/IBM_System/360_Model_91 Wikipedia [Электронный ресурс]. – Электронные данные. – Режим доступа: https://ru.wikipedia.org/wiki/IBM_System/360_Model_91 |