Войти
Устранение неоднозначности памяти - это набор методов, используемых высокопроизводительными микропроцессорами, выполняемыми вне очереди, которые выполняют инструкции доступа к памяти (загрузки и сохранения) вне программного порядка. Механизмы устранения неоднозначности в памяти, реализованные с использованием цифровой логики внутри ядра микропроцессора, обнаруживают истинные зависимости между операциями с памятью во время выполнения и позволяют процессору восстанавливаться, когда зависимость была нарушена. Они также устраняют ложные зависимости памяти и обеспечивают больший параллелизм на уровне инструкций, обеспечивая безопасное выполнение загрузок и сохранений вне очереди.
При попытке выполнить инструкции не по порядку микропроцессор должен учитывать истинные зависимости между инструкциями. Например, рассмотрим простую истинную зависимость:
1: add $1, $2, $3 # R1 lt;= R2 + R3 2: add $5, $1, $4 # R5 lt;= R1 + R4 (dependent on 1)
В этом примере addинструкция в строке 2 зависит от addинструкции в строке 1, потому что регистр R1 является исходным операндом операции сложения в строке 2. Операция addв строке 2 не может выполняться, пока не addзавершится строка 1. В этом случае зависимость статическая и легко определяется микропроцессором, потому что источники и назначения являются регистрами. Регистр назначения команды в addстроке 1 ( R1) является частью кодирования команды, и поэтому может быть определен микропроцессором на ранней стадии, на этапе декодирования конвейера. Точно так же исходные регистры addинструкции в строке 2 ( R1и R4) также кодируются в самой инструкции и определяются при декодировании. Чтобы соблюдать эту истинную зависимость, логика планировщика микропроцессора будет выдавать эти инструкции в правильном порядке (сначала инструкция 1, затем инструкция 2), так что результаты 1 будут доступны, когда они потребуются инструкции 2.
Сложности возникают, когда зависимость не поддается статическому определению. Такие нестатические зависимости возникают с инструкциями памяти (загрузка и сохранение), потому что расположение операнда может быть косвенно определено как регистровый операнд, а не прямо указано в самой кодировке инструкции.
1: store $1, 2($2) # Mem[R2+2] lt;= R1 2: load $3, 4($4) # R3 lt;= Mem[R4+4] (possibly dependent on 1, possible same address as above)
Здесь инструкция сохранения записывает значение в ячейку памяти, указанную значением в адресе (R2 + 2), а инструкция загрузки считывает значение в ячейке памяти, указанной значением в адресе (R4 + 4). Микропроцессор не может статически определить перед выполнением, являются ли ячейки памяти, указанные в этих двух инструкциях, разными или одинаковыми, поскольку эти ячейки зависят от значений в R2 и R4. Если расположение отличается, инструкции независимы и могут быть успешно выполнены вне очереди. Однако, если местоположения совпадают, то инструкция загрузки зависит от хранилища для получения своего значения. Это известно как неоднозначная зависимость.
Выполнение загрузок и сохранений не по порядку может привести к неверным результатам, если зависимая пара загрузка / сохранение была выполнена не по порядку. Рассмотрим следующий фрагмент кода, представленный в сборке MIPS :
1: div $27, $20 2: sw $27, 0($30) 3: lw $08, 0($31) 4: sw $26, 0($30) 5: lw $09, 0($31)
Предположим, что логика планирования выдаст инструкцию исполнительному блоку, когда все его операнды регистра будут готовы. Далее предположим, что регистры $30и $31готовы: значения в $30и $31были вычислены давно и не изменились. Однако предписание $27не готово: его значение все еще вычисляется divинструкцией (целочисленное деление). Наконец, предположим, что регистрируется $30и $31хранится одно и то же значение, и, следовательно, все загрузки и сохранения в фрагменте обращаются к одному и тому же слову памяти.
В этой ситуации sw $27, 0($30)инструкция в строке 2 не готова к выполнению, но lw $08, 0($31)инструкция в строке 3 готова. Если процессор разрешает выполнение lwинструкции до sw, загрузка считывает старое значение из системы памяти; однако он должен был прочитать значение, которое только что было записано там sw. Загрузка и сохранение выполнялись не в программном порядке, но между ними была нарушена зависимость памяти.
Кроме того, предположим, что регистр $26 является готов. sw $26, 0($30)Инструкция по линии 4 также готова выполнить, и он может выполняться до предыдущих lw $08, 0($31)на линии 3. Если это произойдет, то lw $08, 0($31)инструкция прочитает неправильное значение из памяти системы, так как позже команда сохранения написала свое значение там до нагрузки выполнен.
Зависимости памяти бывают трех видов:
Три зависимости показаны в предыдущем сегменте кода (воспроизведены для ясности):
1: div $27, $20 2: sw $27, 0($30) 3: lw $08, 0($31) 4: sw $26, 0($30) 5: lw $09, 0($31)
lw $08, 0($31)Инструкция по линии 3 имеет RAW зависимости от sw $27, 0($30)инструкции по линии 2, и lw $09, 0($31)инструкция по линии 5 имеет зависимость RAW на sw $26, 0($30)инструкции по линии 4. Обе команды загрузки прочитать адрес памяти, который хранит предыдущее написал. Хранилища были самыми последними производителями для этого адреса памяти, и нагрузки считывают значение этого адреса памяти.sw $26, 0($30)Инструкция по линии 4 имеет WAR зависимость от lw $08, 0($31)инструкции по линии 3, так как он записывает адрес памяти, что предшествующие нагрузки считывают с.sw $26, 0($30)Инструкция по линии 4 имеет WAW зависимость от sw $27, 0($30)инструкции по линии 2, поскольку оба магазина записи в тот же адрес памяти.Современные микропроцессоры используют следующие механизмы, реализованные на аппаратном уровне, для разрешения неоднозначных зависимостей и восстановления, когда зависимость была нарушена.
Значения из инструкций хранилища не передаются в систему памяти (в современных микропроцессорах, кэш ЦП ) при выполнении. Вместо этого инструкции сохранения, включая адрес памяти и данные сохранения, буферизируются в очереди хранения до тех пор, пока не достигнут точки вывода из эксплуатации. Когда магазин уходит в отставку, он затем записывает его значение в системе памяти. Это позволяет избежать проблем зависимости WAR и WAW, показанных в приведенном выше фрагменте кода, когда более ранняя загрузка получает неправильное значение из системы памяти, потому что более позднему хранилищу было разрешено выполняться до более ранней загрузки.
Кроме того, буферизация хранилищ до вывода из эксплуатации позволяет процессорам спекулятивно выполнять инструкции хранилища, которые следуют инструкции, которая может вызвать исключение (например, загрузку неверного адреса, деление на ноль и т. Д.) Или команду условного перехода, направление которой (принятое или нет взяты) пока не известно. Если вызывающая исключение инструкция не была выполнена или направление ветвления было предсказано неверно, процессор будет выбирать и выполнять инструкции по «неправильному пути». Эти инструкции вообще не должны были выполняться; условие исключения должно было произойти до того, как была выполнена какая-либо из предполагаемых инструкций, или ветвь должна была пойти в другом направлении и вызвать выборку и выполнение различных инструкций. Процессор должен "отбросить" любые результаты неверного пути, предположительно выполненных инструкций, когда он обнаруживает исключение или неверное предсказание перехода. Сложность для хранилищ состоит в том, что любые хранилища на неверном или неверно предсказанном пути не должны передавать свои значения в систему памяти; если бы хранилища зафиксировали свои значения, было бы невозможно "выбросить" фиксацию, и состояние памяти машины было бы искажено данными из инструкции сохранения, которая не должна была выполняться.
Таким образом, без буферизации хранилища хранилища не могут выполняться до тех пор, пока все предыдущие, возможно, вызывающие исключение инструкции не будут выполнены (и не вызвали исключение) и не станут известны все предыдущие направления ветвления. Принуждение хранилищ ждать, пока не станут известны направления ветвления и исключения, значительно снижает агрессивность нарушения порядка и ограничивает ILP ( параллелизм на уровне инструкций ) и производительность. При буферизации хранилища хранилища могут выполняться перед вызывающими исключение или неразрешенными инструкциями ветвления, буферизуя свои данные в очереди хранилища, но не фиксируя свои значения до выхода из эксплуатации. Это предотвращает фиксацию значений хранилищами на неверно предсказанных или неверных путях в системе памяти, в то же время предлагая повышенную ILP и производительность от полного выполнения хранилищ вне очереди.
Буферизация хранилищ до выхода на пенсию позволяет избежать зависимостей WAW и WAR, но создает новую проблему. Рассмотрим следующий сценарий: магазин выполняет и буферизует свой адрес и данные в очереди магазина. Через несколько инструкций выполняется загрузка, которая читает из того же адреса памяти, по которому только что записано хранилище. Если загрузка считывает свои данные из системы памяти, она считывает старое значение, которое было бы перезаписано предыдущим хранилищем. Данные, полученные при загрузке, будут неверными.
Чтобы решить эту проблему, процессоры используют метод, называемый пересылкой от хранилища к загрузке с использованием очереди хранилища. В дополнение к буферизации хранилищ до вывода из эксплуатации, очередь хранилищ служит второй цели: пересылка данных из завершенных, но еще не выведенных из эксплуатации («находящихся в эксплуатации») хранилищ для последующих загрузок. Вместо простой очереди FIFO, очередь хранилища на самом деле представляет собой Content-Addressable Memory (CAM), поиск в которой осуществляется с использованием адреса памяти. Когда выполняется загрузка, она ищет в очереди хранилища оперативные хранилища по тому же адресу, который логически расположен раньше в программном порядке. Если подходящее хранилище существует, загрузка получает значение данных из этого хранилища, а не из системы памяти. Если подходящего хранилища нет, загрузка обращается к системе памяти как обычно; любые предшествующие подходящие магазины должны быть уже выведены из эксплуатации и зафиксированы в своих значениях. Этот метод позволяет загрузкам получать правильные данные, если их хранилище производителя завершено, но еще не закрыто.
В очереди на хранение может присутствовать несколько записей по адресу памяти загрузки. Чтобы справиться с этим случаем, очередь хранилища кодируется по приоритету, чтобы выбрать последнее хранилище, которое логически предшествует загрузке в программном порядке. Определение того, какое хранилище является « самым последним», может быть достигнуто путем прикрепления какой-либо временной метки к инструкциям по мере их выборки и декодирования или, в качестве альтернативы, путем знания относительного положения (слота) загрузки по отношению к самым старым и новейшим хранилищам в очередь магазина.
Современные ЦП, вышедшие из строя, могут использовать ряд методов для обнаружения нарушения зависимости RAW, но все методы требуют отслеживания нагрузки в полете от выполнения до вывода из эксплуатации. Когда загрузка выполняется, она обращается к системе памяти и / или очереди хранилища, чтобы получить значение своих данных, а затем его адрес и данные буферизируются в очереди загрузки до вывода из эксплуатации. Очередь загрузки аналогична по структуре и функциям очереди в хранилище, и на самом деле в некоторых процессорах она может быть объединена с очередью хранилища в единую структуру, называемую очередью загрузки-хранилища или LSQ. Для выявления нарушений RAW-зависимости используются или были предложены следующие методы:
При использовании этого метода очередь загрузки, как и очередь хранилища, представляет собой CAM, поиск которого выполняется с использованием адреса доступа к памяти, и отслеживает все нагрузки в полете. Когда хранилище выполняется, оно ищет в очереди загрузки завершенные загрузки с того же адреса, которые логически находятся позже в программном порядке. Если такая подходящая нагрузка существует, она должна быть выполнена до сохранения и, таким образом, считывать некорректное старое значение из системы памяти / очереди хранилища. Любые инструкции, которые использовали значение нагрузки, также использовали неверные данные. Для восстановления, если такое нарушение обнаружено, нагрузка помечается как «нарушенная» в буфере вывода из эксплуатации. Хранилище остается в очереди хранилища и в буфере вывода из эксплуатации и обычно закрывается, передавая свое значение системе памяти при закрытии. Однако, когда нарушенная нагрузка достигает точки списания, процессор очищает конвейер и перезапускает выполнение с инструкции загрузки. На этом этапе все предыдущие хранилища передали свои значения в систему памяти. Команда загрузки теперь будет считывать правильное значение из системы памяти, и все зависимые инструкции будут повторно выполняться с использованием правильного значения.
Этот метод требует ассоциативного поиска очереди загрузки при каждом выполнении хранилища, что потребляет мощность схемы и может оказаться трудным временным путем для больших очередей загрузки. Однако он не требует дополнительных портов памяти ( кеша ) и не создает конфликтов ресурсов с другими выполняемыми нагрузками или хранилищами.
С помощью этого метода инструкции загрузки, которые были выполнены не по порядку, повторно выполняются (они обращаются к системе памяти и читают значение со своего адреса во второй раз), когда они достигают точки выхода из эксплуатации. Поскольку загрузка теперь является инструкцией по удалению, она не зависит от какой-либо инструкции, все еще находящейся в работе; все предшествующие хранилища передали свои значения в систему памяти, поэтому любое значение, считываемое из системы памяти, гарантированно будет правильным. Значение, считанное из памяти во время повторного выполнения, сравнивается со значением, полученным при первом выполнении загрузки. Если значения совпадают, исходное значение было правильным и никаких нарушений не произошло. Если значение повторного выполнения отличается от исходного значения, произошло нарушение RAW и конвейер должен быть очищен, потому что инструкции, зависящие от загрузки, использовали неправильное значение.
Этот метод концептуально проще, чем поиск в очереди загрузки, и он исключает второй CAM и его энергоемкий поиск (теперь очередь загрузки может быть простой очередью FIFO). Поскольку загрузка должна повторно обращаться к системе памяти непосредственно перед выводом из эксплуатации, доступ должен быть очень быстрым, поэтому в этой схеме используется быстрый кэш. Однако независимо от того, насколько быстрым является кэш, второй доступ к системе памяти для каждой неупорядоченной инструкции загрузки увеличивает задержку вывода команд и увеличивает общее количество обращений к кэш-памяти, которые должны выполняться процессором. Дополнительный доступ к кэш-памяти во время списания может быть удовлетворен повторным использованием существующего порта кэш-памяти; однако это создает конкуренцию за ресурсы порта с другими нагрузками и хранилищами в процессоре, которые пытаются выполнить, и, таким образом, может вызвать снижение производительности. В качестве альтернативы можно добавить дополнительный порт кеша только для устранения неоднозначности нагрузки, но это увеличивает сложность, мощность и площадь кеша. Некоторые недавние работы (Roth 2005) показали способы отфильтровать множество загрузок от повторного выполнения, если известно, что нарушения зависимости RAW не могло произойти; такой метод помог бы или устранил такую задержку и конкуренцию за ресурсы.
Незначительное преимущество этой схемы (по сравнению с поиском в очереди загрузки) заключается в том, что она не будет отмечать нарушение зависимости RAW и запускать очистку конвейера, если хранилище, которое вызвало бы нарушение зависимости RAW (адрес хранилища совпадает с текущим адрес загрузки) имеет значение данных, которое соответствует значению данных, уже находящемуся в кеше. В схеме поиска очереди загрузки необходимо добавить дополнительное сравнение данных к оборудованию поиска очереди загрузки, чтобы предотвратить такую очистку конвейера.
ЦП, которые полностью поддерживают выполнение загрузок и сохранений вне очереди, должны иметь возможность обнаруживать нарушения зависимости RAW, когда они происходят. Однако многие ЦП избегают этой проблемы, заставляя все загрузки и сохранения выполняться по порядку или поддерживая только ограниченную форму выполнения загрузки / сохранения вне очереди. Этот подход предлагает более низкую производительность по сравнению с поддержкой полного выполнения загрузки / сохранения вне очереди, но он может значительно снизить сложность ядра выполнения и кешей.
Первый вариант, обеспечивающий выполнение загрузок и сохранений в порядке, позволяет избежать зависимостей от RAW, поскольку нет возможности выполнения загрузки до сохранения ее производителем и получения неверных данных. Другая возможность - эффективно разбить загрузку и сохранение на две операции: создание адреса и доступ к кешу. С помощью этих двух отдельных, но связанных операций ЦП может разрешить загрузкам и хранилищам доступ к системе памяти только после того, как все предыдущие загрузки и хранилища сгенерировали свои адреса и занесли их в буфер в LSQ. После генерации адреса больше нет неоднозначных зависимостей, так как все адреса известны, и поэтому зависимые загрузки не будут выполняться до тех пор, пока не завершатся их соответствующие хранилища. Эта схема по-прежнему допускает некоторую "неупорядоченность" - операции генерации адресов для любых загрузок и хранилищ в полете могут выполняться не по порядку, и после того, как адреса были сгенерированы, доступ к кешу для каждой загрузки или хранилища может происходят в любом порядке, который соблюдает (теперь известные) истинные зависимости.
Процессоры, которые полностью поддерживают выполнение загрузки / сохранения вне очереди, могут использовать дополнительный связанный метод, называемый прогнозированием зависимости от памяти, чтобы попытаться предсказать истинные зависимости между загрузками и хранилищами до того, как станут известны их адреса. Используя этот метод, процессор может предотвратить выполнение нагрузок, которые, согласно прогнозам, зависят от оперативного хранилища, до завершения этого хранилища, избегая нарушения зависимости RAW и, таким образом, избегая очистки конвейера и возникающего снижения производительности. См. Статью о прогнозировании зависимости от памяти для получения более подробной информации.
